From 0c66deed46dfba225c380ad266dedc93aaf6677f Mon Sep 17 00:00:00 2001 From: Dmitry Lomov Date: Mon, 13 Feb 2017 17:24:43 +0000 Subject: Add an algorithm to reduce aspect paths according to aspects' visibility to each other. Aspects negotiate their visibility by advertizing and requiring providers. The algorithm is not used yet (that is future work). -- PiperOrigin-RevId: 147354682 MOS_MIGRATED_REVID=147354682 --- .../build/lib/analysis/AspectCollection.java | 378 +++++++++++++++++++++ 1 file changed, 378 insertions(+) create mode 100644 src/main/java/com/google/devtools/build/lib/analysis/AspectCollection.java (limited to 'src/main/java/com/google/devtools/build/lib/analysis/AspectCollection.java') diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AspectCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/AspectCollection.java new file mode 100644 index 0000000000..0018525784 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/analysis/AspectCollection.java @@ -0,0 +1,378 @@ +// Copyright 2017 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.analysis; + +import com.google.common.base.Objects; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable; +import com.google.devtools.build.lib.packages.Aspect; +import com.google.devtools.build.lib.packages.AspectDefinition; +import com.google.devtools.build.lib.packages.AspectDescriptor; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.LinkedHashMap; +import java.util.Map.Entry; +import java.util.Set; + +/** + * Represents aspects that should be applied to a target as part of {@link Dependency}. + * + * {@link Dependency} encapsulates all information that is needed to analyze an edge between + * an AspectValue or a ConfiguredTargetValue and their direct dependencies, and + * {@link AspectCollection} represents an aspect-related part of this information. + * + * Analysis arrives to a particular node in target graph with an ordered list of aspects that need + * to be applied. Some of those aspects should visible to the node in question; some of them + * are not directly visible, but are visible to other aspects, as specified by + * {@link AspectDefinition#getRequiredProvidersForAspects()}. + * + * As an example, of all these things in interplay, consider android_binary rule depending + * on java_proto_library rule depending on proto_library rule; consider further that + * we analyze the android_binary with some ide_info aspect: + * 
+ *    proto_library(name = "pl") + ide_info_aspect
+ *       ^
+ *       | [java_proto_aspect]
+ *    java_proto_library(name = "jpl") + ide_info_aspect
+ *       ^
+ *       | [DexArchiveAspect]
+ *    android_binary(name = "ab") + ide_info_aspect
+ *
+ * ide_info_aspect is interested in java_proto_aspect, but not in DexArchiveAspect. + * + * Let's look is the {@link AspectCollection} for a Dependency representing a jpl->pl edge + * for ide_info_aspect application to target jpl: + * + * + * More details on members of {@link AspectCollection} follow, as well as more examples + * of aspect visibility rules. + * + * + *

{@link AspectDeps} is a class that represents an aspect and all aspects that are directly + * visible to it.

+ * + *

