// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.skyframe;
import com.google.common.base.MoreObjects;
import com.google.common.base.MoreObjects.ToStringHelper;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import com.google.devtools.build.lib.util.Preconditions;
import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
* Data the NodeEntry uses to maintain its state before it is done building. It allows the
* {@link NodeEntry} to keep the current state of the entry across invalidation and successive
* evaluations. A done node does not contain any of this data. However, if a node is marked dirty,
* its entry acquires a new {@code BuildingState} object, which persists until it is done again.
*
*
This class should be considered a private inner class of {@link NodeEntry} -- no other
* classes should instantiate a {@code BuildingState} object or call any of its methods directly.
* It is in a separate file solely to keep the {@link NodeEntry} class readable. In particular, the
* caller must synchronize access to this class.
*
*
This class is public only for the benefit of alternative graph implementations outside of the
* package.
*/
@ThreadCompatible
public class BuildingState {
/**
* During its life, a node can go through states as follows:
*
*
Non-existent
*
Just created ({@code evaluating} is false)
*
Evaluating ({@code evaluating} is true)
*
Done (meaning this buildingState object is null)
*
Just created (when it is dirtied during evaluation)
*
Reset (just before it is re-evaluated)
*
Evaluating
*
Done
*
*
*
The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsent} and
* {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to
* call both methods in that order if they want to create a node. The second method calls
* {@link #startEvaluating}, which transitions the current node to the "evaluating" state and
* returns true only the first time it was called. A caller that gets "true" back from that call
* must start the evaluation of this node, while any subsequent callers must not.
*
*
An entry is set to "evaluating" as soon as it is scheduled for evaluation. Thus, even a
* node that is never actually built (for instance, a dirty node that is verified as clean) is
* in the "evaluating" state until it is done.
*/
private boolean evaluating = false;
/**
* The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes
* into either the state {@link DirtyState#CHECK_DEPENDENCIES} or
* {@link DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node
* was itself changed or not. A non-null {@code dirtyState} indicates that the node
* {@link #isDirty} in some way.
*/
private DirtyState dirtyState = null;
/**
* The number of dependencies that are known to be done in a {@link NodeEntry}. There is a
* potential check-then-act race here, so we need to make sure that when this is increased, we
* always check if the new value is equal to the number of required dependencies, and if so, we
* must re-schedule the node for evaluation.
*
*
There are two potential pitfalls here: 1) If multiple dependencies signal this node in
* close succession, this node should be scheduled exactly once. 2) If a thread is still working
* on this node, it should not be scheduled.
*
*
The first problem is solved by the {@link #signalDep} method, which also returns if the
* node needs to be re-scheduled, and ensures that only one thread gets a true return value.
*
*
The second problem is solved by first adding the newly discovered deps to a node's
* {@link #directDeps}, and then looping through the direct deps and registering this node as a
* reverse dependency. This ensures that the signaledDeps counter can only reach
* {@link #directDeps}.size() on the very last iteration of the loop, i.e., the thread is not
* working on the node anymore. Note that this requires that there is no code after the loop in
* {@code ParallelEvaluator.Evaluate#run}.
*/
private int signaledDeps = 0;
/**
* Direct dependencies discovered during the build. They will be written to the immutable field
* {@code ValueEntry#directDeps} and the dependency group data to {@code ValueEntry#groupData}
* once the node is finished building. {@link SkyFunction}s can request deps in groups, and these
* groupings are preserved in this field.
*/
private final GroupedList directDeps = new GroupedList<>();
/**
* The set of reverse dependencies that are registered before the node has finished building.
* Upon building, these reverse deps will be signaled and then stored in the permanent
* {@code ValueEntry#reverseDeps}.
*/
// TODO(bazel-team): Remove this field. With eager invalidation, all direct deps on this dirty
// node will be removed by the time evaluation starts, so reverse deps to signal can just be
// reverse deps in the main ValueEntry object.
private Object reverseDepsToSignal = ImmutableList.of();
private List