src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java

// Copyright 2023 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 static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.skyframe.PackageoidValue;
import com.google.devtools.build.lib.skyframe.serialization.DeserializedSkyValue;
import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.ForOverride;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;

/** An {@link InMemoryNodeEntry} that {@link #keepsEdges} for use in incremental evaluations. */
public class IncrementalInMemoryNodeEntry extends AbstractInMemoryNodeEntry<DirtyBuildingState> {
  public static final EmptySkyValue CLEARED_SKY_VALUE = new EmptySkyValue();

  protected volatile NodeVersion version = Version.minimal();

  /**
   * 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 {@link
   * GroupedDeps} (constructed via {@link GroupedDeps.WithHashSet} if {@code
   * key.supportsPartialReevaluation()}) before the node is finished building, or the full direct
   * deps, compressed in a memory-efficient way (via {@link GroupedDeps#compress}), after the node
   * is done.
   *
   * <p>It is initialized lazily in getTemporaryDirectDeps() to save a little memory.
   */
  protected Object directDeps = null;

  /**
   * This field stores the reverse dependencies of this node that have been declared so far.
   *
   * <p>In case of a single object we store the object unwrapped, without the list, for
   * memory-efficiency.
   *
   * <p>When an entry is being evaluated or has delayed reverse dep operations on a done node, this
   * field also stores the pending operations list (as a {@link DataToConsolidateList} when there
   * are no prior reverse deps, or wrapped alongside the prior reverse deps in a {@link
   * ReverseDepsWithDataToConsolidate} record) to avoid a dedicated reference field on every node
   * entry.
   *
   * <p>The pending operations 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.
   *
   * <p>The pending operations 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 list 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.
   *
   * <p>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).
   *
   * <p>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}.
   */
  protected Object reverseDeps = ImmutableList.of();

  public IncrementalInMemoryNodeEntry(SkyKey key) {
    super(key);
  }

  /**
   * Replaces the SkyValue with a placeholder value indicating that it has been cleared.
   *
   * <p>Almost all SkyFunctions will break if they receive a cleared value and it should only be
   * used in situations where that is known to be impossible. It should never be used in cases where
   * a Bazel server instance will be kept running for incremental builds since the graph would be
   * mutilated.
   *
   * <p>One appropriate use case is an optimization for Skycache primer builds (which are always
   * cold) that reduces peak heap by discarding unneeded values before serialization.
   */
  public void clearSkyValue() {
    Preconditions.checkState(isDone());
    if (toValue() instanceof PackageoidValue packageoidValue) {
      InMemoryGraphImpl.weakInternPackageTargetsLabels(packageoidValue);
    }
    this.value = CLEARED_SKY_VALUE;
  }

  @Override
  public final boolean keepsEdges() {
    return true;
  }

  @Override
  public final Iterable<SkyKey> getDirectDeps() {
    return GroupedDeps.compressedToIterable(getCompressedDirectDepsForDoneEntry());
  }

  @Override
  public final boolean hasAtLeastOneDep() {
    return !GroupedDeps.isEmpty(getCompressedDirectDepsForDoneEntry());
  }

  @Override
  public final synchronized @GroupedDeps.Compressed Object getCompressedDirectDepsForDoneEntry() {
    checkState(isDone(), "no deps until done. NodeEntry: %s", this);
    checkNotNull(directDeps, "deps can't be null: %s", this);
    return GroupedDeps.castAsCompressed(directDeps);
  }

  /**
   * Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one may
   * need to override the other.
   */
  @ForOverride
  protected void markDone() {
    dirtyBuildingState = null;
  }

