bazel syntax: tweaks to list and tuple
...to address review comments on commit ccdeeda22778df438e5f26d87b5d7fe61cd63f04:
- tests of list.add and range
- move grow method to keep add overloads together
- in clear, zero only the live prefix of the array
- merge two cases in addAll
- tweaks for clarity in RangeList
PiperOrigin-RevId: 281091696
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 4a40253..edd38b3 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
@@ -91,7 +91,7 @@
if (index < 0 || index >= size()) {
throw new ArrayIndexOutOfBoundsException(index + ":" + this);
}
- return start + step * index;
+ return at(index);
}
@Override
@@ -152,13 +152,14 @@
throws EvalException {
Slice slice = Slice.from(size(), start, end, step, loc);
int substep = slice.step * this.step;
- // TODO(adonovan): why no bounds check here?
- int substart = getNoCheck(slice.start);
- int substop = getNoCheck(slice.stop);
+ // Unlike get, no bounds check is wanted here. Consider:
+ // range(1, 10, 2)[:99] == range(1, 11, 2).
+ int substart = at(slice.start);
+ int substop = at(slice.stop);
return new RangeList(substart, substop, substep);
}
- private int getNoCheck(int i) {
+ private int at(int i) {
return start + step * i;
}
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 d97d1a0..a85631f 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
@@ -48,8 +48,11 @@
+ "Lists are mutable, as in Python.")
public final class StarlarkList<E> extends AbstractList<E> implements Sequence<E>, StarlarkMutable {
+ // The implementation strategy is similar to ArrayList,
+ // but without the extra indirection of using ArrayList.
+
private int size;
- private Object[] elems = EMPTY_ARRAY;
+ private Object[] elems = EMPTY_ARRAY; // elems[i] == null iff i >= size
/** Final except for {@link #unsafeShallowFreeze}; must not be modified any other way. */
private Mutability mutability;
@@ -96,6 +99,11 @@
return (StarlarkList<T>) EMPTY;
}
+ /** Returns a new, empty list with the specified Mutability. */
+ public static <T> StarlarkList<T> newList(Mutability mutability) {
+ return wrap(mutability, EMPTY_ARRAY);
+ }
+
/**
* Returns a {@code StarlarkList} whose items are given by an iterable and which has the given
* {@link Mutability}. If {@code mutability} is null, the list is immutable.
@@ -238,18 +246,6 @@
return wrap(mutability, array);
}
- /**
- * Appends an element to the end of the list, after validating that mutation is allowed.
- *
- * @param element the element to add
- * @param loc the location to use for error reporting
- */
- public void add(E element, Location loc) throws EvalException {
- checkMutable(loc);
- grow(size + 1);
- elems[size++] = element;
- }
-
// Postcondition: elems.length >= mincap.
private void grow(int mincap) {
int oldcap = elems.length;
@@ -263,6 +259,18 @@
}
/**
+ * Appends an element to the end of the list, after validating that mutation is allowed.
+ *
+ * @param element the element to add
+ * @param loc the location to use for error reporting
+ */
+ public void add(E element, Location loc) throws EvalException {
+ checkMutable(loc);
+ grow(size + 1);
+ elems[size++] = element;
+ }
+
+ /**
* Inserts an element at a given position to the list.
*
* @param index the new element's index
@@ -286,24 +294,16 @@
public void addAll(Iterable<? extends E> elements, Location loc) throws EvalException {
checkMutable(loc);
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;
- }
+ StarlarkList<?> that = (StarlarkList) elements;
+ // (safe even if this == that)
+ grow(this.size + that.size);
+ System.arraycopy(that.elems, 0, this.elems, this.size, that.size);
+ this.size += that.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) {
+ Collection<?> that = (Collection) elements;
+ grow(size + that.size());
+ for (Object x : that) {
elems[size++] = x;
}
} else {
@@ -380,7 +380,9 @@
useLocation = true)
public NoneType clearMethod(Location loc) throws EvalException {
checkMutable(loc);
- Arrays.fill(elems, null); // aid GC
+ for (int i = 0; i < size; i++) {
+ elems[i] = null; // aid GC
+ }
size = 0;
return Starlark.NONE;
}
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
index 4459d1d..b289aa1 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
@@ -516,7 +516,11 @@
.testExpression("4 in range(0, 8, 2)", true)
.testExpression("4 in range(1, 8, 2)", false)
.testExpression("range(0, 5, 10) == range(0, 5, 11)", true)
- .testExpression("range(0, 5, 2) == [0, 2, 4]", false);
+ .testExpression("range(0, 5, 2) == [0, 2, 4]", false)
+ .testExpression("str(list(range(1, 10, 2)))", "[1, 3, 5, 7, 9]")
+ .testExpression("str(range(1, 10, 2)[:99])", "range(1, 11, 2)")
+ .testExpression("range(1, 10, 2) == range(1, 11, 2)", true)
+ .testExpression("range(1, 10, 2) == range(1, 12, 2)", false);
}
@Test
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 ce8ef3c..a404505 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
@@ -237,6 +237,25 @@
}
@Test
+ public void testListAddWithIndex() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ StarlarkList<String> list = StarlarkList.newList(mutability);
+ Location loc = null;
+ list.add("a", loc);
+ list.add("b", loc);
+ list.add("c", loc);
+ list.add(0, "d", loc);
+ assertThat(list.toString()).isEqualTo("[\"d\", \"a\", \"b\", \"c\"]");
+ list.add(2, "e", loc);
+ assertThat(list.toString()).isEqualTo("[\"d\", \"a\", \"e\", \"b\", \"c\"]");
+ list.add(4, "f", loc);
+ assertThat(list.toString()).isEqualTo("[\"d\", \"a\", \"e\", \"b\", \"f\", \"c\"]");
+ list.add(6, "g", loc);
+ assertThat(list.toString()).isEqualTo("[\"d\", \"a\", \"e\", \"b\", \"f\", \"c\", \"g\"]");
+ assertThrows(ArrayIndexOutOfBoundsException.class, () -> list.add(8, "h", loc));
+ }
+
+ @Test
public void testMutatorsCheckMutability() throws Exception {
Mutability mutability = Mutability.create("test");
StarlarkList<Object> list = StarlarkList.copyOf(mutability, ImmutableList.of(1, 2, 3));