Changes DependencyResolver <Attribute, Dep> map from a ListMultimap to new class

OrderedSetMultimap. This maintains insertion order while eliminating duplicates.

Certain rules, in particular, otherwise break this invariant:
https://github.com/bazelbuild/bazel/blo[]e3e28274cca5b87f48abe33884edb84016dd3/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java#L403

There's no reason (to my knowledge) to need multiple instances of the same <Attribute, Dependency> pair.

More context from Google code review:

(Michael Staib):
> There are many things which pass around a dependentNodeMap or help construct one or modify one. We want an interface which has the right guarantees.
> ListMultimap is not the right interface because it has no guarantee of unique elements, which we want - we don't want the problem that this CL ran into, and there's no reason (that we know of, to be confirmed) that anyone would want multiple identical Dependencies.
> SetMultimap is not the right interface because it has no guarantee of deterministic iteration order or efficient iteration, which we want - dependency order sometimes matters (e.g., Java classpath or C++ link order).
> We agreed that the best way to get what we want is to define our own interface with its own simultaneous uniqueness and iterability guarantees. Unspoken in the discussion was why we wouldn't just use LinkedHashMultimap as the thing we pass around. IMO the reason for that is that we don't care that it be a LinkedHashMultimap specifically; if tomorrow Guava comes out with a faster cooler map that has deterministic and efficient iteration and guarantees element uniqueness, we want it.
> In this case we're going to make the "interface" be a (final?) class: OrderedSetMultimap, an extension of ForwardingSetMultimap which delegates to LinkedHashMultimap, an implementation which does support both of those guarantees.
> I had mentioned in the conversation that none of the Multimap implementations make guarantees about key iteration order, but this is not true - LinkedHashMultimap preserves key insertion order. We should perhaps declare this as part of the OrderedSetMultimap contract as well.

--
MOS_MIGRATED_REVID=130037643

10 files changed, 100 insertions, 59 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 55bcf81851..5fed4a32fa 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -18,13 +18,10 @@ import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Function;
 import com.google.common.base.Predicate;
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
@@ -74,6 +71,7 @@ import com.google.devtools.build.lib.skyframe.SkyframeAnalysisResult;
 import com.google.devtools.build.lib.skyframe.SkyframeBuildView;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.RegexFilter;
@@ -877,12 +875,12 @@ public class BuildView {
   }
 
   @VisibleForTesting
