src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.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.truth.Truth.assertThat;
import static com.google.devtools.build.skyframe.NodeEntrySubjectFactory.assertThatNodeEntry;
import static org.junit.Assert.assertThrows;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.collect.nestedset.Order;
import com.google.devtools.build.lib.events.Reportable;
import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
import com.google.devtools.build.skyframe.NodeEntry.DirtyType;
import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.ForOverride;
import com.google.testing.junit.testparameterinjector.TestParameter;
import java.util.Set;
import javax.annotation.Nullable;
import org.junit.Test;

/**
 * Tests for {@link InMemoryNodeEntry} implementations.
 *
 * <p>Contains test cases that are relevant to both {@link IncrementalInMemoryNodeEntry} and {@link
 * NonIncrementalInMemoryNodeEntry}. Test cases that are only partially relevant to one or the other
 * may branch on {@link InMemoryNodeEntry#keepsEdges} and return early.
 *
 * @param <V> The type of {@link Version} used by the {@link InMemoryNodeEntry} class under test
 */
abstract class InMemoryNodeEntryTest<V extends Version> {

  private static final SkyKey REGULAR_KEY = GraphTester.skyKey("regular");
  private static final SkyKey PARTIAL_REEVALUATION_KEY =
      new SkyKey() {
        @Override
        public SkyFunctionName functionName() {
          return SkyFunctionName.FOR_TESTING;
        }

        @Override
        public boolean supportsPartialReevaluation() {
          return true;
        }
      };

  private static final NestedSet<Reportable> NO_EVENTS =
      NestedSetBuilder.emptySet(Order.STABLE_ORDER);

  @TestParameter boolean isPartialReevaluation;

  protected final V initialVersion = getInitialVersion();

  static SkyKey key(String name) {
    return GraphTester.skyKey(name);
  }

  final InMemoryNodeEntry createEntry() {
    return createEntry(isPartialReevaluation ? PARTIAL_REEVALUATION_KEY : REGULAR_KEY);
  }

  @ForOverride
  protected abstract InMemoryNodeEntry createEntry(SkyKey key);

  @ForOverride
  abstract V getInitialVersion();

