blob: e582240e645e0b6d9cf76bf712bab36f04d29183 [file] [log] [blame]
// 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);
}
}