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.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
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> {

  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 list 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 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.
   *
   * <p>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.
   *
   * <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}.
   */
  private List<Object> reverseDepsDataToConsolidate = null;

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

  @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, just use the old value. Note that we don't use the new
      // value, because preserving == equality is even better than .equals() equality.
      Version lastChanged = version.lastChanged();
      version = NodeVersion.of(lastChanged, graphVersion);
      this.value = dirtyBuildingState.getLastBuildValue();
    } 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;
    }
  }

  /** Sets {@link #reverseDeps}. Does not alter {@link #reverseDepsDataToConsolidate}. */
  synchronized void setReverseDepsForReverseDepsUtil(Object reverseDeps) {
    this.reverseDeps = reverseDeps;
  }

  /** Sets {@link #reverseDepsDataToConsolidate}. Does not alter {@link #reverseDeps}. */
  synchronized void setReverseDepsDataToConsolidateForReverseDepsUtil(
      List<Object> dataToConsolidate) {
    this.reverseDepsDataToConsolidate = dataToConsolidate;
  }

  synchronized Object getReverseDepsRawForReverseDepsUtil() {
    return this.reverseDeps;
  }

  synchronized List<Object> getReverseDepsDataToConsolidateForReverseDepsUtil() {
    return this.reverseDepsDataToConsolidate;
  }

  private synchronized void appendToReverseDepOperations(SkyKey reverseDep, Op op) {
    checkState(!isDone(), "Don't append to done %s %s %s", this, reverseDep, op);
    if (reverseDepsDataToConsolidate == null) {
      reverseDepsDataToConsolidate = new ArrayList<>();
    }
    checkState(isDirty() || op != Op.CHECK, "Not dirty check %s %s", this, reverseDep);
    reverseDepsDataToConsolidate.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();
  }

  @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();
  }

  /**
   * For Skyfocus only: clears out all direct dep edges of this node. It is not safe to call this
   * otherwise.
   */
  public final synchronized void clearDirectDepsForSkyfocus() {

    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);
    }
  }
}