{@link #getVisibleAspects()} returns aspects that should be visible to the node in question. + *

+ * + *

{@link #getAllAspects()} return all aspects that should be applied to the target, + * in topological order.

+ * + *

In the following scenario, consider rule ri sending an aspect ai + * to its dependency: + * 

+ *      [r0]
+ *       ^
+ *  (a1) |
+ *      [r1]
+ *  (a2) |
+ *      [r2]
+ *  (a3) |
+ *      [r3]
+ *
+ * + * When a3 is propagated to target r0, the analysis arrives there with a path [a1, a2, a3]. + * Since we analyse the propagation of aspect a3, the only visible aspect is a3. + * + *

Let's first assume that aspect a3 wants to see aspects a1 and a2, but aspects a1 and a2 are + * not interested in each other (according to their + * {@link AspectDefinition#getRequiredProvidersForAspects()}). + * + * Since a3 is interested in all aspects, the result of {@link #getAllAspects()} will be + * [a1, a2, a3], and {@link AspectCollection} will be: + *

+ * + *

Now what happens if a3 is interested in a2 but not a1, and a2 is interested in a1? + * Again, all aspects are transitively interesting to a visible a3, so {@link #getAllAspects()} + * will be [a1, a2, a3], but {@link AspectCollection} will now be: + *

+ * + *

As a final example, what happens if a3 is interested in a1, and a1 is interested in a2, but + * a3 is not interested in a2? Now the result of {@link #getAllAspects()} will be [a1, a3]. + * a1 is interested in a2, but a2 comes later in the path than a1, so a1 does not see it (a1 only + * started propagating on r1 -> r0 edge, and there is now a2 originating on that path). + * And {@link AspectCollection} will now be: + *

+ * Note that is does not matter if a2 is interested in a1 or not - since no one after it + * in the path is interested in it, a2 is filtered out. + *

+ */ +@Immutable +public final class AspectCollection { + /** all aspects in the path; transitively visible to {@link #visibleAspects} */ + private final ImmutableSet aspectPath; + + /** aspects that should be visible to a dependency */ + private final ImmutableSet visibleAspects; + + public static final AspectCollection EMPTY = new AspectCollection( + ImmutableSet.of(), ImmutableSet.of()); + + + private AspectCollection( + ImmutableSet allAspects, + ImmutableSet visibleAspects) { + this.aspectPath = allAspects; + this.visibleAspects = visibleAspects; + } + + public Iterable getAllAspects() { + return aspectPath; + } + + public ImmutableSet getVisibleAspects() { + return visibleAspects; + } + + public boolean isEmpty() { + return aspectPath.isEmpty(); + } + + @Override + public int hashCode() { + return aspectPath.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof AspectCollection)) { + return false; + } + AspectCollection that = (AspectCollection) obj; + return Objects.equal(aspectPath, that.aspectPath); + } + + + /** + * Represents an aspect with all the aspects it depends on + * (within an {@link AspectCollection}. + * + * We preserve the order of aspects to correspond to the order in the + * original {@link AspectCollection#aspectPath}, although that is not + * strictly needed semantically. + */ + @Immutable + public static final class AspectDeps { + private final AspectDescriptor aspect; + private final ImmutableList dependentAspects; + + private AspectDeps(AspectDescriptor aspect, + ImmutableList dependentAspects) { + this.aspect = aspect; + this.dependentAspects = dependentAspects; + } + + public AspectDescriptor getAspect() { + return aspect; + } + + public ImmutableList getDependentAspects() { + return dependentAspects; + } + } + + public static AspectCollection createForTests(ImmutableSet descriptors) { + ImmutableSet.Builder depsBuilder = ImmutableSet.builder(); + for (AspectDescriptor descriptor : descriptors) { + depsBuilder.add(new AspectDeps(descriptor, ImmutableList.of())); + } + return new AspectCollection(descriptors, depsBuilder.build()); + } + + /** + * Creates an {@link AspectCollection} from an ordered list of aspects and + * a set of visible aspects. + * + * The order of aspects is reverse to the order in which they originated, with + * the earliest originating occurring last in the list. + */ + public static AspectCollection create( + Iterable aspectPath, + Set visibleAspects) throws AspectCycleOnPathException { + LinkedHashMap aspectMap = deduplicateAspects(aspectPath); + + LinkedHashMap> deps = + new LinkedHashMap<>(); + + // Calculate all needed aspects (either visible from outside or visible to + // other needed aspects). Already discovered needed aspects are in key set of deps. + // 1) Start from the end of the path. The aspect only sees other aspects that are + // before it + // 2) If the 'aspect' is visible from outside, it is needed. + // 3) Otherwise, check whether 'aspect' is visible to any already needed aspects, + // if it is visible to a needed 'depAspect', + // add the 'aspect' to a list of aspects visible to 'depAspect'. + // if 'aspect' is needed, add it to 'deps'. + // At the end of this algorithm, key set of 'deps' contains a subset of original + // aspect list consisting only of needed aspects, in reverse (since we iterate + // the original list in reverse). + // + // deps[aspect] contains all aspects that 'aspect' needs, in reverse order. + for (Entry aspect : + ImmutableList.copyOf(aspectMap.entrySet()).reverse()) { + boolean needed = visibleAspects.contains(aspect.getKey()); + for (AspectDescriptor depAspectDescriptor : deps.keySet()) { + if (depAspectDescriptor.equals(aspect.getKey())) { + continue; + } + Aspect depAspect = aspectMap.get(depAspectDescriptor); + if (depAspect.getDefinition().getRequiredProvidersForAspects() + .isSatisfiedBy(aspect.getValue().getDefinition().getAdvertisedProviders())) { + deps.get(depAspectDescriptor).add(aspect.getKey()); + needed = true; + } + } + if (needed && !deps.containsKey(aspect.getKey())) { + deps.put(aspect.getKey(), new ArrayList()); + } + } + + // Record only the needed aspects from all aspects, in correct order. + ImmutableList neededAspects = ImmutableList.copyOf(deps.keySet()).reverse(); + + // Calculate visible aspect paths. + HashMap aspectPaths = new HashMap<>(); + ImmutableSet.Builder visibleAspectPaths = ImmutableSet.builder(); + for (AspectDescriptor visibleAspect : visibleAspects) { + visibleAspectPaths.add(buildAspectDeps(visibleAspect, aspectPaths, deps)); + } + return new AspectCollection(ImmutableSet.copyOf(neededAspects), + visibleAspectPaths.build()); + } + + /** + * Deduplicate aspects in path. + * + * @throws AspectCycleOnPathException if an aspect occurs twice on the path and + * the second occurrence sees a different set of aspects. + */ + private static LinkedHashMap deduplicateAspects( + Iterable aspectPath) throws AspectCycleOnPathException { + + LinkedHashMap aspectMap = new LinkedHashMap<>(); + ArrayList seenAspects = new ArrayList<>(); + for (Aspect aspect : aspectPath) { + if (!aspectMap.containsKey(aspect.getDescriptor())) { + aspectMap.put(aspect.getDescriptor(), aspect); + seenAspects.add(aspect); + } else { + validateDuplicateAspect(aspect, seenAspects); + } + } + return aspectMap; + } + + /** + * Detect inconsistent duplicate occurrence of an aspect on the path. + * There is a previous occurrence of {@code aspect} in {@code seenAspects}. + * + * If in between that previous occurrence and the newly discovered occurrence + * there is an aspect that is visible to {@code aspect}, then the second occurrence + * is inconsistent - the set of aspects it sees is different from the first one. + */ + private static void validateDuplicateAspect(Aspect aspect, ArrayList seenAspects) + throws AspectCycleOnPathException { + for (int i = seenAspects.size() - 1; i >= 0; i--) { + Aspect seenAspect = seenAspects.get(i); + if (aspect.getDescriptor().equals(seenAspect.getDescriptor())) { + // This is a previous occurrence of the same aspect. + return; + } + + if (aspect.getDefinition().getRequiredProvidersForAspects() + .isSatisfiedBy(seenAspect.getDefinition().getAdvertisedProviders())) { + throw new AspectCycleOnPathException(aspect.getDescriptor(), seenAspect.getDescriptor()); + } + } + } + + private static AspectDeps buildAspectDeps(AspectDescriptor descriptor, + HashMap aspectPaths, + LinkedHashMap> deps) { + if (aspectPaths.containsKey(descriptor)) { + return aspectPaths.get(descriptor); + } + + ImmutableList.Builder aspectPathBuilder = ImmutableList.builder(); + ArrayList depList = deps.get(descriptor); + + // deps[aspect] contains all aspects visible to 'aspect' in reverse order. + for (int i = depList.size() - 1; i >= 0; i--) { + aspectPathBuilder.add(buildAspectDeps(depList.get(i), aspectPaths, deps)); + } + AspectDeps aspectPath = new AspectDeps(descriptor, aspectPathBuilder.build()); + aspectPaths.put(descriptor, aspectPath); + return aspectPath; + } + + /** + * Signals an inconsistency on aspect path: an aspect occurs twice on the path and + * the second occurrence sees a different set of aspects. + * + * {@link #getAspect()} is the aspect occuring twice, and {@link #getPreviousAspect()} + * is the aspect that the second occurrence sees but the first does not. + */ + public static class AspectCycleOnPathException extends Exception { + + private final AspectDescriptor aspect; + private final AspectDescriptor previousAspect; + + public AspectCycleOnPathException(AspectDescriptor aspect, AspectDescriptor previousAspect) { + super(String.format("Aspect %s is applied twice, both before and after aspect %s", + aspect.getDescription(), previousAspect.getDescription() + )); + this.aspect = aspect; + this.previousAspect = previousAspect; + } + + public AspectDescriptor getAspect() { + return aspect; + } + + public AspectDescriptor getPreviousAspect() { + return previousAspect; + } + } +} \ No newline at end of file -- cgit v1.2.3