Refactor "determine all dependency edges from all aspects" logic to be a streaming visitation.
In doing so, we use more efficient algorithm that notably doesn't have several large sources of garbage. The inefficiencies and garbage churn of the old algorithm are more easily noticed when you consider the pseudo-code.
The old algorithm for was:
res <- []
for each attribute A of T that entails a label dep
for each label dep L entailed by A
aspectDeps <- {}
for each aspect S of A
if S is satisfied by T
for each attribute A' of S
for each label dep L' entailed by A'
// Note that L' has nothing directly to do with L.
aspectDeps <- aspectDeps U {A', L')
for each {a, l} in aspectDeps
res <- res + [l]
return res
And the new algorithm is:
res <- []
for each attribute A of T that entails a label dep
for each aspect S of A
if there exists a label dep L entailed by A that satisfies S
for each label dep L' entailed by S
res <- res + [L']
return res
This refactor exposes an existing inefficiency in LabelVisitor. I added a TODO comment explaining it.
RELNOTES: None
PiperOrigin-RevId: 237063485
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
index 9cf3a1a..8237982 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
@@ -17,13 +17,10 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableMultimap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
-import com.google.common.collect.LinkedHashMultimap;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;
-import com.google.common.collect.SetMultimap;
import com.google.devtools.build.lib.analysis.config.transitions.ConfigurationTransition;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -38,6 +35,7 @@
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
+import java.util.function.BiConsumer;
import javax.annotation.Nullable;
/**
@@ -172,38 +170,8 @@
return applyToFiles;
}
- /** Returns the attribute -> set of labels that are provided by aspects of attribute. */
- public static ImmutableMultimap<Attribute, Label> visitAspectsIfRequired(
- Target from,
- ImmutableList<Aspect> aspectsOfAttribute,
- Target to,
- DependencyFilter dependencyFilter) {
- // Aspect can be declared only for Rules.
- if (!(from instanceof Rule) || !(to instanceof Rule)) {
- return ImmutableMultimap.of();
- }
- RuleClass ruleClass = ((Rule) to).getRuleClassObject();
- AdvertisedProviderSet providers = ruleClass.getAdvertisedProviders();
- return visitAspectsIfRequired((Rule) from, aspectsOfAttribute, providers, dependencyFilter);
- }
-
- /** Returns the attribute -> set of labels that are provided by aspects of attribute. */
- public static ImmutableMultimap<Attribute, Label> visitAspectsIfRequired(
- Rule from,
- ImmutableList<Aspect> aspectsOfAttribute,
- AdvertisedProviderSet advertisedProviders,
- DependencyFilter dependencyFilter) {
- SetMultimap<Attribute, Label> result = LinkedHashMultimap.create();
- for (Aspect candidateClass : aspectsOfAttribute) {
- // Check if target satisfies condition for this aspect (has to provide all required
- // TransitiveInfoProviders)
- RequiredProviders requiredProviders =
- candidateClass.getDefinition().getRequiredProviders();
- if (requiredProviders.isSatisfiedBy(advertisedProviders)) {
- addAllAttributesOfAspect(from, result, candidateClass, dependencyFilter);
- }
- }
- return ImmutableMultimap.copyOf(result);
+ public static boolean satisfies(Aspect aspect, AdvertisedProviderSet advertisedProviderSet) {
+ return aspect.getDefinition().getRequiredProviders().isSatisfiedBy(advertisedProviderSet);
}
@Nullable
@@ -219,16 +187,23 @@
final Multimap<Attribute, Label> labelBuilder,
Aspect aspect,
DependencyFilter dependencyFilter) {
+ forEachLabelDepFromAllAttributesOfAspect(from, aspect, dependencyFilter, labelBuilder::put);
+ }
+
+ public static void forEachLabelDepFromAllAttributesOfAspect(
+ Rule from,
+ Aspect aspect,
+ DependencyFilter dependencyFilter,
+ BiConsumer<Attribute, Label> consumer) {
LabelVisitor<Attribute> labelVisitor =
(label, aspectAttribute) -> {
- Label repositoryRelative = maybeGetRepositoryRelativeLabel(from, label);
- if (repositoryRelative == null) {
+ Label repositoryRelativeLabel = maybeGetRepositoryRelativeLabel(from, label);
+ if (repositoryRelativeLabel == null) {
return;
}
- labelBuilder.put(aspectAttribute, repositoryRelative);
+ consumer.accept(aspectAttribute, repositoryRelativeLabel);
};
- ImmutableMap<String, Attribute> attributes = aspect.getDefinition().getAttributes();
- for (final Attribute aspectAttribute : attributes.values()) {
+ for (Attribute aspectAttribute : aspect.getDefinition().getAttributes().values()) {
if (!dependencyFilter.apply(aspect, aspectAttribute)) {
continue;
}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
index 4cadef9..e1e982c 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
@@ -17,7 +17,6 @@
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMultimap;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
import com.google.devtools.build.lib.concurrent.ErrorClassifier;
@@ -39,7 +38,6 @@
import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
import com.google.devtools.build.lib.pkgcache.TargetProvider;
import java.util.Collection;
-import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;
@@ -396,15 +394,26 @@
private void visitAspectsIfRequired(
Target from, Attribute attribute, final Target to, int depth, int count) {
// TODO(bazel-team): The getAspects call below is duplicate work for each direct dep entailed
- // by an attribute's value. Consider doing a slight refactor where we make this method call
- // exactly once per Attribute.
- ImmutableList<Aspect> aspectsOfAttribute =
- (from instanceof Rule) ? attribute.getAspects((Rule) from) : ImmutableList.of();
- ImmutableMultimap<Attribute, Label> labelsFromAspects =
- AspectDefinition.visitAspectsIfRequired(from, aspectsOfAttribute, to, edgeFilter);
- // Create an edge from target to the attribute value.
- for (Map.Entry<Attribute, Label> entry : labelsFromAspects.entries()) {
- enqueueTarget(from, entry.getKey(), entry.getValue(), depth, count);
+ // by an attribute's value. Additionally, we might end up enqueueing the same exact visitation
+ // multiple times: consider the case where the same direct dependency is entailed by aspects
+ // of *different* attributes. These visitations get culled later, but we still have to pay the
+ // overhead for all that.
+
+ if (!(from instanceof Rule) || !(to instanceof Rule)) {
+ return;
+ }
+ Rule fromRule = (Rule) from;
+ Rule toRule = (Rule) to;
+ for (Aspect aspect : attribute.getAspects(fromRule)) {
+ if (AspectDefinition.satisfies(
+ aspect, toRule.getRuleClassObject().getAdvertisedProviders())) {
+ AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+ fromRule,
+ aspect,
+ edgeFilter,
+ (aspectAttribute, aspectLabel) ->
+ enqueueTarget(from, aspectAttribute, aspectLabel, depth, count));
+ }
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
index 8e0e8fb..5fd43d2 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
@@ -13,7 +13,6 @@
// limitations under the License.
package com.google.devtools.build.lib.query2.output;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMultimap;
import com.google.common.collect.LinkedListMultimap;
import com.google.common.collect.Multimap;
@@ -50,25 +49,18 @@
}
@Override
- public ImmutableMultimap<Attribute, Label> computeAspectDependencies(Target target,
- DependencyFilter dependencyFilter) throws InterruptedException {
+ public ImmutableMultimap<Attribute, Label> computeAspectDependencies(
+ Target target, DependencyFilter dependencyFilter) throws InterruptedException {
Multimap<Attribute, Label> result = LinkedListMultimap.create();
if (target instanceof Rule) {
Rule rule = (Rule) target;
Multimap<Attribute, Label> transitions =
rule.getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
for (Attribute attribute : transitions.keySet()) {
- ImmutableList<Aspect> aspects = attribute.getAspects(rule);
- for (Label toLabel : transitions.get(attribute)) {
- Target toTarget;
- try {
- toTarget = packageProvider.getTarget(eventHandler, toLabel);
- result.putAll(
- AspectDefinition.visitAspectsIfRequired(
- target, aspects, toTarget, dependencyFilter));
- } catch (NoSuchThingException e) {
- // Do nothing. One of target direct deps has an error. The dependency on the BUILD file
- // (or one of the files included in it) will be reported in the query result of :BUILD.
+ for (Aspect aspect : attribute.getAspects(rule)) {
+ if (hasDepThatSatisfies(aspect, transitions.get(attribute))) {
+ AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+ rule, aspect, dependencyFilter, result::put);
}
}
}
@@ -76,6 +68,29 @@
return ImmutableMultimap.copyOf(result);
}
+ private boolean hasDepThatSatisfies(Aspect aspect, Iterable<Label> labelDeps)
+ throws InterruptedException {
+ for (Label toLabel : labelDeps) {
+ Target toTarget;
+ try {
+ toTarget = packageProvider.getTarget(eventHandler, toLabel);
+ } catch (NoSuchThingException e) {
+ // Do nothing interesting. One of target direct deps has an error. The dependency on the
+ // BUILD file (or one of the files included in it) will be reported in the query result of
+ // :BUILD.
+ continue;
+ }
+ if (!(toTarget instanceof Rule)) {
+ continue;
+ }
+ if (AspectDefinition.satisfies(
+ aspect, ((Rule) toTarget).getRuleClassObject().getAdvertisedProviders())) {
+ return true;
+ }
+ }
+ return false;
+ }
+
@Override
public Set<Label> computeBuildFileDependencies(Package pkg) throws InterruptedException {
Set<Label> result = new LinkedHashSet<>();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
index 19bc9ec..1048fbc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
@@ -23,7 +23,9 @@
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
import com.google.devtools.build.lib.packages.Aspect;
+import com.google.devtools.build.lib.packages.AspectDefinition;
import com.google.devtools.build.lib.packages.Attribute;
import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
import com.google.devtools.build.lib.packages.DependencyFilter;
@@ -41,7 +43,6 @@
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.ValueOrException2;
import java.util.Collection;
-import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
@@ -186,41 +187,53 @@
Environment env)
throws InterruptedException {
if (!(target instanceof Rule)) {
+ // Aspects can be declared only for Rules.
return ImmutableList.of();
}
Rule rule = (Rule) target;
- Map<Label, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> labelDepMap =
- new HashMap<>(depMap.size());
- for (Map.Entry<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> entry :
- depMap.entrySet()) {
- labelDepMap.put(argumentFromKey(entry.getKey()), entry.getValue());
- }
List<SkyKey> depKeys = Lists.newArrayList();
Multimap<Attribute, Label> transitions =
rule.getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
for (Attribute attribute : transitions.keySet()) {
- ImmutableList<Aspect> aspects = attribute.getAspects(rule);
- for (Label toLabel : transitions.get(attribute)) {
- ValueOrException2<NoSuchPackageException, NoSuchTargetException> value =
- labelDepMap.get(toLabel);
- getAspectLabels(rule, aspects, toLabel, value, env)
- .forEach(aspectLabel -> depKeys.add(getKey(aspectLabel)));
+ for (Aspect aspect : attribute.getAspects(rule)) {
+ if (hasDepThatSatisfies(aspect, transitions.get(attribute), depMap, env)) {
+ AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+ rule,
+ aspect,
+ DependencyFilter.ALL_DEPS,
+ (aspectAttribute, aspectLabel) -> depKeys.add(getKey(aspectLabel)));
+ }
}
}
return depKeys;
}
- /** Get the Aspect-related Label deps for the given edge. */
- protected abstract Collection<Label> getAspectLabels(
- Rule fromRule,
- ImmutableList<Aspect> aspectsOfAttribute,
+ @Nullable
+ protected abstract AdvertisedProviderSet getAdvertisedProviderSet(
Label toLabel,
- ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+ @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
Environment env)
throws InterruptedException;
+ private final boolean hasDepThatSatisfies(
+ Aspect aspect,
+ Iterable<Label> depLabels,
+ Map<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> fullDepMap,
+ Environment env)
+ throws InterruptedException {
+ for (Label depLabel : depLabels) {
+ AdvertisedProviderSet advertisedProviderSet =
+ getAdvertisedProviderSet(depLabel, fullDepMap.get(depLabel), env);
+ if (advertisedProviderSet != null
+ && AspectDefinition.satisfies(aspect, advertisedProviderSet)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
// TODO(bazel-team): Unify this logic with that in LabelVisitor, and possibly DependencyResolver.
private static Collection<Label> getLabelDeps(Target target) throws InterruptedException {
if (target instanceof OutputFile) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
index 4366a0c..5f0be6d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
@@ -13,7 +13,6 @@
// limitations under the License.
package com.google.devtools.build.lib.skyframe;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -24,11 +23,9 @@
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.packages.Aspect;
-import com.google.devtools.build.lib.packages.AspectDefinition;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
import com.google.devtools.build.lib.packages.Attribute;
import com.google.devtools.build.lib.packages.ConfigurationFragmentPolicy;
-import com.google.devtools.build.lib.packages.DependencyFilter;
import com.google.devtools.build.lib.packages.NoSuchPackageException;
import com.google.devtools.build.lib.packages.NoSuchTargetException;
import com.google.devtools.build.lib.packages.NoSuchThingException;
@@ -219,36 +216,38 @@
}
}
+ @Nullable
@Override
- protected Collection<Label> getAspectLabels(
- Rule fromRule,
- ImmutableList<Aspect> aspectsOfAttribute,
+ protected AdvertisedProviderSet getAdvertisedProviderSet(
Label toLabel,
- ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
- final Environment env)
+ @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+ Environment env)
throws InterruptedException {
SkyKey packageKey = PackageValue.key(toLabel.getPackageIdentifier());
+ Target toTarget;
try {
PackageValue pkgValue =
(PackageValue) env.getValueOrThrow(packageKey, NoSuchPackageException.class);
if (pkgValue == null) {
- return ImmutableList.of();
+ return null;
}
Package pkg = pkgValue.getPackage();
if (pkg.containsErrors()) {
- // Do nothing. This error was handled when we computed the corresponding
+ // Do nothing interesting. This error was handled when we computed the corresponding
// TransitiveTargetValue.
- return ImmutableList.of();
+ return null;
}
- Target dependedTarget = pkgValue.getPackage().getTarget(toLabel.getName());
- return AspectDefinition.visitAspectsIfRequired(
- fromRule, aspectsOfAttribute, dependedTarget, DependencyFilter.ALL_DEPS)
- .values();
+ toTarget = pkgValue.getPackage().getTarget(toLabel.getName());
} catch (NoSuchThingException e) {
- // Do nothing. This error was handled when we computed the corresponding
+ // Do nothing interesting. This error was handled when we computed the corresponding
// TransitiveTargetValue.
- return ImmutableList.of();
+ return null;
}
+ if (!(toTarget instanceof Rule)) {
+ // Aspect can be declared only for Rules.
+ return null;
+ }
+ return ((Rule) toTarget).getRuleClassObject().getAdvertisedProviders();
}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
index 96cee0f..3f72cf9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
@@ -14,17 +14,13 @@
package com.google.devtools.build.lib.skyframe;
import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.packages.Aspect;
-import com.google.devtools.build.lib.packages.AspectDefinition;
-import com.google.devtools.build.lib.packages.DependencyFilter;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
import com.google.devtools.build.lib.packages.NoSuchPackageException;
import com.google.devtools.build.lib.packages.NoSuchTargetException;
import com.google.devtools.build.lib.packages.NoSuchThingException;
-import com.google.devtools.build.lib.packages.Rule;
import com.google.devtools.build.lib.skyframe.TransitiveTraversalFunction.FirstErrorMessageAccumulator;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.skyframe.SkyFunction;
@@ -89,30 +85,21 @@
}
}
+ @Nullable
@Override
- protected Collection<Label> getAspectLabels(
- Rule fromRule,
- ImmutableList<Aspect> aspectsOfAttribute,
+ protected AdvertisedProviderSet getAdvertisedProviderSet(
Label toLabel,
- ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+ @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
Environment env) {
+ if (toVal == null) {
+ return null;
+ }
try {
- if (toVal == null) {
- return ImmutableList.of();
- }
- TransitiveTraversalValue traversalVal = (TransitiveTraversalValue) toVal.get();
- if (traversalVal == null || traversalVal.getProviders() == null) {
- return ImmutableList.of();
- }
- // Retrieve the providers of the dep from the TransitiveTraversalValue, so we can avoid
- // issuing a dep on its defining Package.
- return AspectDefinition.visitAspectsIfRequired(
- fromRule, aspectsOfAttribute, traversalVal.getProviders(), DependencyFilter.ALL_DEPS)
- .values();
+ return ((TransitiveTraversalValue) toVal.get()).getProviders();
} catch (NoSuchThingException e) {
- // Do nothing. This error was handled when we computed the corresponding
+ // Do nothing interesting. This error was handled when we computed the corresponding
// TransitiveTargetValue.
- return ImmutableList.of();
+ return null;
}
}