-  public ListMultimap<Attribute, Dependency> getDirectPrerequisiteDependenciesForTesting(
+  public OrderedSetMultimap<Attribute, Dependency> getDirectPrerequisiteDependenciesForTesting(
       final EventHandler eventHandler, final ConfiguredTarget ct,
       BuildConfigurationCollection configurations)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     if (!(ct.getTarget() instanceof Rule)) {
-      return ArrayListMultimap.create();
+      return OrderedSetMultimap.create();
     }
 
     class SilentDependencyResolver extends DependencyResolver {
@@ -965,23 +963,22 @@ public class BuildView {
     return ImmutableMap.copyOf(keys);
   }
 
-  private ListMultimap<Attribute, ConfiguredTarget> getPrerequisiteMapForTesting(
+  private OrderedSetMultimap<Attribute, ConfiguredTarget> getPrerequisiteMapForTesting(
       final EventHandler eventHandler, ConfiguredTarget target,
       BuildConfigurationCollection configurations)
       throws EvalException, InvalidConfigurationException, InterruptedException {
-    ListMultimap<Attribute, Dependency> depNodeNames = getDirectPrerequisiteDependenciesForTesting(
-        eventHandler, target, configurations);
+    OrderedSetMultimap<Attribute, Dependency> depNodeNames =
+        getDirectPrerequisiteDependenciesForTesting(eventHandler, target, configurations);
 
     ImmutableMap<Dependency, ConfiguredTarget> cts = skyframeExecutor.getConfiguredTargetMap(
         eventHandler,
         target.getConfiguration(), ImmutableSet.copyOf(depNodeNames.values()), false);
 
-    ImmutableListMultimap.Builder<Attribute, ConfiguredTarget> builder =
-        ImmutableListMultimap.builder();
+    OrderedSetMultimap<Attribute, ConfiguredTarget> result = OrderedSetMultimap.create();
     for (Map.Entry<Attribute, Dependency> entry : depNodeNames.entries()) {
-      builder.put(entry.getKey(), cts.get(entry.getValue()));
+      result.put(entry.getKey(), cts.get(entry.getValue()));
     }
-    return builder.build();
+    return result;
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index ac47679ddb..0ace78b551 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.analysis;
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -51,6 +50,7 @@ import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.rules.SkylarkRuleConfiguredTargetBuilder;
 import com.google.devtools.build.lib.rules.fileset.FilesetProvider;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
@@ -79,7 +79,7 @@ public final class ConfiguredTargetFactory {
    * to the {@code AnalysisEnvironment}.
    */
   private NestedSet<PackageSpecification> convertVisibility(
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap, EventHandler reporter,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap, EventHandler reporter,
       Target target, BuildConfiguration packageGroupConfiguration) {
     RuleVisibility ruleVisibility = target.getVisibility();
     if (ruleVisibility instanceof ConstantRuleVisibility) {
@@ -125,7 +125,7 @@ public final class ConfiguredTargetFactory {
   }
 
   private ConfiguredTarget findPrerequisite(
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap, Label label,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap, Label label,
       BuildConfiguration config) {
     for (ConfiguredTarget prerequisite : prerequisiteMap.get(null)) {
       if (prerequisite.getLabel().equals(label) && (prerequisite.getConfiguration() == config)) {
@@ -163,7 +163,8 @@ public final class ConfiguredTargetFactory {
   @Nullable
   public final ConfiguredTarget createConfiguredTarget(AnalysisEnvironment analysisEnvironment,
       ArtifactFactory artifactFactory, Target target, BuildConfiguration config,
-      BuildConfiguration hostConfig, ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      BuildConfiguration hostConfig,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws InterruptedException {
     if (target instanceof Rule) {
@@ -218,7 +219,7 @@ public final class ConfiguredTargetFactory {
   private ConfiguredTarget createRule(
       AnalysisEnvironment env, Rule rule, BuildConfiguration configuration,
       BuildConfiguration hostConfiguration,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     // Visibility computation and checking is done for every rule.
     RuleContext ruleContext =
@@ -310,7 +311,7 @@ public final class ConfiguredTargetFactory {
       RuleConfiguredTarget associatedTarget,
       ConfiguredAspectFactory aspectFactory,
       Aspect aspect,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       BuildConfiguration aspectConfiguration,
       BuildConfiguration hostConfiguration)
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
index 3956037516..6816b42e8d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -14,12 +14,10 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
@@ -45,6 +43,7 @@ import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.util.ArrayList;
@@ -92,14 +91,14 @@ public abstract class DependencyResolver {
    *
    * @return a mapping of each attribute in this rule or aspect to its dependent nodes
    */
-  public final ListMultimap<Attribute, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.<Label>stableOrder();
-    ListMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
         node, hostConfig, aspect, configConditions, rootCauses);
     if (!rootCauses.isEmpty()) {
       throw new IllegalStateException(rootCauses.build().iterator().next().toString());
@@ -135,7 +134,7 @@ public abstract class DependencyResolver {
    *
    * @return a mapping of each attribute in this rule or aspect to its dependent nodes
    */
-  public final ListMultimap<Attribute, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
@@ -144,7 +143,7 @@ public abstract class DependencyResolver {
       throws EvalException, InvalidConfigurationException, InterruptedException {
     Target target = node.getTarget();
     BuildConfiguration config = node.getConfiguration();
-    ListMultimap<Attribute, Dependency> outgoingEdges = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
     if (target instanceof OutputFile) {
       Preconditions.checkNotNull(config);
       visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
@@ -170,7 +169,7 @@ public abstract class DependencyResolver {
       @Nullable Aspect aspect,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Label> rootCauses,
-      ListMultimap<Attribute, Dependency> outgoingEdges)
+      OrderedSetMultimap<Attribute, Dependency> outgoingEdges)
       throws EvalException, InvalidConfigurationException, InterruptedException {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     BuildConfiguration ruleConfig = Preconditions.checkNotNull(node.getConfiguration());
@@ -475,12 +474,13 @@ public abstract class DependencyResolver {
    * @throws IllegalArgumentException if the {@code node} does not refer to a {@link Rule} instance
    */
   public final Collection<Dependency> resolveRuleLabels(TargetAndConfiguration node,
-      ListMultimap<Attribute, Label> depLabels, NestedSetBuilder<Label> rootCauses) {
+      OrderedSetMultimap<Attribute, Label> depLabels, NestedSetBuilder<Label> rootCauses) {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     Rule rule = (Rule) node.getTarget();
-    ListMultimap<Attribute, Dependency> outgoingEdges = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
     RuleResolver depResolver = new RuleResolver(rule, node.getConfiguration(), /*aspect=*/null,
         /*attributeMap=*/null, rootCauses, outgoingEdges);
+    Map<Attribute, Collection<Label>> m = depLabels.asMap();
     for (Map.Entry<Attribute, Collection<Label>> entry : depLabels.asMap().entrySet()) {
       for (Label depLabel : entry.getValue()) {
         depResolver.resolveDep(entry.getKey(), depLabel);
@@ -572,7 +572,7 @@ public abstract class DependencyResolver {
     private final Aspect aspect;
     private final ConfiguredAttributeMapper attributeMap;
     private final NestedSetBuilder<Label> rootCauses;
-    private final ListMultimap<Attribute, Dependency> outgoingEdges;
+    private final OrderedSetMultimap<Attribute, Dependency> outgoingEdges;
     private final List<Attribute> attributes;
 
     /**
@@ -587,7 +587,7 @@ public abstract class DependencyResolver {
      */
     RuleResolver(Rule rule, BuildConfiguration ruleConfig, Aspect aspect,
         ConfiguredAttributeMapper attributeMap, NestedSetBuilder<Label> rootCauses,
-        ListMultimap<Attribute, Dependency> outgoingEdges) {
+        OrderedSetMultimap<Attribute, Dependency> outgoingEdges) {
       this.rule = rule;
       this.ruleConfig = ruleConfig;
       this.aspect = aspect;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index d4cea81c20..321c385d07 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -78,6 +78,7 @@ import com.google.devtools.build.lib.shell.ShellUtils;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.FileTypeSet;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
@@ -1398,7 +1399,7 @@ public final class RuleContext extends TargetContext
     private final PrerequisiteValidator prerequisiteValidator;
     @Nullable private final String aspectName;
     private final ErrorReporter reporter;
-    private ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap;
+    private OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap;
     private ImmutableMap<Label, ConfigMatchingProvider> configConditions;
     private NestedSet<PackageSpecification> visibility;
     private ImmutableMap<String, Attribute> aspectAttributes;
@@ -1455,7 +1456,7 @@ public final class RuleContext extends TargetContext
      * Sets the prerequisites and checks their visibility. It also generates appropriate error or
      * warning messages and sets the error flag as appropriate.
      */
-    Builder setPrerequisites(ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
+    Builder setPrerequisites(OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap) {
       this.prerequisiteMap = Preconditions.checkNotNull(prerequisiteMap);
       return this;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
index ff60869537..cf1afb2de6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -48,14 +49,16 @@ public class TargetContext {
 
   /**
    * The constructor is intentionally package private.
+   *
+   * <p>directPrerequisites is expected to be ordered.
    */
   TargetContext(AnalysisEnvironment env, Target target, BuildConfiguration configuration,
-      List<ConfiguredTarget> directPrerequisites,
+      Iterable<ConfiguredTarget> directPrerequisites,
       NestedSet<PackageSpecification> visibility) {
     this.env = env;
     this.target = target;
     this.configuration = configuration;
-    this.directPrerequisites = directPrerequisites;
+    this.directPrerequisites = ImmutableList.<ConfiguredTarget>copyOf(directPrerequisites);
     this.visibility = visibility;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 9de5f09b81..c1f8c335ec 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
@@ -52,6 +51,7 @@ import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.Dependenc
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -230,7 +230,7 @@ public final class AspectFunction implements SkyFunction {
         return null;
       }
 
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap =
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap =
           ConfiguredTargetFunction.computeDependencies(
               env,
               resolver,
@@ -310,7 +310,7 @@ public final class AspectFunction implements SkyFunction {
       RuleConfiguredTarget associatedTarget,
       BuildConfiguration aspectConfiguration,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
-      ListMultimap<Attribute, ConfiguredTarget> directDeps,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> directDeps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectFunctionException, InterruptedException {
 
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 b09fc1dbe4..9a82ef4d98 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
@@ -16,12 +16,11 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.base.Verify;
-import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.LinkedHashMultimap;
 import com.google.common.collect.LinkedListMultimap;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
@@ -68,6 +67,7 @@ import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -213,7 +213,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
             new ConfiguredValueCreationException(transitiveLoadingRootCauses.build()));
       }
 
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap =
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap =
           computeDependencies(
               env,
               resolver,
@@ -275,7 +275,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
    *     the host configuration as early as possible and pass this reference to all consumers
    * */
   @Nullable
-  static ListMultimap<Attribute, ConfiguredTarget> computeDependencies(
+  static OrderedSetMultimap<Attribute, ConfiguredTarget> computeDependencies(
       Environment env,
       SkyframeDependencyResolver resolver,
       TargetAndConfiguration ctgValue,
@@ -286,8 +286,8 @@ final class ConfiguredTargetFunction implements SkyFunction {
       NestedSetBuilder<Package> transitivePackages,
       NestedSetBuilder<Label> transitiveLoadingRootCauses)
       throws DependencyEvaluationException, AspectCreationException, InterruptedException {
-    // Create the map from attributes to list of (target, configuration) pairs.
-    ListMultimap<Attribute, Dependency> depValueNames;
+    // Create the map from attributes to set of (target, configuration) pairs.
+    OrderedSetMultimap<Attribute, Dependency> depValueNames;
     try {
       depValueNames = resolver.dependentNodeMap(
           ctgValue, hostConfiguration, aspect, configConditions, transitiveLoadingRootCauses);
@@ -318,7 +318,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
     }
 
     // Resolve required aspects.
-    ListMultimap<SkyKey, ConfiguredAspect> depAspects = resolveAspectDependencies(
+    OrderedSetMultimap<SkyKey, ConfiguredAspect> depAspects = resolveAspectDependencies(
         env, depValues, depValueNames.values(), transitivePackages);
     if (depAspects == null) {
       return null;
@@ -421,8 +421,8 @@ final class ConfiguredTargetFunction implements SkyFunction {
    * changes you make.
    */
   @Nullable
-  static ListMultimap<Attribute, Dependency> trimConfigurations(Environment env,
-      TargetAndConfiguration ctgValue, ListMultimap<Attribute, Dependency> originalDeps,
+  static OrderedSetMultimap<Attribute, Dependency> trimConfigurations(Environment env,
+      TargetAndConfiguration ctgValue, OrderedSetMultimap<Attribute, Dependency> originalDeps,
       BuildConfiguration hostConfiguration, RuleClassProvider ruleClassProvider)
       throws DependencyEvaluationException {
 
@@ -450,7 +450,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
     // the results in order (some results need Skyframe-evaluated configurations while others can
     // be computed trivially), we dump them all into this map, then as a final step iterate through
     // the original list and pluck out values from here for the final value.
-    Multimap<AttributeAndLabel, Dependency> trimmedDeps = ArrayListMultimap.create();
+    Multimap<AttributeAndLabel, Dependency> trimmedDeps = LinkedHashMultimap.create();
 
     for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
       Dependency dep = depsEntry.getValue();
@@ -576,7 +576,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
 
     // Re-assemble the output map with the same value ordering (e.g. each attribute's dep labels
     // appear in the same order) as the input.
-    ListMultimap<Attribute, Dependency> result = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Dependency> result = OrderedSetMultimap.create();
     for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
       Collection<Dependency> trimmedAttrDeps = trimmedDeps.get(
           new AttributeAndLabel(depsEntry.getKey(), depsEntry.getValue().getLabel()));
@@ -655,11 +655,11 @@ final class ConfiguredTargetFunction implements SkyFunction {
    * combinations of aspects for a particular configured target, so it would result in a
    * combinatiorial explosion of Skyframe nodes.
    */
-  private static ListMultimap<Attribute, ConfiguredTarget> mergeAspects(
-      ListMultimap<Attribute, Dependency> depValueNames,
+  private static OrderedSetMultimap<Attribute, ConfiguredTarget> mergeAspects(
+      OrderedSetMultimap<Attribute, Dependency> depValueNames,
       Map<SkyKey, ConfiguredTarget> depConfiguredTargetMap,
-      ListMultimap<SkyKey, ConfiguredAspect> depAspectMap) {
-    ListMultimap<Attribute, ConfiguredTarget> result = ArrayListMultimap.create();
+      OrderedSetMultimap<SkyKey, ConfiguredAspect> depAspectMap) {
+    OrderedSetMultimap<Attribute, ConfiguredTarget> result = OrderedSetMultimap.create();
 
     for (Map.Entry<Attribute, Dependency> entry : depValueNames.entries()) {
       Dependency dep = entry.getValue();
@@ -679,13 +679,13 @@ final class ConfiguredTargetFunction implements SkyFunction {
    * <p>Returns null if the required aspects are not computed yet.
    */
   @Nullable
-  private static ListMultimap<SkyKey, ConfiguredAspect> resolveAspectDependencies(
+  private static OrderedSetMultimap<SkyKey, ConfiguredAspect> resolveAspectDependencies(
       Environment env,
       Map<SkyKey, ConfiguredTarget> configuredTargetMap,
       Iterable<Dependency> deps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectCreationException {
-    ListMultimap<SkyKey, ConfiguredAspect> result = ArrayListMultimap.create();
+    OrderedSetMultimap<SkyKey, ConfiguredAspect> result = OrderedSetMultimap.create();
     Set<SkyKey> aspectKeys = new HashSet<>();
     for (Dependency dep : deps) {
       for (Entry<AspectDescriptor, BuildConfiguration> depAspect
@@ -785,7 +785,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
     Map<Label, ConfigMatchingProvider> configConditions = new LinkedHashMap<>();
 
     // Collect the labels of the configured targets we need to resolve.
-    ListMultimap<Attribute, Label> configLabelMap = ArrayListMultimap.create();
+    OrderedSetMultimap<Attribute, Label> configLabelMap = OrderedSetMultimap.create();
     RawAttributeMapper attributeMap = RawAttributeMapper.of(((Rule) target));
     for (Attribute a : ((Rule) target).getAttributes()) {
       for (Label configLabel : attributeMap.getConfigurabilityKeys(a.getName(), a.getType())) {
@@ -901,7 +901,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
   @Nullable
   private ConfiguredTargetValue createConfiguredTarget(SkyframeBuildView view,
       Environment env, Target target, BuildConfiguration configuration,
-      ListMultimap<Attribute, ConfiguredTarget> depValueMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> depValueMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Package> transitivePackages)
       throws ConfiguredTargetFunctionException, InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
index 92b2678d13..e221ae7be1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.base.Function;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
@@ -33,6 +32,7 @@ import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ConflictException;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -97,7 +97,7 @@ public class PostConfiguredTargetFunction implements SkyFunction {
       return null;
     }
 
-    ListMultimap<Attribute, Dependency> deps;
+    OrderedSetMultimap<Attribute, Dependency> deps;
     try {
       BuildConfiguration hostConfiguration =
           buildViewProvider.getSkyframeBuildView().getHostConfiguration(ct.getConfiguration());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 556d781aa0..546a0e2575 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -19,7 +19,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -64,6 +63,7 @@ import com.google.devtools.build.lib.skyframe.BuildInfoCollectionValue.BuildInfo
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ConflictException;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
+import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.skyframe.CycleInfo;
@@ -474,7 +474,7 @@ public final class SkyframeBuildView {
   @Nullable
   ConfiguredTarget createConfiguredTarget(Target target, BuildConfiguration configuration,
       CachingAnalysisEnvironment analysisEnvironment,
-      ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
+      OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     Preconditions.checkState(enableAnalysis,
         "Already in execution phase %s %s", target, configuration);
diff --git a/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java b/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java
new file mode 100644
index 0000000000..a64ddf6602
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java
@@ -0,0 +1,39 @@
+// Copyright 2016 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.lib.util;
+
+import com.google.common.collect.ForwardingSetMultimap;
+import com.google.common.collect.LinkedHashMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.SetMultimap;
+
+/**
+ * A {@code Multimap} that cannot hold duplicate key-value pairs, returns {@code keySet},
+ * {@code keys}, and {@code asMap} collections that iterate through the keys in the order they were
+ * first added, and maintains the insertion ordering of values for a given key. See the
+ * {@link Multimap} documentation for information common to all multimaps.
+ */
+public final class OrderedSetMultimap<K, V> extends ForwardingSetMultimap<K, V> {
+  private final LinkedHashMultimap<K, V> delegate = LinkedHashMultimap.<K, V>create();
+
+  @Override
+  protected SetMultimap delegate() {
+    return delegate;
+  }
+
+  public static <K, V> OrderedSetMultimap<K, V> create() {
+    return new OrderedSetMultimap<K, V>();
+  }
+}