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
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 55bcf81..5fed4a3 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.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.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 @@
}
@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 @@
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 ac47679..0ace78b 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 @@
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.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 @@
* 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 @@
}
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 @@
@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 @@
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 @@
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 3956037..6816b42 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.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 @@
*
* @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 @@
*
* @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 @@
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 @@
@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 @@
* @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 @@
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 @@
*/
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 d4cea81..321c385 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.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 @@
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 @@
* 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 ff60869..cf1afb2 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 @@
/**
* 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;
}
