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;
}
