diff options
author | Jon Brandvein <brandjon@google.com> | 2016-11-11 16:27:01 +0000 |
---|---|---|
committer | Kristina Chodorow <kchodorow@google.com> | 2016-11-14 14:51:36 +0000 |
commit | fab84872276291dc8ed24e1638f743595df0e722 (patch) | |
tree | 39dc40821a4c49fbef7e2d790eac3f68157a28c3 /src/main/java/com | |
parent | 8d10221f7e990253f24a37555d043a9a959371eb (diff) |
Fix bugs in slicing with a negative stride
There was a crash when the starting point of a negative slice is larger than
the list length.
In addition, there was an incorrect result when the ending point of a negative
slice is less than the list's length times -1. It would wrongly exclude the
first element.
RELNOTES: Fix slicing bug where "abc"[:-4:-1] would give wrong answer
--
MOS_MIGRATED_REVID=138878716
Diffstat (limited to 'src/main/java/com')
5 files changed, 134 insertions, 106 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java index f9f2f62a88..c83ed98793 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java @@ -381,6 +381,130 @@ public final class EvalUtils { return -1; } + // The following functions for indexing and slicing match the behavior of Python. + + /** + * Resolves a positive or negative index to an index in the range [0, length), or throws + * EvalException if it is out-of-range. If the index is negative, it counts backward from + * length. + */ + public static int getSequenceIndex(int index, int length, Location loc) + throws EvalException { + int actualIndex = index; + if (actualIndex < 0) { + actualIndex += length; + } + if (actualIndex < 0 || actualIndex >= length) { + throw new EvalException(loc, "Index out of range (index is " + + index + ", but sequence has " + length + " elements)"); + } + return actualIndex; + } + + /** + * Performs index resolution after verifying that the given object has index type. + */ + public static int getSequenceIndex(Object index, int length, Location loc) + throws EvalException { + if (!(index instanceof Integer)) { + throw new EvalException(loc, "Indices must be integers, not " + + EvalUtils.getDataTypeName(index)); + } + return getSequenceIndex(((Integer) index).intValue(), length, loc); + } + + /** + * Resolves a positive or negative index to an integer that can denote the left or right boundary + * of a slice. If reverse is false, the slice has positive stride (i.e., its elements are in their + * normal order) and the result is guaranteed to be in range [0, length + 1). If reverse is true, + * the slice has negative stride and the result is in range [-1, length). In either case, if the + * index is negative, it counts backward from length. Note that an input index of -1 represents + * the last element's position, while an output integer of -1 represents the imaginary position + * to the left of the first element. + */ + public static int clampRangeEndpoint(int index, int length, boolean reverse) { + if (index < 0) { + index += length; + } + if (!reverse) { + return Math.max(Math.min(index, length), 0); + } else { + return Math.max(Math.min(index, length - 1), -1); + } + } + + /** + * Resolves a positive or negative index to an integer that can denote the boundary for a + * slice with positive stride. + */ + public static int clampRangeEndpoint(int index, int length) { + return clampRangeEndpoint(index, length, false); + } + + /** + * Calculates the indices of the elements that should be included in the slice [start:end:step] + * of a sequence with the given length. Each of start, end, and step must be supplied, and step + * may not be 0. + */ + public static List<Integer> getSliceIndices(int start, int end, int step, int length) { + if (step == 0) { + throw new IllegalArgumentException("Slice step cannot be zero"); + } + start = clampRangeEndpoint(start, length, step < 0); + end = clampRangeEndpoint(end, length, step < 0); + ImmutableList.Builder<Integer> indices = ImmutableList.builder(); + for (int current = start; step > 0 ? current < end : current > end; current += step) { + indices.add(current); + } + return indices.build(); + } + + /** + * Calculates the indices of the elements in a slice, after validating the arguments and replacing + * Runtime.NONE with default values. Throws an EvalException if a bad argument is given. + */ + public static List<Integer> getSliceIndices( + Object startObj, Object endObj, Object stepObj, int length, Location loc) + throws EvalException { + int start; + int end; + int step; + + if (stepObj == Runtime.NONE) { + // This case is excluded by the parser, but let's handle it for completeness. + step = 1; + } else if (stepObj instanceof Integer) { + step = ((Integer) stepObj).intValue(); + } else { + throw new EvalException(loc, + String.format("Slice step must be an integer, not '%s'", stepObj)); + } + if (step == 0) { + throw new EvalException(loc, "Slice step cannot be zero"); + } + + if (startObj == Runtime.NONE) { + start = (step > 0) ? 0 : length - 1; + } else if (startObj instanceof Integer) { + start = ((Integer) startObj).intValue(); + } else { + throw new EvalException(loc, + String.format("Slice start must be an integer, not '%s'", startObj)); + } + if (endObj == Runtime.NONE) { + // If step is negative, can't use -1 for end since that would be converted + // to the rightmost element's position. + end = (step > 0) ? length : -length - 1; + } else if (endObj instanceof Integer) { + end = ((Integer) endObj).intValue(); + } else { + throw new EvalException(loc, + String.format("Slice end must be an integer, not '%s'", endObj)); + } + + return getSliceIndices(start, end, step, length); + } + /** @return true if x is Java null or Skylark None */ public static boolean isNullOrNone(Object x) { return x == null || x == Runtime.NONE; 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 index 32114ada7e..575a7d2de1 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/IndexExpression.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/IndexExpression.java @@ -51,7 +51,7 @@ public final class IndexExpression extends Expression { return SkylarkType.convertToSkylark(result, env); } else if (objValue instanceof String) { String string = (String) objValue; - int index = MethodLibrary.getListIndex(keyValue, string.length(), loc); + int index = EvalUtils.getSequenceIndex(keyValue, string.length(), loc); return string.substring(index, index + 1); } 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 ee00adbca3..6157e7cafe 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,7 +33,6 @@ import com.google.devtools.build.lib.syntax.SkylarkList.MutableList; import com.google.devtools.build.lib.syntax.SkylarkList.Tuple; import com.google.devtools.build.lib.syntax.Type.ConversionException; import java.util.ArrayList; -import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.List; @@ -52,16 +51,6 @@ public class MethodLibrary { private 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. - public static int clampIndex(int index, int length) { - if (index < 0) { - index += length; - } - return Math.max(Math.min(index, length), 0); - } - // Emulate Python substring function // It converts out of range indices, and never fails private static String pythonSubstring(String str, int start, Object end, String msg) @@ -69,12 +58,12 @@ public class MethodLibrary { if (start == 0 && EvalUtils.isNullOrNone(end)) { return str; } - start = clampIndex(start, str.length()); + start = EvalUtils.clampRangeEndpoint(start, str.length()); int stop; if (EvalUtils.isNullOrNone(end)) { stop = str.length(); } else { - stop = clampIndex(Type.INTEGER.convert(end, msg), str.length()); + stop = EvalUtils.clampRangeEndpoint(Type.INTEGER.convert(end, msg), str.length()); } if (start >= stop) { return ""; @@ -82,29 +71,6 @@ public class MethodLibrary { return str.substring(start, stop); } - private static int getListIndex(int index, int listSize, Location loc) - throws EvalException { - // Get the nth element in the list - int actualIndex = index; - if (actualIndex < 0) { - actualIndex += listSize; - } - if (actualIndex < 0 || actualIndex >= listSize) { - throw new EvalException(loc, "List index out of range (index is " - + index + ", but list has " + listSize + " elements)"); - } - 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 @SkylarkSignature(name = "join", objectType = StringModule.class, returnType = String.class, @@ -576,7 +542,7 @@ public class MethodLibrary { throws ConversionException { String substr = pythonSubstring(self, start, end, msg); int subpos = forward ? substr.indexOf(sub) : substr.lastIndexOf(sub); - start = clampIndex(start, self.length()); + start = EvalUtils.clampRangeEndpoint(start, self.length()); return subpos < 0 ? subpos : subpos + start; } @@ -994,68 +960,6 @@ public class MethodLibrary { } }; - /** - * Calculates the indices of the elements that should be included in the slice [start:end:step] - * of a sequence with the given length. - */ - 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 = getSliceIndex(startObj, - step, - /*positiveStepDefault=*/ 0, - /*negativeStepDefault=*/ length - 1, - /*length=*/ length, - loc); - int end = getSliceIndex(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 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 MethodLibrary.clampIndex(Type.INTEGER.cast(value), length); - } catch (ClassCastException ex) { - throw new EvalException(loc, String.format("'%s' is not a valid int", value)); - } - } - } - - private static Ordering<Integer> getOrderingForStep(int step) { - Ordering<Integer> ordering = Ordering.<Integer>natural(); - if (step < 0) { - ordering = ordering.reverse(); - } - return ordering; - } - @SkylarkSignature( name = "min", returnType = Object.class, @@ -1255,7 +1159,7 @@ public class MethodLibrary { public Runtime.NoneType invoke( MutableList<Object> self, Integer index, Object item, Location loc, Environment env) throws EvalException { - self.add(clampIndex(index, self.size()), item, loc, env); + self.add(EvalUtils.clampRangeEndpoint(index, self.size()), item, loc, env); return Runtime.NONE; } }; @@ -1363,7 +1267,7 @@ public class MethodLibrary { public Object invoke(MutableList<?> self, Object i, Location loc, Environment env) throws EvalException { int arg = i == Runtime.NONE ? -1 : (Integer) i; - int index = getListIndex(arg, self.size(), loc); + int index = EvalUtils.getSequenceIndex(arg, self.size(), loc); Object result = self.get(index); self.remove(index, loc, env); return result; 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 1c1c52b6bb..1221aa67cc 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 @@ -132,7 +132,7 @@ public abstract class SkylarkList<E> extends MutableCollection<E> implements Lis @Override public final E getIndex(Object key, Location loc) throws EvalException { List<E> list = getContentsUnsafe(); - int index = MethodLibrary.getListIndex(key, list.size(), loc); + int index = EvalUtils.getSequenceIndex(key, list.size(), loc); return list.get(index); } @@ -159,7 +159,7 @@ public abstract class SkylarkList<E> extends MutableCollection<E> implements Lis List<E> list = getContentsUnsafe(); int length = list.size(); ImmutableList.Builder<E> slice = ImmutableList.builder(); - for (int pos : MethodLibrary.getSliceIndices(start, end, step, length, loc)) { + for (int pos : EvalUtils.getSliceIndices(start, end, step, length, loc)) { slice.add(list.get(pos)); } return slice.build(); @@ -176,7 +176,7 @@ 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); List list = getContentsUnsafe(); - int index = MethodLibrary.getListIndex(key, list.size(), loc); + int index = EvalUtils.getSequenceIndex(key, list.size(), loc); list.set(index, value); } 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 index 0647e2942c..f7c36e5a7a 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/SliceExpression.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/SliceExpression.java @@ -74,7 +74,7 @@ public final class SliceExpression extends Expression { return SkylarkType.convertToSkylark(slice, env); } else if (objValue instanceof String) { String string = (String) objValue; - List<Integer> indices = MethodLibrary.getSliceIndices(startValue, endValue, stepValue, + List<Integer> indices = EvalUtils.getSliceIndices(startValue, endValue, stepValue, string.length(), loc); char[] result = new char[indices.size()]; char[] original = ((String) objValue).toCharArray(); |