Skylark: Slice operations now accept a step argument.
--
MOS_MIGRATED_REVID=110446625
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 3c272ac..3cf6113 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
@@ -33,6 +33,7 @@
import com.google.devtools.build.lib.syntax.Type.ConversionException;
import java.util.ArrayList;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
@@ -921,57 +922,162 @@
};
// slice operator
- @SkylarkSignature(name = "$slice", objectType = String.class,
- documented = false,
- mandatoryPositionals = {
- @Param(name = "self", type = String.class, doc = "This string."),
- @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
- @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
- doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.")
- private static BuiltinFunction stringSlice = new BuiltinFunction("$slice") {
- public Object invoke(String self, Integer left, Integer right)
- throws EvalException, ConversionException {
- return pythonSubstring(self, left, right, "");
- }
- };
+ @SkylarkSignature(
+ name = "$slice",
+ objectType = String.class,
+ documented = false,
+ mandatoryPositionals = {
+ @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.")
+ },
+ optionalPositionals = {
+ @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 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,
- mandatoryPositionals = {
- @Param(name = "self", type = MutableList.class, doc = "This list."),
- @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
- @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
- doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
- useEnvironment = true)
- private static BuiltinFunction mutableListSlice = new BuiltinFunction("$slice") {
- public MutableList invoke(MutableList self, Integer left, Integer right,
- Environment env) throws EvalException, ConversionException {
- return new MutableList(sliceList(self.getList(), left, right), env);
- }
- };
+ @SkylarkSignature(
+ name = "$slice",
+ objectType = MutableList.class,
+ returnType = MutableList.class,
+ documented = false,
+ mandatoryPositionals = {
+ @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.")
+ },
+ optionalPositionals = {
+ @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 BuiltinFunction mutableListSlice =
+ new BuiltinFunction("$slice") {
+ @SuppressWarnings("unused") // Accessed via Reflection.
+ public MutableList invoke(
+ 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);
+ }
+ };
- @SkylarkSignature(name = "$slice", objectType = Tuple.class, returnType = Tuple.class,
- documented = false,
- mandatoryPositionals = {
- @Param(name = "self", type = Tuple.class, doc = "This tuple."),
- @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
- @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
- doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
- useEnvironment = true)
- private static BuiltinFunction tupleSlice = new BuiltinFunction("$slice") {
- public Tuple invoke(Tuple self, Integer left, Integer right,
- Environment env) throws EvalException, ConversionException {
- return Tuple.copyOf(sliceList(self.getList(), left, right));
+ @SkylarkSignature(
+ name = "$slice",
+ objectType = Tuple.class,
+ returnType = Tuple.class,
+ documented = false,
+ mandatoryPositionals = {
+ @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.")
+ },
+ optionalPositionals = {
+ @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 BuiltinFunction tupleSlice =
+ new BuiltinFunction("$slice") {
+ @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));
+ }
+ };
+
+ 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 {
+ if (step == 0) {
+ throw new EvalException(loc, "slice step cannot be zero");
+ }
+ int start = getIndex(startObj,
+ step,
+ /*positiveStepDefault=*/ 0,
+ /*negativeStepDefault=*/ length - 1,
+ /*length=*/ length,
+ loc);
+ int end = getIndex(endObj,
+ step,
+ /*positiveStepDefault=*/ length,
+ /*negativeStepDefault=*/ -1,
+ /*length=*/ length,
+ loc);
+ Comparator<Integer> comparator = getOrderingForStep(step);
+ ImmutableList.Builder<Integer> indices = ImmutableList.builder();
+ for (int current = start; comparator.compare(current, end) < 0; current += step) {
+ indices.add(current);
+ }
+ return indices.build();
+ }
+
+ /**
+ * Converts the given value into an integer index.
+ *
+ * <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,
+ 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);
+ } catch (ClassCastException ex) {
+ throw new EvalException(loc, String.format("'%s' is not a valid int", value));
}
- };
-
- private static List<Object> sliceList(List<Object> list, Integer left, Integer right) {
- left = clampIndex(left, list.size());
- right = clampIndex(right, list.size());
- if (left > right) {
- left = right;
}
- return list.subList(left, right);
+ }
+
+ private static Ordering<Integer> getOrderingForStep(int step) {
+ Ordering<Integer> ordering = Ordering.<Integer>natural();
+ if (step < 0) {
+ ordering = ordering.reverse();
+ }
+ return ordering;
}
@SkylarkSignature(
@@ -1871,22 +1977,28 @@
/**
* Skylark String module.
*/
- @SkylarkModule(name = "string", doc =
- "A language built-in type to support strings. "
- + "Examples of string literals:<br>"
- + "<pre class=\"language-python\">a = 'abc\\ndef'\n"
- + "b = \"ab'cd\"\n"
- + "c = \"\"\"multiline string\"\"\"\n"
- + "\n"
- + "# Strings support slicing (negative index starts from the end):\n"
- + "x = \"hello\"[2:4] # \"ll\"\n"
- + "y = \"hello\"[1:-1] # \"ell\"\n"
- + "z = \"hello\"[:4] # \"hell\"</pre>"
- + "Strings are iterable and support the <code>in</code> operator. Examples:<br>"
- + "<pre class=\"language-python\">\"bc\" in \"abcd\" # evaluates to True\n"
- + "x = [s for s in \"abc\"] # x == [\"a\", \"b\", \"c\"]</pre>\n"
- + "Implicit concatenation of strings is not allowed; use the <code>+</code> "
- + "operator instead.")
+ @SkylarkModule(
+ name = "string",
+ doc =
+ "A language built-in type to support strings. "
+ + "Examples of string literals:<br>"
+ + "<pre class=\"language-python\">a = 'abc\\ndef'\n"
+ + "b = \"ab'cd\"\n"
+ + "c = \"\"\"multiline string\"\"\"\n"
+ + "\n"
+ + "# Strings support slicing (negative index starts from the end):\n"
+ + "x = \"hello\"[2:4] # \"ll\"\n"
+ + "y = \"hello\"[1:-1] # \"ell\"\n"
+ + "z = \"hello\"[:4] # \"hell\""
+ + "# Slice steps can be used, too:\n"
+ + "s = \"hello\"[::2] # \"hlo\"\n"
+ + "t = \"hello\"[3:0:-1] # \"lle\"\n</pre>"
+ + "Strings are iterable and support the <code>in</code> operator. Examples:<br>"
+ + "<pre class=\"language-python\">\"bc\" in \"abcd\" # evaluates to True\n"
+ + "x = [s for s in \"abc\"] # x == [\"a\", \"b\", \"c\"]</pre>\n"
+ + "Implicit concatenation of strings is not allowed; use the <code>+</code> "
+ + "operator instead."
+ )
static final class StringModule {}
/**
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 1214d8d..c5f612f 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
@@ -713,16 +713,15 @@
return receiver;
}
- // substring_suffix ::= '[' expression? ':' expression? ']'
+ // substring_suffix ::= '[' expression? ':' expression? ':' expression? ']'
private Expression parseSubstringSuffix(int start, Expression receiver) {
List<Argument.Passed> args = new ArrayList<>();
Expression startExpr;
- Expression endExpr;
expect(TokenKind.LBRACKET);
int loc1 = token.left;
if (token.kind == TokenKind.COLON) {
- startExpr = setLocation(new IntegerLiteral(0), token.left, token.right);
+ startExpr = setLocation(new Identifier("None"), token.left, token.right);
} else {
startExpr = parseExpression();
}
@@ -734,20 +733,38 @@
start, token.right);
}
// This is a slice (or substring)
- expect(TokenKind.COLON);
- int loc2 = token.left;
- if (token.kind == TokenKind.RBRACKET) {
- endExpr = setLocation(new IntegerLiteral(Integer.MAX_VALUE), token.left, token.right);
- } else {
- endExpr = parseNonTupleExpression();
- }
+ args.add(parseSliceArgument(new Identifier("None")));
+ args.add(parseSliceArgument(new IntegerLiteral(1)));
expect(TokenKind.RBRACKET);
-
- args.add(setLocation(new Argument.Positional(endExpr), loc2, endExpr));
return makeFuncallExpression(receiver, new Identifier("$slice"), args,
start, token.right);
}
+ /**
+ * Parses {@code [':' [expr]]} which can either be the end or the step argument of a slice
+ * operation. If no such expression is found, this method returns an argument that represents
+ * {@code defaultValue}.
+ */
+ private Argument.Positional 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);
+ }
+
+ private Expression getSliceEndOrStepExpression() {
+ // There has to be a colon before any end or slice argument.
+ // However, if the next token thereafter is another colon or a right bracket, no argument value
+ // was specified.
+ if (token.kind == TokenKind.COLON) {
+ expect(TokenKind.COLON);
+ if (token.kind != TokenKind.COLON && token.kind != TokenKind.RBRACKET) {
+ return parseNonTupleExpression();
+ }
+ }
+ return null;
+ }
+
// Equivalent to 'exprlist' rule in Python grammar.
// loop_variables ::= primary_with_suffix ( ',' primary_with_suffix )* ','?
private Expression parseForLoopVariables() {
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 97cdd4e..1f88c4b 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
@@ -168,16 +168,23 @@
/**
* A class for mutable lists.
*/
- @SkylarkModule(name = "list",
- 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>"
- + "Lists are mutable, as in Python.")
+ @SkylarkModule(
+ name = "list",
+ 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 extends SkylarkList implements Freezable {
private final ArrayList<Object> contents = new ArrayList<>();
@@ -371,16 +378,23 @@
/**
* An immutable tuple, e.g. in (1, 2, 3)
*/
- @SkylarkModule(name = "tuple",
- 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>"
- + "Tuples are immutable, therefore <code>x[1] = \"a\"</code> is not supported.")
+ @SkylarkModule(
+ name = "tuple",
+ 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."
+ )
@Immutable
public static final class Tuple extends SkylarkList {
