1 files changed, 373 insertions, 0 deletions
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
new file mode 100644
index 0000000000..ef9fe1014e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
@@ -0,0 +1,373 @@
+// Copyright 2014 Google Inc. 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.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.events.Location;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * A class to handle lists and tuples in Skylark.
+ */
+@SkylarkModule(name = "list",
+    doc = "A language built-in type to support lists. Example of list literal:<br>"
+        + "<pre class=language-python>l = [1, 2, 3]</pre>"
+        + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
+        + "<pre class=language-python>e = l[1]   # e == 2</pre>"
+        + "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
+        + "<pre class=language-python>l = [1, 2] + [3, 4]   # l == [1, 2, 3, 4]\n"
+        + "l = [\"a\", \"b\"]\n"
+        + "l += [\"c\"]            # l == [\"a\", \"b\", \"c\"]</pre>"
+        + "List elements have to be of the same type, <code>[1, 2, \"c\"]</code> results in an "
+        + "error. Lists - just like everything - are immutable, therefore <code>l[1] = \"a\""
+        + "</code> is not supported.")
+public abstract class SkylarkList implements Iterable<Object> {
+
+  private final boolean tuple;
+  private final Class<?> genericType;
+
+  private SkylarkList(boolean tuple, Class<?> genericType) {
+    this.tuple = tuple;
+    this.genericType = genericType;
+  }
+
+  /**
+   * The size of the list.
+   */
+  public abstract int size();
+
+  /**
+   * Returns true if the list is empty.
+   */
+  public abstract boolean isEmpty();
+
+  /**
+   * Returns the i-th element of the list.
+   */
+  public abstract Object get(int i);
+
+  /**
+   * Returns true if this list is a tuple.
+   */
+  public boolean isTuple() {
+    return tuple;
+  }
+
+  @VisibleForTesting
+  public Class<?> getGenericType() {
+    return genericType;
+  }
+
+  @Override
+  public String toString() {
+    return toList().toString();
+  }
+
+  // TODO(bazel-team): we should be very careful using this method. Check and remove
+  // auto conversions on the Java-Skylark interface if possible.
+  /**
+   * Converts this Skylark list to a Java list.
+   */
+  public abstract List<?> toList();
+
+  @SuppressWarnings("unchecked")
+  public <T> Iterable<T> to(Class<T> type) {
+    Preconditions.checkArgument(this == EMPTY_LIST || type.isAssignableFrom(genericType));
+    return (Iterable<T>) this;
+  }
+
+  private static final class EmptySkylarkList extends SkylarkList {
+    private EmptySkylarkList(boolean tuple) {
+      super(tuple, Object.class);
+    }
+
+    @Override
+    public Iterator<Object> iterator() {
+      return ImmutableList.of().iterator();
+    }
+
+    @Override
+    public int size() {
+      return 0;
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return true;
+    }
+
+    @Override
+    public Object get(int i) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public List<?> toList() {
+      return isTuple() ? ImmutableList.of() : Lists.newArrayList();
+    }
+
+    @Override
+    public String toString() {
+      return "[]";
+    }
+  }
+
+  /**
+   * An empty Skylark list.
+   */
+  public static final SkylarkList EMPTY_LIST = new EmptySkylarkList(false);
+
+  private static final class SimpleSkylarkList extends SkylarkList {
+    private final ImmutableList<Object> list;
+
+    private SimpleSkylarkList(ImmutableList<Object> list, boolean tuple, Class<?> genericType) {
+      super(tuple, genericType);
+      this.list = Preconditions.checkNotNull(list);
+    }
+
+    @Override
+    public Iterator<Object> iterator() {
+      return list.iterator();
+    }
+
+    @Override
+    public int size() {
+      return list.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return list.isEmpty();
+    }
+
+    @Override
+    public Object get(int i) {
+      return list.get(i);
+    }
+
+    @Override
+    public List<?> toList() {
+      return isTuple() ? list : Lists.newArrayList(list);
+    }
+
+    @Override
+    public String toString() {
+      return list.toString();
+    }
+
+    @Override
+    public int hashCode() {
+      return list.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+      if (!(obj instanceof SimpleSkylarkList)) {
+        return false;
+      }
+      SimpleSkylarkList other = (SimpleSkylarkList) obj;
+      return other.list.equals(this.list);
+    }
+  }
+
+  /**
+   * A Skylark list to support lazy iteration (i.e. we only call iterator on the object this
+   * list masks when it's absolutely necessary). This is useful if iteration is expensive
+   * (e.g. NestedSet-s). Size(), get() and isEmpty() are expensive operations but
+   * concatenation is quick.
+   */
+  private static final class LazySkylarkList extends SkylarkList {
+    private final Iterable<Object> iterable;
+    private ImmutableList<Object> list = null;
+
+    private LazySkylarkList(Iterable<Object> iterable, boolean tuple, Class<?> genericType) {
+      super(tuple, genericType);
+      this.iterable = Preconditions.checkNotNull(iterable);
+    }
+
+    @Override
+    public Iterator<Object> iterator() {
+      return iterable.iterator();
+    }
+
+    @Override
+    public int size() {
+      return Iterables.size(iterable);
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return Iterables.isEmpty(iterable);
+    }
+
+    @Override
+    public Object get(int i) {
+      return getList().get(i);
+    }
+
+    @Override
+    public List<?> toList() {
+      return getList();
+    }
+
+    private ImmutableList<Object> getList() {
+      if (list == null) {
+        list = ImmutableList.copyOf(iterable);
+      }
+      return list;
+    }
+  }
+
+  /**
+   * A Skylark list to support quick concatenation of lists. Concatenation is O(1),
+   * size(), isEmpty() is O(n), get() is O(h).
+   */
+  private static final class ConcatenatedSkylarkList extends SkylarkList {
+    private final SkylarkList left;
+    private final SkylarkList right;
+
+    private ConcatenatedSkylarkList(
+        SkylarkList left, SkylarkList right, boolean tuple, Class<?> genericType) {
+      super(tuple, genericType);
+      this.left = Preconditions.checkNotNull(left);
+      this.right = Preconditions.checkNotNull(right);
+    }
+
+    @Override
+    public Iterator<Object> iterator() {
+      return Iterables.concat(left, right).iterator();
+    }
+
+    @Override
+    public int size() {
+      // We shouldn't evaluate the size function until it's necessary, because it can be expensive
+      // for lazy lists (e.g. lists containing a NestedSet).
+      // TODO(bazel-team): make this class more clever to store the size and empty parameters
+      // for every non-LazySkylarkList member.
+      return left.size() + right.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return left.isEmpty() && right.isEmpty();
+    }
+
+    @Override
+    public Object get(int i) {
+      int leftSize = left.size();
+      if (i < leftSize) {
+        return left.get(i);
+      } else {
+        return right.get(i - leftSize);
+      }
+    }
+
+    @Override
+    public List<?> toList() {
+      return ImmutableList.<Object>builder().addAll(left).addAll(right).build();
+    }
+  }
+
+  /**
+   * Returns a Skylark list containing elements without a type check. Only use if all elements
+   * are of the same type.
+   */
+  public static SkylarkList list(Collection<?> elements, Class<?> genericType) {
+    if (elements.isEmpty()) {
+      return EMPTY_LIST;
+    }
+    return new SimpleSkylarkList(ImmutableList.copyOf(elements), false, genericType);
+  }
+
+  /**
+   * Returns a Skylark list containing elements without a type check and without creating
+   * an immutable copy. Therefore the iterable containing elements must be immutable
+   * (which is not checked here so callers must be extra careful). This way
+   * it's possibly to create a SkylarkList without requesting the original iterator. This
+   * can be useful for nested set - list conversions.
+   */
+  @SuppressWarnings("unchecked")
+  public static SkylarkList lazyList(Iterable<?> elements, Class<?> genericType) {
+    return new LazySkylarkList((Iterable<Object>) elements, false, genericType);
+  }
+
+  /**
+   * Returns a Skylark list containing elements. Performs type check and throws an exception
+   * in case the list contains elements of different type.
+   */
+  public static SkylarkList list(Collection<?> elements, Location loc) throws EvalException {
+    if (elements.isEmpty()) {
+      return EMPTY_LIST;
+    }
+    return new SimpleSkylarkList(
+        ImmutableList.copyOf(elements), false, getGenericType(elements, loc));
+  }
+
+  private static Class<?> getGenericType(Collection<?> elements, Location loc)
+      throws EvalException {
+    Class<?> genericType = elements.iterator().next().getClass();
+    for (Object element : elements) {
+      Class<?> type = element.getClass();
+      if (!EvalUtils.getSkylarkType(genericType).equals(EvalUtils.getSkylarkType(type))) {
+        throw new EvalException(loc, String.format(
+            "Incompatible types in list: found a %s but the first element is a %s",
+            EvalUtils.getDataTypeNameFromClass(type),
+            EvalUtils.getDataTypeNameFromClass(genericType)));
+      }
+    }
+    return genericType;
+  }
+
+  /**
+   * Returns a Skylark list created from Skylark lists left and right. Throws an exception
+   * if they are not of the same generic type.
+   */
+  public static SkylarkList concat(SkylarkList left, SkylarkList right, Location loc)
+      throws EvalException {
+    if (left.isTuple() != right.isTuple()) {
+      throw new EvalException(loc, "cannot concatenate lists and tuples");
+    }
+    if (left == EMPTY_LIST) {
+      return right;
+    }
+    if (right == EMPTY_LIST) {
+      return left;
+    }
+    if (!left.genericType.equals(right.genericType)) {
+      throw new EvalException(loc, String.format("cannot concatenate list of %s with list of %s",
+          EvalUtils.getDataTypeNameFromClass(left.genericType),
+          EvalUtils.getDataTypeNameFromClass(right.genericType)));
+    }
+    return new ConcatenatedSkylarkList(left, right, left.isTuple(), left.genericType);
+  }
+
+  /**
+   * Returns a Skylark tuple containing elements.
+   */
+  public static SkylarkList tuple(List<?> elements) {
+    // Tuple elements do not have to have the same type.
+    return new SimpleSkylarkList(ImmutableList.copyOf(elements), true, Object.class);
+  }
+}