diff options
Diffstat (limited to 'src/main/java/com')
3 files changed, 12 insertions, 420 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AggregatedPatterns.java b/src/main/java/com/google/devtools/build/lib/skyframe/AggregatedPatterns.java deleted file mode 100644 index 4600cd9a4c..0000000000 --- a/src/main/java/com/google/devtools/build/lib/skyframe/AggregatedPatterns.java +++ /dev/null @@ -1,363 +0,0 @@ -// Copyright 2015 Google Inc. 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.skyframe; - -import com.google.common.base.Preconditions; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Lists; -import com.google.devtools.build.lib.cmdline.TargetPattern.Type; -import com.google.devtools.build.lib.pkgcache.FilteringPolicies; -import com.google.devtools.build.lib.pkgcache.FilteringPolicy; -import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey; - -import java.util.Collections; -import java.util.Iterator; -import java.util.List; -import java.util.Map.Entry; -import java.util.NavigableMap; -import java.util.Set; -import java.util.TreeMap; - -/** - * This is used by {@link TargetPatternValue#keys} to help it convert a sequence of target patterns - * into a sequence of {@link TargetPatternKey}s that, when evaluated and combined together, yield - * the targets matched by the target pattern sequence. - * - * <p>Its main strategy for accomplishing this is to sort the target patterns by the directories - * that contain the targets they match, and take advantage of that sorting to efficiently discover - * redundant patterns (e.g. the two patterns "//foo/..." and "//foo/bar/..." don't each need to be - * evaluated if they appear side-by-side in the sequence) and exclusionary patterns (e.g. the two - * patterns "//foo/..." and "-//foo/bar/..." don't each need to be evaluated--instead, while - * evaluating the targets below "foo", the subdirectory "bar" can be skipped). - * - * <p>An {@link AggregatedPatterns} instance expects its {@link #addPattern} method to be called - * for each target pattern in the sequence in a left-to-right order. This is because a pattern of - * type {@code Type.TARGETS_BELOW_DIRECTORY} overrides everything encountered so far in and below - * the directory it specifies, and this class implements that by removing all target patterns - * that were already added in and below that directory. - * - * <p>The class takes a {@link FilteringPolicy} and a ({@link String}) offset in its constructor, as - * the {@link TargetPatternKey}s it constructs from a target pattern sequence include those values. - * - * <p>The creation of {@link TargetPatternKey}s begins when {@link AggregatedPatterns#build} is - * called. It processes the sorted target patterns recursively, breaking the problem of - * converting the sequence of target patterns to a sequence of {@link TargetPatternKey}s into a - * set of sub-problems, where each sub-problem consists of converting the patterns beneath each - * {@code Type.TARGETS_BELOW_DIRECTORY} pattern into a sequence of {@link TargetPatternKey}s. - * This gets off the ground because one can think of every target pattern sequence as implicitly - * starting with the "-//..." pattern. - */ -class AggregatedPatterns { - - // Keys in this ordered map are strings representing directories. These strings are either "" (to - // indicate the depot root) or end with a trailing '/'. - // - // They end with '/' to ensure that an iteration through the map corresponds to a depth-first - // traversal through the directory tree, and that an entry for a directory directly precedes the - // entries for its subdirectories. - // - // For example, consider the three directories "a/", "a/b/", and "a.1/". When sorted into the - // map, their entries will be visited in this order: - // - // "a.1/" - // "a/" - // "a/b/" - // - // If the keys were directories in normal form (i.e. lacking a trailing '/') they would be - // visited in this order: - // - // "a" - // "a.1" - // "a/b" - // - // (Note how "a" and "a/b" are sadly separated in this latter example.) - // - // If {@code l = orderedPatternsByDirectory.get(d)}, then {@code l} is the list of all target - // patterns {@code p} such that {@code maybeAddTrailingSlash(p.getDirectory()).equals(d)}, in - // order of insertion via {@link AggregatedPatterns#addPattern} (which is assumed to correspond - // to logic order in the target pattern sequence), which were not inserted before any - // {@code Type.TARGETS_BELOW_DIRECTORY} patterns with directories equal to or above {@code d} - // (because later patterns take precedence over earlier patterns). - private final NavigableMap<String, List<SignedPattern>> orderedPatternsByDirectory = - new TreeMap<>(); - private final FilteringPolicy policy; - private final String offset; - - AggregatedPatterns(FilteringPolicy policy, String offset) { - this.policy = policy; - this.offset = offset; - } - - /** Must be called for each target pattern in the sequence in order from left to right. */ - AggregatedPatterns addPattern(SignedPattern signedPattern) { - Preconditions.checkNotNull(signedPattern); - String directoryWithoutTrailingSlash = signedPattern.getPattern().getDirectory(); - - // If the new pattern is a TargetsBelowDirectory, then it overrides everything in and below its - // directory, so we can remove those keys. - if (isTargetsBelowDirectory(signedPattern)) { - // The set returned by SortedMap.keySet supports element removal via the clear operation. - getDirectoriesBelow(directoryWithoutTrailingSlash).clear(); - } - - // If the pattern's directory is non-empty, we add a trailing "/" to the directory key. See the - // comment on orderedPatternsByDirectory for the reason why. - String directoryKey = getDirectoryKey(directoryWithoutTrailingSlash); - List<SignedPattern> patternsMaybe = orderedPatternsByDirectory.get(directoryKey); - if (patternsMaybe == null) { - patternsMaybe = Lists.newArrayList(); - orderedPatternsByDirectory.put(directoryKey, patternsMaybe); - } - patternsMaybe.add(signedPattern); - return this; - } - - Iterable<TargetPatternKey> build() { - return getKeysAndExcludedDirsUnder(orderedPatternsByDirectory, false).getKeys(); - } - - private enum DirectoryInclusion { - INCLUDED, - EXCLUDED, - MIXED; - - static DirectoryInclusion from(boolean isIncluded) { - return isIncluded ? INCLUDED : EXCLUDED; - } - } - - private static class KeysAndExcludedDirectories { - private final ImmutableList<TargetPatternKey> keys; - private final ImmutableSet<String> excludedDirectories; - - private KeysAndExcludedDirectories(ImmutableList<TargetPatternKey> keys, - ImmutableSet<String> excludedDirectories) { - this.keys = Preconditions.checkNotNull(keys); - this.excludedDirectories = Preconditions.checkNotNull(excludedDirectories); - } - - public ImmutableList<TargetPatternKey> getKeys() { - return keys; - } - - public ImmutableSet<String> getExcludedDirectories() { - return excludedDirectories; - } - } - - private static class SubdirectoriesAndRemainder { - private final NavigableMap<String, List<SignedPattern>> subdirectoriesMap; - private final Iterator<Entry<String, List<SignedPattern>>> remainder; - - public SubdirectoriesAndRemainder( - NavigableMap<String, List<SignedPattern>> subdirectoriesMap, - Iterator<Entry<String, List<SignedPattern>>> remainder) { - this.subdirectoriesMap = Preconditions.checkNotNull(subdirectoriesMap); - this.remainder = Preconditions.checkNotNull(remainder); - } - - public NavigableMap<String, List<SignedPattern>> getSubdirectoriesMap() { - return subdirectoriesMap; - } - - public Iterator<Entry<String, List<SignedPattern>>> getRemainder() { - return remainder; - } - } - - /** - * Calculates a list of {@link TargetPatternKey}s and a set of excluded directories - * (represented by {@link String}s in normal form, relative to the workspace root) - * corresponding to the {@link SignedPattern}s included in {@code directories}. - * - * <p>The function tries to eliminate redundant {@link TargetPatternKey}s from the returned value. - * To help it discover these redundancies it must be told whether targets in - * {@code directories} are considered included by default, via {@code includedByDefault}. For - * example, if all the directories in {@code directories} are subdirectories below "some/path", - * and we had already seen a target pattern corresponding to "//some/path/...", then {@code - * includedByDefault} would be true. - * - * @param directories an ordered map of directories to ordered lists of target patterns, - * sharing the same requirements as {@code orderedPatternsByDirectory} - * @param includedByDefault whether targets in {@code directories} should be considered - * included by default - */ - private KeysAndExcludedDirectories getKeysAndExcludedDirsUnder( - NavigableMap<String, List<SignedPattern>> directories, boolean includedByDefault) { - ImmutableList.Builder<TargetPatternKey> keysBuilder = ImmutableList.builder(); - ImmutableSet.Builder<String> excludedDirsBuilder = ImmutableSet.builder(); - - // The following {@code iterator} variable is used to iterate through the directories in - // {@code orderedPatternsByDirectory}. When it encounters a pattern of type - // {@code Type.TARGETS_BELOW_DIRECTORY} in a directory, it recursively calls itself to evaluate - // the interval of entries corresponding to the subdirectories beneath that directory. - // Afterwards, it skips past that already-processed interval by *assigning to* - // {@code iterator}, to make it point at the first element after the interval (or to an "empty" - // iterator if there is no such element). That assignment is why this while loop isn't a - // standard "for(T e : iterable)" loop. - Iterator<Entry<String, List<SignedPattern>>> iterator = directories.entrySet().iterator(); - while (iterator.hasNext()) { - Entry<String, List<SignedPattern>> directoryEntry = iterator.next(); - // The following {@code directoryInclusion} variable represents whether targets in this - // directory are included by default. It's initialized to INCLUDED or EXCLUDED based on the - // value of {@code includedByDefault}. It will be set to INCLUDED if we encounter a positive - // TargetsBelowDirectory (TBD) pattern in the directory, EXCLUDED if we encounter a - // negative TBD pattern in the directory, and will be set to MIXED if we encounter a - // non-TBD pattern to be subtracted while in the INCLUDED state or if we encounter a - // non-TBD pattern to be added while in the EXCLUDED state. (Note that only the first - // pattern in the directory can be a TBD pattern because adding a TBD pattern removes all - // existing patterns in and below its directory.) - // - // It's used to discover redundant patterns, i.e. patterns that can be skipped because a - // prior pattern already includes it (and it's positive) or because a prior pattern - // already excluded it (and it's negative). - // - // Currently, the only kind of prior patterns that this code is sensitive to are those of - // type TBD. This code doesn't keep track of targets in a more fine-grained way for - // simplicity. (See the final comment in the - // TargetPatternValueTest#testSubtractingThenAddingInIncludedDirectory unit test for more - // information.) Still, this approach offers the benefit of skipping positive targets under - // a positive TBD pattern and negative targets under a negative TBD pattern. - DirectoryInclusion directoryInclusion = DirectoryInclusion.from(includedByDefault); - - Iterable<SignedPattern> directoryPatterns = directoryEntry.getValue(); - for (SignedPattern signedPattern : directoryPatterns) { - if (isTargetsBelowDirectory(signedPattern)) { - if (!signedPattern.isPositive()) { - // Add its directory to the excluded directories. - excludedDirsBuilder.add(signedPattern.getPattern().getDirectory()); - } - - // If it's a TBD pattern with sign opposite from the current default inclusion policy, - // then it isn't redundant, and will contribute to the returned value as either a - // TargetPatternKey (if the pattern's sign is positive) or as an excluded directory (if - // the pattern's sign is negative). - if (signedPattern.isPositive() != includedByDefault) { - // 1) Remember the new effective inclusion policy for this directory. - directoryInclusion = DirectoryInclusion.from(signedPattern.isPositive()); - - // 2) Collect any additional keys and excluded directories from subdirectories below - // this one. - SubdirectoriesAndRemainder subdirectoriesAndRemainder = - getSubdirectoriesAndRemainder(directories, directoryEntry.getKey()); - NavigableMap<String, List<SignedPattern>> subMapForSubdirectories = - subdirectoriesAndRemainder.getSubdirectoriesMap(); - KeysAndExcludedDirectories keysAndExcludedDirs = - getKeysAndExcludedDirsUnder(subMapForSubdirectories, - /*includedByDefault=*/signedPattern.isPositive()); - - if (signedPattern.isPositive()) { - // 2.5) If this TBD pattern is positive, specify the excluded subdirectories in the - // TargetPatternKey for this pattern and add the key to the keysBuilder. - keysBuilder.add(createTargetPatternKey(signedPattern, policy, offset, - keysAndExcludedDirs.getExcludedDirectories())); - } - - // 3) Include the keys collected from subdirectories. - // Note that this statement means that the number of references this algorithm copies - // is potentially quadratic. An adversary could engineer a target pattern sequence - // that degrades performance. - keysBuilder.addAll(keysAndExcludedDirs.getKeys()); - - // 4) Skip past the keys from subdirectories below this one. - iterator = subdirectoriesAndRemainder.getRemainder(); - } - // Else, it's a TBD pattern with sign equal to the current default inclusion policy. - // Skip it because it's redundant. - } else { // It's not a TBD pattern. - boolean subtractingFromIncludedDirectory = - directoryInclusion.equals(DirectoryInclusion.INCLUDED) && !signedPattern.isPositive(); - boolean addingToExcludedDirectory = - directoryInclusion.equals(DirectoryInclusion.EXCLUDED) && signedPattern.isPositive(); - boolean alreadyMixed = directoryInclusion.equals(DirectoryInclusion.MIXED); - if (subtractingFromIncludedDirectory || addingToExcludedDirectory || alreadyMixed) { - // If we're subtracting from an included directory, or adding to an excluded - // directory, or if the directory is already mixed, add the pattern to the keysBuilder. - keysBuilder.add(createTargetPatternKey(signedPattern, policy, offset)); - // Also remember that this directory is now both including and excluding some targets, - // so all subsequent patterns must be evaluated. - directoryInclusion = DirectoryInclusion.MIXED; - } - } - } - } - return new KeysAndExcludedDirectories(keysBuilder.build(), excludedDirsBuilder.build()); - } - - private static String getDirectoryKey(String directoryWithoutTrailingSlash) { - return directoryWithoutTrailingSlash.length() == 0 ? "" : directoryWithoutTrailingSlash + "/"; - } - - private static TargetPatternKey createTargetPatternKey(SignedPattern pattern, - FilteringPolicy policy, String offset) { - return createTargetPatternKey(pattern, policy, offset, ImmutableSet.<String>of()); - } - - private static TargetPatternKey createTargetPatternKey(SignedPattern signedPattern, - FilteringPolicy policy, String offset, ImmutableSet<String> excludedDirectories) { - if (signedPattern.isPositive()) { - return new TargetPatternKey(signedPattern.getPattern(), policy, /*isNegative=*/false, offset, - excludedDirectories); - } else { - return new TargetPatternKey(signedPattern.getPattern(), FilteringPolicies.NO_FILTER, - /*isNegative=*/true, offset, excludedDirectories); - } - } - - private static SubdirectoriesAndRemainder getSubdirectoriesAndRemainder( - NavigableMap<String, List<SignedPattern>> directories, String directoryKey) { - NavigableMap<String, List<SignedPattern>> subdirectories; - Iterator<Entry<String, List<SignedPattern>>> remainder; - if (directoryKey.length() == 0) { - subdirectories = directories.tailMap(directoryKey, - /*inclusive, referring to the directoryKey endpoint=*/false); - remainder = Collections.emptyIterator(); - } else { - String afterKey = getKeyAfterAllPathsBelowDirectoryWithoutTrailingSlash( - directoryKey.substring(0, directoryKey.length() - 1)); - subdirectories = directories.subMap(directoryKey, - /*inclusive, referring to the directoryKey endpoint=*/false, afterKey, - /*inclusive, referring to the afterKey endpoint=*/false); - remainder = directories.tailMap(afterKey).entrySet().iterator(); - } - return new SubdirectoriesAndRemainder(subdirectories, remainder); - } - - private static String getKeyAfterAllPathsBelowDirectoryWithoutTrailingSlash( - String directoryWithoutTrailingSlash) { - // We calculate the least character greater than '/' (which happens to be '0'). We use this - // to collect all paths in subdirectories of the current one, using NavigableMap's subMap - // method, which takes an interval. - return directoryWithoutTrailingSlash + ((char) ('/' + 1)); - } - - private Set<String> getDirectoriesBelow(String directoryWithoutTrailingSlash) { - // If the empty string is passed in, collect all the directories. - if (directoryWithoutTrailingSlash.length() == 0) { - return orderedPatternsByDirectory.keySet(); - } - // Otherwise, collect the keyset belonging to the passed-in directory and its subdirectories. - String afterKey = getKeyAfterAllPathsBelowDirectoryWithoutTrailingSlash( - directoryWithoutTrailingSlash); - // Note that the subMap method defaults to interpreting the first, lesser, argument inclusively - // and the second, greater, argument exclusively. - return orderedPatternsByDirectory.subMap(getDirectoryKey(directoryWithoutTrailingSlash), - afterKey).keySet(); - } - - private static boolean isTargetsBelowDirectory(SignedPattern signedPattern) { - return signedPattern.getPattern().getType().equals(Type.TARGETS_BELOW_DIRECTORY); - } -} diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SignedPattern.java b/src/main/java/com/google/devtools/build/lib/skyframe/SignedPattern.java deleted file mode 100644 index 034f35e5cc..0000000000 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SignedPattern.java +++ /dev/null @@ -1,40 +0,0 @@ -// Copyright 2015 Google Inc. 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.skyframe; - -import com.google.devtools.build.lib.cmdline.TargetPattern; - -final class SignedPattern { - - private final boolean positive; - private final TargetPattern pattern; - - SignedPattern(boolean positive, TargetPattern pattern) { - this.positive = positive; - this.pattern = pattern; - } - - boolean isPositive() { - return positive; - } - - TargetPattern getPattern() { - return pattern; - } - - @Override - public String toString() { - return (positive ? "" : "-") + pattern.getOriginalPattern(); - } -} diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java index 1f1b369396..1f665e0152 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java @@ -23,6 +23,7 @@ import com.google.devtools.build.lib.cmdline.TargetParsingException; import com.google.devtools.build.lib.cmdline.TargetPattern; import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; +import com.google.devtools.build.lib.pkgcache.FilteringPolicies; import com.google.devtools.build.lib.pkgcache.FilteringPolicy; import com.google.devtools.build.lib.syntax.Label; import com.google.devtools.build.lib.syntax.Label.SyntaxException; @@ -111,14 +112,9 @@ public final class TargetPatternValue implements SkyValue { /** * Returns an iterable of {@link TargetPatternSkyKeyOrException}, with {@link TargetPatternKey} - * arguments. If a provided pattern fails to parse, an element in the returned iterable will - * throw when its {@link TargetPatternSkyKeyOrException#getSkyKey} method is called and will - * return the failing pattern when its {@link - * TargetPatternSkyKeyOrException#getOriginalPattern} method is called. - * - * <p>There may be fewer returned elements than patterns provided as input. This function may - * combine patterns to return an iterable of SkyKeys that is equivalent but more efficient to - * evaluate. + * arguments, in the same order as the list of patterns provided as input. If a provided pattern + * fails to parse, the element in the returned iterable corresponding to it will throw when its + * {@link TargetPatternSkyKeyOrException#getSkyKey} method is called. * * @param patterns The list of patterns, eg "-foo/biz...". If a pattern's first character is "-", * it is treated as a negative pattern. @@ -129,24 +125,23 @@ public final class TargetPatternValue implements SkyValue { public static Iterable<TargetPatternSkyKeyOrException> keys(List<String> patterns, FilteringPolicy policy, String offset) { TargetPattern.Parser parser = new TargetPattern.Parser(offset); - AggregatedPatterns aggregatedPatterns = new AggregatedPatterns(policy, offset); ImmutableList.Builder<TargetPatternSkyKeyOrException> builder = ImmutableList.builder(); for (String pattern : patterns) { boolean positive = !pattern.startsWith("-"); String absoluteValueOfPattern = positive ? pattern : pattern.substring(1); + TargetPattern targetPattern; try { - aggregatedPatterns.addPattern( - new SignedPattern(positive, parser.parse(absoluteValueOfPattern))); + targetPattern = parser.parse(absoluteValueOfPattern); } catch (TargetParsingException e) { builder.add(new TargetPatternSkyKeyException(e, absoluteValueOfPattern)); + continue; } + TargetPatternKey targetPatternKey = new TargetPatternKey(targetPattern, + positive ? policy : FilteringPolicies.NO_FILTER, /*isNegative=*/!positive, offset, + ImmutableSet.<String>of()); + SkyKey skyKey = new SkyKey(SkyFunctions.TARGET_PATTERN, targetPatternKey); + builder.add(new TargetPatternSkyKeyValue(skyKey)); } - - for (TargetPatternKey patternKey : aggregatedPatterns.build()) { - builder.add( - new TargetPatternSkyKeyValue(new SkyKey(SkyFunctions.TARGET_PATTERN, patternKey))); - } - return builder.build(); } |