starlark: add StarlarkList.Builder
...and use it to reduce copying during construction.
+ Tests
See CL 339475495 for corresponding Dict change.
PiperOrigin-RevId: 340344770
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkAttributesCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkAttributesCollection.java
index ca59e2e..ab0dbfa 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkAttributesCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkAttributesCollection.java
@@ -199,8 +199,7 @@
}
filesBuilder.put(
skyname,
- StarlarkList.copyOf(
- /*mutability=*/ null,
+ StarlarkList.immutableCopyOf(
context.getRuleContext().getPrerequisiteArtifacts(a.getName()).list()));
if (type == BuildType.LABEL && !a.getTransitionFactory().isSplit()) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
index d6aa055..079ab04 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
@@ -186,13 +186,13 @@
if (type.getLabelClass() != LabelClass.OUTPUT) {
continue;
}
- ImmutableList.Builder<Artifact> artifactsBuilder = ImmutableList.builder();
+ StarlarkList.Builder<Artifact> artifactsBuilder = StarlarkList.builder();
for (OutputFile outputFile : ruleContext.getRule().getOutputFileMap().get(attrName)) {
Artifact artifact = ruleContext.createOutputArtifact(outputFile);
artifactsBuilder.add(artifact);
artifactLabelMapBuilder.put(artifact, outputFile.getLabel());
}
- ImmutableList<Artifact> artifacts = artifactsBuilder.build();
+ StarlarkList<Artifact> artifacts = artifactsBuilder.buildImmutable();
if (type == BuildType.OUTPUT) {
if (artifacts.size() == 1) {
@@ -201,7 +201,7 @@
outputs.addOutput(attrName, Starlark.NONE);
}
} else if (type == BuildType.OUTPUT_LIST) {
- outputs.addOutput(attrName, StarlarkList.immutableCopyOf(artifacts));
+ outputs.addOutput(attrName, artifacts);
} else {
throw new IllegalArgumentException(
"Type of " + attrName + "(" + type + ") is not output type ");
diff --git a/src/main/java/net/starlark/java/eval/Eval.java b/src/main/java/net/starlark/java/eval/Eval.java
index 29bbec7..5f20a32 100644
--- a/src/main/java/net/starlark/java/eval/Eval.java
+++ b/src/main/java/net/starlark/java/eval/Eval.java
@@ -748,7 +748,7 @@
private static Object evalComprehension(StarlarkThread.Frame fr, Comprehension comp)
throws EvalException, InterruptedException {
final Dict<Object, Object> dict = comp.isDict() ? Dict.of(fr.thread.mutability()) : null;
- final ArrayList<Object> list = comp.isDict() ? null : new ArrayList<>();
+ final StarlarkList.Builder<Object> list = comp.isDict() ? null : StarlarkList.builder();
// Save previous value (if any) of local variables bound in a 'for' clause
// so we can restore them later.
@@ -836,7 +836,7 @@
}
}
- return comp.isDict() ? dict : StarlarkList.copyOf(fr.thread.mutability(), list);
+ return comp.isDict() ? dict : list.build(fr.thread.mutability());
}
private static final Object[] EMPTY = {};
diff --git a/src/main/java/net/starlark/java/eval/MethodLibrary.java b/src/main/java/net/starlark/java/eval/MethodLibrary.java
index 934b5c8..a1893c4 100644
--- a/src/main/java/net/starlark/java/eval/MethodLibrary.java
+++ b/src/main/java/net/starlark/java/eval/MethodLibrary.java
@@ -15,13 +15,10 @@
package net.starlark.java.eval;
import com.google.common.base.Ascii;
-import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;
-import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
-import java.util.List;
import java.util.NoSuchElementException;
import net.starlark.java.annot.Param;
import net.starlark.java.annot.ParamType;
@@ -754,27 +751,27 @@
extraPositionals = @Param(name = "args", doc = "lists to zip."),
useStarlarkThread = true)
public StarlarkList<?> zip(Sequence<?> args, StarlarkThread thread) throws EvalException {
- Iterator<?>[] iterators = new Iterator<?>[args.size()];
- for (int i = 0; i < args.size(); i++) {
- iterators[i] = Starlark.toIterable(args.get(i)).iterator();
- }
- ArrayList<Tuple> result = new ArrayList<>();
- boolean allHasNext;
- do {
- allHasNext = !args.isEmpty();
- List<Object> elem = Lists.newArrayListWithExpectedSize(args.size());
- for (Iterator<?> iterator : iterators) {
- if (iterator.hasNext()) {
- elem.add(iterator.next());
- } else {
- allHasNext = false;
+ StarlarkList.Builder<Tuple> result = StarlarkList.builder();
+ int ncols = args.size();
+ if (ncols > 0) {
+ Iterator<?>[] iterators = new Iterator<?>[ncols];
+ for (int i = 0; i < ncols; i++) {
+ iterators[i] = Starlark.toIterable(args.get(i)).iterator();
+ }
+ rows:
+ for (; ; ) {
+ Object[] elem = new Object[ncols];
+ for (int i = 0; i < ncols; i++) {
+ Iterator<?> it = iterators[i];
+ if (!it.hasNext()) {
+ break rows;
+ }
+ elem[i] = it.next();
}
+ result.add(Tuple.wrap(elem));
}
- if (allHasNext) {
- result.add(Tuple.copyOf(elem));
- }
- } while (allHasNext);
- return StarlarkList.copyOf(thread.mutability(), result);
+ }
+ return result.build(thread.mutability());
}
/** Starlark bool type. */
diff --git a/src/main/java/net/starlark/java/eval/StarlarkList.java b/src/main/java/net/starlark/java/eval/StarlarkList.java
index 87ac690..c11bfcc 100644
--- a/src/main/java/net/starlark/java/eval/StarlarkList.java
+++ b/src/main/java/net/starlark/java/eval/StarlarkList.java
@@ -85,9 +85,9 @@
private static final Object[] EMPTY_ARRAY = {};
- private StarlarkList(@Nullable Mutability mutability, Object[] elems) {
+ private StarlarkList(@Nullable Mutability mutability, Object[] elems, int size) {
this.elems = elems;
- this.size = elems.length;
+ this.size = size;
this.mutability = mutability == null ? Mutability.IMMUTABLE : mutability;
}
@@ -97,7 +97,7 @@
* instance may do so.
*/
static <T> StarlarkList<T> wrap(@Nullable Mutability mutability, Object[] elems) {
- return new StarlarkList<>(mutability, elems);
+ return new StarlarkList<>(mutability, elems, elems.length);
}
@Override
@@ -181,6 +181,79 @@
return wrap(null, Arrays.copyOf(elems, elems.length));
}
+ /** Returns a new empty StarlarkList builder. */
+ public static <T> Builder<T> builder() {
+ return new Builder<>();
+ }
+
+ /** A reusable builder for StarlarkLists. */
+ public static final class Builder<T> {
+ private Object[] elems = EMPTY;
+ private int size;
+ private boolean shared; // whether elems is nonempty and shared with some StarlarkList
+
+ private static final Object[] EMPTY = {};
+
+ /** Adds an element to the builder. */
+ public Builder<T> add(T v) {
+ ensureCapacity(1);
+ elems[size++] = Starlark.checkValid(v);
+ return this;
+ }
+
+ /** Adds all the iterable's entries to the builder. */
+ public Builder<T> addAll(Iterable<? extends T> seq) {
+ if (!(seq instanceof Collection)) {
+ // iterable of unknown size
+ for (T elem : seq) {
+ add(elem);
+ }
+
+ } else if (size == 0) {
+ // first time: bulk copy, avoiding iterator
+ elems = ((Collection<? extends T>) seq).toArray();
+ for (Object elem : elems) {
+ Starlark.checkValid(elem);
+ }
+ size = elems.length;
+
+ } else {
+ // general case
+ ensureCapacity(((Collection) seq).size());
+ for (Object elem : seq) {
+ elems[size++] = Starlark.checkValid(elem);
+ }
+ }
+ return this;
+ }
+
+ // Ensures elems is unshared with sufficient capacity for n additional elements.
+ private void ensureCapacity(int n) {
+ int cap = elems.length;
+ if (shared || size + n > cap) {
+ int newcap = Math.max(size + n, cap + (cap >> 1) + 1); // grow by at least 50%
+ elems = Arrays.copyOf(elems, newcap);
+ shared = false;
+ }
+ }
+
+ /** Returns a new immutable StarlarkList containing the elements added so far. */
+ public StarlarkList<T> buildImmutable() {
+ return build(null);
+ }
+
+ /**
+ * Returns a new StarlarkList containing the elements added so far. The result has the specified
+ * mutability; null means immutable.
+ */
+ public StarlarkList<T> build(@Nullable Mutability mu) {
+ // TODO(adonovan): opt: if elems.length ≫ size, reallocate smaller.
+ ensureCapacity(0);
+ shared = size > 0;
+ return new StarlarkList<T>(mu, elems, size);
+ }
+ }
+
@Override
public Mutability mutability() {
return mutability;
diff --git a/src/main/java/net/starlark/java/eval/StringModule.java b/src/main/java/net/starlark/java/eval/StringModule.java
index 448bcb9..a40f768 100644
--- a/src/main/java/net/starlark/java/eval/StringModule.java
+++ b/src/main/java/net/starlark/java/eval/StringModule.java
@@ -17,10 +17,8 @@
import com.google.common.base.Ascii;
import com.google.common.base.CharMatcher;
import com.google.common.base.Joiner;
-import com.google.common.collect.ImmutableList;
import java.util.ArrayList;
import java.util.Collections;
-import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import net.starlark.java.annot.Param;
@@ -339,7 +337,7 @@
if (maxSplitO != Starlark.NONE) {
maxSplit = Starlark.toInt(maxSplitO, "maxsplit");
}
- ArrayList<String> res = new ArrayList<>();
+ StarlarkList.Builder<String> res = StarlarkList.builder();
int start = 0;
while (true) {
int end = self.indexOf(sep, start);
@@ -350,7 +348,7 @@
res.add(self.substring(start, end));
start = end + sep.length();
}
- return StarlarkList.copyOf(thread.mutability(), res);
+ return res.build(thread.mutability());
}
@StarlarkMethod(
@@ -646,7 +644,7 @@
name = "splitlines",
doc =
"Splits the string at line boundaries ('\\n', '\\r\\n', '\\r') "
- + "and returns the result as a list.",
+ + "and returns the result as a new mutable list.",
parameters = {
@Param(name = "self", doc = "This string."),
@Param(
@@ -654,9 +652,10 @@
name = "keepends",
defaultValue = "False",
doc = "Whether the line breaks should be included in the resulting list.")
- })
- public Sequence<String> splitLines(String self, Boolean keepEnds) throws EvalException {
- List<String> result = new ArrayList<>();
+ },
+ useStarlarkThread = true)
+ public Sequence<String> splitLines(String self, boolean keepEnds, StarlarkThread thread) {
+ StarlarkList.Builder<String> result = StarlarkList.builder();
Matcher matcher = SPLIT_LINES_PATTERN.matcher(self);
while (matcher.find()) {
String line = matcher.group("line");
@@ -671,9 +670,9 @@
result.add(line);
}
}
- // TODO(adonovan): spec should state immutability.
- // Python[23] and go.starlark.net return a mutable list.
- return StarlarkList.immutableCopyOf(result);
+ // TODO(adonovan): spec should state that result is mutable,
+ // as in Python[23] and go.starlark.net.
+ return result.build(thread.mutability());
}
@StarlarkMethod(
@@ -856,12 +855,13 @@
+ "Equivalent to <code>[s[i] for i in range(len(s))]</code>, except that the "
+ "returned value might not be a list.",
parameters = {@Param(name = "self", doc = "This string.")})
- public Sequence<String> elems(String self) throws EvalException {
- ImmutableList.Builder<String> builder = new ImmutableList.Builder<>();
+ public Sequence<String> elems(String self) {
+ // TODO(adonovan): opt: return a new type that is lazily iterable.
+ StarlarkList.Builder<String> res = StarlarkList.builder();
for (char c : self.toCharArray()) {
- builder.add(String.valueOf(c));
+ res.add(String.valueOf(c));
}
- return StarlarkList.immutableCopyOf(builder.build());
+ return res.buildImmutable();
}
@StarlarkMethod(
diff --git a/src/test/java/net/starlark/java/eval/StarlarkListTest.java b/src/test/java/net/starlark/java/eval/StarlarkListTest.java
index 4505f6d..9685696 100644
--- a/src/test/java/net/starlark/java/eval/StarlarkListTest.java
+++ b/src/test/java/net/starlark/java/eval/StarlarkListTest.java
@@ -329,4 +329,55 @@
wrapped[0] = "goodbye";
assertThat((List<String>) mutableList).containsExactly("goodbye");
}
+
+ @Test
+ public void testBuilder() throws EvalException {
+ // add
+ StarlarkList<String> list1 =
+ StarlarkList.<String>builder().add("a").add("b").add("c").buildImmutable();
+ assertThat((List<?>) list1).containsExactly("a", "b", "c");
+ assertThrows(EvalException.class, () -> list1.addElement("d")); // immutable
+
+ // addAll(Collection)
+ StarlarkList<String> list2 =
+ StarlarkList.<String>builder()
+ .addAll(ImmutableList.of("a", "b"))
+ .addAll(ImmutableList.of("c", "d"))
+ .buildImmutable();
+ assertThat((List<?>) list2).containsExactly("a", "b", "c", "d");
+
+ // addAll(Iterable)
+ StarlarkList<String> list3 =
+ StarlarkList.<String>builder()
+ .addAll(() -> ImmutableList.of("a", "b", "c").iterator())
+ .buildImmutable();
+ assertThat((List<?>) list3).containsExactly("a", "b", "c");
+
+ // mutability and builder re-use
+ StarlarkList.Builder<String> builder = StarlarkList.<String>builder().add("a").add("b");
+ StarlarkList<String> list4 = builder.buildImmutable();
+ assertThat((List<?>) list4).containsExactly("a", "b");
+ builder.add("c"); // continue building
+ StarlarkList<String> list5 = builder.buildImmutable();
+ assertThat((List<?>) list5).containsExactly("a", "b", "c");
+ assertThat((List<?>) list4).containsExactly("a", "b"); // unchanged
+ Mutability mu = Mutability.create("test");
+ StarlarkList<String> list6 = builder.build(mu);
+ list6.addElement("d");
+ mu.close();
+ assertThrows(EvalException.class, () -> list6.addElement("e")); // frozen
+ assertThat((List<?>) list6).containsExactly("a", "b", "c", "d");
+ }
+
+ @Test
+ public void testListsFromSameBuilderDoNotShareBackingArray() throws EvalException {
+ Mutability mu = Mutability.create("test");
+ StarlarkList.Builder<String> builder = StarlarkList.<String>builder().add("a").add("b");
+ StarlarkList<String> x = builder.build(mu);
+ x.setElementAt(1, "c");
+ StarlarkList<String> y = builder.build(mu);
+ y.setElementAt(1, "C");
+ assertThat((List<?>) x).containsExactly("a", "c");
+ assertThat((List<?>) y).containsExactly("a", "C");
+ }
}
