bazel syntax: simplify and optimize list, tuple, range
Sequence:
- is now an interface
- delete getContentsUnsafe: don't prescribe representation.
- delete unnecessary stub methods from StarlarkValue and AbstractList.
- delete abstract repeat method. It is defined only for list and tuple.
Tuple:
- now extends AbstractList
- manipulates an Object[] directly, eliminating ImmutableList intermediary
...yet getImmutableList avoids a copy using the toArray sharing trick.
- eliminate all unnecessary array copies
- isHashable and isImmutable iterate over Object[] directly, not List wrapper.
StarlarkList
- now extends AbstractList
- delete one overload of StarlarkList.wrapUnsafe
- manipulates an Object[] directly, eliminating ArrayList intermediary.
- eliminate all unnecessary array copies
RangeList:
- optimize equals() not to materialize the sequence
- merge RangeList and RangeListView
- delete unreachable repeat() method
Also:
- removed comment at Sequence.createImmutable.
We should stop using StarlarkThread to mean Mutability.
(Longer term, we should get rid of Mutability in favor of a per-object frozen bit.)
PiperOrigin-RevId: 280680660
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Dict.java b/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
index 257fb77..b34f094 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
@@ -22,7 +22,6 @@
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
-import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
@@ -191,7 +190,7 @@
Object key = keySet().iterator().next();
Object value = get(key);
remove(key, loc);
- return Tuple.of(key, value);
+ return Tuple.pair(key, value);
}
@SkylarkCallable(
@@ -280,11 +279,12 @@
+ "</pre>\n",
useStarlarkThread = true)
public StarlarkList<?> items(StarlarkThread thread) throws EvalException {
- ArrayList<Object> list = Lists.newArrayListWithCapacity(size());
- for (Map.Entry<?, ?> entries : entrySet()) {
- list.add(Tuple.of(entries.getKey(), entries.getValue()));
+ Object[] array = new Object[size()];
+ int i = 0;
+ for (Map.Entry<?, ?> e : entrySet()) {
+ array[i++] = Tuple.pair(e.getKey(), e.getValue());
}
- return StarlarkList.wrapUnsafe(thread, list);
+ return StarlarkList.wrap(thread.mutability(), array);
}
@SkylarkCallable(
@@ -295,11 +295,12 @@
+ "</pre>\n",
useStarlarkThread = true)
public StarlarkList<?> keys(StarlarkThread thread) throws EvalException {
- ArrayList<Object> list = Lists.newArrayListWithCapacity(size());
- for (Map.Entry<?, ?> entries : entrySet()) {
- list.add(entries.getKey());
+ Object[] array = new Object[size()];
+ int i = 0;
+ for (Map.Entry<?, ?> e : entrySet()) {
+ array[i++] = e.getKey();
}
- return StarlarkList.wrapUnsafe(thread, list);
+ return StarlarkList.wrap(thread.mutability(), array);
}
private static final Dict<?, ?> EMPTY = withMutability(Mutability.IMMUTABLE);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
index 68d60d2..dd14952 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
@@ -547,13 +547,12 @@
case LIST_EXPR:
{
ListExpression list = (ListExpression) expr;
- ArrayList<Object> result = new ArrayList<>(list.getElements().size());
- for (Expression elem : list.getElements()) {
- result.add(eval(thread, elem));
+ int n = list.getElements().size();
+ Object[] array = new Object[n];
+ for (int i = 0; i < n; i++) {
+ array[i] = eval(thread, list.getElements().get(i));
}
- return list.isTuple()
- ? Tuple.copyOf(result) // TODO(adonovan): opt: avoid copy
- : StarlarkList.wrapUnsafe(thread, result);
+ return list.isTuple() ? Tuple.wrap(array) : StarlarkList.wrap(thread.mutability(), array);
}
case SLICE:
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 723d49b..363a3a9 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -853,11 +853,11 @@
if (otherFactor instanceof Integer) {
return Math.multiplyExact(number, (Integer) otherFactor);
} else if (otherFactor instanceof String) {
- // Similar to Python, a factor < 1 leads to an empty string.
return Strings.repeat((String) otherFactor, Math.max(0, number));
- } else if (otherFactor instanceof Sequence && !(otherFactor instanceof RangeList)) {
- // Similar to Python, a factor < 1 leads to an empty string.
- return ((Sequence<?>) otherFactor).repeat(number, thread.mutability());
+ } else if (otherFactor instanceof Tuple) {
+ return ((Tuple<?>) otherFactor).repeat(number, thread.mutability());
+ } else if (otherFactor instanceof StarlarkList) {
+ return ((StarlarkList<?>) otherFactor).repeat(number, thread.mutability());
}
}
throw unknownBinaryOperator(x, y, TokenKind.STAR, location);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 166a698..93acac3 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -36,6 +36,8 @@
import com.google.devtools.build.lib.syntax.StarlarkSemantics.FlagIdentifier;
import java.util.ArrayDeque;
import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
@@ -199,10 +201,10 @@
final StarlarkThread thread)
throws EvalException, InterruptedException {
- ArrayList<?> list = new ArrayList<>(EvalUtils.toCollection(iterable, loc, thread));
+ Object[] array = EvalUtils.toCollection(iterable, loc, thread).toArray();
if (key == Starlark.NONE) {
try {
- Collections.sort(list, EvalUtils.SKYLARK_COMPARATOR);
+ Arrays.sort(array, EvalUtils.SKYLARK_COMPARATOR);
} catch (EvalUtils.ComparisonException e) {
throw new EvalException(loc, e);
}
@@ -232,7 +234,7 @@
KeyComparator comp = new KeyComparator();
try {
- Collections.sort(list, comp);
+ Arrays.sort(array, comp);
} catch (EvalUtils.ComparisonException e) {
throw new EvalException(loc, e);
}
@@ -249,9 +251,13 @@
}
if (reverse) {
- Collections.reverse(list);
+ for (int i = 0, j = array.length - 1; i < j; i++, j--) {
+ Object tmp = array[i];
+ array[i] = array[j];
+ array[j] = tmp;
+ }
}
- return StarlarkList.wrapUnsafe(thread, list);
+ return StarlarkList.wrap(thread.mutability(), array);
}
@SkylarkCallable(
@@ -278,7 +284,7 @@
for (Object element : EvalUtils.toIterable(sequence, loc, thread)) {
tmpList.addFirst(element);
}
- return StarlarkList.copyOf(thread, tmpList);
+ return StarlarkList.copyOf(thread.mutability(), tmpList);
}
@SkylarkCallable(
@@ -320,7 +326,7 @@
useLocation = true,
useStarlarkThread = true)
public StarlarkList<?> list(Object x, Location loc, StarlarkThread thread) throws EvalException {
- return StarlarkList.copyOf(thread, EvalUtils.toCollection(x, loc, thread));
+ return StarlarkList.copyOf(thread.mutability(), EvalUtils.toCollection(x, loc, thread));
}
@SkylarkCallable(
@@ -633,13 +639,14 @@
useLocation = true)
public StarlarkList<?> enumerate(Object input, Integer start, Location loc, StarlarkThread thread)
throws EvalException {
- int count = start;
- ArrayList<Sequence<?>> result = new ArrayList<>();
- for (Object obj : EvalUtils.toCollection(input, loc, thread)) {
- result.add(Tuple.of(count, obj));
- count++;
+ Collection<?> src = EvalUtils.toCollection(input, loc, thread);
+ Object[] array = new Object[src.size()];
+ int i = 0;
+ for (Object x : src) {
+ array[i] = Tuple.pair(i + start, x);
+ i++;
}
- return StarlarkList.wrapUnsafe(thread, result);
+ return StarlarkList.wrap(thread.mutability(), array);
}
@SkylarkCallable(
@@ -719,7 +726,7 @@
if (step == 0) {
throw new EvalException(loc, "step cannot be 0");
}
- return RangeList.of(start, stop, step);
+ return new RangeList(start, stop, step);
}
/** Returns true if the object has a field of the given name, otherwise false. */
@@ -820,7 +827,7 @@
fields.addAll(((ClassObject) object).getFieldNames());
}
fields.addAll(CallUtils.getMethodNames(thread.getSemantics(), object.getClass()));
- return StarlarkList.copyOf(thread, fields);
+ return StarlarkList.copyOf(thread.mutability(), fields);
}
@SkylarkCallable(
@@ -1204,7 +1211,7 @@
result.add(Tuple.copyOf(elem));
}
} while (allHasNext);
- return StarlarkList.wrapUnsafe(thread, result);
+ return StarlarkList.copyOf(thread.mutability(), result);
}
/** Skylark int type. */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java b/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java
index 275b0b9..4a40253 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java
@@ -15,7 +15,6 @@
package com.google.devtools.build.lib.syntax;
import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.UnmodifiableIterator;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.events.Location;
@@ -24,7 +23,6 @@
import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
import java.util.AbstractList;
import java.util.Iterator;
-import java.util.List;
import java.util.NoSuchElementException;
/**
@@ -53,34 +51,87 @@
+ "range(10)[3:0:-1] # range(3, 0, -1)</pre>"
+ "Ranges are immutable, as in Python 3.")
@Immutable
-final class RangeList extends Sequence<Integer> {
+final class RangeList extends AbstractList<Integer> implements Sequence<Integer> {
- private final int step;
private final int start;
+ private final int stop;
+ private final int step;
+ private final int size; // (derived)
- private static int computeItem(int start, int step, int index) {
+ RangeList(int start, int stop, int step) {
+ Preconditions.checkArgument(step != 0);
+
+ this.start = start;
+ this.stop = stop;
+ this.step = step;
+
+ // compute size.
+ // Python version:
+ // https://github.com/python/cpython/blob/09bb918a61031377d720f1a0fa1fe53c962791b6/Objects/rangeobject.c#L144
+ int low; // [low,high) is a half-open interval
+ int high;
+ if (step > 0) {
+ low = start;
+ high = stop;
+ } else {
+ low = stop;
+ high = start;
+ step = -step;
+ }
+ if (low >= high) {
+ this.size = 0;
+ } else {
+ int diff = high - low - 1;
+ this.size = diff / step + 1;
+ }
+ }
+
+ @Override
+ public Integer get(int index) {
+ if (index < 0 || index >= size()) {
+ throw new ArrayIndexOutOfBoundsException(index + ":" + this);
+ }
return start + step * index;
}
- /** Provides access to range elements based on their index. */
- private static class RangeListView extends AbstractList<Integer> {
+ @Override
+ public int size() {
+ return size;
+ }
- /** Iterator for increasing/decreasing sequences. */
- private static class RangeListIterator extends UnmodifiableIterator<Integer> {
- private final int stop;
- private final int step;
+ @Override
+ public int hashCode() {
+ return 7873 ^ (5557 * start) ^ (3251 * step) ^ (1091 * size);
+ }
- private int cursor;
+ @Override
+ public boolean equals(Object other) {
+ if (!(other instanceof RangeList)) {
+ return false;
+ }
+ RangeList that = (RangeList) other;
- private RangeListIterator(int start, int stop, int step) {
- this.cursor = start;
- this.stop = stop;
- this.step = step;
- }
+ // Two RangeLists compare equal if they denote the same sequence.
+ if (this.size != that.size) {
+ return false; // sequences differ in length
+ }
+ if (this.size == 0) {
+ return true; // both sequences are empty
+ }
+ if (this.start != that.start) {
+ return false; // first element differs
+ }
+ return this.size == 1 || this.step == that.step;
+ }
+
+ @Override
+ public Iterator<Integer> iterator() {
+ return new UnmodifiableIterator<Integer>() {
+ int cursor = start;
@Override
public boolean hasNext() {
- return (step > 0) ? cursor < stop : cursor > stop;
+ return (step > 0) ? (cursor < stop) : (cursor > stop);
}
@Override
@@ -92,94 +143,7 @@
cursor += step;
return current;
}
- }
-
- /**
- * @return The size of the range specified by {@code start}, {@code stop} and {@code step}.
- * Python version:
- * https://github.com/python/cpython/blob/09bb918a61031377d720f1a0fa1fe53c962791b6/Objects/rangeobject.c#L144
- */
- private static int computeSize(int start, int stop, int step) {
- // low and high represent bounds of the interval with only one of the sides being open.
- int low;
- int high;
- if (step > 0) {
- low = start;
- high = stop;
- } else {
- low = stop;
- high = start;
- step = -step;
- }
- if (low >= high) {
- return 0;
- }
-
- int diff = high - low - 1;
- return diff / step + 1;
- }
-
- private final int start;
- private final int stop;
- private final int step;
- private final int size;
-
- private RangeListView(int start, int stop, int step) {
- this.start = start;
- this.stop = stop;
- this.step = step;
- this.size = computeSize(start, stop, step);
- }
-
- @Override
- public Integer get(int index) {
- if (index < 0 || index >= size()) {
- throw new ArrayIndexOutOfBoundsException(index);
- }
- return computeItem(start, step, index);
- }
-
- @Override
- public int size() {
- return size;
- }
-
- /**
- * Returns an iterator optimized for traversing range elements, since it's the most frequent
- * operation for which ranges are used.
- */
- @Override
- public Iterator<Integer> iterator() {
- return new RangeListIterator(start, stop, step);
- }
-
- /** @return the start of the range. */
- public int getStart() {
- return start;
- }
-
- /** @return the stop element (next after the last one) of the range. */
- public int getStop() {
- return stop;
- }
-
- /** @return the step between each element of the range. */
- public int getStep() {
- return step;
- }
- }
-
- private final RangeListView contents;
-
- private RangeList(int start, int stop, int step) {
- this.step = step;
- this.start = start;
- this.contents = new RangeListView(start, stop, step);
- }
-
- @Override
- public ImmutableList<Integer> getImmutableList() {
- return ImmutableList.copyOf(contents);
+ };
}
@Override
@@ -188,41 +152,26 @@
throws EvalException {
Slice slice = Slice.from(size(), start, end, step, loc);
int substep = slice.step * this.step;
- int substart = computeItem(this.start, this.step, slice.start);
- int substop = computeItem(this.start, this.step, slice.stop);
- return RangeList.of(substart, substop, substep);
+ // TODO(adonovan): why no bounds check here?
+ int substart = getNoCheck(slice.start);
+ int substop = getNoCheck(slice.stop);
+ return new RangeList(substart, substop, substep);
}
- @Override
- public Sequence<Integer> repeat(int times, Mutability mutability) {
- throw new UnsupportedOperationException("Ranges do not support repetition.");
- }
-
- @Override
- protected List<Integer> getContentsUnsafe() {
- return contents;
+ private int getNoCheck(int i) {
+ return start + step * i;
}
@Override
public void repr(SkylarkPrinter printer) {
- if (contents.getStep() == 1) {
- printer.format("range(%d, %d)", contents.getStart(), contents.getStop());
+ if (step == 1) {
+ printer.format("range(%d, %d)", start, stop);
} else {
- printer.format(
- "range(%d, %d, %d)", contents.getStart(), contents.getStop(), contents.getStep());
+ printer.format("range(%d, %d, %d)", start, stop, step);
}
}
/**
- * @return A half-opened range defined by its starting value (inclusive), stop value (exclusive)
- * and a step from previous value to the next one.
- */
- static RangeList of(int start, int stop, int step) {
- Preconditions.checkArgument(step != 0);
- return new RangeList(start, stop, step);
- }
-
- /**
* Represents a slice produced by applying {@code [start:end:step]} to a {@code range}.
*
* <p>{@code start} and {@code stop} define a half-open interval
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java b/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
index 329c41a..ff9b4da 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
@@ -15,17 +15,12 @@
package com.google.devtools.build.lib.syntax;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterators;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
-import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
-import java.util.Collection;
import java.util.Collections;
-import java.util.Iterator;
import java.util.List;
-import java.util.ListIterator;
import java.util.RandomAccess;
import javax.annotation.Nullable;
@@ -40,15 +35,17 @@
documented = false,
category = SkylarkModuleCategory.BUILTIN,
doc = "common type of lists and tuples.")
-public abstract class Sequence<E> implements SkylarkValue, List<E>, RandomAccess, SkylarkIndexable {
+public interface Sequence<E> extends SkylarkValue, List<E>, RandomAccess, SkylarkIndexable {
@Override
- public final boolean truth() {
+ default boolean truth() {
return !isEmpty();
}
/** Returns an ImmutableList object with the current underlying contents of this Sequence. */
- public abstract ImmutableList<E> getImmutableList();
+ default ImmutableList<E> getImmutableList() {
+ return ImmutableList.copyOf(this);
+ }
/**
* Retrieve an entry from a Sequence.
@@ -58,20 +55,13 @@
* @throws EvalException if the key is invalid
*/
@Override
- public E getIndex(Object key, Location loc) throws EvalException {
- List<E> list = getContentsUnsafe();
- int index = EvalUtils.getSequenceIndex(key, list.size(), loc);
- return list.get(index);
+ default E getIndex(Object key, Location loc) throws EvalException {
+ return get(EvalUtils.getSequenceIndex(key, size(), loc));
}
@Override
- public boolean containsKey(Object key, Location loc) throws EvalException {
- for (Object obj : this) {
- if (obj.equals(key)) {
- return true;
- }
- }
- return false;
+ default boolean containsKey(Object key, Location loc) throws EvalException {
+ return contains(key);
}
/**
@@ -83,48 +73,10 @@
* @see EvalUtils#getSliceIndices
* @throws EvalException if the key is invalid; uses {@code loc} for error reporting
*/
- public abstract Sequence<E> getSlice(
- Object start, Object end, Object step, Location loc, Mutability mutability)
+ Sequence<E> getSlice(Object start, Object end, Object step, Location loc, Mutability mutability)
throws EvalException;
/**
- * Constructs a repetition of this {@code Sequence}.
- *
- * <p>{@code mutability} will be used for the resulting list. If it is null, the list will be
- * immutable. For {@code Tuple}s, which are always immutable, this argument is ignored.
- */
- // TODO(adonovan): remove this method and handle only int*{list,tuple} in EvalUtils.mult.
- // In particular, reject int*range. (In principal this is a breaking change.)
- public abstract Sequence<E> repeat(int times, Mutability mutability);
-
- @Override
- public void repr(SkylarkPrinter printer) {
- printer.printList(getContentsUnsafe(), this instanceof Tuple);
- }
-
- @Override
- public String toString() {
- return Printer.repr(this);
- }
-
- // Note that the following two functions slightly violate the Java List protocol,
- // in that it does NOT consider that a Sequence .equals() an arbitrary List with same contents.
- // This is because we use .equals() to model skylark equality, which like Python
- // distinguishes a StarlarkList from a Tuple.
- @Override
- public boolean equals(Object object) {
- return (this == object)
- || ((object != null)
- && (this.getClass() == object.getClass())
- && getContentsUnsafe().equals(((Sequence) object).getContentsUnsafe()));
- }
-
- @Override
- public int hashCode() {
- return getClass().hashCode() + 31 * getContentsUnsafe().hashCode();
- }
-
- /**
* Casts a {@code List<?>} to an unmodifiable {@code List<T>}, after checking that its contents
* all have type {@code type}.
*
@@ -137,6 +89,7 @@
// We could have used bounded generics to ensure that only downcasts are possible (i.e. cast
// List<S> to List<T extends S>), but this would be less convenient for some callers, and it would
// disallow casting an empty list to any type.
+ // TODO(adonovan): this method doesn't belong here.
@SuppressWarnings("unchecked")
public static <T> List<T> castList(List<?> list, Class<T> type, @Nullable String description)
throws EvalException {
@@ -158,6 +111,7 @@
* @param type the expected type of all the list's elements
* @param description a description of the argument being converted, or null, for debugging
*/
+ // TODO(adonovan): this method doesn't belong here.
public static <T> List<T> castSkylarkListOrNoneToList(
Object obj, Class<T> type, @Nullable String description) throws EvalException {
if (EvalUtils.isNullOrNone(obj)) {
@@ -172,168 +126,25 @@
}
/**
- * Casts this list as an unmodifiable {@code List<T>}, after checking that each element has
- * type {@code type}.
+ * Casts this list as an unmodifiable {@code List<T>}, after checking that each element has type
+ * {@code type}.
*
* @param type the expected type of all the list's elements
* @param description a description of the argument being converted, or null, for debugging
*/
- public <T> List<T> getContents(Class<T> type, @Nullable String description)
+ // TODO(adonovan): this method doesn't belong here.
+ default <T> List<T> getContents(Class<T> type, @Nullable String description)
throws EvalException {
- return castList(getContentsUnsafe(), type, description);
+ return castList(this, type, description);
}
/**
- * Creates an immutable Skylark list with the given elements.
- *
- * <p>It is unspecified whether this is a Skylark list or tuple. For more control, use one of the
- * factory methods in {@link StarlarkList} or {@link Tuple}.
+ * Creates an immutable StarlarkList with the given elements.
*
* <p>The caller must ensure that the elements of {@code contents} are not mutable.
*/
- // TODO(bazel-team): Eliminate this function in favor of a new StarlarkList factory method. With
- // such a method, we may no longer need to take null as a possible value for the Mutability or
- // StarlarkThread. That in turn would allow us to overload StarlarkList#of to take either a
- // Mutability or StarlarkThread.
+ // TODO(adonovan): move to StarlarkList.
public static <E> Sequence<E> createImmutable(Iterable<? extends E> contents) {
return StarlarkList.copyOf(Mutability.IMMUTABLE, contents);
}
-
- // methods of java.util.List
-
- // read operations
- //
- // TODO(adonovan): opt: push all read operations down into the subclasses
- // (list and tuple), as the getContentsUnsafe abstraction forces the internals
- // to be expressed in terms of Lists, which requires either a wasteful indirect
- // representation, or a wasteful lazy allocation of a list wrapper.
- protected abstract List<E> getContentsUnsafe();
-
- @Override
- public boolean contains(@Nullable Object object) {
- return getContentsUnsafe().contains(object);
- }
-
- @Override
- public boolean containsAll(Collection<?> collection) {
- return getContentsUnsafe().containsAll(collection);
- }
-
- @Override
- public E get(int i) {
- return getContentsUnsafe().get(i);
- }
-
- @Override
- public int indexOf(Object element) {
- return getContentsUnsafe().indexOf(element);
- }
-
- @Override
- public boolean isEmpty() {
- return getContentsUnsafe().isEmpty();
- }
-
- @Override
- public Iterator<E> iterator() {
- return Iterators.unmodifiableIterator(getContentsUnsafe().iterator());
- }
-
- @Override
- public int lastIndexOf(Object element) {
- return getContentsUnsafe().lastIndexOf(element);
- }
-
- @Override
- public ListIterator<E> listIterator() {
- return Collections.unmodifiableList(getContentsUnsafe()).listIterator();
- }
-
- @Override
- public ListIterator<E> listIterator(int index) {
- return Collections.unmodifiableList(getContentsUnsafe()).listIterator(index);
- }
-
- @Override
- public List<E> subList(int fromIndex, int toIndex) {
- return Collections.unmodifiableList(getContentsUnsafe()).subList(fromIndex, toIndex);
- }
-
- @Override
- public int size() {
- return getContentsUnsafe().size();
- }
-
- // toArray() and toArray(T[]) return copies, so we don't need an unmodifiable view.
- @Override
- public Object[] toArray() {
- return getContentsUnsafe().toArray();
- }
-
- @Override
- public <T> T[] toArray(T[] other) {
- return getContentsUnsafe().toArray(other);
- }
-
- // modify operations
-
- @Deprecated
- @Override
- public final boolean add(E element) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final void add(int index, E element) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final boolean addAll(int index, Collection<? extends E> elements) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final boolean addAll(Collection<? extends E> collection) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final void clear() {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final E remove(int index) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final boolean remove(Object object) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final boolean removeAll(Collection<?> collection) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final boolean retainAll(Collection<?> collection) {
- throw new UnsupportedOperationException();
- }
-
- @Deprecated
- @Override
- public final E set(int index, E element) {
- throw new UnsupportedOperationException();
- }
}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
index 7a21223..dbcf763 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
@@ -14,16 +14,16 @@
package com.google.devtools.build.lib.syntax;
-import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.skylarkinterface.Param;
import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
-import java.util.ArrayList;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
+import java.util.AbstractList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import javax.annotation.Nullable;
@@ -46,34 +46,29 @@
+ "['a', 'b', 'c', 'd'][::2] # ['a', 'c']\n"
+ "['a', 'b', 'c', 'd'][3:0:-1] # ['d', 'c', 'b']</pre>"
+ "Lists are mutable, as in Python.")
-public final class StarlarkList<E> extends Sequence<E> implements StarlarkMutable {
+public final class StarlarkList<E> extends AbstractList<E> implements Sequence<E>, StarlarkMutable {
- private final ArrayList<E> contents;
+ private int size;
+ private Object[] elems = EMPTY_ARRAY;
/** Final except for {@link #unsafeShallowFreeze}; must not be modified any other way. */
private Mutability mutability;
- private StarlarkList(ArrayList<E> rawContents, @Nullable Mutability mutability) {
- this.contents = Preconditions.checkNotNull(rawContents);
+ private static final Object[] EMPTY_ARRAY = {};
+
+ private StarlarkList(@Nullable Mutability mutability, Object[] elems) {
+ this.elems = elems;
+ this.size = elems.length;
this.mutability = mutability == null ? Mutability.IMMUTABLE : mutability;
}
/**
- * Creates an instance, taking ownership of the supplied {@link ArrayList}. This is exposed for
- * performance reasons. May be used when the calling code will not modify the supplied list after
- * calling (honor system).
+ * Takes ownership of the supplied array and returns a new StarlarkList instance that initially
+ * wraps the array. The caller must not subsequently modify the array, but the StarlarkList
+ * instance may do so.
*/
- static <T> StarlarkList<T> wrapUnsafe(@Nullable StarlarkThread thread, ArrayList<T> rawContents) {
- return wrapUnsafe(thread == null ? null : thread.mutability(), rawContents);
- }
-
- /**
- * Create an instance, taking ownership of the supplied {@link ArrayList}. This is exposed for
- * performance reasons. May be used when the calling code will not modify the supplied list after
- * calling (honor system).
- */
- static <T> StarlarkList<T> wrapUnsafe(@Nullable Mutability mutability, ArrayList<T> rawContents) {
- return new StarlarkList<>(rawContents, mutability);
+ static <T> StarlarkList<T> wrap(@Nullable Mutability mutability, Object[] elems) {
+ return new StarlarkList<>(mutability, elems);
}
@Override
@@ -93,10 +88,9 @@
* environments were then frozen. This instance is for empty lists that were always frozen from
* the beginning.
*/
- private static final StarlarkList<?> EMPTY =
- StarlarkList.copyOf(Mutability.IMMUTABLE, ImmutableList.of());
+ private static final StarlarkList<?> EMPTY = wrap(Mutability.IMMUTABLE, EMPTY_ARRAY);
- /** Returns an empty frozen list, cast to have an arbitrary content type. */
+ /** Returns an empty frozen list of the desired type. */
@SuppressWarnings("unchecked")
public static <T> StarlarkList<T> empty() {
return (StarlarkList<T>) EMPTY;
@@ -107,28 +101,34 @@
* {@link Mutability}. If {@code mutability} is null, the list is immutable.
*/
public static <T> StarlarkList<T> copyOf(
- @Nullable Mutability mutability, Iterable<? extends T> contents) {
- return new StarlarkList<>(Lists.newArrayList(contents), mutability);
+ @Nullable Mutability mutability, Iterable<? extends T> elems) {
+ return wrap(mutability, Iterables.toArray(elems, Object.class));
}
/**
* Returns a {@code StarlarkList} whose items are given by an iterable and which has the {@link
* Mutability} belonging to the given {@link StarlarkThread}. If {@code thread} is null, the list
* is immutable.
+ *
+ * @deprecated call {@code copyOf(thread.mutability(), elems)} instead.
*/
+ @Deprecated
public static <T> StarlarkList<T> copyOf(
- @Nullable StarlarkThread thread, Iterable<? extends T> contents) {
- return StarlarkList.copyOf(thread == null ? null : thread.mutability(), contents);
+ @Nullable StarlarkThread thread, Iterable<? extends T> elems) {
+ Mutability mu = thread == null ? null : thread.mutability();
+ return copyOf(mu, elems);
}
/**
* Returns a {@code StarlarkList} with the given items and the {@link Mutability} of the given
* {@link StarlarkThread}. If {@code thread} is null, the list is immutable.
+ *
+ * @deprecated call {@code of(thread.mutability(), elems)} instead.
*/
- public static <T> StarlarkList<T> of(@Nullable StarlarkThread thread, T... contents) {
- // Safe since we're taking a copy of the input.
- return StarlarkList.wrapUnsafe(
- thread == null ? null : thread.mutability(), Lists.newArrayList(contents));
+ @Deprecated
+ public static <T> StarlarkList<T> of(@Nullable StarlarkThread thread, T... elems) {
+ Mutability mu = thread == null ? null : thread.mutability();
+ return wrap(mu, Arrays.copyOf(elems, elems.length));
}
@Override
@@ -144,12 +144,13 @@
@Override
public ImmutableList<E> getImmutableList() {
- return ImmutableList.copyOf(contents);
- }
+ // Optimization: a frozen array needn't be copied.
+ // If the entire array is full, we can wrap it directly.
+ if (elems.length == size && mutability().isFrozen()) {
+ return Tuple.wrapImmutable(elems);
+ }
- @Override
- protected List<E> getContentsUnsafe() {
- return contents;
+ return ImmutableList.copyOf(this);
}
/**
@@ -157,46 +158,84 @@
* new list will have the given {@link Mutability}.
*/
public static <T> StarlarkList<T> concat(
- StarlarkList<? extends T> left, StarlarkList<? extends T> right, Mutability mutability) {
-
- ArrayList<T> newContents = new ArrayList<>(left.size() + right.size());
- addAll(newContents, left.contents);
- addAll(newContents, right.contents);
- return new StarlarkList<>(newContents, mutability);
- }
-
- /** More efficient {@link List#addAll} replacement when both lists are {@link ArrayList}s. */
- private static <T> void addAll(ArrayList<T> addTo, ArrayList<? extends T> addFrom) {
- // Hot code path, skip iterator.
- for (int i = 0; i < addFrom.size(); i++) {
- addTo.add(addFrom.get(i));
- }
+ StarlarkList<? extends T> x, StarlarkList<? extends T> y, Mutability mutability) {
+ Object[] res = new Object[x.size + y.size];
+ System.arraycopy(x.elems, 0, res, 0, x.size);
+ System.arraycopy(y.elems, 0, res, x.size, y.size);
+ return wrap(mutability, res);
}
@Override
- public StarlarkList<E> repeat(int times, Mutability mutability) {
- if (times <= 0) {
- return StarlarkList.wrapUnsafe(mutability, new ArrayList<>());
+ public boolean equals(Object that) {
+ // This slightly violates the java.util.List equivalence contract
+ // because it considers the class, not just the elements.
+ return this == that || (that instanceof StarlarkList && sameElems(this, ((StarlarkList) that)));
+ }
+
+ private static boolean sameElems(StarlarkList<?> x, StarlarkList<?> y) {
+ if (x.size != y.size) {
+ return false;
+ }
+ for (int i = 0; i < x.size; i++) {
+ if (!x.elems[i].equals(y.elems[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ return 6047 + 4673 * Arrays.hashCode(elems);
+ }
+
+ @Override
+ public void repr(SkylarkPrinter printer) {
+ printer.printList(this, /*isTuple=*/ false);
+ }
+
+ // TODO(adonovan): SkylarkValue has 3 String methods yet still we need this fourth. Why?
+ @Override
+ public String toString() {
+ return Printer.repr(this);
+ }
+
+ /** Returns a new StarlarkList containing n consecutive repeats of this tuple. */
+ public StarlarkList<E> repeat(int n, Mutability mutability) {
+ if (n <= 0) {
+ return wrap(mutability, EMPTY_ARRAY);
}
- ArrayList<E> repeated = new ArrayList<>(this.size() * times);
- for (int i = 0; i < times; i++) {
- repeated.addAll(this);
+ // TODO(adonovan): reject unreasonably large n.
+ Object[] res = new Object[n * size];
+ for (int i = 0; i < n; i++) {
+ System.arraycopy(elems, 0, res, i * size, size);
}
- return StarlarkList.wrapUnsafe(mutability, repeated);
+ return wrap(mutability, res);
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public E get(int i) {
+ return (E) elems[i]; // unchecked
+ }
+
+ @Override
+ public int size() {
+ return size;
}
@Override
public StarlarkList<E> getSlice(
Object start, Object end, Object step, Location loc, Mutability mutability)
throws EvalException {
- List<Integer> sliceIndices = EvalUtils.getSliceIndices(start, end, step, this.size(), loc);
- ArrayList<E> list = new ArrayList<>(sliceIndices.size());
- // foreach is not used to avoid iterator overhead
- for (int i = 0; i < sliceIndices.size(); ++i) {
- list.add(this.get(sliceIndices.get(i)));
+ // TODO(adonovan): this is horribly inefficient.
+ List<Integer> indices = EvalUtils.getSliceIndices(start, end, step, size(), loc);
+ Object[] array = new Object[indices.size()];
+ for (int i = 0; i < indices.size(); ++i) {
+ array[i] = elems[indices.get(i)];
}
- return StarlarkList.wrapUnsafe(mutability, list);
+ return wrap(mutability, array);
}
/**
@@ -207,7 +246,20 @@
*/
public void add(E element, Location loc) throws EvalException {
checkMutable(loc);
- contents.add(element);
+ grow(size + 1);
+ elems[size++] = element;
+ }
+
+ // Postcondition: elems.length >= mincap.
+ private void grow(int mincap) {
+ int oldcap = elems.length;
+ if (oldcap < mincap) {
+ int newcap = oldcap + (oldcap >> 1); // grow by at least 50%
+ if (newcap < mincap) {
+ newcap = mincap;
+ }
+ elems = Arrays.copyOf(elems, newcap);
+ }
}
/**
@@ -219,7 +271,10 @@
*/
public void add(int index, E element, Location loc) throws EvalException {
checkMutable(loc);
- contents.add(index, element);
+ grow(size + 1);
+ System.arraycopy(elems, index, elems, index + 1, size - index);
+ elems[index] = element;
+ size++;
}
/**
@@ -230,7 +285,34 @@
*/
public void addAll(Iterable<? extends E> elements, Location loc) throws EvalException {
checkMutable(loc);
- Iterables.addAll(contents, elements);
+ if (elements instanceof StarlarkList) {
+ if (this == elements) {
+ // special case: x.addAll(x)
+ grow(size + size);
+ System.arraycopy(elems, 0, elems, size, size);
+ size += size;
+ } else {
+ // another list
+ StarlarkList<?> src = (StarlarkList) elements;
+ grow(this.size + src.size);
+ System.arraycopy(src.elems, 0, this.elems, this.size, src.size);
+ this.size += src.size;
+ }
+ } else if (elements instanceof Collection) {
+ // collection of known size
+ Collection<?> src = (Collection) elements;
+ int srcsize = src.size();
+ grow(size + srcsize);
+ for (Object x : src) {
+ elems[size++] = x;
+ }
+ } else {
+ // iterable
+ for (Object x : elements) {
+ grow(size + 1);
+ elems[size++] = x;
+ }
+ }
}
/**
@@ -242,7 +324,11 @@
*/
public void remove(int index, Location loc) throws EvalException {
checkMutable(loc);
- contents.remove(index);
+ int n = size - index - 1;
+ if (n > 0) {
+ System.arraycopy(elems, index + 1, elems, index, n);
+ }
+ elems[--size] = null; // aid GC
}
@SkylarkCallable(
@@ -253,8 +339,8 @@
parameters = {@Param(name = "x", type = Object.class, doc = "The object to remove.")},
useLocation = true)
public NoneType removeObject(Object x, Location loc) throws EvalException {
- for (int i = 0; i < size(); i++) {
- if (get(i).equals(x)) {
+ for (int i = 0; i < size; i++) {
+ if (elems[i].equals(x)) {
remove(i, loc);
return Starlark.NONE;
}
@@ -272,7 +358,7 @@
*/
public void set(int index, E value, Location loc) throws EvalException {
checkMutable(loc);
- contents.set(index, value);
+ elems[index] = value;
}
@SkylarkCallable(
@@ -282,9 +368,9 @@
@Param(name = "item", type = Object.class, doc = "Item to add at the end.", noneable = true)
},
useLocation = true)
- @SuppressWarnings("unchecked") // Cast of Object item to E
+ @SuppressWarnings("unchecked")
public NoneType append(Object item, Location loc) throws EvalException {
- add((E) item, loc);
+ add((E) item, loc); // unchecked
return Starlark.NONE;
}
@@ -294,7 +380,8 @@
useLocation = true)
public NoneType clearMethod(Location loc) throws EvalException {
checkMutable(loc);
- contents.clear();
+ Arrays.fill(elems, null); // aid GC
+ size = 0;
return Starlark.NONE;
}
@@ -306,9 +393,9 @@
@Param(name = "item", type = Object.class, doc = "The item.", noneable = true)
},
useLocation = true)
- @SuppressWarnings("unchecked") // Cast of Object item to E
+ @SuppressWarnings("unchecked")
public NoneType insert(Integer index, Object item, Location loc) throws EvalException {
- add(EvalUtils.clampRangeEndpoint(index, size()), (E) item, loc);
+ add(EvalUtils.clampRangeEndpoint(index, size), (E) item, loc); // unchecked
return Starlark.NONE;
}
@@ -318,9 +405,11 @@
parameters = {@Param(name = "items", type = Object.class, doc = "Items to add at the end.")},
useLocation = true,
useStarlarkThread = true)
- @SuppressWarnings("unchecked")
public NoneType extend(Object items, Location loc, StarlarkThread thread) throws EvalException {
- addAll((Collection<? extends E>) EvalUtils.toCollection(items, loc, thread), loc);
+ @SuppressWarnings("unchecked")
+ Collection<? extends E> src =
+ (Collection<? extends E>) EvalUtils.toCollection(items, loc, thread);
+ addAll(src, loc);
return Starlark.NONE;
}
@@ -348,17 +437,12 @@
},
useLocation = true)
public Integer index(Object x, Object start, Object end, Location loc) throws EvalException {
- int i = start == Starlark.NONE ? 0 : EvalUtils.clampRangeEndpoint((Integer) start, this.size());
- int j =
- end == Starlark.NONE
- ? this.size()
- : EvalUtils.clampRangeEndpoint((Integer) end, this.size());
-
- while (i < j) {
- if (this.get(i).equals(x)) {
+ int i = start == Starlark.NONE ? 0 : EvalUtils.clampRangeEndpoint((Integer) start, size);
+ int j = end == Starlark.NONE ? size : EvalUtils.clampRangeEndpoint((Integer) end, size);
+ for (; i < j; i++) {
+ if (elems[i].equals(x)) {
return i;
}
- i++;
}
throw new EvalException(loc, Printer.format("item %r not found in list", x));
}
@@ -380,8 +464,8 @@
useLocation = true)
public Object pop(Object i, Location loc) throws EvalException {
int arg = i == Starlark.NONE ? -1 : (Integer) i;
- int index = EvalUtils.getSequenceIndex(arg, size(), loc);
- Object result = get(index);
+ int index = EvalUtils.getSequenceIndex(arg, size, loc);
+ Object result = elems[index];
remove(index, loc);
return result;
}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java b/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
index a468cae..fc190dd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
@@ -360,7 +360,7 @@
res.add(self.substring(start, end));
start = end + sep.length();
}
- return StarlarkList.wrapUnsafe(thread, res);
+ return StarlarkList.copyOf(thread.mutability(), res);
}
@SkylarkCallable(
@@ -410,7 +410,7 @@
end = start;
}
Collections.reverse(res);
- return StarlarkList.wrapUnsafe(thread, res);
+ return StarlarkList.copyOf(thread.mutability(), res);
}
@SkylarkCallable(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Tuple.java b/src/main/java/com/google/devtools/build/lib/syntax/Tuple.java
index ea2004c..dbee242 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Tuple.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Tuple.java
@@ -15,9 +15,16 @@
package com.google.devtools.build.lib.syntax;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.ObjectArrays;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
+import java.util.AbstractCollection;
+import java.util.AbstractList;
+import java.util.Arrays;
+import java.util.Iterator;
import java.util.List;
/**
@@ -41,62 +48,70 @@
+ "('a', 'b', 'c', 'd')[::2] # ('a', 'c')\n"
+ "('a', 'b', 'c', 'd')[3:0:-1] # ('d', 'c', 'b')</pre>"
+ "Tuples are immutable, therefore <code>x[1] = \"a\"</code> is not supported.")
-public final class Tuple<E> extends Sequence<E> {
+public final class Tuple<E> extends AbstractList<E> implements Sequence<E> {
- private final ImmutableList<E> contents;
+ private final Object[] elems;
- private Tuple(ImmutableList<E> contents) {
- this.contents = contents;
+ private Tuple(Object[] elems) {
+ this.elems = elems;
}
- /**
- * A shared instance for the empty tuple.
- *
- * <p>This instance should be the only empty tuple.
- */
- private static final Tuple<?> EMPTY = new Tuple<>(ImmutableList.of());
+ // The shared (sole) empty tuple.
+ private static final Tuple<?> EMPTY = new Tuple<>(new Object[0]);
/** Returns the empty tuple, cast to have an arbitrary content type. */
@SuppressWarnings("unchecked")
public static <T> Tuple<T> empty() {
- return (Tuple<T>) EMPTY;
+ return (Tuple<T>) EMPTY; // unchecked
}
/**
- * Creates a {@code Tuple} from an {@link ImmutableList}, reusing the empty instance if
- * applicable.
+ * Returns a Tuple that wraps the specified array, which must not be subsequently modified. The
+ * caller is additionally trusted to choose an appropriate type T.
*/
- private static <T> Tuple<T> create(ImmutableList<T> contents) {
- if (contents.isEmpty()) {
+ static <T> Tuple<T> wrap(Object[] array) {
+ return array.length == 0 ? empty() : new Tuple<T>(array);
+ }
+
+ /** Returns a tuple containing the given elements. */
+ @SuppressWarnings("unchecked")
+ public static <T> Tuple<T> copyOf(Iterable<? extends T> seq) {
+ if (seq instanceof Tuple) {
+ return (Tuple<T>) seq; // unchecked
+ }
+ return wrap(Iterables.toArray(seq, Object.class));
+ }
+
+ /** Returns a tuple containing the given elements. */
+ public static <T> Tuple<T> of(T... elems) {
+ if (elems.length == 0) {
return empty();
}
- return new Tuple<>(contents);
+ return new Tuple<T>(Arrays.copyOf(elems, elems.length));
}
- /** Returns a {@code Tuple} whose items are given by an iterable. */
- public static <T> Tuple<T> copyOf(Iterable<? extends T> contents) {
- return create(ImmutableList.<T>copyOf(contents));
+ /** Returns a two-element tuple. */
+ public static <T> Tuple<T> pair(T a, T b) {
+ // Equivalent to of(a, b) but avoids variadic array allocation.
+ return wrap(new Object[] {a, b});
}
- /**
- * Returns a {@code Tuple} whose items are given by an immutable list.
- *
- * <p>This method is a specialization of a {@link #copyOf(Iterable)} that avoids an unnecessary
- * {@code copyOf} invocation.
- */
- public static <T> Tuple<T> copyOf(ImmutableList<T> contents) {
- return create(contents);
+ /** Returns a three-element tuple. */
+ public static <T> Tuple<T> triple(T a, T b, T c) {
+ // Equivalent to of(a, b, c) but avoids variadic array allocation.
+ return wrap(new Object[] {a, b, c});
}
- /** Returns a {@code Tuple} with the given items. */
- public static <T> Tuple<T> of(T... elements) {
- return Tuple.create(ImmutableList.copyOf(elements));
+ /** Returns a tuple that is the concatenation of two tuples. */
+ public static <T> Tuple<T> concat(Tuple<? extends T> x, Tuple<? extends T> y) {
+ // TODO(adonovan): opt: exploit x + () == x; y + () == y.
+ return wrap(ObjectArrays.concat(x.elems, y.elems, Object.class));
}
@Override
public boolean isImmutable() {
- for (Object item : this) {
- if (!EvalUtils.isImmutable(item)) {
+ for (Object x : elems) {
+ if (!EvalUtils.isImmutable(x)) {
return false;
}
}
@@ -105,8 +120,8 @@
@Override
public boolean isHashable() {
- for (Object item : this) {
- if (!EvalUtils.isHashable(item)) {
+ for (Object x : elems) {
+ if (!EvalUtils.isHashable(x)) {
return false;
}
}
@@ -114,49 +129,109 @@
}
@Override
- public ImmutableList<E> getImmutableList() {
- return contents;
+ public int hashCode() {
+ return 9857 + 8167 * Arrays.hashCode(elems);
}
@Override
- protected List<E> getContentsUnsafe() {
- return contents;
+ public boolean equals(Object that) {
+ // This slightly violates the java.util.List equivalence contract
+ // because it considers the class, not just the elements.
+ return this == that
+ || (that instanceof Tuple && Arrays.equals(this.elems, ((Tuple) that).elems));
}
- /** Returns a {@code Tuple} that is the concatenation of two {@code Tuple}s. */
- public static <T> Tuple<T> concat(Tuple<? extends T> left, Tuple<? extends T> right) {
- // Build the ImmutableList directly rather than use Iterables.concat, to avoid unnecessary
- // array resizing.
- return create(
- ImmutableList.<T>builderWithExpectedSize(left.size() + right.size())
- .addAll(left)
- .addAll(right)
- .build());
+ @Override
+ @SuppressWarnings("unchecked")
+ public E get(int i) {
+ return (E) elems[i]; // unchecked
+ }
+
+ @Override
+ public int size() {
+ return elems.length;
+ }
+
+ @Override
+ public Tuple<E> subList(int from, int to) {
+ return wrap(Arrays.copyOfRange(elems, from, to));
+ }
+
+ @Override
+ public Object[] toArray() {
+ return Arrays.copyOf(elems, elems.length);
+ }
+
+ @Override
+ public void repr(SkylarkPrinter printer) {
+ // TODO(adonovan): when SkylarkPrinter moves into this package,
+ // inline and simplify this, the sole call with isTuple=true.
+ printer.printList(this, /*isTuple=*/ true);
+ }
+
+ // TODO(adonovan): SkylarkValue has 3 String methods yet still we need this fourth. Why?
+ @Override
+ public String toString() {
+ return Printer.repr(this);
+ }
+
+ @Override
+ public ImmutableList<E> getImmutableList() {
+ // Share the array with this (immutable) Tuple.
+ return wrapImmutable(elems);
+ }
+
+ /**
+ * Returns a new ImmutableList<T> backed by {@code array}, which must not be subsequently
+ * modified.
+ */
+ // TODO(adonovan): move this somewhere more appropriate.
+ static <T> ImmutableList<T> wrapImmutable(Object[] array) {
+ // Construct an ImmutableList that shares the array.
+ // ImmutableList relies on the implementation of Collection.toArray
+ // not subsequently modifying the returned array.
+ return ImmutableList.copyOf(
+ new AbstractCollection<T>() {
+ @Override
+ public Object[] toArray() {
+ return array;
+ }
+
+ @Override
+ public int size() {
+ return array.length;
+ }
+
+ @Override
+ public Iterator<T> iterator() {
+ throw new UnsupportedOperationException();
+ }
+ });
}
@Override
public Tuple<E> getSlice(
Object start, Object end, Object step, Location loc, Mutability mutability)
throws EvalException {
- List<Integer> sliceIndices = EvalUtils.getSliceIndices(start, end, step, this.size(), loc);
- ImmutableList.Builder<E> builder = ImmutableList.builderWithExpectedSize(sliceIndices.size());
- // foreach is not used to avoid iterator overhead
- for (int i = 0; i < sliceIndices.size(); ++i) {
- builder.add(this.get(sliceIndices.get(i)));
+ // TODO(adonovan): opt: this is horribly inefficient.
+ List<Integer> indices = EvalUtils.getSliceIndices(start, end, step, this.size(), loc);
+ Object[] res = new Object[indices.size()];
+ for (int i = 0; i < indices.size(); ++i) {
+ res[i] = elems[indices.get(i)];
}
- return copyOf(builder.build());
+ return wrap(res);
}
- @Override
- public Tuple<E> repeat(int times, Mutability mutability) {
- if (times <= 0) {
+ /** Returns a Tuple containing n consecutive repeats of this tuple. */
+ public Tuple<E> repeat(int n, Mutability mutability) {
+ if (n <= 0 || isEmpty()) {
return empty();
}
-
- ImmutableList.Builder<E> builder = ImmutableList.builderWithExpectedSize(this.size() * times);
- for (int i = 0; i < times; i++) {
- builder.addAll(this);
+ // TODO(adonovan): reject unreasonably large n.
+ Object[] res = new Object[n * elems.length];
+ for (int i = 0; i < n; i++) {
+ System.arraycopy(elems, 0, res, i * elems.length, elems.length);
}
- return copyOf(builder.build());
+ return wrap(res);
}
}
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
index 8732de1..ce8ef3c 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
@@ -284,16 +284,14 @@
}
@Test
- public void testWrapUnsafeTakesOwnershipOfPassedArrayList() throws EvalException {
- ArrayList<String> wrapped = Lists.newArrayList("hi");
+ public void testWrapTakesOwnershipOfArray() throws EvalException {
+ String[] wrapped = {"hello"};
Mutability mutability = Mutability.create("test");
- StarlarkList<String> mutableList = StarlarkList.wrapUnsafe(mutability, wrapped);
+ StarlarkList<String> mutableList = StarlarkList.wrap(mutability, wrapped);
// Big no-no, but we're proving a point.
- wrapped.add("added1");
- mutableList.add("added2", /*loc=*/ null);
- assertThat(wrapped).containsExactly("hi", "added1", "added2").inOrder();
- assertThat(mutableList).containsExactly("hi", "added1", "added2").inOrder();
+ wrapped[0] = "goodbye";
+ assertThat(mutableList).containsExactly("goodbye");
}
@Test
