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
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 ac7ade3..429f419 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 @@
}
}
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 61bab35..93bbcfe 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 @@
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 755a5df..c20d574 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.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 @@
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();
- private StructConcatter() {}
+ /**
+ * {@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 SkylarkInfo concat(Concatable left, Concatable right, Location loc)
- throws EvalException {
+ 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];
+ }
+
+ @Override
+ public boolean hasKey(String name) {
+ Integer index = layout.get(name);
+ return index != null && values[index] != null;
+ }
+
+ @Override
+ 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 0cec941..cdbf73e 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 @@
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 @@
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 @@
@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 f0cb164..fa06153 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 @@
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 @@
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 0000000..a0d546f
--- /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 bbf3c5b..ccf7309 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 @@
}
@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)"
