diff options
author | Benjamin Peterson <bp@benjamin.pe> | 2017-11-27 03:14:43 -0800 |
---|---|---|
committer | Copybara-Service <copybara-piper@google.com> | 2017-11-27 03:16:07 -0800 |
commit | 8610d97d2b68cfbcf6b7de4441665a64f378eb9c (patch) | |
tree | 15a4967abd18a1963fa147fcbd462ca74155085d | |
parent | 9fea5b89a5cf8744dbe32aff279a9e2c2613c9d8 (diff) |
Shape sharing for Skylark providers.
Add CompactSkylarkInfo, which stores its values as an array instead of
a map. The space savings will probably not be dramatic because
providers usually have a limited amount of keys. But, there are a lot
of them!
Change-Id: Idd452a5e3982f773b1c5202c73f3d7031ec022c6
PiperOrigin-RevId: 176995376
7 files changed, 325 insertions, 53 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ActionsProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/ActionsProvider.java index ac7ade351c..429f419b2c 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/ActionsProvider.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/ActionsProvider.java @@ -46,6 +46,6 @@ public final class ActionsProvider { } } ImmutableMap<String, Object> fields = ImmutableMap.<String, Object>of("by_file", map); - return new SkylarkInfo(SKYLARK_CONSTRUCTOR, fields, Location.BUILTIN); + return SkylarkInfo.fromMap(SKYLARK_CONSTRUCTOR, fields, Location.BUILTIN); } } diff --git a/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java b/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java index 61bab352de..93bbcfe025 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java +++ b/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java @@ -79,15 +79,15 @@ public abstract class NativeProvider<VALUE extends Info> extends Provider { protected Info createInstanceFromSkylark(Object[] args, Location loc) { @SuppressWarnings("unchecked") Map<String, Object> kwargs = (Map<String, Object>) args[0]; - return new SkylarkInfo(this, kwargs, loc); + return SkylarkInfo.fromMap(this, kwargs, loc); } public Info create(Map<String, Object> values, String message) { - return new SkylarkInfo(this, values, message); + return new SkylarkInfo.MapBackedSkylarkInfo(this, values, message); } public Info create(Location loc) { - return new SkylarkInfo(this, ImmutableMap.of(), loc); + return SkylarkInfo.fromMap(this, ImmutableMap.of(), loc); } } diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkInfo.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkInfo.java index 755a5df5f1..c20d574f25 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkInfo.java +++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkInfo.java @@ -14,8 +14,10 @@ package com.google.devtools.build.lib.packages; import com.google.common.base.Joiner; +import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableCollection; import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSet; import com.google.common.collect.Sets; import com.google.common.collect.Sets.SetView; import com.google.devtools.build.lib.events.Location; @@ -23,40 +25,23 @@ import com.google.devtools.build.lib.packages.NativeProvider.StructConstructor; import com.google.devtools.build.lib.syntax.Concatable; import com.google.devtools.build.lib.syntax.EvalException; import com.google.devtools.build.lib.syntax.EvalUtils; +import java.util.Arrays; import java.util.Map; /** Implementation of {@link Info} created from Skylark. */ -public final class SkylarkInfo extends Info implements Concatable { - protected final ImmutableMap<String, Object> values; +public abstract class SkylarkInfo extends Info implements Concatable { - public SkylarkInfo(Provider provider, Map<String, Object> kwargs, Location loc) { + public SkylarkInfo(Provider provider, Location loc) { super(provider, loc); - this.values = copyValues(kwargs); } public SkylarkInfo(StructConstructor provider, Map<String, Object> values, String message) { super(provider, values, message); - this.values = copyValues(values); } @Override public Concatter getConcatter() { - return StructConcatter.INSTANCE; - } - - @Override - public Object getValue(String name) { - return values.get(name); - } - - @Override - public boolean hasKey(String name) { - return values.containsKey(name); - } - - @Override - public ImmutableCollection<String> getKeys() { - return values.keySet(); + return SkylarkInfoConcatter.INSTANCE; } @Override @@ -65,41 +50,161 @@ public final class SkylarkInfo extends Info implements Concatable { if (!getProvider().isExported()) { return false; } - for (Object item : values.values()) { - if (!EvalUtils.isImmutable(item)) { + for (Object item : getValues()) { + if (item != null && !EvalUtils.isImmutable(item)) { return false; } } return true; } - private static class StructConcatter implements Concatter { - private static final StructConcatter INSTANCE = new StructConcatter(); + /** Return all the values stored in the object. */ + protected abstract Iterable<Object> getValues(); + + /** + * {@link SkylarkInfo} implementation that stores its values in a map. This is mainly used for the + * Skylark {@code struct()} constructor. + */ + static final class MapBackedSkylarkInfo extends SkylarkInfo { + protected final ImmutableMap<String, Object> values; + + public MapBackedSkylarkInfo(Provider provider, Map<String, Object> kwargs, Location loc) { + super(provider, loc); + this.values = copyValues(kwargs); + } + + public MapBackedSkylarkInfo( + StructConstructor provider, Map<String, Object> values, String message) { + super(provider, values, message); + this.values = copyValues(values); + } + + @Override + public Object getValue(String name) { + return values.get(name); + } + + @Override + public boolean hasKey(String name) { + return values.containsKey(name); + } + + @Override + public ImmutableCollection<String> getKeys() { + return values.keySet(); + } + + @Override + protected Iterable<Object> getValues() { + return values.values(); + } + } + + /** Create a {@link SkylarkInfo} instance from a provider and a map. */ + public static SkylarkInfo fromMap(Provider provider, Map<String, Object> values, Location loc) { + return new MapBackedSkylarkInfo(provider, values, loc); + } + + /** Implementation of {@link SkylarkInfo} that stores its values in array to save space. */ + static final class CompactSkylarkInfo extends SkylarkInfo implements Concatable { + private final ImmutableMap<String, Integer> layout; + private final Object[] values; + + public CompactSkylarkInfo( + Provider provider, ImmutableMap<String, Integer> layout, Object[] values, Location loc) { + super(provider, loc); + Preconditions.checkState(layout.size() == values.length); + this.layout = layout; + this.values = values; + } + + @Override + public Concatter getConcatter() { + return SkylarkInfoConcatter.INSTANCE; + } + + @Override + public Object getValue(String name) { + Integer index = layout.get(name); + if (index == null) { + return null; + } + return values[index]; + } - private StructConcatter() {} + @Override + public boolean hasKey(String name) { + Integer index = layout.get(name); + return index != null && values[index] != null; + } @Override - public SkylarkInfo concat(Concatable left, Concatable right, Location loc) - throws EvalException { + public ImmutableCollection<String> getKeys() { + ImmutableSet.Builder<String> result = new ImmutableSet.Builder(); + for (Map.Entry<String, Integer> entry : layout.entrySet()) { + if (values[entry.getValue()] != null) { + result.add(entry.getKey()); + } + } + return result.build(); + } + + @Override + protected Iterable<Object> getValues() { + return Arrays.asList(values); + } + } + + /** Concatter for concrete {@link SkylarkInfo} subclasses. */ + private static final class SkylarkInfoConcatter implements Concatable.Concatter { + private static final SkylarkInfoConcatter INSTANCE = new SkylarkInfoConcatter(); + + private SkylarkInfoConcatter() {} + + @Override + public Concatable concat(Concatable left, Concatable right, Location loc) throws EvalException { SkylarkInfo lval = (SkylarkInfo) left; SkylarkInfo rval = (SkylarkInfo) right; - if (!lval.getProvider().equals(rval.getProvider())) { + Provider provider = lval.getProvider(); + if (!provider.equals(rval.getProvider())) { throw new EvalException( loc, String.format( "Cannot concat %s with %s", - lval.getProvider().getPrintableName(), rval.getProvider().getPrintableName())); + provider.getPrintableName(), rval.getProvider().getPrintableName())); } - SetView<String> commonFields = Sets.intersection(lval.values.keySet(), rval.values.keySet()); + SetView<String> commonFields = + Sets.intersection( + ImmutableSet.copyOf(lval.getKeys()), ImmutableSet.copyOf(rval.getKeys())); if (!commonFields.isEmpty()) { throw new EvalException( loc, "Cannot concat structs with common field(s): " + Joiner.on(",").join(commonFields)); } - return new SkylarkInfo( - lval.getProvider(), - ImmutableMap.<String, Object>builder().putAll(lval.values).putAll(rval.values).build(), - loc); + // Keep homogeneous compact concatenations compact. + if (lval instanceof CompactSkylarkInfo + && rval instanceof CompactSkylarkInfo + && ((CompactSkylarkInfo) lval).layout == ((CompactSkylarkInfo) rval).layout) { + CompactSkylarkInfo compactLeft = (CompactSkylarkInfo) lval; + CompactSkylarkInfo compactRight = (CompactSkylarkInfo) rval; + int nvals = compactLeft.layout.size(); + Preconditions.checkState(nvals == compactRight.layout.size()); + Object[] newValues = new Object[nvals]; + for (int i = 0; i < nvals; i++) { + newValues[i] = + (compactLeft.values[i] != null) ? compactLeft.values[i] : compactRight.values[i]; + } + return new CompactSkylarkInfo( + compactLeft.getProvider(), compactLeft.layout, newValues, loc); + } + ImmutableMap.Builder<String, Object> newValues = ImmutableMap.builder(); + for (String key : lval.getKeys()) { + newValues.put(key, lval.getValue(key)); + } + for (String key : rval.getKeys()) { + newValues.put(key, rval.getValue(key)); + } + return new MapBackedSkylarkInfo(provider, newValues.build(), loc); } } } diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkProvider.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkProvider.java index 0cec941a08..cdbf73edd1 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkProvider.java +++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkProvider.java @@ -38,6 +38,14 @@ public class SkylarkProvider extends Provider implements SkylarkExportable { private static final FunctionSignature.WithValues<Object, SkylarkType> SIGNATURE = FunctionSignature.WithValues.create(FunctionSignature.KWARGS); + /** + * A map from provider fields to a continuous range of integers. This allows provider instances to + * store their values in an array rather than a map. {@code layout} will be null if the provider + * fields aren't known up front. + */ + @Nullable + private final ImmutableMap<String, Integer> layout; + @Nullable private SkylarkKey key; @Nullable private String errorMessageFormatForInstances; @@ -58,6 +66,16 @@ public class SkylarkProvider extends Provider implements SkylarkExportable { String name, FunctionSignature.WithValues<Object, SkylarkType> signature, Location location) { super(name, signature, location); + if (signature.getSignature().getShape().hasKwArg()) { + layout = null; + } else { + ImmutableMap.Builder<String, Integer> layoutBuilder = ImmutableMap.builder(); + int i = 0; + for (String field : signature.getSignature().getNames()) { + layoutBuilder.put(field, i++); + } + layout = layoutBuilder.build(); + } this.errorMessageFormatForInstances = DEFAULT_ERROR_MESSAFE; } @@ -74,21 +92,13 @@ public class SkylarkProvider extends Provider implements SkylarkExportable { @Override protected Info createInstanceFromSkylark(Object[] args, Location loc) throws EvalException { - if (signature.getSignature().getShape().hasKwArg()) { + if (layout == null) { @SuppressWarnings("unchecked") Map<String, Object> kwargs = (Map<String, Object>) args[0]; - return new SkylarkInfo(this, kwargs, loc); + return SkylarkInfo.fromMap(this, kwargs, loc); } else { - // todo(dslomov): implement shape sharing. - ImmutableList<String> names = signature.getSignature().getNames(); - Preconditions.checkState(names.size() == args.length); - ImmutableMap.Builder<String, Object> fields = ImmutableMap.builder(); - for (int i = 0; i < args.length; i++) { - if (args[i] != null) { - fields.put(names.get(i), args[i]); - } - } - return new SkylarkInfo(this, fields.build(), loc); + // Note: This depends on the layout map using the same ordering as args. + return new SkylarkInfo.CompactSkylarkInfo(this, layout, args, loc); } } diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java index f0cb1644c2..fa061530cf 100644 --- a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java +++ b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java @@ -234,7 +234,7 @@ public enum ApplePlatform implements SkylarkValue { for (ApplePlatform type : values()) { fields.put(type.skylarkKey, type); } - return new SkylarkInfo(constructor, fields, Location.BUILTIN); + return SkylarkInfo.fromMap(constructor, fields, Location.BUILTIN); } @Override @@ -308,7 +308,7 @@ public enum ApplePlatform implements SkylarkValue { for (PlatformType type : values()) { fields.put(type.skylarkKey, type); } - return new SkylarkInfo(constructor, fields, Location.BUILTIN); + return SkylarkInfo.fromMap(constructor, fields, Location.BUILTIN); } @Override diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkInfoTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkInfoTest.java new file mode 100644 index 0000000000..a0d546f4fb --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkInfoTest.java @@ -0,0 +1,124 @@ +// Copyright 2017 The Bazel Authors. 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.packages; + +import static com.google.common.truth.Truth.assertThat; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableMap; +import com.google.common.testing.EqualsTester; +import com.google.devtools.build.lib.cmdline.Label; +import com.google.devtools.build.lib.events.Location; +import com.google.devtools.build.lib.packages.SkylarkInfo.CompactSkylarkInfo; +import com.google.devtools.build.lib.packages.SkylarkInfo.MapBackedSkylarkInfo; +import com.google.devtools.build.lib.syntax.Concatable; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Test class for {@link SkylarkInfo} and its subclasses. */ +@RunWith(JUnit4.class) +public class SkylarkInfoTest { + + @Test + public void sameProviderDifferentLayoutConcatenation() throws Exception { + SkylarkProvider provider = + new SkylarkProvider("provider", ImmutableList.of("f1", "f2"), Location.BUILTIN); + ImmutableMap<String, Integer> layout1 = ImmutableMap.of("f1", 0, "f2", 1); + ImmutableMap<String, Integer> layout2 = ImmutableMap.of("f1", 1, "f2", 0); + CompactSkylarkInfo info1 = + new CompactSkylarkInfo(provider, layout1, new Object[] {5, null}, Location.BUILTIN); + CompactSkylarkInfo info2 = + new CompactSkylarkInfo(provider, layout2, new Object[] {4, null}, Location.BUILTIN); + SkylarkInfo result = (SkylarkInfo) info1.getConcatter().concat(info1, info2, Location.BUILTIN); + assertThat(result).isInstanceOf(MapBackedSkylarkInfo.class); + assertThat(result.getValue("f1")).isEqualTo(5); + assertThat(result.getValue("f2")).isEqualTo(4); + } + + @Test + public void immutabilityPredicate() throws Exception { + SkylarkProvider provider = + new SkylarkProvider("provider", ImmutableList.of("f1", "f2"), Location.BUILTIN); + ImmutableMap<String, Integer> layout = ImmutableMap.of("f1", 0, "f2", 1); + SkylarkInfo compactInfo = + new CompactSkylarkInfo(provider, layout, new Object[] {5, null}, Location.BUILTIN); + assertThat(compactInfo.isImmutable()).isFalse(); + SkylarkInfo mapInfo = + new MapBackedSkylarkInfo(provider, ImmutableMap.of("f1", 5), Location.BUILTIN); + assertThat(mapInfo.isImmutable()).isFalse(); + provider.export(Label.create("package", "target"), "provider"); + assertThat(compactInfo.isImmutable()).isTrue(); + assertThat(mapInfo.isImmutable()).isTrue(); + compactInfo = + new CompactSkylarkInfo(provider, layout, new Object[] {5, new Object()}, Location.BUILTIN); + assertThat(compactInfo.isImmutable()).isFalse(); + mapInfo = + new MapBackedSkylarkInfo( + provider, ImmutableMap.of("f1", 5, "f2", new Object()), Location.BUILTIN); + assertThat(mapInfo.isImmutable()).isFalse(); + } + + @Test + public void equality() throws Exception { + Provider provider1 = + new SkylarkProvider("provider1", ImmutableList.of("f1", "f2"), Location.BUILTIN); + Provider provider2 = + new SkylarkProvider("provider2", ImmutableList.of("f1", "f2"), Location.BUILTIN); + ImmutableMap<String, Integer> layout = ImmutableMap.of("f1", 0, "f2", 1); + new EqualsTester() + .addEqualityGroup( + new CompactSkylarkInfo(provider1, layout, new Object[] {4, null}, Location.BUILTIN), + new MapBackedSkylarkInfo(provider1, ImmutableMap.of("f1", 4), Location.BUILTIN)) + .addEqualityGroup( + new CompactSkylarkInfo(provider2, layout, new Object[] {4, null}, Location.BUILTIN), + new MapBackedSkylarkInfo(provider2, ImmutableMap.of("f1", 4), Location.BUILTIN)) + .addEqualityGroup( + new CompactSkylarkInfo(provider1, layout, new Object[] {4, 5}, Location.BUILTIN), + new MapBackedSkylarkInfo( + provider1, ImmutableMap.of("f1", 4, "f2", 5), Location.BUILTIN)) + .testEquals(); + } + + @Test + public void heterogeneousConcatenation() throws Exception { + Provider provider = + new SkylarkProvider("provider", ImmutableList.of("f1", "f2"), Location.BUILTIN); + ImmutableMap<String, Integer> layout = ImmutableMap.of("f1", 0, "f2", 1); + SkylarkInfo p1 = new MapBackedSkylarkInfo(provider, ImmutableMap.of("f1", 4), Location.BUILTIN); + CompactSkylarkInfo p2 = + new CompactSkylarkInfo(provider, layout, new Object[] {null, 5}, Location.BUILTIN); + Concatable result = p1.getConcatter().concat(p1, p2, Location.BUILTIN); + assertThat(result).isInstanceOf(MapBackedSkylarkInfo.class); + assertThat(((SkylarkInfo) result).getKeys()).containsExactly("f1", "f2"); + assertThat(((SkylarkInfo) result).getValue("f1")).isEqualTo(4); + assertThat(((SkylarkInfo) result).getValue("f2")).isEqualTo(5); + } + + @Test + public void compactConcatenationReturnsCompact() throws Exception { + Provider provider = + new SkylarkProvider("provider", ImmutableList.of("f1", "f2"), Location.BUILTIN); + ImmutableMap<String, Integer> layout = ImmutableMap.of("f1", 0, "f2", 1); + CompactSkylarkInfo p1 = + new CompactSkylarkInfo(provider, layout, new Object[] {4, null}, Location.BUILTIN); + CompactSkylarkInfo p2 = + new CompactSkylarkInfo(provider, layout, new Object[] {null, 5}, Location.BUILTIN); + Concatable result = p1.getConcatter().concat(p1, p2, Location.BUILTIN); + assertThat(result).isInstanceOf(CompactSkylarkInfo.class); + assertThat(((CompactSkylarkInfo) result).getKeys()).containsExactly("f1", "f2"); + assertThat(((CompactSkylarkInfo) result).getValue("f1")).isEqualTo(4); + assertThat(((CompactSkylarkInfo) result).getValue("f2")).isEqualTo(5); + } +} diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java index bbf3c5b09c..ccf7309412 100644 --- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java +++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java @@ -1265,6 +1265,39 @@ public class SkylarkRuleClassFunctionsTest extends SkylarkTestCase { } @Test + public void declaredProvidersWithFieldsConcatSuccess() throws Exception { + evalAndExport( + "data = provider(fields=['f1', 'f2'])", + "d1 = data(f1 = 4)", + "d2 = data(f2 = 5)", + "d3 = d1 + d2", + "f1 = d3.f1", + "f2 = d3.f2"); + assertThat(lookup("f1")).isEqualTo(4); + assertThat(lookup("f2")).isEqualTo(5); + } + + @Test + public void declaredProvidersWithFieldsConcatError() throws Exception { + evalAndExport("data1 = provider(fields=['f1', 'f2'])", "data2 = provider(fields=['f3'])"); + checkEvalError( + "Cannot concat data1 with data2", + "d1 = data1(f1=1, f2=2)", + "d2 = data2(f3=3)", + "d = d1 + d2"); + } + + @Test + public void declaredProvidersWithOverlappingFieldsConcatError() throws Exception { + evalAndExport("data = provider(fields=['f1', 'f2'])"); + checkEvalError( + "Cannot concat structs with common field(s): f1", + "d1 = data(f1 = 4)", + "d2 = data(f1 = 5)", + "d1 + d2"); + } + + @Test public void structsAsDeclaredProvidersTest() throws Exception { evalAndExport( "data = struct(x = 1)" |