Permit marking dirty/changed a node more than once

This functionality will be useful for node restarting. More than one
parent node may request the restart of a shared child node, and this
should not fail.

Instead, the returned MarkedDirtyResult indicates whether the dirtying
was redundant, and the calling code can assert on that.

RELNOTES: None.
PiperOrigin-RevId: 201005663

3 files changed, 107 insertions, 46 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 00f52dd73d..bb6a2d1d4b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -475,21 +475,19 @@ public class InMemoryNodeEntry implements NodeEntry {
           DirtyBuildingState.create(isChanged, GroupedList.<SkyKey>create(directDeps), value);
       value = null;
       directDeps = null;
-      return new MarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this));
+      return new FromCleanMarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this));
     }
-    // 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.
-    Preconditions.checkState(isChanged != isChanged(),
-        "Cannot mark node dirty twice or changed twice: %s", this);
+
     Preconditions.checkState(value == null, "Value should have been reset already %s", this);
-    if (isChanged) {
-      // If the changed marker lost the race, we just need to mark changed in this method -- all
-      // other work was done by the dirty marker.
-      getDirtyBuildingState().markChanged();
+    if (isChanged != isChanged()) {
+      if (isChanged) {
+        getDirtyBuildingState().markChanged();
+      }
+      // If !isChanged, then this call made no changes to the node, but redundancy is a property of
+      // the sequence of markDirty calls, not their effects.
+      return FromDirtyMarkedDirtyResult.NOT_REDUNDANT;
     }
-    return null;
+    return FromDirtyMarkedDirtyResult.REDUNDANT;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index ceae771e88..9d2d811594 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -207,7 +207,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
     }
   }
 
