// 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.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
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.KeyToConsolidate.Op;
import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
/**
* In-memory implementation of {@link NodeEntry}. All operations on this class are thread-safe.
*
*
Care was taken to provide certain compound operations to avoid certain check-then-act races.
* That means this class is somewhat closely tied to the exact Evaluator implementation.
*
*
Consider the example with two threads working on two nodes, where one depends on the other,
* say b depends on a. If a completes first, it's done. If it completes second, it needs to signal
* b, and potentially re-schedule it. If b completes first, it must exit, because it will be
* signaled (and re-scheduled) by a. If it completes second, it must signal (and re-schedule)
* itself. However, if the Evaluator supported re-entrancy for a node, then this wouldn't have to be
* so strict, because duplicate scheduling would be less problematic.
*
*
During its life, a node can go through states as follows:
*
*
*
Non-existent
*
Just created ({@link #isEvaluating} is false)
*
Evaluating ({@link #isEvaluating} is true)
*
Done ({@link #isDone} is true)
*
Just created (when it is dirtied: {@link #dirtyBuildingState} is not null)
*
Reset (just before it is re-evaluated: {@link #dirtyBuildingState#getDirtyState} returns
* {@link DirtyState#NEEDS_REBUILDING})
*
Evaluating
*
Done
*
*
*
The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch} 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 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.
*
*
This class is public only for the benefit of alternative graph implementations outside of the
* package.
*/
public class InMemoryNodeEntry implements NodeEntry {
/** Actual data stored in this entry when it is done. */
private SkyValue value = null;
/**
* The last version of the graph at which this node's value was changed. In {@link #setValue} it
* may be determined that the value being written to the graph at a given version is the same as
* the already-stored value. In that case, the version will remain the same. The version can be
* thought of as the latest timestamp at which this value was changed.
*/
protected Version lastChangedVersion = MinimalVersion.INSTANCE;
/**
* Returns the last version this entry was evaluated at, even if it re-evaluated to the same
* value. When a child signals this entry with the last version it was changed at in
* {@link #signalDep}, this entry need not re-evaluate if the child's version is at most this
* version, even if the {@link #lastChangedVersion} is less than this one.
*
* @see #signalDep(Version)
*/
protected Version lastEvaluatedVersion = MinimalVersion.INSTANCE;
/**
* This object represents the direct deps of the node, in groups if the {@code SkyFunction}
* requested them that way. It contains either the in-progress direct deps, stored as a
* {@code GroupedList} before the node is finished building, or the full direct deps,
* compressed in a memory-efficient way (via {@link GroupedList#compress}, after the node is done.
*
*
It is initialized lazily in getTemporaryDirectDeps() to save a little bit more memory.
*/
private Object directDeps = null;
/**
* This list stores the reverse dependencies of this node that have been declared so far.
*
*
In case of a single object we store the object unwrapped, without the list, for
* memory-efficiency.
*
*
When an entry is being re-evaluated, this object stores the reverse deps from the previous
* evaluation. At the end of evaluation, the changed reverse dep operations from {@link
* #reverseDepsDataToConsolidate} are merged in here.
*/
protected Object reverseDeps = ImmutableList.of();
/**
* This list stores objects returned by {@link KeyToConsolidate#create}. Morally they are {@link
* KeyToConsolidate} objects, but since some operations are stored bare, we can only declare that
* this list holds {@link Object} references. Created lazily to save memory.
*
*
This list serves double duty. For a done node, when a reverse dep is removed, checked for
* presence, or possibly added, we store the mutation in this object instead of immediately doing
* the operation. That is because removals/checks in reverseDeps are O(N). Originally reverseDeps
* was a HashSet, but because of memory consumption we switched to a list.
*
*
Internally, {@link ReverseDepsUtility} consolidates this data periodically, and when the set
* of reverse deps is requested. While this operation is not free, it can be done more effectively
* than trying to remove/check each dirty reverse dependency individually (O(N) each time).
*
*
When the node entry is evaluating, this list serves to declare the reverse dep operations
* that have taken place on it during this evaluation. When evaluation finishes, this list will be
* merged into the existing reverse deps if any, but furthermore, this list will also be used to
* calculate the set of reverse deps to signal when this entry finishes evaluation. That is done
* by {@link ReverseDepsUtility#consolidateDataAndReturnNewElements}.
*/
private List