  @Test
  public void entryAtStartOfEvaluation() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    assertThat(entry.isDone()).isFalse();
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    assertThat(entry.isDirty()).isTrue();
    assertThat(entry.isChanged()).isTrue();
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();
    assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
        .isEqualTo(isPartialReevaluation);
  }

  @Test
  public void signalEntry() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    SkyKey dep1 = key("dep1");
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.isReadyToEvaluate()).isEqualTo(isPartialReevaluation);
    assertThat(entry.hasUnsignaledDeps()).isTrue();
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep1);
    SkyKey dep2 = key("dep2");
    SkyKey dep3 = key("dep3");
    entry.addSingletonTemporaryDirectDep(dep2);
    entry.addSingletonTemporaryDirectDep(dep3);
    assertThat(entry.isReadyToEvaluate()).isEqualTo(isPartialReevaluation);
    assertThat(entry.hasUnsignaledDeps()).isTrue();
    assertThat(entry.signalDep(initialVersion, dep2)).isFalse();
    assertThat(entry.isReadyToEvaluate()).isEqualTo(isPartialReevaluation);
    assertThat(entry.hasUnsignaledDeps()).isTrue();
    assertThat(entry.signalDep(initialVersion, dep3)).isTrue();
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    assertThat(setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion)).isEmpty();
    assertThat(entry.isDone()).isTrue();
    assertThat(entry.getVersion()).isEqualTo(initialVersion);

    if (!entry.keepsEdges()) {
      return;
    }

    assertThat(entry.getDirectDeps()).containsExactly(dep1, dep2, dep3);
  }

  @Test
  public void signalExternalDep() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    entry.addExternalDep();
    assertThat(entry.isReadyToEvaluate()).isEqualTo(isPartialReevaluation);
    assertThat(entry.hasUnsignaledDeps()).isTrue();
    assertThat(entry.signalDep(initialVersion, null)).isTrue();
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    entry.addExternalDep();
    assertThat(entry.isReadyToEvaluate()).isEqualTo(isPartialReevaluation);
    assertThat(entry.hasUnsignaledDeps()).isTrue();
    assertThat(entry.signalDep(initialVersion, null)).isTrue();
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly();
  }

  @Test
  public void reverseDeps() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    SkyKey mother = key("mother");
    SkyKey father = key("father");
    assertThat(entry.addReverseDepAndCheckIfDone(mother))
        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
    assertThat(entry.addReverseDepAndCheckIfDone(null))
        .isEqualTo(DependencyState.ALREADY_EVALUATING);
    assertThat(entry.addReverseDepAndCheckIfDone(father))
        .isEqualTo(DependencyState.ALREADY_EVALUATING);
    entry.markRebuilding();
    assertThat(setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion))
        .containsExactly(mother, father);

    if (!entry.keepsEdges()) {
      return;
    }

    assertThat(entry.getReverseDepsForDoneEntry()).containsExactly(mother, father);
    assertThat(entry.isDone()).isTrue();
    entry.removeReverseDep(mother);
    assertThat(entry.getReverseDepsForDoneEntry()).doesNotContain(mother);
  }

  @Test
  public void errorValue() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    ReifiedSkyFunctionException exception =
        new ReifiedSkyFunctionException(
            new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT));
    ErrorInfo errorInfo = ErrorInfo.fromException(exception, false);
    assertThat(setValue(entry, /* value= */ null, errorInfo, initialVersion)).isEmpty();
    assertThat(entry.isDone()).isTrue();
    assertThat(entry.getValue()).isNull();
    assertThat(entry.getErrorInfo()).isEqualTo(errorInfo);
  }

  @Test
  public void errorAndValue() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    ReifiedSkyFunctionException exception =
        new ReifiedSkyFunctionException(
            new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT));
    ErrorInfo errorInfo = ErrorInfo.fromException(exception, false);
    setValue(entry, new SkyValue() {}, errorInfo, initialVersion);
    assertThat(entry.isDone()).isTrue();
    assertThat(entry.getErrorInfo()).isEqualTo(errorInfo);
  }

  @Test
  public void crashOnNullErrorAndValue() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    assertThrows(
        IllegalStateException.class,
        () -> setValue(entry, /* value= */ null, /* errorInfo= */ null, initialVersion));
  }

  @Test
  public void crashOnTooManySignals() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    assertThrows(IllegalStateException.class, () -> entry.signalDep(initialVersion, null));
  }

  @Test
  public void crashOnSetValueWhenDone() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion);
    assertThat(entry.isDone()).isTrue();
    assertThrows(
        IllegalStateException.class,
        () -> setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion));
  }

  @Test
  public void crashOnAddReverseDepTwice() {
    InMemoryNodeEntry entry = createEntry();
    SkyKey parent = key("parent");
    assertThat(entry.addReverseDepAndCheckIfDone(parent))
        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
    entry.addReverseDepAndCheckIfDone(parent);
    entry.markRebuilding();
    IllegalStateException e =
        assertThrows(
            "Cannot add same dep twice",
            IllegalStateException.class,
            () -> setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion));
    assertThat(e).hasMessageThat().containsMatch("[Dd]uplicate( new)? reverse deps");
  }

  static final class IntegerValue implements SkyValue {
    private final int value;

    IntegerValue(int value) {
      this.value = value;
    }

    @Override
    public boolean equals(Object that) {
      return (that instanceof IntegerValue) && (((IntegerValue) that).value == value);
    }

    @Override
    public int hashCode() {
      return value;
    }
  }

  @Test
  public void addTemporaryDirectDepsInGroups() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    entry.addTemporaryDirectDepsInGroups(
        ImmutableSet.of(
            key("1A"), key("2A"), key("2B"), key("3A"), key("3B"), key("3C"), key("4A"), key("4B"),
            key("4C"), key("4D")),
        ImmutableList.of(1, 2, 3, 4));
    assertThat(entry.getTemporaryDirectDeps())
        .containsExactly(
            ImmutableList.of(key("1A")),
            ImmutableList.of(key("2A"), key("2B")),
            ImmutableList.of(key("3A"), key("3B"), key("3C")),
            ImmutableList.of(key("4A"), key("4B"), key("4C"), key("4D")))
        .inOrder();
  }

  @Test
  public void addTemporaryDirectDepsInGroups_toleratesEmpty() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    entry.addTemporaryDirectDepsInGroups(ImmutableSet.of(), ImmutableList.of());
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();
  }

  @Test
  public void addTemporaryDirectDepsInGroups_toleratesGroupSizeOfZero() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    entry.addTemporaryDirectDepsInGroups(ImmutableSet.of(key("dep")), ImmutableList.of(0, 1, 0));
    assertThat(entry.getTemporaryDirectDeps()).containsExactly(ImmutableList.of(key("dep")));
  }

  @Test
  public void addTemporaryDirectDepsInGroups_notEnoughGroups_throws() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    assertThrows(
        RuntimeException.class,
        () ->
            entry.addTemporaryDirectDepsInGroups(ImmutableSet.of(key("dep")), ImmutableList.of()));
  }

  @Test
  public void addTemporaryDirectDepsInGroups_tooManyGroups_throws() {
    InMemoryNodeEntry entry = createEntry();
    assertThrows(
        RuntimeException.class,
        () -> entry.addTemporaryDirectDepsInGroups(ImmutableSet.of(), ImmutableList.of(1)));
  }

  @Test
  public void addTemporaryDirectDepsInGroups_depsLeftOver_throws() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    assertThrows(
        RuntimeException.class,
        () ->
            entry.addTemporaryDirectDepsInGroups(
                ImmutableSet.of(key("1"), key("2"), key("3")), ImmutableList.of(1, 1)));
  }

  @Test
  public void addTemporaryDirectDepsInGroups_depsExhausted_throws() {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null);
    assertThrows(
        RuntimeException.class,
        () ->
            entry.addTemporaryDirectDepsInGroups(
                ImmutableSet.of(key("1"), key("2"), key("3")), ImmutableList.of(1, 1, 2)));
  }

  @Test
  public void resetLifecycle() throws Exception {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();

    // Rdep added before reset.
    SkyKey parent1 = key("parent1");
    assertThatNodeEntry(entry)
        .addReverseDepAndCheckIfDone(parent1)
        .isEqualTo(DependencyState.ALREADY_EVALUATING);

    // Dep added before reset.
    SkyKey dep1 = key("dep1");
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    assertThat(entry.getResetDirectDeps()).isEmpty();

    // Reset clears temporary direct deps.
    entry.resetEvaluationFromScratch();
    assertThat(entry.getDirtyState()).isEqualTo(DirtyState.REBUILDING);
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();
    assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
        .isEqualTo(isPartialReevaluation);

    // Rdep added after reset.
    SkyKey parent2 = key("parent2");
    assertThatNodeEntry(entry)
        .addReverseDepAndCheckIfDone(parent2)
        .isEqualTo(DependencyState.ALREADY_EVALUATING);

    // Add back same dep.
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    assertThat(entry.getTemporaryDirectDeps()).containsExactly(ImmutableList.of(dep1));

    // Dep added after reset.
    SkyKey dep2 = key("dep2");
    entry.addSingletonTemporaryDirectDep(dep2);
    assertThat(entry.signalDep(initialVersion, dep2)).isTrue();
    assertThat(entry.getTemporaryDirectDeps())
        .containsExactly(ImmutableList.of(dep1), ImmutableList.of(dep2));

    // Deps registered before the reset must be tracked if keeping edges.
    if (entry.keepsEdges()) {
      assertThat(entry.getResetDirectDeps()).containsExactly(dep1);
    }

    // Set value and check that both parents will be signaled.
    assertThat(setValue(entry, new IntegerValue(1), /* errorInfo= */ null, initialVersion))
        .containsExactly(parent1, parent2);
  }

  @Test
  public void resetTwice_moreDepsRequestedBeforeFirstReset() throws Exception {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();

    // Rdep added before any reset.
    SkyKey parent = key("parent");
    assertThatNodeEntry(entry)
        .addReverseDepAndCheckIfDone(parent)
        .isEqualTo(DependencyState.ALREADY_EVALUATING);

    // Two deps added before first reset.
    SkyKey dep1 = key("dep1");
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    SkyKey dep2 = key("dep2");
    entry.addSingletonTemporaryDirectDep(dep2);
    assertThat(entry.signalDep(initialVersion, dep2)).isTrue();

    // First reset.
    entry.resetEvaluationFromScratch();
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();

    // Add back only one dep.
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    assertThat(entry.getTemporaryDirectDeps()).containsExactly(ImmutableList.of(dep1));

    // Second reset.
    entry.resetEvaluationFromScratch();
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();

    // Both deps added back.
    entry.addSingletonTemporaryDirectDep(dep1);
    assertThat(entry.signalDep(initialVersion, dep1)).isTrue();
    entry.addSingletonTemporaryDirectDep(dep2);
    assertThat(entry.signalDep(initialVersion, dep2)).isTrue();
    assertThat(entry.getTemporaryDirectDeps())
        .containsExactly(ImmutableList.of(dep1), ImmutableList.of(dep2));

    // If tracking of reset deps is required, make sure both deps are reported even though only dep1
    // was registered during the most recent evaluation attempt.
    if (entry.keepsEdges()) {
      assertThat(entry.getResetDirectDeps()).containsExactly(dep1, dep2);
    }

    // Set value and check that parent will be signaled.
    assertThat(setValue(entry, new IntegerValue(1), /* errorInfo= */ null, initialVersion))
        .containsExactly(parent);
  }

  @Test
  public void rewindingLifecycle() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();

    // Rdep that will eventually rewind the entry.
    SkyKey resetParent = key("resetParent");
    assertThatNodeEntry(entry)
        .addReverseDepAndCheckIfDone(resetParent)
        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
    entry.markRebuilding();

    // Node completes.
    assertThat(setValue(entry, new IntegerValue(1), /* errorInfo= */ null, initialVersion))
        .containsExactly(resetParent);
    assertThat(entry.isDirty()).isFalse();
    assertThat(entry.isDone()).isTrue();

    // Rewinding initiated.
    entry.markDirty(DirtyType.REWIND);
    assertThat(entry.isDirty()).isTrue();
    assertThat(entry.isChanged()).isTrue();
    assertThat(entry.isDone()).isFalse();
    assertThat(entry.getTemporaryDirectDeps() instanceof GroupedDeps.WithHashSet)
        .isEqualTo(isPartialReevaluation);

    // Parent declares dep again after resetting.
    var dependencyState =
        entry.keepsEdges()
            ? entry.checkIfDoneForDirtyReverseDep(resetParent)
            : entry.addReverseDepAndCheckIfDone(resetParent);
    assertThat(dependencyState).isEqualTo(DependencyState.NEEDS_SCHEDULING);
    assertThat(entry.getDirtyState()).isEqualTo(DirtyState.NEEDS_REBUILDING);
    assertThat(entry.isReadyToEvaluate()).isTrue();
    assertThat(entry.hasUnsignaledDeps()).isFalse();
    assertThat(entry.getTemporaryDirectDeps()).isEmpty();
    entry.markRebuilding();
    assertThat(entry.getDirtyState()).isEqualTo(DirtyState.REBUILDING);

    // Rewound evaluation completes. The parent that initiated rewinding is signalled.
    assertThat(setValue(entry, new IntegerValue(2), /* errorInfo= */ null, initialVersion))
        .containsExactly(resetParent);
    assertThat(entry.getValue()).isEqualTo(new IntegerValue(2));
    assertThat(entry.getVersion()).isEqualTo(initialVersion);
  }

  @Test
  public void concurrentRewindingAllowed() throws InterruptedException {
    InMemoryNodeEntry entry = createEntry();
    entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
    entry.markRebuilding();
    setValue(entry, new SkyValue() {}, /* errorInfo= */ null, initialVersion);
    assertThat(entry.isDirty()).isFalse();
    assertThat(entry.isDone()).isTrue();

    assertThat(entry.markDirty(DirtyType.REWIND)).isNotNull();
    assertThat(entry.markDirty(DirtyType.REWIND)).isNull();

    assertThat(entry.isDirty()).isTrue();
    assertThat(entry.isChanged()).isTrue();
    assertThat(entry.isDone()).isFalse();
    assertThat(entry.getDirtyState()).isEqualTo(DirtyState.NEEDS_REBUILDING);
  }

  @CanIgnoreReturnValue
  static Set<SkyKey> setValue(
      NodeEntry entry, SkyValue value, @Nullable ErrorInfo errorInfo, Version graphVersion)
      throws InterruptedException {
    return entry.setValue(
        ValueWithMetadata.normal(value, errorInfo, NO_EVENTS),
        checkNotNull(graphVersion),
        /* maxTransitiveSourceVersion= */ null);
  }
}