Rollback of commit 7505d94c19727e3100ac5e16a960bff2cb324f23.

*** Reason for rollback ***

Newly added test fail on Windows platform

Fixes https://github.com/bazelbuild/bazel/issues/2191

*** Original change description ***

Provide deterministic order for split configured deps.

Also:
- Make ConfiguredTargetFunction.getDynamicConfigurations more readable.
- Add a bit more testing coverage for configured dep resolution.

--
PiperOrigin-RevId: 141167110
MOS_MIGRATED_REVID=141167110

2 files changed, 31 insertions, 113 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 04130caf35..df1b7c94a5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -80,8 +80,6 @@ import com.google.devtools.build.skyframe.ValueOrException;
 import com.google.devtools.build.skyframe.ValueOrException2;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
@@ -487,23 +485,15 @@ final class ConfiguredTargetFunction implements SkyFunction {
         ctgValue.getConfiguration().fragmentClasses();
     BuildOptions ctgOptions = ctgValue.getConfiguration().getOptions();
 
-    // Stores the dynamically configured versions of each dependency. This method must preserve the
-    // original label ordering of each attribute. For example, if originalDeps.get("data") is
-    // [":a", ":b"], the dynamic variant must also be [":a", ":b"] in the same order. Because we may
-    // not actualize the results in order (some results need Skyframe-evaluated configurations while
-    // others can be computed trivially), we dump them all into this map, then as a final step
-    // iterate through the original list and pluck out values from here for the final value.
-    //
-    // For split transitions, originaldeps.get("data") = [":a", ":b"] can produce the output
-    // [":a"<config1>, ":a"<config2>, ..., ":b"<config1>, ":b"<config2>, ...]. All instances of ":a"
-    // still appear before all instances of ":b". But the [":a"<config1>, ":a"<config2>"] subset may
-    // be in any (deterministic) order. In particular, this may not be the same order as
-    // SplitTransition.split. If needed, this code can be modified to use that order, but that
-    // involves more runtime in performance-critical code, so we won't make that change without a
-    // clear need.
+    // Stores the trimmed versions of each dependency. This method must preserve the original label
+    // ordering of each attribute. For example, if originalDeps.get("data") is [":a", ":b"], the
+    // trimmed variant must also be [":a", ":b"] in the same order. Because we may not actualize
+    // the results in order (some results need Skyframe-evaluated configurations while others can
+    // be computed trivially), we dump them all into this map, then as a final step iterate through
+    // the original list and pluck out values from here for the final value.
     //
     // This map is used heavily by all builds. Inserts and gets should be as fast as possible.
-    Multimap<AttributeAndLabel, Dependency> dynamicDeps = LinkedHashMultimap.create();
+    Multimap<AttributeAndLabel, Dependency> trimmedDeps = LinkedHashMultimap.create();
 
     // Performance optimization: This method iterates over originalDeps twice. By storing
     // AttributeAndLabel instances in this list, we avoid having to recreate them the second time
@@ -550,7 +540,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
         if (transition == Attribute.ConfigurationTransition.NONE) {
           // The dep uses the same exact configuration.
           putOnlyEntry(
-              dynamicDeps,
+              trimmedDeps,
               attributeAndLabel,
               Dependency.withConfigurationAndAspects(
                   dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
@@ -562,7 +552,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
           // to incur multiple host transitions. So we aggressively optimize to avoid hurting
           // analysis time.
           putOnlyEntry(
-              dynamicDeps,
+              trimmedDeps,
               attributeAndLabel,
               Dependency.withConfigurationAndAspects(
                   dep.getLabel(), hostConfiguration, dep.getAspects()));
@@ -574,6 +564,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
       FragmentsAndTransition transitionKey = new FragmentsAndTransition(depFragments, transition);
       List<BuildOptions> toOptions = transitionsMap.get(transitionKey);
       if (toOptions == null) {
+        ImmutableList.Builder<BuildOptions> toOptionsBuilder = ImmutableList.builder();
         toOptions = getDynamicTransitionOptions(ctgOptions, transition, depFragments,
             ruleClassProvider, !sameFragments);
         transitionsMap.put(transitionKey, toOptions);
@@ -584,7 +575,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
       if (sameFragments && toOptions.size() == 1
           && Iterables.getOnlyElement(toOptions).equals(ctgOptions)) {
         putOnlyEntry(
-            dynamicDeps,
+            trimmedDeps,
             attributeAndLabel,
             Dependency.withConfigurationAndAspects(
                 dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
@@ -616,9 +607,9 @@ final class ConfiguredTargetFunction implements SkyFunction {
           Dependency resolvedDep = Dependency.withConfigurationAndAspects(originalDep.getLabel(),
               trimmedConfig.getConfiguration(), originalDep.getAspects());
           if (attr.attribute.hasSplitConfigurationTransition()) {
-            dynamicDeps.put(attr, resolvedDep);
+            trimmedDeps.put(attr, resolvedDep);
           } else {
-            putOnlyEntry(dynamicDeps, attr, resolvedDep);
+            putOnlyEntry(trimmedDeps, attr, resolvedDep);
           }
         }
       }
@@ -626,7 +617,21 @@ final class ConfiguredTargetFunction implements SkyFunction {
       throw new DependencyEvaluationException(e);
     }
 
-    return sortDynamicallyConfiguredDeps(originalDeps, dynamicDeps, attributesAndLabels);
+    // Re-assemble the output map with the same value ordering (e.g. each attribute's dep labels
+    // appear in the same order) as the input.
+    Iterator<AttributeAndLabel> iterator = attributesAndLabels.iterator();
+    OrderedSetMultimap<Attribute, Dependency> result = OrderedSetMultimap.create();
+    for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
+      AttributeAndLabel attrAndLabel = iterator.next();
+      if (depsEntry.getValue().hasStaticConfiguration()) {
+        result.put(attrAndLabel.attribute, depsEntry.getValue());
+      } else {
+        Collection<Dependency> trimmedAttrDeps = trimmedDeps.get(attrAndLabel);
+        Verify.verify(!trimmedAttrDeps.isEmpty());
+        result.putAll(depsEntry.getKey(), trimmedAttrDeps);
+      }
+    }
+    return result;
   }
 
   /**
@@ -729,51 +734,6 @@ final class ConfiguredTargetFunction implements SkyFunction {
     }
   }
 
-  /**
-   * Determines the output ordering of each <attribute, depLabel> ->
-   * [dep<config1>, dep<config2>, ...] collection produced by a split transition.
-   */
-  private static final Comparator DYNAMIC_SPLIT_DEP_ORDERING =
-      new Comparator<Dependency>() {
-        @Override
-        public int compare(Dependency d1, Dependency d2) {
-          return d1.getConfiguration().getMnemonic().compareTo(d2.getConfiguration().getMnemonic());
-        }
-      };
-
-  /**
-   * Helper method for {@link #getDynamicConfigurations}: returns a copy of the output deps
-   * using the same key and value ordering as the input deps.
-   *
-   * @param originalDeps the input deps with the ordering to preserve
-   * @param dynamicDeps the unordered output deps
-   * @param attributesAndLabels collection of <attribute, depLabel> pairs guaranteed to match
-   *   the ordering of originalDeps.entries(). This is a performance optimization: see
-   *   {@link #getDynamicConfigurations#attributesAndLabels} for details.
-   */
-  private static OrderedSetMultimap<Attribute, Dependency> sortDynamicallyConfiguredDeps(
-      OrderedSetMultimap<Attribute, Dependency> originalDeps,
-      Multimap<AttributeAndLabel, Dependency> dynamicDeps,
-      ArrayList<AttributeAndLabel> attributesAndLabels) {
-    Iterator<AttributeAndLabel> iterator = attributesAndLabels.iterator();
-    OrderedSetMultimap<Attribute, Dependency> result = OrderedSetMultimap.create();
-    for (Map.Entry<Attribute, Dependency> depsEntry : originalDeps.entries()) {
-      AttributeAndLabel attrAndLabel = iterator.next();
-      if (depsEntry.getValue().hasStaticConfiguration()) {
-        result.put(attrAndLabel.attribute, depsEntry.getValue());
-      } else {
-        Collection<Dependency> dynamicAttrDeps = dynamicDeps.get(attrAndLabel);
-        Verify.verify(!dynamicAttrDeps.isEmpty());
-        if (dynamicAttrDeps.size() > 1) {
-          List<Dependency> sortedSplitList = new ArrayList<>(dynamicAttrDeps);
-          Collections.sort(sortedSplitList, DYNAMIC_SPLIT_DEP_ORDERING);
-          dynamicAttrDeps = sortedSplitList;
-        }
-        result.putAll(depsEntry.getKey(), dynamicAttrDeps);
-      }
-    }
-    return result;
-  }
 
   /**
    * Merges the each direct dependency configured target with the aspects associated with it.
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
index 2a44811049..e6bfebc8ac 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
@@ -50,8 +50,7 @@ import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.util.List;
-
+import java.util.Collection;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -210,12 +209,12 @@ public class ConfigurationsForTargetsTest extends AnalysisTestCase {
    *
    * <p>Throws an exception if the attribute can't be found.
    */
-  private List<ConfiguredTarget> getConfiguredDeps(String targetLabel, String attrName)
+  private Collection<ConfiguredTarget> getConfiguredDeps(String targetLabel, String attrName)
       throws Exception {
     Multimap<Attribute, ConfiguredTarget> allDeps = getConfiguredDeps(targetLabel);
     for (Attribute attribute : allDeps.keySet()) {
       if (attribute.getName().equals(attrName)) {
-        return ImmutableList.copyOf(allDeps.get(attribute));
+        return allDeps.get(attribute);
       }
     }
     throw new AssertionError(
@@ -262,47 +261,6 @@ public class ConfigurationsForTargetsTest extends AnalysisTestCase {
     assertThat(genIn.getConfiguration()).isNull();
   }
 
-  @Test
-  public void targetDeps() throws Exception {
-    scratch.file(
-        "a/BUILD",
-        "cc_library(name = 'dep1', srcs = ['dep1.cc'])",
-        "cc_library(name = 'dep2', srcs = ['dep2.cc'])",
-        "cc_binary(name = 'binary', srcs = ['main.cc'], deps = [':dep1', ':dep2'])");
-    List<ConfiguredTarget> deps = getConfiguredDeps("//a:binary", "deps");
-    assertThat(deps).hasSize(2);
-    for (ConfiguredTarget dep : deps) {
-      assertThat(getTargetConfiguration().equalsOrIsSupersetOf(dep.getConfiguration())).isTrue();
-    }
-  }
-
-  @Test
-  public void hostDeps() throws Exception {
-    scratch.file(
-        "a/BUILD",
-        "cc_binary(name = 'host_tool', srcs = ['host_tool.cc'])",
-        "genrule(name = 'gen', srcs = [], cmd = '', outs = ['gen.out'], tools = [':host_tool'])");
-    ConfiguredTarget toolDep = Iterables.getOnlyElement(getConfiguredDeps("//a:gen", "tools"));
-    assertThat(toolDep.getConfiguration().isHostConfiguration()).isTrue();
-  }
-
-  @Test
-  public void splitDeps() throws Exception {
-    scratch.file(
-        "java/a/BUILD",
-        "cc_library(name = 'lib', srcs = ['lib.cc'])",
-        "android_binary(name='a', manifest = 'mainfest.xml', deps = [':lib'])");
-    useConfiguration("--fat_apk_cpu=k8,ppc");
-    List<ConfiguredTarget> deps = getConfiguredDeps("//java/a:a", "deps");
-    assertThat(deps).hasSize(2);
-    assertThat(
-        ImmutableList.<String>of(
-            deps.get(0).getConfiguration().getCpu(),
-            deps.get(1).getConfiguration().getCpu()))
-        .containsExactly("k8", "ppc")
-        .inOrder(); // We don't care what order split deps are listed, but it must be deterministic.
-  }
-
   /** Runs the same test with trimmed dynamic configurations. */
   @TestSpec(size = Suite.SMALL_TESTS)
   @RunWith(JUnit4.class)