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

1 files changed, 452 insertions, 0 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/analysis/AspectCollectionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/AspectCollectionTest.java
new file mode 100644
index 0000000000..2175ae5fec
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/analysis/AspectCollectionTest.java
@@ -0,0 +1,452 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+import static com.google.common.truth.Truth.assertWithMessage;
+
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.analysis.AspectCollection.AspectCycleOnPathException;
+import com.google.devtools.build.lib.analysis.AspectCollection.AspectDeps;
+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 com.google.devtools.build.lib.packages.AspectParameters;
+import com.google.devtools.build.lib.packages.NativeAspectClass;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
+import com.google.devtools.build.lib.util.Pair;
+import java.util.HashMap;
+import java.util.HashSet;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/**
+ * Tests for {@link AspectCollection}
+ */
+@RunWith(JUnit4.class)
+public class AspectCollectionTest {
+
+  private static final Function<Aspect, AspectDescriptor> ASPECT_TO_DESCRIPTOR =
+      new Function<Aspect, AspectDescriptor>() {
+        @Override
+        public AspectDescriptor apply(Aspect aspect) {
+          return aspect.getDescriptor();
+        }
+      };
+
+  private static final Function<AspectDeps, AspectDescriptor> ASPECT_PATH_TO_DESCRIPTOR =
+      new Function<AspectDeps, AspectDescriptor>() {
+        @Override
+        public AspectDescriptor apply(AspectDeps aspectPath) {
+          return aspectPath.getAspect();
+        }
+      };
+
+  /**
+   * a3 wants a1 and a2, a1 and a2 want no one, path is a1, a2, a3.
+   */
+  @Test
+  public void linearAspectPath1() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3", "a1", "a2");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a1, a2, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a1, a2),
+        expectDeps(a1),
+        expectDeps(a2)
+    );
+  }
+
+  /**
+   * a3 wants a2, a2 wants a1, a1 wants no one, path is a1, a2, a3.
+   */
+  @Test
+  public void linearAspectPath2() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a2");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a1, a2, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a2),
+        expectDeps(a2, a1),
+        expectDeps(a1)
+    );
+  }
+
+  /**
+   * a3 wants a1, a1 wants a2,  path is a1, a2, a3, so a2 comes after a1.
+   */
+  @Test
+  public void validateOrder() throws Exception {
+    Aspect a1 = createAspect("a1", "a2");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3", "a1");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a1, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a1),
+        expectDeps(a1)
+    );
+  }
+
+  /**
+   * a3 wants a1, a1 wants a2, a2 wants a1, path is a1, a2, a3, so a2 comes after a1.
+   */
+  @Test
+  public void validateOrder2() throws Exception {
+    Aspect a1 = createAspect("a1", "a2");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a1");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a1, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a1),
+        expectDeps(a1)
+    );
+  }
+
+  /**
+   * a3 wants no one => a1 and a2 must be removed.
+   */
+  @Test
+  public void unneededRemoved() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a3),
+        ImmutableList.of(a3),
+        expectDeps(a3)
+    );
+  }
+
+  /**
+   * a3 wants itself.
+   */
+  @Test
+  public void recursive() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3", "a3");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a3),
+        ImmutableList.of(a3),
+        expectDeps(a3)
+    );
+  }
+
+  /**
+   * a2 (non-visible aspect) wants itself, a3 wants a2.
+   */
+  @Test
+  public void recursiveNonVisible()  throws Exception{
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2", "a2");
+    Aspect a3 = createAspect("a3", "a2");
+    AspectCollection collection = AspectCollection
+        .create(ImmutableList.of(a1, a2, a3), ImmutableSet.of(a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a2, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a2),
+        expectDeps(a2)
+    );
+  }
+
+  /**
+   * Both a2 and a3 are visible, a2 wants a1, a3 wants nothing.
+   */
+  @Test
+  public void twoVisibleAspects() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3");
+    AspectCollection collection = AspectCollection
+        .create(
+            ImmutableList.of(a1, a2, a3),
+            ImmutableSet.of(a2.getDescriptor(), a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a1, a2, a3),
+        ImmutableList.of(a2, a3),
+        expectDeps(a3),
+        expectDeps(a2, a1),
+        expectDeps(a1)
+    );
+  }
+
+  /**
+   * a2 wants a1, a3 wants a1 and a2, the path is [a2, a1, a2, a3], so a2 occurs twice.
+   *
+   * First occurrence of a2 would not see a1, but the second would: that is an error.
+   */
+  @Test
+  public void duplicateAspect()  throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a2", "a1");
+    try {
+      AspectCollection
+          .create(
+              ImmutableList.of(a2, a1, a2, a3),
+              ImmutableSet.of(a3.getDescriptor()));
+      Assert.fail();
+    } catch (AspectCycleOnPathException e) {
+      assertThat(e.getAspect()).isEqualTo(a2.getDescriptor());
+      assertThat(e.getPreviousAspect()).isEqualTo(a1.getDescriptor());
+    }
+  }
+
+  /**
+   * a2 wants a1, a3 wants a2, the path is [a2, a1, a2, a3], so a2 occurs twice.
+   *
+   * First occurrence of a2 would not see a1, but the second would: that is an error.
+   */
+  @Test
+  public void duplicateAspect2() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a2");
+    try {
+      AspectCollection
+          .create(
+              ImmutableList.of(a2, a1, a2, a3),
+              ImmutableSet.of(a3.getDescriptor()));
+      Assert.fail();
+    } catch (AspectCycleOnPathException e) {
+      assertThat(e.getAspect()).isEqualTo(a2.getDescriptor());
+      assertThat(e.getPreviousAspect()).isEqualTo(a1.getDescriptor());
+    }
+  }
+
+  /**
+   *  a3 wants a1 and a2, a2 does not want a1.
+   *  The path is [a2, a1, a2, a3], so a2 occurs twice.
+   *  Second occurrence of a2 is consistent with the first.
+   */
+  @Test
+  public void duplicateAspect2a() throws Exception {
+    Aspect a1 = createAspect("a1");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3", "a1", "a2");
+
+    AspectCollection collection = AspectCollection.create(
+        ImmutableList.of(a2, a1, a2, a3),
+        ImmutableSet.of(a3.getDescriptor())
+    );
+
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a2, a1, a3),
+        ImmutableList.of(a3),
+        expectDeps(a3, a2, a1),
+        expectDeps(a2),
+        expectDeps(a1)
+    );
+  }
+
+
+  /**
+   * a2 wants a1, a3 wants a1 and a2, a1 wants a2. the path is [a2, a1, a2, a3], so a2 occurs twice.
+   * First occurrence of a2 does not see a1, but the second does => error.
+   */
+  @Test
+  public void duplicateAspect3() throws Exception {
+    Aspect a1 = createAspect("a1", "a2");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a1", "a2");
+    try {
+      AspectCollection
+          .create(
+              ImmutableList.of(a2, a1, a2, a3),
+              ImmutableSet.of(a3.getDescriptor()));
+      Assert.fail();
+    } catch (AspectCycleOnPathException e) {
+      assertThat(e.getAspect()).isEqualTo(a2.getDescriptor());
+      assertThat(e.getPreviousAspect()).isEqualTo(a1.getDescriptor());
+    }
+  }
+
+  /**
+   * a2 wants a1, a3 wants a2, a1 wants a2. the path is [a2, a1, a2, a3], so a2 occurs twice.
+   * First occurrence of a2 does not see a1, but the second does => error.
+   * a1 disappears.
+   */
+  @Test
+  public void duplicateAspect4() throws Exception {
+    Aspect a1 = createAspect("a1", "a2");
+    Aspect a2 = createAspect("a2", "a1");
+    Aspect a3 = createAspect("a3", "a2");
+    try {
+      AspectCollection
+          .create(
+              ImmutableList.of(a2, a1, a2, a3),
+              ImmutableSet.of(a3.getDescriptor()));
+      Assert.fail();
+    } catch (AspectCycleOnPathException e) {
+      assertThat(e.getAspect()).isEqualTo(a2.getDescriptor());
+      assertThat(e.getPreviousAspect()).isEqualTo(a1.getDescriptor());
+    }
+  }
+
+  /**
+   * a2 and a3 are visible.
+   * a3 wants a2, a1 wants a2. The path is [a2, a1, a2, a3], so a2 occurs twice.
+   * First occurrence of a2 is consistent with the second.
+   * a1 disappears.
+   */
+  @Test
+  public void duplicateAspectVisible() throws Exception {
+    Aspect a1 = createAspect("a1", "a2");
+    Aspect a2 = createAspect("a2");
+    Aspect a3 = createAspect("a3", "a2");
+    AspectCollection collection = AspectCollection
+        .create(
+            ImmutableList.of(a2, a1, a2, a3),
+            ImmutableSet.of(a2.getDescriptor(), a3.getDescriptor()));
+    validateAspectCollection(
+        collection,
+        ImmutableList.of(a2, a3),
+        ImmutableList.of(a2, a3),
+        expectDeps(a3, a2),
+        expectDeps(a2)
+    );
+  }
+
+
+  private static Pair<Aspect, ImmutableList<Aspect>> expectDeps(Aspect a, Aspect... deps) {
+    return Pair.of(a, ImmutableList.copyOf(deps));
+  }
+
+  @SafeVarargs
+  private static void validateAspectCollection(AspectCollection collection,
+      ImmutableList<Aspect> allAspects,
+      ImmutableList<Aspect> visibleAspects,
+      Pair<Aspect, ImmutableList<Aspect>>... expectedPaths) {
+
+    assertThat(collection.getAllAspects())
+        .containsExactlyElementsIn(Iterables.transform(allAspects, ASPECT_TO_DESCRIPTOR))
+        .inOrder();
+    assertThat(Iterables.transform(collection.getVisibleAspects(), ASPECT_PATH_TO_DESCRIPTOR))
+        .containsExactlyElementsIn(Iterables.transform(visibleAspects, ASPECT_TO_DESCRIPTOR))
+        .inOrder();
+    validateAspectPaths(
+        collection,
+        ImmutableList.copyOf(expectedPaths)
+    );
+  }
+
+  private static void validateAspectPaths(AspectCollection collection,
+      ImmutableList<Pair<Aspect, ImmutableList<Aspect>>> expectedList) {
+    HashMap<AspectDescriptor, AspectDeps> allPaths = new HashMap<>();
+    for (AspectDeps aspectPath : collection.getVisibleAspects()) {
+      collectAndValidateAspectDeps(aspectPath, allPaths);
+    }
+
+    HashSet<AspectDescriptor> expectedKeys = new HashSet<>();
+
+    for (Pair<Aspect, ImmutableList<Aspect>> expected : expectedList) {
+      assertThat(allPaths).containsKey(expected.first.getDescriptor());
+      AspectDeps aspectPath = allPaths.get(expected.first.getDescriptor());
+      assertThat(Iterables.transform(aspectPath.getDependentAspects(), ASPECT_PATH_TO_DESCRIPTOR))
+          .containsExactlyElementsIn(Iterables.transform(expected.second, ASPECT_TO_DESCRIPTOR))
+          .inOrder();
+      expectedKeys.add(expected.first.getDescriptor());
+    }
+    assertThat(allPaths.keySet())
+        .containsExactlyElementsIn(expectedKeys);
+  }
+
+  /**
+   * Collects all aspect paths transitively visible from {@code aspectDeps}.
+   * Validates that {@link AspectDeps} instance corresponding to a given {@link AspectDescriptor}
+   * is unique.
+   */
+  private static void collectAndValidateAspectDeps(AspectDeps aspectDeps,
+      HashMap<AspectDescriptor, AspectDeps> allDeps) {
+    if (allDeps.containsKey(aspectDeps.getAspect())) {
+      assertWithMessage(
+          String.format("Two different deps for aspect %s", aspectDeps.getAspect()))
+          .that(allDeps.get(aspectDeps.getAspect()))
+          .isSameAs(aspectDeps);
+      return;
+    }
+    allDeps.put(aspectDeps.getAspect(), aspectDeps);
+    for (AspectDeps path : aspectDeps.getDependentAspects()) {
+      collectAndValidateAspectDeps(path, allDeps);
+    }
+  }
+
+
+  /**
+   * Creates an aspect wiht a class named {@code className} advertizing a provider
+   * {@code className} that requires any of providers {@code requiredAspects}.
+   */
+  private Aspect createAspect(final String className, String... requiredAspects) {
+    ImmutableList.Builder<ImmutableSet<SkylarkProviderIdentifier>> requiredProvidersBuilder =
+        ImmutableList.builder();
+
+    for (String requiredAspect : requiredAspects) {
+      requiredProvidersBuilder.add(
+          ImmutableSet.of((SkylarkProviderIdentifier.forLegacy(requiredAspect))));
+    }
+    final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> requiredProviders =
+        requiredProvidersBuilder.build();
+    return Aspect.forNative(
+        new NativeAspectClass() {
+          @Override
+          public String getName() {
+            return className;
+          }
+
+          @Override
+          public AspectDefinition getDefinition(AspectParameters aspectParameters) {
+            return AspectDefinition.builder(this)
+                .requireAspectsWithProviders(requiredProviders)
+                .advertiseProvider(ImmutableList.of(SkylarkProviderIdentifier.forLegacy(className)))
+                .build();
+          }
+        }
+    );
+  }
+
+
+}