-  public static class DirtyingInvalidationState extends InvalidationState {
+  static class DirtyingInvalidationState extends InvalidationState {
     public DirtyingInvalidationState() {
       super(InvalidationType.CHANGED);
     }
@@ -477,7 +477,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
                 // method.
                 // Any exception thrown should be unrecoverable.
                 // This entry remains in the graph in this dirty state until it is re-evaluated.
-                MarkedDirtyResult markedDirtyResult = null;
+                MarkedDirtyResult markedDirtyResult;
                 try {
                   markedDirtyResult = entry.markDirty(isChanged);
                 } catch (InterruptedException e) {
@@ -487,8 +487,13 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
                   // visitation, so we can resume next time.
                   return;
                 }
-                if (markedDirtyResult == null) {
-                  // Another thread has already dirtied this node. Don't do anything in this thread.
+                Preconditions.checkState(
+                    !markedDirtyResult.wasCallRedundant(),
+                    "Node unexpectedly marked dirty or changed twice: %s",
+                    entry);
+                if (!markedDirtyResult.wasClean()) {
+                  // Another thread has already handled this node's rdeps. Don't do anything in this
+                  // thread.
                   if (supportInterruptions) {
                     pendingVisitations.remove(Pair.of(key, invalidationType));
                   }
@@ -496,7 +501,10 @@ public abstract class InvalidatingNodeVisitor<TGraph extends QueryableGraph> {
                 }
                 // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps should
                 // only be marked dirty (because only a dependency of theirs has changed).
-                visit(markedDirtyResult.getReverseDepsUnsafe(), InvalidationType.DIRTIED, key);
+                visit(
+                    markedDirtyResult.getReverseDepsUnsafeIfWasClean(),
+                    InvalidationType.DIRTIED,
+                    key);
 
                 progressReceiver.invalidated(key,
                     EvaluationProgressReceiver.InvalidationState.DIRTY);
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
index eef5487436..c063ce6f67 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -15,11 +15,10 @@ package com.google.devtools.build.skyframe;
 
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
-import javax.annotation.Nullable;
 
 /**
  * A node in the graph without the means to access its value. All operations on this class are
- * thread-safe. Note, however, the warning on the return value of {@link #markDirty}.
+ * thread-safe (note, however, the warning on the return value of {@link #markDirty}).
  *
  * <p>This interface is public only for the benefit of alternative graph implementations outside of
  * the package.
@@ -45,45 +44,101 @@ public interface ThinNodeEntry {
   boolean isChanged();
 
   /**
-   * Marks this node dirty, or changed if {@code isChanged} is true. The node is put in the
-   * just-created state. It will be re-evaluated if necessary during the evaluation phase, but if it
-   * has not changed, it will not force a re-evaluation of its parents.
+   * Marks this node dirty, or changed if {@code isChanged} is true.
    *
-   * <p>{@code markDirty(b)} must not be called on an undone node if {@code isChanged() == b}. It is
-   * the caller's responsibility to ensure that this does not happen. Calling {@code
-   * markDirty(false)} when {@code isChanged() == true} has no effect. The idea here is that the
-   * caller will only ever want to call {@code markDirty()} a second time if a transition from a
-   * dirty-unchanged state to a dirty-changed state is required.
+   * <p>A dirty node P is re-evaluated during the evaluation phase if it's requested and directly
+   * depends on some node C whose value changed since the last evaluation of P. If it's requested
+   * and there is no such node C, P is marked clean.
    *
-   * @return A {@link ThinNodeEntry.MarkedDirtyResult} if the node was previously clean, and {@code
-   *     null} if it was already dirty. If it was already dirty, the caller should abort its
-   *     handling of this node, since another thread is already dealing with it. Note the warning on
-   *     {@link ThinNodeEntry.MarkedDirtyResult} regarding the collection it provides.
+   * <p>A changed node is re-evaluated during the evaluation phase if it's requested (regardless of
+   * the state of its dependencies).
+   *
+   * @return a {@link MarkedDirtyResult} indicating whether the call was redundant and which may
+   *     include the node's reverse deps
    */
-  @Nullable
   @ThreadSafe
   MarkedDirtyResult markDirty(boolean isChanged) throws InterruptedException;
 
-  /**
-   * Returned by {@link #markDirty} if that call changed the node from clean to dirty. Contains an
-   * iterable of the node's reverse deps for efficiency, because the single use case for {@link
-   * #markDirty} is during invalidation, and if such an invalidation call wins, the invalidator
-   * must immediately afterwards schedule the invalidation of the node's reverse deps.
-   *
-   * <p>Warning: {@link #getReverseDepsUnsafe()} may return a live view of the reverse deps
-   * collection of the marked-dirty node. The consumer of this data must be careful only to
-   * iterate over and consume its values while that collection is guaranteed not to change. This
-   * is true during invalidation, because reverse deps don't change during invalidation.
-   */
-  class MarkedDirtyResult {
+  /** Returned by {@link #markDirty}. */
+  interface MarkedDirtyResult {
+
+    /** Returns true iff the node was clean prior to the {@link #markDirty} call. */
+    boolean wasClean();
+
+    /**
+     * Returns true iff the call to {@link #markDirty} was the same as some previous call to {@link
+     * #markDirty} (i.e., sharing the same {@code isChanged} parameter value) since the last time
+     * the node was clean.
+     *
+     * <p>More specifically, this returns true iff the call was {@code n.markDirty(b)} and prior to
+     * the call {@code n.isDirty() && n.isChanged() == b}).
+     */
+    boolean wasCallRedundant();
+
+    /**
+     * If {@code wasClean()}, this returns an iterable of the node's reverse deps for efficiency,
+     * because the {@link #markDirty} caller may be doing graph invalidation, and after dirtying a
+     * node, the invalidation process may want to dirty the node's reverse deps.
+     *
+     * <p>If {@code !wasClean()}, this must not be called. It will throw {@link
+     * IllegalStateException}.
+     *
+     * <p>Warning: the returned iterable may be a live view of the reverse deps collection of the
+     * marked-dirty node. The consumer of this data must be careful only to iterate over and consume
+     * its values while that collection is guaranteed not to change. This is true during
+     * invalidation, because reverse deps don't change during invalidation.
+     */
+    Iterable<SkyKey> getReverseDepsUnsafeIfWasClean();
+  }
+
+  /** A {@link MarkedDirtyResult} returned when {@link #markDirty} is called on a clean node. */
+  class FromCleanMarkedDirtyResult implements MarkedDirtyResult {
     private final Iterable<SkyKey> reverseDepsUnsafe;
 
-    public MarkedDirtyResult(Iterable<SkyKey> reverseDepsUnsafe) {
+    public FromCleanMarkedDirtyResult(Iterable<SkyKey> reverseDepsUnsafe) {
       this.reverseDepsUnsafe = Preconditions.checkNotNull(reverseDepsUnsafe);
     }
 
-    public Iterable<SkyKey> getReverseDepsUnsafe() {
+    @Override
+    public boolean wasClean() {
+      return true;
+    }
+
+    @Override
+    public boolean wasCallRedundant() {
+      return false;
+    }
+
+    @Override
+    public Iterable<SkyKey> getReverseDepsUnsafeIfWasClean() {
       return reverseDepsUnsafe;
     }
   }
+
+  /** A {@link MarkedDirtyResult} returned when {@link #markDirty} is called on a dirty node. */
+  class FromDirtyMarkedDirtyResult implements MarkedDirtyResult {
+    static final FromDirtyMarkedDirtyResult REDUNDANT = new FromDirtyMarkedDirtyResult(true);
+    static final FromDirtyMarkedDirtyResult NOT_REDUNDANT = new FromDirtyMarkedDirtyResult(false);
+
+    private final boolean redundant;
+
+    private FromDirtyMarkedDirtyResult(boolean redundant) {
+      this.redundant = redundant;
+    }
+
+    @Override
+    public boolean wasClean() {
+      return false;
+    }
+
+    @Override
+    public boolean wasCallRedundant() {
+      return redundant;
+    }
+
+    @Override
+    public Iterable<SkyKey> getReverseDepsUnsafeIfWasClean() {
+      throw new IllegalStateException();
+    }
+  }
 }