  protected final synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
    Set<SkyKey> reverseDepsToSignal = ReverseDepsUtility.consolidateDataAndReturnNewElements(this);
    directDeps = getTemporaryDirectDeps().compress();
    markDone();
    return reverseDepsToSignal;
  }

  @Override
  public synchronized Set<SkyKey> getInProgressReverseDeps() {
    checkState(!isDone(), this);
    return ReverseDepsUtility.returnNewElements(this);
  }

  /**
   * {@inheritDoc}
   *
   * <p>In this method it is crucial that {@link #version} is set prior to {@link #value} because
   * although this method itself is synchronized, there are unsynchronized consumers of the version
   * and the value.
   */
  @Override
  @CanIgnoreReturnValue
  public synchronized Set<SkyKey> setValue(
      SkyValue value, Version graphVersion, @Nullable Version maxTransitiveSourceVersion)
      throws InterruptedException {
    checkState(!hasUnsignaledDeps(), "Has unsignaled deps (this=%s, value=%s)", this, value);
    checkState(
        version.lastChanged().atMost(graphVersion) && version.lastEvaluated().atMost(graphVersion),
        "Bad version (this=%s, version=%s, value=%s)",
        this,
        graphVersion,
        value);

    if (dirtyBuildingState.unchangedFromLastBuild(value)) {
      // If the value is the same as before, prefer the old value. Note that we don't prefer the new
      // value, because preserving == equality is even better than .equals() equality. The exception
      // is when comparing a regular SkyValue vs an otherwise equal DeserializedSkyValue:
      //  - If old computed -> new deserialized, we need the deserialized value for proper
      //    invalidation on subsequent evaluations, since we don't have proper deps. See
      //    SkyframeExecutor#invalidateWithExternalService.
      //  - If old deserialized -> new computed, we prefer the computed value since we do have
      //    proper deps and can therefore rely on the more precise classic bottom-up invalidation.
      Version lastChanged = version.lastChanged();
      version = NodeVersionGetter.get(lastChanged, graphVersion);
      SkyValue oldValue = dirtyBuildingState.getLastBuildValue();
      this.value =
          value instanceof DeserializedSkyValue != oldValue instanceof DeserializedSkyValue
              ? value
              : oldValue;
    } else {
      // If this is a new value, or it has changed since the last build, set the version to the
      // current graph version.
      version = graphVersion;
      this.value = value;
    }
    return setStateFinishedAndReturnReverseDepsToSignal();
  }

  @Override
  @CanIgnoreReturnValue
  public DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
    if (reverseDep == null && isDone()) {
      return DependencyState.DONE;
    }

    synchronized (this) {
      boolean done = isDone();
      if (!done && dirtyBuildingState == null) {
        dirtyBuildingState = new InitialBuildingState();
      }
      if (reverseDep != null) {
        if (done) {
          ReverseDepsUtility.addReverseDep(this, reverseDep);
        } else {
          appendToReverseDepOperations(reverseDep, Op.ADD);
        }
      }
      if (done) {
        return DependencyState.DONE;
      }
      if (dirtyBuildingState.isEvaluating()) {
        return DependencyState.ALREADY_EVALUATING;
      }
      dirtyBuildingState.startEvaluating();
      return DependencyState.NEEDS_SCHEDULING;
    }
  }

  /**
   * Marker subclass of {@link ArrayList} used to store pending reverse dep operations directly in
   * {@link #reverseDeps} when there are no prior consolidated reverse deps. Avoids allocating a
   * wrapper object on initial node evaluations.
   */
  private static final class DataToConsolidateList extends ArrayList<Object> {}

  private record ReverseDepsWithDataToConsolidate(
      Object reverseDeps, List<Object> dataToConsolidate) {}

  /** Sets consolidated {@link #reverseDeps}. Pending data to consolidate must already be null. */
  synchronized void setReverseDepsForReverseDepsUtil(Object reverseDeps) {
    checkState(getReverseDepsDataToConsolidateForReverseDepsUtil() == null, this);
    this.reverseDeps = reverseDeps;
  }

  /** Sets pending data to consolidate. Does not alter consolidated {@link #reverseDeps}. */
  synchronized void setReverseDepsDataToConsolidateForReverseDepsUtil(
      @Nullable List<Object> dataToConsolidate) {
    Object rawReverseDeps = getReverseDepsRawForReverseDepsUtil();
    if (dataToConsolidate == null) {
      this.reverseDeps = rawReverseDeps;
    } else if (rawReverseDeps instanceof List<?> list
        && list.isEmpty()
        && dataToConsolidate instanceof DataToConsolidateList) {
      this.reverseDeps = dataToConsolidate;
    } else {
      this.reverseDeps = new ReverseDepsWithDataToConsolidate(rawReverseDeps, dataToConsolidate);
    }
  }

  synchronized Object getReverseDepsRawForReverseDepsUtil() {
    if (this.reverseDeps instanceof DataToConsolidateList) {
      return ImmutableList.of();
    }
    if (this.reverseDeps instanceof ReverseDepsWithDataToConsolidate consolidated) {
      return consolidated.reverseDeps();
    }
    return this.reverseDeps;
  }

  @Nullable
  synchronized List<Object> getReverseDepsDataToConsolidateForReverseDepsUtil() {
    if (this.reverseDeps instanceof DataToConsolidateList dataToConsolidate) {
      return dataToConsolidate;
    }
    if (this.reverseDeps instanceof ReverseDepsWithDataToConsolidate consolidated) {
      return consolidated.dataToConsolidate();
    }
    return null;
  }

  private synchronized void appendToReverseDepOperations(SkyKey reverseDep, Op op) {
    checkState(!isDone(), "Don't append to done %s %s %s", this, reverseDep, op);
    List<Object> dataToConsolidate = getReverseDepsDataToConsolidateForReverseDepsUtil();
    if (dataToConsolidate == null) {
      dataToConsolidate = new DataToConsolidateList();
      setReverseDepsDataToConsolidateForReverseDepsUtil(dataToConsolidate);
    }
    checkState(isDirty() || op != Op.CHECK, "Not dirty check %s %s", this, reverseDep);
    dataToConsolidate.add(KeyToConsolidate.create(reverseDep, op, this));
  }

  @Override
  public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
    checkNotNull(reverseDep, this);
    if (isDone()) {
      return DependencyState.DONE;
    }
    appendToReverseDepOperations(reverseDep, Op.CHECK);
    return addReverseDepAndCheckIfDone(null);
  }

  @Override
  public synchronized void removeReverseDep(SkyKey reverseDep) {
    if (isDone()) {
      ReverseDepsUtility.removeReverseDep(this, reverseDep);
    } else {
      // Removing a reverse dep from an in-flight node is rare -- it should only happen when there
      // is a cycle or this node is about to be cleaned from the graph.
      appendToReverseDepOperations(reverseDep, Op.REMOVE);
    }
  }

  @Override
  public synchronized void removeReverseDepsFromDoneEntryDueToDeletion(Set<SkyKey> deletedKeys) {
    checkState(isDone(), this);
    ReverseDepsUtility.removeReverseDepsMatching(this, deletedKeys);
  }

  @Override
  public synchronized Collection<SkyKey> getReverseDepsForDoneEntry() {
    checkState(isDone(), "Called on not done %s", this);
    return ReverseDepsUtility.consolidateAndGetReverseDeps(this, /* checkConsistency= */ true);
  }

  @Override
  public synchronized Collection<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
    if (!isDone()) {
      // This consolidation loses information about pending reverse deps to signal, but that is
      // unimportant since this node is being deleted.
      ReverseDepsUtility.consolidateDataAndReturnNewElements(this);
    }
    return ReverseDepsUtility.consolidateAndGetReverseDeps(this, /* checkConsistency= */ false);
  }

  @Override
  public synchronized boolean signalDep(Version childVersion, @Nullable SkyKey childForDebugging) {
    checkState(
        !isDone(), "Value must not be done in signalDep %s child=%s", this, childForDebugging);
    checkNotNull(dirtyBuildingState, "%s %s", this, childForDebugging);
    dirtyBuildingState.signalDep(this, version, childVersion, childForDebugging);
    return !hasUnsignaledDeps();
  }

  /**
   * Creates a {@link DirtyBuildingState} for the case where this node is done and is being marked
   * dirty.
   */
  @ForOverride
  protected DirtyBuildingState createDirtyBuildingStateForDoneNode(
      DirtyType dirtyType, GroupedDeps directDeps, SkyValue value) {
    return new IncrementalBuildingState(dirtyType, directDeps, value);
  }

  @Nullable
  @Override
  public synchronized MarkedDirtyResult markDirty(DirtyType dirtyType) {
    checkNotNull(dirtyType, this);

    if (isDone()) {
      if (dirtyType == DirtyType.REWIND && getErrorInfo() != null) {
        return null; // Rewinding errors is no-op.
      }
      GroupedDeps directDeps = GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry());
      checkState(
          dirtyType != DirtyType.DIRTY || !directDeps.isEmpty(),
          "%s is being marked dirty but has no children that could have dirtied it",
          getKey());
      dirtyBuildingState = createDirtyBuildingStateForDoneNode(dirtyType, directDeps, value);
      value = null;
      this.directDeps = null;
      if (dirtyType == DirtyType.REWIND) {
        // For rewinding, the reverse deps don't need to be included in the MarkedDirtyResult, but
        // they do need to be consolidated so that ReverseDepsUtility considers only rdep operations
        // that occur after the rewind to be "new elements." This is important because only rdeps
        // registered after the rewind should be signalled when the rewound evaluation completes.
        ReverseDepsUtility.consolidateData(this);
        return MarkedDirtyResult.forRewinding();
      } else {
        return MarkedDirtyResult.withReverseDeps(
            ReverseDepsUtility.consolidateAndGetReverseDeps(this, /* checkConsistency= */ true));
      }
    }

    // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
    // thread may have lost the race, but it is the caller's responsibility not to try to mark this
    // node changed twice. The end result of racing markers must be a changed node, since one of the
    // markers is trying to mark the node changed.
    checkState(value == null, "Value should have been reset already %s", this);
    switch (dirtyType) {
      case CHANGE:
        checkState(!isChanged(), "Cannot mark node changed twice: %s", this);
        checkNotNull(dirtyBuildingState, this).markChanged();
        break;
      case DIRTY:
        checkState(isChanged(), "Cannot mark node dirty twice: %s", this);
        break;
      case REWIND:
        // Rewinding is legal at any time in the node's lifecycle, but is no-op when it is not done.
        break;
    }
    return null;
  }

  @Override
  public synchronized NodeValueAndRdepsToSignal markClean() throws InterruptedException {
    checkNotNull(dirtyBuildingState, this);
    this.value = checkNotNull(dirtyBuildingState.getLastBuildValue());
    checkState(!hasUnsignaledDeps(), this);
    checkState(
        dirtyBuildingState.depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
        "Direct deps must be the same as those found last build for node to be marked clean: %s",
        this);
    checkState(isDirty(), this);
    checkState(!dirtyBuildingState.isChanged(), "shouldn't be changed: %s", this);
    Set<SkyKey> rDepsToSignal = setStateFinishedAndReturnReverseDepsToSignal();
    return new NodeValueAndRdepsToSignal(this.value, rDepsToSignal);
  }

  @Override
  public Version getVersion() {
    return version.lastChanged();
  }

  /**
   * Returns this node's direct deps from the last evaluation if the node may be resurrected by
   * change pruning; otherwise returns {@code null}. The node may be kept iff every returned dep is
   * still present and was not changed more recently than {@link #lastEvaluatedVersion}.
   */
  @Nullable
  final Iterable<SkyKey> lastBuildDepsIfChangePrunable() {
    var localDirtyBuildingState = dirtyBuildingState;
    if (localDirtyBuildingState == null
        || !localDirtyBuildingState.isIncremental()
        || isChanged()) {
      return null;
    }
    try {
      return localDirtyBuildingState.getLastBuildDirectDeps().getAllElementsAsIterable();
    } catch (InterruptedException e) {
      // An incremental dirty state returns its stored deps without blocking.
      throw new IllegalStateException(e);
    }
  }

  /** Returns the version at which this node was last evaluated; see {@link NodeVersion}. */
  public final Version lastEvaluatedVersion() {
    return version.lastEvaluated();
  }

  @Override
  public final synchronized ImmutableSet<SkyKey> getAllDirectDepsForIncompleteNode()
      throws InterruptedException {
    checkState(!isDone(), this);
    if (dirtyBuildingState == null) {
      return ImmutableSet.of();
    }
    return ImmutableSet.<SkyKey>builder()
        .addAll(getTemporaryDirectDeps().getAllElementsAsIterable())
        .addAll(dirtyBuildingState.getAllRemainingDirtyDirectDeps(/* preservePosition= */ false))
        .addAll(getResetDirectDeps())
        .build();
  }

  @Override
  public synchronized GroupedDeps getTemporaryDirectDeps() {
    checkState(!isDone(), "temporary shouldn't be done: %s", this);
    if (directDeps == null) {
      // Initialize lazily, to save a little memory.
      directDeps = newGroupedDeps();
    }
    return (GroupedDeps) directDeps;
  }

  @Override
  public final synchronized void forceRebuild() {
    checkNotNull(dirtyBuildingState, this).forceRebuild(getNumTemporaryDirectDeps());
  }

  @Override
  final synchronized int getNumTemporaryDirectDeps() {
    return directDeps == null ? 0 : getTemporaryDirectDeps().numElements();
  }

  @Override
  public final synchronized void resetEvaluationFromScratch() {
    checkState(!hasUnsignaledDeps(), this);

    ImmutableSet<SkyKey> resetDeps =
        ImmutableSet.<SkyKey>builder()
            .addAll(getResetDirectDeps()) // In case this isn't the first reset.
            .addAll(getTemporaryDirectDeps().getAllElementsAsIterable())
            .build();

    if (dirtyBuildingState.isIncremental()) {
      var incrementalBuildingState = (IncrementalBuildingState) dirtyBuildingState;
      dirtyBuildingState =
          new ResetIncrementalBuildingState(
              incrementalBuildingState.lastBuildDirectDeps,
              incrementalBuildingState.lastBuildValue,
              incrementalBuildingState.dirtyDirectDepIndex,
              resetDeps);
    } else {
      dirtyBuildingState = new ResetInitialBuildingState(resetDeps);
    }
    directDeps = null;
  }

  @Override
  public final ImmutableSet<SkyKey> getResetDirectDeps() {
    return checkNotNull(dirtyBuildingState, this).getResetDirectDeps();
  }

  /**
   * Clears out all direct dep edges of this node.
   *
   * <p>Only safe once the graph no longer needs to be incrementally correct: by Skycache uploads
   * under {@code --nokeep_state_after_build}.
   */
  public final synchronized void clearDirectDeps() {

    checkState(isDone(), this);
    this.directDeps = GroupedDeps.EMPTY_COMPRESSED;
  }
  /** Flushes pending reverse dep operations, which potentially saves memory. */
  public final synchronized void consolidateReverseDeps() {

    checkState(isDone(), this);
    ReverseDepsUtility.consolidateData(this);
  }

  @Override
  protected synchronized MoreObjects.ToStringHelper toStringHelper() {
    return super.toStringHelper()
        .add("version", version)
        .add(
            "directDeps",
            isDone() ? GroupedDeps.decompress(getCompressedDirectDepsForDoneEntry()) : directDeps)
        .add("reverseDeps", ReverseDepsUtility.toString(this));
  }

  /** {@link DirtyBuildingState} for a node on an incremental build. */
  private static class IncrementalBuildingState extends DirtyBuildingState {
    private final GroupedDeps lastBuildDirectDeps;
    private final SkyValue lastBuildValue;

    private IncrementalBuildingState(
        DirtyType dirtyType, GroupedDeps lastBuildDirectDeps, SkyValue lastBuildValue) {
      super(dirtyType);
      this.lastBuildDirectDeps = lastBuildDirectDeps;
      this.lastBuildValue = lastBuildValue;
    }

    @Override
    protected final boolean isIncremental() {
      return true;
    }

    @Override
    public final SkyValue getLastBuildValue() {
      return lastBuildValue;
    }

    @Override
    public final GroupedDeps getLastBuildDirectDeps() {
      return lastBuildDirectDeps;
    }

    @Override
    protected final int getNumOfGroupsInLastBuildDirectDeps() {
      return lastBuildDirectDeps.numGroups();
    }

    @Override
    protected MoreObjects.ToStringHelper getStringHelper() {
      return super.getStringHelper()
          .add("lastBuildDirectDeps", lastBuildDirectDeps)
          .add("lastBuildValue", lastBuildValue);
    }
  }

  /**
   * Used to track already registered deps when there is a {@linkplain #resetEvaluationFromScratch
   * reset} on a node's initial build.
   */
  private static final class ResetInitialBuildingState extends InitialBuildingState {
    private final ImmutableSet<SkyKey> resetDeps;

    ResetInitialBuildingState(ImmutableSet<SkyKey> resetDeps) {
      this.resetDeps = resetDeps;
      markRebuilding();
      startEvaluating();
    }

    @Override
    ImmutableSet<SkyKey> getResetDirectDeps() {
      return resetDeps;
    }

    @Override
    protected MoreObjects.ToStringHelper getStringHelper() {
      return super.getStringHelper().add("resetDeps", resetDeps);
    }
  }

  /**
   * Used to track already registered deps when there is a {@linkplain #resetEvaluationFromScratch
   * reset} on a node's incremental build.
   */
  private static final class ResetIncrementalBuildingState extends IncrementalBuildingState {
    private final ImmutableSet<SkyKey> resetDeps;

    private ResetIncrementalBuildingState(
        GroupedDeps lastBuildDirectDeps,
        SkyValue lastBuildValue,
        int dirtyDirectDepIndex,
        ImmutableSet<SkyKey> resetDeps) {
      // CHANGE (not DIRTY) since we already know it needs rebuilding.
      super(DirtyType.CHANGE, lastBuildDirectDeps, lastBuildValue);
      this.dirtyDirectDepIndex = dirtyDirectDepIndex;
      this.resetDeps = resetDeps;
      markRebuilding();
      startEvaluating();
    }

    @Override
    ImmutableSet<SkyKey> getResetDirectDeps() {
      return resetDeps;
    }

    @Override
    protected MoreObjects.ToStringHelper getStringHelper() {
      return super.getStringHelper().add("resetDeps", resetDeps);
    }
  }
}