From 33ac07ccfe4825aa078643c40b2bd230b380de48 Mon Sep 17 00:00:00 2001 From: Michael Staib Date: Fri, 22 Jul 2016 20:34:18 +0000 Subject: 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 --- .../build/lib/rules/cpp/CcLibraryHelper.java | 54 +++++++++++----------- .../build/lib/rules/cpp/CcLinkingOutputs.java | 29 +++++++----- .../google/devtools/build/lib/util/FileType.java | 9 ++++ 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 allLibraries = - Iterables.concat(staticLibraries, picStaticLibraries, dynamicLibraries); - for (LibraryToLink precompiledLibrary : allLibraries) { - List matchingLibs = - originalLinkingOutputs.getLibrariesWithSameIdentifierAs(precompiledLibrary); - if (!matchingLibs.isEmpty()) { - Iterable matchingLibArtifactNames = - Iterables.transform( - matchingLibs, - new Function() { - @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 precompiledLibraryMap = + CcLinkingOutputs.getLibrariesByIdentifier( + Iterables.concat(staticLibraries, picStaticLibraries, dynamicLibraries)); + ImmutableSetMultimap linkedLibraryMap = + originalLinkingOutputs.getLibrariesByIdentifier(); + for (String matchingIdentifier : + Sets.intersection(precompiledLibraryMap.keySet(), linkedLibraryMap.keySet())) { + Iterable matchingInputLibs = + LinkerInputs.toNonSolibArtifacts(precompiledLibraryMap.get(matchingIdentifier)); + Iterable 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 getLibrariesWithSameIdentifierAs(LibraryToLink input) { - Iterable allLibraries = + public ImmutableSetMultimap getLibrariesByIdentifier() { + return getLibrariesByIdentifier( Iterables.concat( - staticLibraries, picStaticLibraries, dynamicLibraries, executionDynamicLibraries); - ImmutableList.Builder 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 getLibrariesByIdentifier( + Iterable inputs) { + ImmutableSetMultimap.Builder 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 getFilename(); } + public static final Function TO_FILENAME = + new Function() { + @Override + public String apply(HasFilename input) { + return input.getFilename(); + } + }; + /** * Checks whether an Iterable contains any of the specified file types. * -- cgit v1.2.3