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 {