Be less naive with CcLibraryHelper precompiled library collision detection.

The naive algorithm was O(n*m) where n = number of precompiled libraries and
m = number of libraries linked during this rule. Ugly!

This one provides hopefully much more reasonable performance.

--
MOS_MIGRATED_REVID=128206057

3 files changed, 54 insertions, 38 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
index c43404e3b9..401fefd881 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
@@ -19,7 +19,9 @@ import com.google.common.base.Joiner;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSetMultimap;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.FileProvider;
@@ -43,6 +45,7 @@ import com.google.devtools.build.lib.rules.cpp.CppConfiguration.HeadersCheckingM
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.rules.cpp.LinkerInputs.LibraryToLink;
 import com.google.devtools.build.lib.syntax.Type;
+import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -920,33 +923,30 @@ public final class CcLibraryHelper {
         // Add the linked outputs of this rule iff we had anything to put in them, but then
         // make sure we're not colliding with some library added from the inputs.
         newOutputsBuilder.merge(originalLinkingOutputs);
-        Iterable<LibraryToLink> allLibraries =
-            Iterables.concat(staticLibraries, picStaticLibraries, dynamicLibraries);
-        for (LibraryToLink precompiledLibrary : allLibraries) {
-          List<LibraryToLink> matchingLibs =
-              originalLinkingOutputs.getLibrariesWithSameIdentifierAs(precompiledLibrary);
-          if (!matchingLibs.isEmpty()) {
-            Iterable<String> matchingLibArtifactNames =
-                Iterables.transform(
-                    matchingLibs,
-                    new Function<LibraryToLink, String>() {
-                      @Override
-                      public String apply(LibraryToLink input) {
-                        return input.getOriginalLibraryArtifact().getFilename();
-                      }
-                    });
-            ruleContext.ruleError(
-                "Can't put "
-                    + precompiledLibrary.getArtifact().getFilename()
-                    + " into the srcs of a "
-                    + ruleContext.getRuleClassNameForLogging()
-                    + " with the same name ("
-                    + ruleContext.getRule().getName()
-                    + ") which also contains other code or objects to link; it shares a name with "
-                    + Joiner.on(", ").join(matchingLibArtifactNames)
-                    + " (output compiled and linked from the non-library sources of this rule), "
-                    + "which could cause confusion");
-          }
+        ImmutableSetMultimap<String, LibraryToLink> precompiledLibraryMap =
+            CcLinkingOutputs.getLibrariesByIdentifier(
+                Iterables.concat(staticLibraries, picStaticLibraries, dynamicLibraries));
+        ImmutableSetMultimap<String, LibraryToLink> linkedLibraryMap =
+            originalLinkingOutputs.getLibrariesByIdentifier();
+        for (String matchingIdentifier :
+            Sets.intersection(precompiledLibraryMap.keySet(), linkedLibraryMap.keySet())) {
+          Iterable<Artifact> matchingInputLibs =
+              LinkerInputs.toNonSolibArtifacts(precompiledLibraryMap.get(matchingIdentifier));
+          Iterable<Artifact> matchingOutputLibs =
+              LinkerInputs.toNonSolibArtifacts(linkedLibraryMap.get(matchingIdentifier));
+          ruleContext.ruleError(
+              "Can't put "
+                  + Joiner.on(", ")
+                      .join(Iterables.transform(matchingInputLibs, FileType.TO_FILENAME))
+                  + " into the srcs of a "
+                  + ruleContext.getRuleClassNameForLogging()
+                  + " with the same name ("
+                  + ruleContext.getRule().getName()
+                  + ") which also contains other code or objects to link; it shares a name with "
+                  + Joiner.on(", ")
+                      .join(Iterables.transform(matchingOutputLibs, FileType.TO_FILENAME))
+                  + " (output compiled and linked from the non-library sources of this rule), "
+                  + "which could cause confusion");
         }
       }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingOutputs.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingOutputs.java
index aab459989c..a763a924bb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingOutputs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingOutputs.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSetMultimap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkStaticness;
@@ -69,19 +70,25 @@ public class CcLinkingOutputs {
   }
 
   /**
-   * Returns all libraries in this CcLinkingOutputs with the same library identifier - i.e., those
-   * which would be considered different forms of the same library by getPreferredLibrary.
+   * Returns a map from library identifiers to sets of LibraryToLink from this CcLinkingOutputs
+   * which share that library identifier.
    */
-  public List<LibraryToLink> getLibrariesWithSameIdentifierAs(LibraryToLink input) {
-    Iterable<LibraryToLink> allLibraries =
+  public ImmutableSetMultimap<String, LibraryToLink> getLibrariesByIdentifier() {
+    return getLibrariesByIdentifier(
         Iterables.concat(
-            staticLibraries, picStaticLibraries, dynamicLibraries, executionDynamicLibraries);
-    ImmutableList.Builder<LibraryToLink> result = new ImmutableList.Builder<>();
-    for (LibraryToLink library : allLibraries) {
-      if (libraryIdentifierOf(library.getOriginalLibraryArtifact())
-          .equals(libraryIdentifierOf(input.getOriginalLibraryArtifact()))) {
-        result.add(library);
-      }
+            staticLibraries, picStaticLibraries, dynamicLibraries, executionDynamicLibraries));
+  }
+
+  /**
+   * Gathers up a map from library identifiers to sets of LibraryToLink which share that library
+   * identifier.
+   */
+  public static ImmutableSetMultimap<String, LibraryToLink> getLibrariesByIdentifier(
+      Iterable<LibraryToLink> inputs) {
+    ImmutableSetMultimap.Builder<String, LibraryToLink> result =
+        new ImmutableSetMultimap.Builder<>();
+    for (LibraryToLink library : inputs) {
+      result.put(libraryIdentifierOf(library.getOriginalLibraryArtifact()), library);
     }
     return result.build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/util/FileType.java b/src/main/java/com/google/devtools/build/lib/util/FileType.java
index b8b4fdc119..b984e98d70 100644
--- a/src/main/java/com/google/devtools/build/lib/util/FileType.java
+++ b/src/main/java/com/google/devtools/build/lib/util/FileType.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.util;
 
+import com.google.common.base.Function;
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
@@ -129,6 +130,14 @@ public abstract class FileType implements Predicate<String> {
     String getFilename();
   }
 
+  public static final Function<HasFilename, String> TO_FILENAME =
+      new Function<HasFilename, String>() {
+        @Override
+        public String apply(HasFilename input) {
+          return input.getFilename();
+        }
+      };
+
   /**
    * Checks whether an Iterable<? extends HasFileType> contains any of the specified file types.
    *