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