Index and slice calls are implemented as separate AST nodes rather than special

function calls.

--
MOS_MIGRATED_REVID=133259901

10 files changed, 348 insertions, 256 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index e5aa180426..5c8f13acd1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -287,24 +287,11 @@ public final class FuncallExpression extends Expression {
   }
 
   private String functionName() {
-    String name = func.getName();
-    if (name.equals("$slice")) {
-      return "operator [:]";
-    } else if (name.equals("$index")) {
-      return "operator []";
-    } else {
-      return "function " + name;
-    }
+    return "function " + func.getName();
   }
 
   @Override
   public String toString() {
-    if (func.getName().equals("$slice")) {
-      return obj + "[" + args.get(0) + ":" + args.get(1) + "]";
-    }
-    if (func.getName().equals("$index")) {
-      return obj + "[" + args.get(0) + "]";
-    }
     StringBuilder sb = new StringBuilder();
     if (obj != null) {
       sb.append(obj).append(".");
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/IndexExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/IndexExpression.java
new file mode 100644
index 0000000000..ef278442ae
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/IndexExpression.java
@@ -0,0 +1,82 @@
+// 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.devtools.build.lib.events.Location;
+
+/** Syntax node for an index expression. e.g. obj[field], but not obj[from:to] */
+public final class IndexExpression extends Expression {
+
+  private final Expression obj;
+
+  private final Expression key;
+
+  public IndexExpression(Expression obj, Expression key) {
+    this.obj = obj;
+    this.key = key;
+  }
+
+  public Expression getObject() {
+    return obj;
+  }
+
+  public Expression getKey() {
+    return key;
+  }
+
+  @Override
+  public String toString() {
+    return String.format("%s[%s]", obj, key);
+  }
+
+  @Override
+  Object doEval(Environment env) throws EvalException, InterruptedException {
+    Object objValue = obj.eval(env);
+    Object keyValue = key.eval(env);
+    return eval(objValue, keyValue, getLocation(), env);
+  }
+
+  /**
+   * Returns the field of the given key of the struct objValue, or null if no such field exists.
+   */
+  private Object eval(Object objValue, Object keyValue, Location loc, Environment env)
+      throws EvalException {
+
+    if (objValue instanceof SkylarkIndexable) {
+      Object result = ((SkylarkIndexable) objValue).getIndex(keyValue, loc);
+      return SkylarkType.convertToSkylark(result, env);
+    } else if (objValue instanceof String) {
+      String string = (String) objValue;
+      int index = MethodLibrary.getListIndex(keyValue, string.length(), loc);
+      return string.substring(index, index + 1);
+    }
+
+    throw new EvalException(
+        loc,
+        Printer.format(
+            "Type %s has no operator [](%s)",
+            EvalUtils.getDataTypeName(objValue),
+            EvalUtils.getDataTypeName(keyValue)));
+  }
+
+  @Override
+  public void accept(SyntaxTreeVisitor visitor) {
+    visitor.visit(this);
+  }
+
+  @Override
+  void validate(ValidationEnvironment env) throws EvalException {
+    obj.validate(env);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index ef5bdb78de..491e026e1b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -22,16 +22,14 @@ import com.google.devtools.build.lib.syntax.compiler.DebugInfo.AstAccessors;
 import com.google.devtools.build.lib.syntax.compiler.Variable.InternalVariable;
 import com.google.devtools.build.lib.syntax.compiler.VariableScope;
 import com.google.devtools.build.lib.util.Preconditions;
-
-import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
-import net.bytebuddy.implementation.bytecode.Removal;
-import net.bytebuddy.implementation.bytecode.constant.IntegerConstant;
-
 import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.Removal;
+import net.bytebuddy.implementation.bytecode.constant.IntegerConstant;
 
 /**
  * Class representing an LValue.
@@ -85,16 +83,12 @@ public class LValue implements Serializable {
 
     // Support syntax for setting an element in an array, e.g. a[5] = 2
     // TODO: We currently do not allow slices (e.g. a[2:6] = [3]).
-    if (lvalue instanceof FuncallExpression) {
-      FuncallExpression func = (FuncallExpression) lvalue;
-      List<Argument.Passed> args = func.getArguments();
-      if (func.getFunction().getName().equals("$index")
-          && args.size() == 1) {
-        Object key = args.get(0).getValue().eval(env);
-        Object evaluatedObject = func.getObject().eval(env);
-        assignItem(env, loc, evaluatedObject, key, result);
-        return;
-      }
+    if (lvalue instanceof IndexExpression) {
+      IndexExpression expression = (IndexExpression) lvalue;
+      Object key = expression.getKey().eval(env);
+      Object evaluatedObject = expression.getObject().eval(env);
+      assignItem(env, loc, evaluatedObject, key, result);
+      return;
     }
     throw new EvalException(loc,
         "can only assign to variables and tuples, not to '" + lvalue + "'");
@@ -156,11 +150,8 @@ public class LValue implements Serializable {
       }
       return;
     }
-    if (expr instanceof FuncallExpression) {
-      FuncallExpression func = (FuncallExpression) expr;
-      if (func.getFunction().getName().equals("$index")) {
-        return;
-      }
+    if (expr instanceof IndexExpression) {
+      return;
     }
     throw new EvalException(loc,
         "can only assign to variables and tuples, not to '" + expr + "'");
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 b9389936a8..21baa82ff5 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
@@ -55,7 +55,7 @@ public class MethodLibrary {
   // Convert string index in the same way Python does.
   // If index is negative, starts from the end.
   // If index is outside bounds, it is restricted to the valid range.
-  private static int clampIndex(int index, int length) {
+  public static int clampIndex(int index, int length) {
     if (index < 0) {
       index += length;
     }
@@ -82,17 +82,27 @@ public class MethodLibrary {
     return str.substring(start, stop);
   }
 
-  public static int getListIndex(int index, int listSize, Location loc)
-      throws ConversionException, EvalException {
+  private static int getListIndex(int index, int listSize, Location loc)
+      throws EvalException {
     // Get the nth element in the list
-    if (index < 0) {
-      index += listSize;
+    int actualIndex = index;
+    if (actualIndex < 0) {
+      actualIndex += listSize;
     }
-    if (index < 0 || index >= listSize) {
+    if (actualIndex < 0 || actualIndex >= listSize) {
       throw new EvalException(loc, "List index out of range (index is "
           + index + ", but list has " + listSize + " elements)");
     }
-    return index;
+    return actualIndex;
+  }
+
+  public static int getListIndex(Object index, int listSize, Location loc)
+      throws EvalException {
+    if (!(index instanceof Integer)) {
+      throw new EvalException(loc, "List indices must be integers, not "
+          + EvalUtils.getDataTypeName(index));
+    }
+    return getListIndex(((Integer) index).intValue(), listSize, loc);
   }
 
   // supported string methods
@@ -900,120 +910,28 @@ public class MethodLibrary {
     }
   };
 
-  // slice operator
-  @SkylarkSignature(
-    name = "$slice",
-    objectType = String.class,
-    documented = false,
-    parameters = {
-      @Param(name = "self", type = String.class, doc = "This string."),
-      @Param(name = "start", type = Object.class, doc = "start position of the slice."),
-      @Param(name = "end", type = Object.class, doc = "end position of the slice."),
-      @Param(name = "step", type = Integer.class, defaultValue = "1", doc = "step value.")
-    },
-    doc =
-        "x[<code>start</code>:<code>end</code>:<code>step</code>] returns a slice or a list slice. "
-            + "Values may be negative and can be omitted.",
-    useLocation = true
-  )
-  private static final BuiltinFunction stringSlice =
-      new BuiltinFunction("$slice") {
-        @SuppressWarnings("unused") // Accessed via Reflection.
-        public Object invoke(String self, Object start, Object end, Integer step, Location loc)
-            throws EvalException, ConversionException {
-          List<Integer> indices = getSliceIndices(start, end, step, self.length(), loc);
-          char[] result = new char[indices.size()];
-          char[] original = self.toCharArray();
-          int resultIndex = 0;
-          for (int originalIndex : indices) {
-            result[resultIndex] = original[originalIndex];
-            ++resultIndex;
-          }
-          return new String(result);
-        }
-      };
-
-  @SkylarkSignature(
-    name = "$slice",
-    objectType = MutableList.class,
-    returnType = MutableList.class,
-    documented = false,
-    parameters = {
-      @Param(name = "self", type = MutableList.class, doc = "This list."),
-      @Param(name = "start", type = Object.class, doc = "start position of the slice."),
-      @Param(name = "end", type = Object.class, doc = "end position of the slice."),
-      @Param(name = "step", type = Integer.class, defaultValue = "1", doc = "step value.")
-    },
-    doc =
-        "x[<code>start</code>:<code>end</code>:<code>step</code>] returns a slice or a list slice."
-            + "Values may be negative and can be omitted.",
-    useLocation = true,
-    useEnvironment = true
-  )
-  private static final BuiltinFunction mutableListSlice =
-      new BuiltinFunction("$slice") {
-        @SuppressWarnings("unused") // Accessed via Reflection.
-        public MutableList<Object> invoke(
-            MutableList<Object> self, Object start, Object end, Integer step, Location loc,
-            Environment env)
-            throws EvalException, ConversionException {
-          return new MutableList(sliceList(self, start, end, step, loc), env);
-        }
-      };
-
-  @SkylarkSignature(
-    name = "$slice",
-    objectType = Tuple.class,
-    returnType = Tuple.class,
-    documented = false,
-    parameters = {
-      @Param(name = "self", type = Tuple.class, doc = "This tuple."),
-      @Param(name = "start", type = Object.class, doc = "start position of the slice."),
-      @Param(name = "end", type = Object.class, doc = "end position of the slice."),
-      @Param(name = "step", type = Integer.class, defaultValue = "1", doc = "step value.")
-    },
-    doc =
-        "x[<code>start</code>:<code>end</code>:<code>step</code>] returns a slice or a list slice. "
-            + "Values may be negative and can be omitted.",
-    useLocation = true
-  )
-  private static final BuiltinFunction tupleSlice =
-      new BuiltinFunction("$slice") {
-        @SuppressWarnings("unused") // Accessed via Reflection.
-        public Tuple<Object> invoke(
-            Tuple<Object> self, Object start, Object end, Integer step, Location loc)
-            throws EvalException, ConversionException {
-          return Tuple.copyOf(sliceList(self, start, end, step, loc));
-        }
-      };
-
-  private static List<Object> sliceList(
-      List<Object> original, Object startObj, Object endObj, int step, Location loc)
-      throws EvalException {
-    int length = original.size();
-    ImmutableList.Builder<Object> slice = ImmutableList.builder();
-    for (int pos : getSliceIndices(startObj, endObj, step, length, loc)) {
-      slice.add(original.get(pos));
-    }
-    return slice.build();
-  }
-
   /**
    *  Calculates the indices of the elements that should be included in the slice [start:end:step]
    * of a sequence with the given length.
    */
-  private static List<Integer> getSliceIndices(
-      Object startObj, Object endObj, int step, int length, Location loc) throws EvalException {
+  public static List<Integer> getSliceIndices(
+      Object startObj, Object endObj, Object stepObj, int length, Location loc
+  ) throws EvalException {
+
+    if (!(stepObj instanceof Integer)) {
+      throw new EvalException(loc, "slice step must be an integer");
+    }
+    int step = ((Integer) stepObj).intValue();
     if (step == 0) {
       throw new EvalException(loc, "slice step cannot be zero");
     }
-    int start = getIndex(startObj,
+    int start = getSliceIndex(startObj,
         step,
         /*positiveStepDefault=*/ 0,
         /*negativeStepDefault=*/ length - 1,
         /*length=*/ length,
         loc);
-    int end = getIndex(endObj,
+    int end = getSliceIndex(endObj,
         step,
         /*positiveStepDefault=*/ length,
         /*negativeStepDefault=*/ -1,
@@ -1033,13 +951,13 @@ public class MethodLibrary {
    * <p>If the value is {@code None}, the return value of this methods depends on the sign of the
    * slice step.
    */
-  private static int getIndex(Object value, int step, int positiveStepDefault,
+  private static int getSliceIndex(Object value, int step, int positiveStepDefault,
       int negativeStepDefault, int length, Location loc) throws EvalException {
     if (value == Runtime.NONE) {
       return step < 0 ? negativeStepDefault : positiveStepDefault;
     } else {
       try {
-        return clampIndex(Type.INTEGER.cast(value), length);
+        return MethodLibrary.clampIndex(Type.INTEGER.cast(value), length);
       } catch (ClassCastException ex) {
         throw new EvalException(loc, String.format("'%s' is not a valid int", value));
       }
@@ -1523,93 +1441,6 @@ public class MethodLibrary {
         }
       };
 
-  // dictionary access operator
-  @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkDict.class,
-      doc = "Looks up a value in a dictionary.",
-      parameters = {
-        @Param(name = "self", type = SkylarkDict.class, doc = "This dict."),
-        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
-      useLocation = true, useEnvironment = true)
-  private static final BuiltinFunction dictIndexOperator = new BuiltinFunction("$index") {
-      public Object invoke(SkylarkDict<?, ?> self, Object key,
-        Location loc, Environment env) throws EvalException, ConversionException {
-      if (!self.containsKey(key)) {
-        throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
-      }
-      return SkylarkType.convertToSkylark(self.get(key), env);
-    }
-  };
-
-  // list access operator
-  @SkylarkSignature(
-    name = "$index",
-    documented = false,
-    objectType = MutableList.class,
-    doc = "Returns the nth element of a list.",
-    parameters = {
-      @Param(name = "self", type = MutableList.class, doc = "This list."),
-      @Param(name = "key", type = Integer.class, doc = "The index or key to access.")
-    },
-    useLocation = true,
-    useEnvironment = true
-  )
-  private static final BuiltinFunction listIndexOperator =
-      new BuiltinFunction("$index") {
-        public Object invoke(MutableList<?> self, Integer key, Location loc, Environment env)
-            throws EvalException, ConversionException {
-          if (self.isEmpty()) {
-            throw new EvalException(loc, "List is empty");
-          }
-          int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.get(index), env);
-        }
-      };
-
-  // tuple access operator
-  @SkylarkSignature(
-    name = "$index",
-    documented = false,
-    objectType = Tuple.class,
-    doc = "Returns the nth element of a tuple.",
-    parameters = {
-      @Param(name = "self", type = Tuple.class, doc = "This tuple."),
-      @Param(name = "key", type = Integer.class, doc = "The index or key to access.")
-    },
-    useLocation = true,
-    useEnvironment = true
-  )
-  private static final BuiltinFunction tupleIndexOperator =
-      new BuiltinFunction("$index") {
-        public Object invoke(Tuple<?> self, Integer key, Location loc, Environment env)
-            throws EvalException, ConversionException {
-          if (self.isEmpty()) {
-            throw new EvalException(loc, "tuple is empty");
-          }
-          int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.get(index), env);
-        }
-      };
-
-  @SkylarkSignature(
-    name = "$index",
-    documented = false,
-    objectType = String.class,
-    doc = "Returns the nth element of a string.",
-    parameters = {
-      @Param(name = "self", type = String.class, doc = "This string."),
-      @Param(name = "key", type = Integer.class, doc = "The index or key to access.")
-    },
-    useLocation = true
-  )
-  private static final BuiltinFunction stringIndexOperator =
-      new BuiltinFunction("$index") {
-        public Object invoke(String self, Integer key, Location loc)
-            throws EvalException, ConversionException {
-          int index = getListIndex(key, self.length(), loc);
-          return self.substring(index, index + 1);
-        }
-      };
-
   @SkylarkSignature(name = "values", objectType = SkylarkDict.class,
       returnType = MutableList.class,
       doc = "Returns the list of values. Dictionaries are always sorted by their keys:"
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
index 1e6d9d84ce..ffe9f02afb 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
@@ -707,29 +707,25 @@ public class Parser {
 
   // substring_suffix ::= '[' expression? ':' expression?  ':' expression? ']'
   private Expression parseSubstringSuffix(int start, Expression receiver) {
-    List<Argument.Passed> args = new ArrayList<>();
     Expression startExpr;
 
     expect(TokenKind.LBRACKET);
-    int loc1 = token.left;
     if (token.kind == TokenKind.COLON) {
       startExpr = setLocation(new Identifier("None"), token.left, token.right);
     } else {
       startExpr = parseExpression();
     }
-    args.add(setLocation(new Argument.Positional(startExpr), loc1, startExpr));
-    // This is a dictionary access
+    // This is an index/key access
     if (token.kind == TokenKind.RBRACKET) {
       expect(TokenKind.RBRACKET);
-      return makeFuncallExpression(receiver, new Identifier("$index"), args,
-                                   start, token.right);
+      return setLocation(new IndexExpression(receiver, startExpr), start, token.right);
     }
     // This is a slice (or substring)
-    args.add(parseSliceArgument(new Identifier("None")));
-    args.add(parseSliceArgument(new IntegerLiteral(1)));
+    Expression endExpr = parseSliceArgument(new Identifier("None"));
+    Expression stepExpr = parseSliceArgument(new IntegerLiteral(1));
     expect(TokenKind.RBRACKET);
-    return makeFuncallExpression(receiver, new Identifier("$slice"), args,
-                                 start, token.right);
+    return setLocation(new SliceExpression(receiver, startExpr, endExpr, stepExpr),
+        start, token.right);
   }
 
   /**
@@ -737,11 +733,12 @@ public class Parser {
    * operation. If no such expression is found, this method returns an argument that represents
    * {@code defaultValue}.
    */
-  private Argument.Positional parseSliceArgument(Expression defaultValue) {
+  private Expression parseSliceArgument(Expression defaultValue) {
     Expression explicitArg = getSliceEndOrStepExpression();
-    Expression argValue =
-        (explicitArg == null) ? setLocation(defaultValue, token.left, token.right) : explicitArg;
-    return setLocation(new Argument.Positional(argValue), token.left, argValue);
+    if (explicitArg == null) {
+      return setLocation(defaultValue, token.left, token.right);
+    }
+    return explicitArg;
   }
 
   private Expression getSliceEndOrStepExpression() {
@@ -1073,7 +1070,8 @@ public class Parser {
    * entry in the map.
    */
   private void parseLoadSymbol(Map<Identifier, String> symbols) {
-    Token nameToken, declaredToken;
+    Token nameToken;
+    Token declaredToken;
 
     if (token.kind == TokenKind.STRING) {
       nameToken = token;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
index 254264ea49..49f6c58908 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
@@ -18,10 +18,8 @@ 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.MutableMap;
-
 import java.util.Map;
 import java.util.TreeMap;
-
 import javax.annotation.Nullable;
 
 /**
@@ -46,7 +44,7 @@ import javax.annotation.Nullable;
     + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
     + "</pre>")
 public final class SkylarkDict<K, V>
-    extends MutableMap<K, V> implements Map<K, V> {
+    extends MutableMap<K, V> implements Map<K, V>, SkylarkIndexable {
 
   private TreeMap<K, V> contents = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
 
@@ -217,6 +215,13 @@ public final class SkylarkDict<K, V>
     return (SkylarkDict<KeyType, ValueType>) this;
   }
 
+  @Override
+  public final Object getIndex(Object key, Location loc) throws EvalException {
+    if (!this.containsKey(key)) {
+      throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
+    }
+    return this.get(key);
+  }
 
   public static <K, V> SkylarkDict<K, V> plus(
       SkylarkDict<? extends K, ? extends V> left,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkIndexable.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkIndexable.java
new file mode 100644
index 0000000000..18293f45cb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkIndexable.java
@@ -0,0 +1,28 @@
+// Copyright 2015 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;
+
+/**
+ * Skylark values that support index access, i.e. object[key]
+ */
+public interface SkylarkIndexable {
+
+  /**
+   * Returns the value associated with the given key.
+   */
+  Object getIndex(Object key, Location loc) throws EvalException;
+}
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 de03e0ace5..81cad2f3de 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
@@ -35,7 +35,8 @@ import javax.annotation.Nullable;
   category = SkylarkModuleCategory.BUILTIN,
   doc = "common type of lists and tuples"
 )
-public abstract class SkylarkList<E> extends MutableCollection<E> implements List<E>, RandomAccess {
+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.
@@ -122,6 +123,39 @@ public abstract class SkylarkList<E> extends MutableCollection<E> implements Lis
   }
 
   /**
+   * 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
@@ -131,12 +165,8 @@ public abstract class SkylarkList<E> extends MutableCollection<E> implements Lis
    */
   public void set(Object key, E value, Location loc, Environment env) throws EvalException {
     checkMutable(loc, env);
-    if (!(key instanceof Integer)) {
-      throw new EvalException(loc, "list indices must be integers, not '" + key + '"');
-    }
-    int index = ((Integer) key).intValue();
     List list = getContentsUnsafe();
-    index = MethodLibrary.getListIndex(index, list.size(), loc);
+    int index = MethodLibrary.getListIndex(key, list.size(), loc);
     list.set(index, value);
   }
 
@@ -497,6 +527,20 @@ public abstract class SkylarkList<E> extends MutableCollection<E> implements Lis
       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;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SliceExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/SliceExpression.java
new file mode 100644
index 0000000000..20804ed095
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SliceExpression.java
@@ -0,0 +1,114 @@
+// 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.devtools.build.lib.events.Location;
+import java.util.List;
+
+/** Syntax node for an index expression. e.g. obj[field], but not obj[from:to] */
+public final class SliceExpression extends Expression {
+
+  private final Expression obj;
+  private final Expression start;
+  private final Expression end;
+  private final Expression step;
+
+  public SliceExpression(Expression obj, Expression start, Expression end, Expression step) {
+    this.obj = obj;
+    this.start = start;
+    this.end = end;
+    this.step = step;
+  }
+
+  public Expression getObject() {
+    return obj;
+  }
+
+  public Expression getStart() {
+    return start;
+  }
+
+  public Expression getEnd() {
+    return end;
+  }
+
+  public Expression getStep() {
+    return step;
+  }
+
+  @Override
+  public String toString() {
+    return String.format("%s[%s:%s%s]",
+        obj,
+        start,
+        // Omit `end` if it's a literal `None` (default value)
+        ((end instanceof Identifier) && (((Identifier) end).getName().equals("None"))) ? "" : end,
+        // Omit `step` if it's an integer literal `1` (default value)
+        ((step instanceof IntegerLiteral) && (((IntegerLiteral) step).value.equals(1)))
+            ? "" : ":" + step
+    );
+  }
+
+  @Override
+  Object doEval(Environment env) throws EvalException, InterruptedException {
+    Object objValue = obj.eval(env);
+    Object startValue = start.eval(env);
+    Object endValue = end.eval(env);
+    Object stepValue = step.eval(env);
+    return eval(objValue, startValue, endValue, stepValue, getLocation(), env);
+  }
+
+  /**
+   * Returns the result of the given slice, or null if no such slice is supported.
+   */
+  private Object eval(Object objValue, Object startValue, Object endValue, Object stepValue,
+      Location loc, Environment env) throws EvalException {
+    if (objValue instanceof SkylarkList) {
+      SkylarkList<Object> list = (SkylarkList<Object>) objValue;
+      Object slice = list.getSlice(startValue, endValue, stepValue, loc);
+      return SkylarkType.convertToSkylark(slice, env);
+    } else if (objValue instanceof String) {
+      String string = (String) objValue;
+      List<Integer> indices = MethodLibrary.getSliceIndices(startValue, endValue, stepValue,
+          string.length(), loc);
+      char[] result = new char[indices.size()];
+      char[] original = ((String) objValue).toCharArray();
+      int resultIndex = 0;
+      for (int originalIndex : indices) {
+        result[resultIndex] = original[originalIndex];
+        ++resultIndex;
+      }
+      return new String(result);
+    }
+
+    throw new EvalException(
+        loc,
+        Printer.format(
+            "Type %s has no operator [:](%s, %s, %s)",
+            EvalUtils.getDataTypeName(objValue),
+            EvalUtils.getDataTypeName(startValue),
+            EvalUtils.getDataTypeName(endValue),
+            EvalUtils.getDataTypeName(stepValue)));
+  }
+
+  @Override
+  public void accept(SyntaxTreeVisitor visitor) {
+    visitor.visit(this);
+  }
+
+  @Override
+  void validate(ValidationEnvironment env) throws EvalException {
+    obj.validate(env);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SyntaxTreeVisitor.java b/src/main/java/com/google/devtools/build/lib/syntax/SyntaxTreeVisitor.java
index d29391a6b4..d18615c61c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SyntaxTreeVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SyntaxTreeVisitor.java
@@ -144,6 +144,18 @@ public class SyntaxTreeVisitor {
     visit(node.getField());
   }
 
+  public void visit(IndexExpression node) {
+    visit(node.getObject());
+    visit(node.getKey());
+  }
+
+  public void visit(SliceExpression node) {
+    visit(node.getObject());
+    visit(node.getStart());
+    visit(node.getEnd());
+    visit(node.getStep());
+  }
+
   public void visit(@SuppressWarnings("unused") Comment node) {}
 
   public void visit(ConditionalExpression node) {