Make SkylarkList a List.

SkylarkList now implements the List interfaces, except that its mutating methods
throw an UnsupportedOperationException, just like ImmutableList does.
To actually mutate a SkylarkList, you need to pass a Location and a suitable
Environment object with a matching Mutability while it is still active.

Introduce SkylarkMutable and SkylarkMutable.MutableCollection to better handle
mutable data structures.

Remove some functions in EvalUtils made obsolete by this and previous changes regarding Skylark lists.

--
MOS_MIGRATED_REVID=112768457

9 files changed, 333 insertions, 156 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index 8676c36a4a..fc1fe9afbb 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -454,19 +454,11 @@ public final class BinaryOperatorExpression extends Expression {
 
     // string % tuple, string % dict, string % anything-else
     if (lval instanceof String) {
+      String pattern = (String) lval;
       try {
-        String pattern = (String) lval;
-        if (rval instanceof List<?>) {
-          List<?> rlist = (List<?>) rval;
-          if (EvalUtils.isTuple(rlist)) {
-            return Printer.formatToString(pattern, rlist);
-          }
-          /* string % list: fall thru */
-        }
         if (rval instanceof Tuple) {
-          return Printer.formatToString(pattern, ((Tuple) rval).getList());
+          return Printer.formatToString(pattern, (Tuple) rval);
         }
-
         return Printer.formatToString(pattern, Collections.singletonList(rval));
       } catch (IllegalFormatException e) {
         throw new EvalException(location, e.getMessage());
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 b3b1d9ee5a..0d001d3016 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
@@ -23,6 +23,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -93,28 +94,6 @@ public final class EvalUtils {
     }
   };
 
-  /**
-   * @return true if the specified sequence is a tuple; false if it's a modifiable list.
-   */
-  public static boolean isTuple(List<?> l) {
-    return isTuple(l.getClass());
-  }
-
-  public static boolean isTuple(Class<?> c) {
-    Preconditions.checkState(List.class.isAssignableFrom(c));
-    return ImmutableList.class.isAssignableFrom(c);
-  }
-
-  public static boolean isTuple(Object o) {
-    if (o instanceof SkylarkList) {
-      return ((SkylarkList) o).isTuple(); // tuples are immutable, lists are not.
-    }
-    if (o instanceof List<?>) {
-      return isTuple(o.getClass());
-    }
-    return false;
-  }
-
   public static final StackManipulation checkValidDictKey =
       ByteCodeUtils.invoke(EvalUtils.class, "checkValidDictKey", Object.class);
 
@@ -137,22 +116,24 @@ public final class EvalUtils {
    * @param o an Object
    * @return true if the object is known to be an immutable value.
    */
+  // NB: This is used as the basis for accepting objects in SkylarkNestedSet-s,
+  // as well as for accepting objects as keys for Skylark dict-s.
   public static boolean isImmutable(Object o) {
-    if (o instanceof SkylarkValue) {
-      return ((SkylarkValue) o).isImmutable();
-    }
-    if (!(o instanceof List<?>)) {
-      return isImmutable(o.getClass());
+    if (o instanceof Tuple) {
+      for (Object item : (Tuple) o) {
+        if (!isImmutable(item)) {
+          return false;
+        }
+      }
+      return true;
     }
-    if (!isTuple((List<?>) o)) {
+    if (o instanceof SkylarkMutable) {
       return false;
     }
-    for (Object item : (List<?>) o) {
-      if (!isImmutable(item)) {
-        return false;
-      }
+    if (o instanceof SkylarkValue) {
+      return ((SkylarkValue) o).isImmutable();
     }
-    return true;
+    return isImmutable(o.getClass());
   }
 
   /**
@@ -224,7 +205,9 @@ public final class EvalUtils {
    * @return a super-class of c to be used in validation-time type inference.
    */
   public static Class<?> getSkylarkType(Class<?> c) {
-    if (ImmutableList.class.isAssignableFrom(c)) {
+    if (SkylarkList.class.isAssignableFrom(c)) {
+      return c;
+    } else if (ImmutableList.class.isAssignableFrom(c)) {
       return ImmutableList.class;
     } else if (List.class.isAssignableFrom(c)) {
       return List.class;
@@ -260,24 +243,19 @@ public final class EvalUtils {
    * Returns a pretty name for the datatype of object {@code object} in Skylark
    * or the BUILD language, with full details if the {@code full} boolean is true.
    */
-  public static String getDataTypeName(Object object, boolean full) {
+  public static String getDataTypeName(Object object, boolean fullDetails) {
     Preconditions.checkNotNull(object);
-    if (object instanceof SkylarkList) {
-      SkylarkList list = (SkylarkList) object;
-      if (list.isTuple()) {
-        return "tuple";
-      } else {
-        return "list";
+    if (fullDetails) {
+      if (object instanceof SkylarkNestedSet) {
+        SkylarkNestedSet set = (SkylarkNestedSet) object;
+        return "set of " + set.getContentType() + "s";
+      }
+      if (object instanceof SelectorList) {
+        SelectorList list = (SelectorList) object;
+        return "select of " + getDataTypeNameFromClass(list.getType());
       }
-    } else if (object instanceof SkylarkNestedSet) {
-      SkylarkNestedSet set = (SkylarkNestedSet) object;
-      return "set" + (full ? " of " + set.getContentType() + "s" : "");
-    } else if (object instanceof SelectorList) {
-      SelectorList list = (SelectorList) object;
-      return "select" + (full ? " of " + getDataTypeNameFromClass(list.getType()) : "");
-    } else {
-      return getDataTypeNameFromClass(object.getClass());
     }
+    return getDataTypeNameFromClass(object.getClass());
   }
 
   /**
@@ -305,11 +283,6 @@ public final class EvalUtils {
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (List.class.isAssignableFrom(c)) {
-      // NB: the capital here is a subtle way to distinguish java List and Tuple (ImmutableList)
-      // from native SkylarkList list and tuple.
-      // TODO(bazel-team): use SkylarkList everywhere instead of java List.
-      return isTuple(c) ? "Tuple" : "List";
     } else if (Map.class.isAssignableFrom(c)) {
       return "dict";
     } else if (BaseFunction.class.isAssignableFrom(c)) {
@@ -330,13 +303,6 @@ public final class EvalUtils {
     }
   }
 
-  /**
-   * Returns a sequence of the appropriate list/tuple datatype for 'seq', based on 'isTuple'.
-   */
-  public static List<?> makeSequence(List<?> seq, boolean isTuple) {
-    return isTuple ? ImmutableList.copyOf(seq) : seq;
-  }
-
   public static Object checkNotNull(Expression expr, Object obj) throws EvalException {
     if (obj == null) {
       throw new EvalException(expr.getLocation(),
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 08455bdc84..b552c1108d 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
@@ -981,7 +981,7 @@ public class MethodLibrary {
             MutableList self, Object start, Object end, Integer step, Location loc,
             Environment env)
             throws EvalException, ConversionException {
-          return new MutableList(sliceList(self.getList(), start, end, step, loc), env);
+          return new MutableList(sliceList(self, start, end, step, loc), env);
         }
       };
 
@@ -1008,7 +1008,7 @@ public class MethodLibrary {
         @SuppressWarnings("unused") // Accessed via Reflection.
         public Tuple invoke(Tuple self, Object start, Object end, Integer step, Location loc)
             throws EvalException, ConversionException {
-          return Tuple.copyOf(sliceList(self.getList(), start, end, step, loc));
+          return Tuple.copyOf(sliceList(self, start, end, step, loc));
         }
       };
 
@@ -1407,7 +1407,7 @@ public class MethodLibrary {
             throw new EvalException(loc, "List is empty");
           }
           int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.getList().get(index), env);
+          return SkylarkType.convertToSkylark(self.get(index), env);
         }
       };
 
@@ -1432,7 +1432,7 @@ public class MethodLibrary {
             throw new EvalException(loc, "tuple is empty");
           }
           int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.getList().get(index), env);
+          return SkylarkType.convertToSkylark(self.get(index), env);
         }
       };
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
index 98a483b8ba..88abe13756 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
@@ -143,7 +143,7 @@ public final class Printer {
 
     } else if (o instanceof List<?>) {
       List<?> seq = (List<?>) o;
-      printList(buffer, seq, EvalUtils.isTuple(seq), quotationMark);
+      printList(buffer, seq, false, quotationMark);
 
     } else if (o instanceof Map<?, ?>) {
       Map<?, ?> dict = (Map<?, ?>) o;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 09d0abd9c6..b24e188f9c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -141,16 +141,19 @@ public final class Runtime {
    * <p>Currently, this is only necessary for mapping the different subclasses of {@link
    * java.util.Map} to the interface.
    */
+  // TODO(bazel-team): make everything a SkylarkValue, and remove this function.
   public static Class<?> getCanonicalRepresentation(Class<?> clazz) {
+    if (SkylarkValue.class.isAssignableFrom(clazz)) {
+      return clazz;
+    }
     if (Map.class.isAssignableFrom(clazz)) {
       return MethodLibrary.DictModule.class;
     }
     if (String.class.isAssignableFrom(clazz)) {
       return MethodLibrary.StringModule.class;
     }
-    if (List.class.isAssignableFrom(clazz)) {
-      return List.class;
-    }
+    Preconditions.checkArgument(
+        !List.class.isAssignableFrom(clazz), "invalid non-SkylarkList list class");
     return clazz;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
index 4d76524fe8..0feb423453 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
@@ -13,9 +13,10 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -37,7 +38,10 @@ import java.util.List;
  *   )
  * </pre>
  */
-public final class SelectorList {
+@SkylarkModule(name = "select",
+    doc = "A selector between configuration-dependent entities.",
+    documented = false)
+public final class SelectorList implements SkylarkValue {
   // TODO(build-team): Selectors are currently split between .packages and .syntax . They should
   // really all be in .packages, but then we'd need to figure out a way how to extend binary
   // operators, which is a non-trivial problem.
@@ -129,6 +133,16 @@ public final class SelectorList {
 
   @Override
   public String toString() {
-    return Joiner.on(" + ").join(elements);
+    return Printer.repr(this);
+  }
+
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.printList(buffer, elements, "", " + ", "", null, quotationMark);
+  }
+
+  @Override
+  public boolean isImmutable() {
+    return false;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
index d4c9366bfa..e9dcb1dbcd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
@@ -15,6 +15,9 @@ package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import java.util.Map;
 import java.util.TreeMap;
@@ -31,7 +34,10 @@ import java.util.TreeMap;
  *       })
  * </pre>
  */
-public final class SelectorValue {
+@SkylarkModule(name = "selector",
+    doc = "A selector between configuration-dependent entities.",
+    documented = false)
+public final class SelectorValue implements SkylarkValue {
   // TODO(bazel-team): Selectors are currently split between .packages and .syntax . They should
   // really all be in .packages, but then we'd need to figure out a way how to extend binary
   // operators, which is a non-trivial problem.
@@ -58,6 +64,16 @@ public final class SelectorValue {
 
   @Override
   public String toString() {
-    return "selector({...})";
+    return Printer.repr(this);
+  }
+
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.formatTo(buffer, "selector(%r)", Tuple.of(dictionary));
+  }
+
+  @Override
+  public boolean isImmutable() {
+    return false;
   }
 }
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 5c66f81dd1..fddebba162 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
@@ -19,14 +19,14 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
-import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
-import com.google.devtools.build.lib.syntax.Mutability.Freezable;
-import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
+import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableCollection;
 
 import java.util.ArrayList;
+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;
 
@@ -35,13 +35,8 @@ import javax.annotation.Nullable;
  */
 @SkylarkModule(name = "sequence", documented = false,
     doc = "common type of lists and tuples")
-public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
-
-  /**
-   * Returns the List object underlying this SkylarkList.
-   * Mutating it (if mutable) will actually mutate the contents of the list.
-   */
-  protected abstract List<Object> getList();
+  public abstract class SkylarkList
+    extends MutableCollection<Object> implements List<Object>, RandomAccess {
 
   /**
    * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
@@ -50,64 +45,104 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
 
   /**
    * Returns a List object with the current underlying contents of this SkylarkList.
-   * This object must not be modified, but may not be an ImmutableList.
-   * It may notably be a GlobList, where appropriate.
+   * This object must not be mutated, but need not be an {@link ImmutableList}.
+   * Indeed it can sometimes be a {@link GlobList}.
    */
-  // TODO(bazel-team): move GlobList out of Skylark, into an extension,
-  // and maybe get rid of this method?
-  protected abstract List<Object> getContents();
+  // TODO(bazel-team): move GlobList out of Skylark, into an extension.
+  @Override
+  public abstract List<Object> getContents();
 
   /**
-   * Returns true if this list is a tuple.
+   * The underlying contents are a (usually) mutable data structure.
+   * Read access is forwarded to these contents.
+   * This object must not be modified outside an {@link Environment}
+   * with a correct matching {@link Mutability},
+   * which should be checked beforehand using {@link #checkMutable}.
+   * it need not be an instance of {@link com.google.common.collect.ImmutableList}.
    */
-  public abstract boolean isTuple();
+  @Override
+  protected abstract List<Object> getContentsUnsafe();
 
   /**
-   * The size of the list.
+   * Returns true if this list is a tuple.
    */
-  public final int size() {
-    return getList().size();
+  public abstract boolean isTuple();
+
+  // A SkylarkList forwards all read-only access to the getContentsUnsafe().
+  @Override
+  public final Object get(int i) {
+    return getContentsUnsafe().get(i);
   }
 
-  /**
-   * Returns true if the list is empty.
-   */
-  public final boolean isEmpty() {
-    return getList().isEmpty();
+  @Override
+  public int indexOf(Object element) {
+    return getContentsUnsafe().indexOf(element);
   }
 
-  /**
-   * Returns the i-th element of the list.
-   */
-  public final Object get(int i) {
-    return getList().get(i);
+  @Override
+  public int lastIndexOf(Object element) {
+    return getContentsUnsafe().lastIndexOf(element);
   }
 
   @Override
-  public void write(Appendable buffer, char quotationMark) {
-    Printer.printList(buffer, getList(), isTuple(), quotationMark);
+  public ListIterator<Object> listIterator() {
+    return getContentsUnsafe().listIterator();
+  }
+
+  @Override
+  public ListIterator<Object> listIterator(int index) {
+    return getContentsUnsafe().listIterator(index);
+  }
+
+  // For subList, use the immutable getContents() rather than getContentsUnsafe,
+  // to prevent subsequent mutation. To get a mutable SkylarkList,
+  // use a method that takes an Environment into account.
+  @Override
+  public List<Object> subList(int fromIndex, int toIndex) {
+    return getContents().subList(fromIndex, toIndex);
+  }
+
+  // A SkylarkList disables all direct mutation methods.
+  @Override
+  public void add(int index, Object element) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public boolean addAll(int index, Collection<?> elements) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public Object remove(int index) {
+    throw new UnsupportedOperationException();
   }
 
   @Override
-  public final Iterator<Object> iterator() {
-    return getList().iterator();
+  public Object set(int index, Object element) {
+    throw new UnsupportedOperationException();
   }
 
+  // Other methods
   @Override
-  public String toString() {
-    return Printer.repr(this);
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.printList(buffer, getContentsUnsafe(), isTuple(), quotationMark);
   }
 
+  // Note that the following two functions slightly violate the Java List protocol,
+  // in that it does NOT consider that a SkylarkList .equals() an arbitrary List with same contents.
+  // This is because we use .equals() to model skylark equality, which like Python
+  // distinguishes a MutableList from a Tuple.
   @Override
   public boolean equals(Object object) {
     return (this == object)
         || ((this.getClass() == object.getClass())
-            && getList().equals(((SkylarkList) object).getList()));
+            && getContentsUnsafe().equals(((SkylarkList) object).getContentsUnsafe()));
   }
 
   @Override
   public int hashCode() {
-    return getClass().hashCode() + 31 * getList().hashCode();
+    return getClass().hashCode() + 31 * getContentsUnsafe().hashCode();
   }
 
   /**
@@ -160,10 +195,9 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
    */
   public <TYPE> List<TYPE> getContents(Class<TYPE> type, @Nullable String description)
       throws EvalException {
-    return castList(getContents(), type, description);
+    return castList(getContentsUnsafe(), type, description);
   }
 
-
   /**
    * A class for mutable lists.
    */
@@ -184,7 +218,7 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
             + "['a', 'b', 'c', 'd'][3:0:-1]  # ['d', 'c', 'b']</pre>"
             + "Lists are mutable, as in Python."
   )
-  public static final class MutableList extends SkylarkList implements Freezable {
+  public static final class MutableList extends SkylarkList {
 
     private final ArrayList<Object> contents = new ArrayList<>();
 
@@ -204,7 +238,7 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
      */
     MutableList(Iterable<?> contents, Mutability mutability) {
       super();
-      addAll(contents);
+      addAllUnsafe(contents);
       if (contents instanceof GlobList<?>) {
         globList = (GlobList<?>) contents;
       }
@@ -248,29 +282,19 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
     }
 
     /**
-     * Adds one element at the end of the MutableList.
-     * @param element the element to add
-     */
-    private void add(Object element) {
-      this.contents.add(element);
-    }
-
-    /**
      * Adds all the elements at the end of the MutableList.
      * @param elements the elements to add
+     * Assumes that you already checked for Mutability.
      */
-    private void addAll(Iterable<?> elements) {
+    private void addAllUnsafe(Iterable<?> elements) {
       for (Object elem : elements) {
-        add(elem);
+        contents.add(elem);
       }
     }
 
-    private void checkMutable(Location loc, Environment env) throws EvalException {
-      try {
-        Mutability.checkMutable(this, env);
-      } catch (MutabilityException ex) {
-        throw new EvalException(loc, ex);
-      }
+    @Override
+    protected void checkMutable(Location loc, Environment env) throws EvalException {
+      super.checkMutable(loc, env);
       globList = null; // If you're going to mutate it, invalidate the underlying GlobList.
     }
 
@@ -290,10 +314,15 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
       return getImmutableList();
     }
 
+    @Override
+    protected List<Object> getContentsUnsafe() {
+      return contents;
+    }
+
     /**
      * @return the GlobList if there is one, otherwise the regular contents.
      */
-    private List<?> getContentsUnsafe() {
+    private List<?> getGlobListOrContentsUnsafe() {
       if (globList != null) {
         return globList;
       }
@@ -312,7 +341,7 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
         return new MutableList(Iterables.concat(left, right), env);
       }
       return new MutableList(GlobList.concat(
-          left.getContentsUnsafe(), right.getContentsUnsafe()), env);
+          left.getGlobListOrContentsUnsafe(), right.getGlobListOrContentsUnsafe()), env);
     }
 
     /**
@@ -323,7 +352,7 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
      */
     public void add(Object element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
-      add(element);
+      contents.add(element);
     }
 
     public void remove(int index, Location loc, Environment env) throws EvalException {
@@ -339,13 +368,7 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
      */
     public void addAll(Iterable<?> elements, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
-      addAll(elements);
-    }
-
-
-    @Override
-    public List<Object> getList() {
-      return contents;
+      addAllUnsafe(elements);
     }
 
     @Override
@@ -404,6 +427,11 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
       this.contents = contents;
     }
 
+    @Override
+    public Mutability mutability() {
+      return Mutability.IMMUTABLE;
+    }
+
     /**
      * THE empty Skylark tuple.
      */
@@ -437,17 +465,17 @@ public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
     }
 
     @Override
-    public List<Object> getList() {
+    public ImmutableList<Object> getImmutableList() {
       return contents;
     }
 
     @Override
-    public ImmutableList<Object> getImmutableList() {
+    public List<Object> getContents() {
       return contents;
     }
 
     @Override
-    public List<Object> getContents() {
+    protected List<Object> getContentsUnsafe() {
       return contents;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
new file mode 100644
index 0000000000..afa107a327
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
@@ -0,0 +1,158 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.syntax;
+
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.Mutability.Freezable;
+import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
+
+import java.util.Collection;
+import java.util.Iterator;
+
+import javax.annotation.Nullable;
+
+/**
+ * Base class for data structures that are only mutable with a proper Mutability.
+ */
+abstract class SkylarkMutable implements Freezable, SkylarkValue {
+
+  protected SkylarkMutable() {}
+
+  /**
+   * Check whether this object is mutable in the current evaluation Environment.
+   * @throws EvalException if the object was not mutable.
+   */
+  protected void checkMutable(Location loc, Environment env) throws EvalException {
+    try {
+      Mutability.checkMutable(this, env);
+    } catch (MutabilityException ex) {
+      throw new EvalException(loc, ex);
+    }
+  }
+
+  @Override
+  public String toString() {
+    return Printer.repr(this);
+  }
+
+  abstract static class MutableCollection<E> extends SkylarkMutable implements Collection<E> {
+
+    protected MutableCollection() {}
+
+    /**
+     * Return the underlying contents of this collection,
+     * that may be of a more specific class with its own methods.
+     * This object MUST NOT be mutated.
+     * If possible, the implementation should make this object effectively immutable,
+     * by throwing {@link UnsupportedOperationException} if attemptedly mutated;
+     * but it need not be an instance of {@link com.google.common.collect.ImmutableCollection}.
+     */
+    public abstract Collection<Object> getContents();
+
+    /**
+     * The underlying contents is a (usually) mutable data structure.
+     * Read access is forwarded to these contents.
+     * This object must not be modified outside an {@link Environment}
+     * with a correct matching {@link Mutability},
+     * which should be checked beforehand using {@link #checkMutable}.
+     * it need not be an instance of {@link com.google.common.collect.ImmutableCollection}.
+     */
+    protected abstract Collection<E> getContentsUnsafe();
+
+    @Override
+    public Iterator<E> iterator() {
+      return getContentsUnsafe().iterator();
+    };
+
+    @Override
+    public int size() {
+      return getContentsUnsafe().size();
+    }
+
+    @Override
+    public final Object[] toArray() {
+      return getContentsUnsafe().toArray();
+    }
+
+    @Override
+    public final <Object> Object[] toArray(Object[] other) {
+      return getContentsUnsafe().toArray(other);
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return getContentsUnsafe().isEmpty();
+    }
+
+    @Override
+    public final boolean contains(@Nullable Object object) {
+      return getContentsUnsafe().contains(object);
+    }
+
+    @Override
+    public final boolean containsAll(Collection<?> collection) {
+      return getContentsUnsafe().containsAll(collection);
+    }
+
+    // Disable all mutation interfaces without a mutation context.
+
+    @Deprecated
+    @Override
+    public final boolean add(E element) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final boolean addAll(Collection<? extends E> collection) {
+      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 void clear() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      return getContentsUnsafe().equals(o);
+    }
+
+    @Override
+    public int hashCode() {
+      return getContentsUnsafe().hashCode();
+    }
+  }
+}