Optimize trusted MutableList construction

Cuts back a lot of unnecessary copying. All construction is funneled through copyOf and
wrapUnsafe. copyOf is the traditional construction mechanism, taking defensive copies of
the input and determining if GlobList information needs to be retained. wrapUnsafe takes
full ownership of the supplied ArrayList, allowing us to skip a lot of copies in trusted
situations. This is particularly useful for common built in functions which return a list,
range() being one common example.

RELNOTES: None
PiperOrigin-RevId: 172361367

4 files changed, 121 insertions, 109 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
index 26bf96b1e9..a8d338acc2 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
@@ -98,7 +98,7 @@ public final class ListLiteral extends Expression {
 
   @Override
   Object doEval(Environment env) throws EvalException, InterruptedException {
-    List<Object> result = new ArrayList<>(elements.size());
+    ArrayList<Object> result = new ArrayList<>(elements.size());
     for (Expression element : elements) {
       // Convert NPEs to EvalExceptions.
       if (element == null) {
@@ -106,7 +106,7 @@ public final class ListLiteral extends Expression {
       }
       result.add(element.eval(env));
     }
-    return isTuple() ? Tuple.copyOf(result) : MutableList.copyOf(env, result);
+    return isTuple() ? Tuple.copyOf(result) : MutableList.wrapUnsafe(env, result);
   }
 
   @Override
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 7b421fe453..b0dc7e4abd 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
@@ -1517,11 +1517,11 @@ public class MethodLibrary {
   private static final BuiltinFunction items =
       new BuiltinFunction("items") {
         public MutableList<?> invoke(SkylarkDict<?, ?> self, Environment env) throws EvalException {
-          List<Object> list = Lists.newArrayListWithCapacity(self.size());
+          ArrayList<Object> list = Lists.newArrayListWithCapacity(self.size());
           for (Map.Entry<?, ?> entries : self.entrySet()) {
             list.add(Tuple.of(entries.getKey(), entries.getValue()));
           }
-          return MutableList.copyOf(env, list);
+          return MutableList.wrapUnsafe(env, list);
         }
       };
 
@@ -1539,11 +1539,11 @@ public class MethodLibrary {
     @SuppressWarnings("unchecked")
     public MutableList<?> invoke(SkylarkDict<?, ?> self,
         Environment env) throws EvalException {
-      List<Object> list = Lists.newArrayListWithCapacity(self.size());
+      ArrayList<Object> list = Lists.newArrayListWithCapacity(self.size());
       for (Map.Entry<?, ?> entries : self.entrySet()) {
         list.add(entries.getKey());
       }
-      return MutableList.copyOf(env, list);
+      return MutableList.wrapUnsafe(env, list);
     }
   };
 
@@ -1863,12 +1863,12 @@ public class MethodLibrary {
       new BuiltinFunction("enumerate") {
         public MutableList<?> invoke(SkylarkList<?> input, Environment env) throws EvalException {
           int count = 0;
-          List<SkylarkList<?>> result = Lists.newArrayList();
+          ArrayList<SkylarkList<?>> result = new ArrayList<>(input.size());
           for (Object obj : input) {
             result.add(Tuple.of(count, obj));
             count++;
           }
-          return MutableList.copyOf(env, result);
+          return MutableList.wrapUnsafe(env, result);
         }
       };
 
@@ -1946,23 +1946,19 @@ public class MethodLibrary {
           if (step == 0) {
             throw new EvalException(loc, "step cannot be 0");
           }
-          ArrayList<Integer> result = Lists.newArrayList();
+          ArrayList<Integer> result = new ArrayList<>(Math.abs((stop - start) / step));
           if (step > 0) {
-            int size = (stop - start) / step;
-            result.ensureCapacity(size);
             while (start < stop) {
               result.add(start);
               start += step;
             }
           } else {
-            int size = (start - stop) / step;
-            result.ensureCapacity(size);
             while (start > stop) {
               result.add(start);
               start += step;
             }
           }
-          return MutableList.copyOf(env, result);
+          return MutableList.wrapUnsafe(env, result);
         }
       };
 
@@ -2184,7 +2180,7 @@ public class MethodLibrary {
           for (int i = 0; i < args.size(); i++) {
             iterators[i] = EvalUtils.toIterable(args.get(i), loc, env).iterator();
           }
-          List<Tuple<?>> result = new ArrayList<>();
+          ArrayList<Tuple<?>> result = new ArrayList<>();
           boolean allHasNext;
           do {
             allHasNext = !args.isEmpty();
@@ -2200,7 +2196,7 @@ public class MethodLibrary {
               result.add(Tuple.copyOf(elem));
             }
           } while (allHasNext);
-          return MutableList.copyOf(env, result);
+          return MutableList.wrapUnsafe(env, result);
         }
       };
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
index 56d078c5fa..382e34a9de 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
@@ -16,13 +16,14 @@ package com.google.devtools.build.lib.syntax;
 
 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.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.syntax.SkylarkMutable.BaseMutableList;
+import com.google.devtools.build.lib.util.Preconditions;
 import java.util.ArrayList;
-import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.RandomAccess;
@@ -76,24 +77,6 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
   }
 
   /**
-   * Constructs an {@link ImmutableList} containing the items in a slice of the given {@code
-   * SkylarkList}.
-   *
-   * @see EvalUtils#getSliceIndices
-   * @throws EvalException if the key is invalid; uses {@code loc} for error reporting
-   */
-  protected static <T> ImmutableList<T> getSliceContents(
-      SkylarkList<T> list, Object start, Object end, Object step, Location loc)
-      throws EvalException {
-    int length = list.size();
-    ImmutableList.Builder<T> items = ImmutableList.builder();
-    for (int pos : EvalUtils.getSliceIndices(start, end, step, length, loc)) {
-      items.add(list.get(pos));
-    }
-    return items.build();
-  }
-
-  /**
    * Constructs a version of this {@code SkylarkList} containing just the items in a slice.
    *
    * <p>{@code mutability} will be used for the resulting list. If it is null, the list will be
@@ -107,22 +90,6 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
       throws EvalException;
 
   /**
-   * Constructs an {@link ImmutableList} containing the items in a repetition of the given {@code
-   * SkylarkList}.
-   *
-   * <p>A repetition is produced by concatenating the list with itself {@code times - 1} many times.
-   * If {@code times} is 1, the new list's contents are the same as the original list. If {@code
-   * times} is <= 0, an empty list is returned.
-   */
-  public static <T> ImmutableList<T> repeatContents(SkylarkList<? extends T> list, int times) {
-    ImmutableList.Builder<T> builder = ImmutableList.builder();
-    for (int i = 0; i < times; i++) {
-      builder.addAll(list);
-    }
-    return builder.build();
-  }
-
-  /**
    * Constructs a repetition of this {@code SkylarkList}.
    *
    * <p>{@code mutability} will be used for the resulting list. If it is null, the list will be
@@ -227,7 +194,7 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
   // Environment. That in turn would allow us to overload MutableList#of to take either a Mutability
   // or Environment.
   public static <E> SkylarkList<E> createImmutable(Iterable<? extends E> contents) {
-    return new MutableList<>(contents, Mutability.IMMUTABLE);
+    return MutableList.copyOf(Mutability.IMMUTABLE, contents);
   }
 
   /**
@@ -253,7 +220,7 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
   )
   public static final class MutableList<E> extends SkylarkList<E> {
 
-    private final ArrayList<E> contents = new ArrayList<>();
+    private final ArrayList<E> contents;
 
     // Treat GlobList specially: external code depends on it.
     // TODO(bazel-team): make data structures *and binary operators* extensible
@@ -264,30 +231,34 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
 
     private final Mutability mutability;
 
-    /**
-     * Constructs from the given items and {@link Mutability}.
-     *
-     * @param contents the contents of the new list. If this is a {@link GlobList}, it is also
-     *     stored in {@code globList}.
-     * @param capacity an size to pre-allocate the array to. Use 0 if unsure. This is unnecessary if
-     *     {@code contents} is a {@link Collection}.
-     * @param mutability the {@code Mutability} to use for the new list. If null, the new list is
-     *     immutable.
-     */
-    // Suppress warning for cast guarded by instanceof.
-    @SuppressWarnings("unchecked")
     private MutableList(
-        Iterable<? extends E> contents, int capacity, @Nullable Mutability mutability) {
-      this.contents.ensureCapacity(capacity);
-      addAllUnsafe(contents);
-      if (contents instanceof GlobList) {
-        globList = (GlobList<E>) contents;
-      }
+        ArrayList<E> rawContents,
+        @Nullable GlobList<E> globList,
+        @Nullable Mutability mutability) {
+      this.contents = Preconditions.checkNotNull(rawContents);
+      this.globList = globList;
       this.mutability = mutability == null ? Mutability.IMMUTABLE : mutability;
     }
 
-    private MutableList(Iterable<? extends E> contents, @Nullable Mutability mutability) {
-      this(contents, /*capacity=*/ 0, mutability);
+    /**
+     * Creates an instance, taking ownership of the supplied {@link ArrayList}. This is exposed for
+     * performance reasons. May be used when the supplied list is certainly not a {@link GlobList}
+     * (should be enforced by type system) and the calling code will not modify the supplied list
+     * after calling (honor system).
+     */
+    static <T> MutableList<T> wrapUnsafe(@Nullable Environment env, ArrayList<T> rawContents) {
+      return wrapUnsafe(env == null ? null : env.mutability(), rawContents);
+    }
+
+    /**
+     * Create an instance, taking ownership of the supplied {@link ArrayList}. This is exposed for
+     * performance reasons. May be used when the supplied list is certainly not a {@link GlobList}
+     * (enforced by type system as long as {@link GlobList} doesn't extend {@link ArrayList}) and
+     * the calling code will not modify the supplied list after calling (honor system).
+     */
+    static <T> MutableList<T> wrapUnsafe(
+        @Nullable Mutability mutability, ArrayList<T> rawContents) {
+      return new MutableList<>(rawContents, /*globList=*/ null, mutability);
     }
 
     /**
@@ -298,7 +269,7 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
      * the beginning.
      */
     private static final MutableList<?> EMPTY =
-        new MutableList<>(ImmutableList.of(), Mutability.IMMUTABLE);
+        MutableList.copyOf(Mutability.IMMUTABLE, ImmutableList.of());
 
     /** Returns an empty frozen list, cast to have an arbitrary content type. */
     @SuppressWarnings("unchecked")
@@ -310,9 +281,13 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
      * Returns a {@code MutableList} whose items are given by an iterable and which has the given
      * {@link Mutability}. If {@code mutability} is null, the list is immutable.
      */
+    @SuppressWarnings("unchecked")  // GlobList cast.
     public static <T> MutableList<T> copyOf(
         @Nullable Mutability mutability, Iterable<? extends T> contents) {
-      return new MutableList<>(contents, mutability);
+      return new MutableList<>(
+          Lists.newArrayList(contents),
+          contents instanceof GlobList ? (GlobList<T>) contents : null,
+          mutability);
     }
 
     /**
@@ -322,7 +297,9 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
      */
     public static <T> MutableList<T> copyOf(
         @Nullable Environment env, Iterable<? extends T> contents) {
-      return new MutableList<>(contents, env == null ? null : env.mutability());
+      return MutableList.copyOf(
+          env == null ? null : env.mutability(),
+          contents);
     }
 
     /**
@@ -330,15 +307,10 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
      * {@link Environment}. If {@code env} is null, the list is immutable.
      */
     public static <T> MutableList<T> of(@Nullable Environment env, T... contents) {
-      return new MutableList<>(
-          ImmutableList.copyOf(contents), env == null ? null : env.mutability());
-    }
-
-    /**
-     * Appends the given elements to the end of the list, without calling {@link #checkMutable}.
-     */
-    private void addAllUnsafe(Iterable<? extends E> elements) {
-      Iterables.addAll(contents, elements);
+      // Safe since it's definitely not a GlobList, and we're taking a copy of the input.
+      return MutableList.wrapUnsafe(
+          env == null ? null : env.mutability(),
+          Lists.newArrayList(contents));
     }
 
     @Override
@@ -386,36 +358,39 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
         MutableList<? extends T> right,
         Mutability mutability) {
       if (left.getGlobList() == null && right.getGlobList() == null) {
-        return new MutableList<>(
-            Iterables.concat(left, right),
-            left.size() + right.size(),
-            mutability);
+        ArrayList<T> newContents = new ArrayList<>(left.size() + right.size());
+        newContents.addAll(left);
+        newContents.addAll(right);
+        return new MutableList<>(newContents, /*globList=*/ null, mutability);
       } else {
         // Preserve glob criteria.
-        return new MutableList<>(
-            GlobList.concat(
-                left.getGlobListOrContentsUnsafe(),
-                right.getGlobListOrContentsUnsafe()),
-            mutability);
+        GlobList<T> newGlobList = GlobList.concat(
+            left.getGlobListOrContentsUnsafe(),
+            right.getGlobListOrContentsUnsafe());
+        return new MutableList<>(new ArrayList<>(newGlobList), newGlobList, mutability);
       }
     }
 
     @Override
     public MutableList<E> repeat(int times, Mutability mutability) {
+      if (times <= 0) {
+        return MutableList.wrapUnsafe(mutability, new ArrayList<>());
+      }
+
       if (getGlobList() == null) {
-        return new MutableList<>(repeatContents(this, times), mutability);
+        ArrayList<E> repeated = new ArrayList<>(this.size() * times);
+        for (int i = 0; i < times; i++) {
+          repeated.addAll(this);
+        }
+        return MutableList.wrapUnsafe(mutability, repeated);
       } else {
-        if (times <= 0) {
-          return new MutableList<>(ImmutableList.of(), mutability);
-        } else {
-          // Preserve glob criteria.
-          List<? extends E> globs = getGlobListOrContentsUnsafe();
-          List<? extends E> original = globs;
-          for (int i = 1; i < times; i++) {
-            globs = GlobList.concat(globs, original);
-          }
-          return new MutableList<>(globs, mutability);
+        // Preserve glob criteria.
+        List<? extends E> globs = getGlobListOrContentsUnsafe();
+        List<? extends E> original = globs;
+        for (int i = 1; i < times; i++) {
+          globs = GlobList.concat(globs, original);
         }
+        return MutableList.copyOf(mutability, globs);
       }
     }
 
@@ -423,7 +398,12 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
     public MutableList<E> getSlice(
         Object start, Object end, Object step, Location loc, Mutability mutability)
         throws EvalException {
-      return new MutableList<>(getSliceContents(this, start, end, step, loc), mutability);
+      List<Integer> sliceIndices = EvalUtils.getSliceIndices(start, end, step, this.size(), loc);
+      ArrayList<E> list = new ArrayList<>(sliceIndices.size());
+      for (int pos : sliceIndices) {
+        list.add(this.get(pos));
+      }
+      return MutableList.wrapUnsafe(mutability, list);
     }
 
     /**
@@ -462,7 +442,7 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
     public void addAll(Iterable<? extends E> elements, Location loc, Mutability mutability)
         throws EvalException {
       checkMutable(loc, mutability);
-      addAllUnsafe(elements);
+      Iterables.addAll(contents, elements);
     }
 
     /**
@@ -601,12 +581,21 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
     public Tuple<E> getSlice(
         Object start, Object end, Object step, Location loc, Mutability mutability)
         throws EvalException {
-      return copyOf(getSliceContents(this, start, end, step, loc));
+      List<Integer> sliceIndices = EvalUtils.getSliceIndices(start, end, step, this.size(), loc);
+      ImmutableList.Builder<E> builder = ImmutableList.builder();
+      for (int pos : sliceIndices) {
+        builder.add(this.get(pos));
+      }
+      return copyOf(builder.build());
     }
 
     @Override
     public Tuple<E> repeat(int times, Mutability mutability) {
-      return copyOf(repeatContents(this, times));
+      ImmutableList.Builder<E> builder = ImmutableList.builder();
+      for (int i = 0; i < times; i++) {
+        builder.addAll(this);
+      }
+      return copyOf(builder.build());
     }
   }
 }
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 98695c56e0..b2768390da 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
@@ -17,9 +17,11 @@ import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
+import java.util.ArrayList;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -275,4 +277,29 @@ public class SkylarkListTest extends EvaluationTestCase {
       assertThat(e).hasMessage("trying to mutate a frozen object");
     }
   }
+
+  @Test
+  public void testCopyOfTakesCopy() throws EvalException {
+    ArrayList<String> copyFrom = Lists.newArrayList("hi");
+    Mutability mutability = Mutability.create("test");
+    MutableList<String> mutableList = MutableList.copyOf(mutability, copyFrom);
+    copyFrom.add("added1");
+    mutableList.add("added2", /*loc=*/ null, mutability);
+
+    assertThat(copyFrom).containsExactly("hi", "added1").inOrder();
+    assertThat(mutableList).containsExactly("hi", "added2").inOrder();
+  }
+
+  @Test
+  public void testWrapUnsafeTakesOwnershipOfPassedArrayList() throws EvalException {
+    ArrayList<String> wrapped = Lists.newArrayList("hi");
+    Mutability mutability = Mutability.create("test");
+    MutableList<String> mutableList = MutableList.wrapUnsafe(mutability, wrapped);
+
+    // Big no-no, but we're proving a point.
+    wrapped.add("added1");
+    mutableList.add("added2", /*loc=*/ null, mutability);
+    assertThat(wrapped).containsExactly("hi", "added1", "added2").inOrder();
+    assertThat(mutableList).containsExactly("hi", "added1", "added2").inOrder();
+  }
 }