src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java - bazel - Git at Google

 // Copyright 2014 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.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 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.syntax.SkylarkMutable.MutableCollection;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.RandomAccess;
 import javax.annotation.Nullable;

 /** A class to handle lists and tuples in Skylark. */
 @SkylarkModule(
   name = "sequence",
   documented = false,
   category = SkylarkModuleCategory.BUILTIN,
   doc = "common type of lists and tuples"
 )
 public abstract class SkylarkList<E> extends MutableCollection<E> implements List<E>, RandomAccess,
     SkylarkIndexable {

   /**
    * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
    */
   public abstract ImmutableList<E> getImmutableList();

   /**
    * Returns a List object with the current underlying contents of this SkylarkList.
    * 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.
   public abstract List<E> getContents();

   /**
    * 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}.
    */
   @Override
   protected abstract List<E> getContentsUnsafe();

   /**
    * Returns true if this list is a tuple.
    */
   public abstract boolean isTuple();

   // A SkylarkList forwards all read-only access to the getContentsUnsafe().
   @Override
   public final E get(int i) {
     return getContentsUnsafe().get(i);
   }

   @Override
   public int indexOf(Object element) {
     return getContentsUnsafe().indexOf(element);
   }

   @Override
   public int lastIndexOf(Object element) {
     return getContentsUnsafe().lastIndexOf(element);
   }

   @Override
   public ListIterator<E> listIterator() {
     return getContentsUnsafe().listIterator();
   }

   @Override
   public ListIterator<E> 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<E> subList(int fromIndex, int toIndex) {
     return getContents().subList(fromIndex, toIndex);
   }

   // A SkylarkList disables all direct mutation methods.
   @Override
   public void add(int index, E element) {
     throw new UnsupportedOperationException();
   }

   @Override
   public boolean addAll(int index, Collection<? extends E> elements) {
     throw new UnsupportedOperationException();
   }

   @Override
   public E remove(int index) {
     throw new UnsupportedOperationException();
   }

   @Override
   public E set(int index, E element) {
     throw new UnsupportedOperationException();
   }

   /**
    * Retrieve an entry from a SkylarkList.
    *
    * @param key the index
    * @param loc a {@link Location} in case of error
    * @throws EvalException if the key is invalid
    */
   @Override
   public final E getIndex(Object key, Location loc) throws EvalException {
     List<E> list = getContentsUnsafe();
     int index = MethodLibrary.getListIndex(key, list.size(), loc);
     return list.get(index);
   }

   /**
    * Retrieve a sublist from a SkylarkList.
    * @param start start value
    * @param end end value
    * @param step step value
    * @param loc a {@link Location} in case of error
    * @throws EvalException if the key is invalid
    */
   public List<E> getSlice(Object start, Object end, Object step, Location loc)
       throws EvalException {
     List<E> list = getContentsUnsafe();
     int length = list.size();
     ImmutableList.Builder<E> slice = ImmutableList.builder();
     for (int pos : MethodLibrary.getSliceIndices(start, end, step, length, loc)) {
       slice.add(list.get(pos));
     }
     return slice.build();
   }

   /**
    * Put an entry into a SkylarkList.
    * @param key the index
    * @param value the associated value
    * @param loc a {@link Location} in case of error
    * @param env an {@link Environment}, to check Mutability
    * @throws EvalException if the key is invalid
    */
   public void set(Object key, E value, Location loc, Environment env) throws EvalException {
     checkMutable(loc, env);
     List list = getContentsUnsafe();
     int index = MethodLibrary.getListIndex(key, list.size(), loc);
     list.set(index, value);
   }

   // Other methods
   @Override
   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())
             && getContentsUnsafe().equals(((SkylarkList) object).getContentsUnsafe()));
   }

   @Override
   public int hashCode() {
     return getClass().hashCode() + 31 * getContentsUnsafe().hashCode();
   }

   /**
    * Cast a {@code List<?>} to a {@code List<T>} after checking its current contents.
    * @param list the List to cast
    * @param type the expected class of elements
    * @param description a description of the argument being converted, or null, for debugging
    */
   @SuppressWarnings("unchecked")
   public static <TYPE> List<TYPE> castList(
       List<?> list, Class<TYPE> type, @Nullable String description)
       throws EvalException {
     Object desc = description == null ? null : Printer.formattable("'%s' element", description);
     for (Object value : list) {
       SkylarkType.checkType(value, type, desc);
     }
     return (List<TYPE>) list;
   }

   /**
    * Cast a SkylarkList to a {@code List<T>} after checking its current contents.
    * Treat None as meaning the empty List.
    * @param obj the Object to cast. null and None are treated as an empty list.
    * @param type the expected class of elements
    * @param description a description of the argument being converted, or null, for debugging
    */
   public static <TYPE> List<TYPE> castSkylarkListOrNoneToList(
       Object obj, Class<TYPE> type, @Nullable String description)
       throws EvalException {
     if (EvalUtils.isNullOrNone(obj)) {
       return ImmutableList.of();
     }
     if (obj instanceof SkylarkList) {
       return ((SkylarkList<?>) obj).getContents(type, description);
     }
     throw new EvalException(null,
         Printer.format("Illegal argument: %s is not of expected type list or NoneType",
             description == null ? Printer.repr(obj) : String.format("'%s'", description)));
   }

   /**
    * Cast the SkylarkList object into a List of the given type.
    * @param type the expected class of elements
    * @param description a description of the argument being converted, or null, for debugging
    */
   public <TYPE> List<TYPE> getContents(Class<TYPE> type, @Nullable String description)
       throws EvalException {
     return castList(getContentsUnsafe(), type, description);
   }

   /**
    * Creates immutable SkylarkList with given elements.
    */
   public static <E> SkylarkList<E> createImmutable(Iterable<? extends E> contents) {
     return new MutableList<E>(contents, Mutability.IMMUTABLE);
   }

   /** A class for mutable lists. */
   @SkylarkModule(
     name = "list",
     category = SkylarkModuleCategory.BUILTIN,
     doc =
         "A language built-in type to support lists. Example of list literal:<br>"
             + "<pre class=language-python>x = [1, 2, 3]</pre>"
             + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
             + "<pre class=language-python>e = x[1]   # e == 2</pre>"
             + "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
             + "<pre class=language-python>x = [1, 2] + [3, 4]   # x == [1, 2, 3, 4]\n"
             + "x = [\"a\", \"b\"]\n"
             + "x += [\"c\"]            # x == [\"a\", \"b\", \"c\"]</pre>"
             + "Similar to strings, lists support slice operations:"
             + "<pre class=language-python>['a', 'b', 'c', 'd'][1:3]   # ['b', 'c']\n"
             + "['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 static final class MutableList<E> extends SkylarkList<E> {

     private final ArrayList<E> contents = new ArrayList<>();

     // Treat GlobList specially: external code depends on it.
     // TODO(bazel-team): make data structures *and binary operators* extensible
     // (via e.g. interface classes for each binary operator) so that GlobList
     // can be implemented outside of the core of Skylark.
     @Nullable private GlobList<E> globList;

     private final Mutability mutability;

     /**
      * Creates a MutableList from contents and a Mutability.
      * @param contents the contents of the list
      * @param mutability a Mutability context
      * @return a MutableList containing the elements
      */
     @SuppressWarnings("unchecked")
     private MutableList(Iterable<? extends E> contents, Mutability mutability) {
       super();
       addAllUnsafe(contents);
       if (contents instanceof GlobList) {
         globList = (GlobList<E>) contents;
       }
       this.mutability = mutability;
     }

     /** Specialized constructor for concat. */
     private MutableList(
         MutableList<? extends E> lhs,
         MutableList<? extends E> rhs,
         @Nullable Environment env) {
       super();
       this.contents.ensureCapacity(lhs.size() + rhs.size());
       this.contents.addAll(lhs);
       this.contents.addAll(rhs);
       this.mutability = env == null ? Mutability.IMMUTABLE : env.mutability();
     }

     /**
      * Creates a MutableList from contents and an Environment.
      * @param contents the contents of the list
      * @param env an Environment from which to inherit Mutability, or null for immutable
      * @return a MutableList containing the elements
      */
     public MutableList(Iterable<? extends E> contents, @Nullable Environment env) {
       this(contents, env == null ? Mutability.IMMUTABLE : env.mutability());
     }

     /**
      * Creates a mutable or immutable MutableList depending on the given {@link Mutability}.
      */
     public MutableList(Mutability mutability) {
       this(Collections.EMPTY_LIST, mutability);
     }

     /**
      * Builds a Skylark list from a variable number of arguments.
      * @param env an Environment from which to inherit Mutability, or null for immutable
      * @param contents the contents of the list
      * @return a Skylark list containing the specified arguments as elements.
      */
     public static <E> MutableList<E> of(@Nullable Environment env, E... contents) {
       return new MutableList(ImmutableList.copyOf(contents), env);
     }

     /**
      * 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 addAllUnsafe(Iterable<? extends E> elements) {
       Iterables.addAll(contents, elements);
     }

     @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.
     }

     @Nullable public GlobList<E> getGlobList() {
       return globList;
     }

     /**
      * @return the GlobList if there is one, otherwise an Immutable copy of the regular contents.
      */
     @Override
     @SuppressWarnings("unchecked")
     public List<E> getContents() {
       if (globList != null) {
         return globList;
       }
       return getImmutableList();
     }

     @Override
     protected List<E> getContentsUnsafe() {
       return contents;
     }

     /**
      * @return the GlobList if there is one, otherwise the regular contents.
      */
     private List<?> getGlobListOrContentsUnsafe() {
       if (globList != null) {
         return globList;
       }
       return contents;
     }

     /**
      * Concatenate two MutableList
      * @param left the start of the new list
      * @param right the end of the new list
      * @param env the Environment in which to create a new list
      * @return a new MutableList
      */
     public static <E> MutableList<E> concat(
         MutableList<? extends E> left,
         MutableList<? extends E> right,
         Environment env) {
       if (left.getGlobList() == null && right.getGlobList() == null) {
         return new MutableList<>(left, right, env);
       }
       return new MutableList(GlobList.concat(
           left.getGlobListOrContentsUnsafe(), right.getGlobListOrContentsUnsafe()), env);
     }

     /**
      * Adds one element at the end of the MutableList.
      * @param element the element to add
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
     public void add(E element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       contents.add(element);
     }

     /**
      * Inserts an item at a given position to the MutableList.
      * @param index the index of the given position
      * @param element the element to add
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
     public void add(int index, E element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       contents.add(index, element);
     }

     public void remove(int index, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       contents.remove(index);
     }

     /**
      * Adds all the elements at the end of the MutableList.
      * @param elements the elements to add
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
     public void addAll(Iterable<? extends E> elements, Location loc, Environment env)
         throws EvalException {
       checkMutable(loc, env);
       addAllUnsafe(elements);
     }

     @Override
     public ImmutableList<E> getImmutableList() {
       return ImmutableList.copyOf(contents);
     }

     @Override
     public Mutability mutability() {
       return mutability;
     }

     @Override
     public boolean isTuple() {
       return false;
     }

     /**
      * An empty IMMUTABLE MutableList.
      */
     public static final MutableList EMPTY = new MutableList(Tuple.EMPTY, Mutability.IMMUTABLE);
   }

   /** An immutable tuple, e.g. in (1, 2, 3) */
   @SkylarkModule(
     name = "tuple",
     category = SkylarkModuleCategory.BUILTIN,
     doc =
         "A language built-in type to support tuples. Example of tuple literal:<br>"
             + "<pre class=language-python>x = (1, 2, 3)</pre>"
             + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
             + "<pre class=language-python>e = x[1]   # e == 2</pre>"
             + "Lists support the <code>+</code> operator to concatenate two tuples. Example:<br>"
             + "<pre class=language-python>x = (1, 2) + (3, 4)   # x == (1, 2, 3, 4)\n"
             + "x = (\"a\", \"b\")\n"
             + "x += (\"c\",)            # x == (\"a\", \"b\", \"c\")</pre>"
             + "Similar to lists, tuples support slice operations:"
             + "<pre class=language-python>('a', 'b', 'c', 'd')[1:3]   # ('b', 'c')\n"
             + "('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 static final class Tuple<E> extends SkylarkList<E> {

     private final ImmutableList<E> contents;

     private Tuple(ImmutableList<E> contents) {
       super();
       this.contents = contents;
     }

     @Override
     public Mutability mutability() {
       return Mutability.IMMUTABLE;
     }

     /**
      * THE empty Skylark tuple.
      */
     private static final Tuple<?> EMPTY = new Tuple<>(ImmutableList.of());

     @SuppressWarnings("unchecked")
     public static final <E> Tuple<E> empty() {
       return (Tuple<E>) EMPTY;
     }

     /**
      * Creates a Tuple from an ImmutableList.
      */
     public static<E> Tuple<E> create(ImmutableList<E> contents) {
       if (contents.isEmpty()) {
         return empty();
       }
       return new Tuple(contents);
     }

     /**
      * Creates a Tuple from an Iterable.
      */
     public static <E> Tuple<E> copyOf(Iterable<? extends E> contents) {
       return create(ImmutableList.<E>copyOf(contents));
     }

     /**
      * Builds a Skylark tuple from a variable number of arguments.
      * @param elements a variable number of arguments (or an Array of Object-s)
      * @return a Skylark tuple containing the specified arguments as elements.
      */
     public static <E> Tuple<E> of(E... elements) {
       return Tuple.create(ImmutableList.copyOf(elements));
     }

     /**
      * Retrieve a sublist from a SkylarkList.
      * @param start start value
      * @param end end value
      * @param step step value
      * @param loc a {@link Location} in case of error
      * @throws EvalException if the key is invalid
      */
     @Override
     public final Tuple<E> getSlice(Object start, Object end, Object step, Location loc)
         throws EvalException {
       return copyOf(super.getSlice(start, end, step, loc));
     }

     @Override
     public ImmutableList<E> getImmutableList() {
       return contents;
     }

     @Override
     public List<E> getContents() {
       return contents;
     }

     @Override
     protected List<E> getContentsUnsafe() {
       return contents;
     }

     @Override
     public boolean isTuple() {
       return true;
     }

     @Override
     public boolean isImmutable() {
       for (Object item : this) {
         if (!EvalUtils.isImmutable(item)) {
           return false;
         }
       }
       return true;
     }
   }
 }
	// Copyright 2014 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.common.collect.ImmutableList;
	import com.google.common.collect.Iterables;
	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.syntax.SkylarkMutable.MutableCollection;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.List;
	import java.util.ListIterator;
	import java.util.RandomAccess;
	import javax.annotation.Nullable;

	/** A class to handle lists and tuples in Skylark. */
	@SkylarkModule(
	name = "sequence",
	documented = false,
	category = SkylarkModuleCategory.BUILTIN,
	doc = "common type of lists and tuples"
	)
	public abstract class SkylarkList<E> extends MutableCollection<E> implements List<E>, RandomAccess,
	SkylarkIndexable {

	/**
	* Returns an ImmutableList object with the current underlying contents of this SkylarkList.
	*/
	public abstract ImmutableList<E> getImmutableList();

	/**
	* Returns a List object with the current underlying contents of this SkylarkList.
	* 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.
	public abstract List<E> getContents();

	/**
	* 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}.
	*/
	@Override
	protected abstract List<E> getContentsUnsafe();

	/**
	* Returns true if this list is a tuple.
	*/
	public abstract boolean isTuple();

	// A SkylarkList forwards all read-only access to the getContentsUnsafe().
	@Override
	public final E get(int i) {
	return getContentsUnsafe().get(i);
	}

	@Override
	public int indexOf(Object element) {
	return getContentsUnsafe().indexOf(element);
	}

	@Override
	public int lastIndexOf(Object element) {
	return getContentsUnsafe().lastIndexOf(element);
	}

	@Override
	public ListIterator<E> listIterator() {
	return getContentsUnsafe().listIterator();
	}

	@Override
	public ListIterator<E> 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<E> subList(int fromIndex, int toIndex) {
	return getContents().subList(fromIndex, toIndex);
	}

	// A SkylarkList disables all direct mutation methods.
	@Override
	public void add(int index, E element) {
	throw new UnsupportedOperationException();
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> elements) {
	throw new UnsupportedOperationException();
	}

	@Override
	public E remove(int index) {
	throw new UnsupportedOperationException();
	}

	@Override
	public E set(int index, E element) {
	throw new UnsupportedOperationException();
	}

	/**
	* Retrieve an entry from a SkylarkList.
	*
	* @param key the index
	* @param loc a {@link Location} in case of error
	* @throws EvalException if the key is invalid
	*/
	@Override
	public final E getIndex(Object key, Location loc) throws EvalException {
	List<E> list = getContentsUnsafe();
	int index = MethodLibrary.getListIndex(key, list.size(), loc);
	return list.get(index);
	}

	/**
	* Retrieve a sublist from a SkylarkList.
	* @param start start value
	* @param end end value
	* @param step step value
	* @param loc a {@link Location} in case of error
	* @throws EvalException if the key is invalid
	*/
	public List<E> getSlice(Object start, Object end, Object step, Location loc)
	throws EvalException {
	List<E> list = getContentsUnsafe();
	int length = list.size();
	ImmutableList.Builder<E> slice = ImmutableList.builder();
	for (int pos : MethodLibrary.getSliceIndices(start, end, step, length, loc)) {
	slice.add(list.get(pos));
	}
	return slice.build();
	}

	/**
	* Put an entry into a SkylarkList.
	* @param key the index
	* @param value the associated value
	* @param loc a {@link Location} in case of error
	* @param env an {@link Environment}, to check Mutability
	* @throws EvalException if the key is invalid
	*/
	public void set(Object key, E value, Location loc, Environment env) throws EvalException {
	checkMutable(loc, env);
	List list = getContentsUnsafe();
	int index = MethodLibrary.getListIndex(key, list.size(), loc);
	list.set(index, value);
	}

	// Other methods
	@Override
	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())
	&& getContentsUnsafe().equals(((SkylarkList) object).getContentsUnsafe()));
	}

	@Override
	public int hashCode() {
	return getClass().hashCode() + 31 * getContentsUnsafe().hashCode();
	}

	/**
	* Cast a {@code List<?>} to a {@code List<T>} after checking its current contents.
	* @param list the List to cast
	* @param type the expected class of elements
	* @param description a description of the argument being converted, or null, for debugging
	*/
	@SuppressWarnings("unchecked")
	public static <TYPE> List<TYPE> castList(
	List<?> list, Class<TYPE> type, @Nullable String description)
	throws EvalException {
	Object desc = description == null ? null : Printer.formattable("'%s' element", description);
	for (Object value : list) {
	SkylarkType.checkType(value, type, desc);
	}
	return (List<TYPE>) list;
	}

	/**
	* Cast a SkylarkList to a {@code List<T>} after checking its current contents.
	* Treat None as meaning the empty List.
	* @param obj the Object to cast. null and None are treated as an empty list.
	* @param type the expected class of elements
	* @param description a description of the argument being converted, or null, for debugging
	*/
	public static <TYPE> List<TYPE> castSkylarkListOrNoneToList(
	Object obj, Class<TYPE> type, @Nullable String description)
	throws EvalException {
	if (EvalUtils.isNullOrNone(obj)) {
	return ImmutableList.of();
	}
	if (obj instanceof SkylarkList) {
	return ((SkylarkList<?>) obj).getContents(type, description);
	}
	throw new EvalException(null,
	Printer.format("Illegal argument: %s is not of expected type list or NoneType",
	description == null ? Printer.repr(obj) : String.format("'%s'", description)));
	}

	/**
	* Cast the SkylarkList object into a List of the given type.
	* @param type the expected class of elements
	* @param description a description of the argument being converted, or null, for debugging
	*/
	public <TYPE> List<TYPE> getContents(Class<TYPE> type, @Nullable String description)
	throws EvalException {
	return castList(getContentsUnsafe(), type, description);
	}

	/**
	* Creates immutable SkylarkList with given elements.
	*/
	public static <E> SkylarkList<E> createImmutable(Iterable<? extends E> contents) {
	return new MutableList<E>(contents, Mutability.IMMUTABLE);
	}

	/** A class for mutable lists. */
	@SkylarkModule(
	name = "list",
	category = SkylarkModuleCategory.BUILTIN,
	doc =
	"A language built-in type to support lists. Example of list literal:<br>"
	+ "<pre class=language-python>x = [1, 2, 3]</pre>"
	+ "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
	+ "<pre class=language-python>e = x[1] # e == 2</pre>"
	+ "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
	+ "<pre class=language-python>x = [1, 2] + [3, 4] # x == [1, 2, 3, 4]\n"
	+ "x = [\"a\", \"b\"]\n"
	+ "x += [\"c\"] # x == [\"a\", \"b\", \"c\"]</pre>"
	+ "Similar to strings, lists support slice operations:"
	+ "<pre class=language-python>['a', 'b', 'c', 'd'][1:3] # ['b', 'c']\n"
	+ "['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 static final class MutableList<E> extends SkylarkList<E> {

	private final ArrayList<E> contents = new ArrayList<>();

	// Treat GlobList specially: external code depends on it.
	// TODO(bazel-team): make data structures and binary operators extensible
	// (via e.g. interface classes for each binary operator) so that GlobList
	// can be implemented outside of the core of Skylark.
	@Nullable private GlobList<E> globList;

	private final Mutability mutability;

	/**
	* Creates a MutableList from contents and a Mutability.
	* @param contents the contents of the list
	* @param mutability a Mutability context
	* @return a MutableList containing the elements
	*/
	@SuppressWarnings("unchecked")
	private MutableList(Iterable<? extends E> contents, Mutability mutability) {
	super();
	addAllUnsafe(contents);
	if (contents instanceof GlobList) {
	globList = (GlobList<E>) contents;
	}
	this.mutability = mutability;
	}

	/** Specialized constructor for concat. */
	private MutableList(
	MutableList<? extends E> lhs,
	MutableList<? extends E> rhs,
	@Nullable Environment env) {
	super();
	this.contents.ensureCapacity(lhs.size() + rhs.size());
	this.contents.addAll(lhs);
	this.contents.addAll(rhs);
	this.mutability = env == null ? Mutability.IMMUTABLE : env.mutability();
	}

	/**
	* Creates a MutableList from contents and an Environment.
	* @param contents the contents of the list
	* @param env an Environment from which to inherit Mutability, or null for immutable
	* @return a MutableList containing the elements
	*/
	public MutableList(Iterable<? extends E> contents, @Nullable Environment env) {
	this(contents, env == null ? Mutability.IMMUTABLE : env.mutability());
	}

	/**
	* Creates a mutable or immutable MutableList depending on the given {@link Mutability}.
	*/
	public MutableList(Mutability mutability) {
	this(Collections.EMPTY_LIST, mutability);
	}

	/**
	* Builds a Skylark list from a variable number of arguments.
	* @param env an Environment from which to inherit Mutability, or null for immutable
	* @param contents the contents of the list
	* @return a Skylark list containing the specified arguments as elements.
	*/
	public static <E> MutableList<E> of(@Nullable Environment env, E... contents) {
	return new MutableList(ImmutableList.copyOf(contents), env);
	}

	/**
	* 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 addAllUnsafe(Iterable<? extends E> elements) {
	Iterables.addAll(contents, elements);
	}

	@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.
	}

	@Nullable public GlobList<E> getGlobList() {
	return globList;
	}

	/**
	* @return the GlobList if there is one, otherwise an Immutable copy of the regular contents.
	*/
	@Override
	@SuppressWarnings("unchecked")
	public List<E> getContents() {
	if (globList != null) {
	return globList;
	}
	return getImmutableList();
	}

	@Override
	protected List<E> getContentsUnsafe() {
	return contents;
	}

	/**
	* @return the GlobList if there is one, otherwise the regular contents.
	*/
	private List<?> getGlobListOrContentsUnsafe() {
	if (globList != null) {
	return globList;
	}
	return contents;
	}

	/**
	* Concatenate two MutableList
	* @param left the start of the new list
	* @param right the end of the new list
	* @param env the Environment in which to create a new list
	* @return a new MutableList
	*/
	public static <E> MutableList<E> concat(
	MutableList<? extends E> left,
	MutableList<? extends E> right,
	Environment env) {
	if (left.getGlobList() == null && right.getGlobList() == null) {
	return new MutableList<>(left, right, env);
	}
	return new MutableList(GlobList.concat(
	left.getGlobListOrContentsUnsafe(), right.getGlobListOrContentsUnsafe()), env);
	}

	/**
	* Adds one element at the end of the MutableList.
	* @param element the element to add
	* @param loc the Location at which to report any error
	* @param env the Environment requesting the modification
	*/
	public void add(E element, Location loc, Environment env) throws EvalException {
	checkMutable(loc, env);
	contents.add(element);
	}

	/**
	* Inserts an item at a given position to the MutableList.
	* @param index the index of the given position
	* @param element the element to add
	* @param loc the Location at which to report any error
	* @param env the Environment requesting the modification
	*/
	public void add(int index, E element, Location loc, Environment env) throws EvalException {
	checkMutable(loc, env);
	contents.add(index, element);
	}

	public void remove(int index, Location loc, Environment env) throws EvalException {
	checkMutable(loc, env);
	contents.remove(index);
	}

	/**
	* Adds all the elements at the end of the MutableList.
	* @param elements the elements to add
	* @param loc the Location at which to report any error
	* @param env the Environment requesting the modification
	*/
	public void addAll(Iterable<? extends E> elements, Location loc, Environment env)
	throws EvalException {
	checkMutable(loc, env);
	addAllUnsafe(elements);
	}

	@Override
	public ImmutableList<E> getImmutableList() {
	return ImmutableList.copyOf(contents);
	}

	@Override
	public Mutability mutability() {
	return mutability;
	}

	@Override
	public boolean isTuple() {
	return false;
	}

	/**
	* An empty IMMUTABLE MutableList.
	*/
	public static final MutableList EMPTY = new MutableList(Tuple.EMPTY, Mutability.IMMUTABLE);
	}

	/** An immutable tuple, e.g. in (1, 2, 3) */
	@SkylarkModule(
	name = "tuple",
	category = SkylarkModuleCategory.BUILTIN,
	doc =
	"A language built-in type to support tuples. Example of tuple literal:<br>"
	+ "<pre class=language-python>x = (1, 2, 3)</pre>"
	+ "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
	+ "<pre class=language-python>e = x[1] # e == 2</pre>"
	+ "Lists support the <code>+</code> operator to concatenate two tuples. Example:<br>"
	+ "<pre class=language-python>x = (1, 2) + (3, 4) # x == (1, 2, 3, 4)\n"
	+ "x = (\"a\", \"b\")\n"
	+ "x += (\"c\",) # x == (\"a\", \"b\", \"c\")</pre>"
	+ "Similar to lists, tuples support slice operations:"
	+ "<pre class=language-python>('a', 'b', 'c', 'd')[1:3] # ('b', 'c')\n"
	+ "('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 static final class Tuple<E> extends SkylarkList<E> {

	private final ImmutableList<E> contents;

	private Tuple(ImmutableList<E> contents) {
	super();
	this.contents = contents;
	}

	@Override
	public Mutability mutability() {
	return Mutability.IMMUTABLE;
	}

	/**
	* THE empty Skylark tuple.
	*/
	private static final Tuple<?> EMPTY = new Tuple<>(ImmutableList.of());

	@SuppressWarnings("unchecked")
	public static final <E> Tuple<E> empty() {
	return (Tuple<E>) EMPTY;
	}

	/**
	* Creates a Tuple from an ImmutableList.
	*/
	public static<E> Tuple<E> create(ImmutableList<E> contents) {
	if (contents.isEmpty()) {
	return empty();
	}
	return new Tuple(contents);
	}

	/**
	* Creates a Tuple from an Iterable.
	*/
	public static <E> Tuple<E> copyOf(Iterable<? extends E> contents) {
	return create(ImmutableList.<E>copyOf(contents));
	}

	/**
	* Builds a Skylark tuple from a variable number of arguments.
	* @param elements a variable number of arguments (or an Array of Object-s)
	* @return a Skylark tuple containing the specified arguments as elements.
	*/
	public static <E> Tuple<E> of(E... elements) {
	return Tuple.create(ImmutableList.copyOf(elements));
	}

	/**
	* Retrieve a sublist from a SkylarkList.
	* @param start start value
	* @param end end value
	* @param step step value
	* @param loc a {@link Location} in case of error
	* @throws EvalException if the key is invalid
	*/
	@Override
	public final Tuple<E> getSlice(Object start, Object end, Object step, Location loc)
	throws EvalException {
	return copyOf(super.getSlice(start, end, step, loc));
	}

	@Override
	public ImmutableList<E> getImmutableList() {
	return contents;
	}

	@Override
	public List<E> getContents() {
	return contents;
	}

	@Override
	protected List<E> getContentsUnsafe() {
	return contents;
	}

	@Override
	public boolean isTuple() {
	return true;
	}

	@Override
	public boolean isImmutable() {
	for (Object item : this) {
	if (!EvalUtils.isImmutable(item)) {
	return false;
	}
	}
	return true;
	}
	}
	}