diff options
author | Nathan Harmata <nharmata@google.com> | 2016-08-25 18:29:43 +0000 |
---|---|---|
committer | John Cater <jcater@google.com> | 2016-08-25 20:21:30 +0000 |
commit | 8ebfb43117a6d6a2597e0b54ebfbddf93922b98d (patch) | |
tree | 60c2ca4b69d0a9e0c9931b80ae5dfa6ba7370176 /src/main/java/com/google | |
parent | a6595116da5fb80554496cd69e4ab74b93c7b1e4 (diff) |
Some optimizations in Type#flatten (used under the covers by AggregatingAttributeMapper#visitLabels):
-Rename Type#flatten to Type#extractLabels.
-Change the return type of Type#extractLabels from Collection to Iterable. This way we don't need to create and concatenate large lists.
-Add an internal-only Type#containsLabels so this way ListType and DictType can have efficient implementations of Type#extractLabels.
Note that AggregatingAttributeMapper#visitLabels is called multiple times on the same in several different places during the lifetime of a non-incremental Blaze invocation (e.g. during Package loading, during transitive target visitation, etc)
--
MOS_MIGRATED_REVID=131311698
Diffstat (limited to 'src/main/java/com/google')
3 files changed, 131 insertions, 38 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java index d89e278ab7..c4c47b4b7a 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java +++ b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java @@ -245,9 +245,9 @@ public abstract class AbstractAttributeMapper implements AttributeMap { return attribute != null && attribute.getType() == type; } - protected static Iterable<Label> extractLabels(Type type, Object value) { + protected static Iterable<Label> extractLabels(Type<?> type, Object value) { return value == null ? ImmutableList.<Label>of() - : Iterables.filter(type.flatten(value), Label.class); + : Iterables.filter(type.extractLabels(value), Label.class); } } diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java index bbef95be91..3a8c69c677 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java +++ b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java @@ -97,8 +97,13 @@ public final class BuildType { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -191,7 +196,12 @@ public final class BuildType { } @Override - public Collection<? extends Object> flatten(Object value) { + protected boolean containsLabels() { + return true; + } + + @Override + public Collection<? extends Object> extractLabels(Object value) { return cast(value).getLabels(); } } @@ -208,7 +218,12 @@ public final class BuildType { } @Override - public Collection<Label> flatten(Object value) { + protected boolean containsLabels() { + return true; + } + + @Override + public Iterable<Label> extractLabels(Object value) { return ImmutableList.of(cast(value)); } @@ -259,8 +274,13 @@ public final class BuildType { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -299,8 +319,13 @@ public final class BuildType { } @Override - public Collection<Object> flatten(Object what) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object what) { + return NO_LABELS; } @Override @@ -326,7 +351,12 @@ public final class BuildType { } @Override - public Collection<Label> flatten(Object value) { + protected boolean containsLabels() { + return true; + } + + @Override + public Collection<Label> extractLabels(Object value) { return ImmutableList.of(cast(value)); } @@ -587,8 +617,13 @@ public final class BuildType { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object value) { + return NO_LABELS; } @Override diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Type.java b/src/main/java/com/google/devtools/build/lib/syntax/Type.java index 49d0b74c3b..a8987e8eca 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/Type.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/Type.java @@ -14,6 +14,7 @@ package com.google.devtools.build.lib.syntax; +import com.google.common.base.Function; import com.google.common.base.Joiner; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; @@ -52,6 +53,14 @@ import javax.annotation.Nullable; */ public abstract class Type<T> { + private final Function<Object, Iterable<? extends Object>> flattenFunction = + new Function<Object, Iterable<? extends Object>>() { + @Override + public Iterable<? extends Object> apply(Object value) { + return extractLabels(value); + } + }; + protected Type() {} /** @@ -126,7 +135,13 @@ public abstract class Type<T> { public abstract T getDefaultValue(); /** - * Flatten the an instance of the type if the type is a composite one. + * Returns whether there exists an {@code x} such that {@code extractLabels(x)} will return a + * non-{@code NO_LABELS} value. + */ + protected abstract boolean containsLabels(); + + /** + * Extracts all the labels from the given instance of the type. * * <p>This is used to support reliable label visitation in * {@link com.google.devtools.build.lib.packages.AbstractAttributeMapper#visitLabels}. To preserve @@ -134,12 +149,12 @@ public abstract class Type<T> { * words, be careful about defining default instances in base types that get auto-inherited by * their children. Keep all definitions as explicit as possible. */ - public abstract Collection<? extends Object> flatten(Object value); + public abstract Iterable<? extends Object> extractLabels(Object value); /** - * {@link #flatten} return value for types that don't contain labels. + * {@link #extractLabels} return value for types that don't contain labels. */ - protected static final Collection<Object> NOT_COMPOSITE_TYPE = ImmutableList.of(); + protected static final ImmutableList<Object> NO_LABELS = ImmutableList.of(); /** * Implementation of concatenation for this type (e.g. "val1 + val2"). Returns null to @@ -265,8 +280,13 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Iterable<? extends Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -292,8 +312,13 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -332,8 +357,13 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Iterable<Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -383,8 +413,13 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - return NOT_COMPOSITE_TYPE; + protected boolean containsLabels() { + return false; + } + + @Override + public Collection<Object> extractLabels(Object value) { + return NO_LABELS; } @Override @@ -429,6 +464,24 @@ public abstract class Type<T> { private final Map<KeyT, ValueT> empty = ImmutableMap.of(); + private final Function< + Map.Entry<KeyT, ValueT>, Iterable<? extends Object>> mapEntryFlattenFunction = + new Function<Map.Entry<KeyT, ValueT>, Iterable<? extends Object>>() { + @Override + public Iterable<? extends Object> apply(Entry<KeyT, ValueT> entry) { + Iterable<? extends Object> flattenedKeys = keyType.extractLabels(entry.getKey()); + Iterable<? extends Object> flattenedValues = valueType.extractLabels(entry.getValue()); + if (keyType.containsLabels() && valueType.containsLabels()) { + return Iterables.concat(flattenedKeys, flattenedValues); + } else if (keyType.containsLabels()) { + return flattenedKeys; + } else if (valueType.containsLabels()) { + return flattenedValues; + } + throw new IllegalStateException(this.toString()); + } + }; + public static <KEY, VALUE> DictType<KEY, VALUE> create( Type<KEY> keyType, Type<VALUE> valueType) { return new DictType<>(keyType, valueType); @@ -482,13 +535,15 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - ImmutableList.Builder<Object> result = ImmutableList.builder(); - for (Map.Entry<KeyT, ValueT> entry : cast(value).entrySet()) { - result.addAll(keyType.flatten(entry.getKey())); - result.addAll(valueType.flatten(entry.getValue())); - } - return result.build(); + protected boolean containsLabels() { + return keyType.containsLabels() || valueType.containsLabels(); + } + + @Override + public Iterable<Object> extractLabels(Object value) { + return containsLabels() + ? Iterables.concat(Iterables.transform(cast(value).entrySet(), mapEntryFlattenFunction)) + : NO_LABELS; } } @@ -524,12 +579,15 @@ public abstract class Type<T> { } @Override - public Collection<Object> flatten(Object value) { - ImmutableList.Builder<Object> labels = ImmutableList.builder(); - for (ElemT entry : cast(value)) { - labels.addAll(elemType.flatten(entry)); - } - return labels.build(); + protected boolean containsLabels() { + return elemType.containsLabels(); + } + + @Override + public Iterable<? extends Object> extractLabels(Object value) { + return containsLabels() + ? Iterables.concat(Iterables.transform(cast(value), elemType.flattenFunction)) + : NO_LABELS; } @Override |