Extract common logic for detecting action and artifact prefix conflicts.

--
MOS_MIGRATED_REVID=120145833

4 files changed, 110 insertions, 55 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/Actions.java b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
index 28aca9100b..3878fcd148 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Actions.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
@@ -14,11 +14,21 @@
 
 package com.google.devtools.build.lib.actions;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.escape.Escaper;
 import com.google.common.escape.Escapers;
+import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.SortedMap;
 
 /**
  * Helper class for actions.
@@ -59,6 +69,95 @@ public final class Actions {
     return true;
   }
 
+
+  /**
+   * Finds action conflicts. An action conflict happens if two actions generate the same output
+   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
+   *
+   * @param actions a list of actions to check for action conflicts
+   * @return a map between generated artifacts and their associated generating actions. If there is
+   *     more than one action generating the same output artifact, only one action is chosen.
+   * @throws ActionConflictException iff there are two unshareable actions generating the same
+   *     output
+   */
+  public static Map<Artifact, Action> filterSharedActionsAndThrowActionConflict(
+      Iterable<Action> actions) throws ActionConflictException {
+    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
+        actions, /*allowSharedAction=*/ true);
+  }
+
+  private static Map<Artifact, Action> maybeFilterSharedActionsAndThrowIfConflict(
+      Iterable<Action> actions, boolean allowSharedAction) throws ActionConflictException {
+    Map<Artifact, Action> generatingActions = new HashMap<>();
+    for (Action action : actions) {
+      for (Artifact artifact : action.getOutputs()) {
+        Action previousAction = generatingActions.put(artifact, action);
+        if (previousAction != null && previousAction != action) {
+          if (!allowSharedAction || !Actions.canBeShared(previousAction, action)) {
+            throw new ActionConflictException(artifact, previousAction, action);
+          }
+        }
+      }
+    }
+    return generatingActions;
+  }
+
+  /**
+   * Finds Artifact prefix conflicts between generated artifacts. An artifact prefix conflict
+   * happens if one action generates an artifact whose path is a prefix of another artifact's path.
+   * Those two artifacts cannot exist simultaneously in the output tree.
+   *
+   * @param actionGraph the {@link ActionGraph} to query for artifact conflicts
+   * @param artifactPathMap a map mapping generated artifacts to their exec paths
+   * @return A map between actions that generated the conflicting artifacts and their associated
+   *     {@link ArtifactPrefixConflictException}.
+   */
+  public static Map<Action, ArtifactPrefixConflictException> findArtifactPrefixConflicts(
+      ActionGraph actionGraph, SortedMap<PathFragment, Artifact> artifactPathMap) {
+    // No actions in graph -- currently happens only in tests. Special-cased because .next() call
+    // below is unconditional.
+    if (artifactPathMap.isEmpty()) {
+      return ImmutableMap.<Action, ArtifactPrefixConflictException>of();
+    }
+
+    // Keep deterministic ordering of bad actions.
+    Map<Action, ArtifactPrefixConflictException> badActions = new LinkedHashMap();
+    Iterator<PathFragment> iter = artifactPathMap.keySet().iterator();
+
+    // Report an error for every derived artifact which is a prefix of another.
+    // If x << y << z (where x << y means "y starts with x"), then we only report (x,y), (x,z), but
+    // not (y,z).
+    for (PathFragment pathJ = iter.next(); iter.hasNext(); ) {
+      // For each comparison, we have a prefix candidate (pathI) and a suffix candidate (pathJ).
+      // At the beginning of the loop, we set pathI to the last suffix candidate, since it has not
+      // yet been tested as a prefix candidate, and then set pathJ to the paths coming after pathI,
+      // until we come to one that does not contain pathI as a prefix. pathI is then verified not to
+      // be the prefix of any path, so we start the next run of the loop.
+      PathFragment pathI = pathJ;
+      // Compare pathI to the paths coming after it.
+      while (iter.hasNext()) {
+        pathJ = iter.next();
+        if (pathJ.startsWith(pathI)) { // prefix conflict.
+          Artifact artifactI = Preconditions.checkNotNull(artifactPathMap.get(pathI), pathI);
+          Artifact artifactJ = Preconditions.checkNotNull(artifactPathMap.get(pathJ), pathJ);
+          Action actionI =
+              Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactI), artifactI);
+          Action actionJ =
+              Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactJ), artifactJ);
+          if (actionI.shouldReportPathPrefixConflict(actionJ)) {
+            ArtifactPrefixConflictException exception = new ArtifactPrefixConflictException(pathI,
+                pathJ, actionI.getOwner().getLabel(), actionJ.getOwner().getLabel());
+            badActions.put(actionI, exception);
+            badActions.put(actionJ, exception);
+          }
+        } else { // pathJ didn't have prefix pathI, so no conflict possible for pathI.
+          break;
+        }
+      }
+    }
+    return ImmutableMap.copyOf(badActions);
+  }
+
   /**
    * Returns the escaped name for a given relative path as a string. This takes
    * a short relative path and turns it into a string suitable for use as a
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
index a78b6a4810..e40817c137 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
@@ -17,6 +17,7 @@ import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
@@ -38,7 +39,7 @@ public class ActionLookupValue implements SkyValue {
   private static Map<Artifact, Action> filterSharedActionsAndThrowRuntimeIfConflict(
       Iterable<Action> actions) {
     try {
-      return ConfiguredTargetFunction.filterSharedActionsAndThrowIfConflict(actions);
+      return Actions.filterSharedActionsAndThrowActionConflict(actions);
     } catch (ActionConflictException e) {
       // Programming bug.
       throw new IllegalStateException(e);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 48b046d0ef..4701750eb6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -850,7 +850,8 @@ final class ConfiguredTargetFunction implements SkyFunction {
     // Check for conflicting actions within this configured target (that indicates a bug in the
     // rule implementation).
     try {
-      generatingActions = filterSharedActionsAndThrowIfConflict(analysisEnvironment.getRegisteredActions());
+      generatingActions = Actions.filterSharedActionsAndThrowActionConflict(
+          analysisEnvironment.getRegisteredActions());
     } catch (ActionConflictException e) {
       throw new ConfiguredTargetFunctionException(e);
     }
@@ -858,21 +859,6 @@ final class ConfiguredTargetFunction implements SkyFunction {
         configuredTarget, generatingActions, transitivePackages.build());
   }
 
-  static Map<Artifact, Action> filterSharedActionsAndThrowIfConflict(Iterable<Action> actions)
-      throws ActionConflictException {
-    Map<Artifact, Action> generatingActions = new HashMap<>();
-    for (Action action : actions) {
-      for (Artifact artifact : action.getOutputs()) {
-        Action previousAction = generatingActions.put(artifact, action);
-        if (previousAction != null && previousAction != action
-            && !Actions.canBeShared(previousAction, action)) {
-          throw new ActionConflictException(artifact, previousAction, action);
-        }
-      }
-    }
-    return generatingActions;
-  }
-
   /**
    * An exception indicating that there was a problem during the construction of
    * a ConfiguredTargetValue.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 78c4dee297..520cc0f0b6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -77,7 +77,6 @@ import com.google.protobuf.ByteString;
 import java.io.IOException;
 import java.util.Collection;
 import java.util.HashSet;
-import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -222,44 +221,14 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
     ActionGraph actionGraph = result.first;
     SortedMap<PathFragment, Artifact> artifactPathMap = result.second;
 
-    // Report an error for every derived artifact which is a prefix of another.
-    // If x << y << z (where x << y means "y starts with x"), then we only report (x,y), (x,z), but
-    // not (y,z).
-    Iterator<PathFragment> iter = artifactPathMap.keySet().iterator();
-    if (!iter.hasNext()) {
-      // No actions in graph -- currently happens only in tests. Special-cased because .next() call
-      // below is unconditional.
-      this.badActionMap = ImmutableMap.of();
-      return;
-    }
-    for (PathFragment pathJ = iter.next(); iter.hasNext(); ) {
-      // For each comparison, we have a prefix candidate (pathI) and a suffix candidate (pathJ).
-      // At the beginning of the loop, we set pathI to the last suffix candidate, since it has not
-      // yet been tested as a prefix candidate, and then set pathJ to the paths coming after pathI,
-      // until we come to one that does not contain pathI as a prefix. pathI is then verified not to
-      // be the prefix of any path, so we start the next run of the loop.
-      PathFragment pathI = pathJ;
-      // Compare pathI to the paths coming after it.
-      while (iter.hasNext()) {
-        pathJ = iter.next();
-        if (pathJ.startsWith(pathI)) { // prefix conflict.
-          Artifact artifactI = Preconditions.checkNotNull(artifactPathMap.get(pathI), pathI);
-          Artifact artifactJ = Preconditions.checkNotNull(artifactPathMap.get(pathJ), pathJ);
-          Action actionI =
-              Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactI), artifactI);
-          Action actionJ =
-              Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactJ), artifactJ);
-          if (actionI.shouldReportPathPrefixConflict(actionJ)) {
-            ArtifactPrefixConflictException exception = new ArtifactPrefixConflictException(pathI,
-                pathJ, actionI.getOwner().getLabel(), actionJ.getOwner().getLabel());
-            temporaryBadActionMap.put(actionI, new ConflictException(exception));
-            temporaryBadActionMap.put(actionJ, new ConflictException(exception));
-          }
-        } else { // pathJ didn't have prefix pathI, so no conflict possible for pathI.
-          break;
-        }
-      }
+    Map<Action, ArtifactPrefixConflictException> actionsWithArtifactPrefixConflict =
+        Actions.findArtifactPrefixConflicts(actionGraph, artifactPathMap);
+    for (Map.Entry<Action, ArtifactPrefixConflictException> actionExceptionPair :
+        actionsWithArtifactPrefixConflict.entrySet()) {
+      temporaryBadActionMap.put(
+          actionExceptionPair.getKey(), new ConflictException(actionExceptionPair.getValue()));
     }
+
     this.badActionMap = ImmutableMap.copyOf(temporaryBadActionMap);
   }