src/main/java/com/google/devtools/build/skyframe/NonIncrementalInMemoryNodeEntry.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.checkArgument;
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.ImmutableSet;
import com.google.devtools.build.skyframe.NonIncrementalInMemoryNodeEntry.NonIncrementalBuildingState;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;

/**
 * An {@link InMemoryNodeEntry} that does not store edges (direct deps and reverse deps) once the
 * node is done. Used to save memory when the graph will not be reused for incremental builds.
 *
 * <p>Edges are stored as usual while the node is being built, but are discarded once the node is
 * done.
 *
 * <p>It is illegal to access edges once the node {@link #isDone}.
 */
public class NonIncrementalInMemoryNodeEntry
    extends AbstractInMemoryNodeEntry<NonIncrementalBuildingState> {

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

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

  @Override
  @CanIgnoreReturnValue
  public synchronized ImmutableSet<SkyKey> setValue(
      SkyValue value, Version graphVersion, @Nullable Version maxTransitiveSourceVersion) {
    checkArgument(
        graphVersion.equals(Version.constant()),
        "Non-incremental evaluations must be at a constant version: %s",
        graphVersion);
    checkState(!hasUnsignaledDeps(), "Has unsignaled deps (this=%s, value=%s)", this, value);
    this.value = value;
    ImmutableSet<SkyKey> reverseDepsToSignal = dirtyBuildingState.getReverseDeps(this);
    dirtyBuildingState = null;
    return reverseDepsToSignal;
  }

  @Override
  @CanIgnoreReturnValue
  public final DependencyState addReverseDepAndCheckIfDone(@Nullable SkyKey reverseDep) {
    // Fast path check before locking. If this node is already done, there is nothing to do since we
    // aren't storing reverse deps.
    if (isDone()) {
      return DependencyState.DONE;
    }

    synchronized (this) {
      // Check again under a lock.
      if (isDone()) {
        return DependencyState.DONE;
      }
      if (dirtyBuildingState == null) {
        dirtyBuildingState = new NonIncrementalBuildingState();
      }
      if (reverseDep != null) {
        dirtyBuildingState.addReverseDep(reverseDep);
      }
      if (dirtyBuildingState.isEvaluating()) {
        return DependencyState.ALREADY_EVALUATING;
      }
      dirtyBuildingState.startEvaluating();
      return DependencyState.NEEDS_SCHEDULING;
    }
  }

  /**
   * {@inheritDoc}
   *
   * <p>A {@link NonIncrementalInMemoryNodeEntry} can only ever be at one of two versions: either
   * {@link Version#constant} when a value is available, or {@link Version#minimal} otherwise.
   *
   * <p>All non-incremental evaluations must use {@link Version#constant} as the graph version. This
   * is enforced in {@link #setValue}.
   */
  @Override
  public final Version getVersion() {
    return value != null ? Version.constant() : Version.minimal();
  }

  @Override
  public final synchronized GroupedDeps getTemporaryDirectDeps() {
    return checkNotNull(dirtyBuildingState, "Not evaluating: %s", this)
        .getTemporaryDirectDeps(this);
  }

  @Override
  public final synchronized void resetEvaluationFromScratch() {
    checkState(!hasUnsignaledDeps(), this);
    SkyValue rewoundValue = dirtyBuildingState.getLastBuildValue();
    var newBuildingState =
        rewoundValue == null
            ? new NonIncrementalBuildingState()
            : new RewoundNonIncrementalBuildingState(rewoundValue);
    newBuildingState.reverseDeps = dirtyBuildingState.reverseDeps;
    newBuildingState.markRebuilding();
    newBuildingState.startEvaluating();
    dirtyBuildingState = newBuildingState;
  }

  @Override
  public final ImmutableSet<SkyKey> getResetDirectDeps() {
    return ImmutableSet.of(); // No accounting necessary since rdeps are not stored.
  }

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

  @Nullable
  @Override
  public final synchronized MarkedDirtyResult markDirty(DirtyType dirtyType) {
    checkArgument(dirtyType == DirtyType.REWIND, "Unexpected dirty type: %s", dirtyType);
    if (!isDone()) {
      return null; // Tolerate concurrent requests to rewind.
    }
    if (getErrorInfo() != null) {
      return null; // Rewinding errors is no-op.
    }
    dirtyBuildingState = new RewoundNonIncrementalBuildingState(value);
    value = null;
    return MarkedDirtyResult.forRewinding();
  }

  @Override
  public final synchronized Set<SkyKey> getInProgressReverseDeps() {
    checkState(!isDone(), this);
    return dirtyBuildingState == null ? ImmutableSet.of() : dirtyBuildingState.getReverseDeps(this);
  }

  @Override
  public final 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)
        .signalDep(this, Version.minimal(), childVersion, childForDebugging);
    return !hasUnsignaledDeps();
  }

  @Override
  public final void removeReverseDep(SkyKey reverseDep) {
    checkNotNull(dirtyBuildingState, "Not evaluating: %s", this).removeReverseDep(reverseDep);
  }

  @Override
  public final @GroupedDeps.Compressed Object getCompressedDirectDepsForDoneEntry() {
    throw unsupported();
  }

  @Override
  public final Iterable<SkyKey> getDirectDeps() {
    throw unsupported();
  }

  @Override
  public final ImmutableSet<SkyKey> getAllDirectDepsForIncompleteNode() {
    throw unsupported();
  }

  @Override
  public final boolean hasAtLeastOneDep() {
    throw unsupported();
  }

  @Override
  public final void removeReverseDepsFromDoneEntryDueToDeletion(Set<SkyKey> deletedKeys) {
    throw unsupported();
  }

  @Override
  public final Collection<SkyKey> getReverseDepsForDoneEntry() {
    throw unsupported();
  }

  @Override
  public final Collection<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
    throw unsupported();
  }

  @Override
  public final DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
    throw unsupported();
  }

  @Override
  public final NodeValueAndRdepsToSignal markClean() {
    throw unsupported();
  }

  @Override
  public void forceRebuild() {
    throw unsupported();
  }

  private UnsupportedOperationException unsupported() {
    return new UnsupportedOperationException("Not keeping edges: " + this);
  }

  /**
   * Specialized {@link DirtyBuildingState} for a non-incremental node.
   *
   * <p>The {@link #directDeps} and {@link #reverseDeps} fields are stored in this class instead of
   * in {@link NonIncrementalInMemoryNodeEntry} since they are not needed after the node is done.
   * This way we don't pay the memory cost of the fields for a done node.
   */
  static class NonIncrementalBuildingState extends InitialBuildingState {
    @Nullable private GroupedDeps directDeps = null;
    @Nullable private List<SkyKey> reverseDeps = null;

    private NonIncrementalBuildingState() {}

    final GroupedDeps getTemporaryDirectDeps(NonIncrementalInMemoryNodeEntry entry) {
      if (directDeps == null) {
        directDeps = entry.newGroupedDeps();
      }
      return directDeps;
    }

    final void addReverseDep(SkyKey reverseDep) {
      if (reverseDeps == null) {
        reverseDeps = new ArrayList<>();
      }
      reverseDeps.add(reverseDep);
    }

    final void removeReverseDep(SkyKey reverseDep) {
      // Reverse dep removal on a non-incremental node is rare (only for cycles), so we can live
      // with inefficiently calling remove on an ArrayList.
      checkState(reverseDeps.remove(reverseDep), "Reverse dep not present: %s", reverseDep);
    }

    final ImmutableSet<SkyKey> getReverseDeps(NonIncrementalInMemoryNodeEntry entry) {
      if (reverseDeps == null) {
        return ImmutableSet.of();
      }
      ImmutableSet<SkyKey> result = ImmutableSet.copyOf(reverseDeps);
      ReverseDepsUtility.checkForDuplicates(result, reverseDeps, entry);
      return result;
    }

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

  /**
   * State for a non-incremental node that was previously {@linkplain #isDone done} but was
   * {@linkplain com.google.devtools.build.skyframe.NodeEntry.DirtyType#REWIND rewound}. Stores the
   * previously built value for the sole purpose of servicing {@link #toValue}.
   */
  private static final class RewoundNonIncrementalBuildingState
      extends NonIncrementalBuildingState {
    private final SkyValue rewoundValue;

    RewoundNonIncrementalBuildingState(SkyValue rewoundValue) {
      this.rewoundValue = rewoundValue;
    }

    @Override
    public SkyValue getLastBuildValue() {
      return rewoundValue;
    }

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