From 9de215db31bc6e8f4becf7058d33fe1d82b0ac9f Mon Sep 17 00:00:00 2001 From: Taras Tsugrii Date: Tue, 17 Jul 2018 08:56:13 -0700 Subject: [Skylark] Make range function lazy. range used to use MutableList which would eagerly allocate an array list with all range elements, which is not efficient for very large ranges or when only a small number of its elements are used. This implementation uses a constant amount of RAM and computes a value for each requested index. For the following Skylark snippet: ``` def check_content(t): if t == []: return t return False def modulo(n): return n % 797 N = 10000000 [check_content(i) for i in range(N)] [check_content(i) for i in range(N)] [modulo(i) for i in range(N)] [modulo(i) for i in range(N)] ``` the total runtime goes from ``` $ time bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl 93.09s user 1.67s system 316% cpu 29.930 total ``` to ``` $ time bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl bazel-bin/src/main/java/com/google/devtools/skylark/Skylark test.bzl 31.45s user 0.86s system 179% cpu 17.974 total ``` which reflects the reduced system time (fewer allocations) and performance. Closes #5240. PiperOrigin-RevId: 204918577 --- site/docs/skylark/backward-compatibility.md | 9 + .../build/lib/packages/SkylarkSemanticsCodec.java | 2 + .../lib/packages/SkylarkSemanticsOptions.java | 13 + .../build/lib/syntax/BinaryOperatorExpression.java | 2 +- .../devtools/build/lib/syntax/MethodLibrary.java | 85 +++--- .../devtools/build/lib/syntax/RangeList.java | 332 +++++++++++++++++++++ .../devtools/build/lib/syntax/SkylarkList.java | 7 +- .../build/lib/syntax/SkylarkSemantics.java | 5 + .../packages/SkylarkSemanticsConsistencyTest.java | 2 + .../build/lib/syntax/MethodLibraryTest.java | 53 ++++ 10 files changed, 456 insertions(+), 54 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/syntax/RangeList.java diff --git a/site/docs/skylark/backward-compatibility.md b/site/docs/skylark/backward-compatibility.md index aac35278ce..6c27fa676c 100644 --- a/site/docs/skylark/backward-compatibility.md +++ b/site/docs/skylark/backward-compatibility.md @@ -231,6 +231,15 @@ no user-visible impact. * Default: `true` +### Python 3 range behavior. +When set, the result of `range(...)` function is a lazy `range` type instead of +a `list`. Because of this repetitions using `*` operator are no longer +supported and `range` slices are also lazy `range` instances. + +* Flag: `--incompatible_range_type` +* Default: `false` + + ### Disable objc provider resources This flag disables certain deprecated resource fields on diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java index a8647a8d6e..2b983e4653 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java +++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsCodec.java @@ -59,6 +59,7 @@ public final class SkylarkSemanticsCodec implements ObjectCodec) otherFactor).repeat(number, env.mutability()); } 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 cbf8ce4e17..d6bd668f85 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 @@ -620,45 +620,41 @@ public class MethodLibrary { }; @SkylarkSignature( - name = "range", - returnType = MutableList.class, - doc = - "Creates a list where items go from start to stop, using a " - + "step increment. If a single argument is provided, items will " - + "range from 0 to that element." - + "
range(4) == [0, 1, 2, 3]\n"
-            + "range(3, 9, 2) == [3, 5, 7]\n"
-            + "range(3, 0, -1) == [3, 2, 1]
", - parameters = { - @Param( - name = "start_or_stop", - type = Integer.class, - doc = - "Value of the start element if stop is provided, " - + "otherwise value of stop and the actual start is 0" - ), - @Param( - name = "stop_or_none", - type = Integer.class, - noneable = true, - defaultValue = "None", - doc = - "optional index of the first item not to be included in the resulting " - + "list; generation of the list stops before stop is reached." - ), - @Param( - name = "step", - type = Integer.class, - defaultValue = "1", - doc = "The increment (default is 1). It may be negative." - ) - }, - useLocation = true, - useEnvironment = true - ) + name = "range", + returnType = SkylarkList.class, + doc = + "Creates a list where items go from start to stop, using a " + + "step increment. If a single argument is provided, items will " + + "range from 0 to that element." + + "
range(4) == [0, 1, 2, 3]\n"
+              + "range(3, 9, 2) == [3, 5, 7]\n"
+              + "range(3, 0, -1) == [3, 2, 1]
", + parameters = { + @Param( + name = "start_or_stop", + type = Integer.class, + doc = + "Value of the start element if stop is provided, " + + "otherwise value of stop and the actual start is 0"), + @Param( + name = "stop_or_none", + type = Integer.class, + noneable = true, + defaultValue = "None", + doc = + "optional index of the first item not to be included in the resulting " + + "list; generation of the list stops before stop is reached."), + @Param( + name = "step", + type = Integer.class, + defaultValue = "1", + doc = "The increment (default is 1). It may be negative.") + }, + useLocation = true, + useEnvironment = true) private static final BuiltinFunction range = new BuiltinFunction("range") { - public MutableList invoke( + public SkylarkList invoke( Integer startOrStop, Object stopOrNone, Integer step, Location loc, Environment env) throws EvalException { int start; @@ -673,19 +669,8 @@ public class MethodLibrary { if (step == 0) { throw new EvalException(loc, "step cannot be 0"); } - ArrayList result = new ArrayList<>(Math.abs((stop - start) / step)); - if (step > 0) { - while (start < stop) { - result.add(start); - start += step; - } - } else { - while (start > stop) { - result.add(start); - start += step; - } - } - return MutableList.wrapUnsafe(env, result); + RangeList range = RangeList.of(start, stop, step); + return env.getSemantics().incompatibleRangeType() ? range : range.toMutableList(env); } }; diff --git a/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java b/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java new file mode 100644 index 0000000000..f93a729ae4 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/syntax/RangeList.java @@ -0,0 +1,332 @@ +// Copyright 2018 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.common.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.UnmodifiableIterator; +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.skylarkinterface.SkylarkPrinter; +import java.util.AbstractList; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +/** + * A sequence returned by the {@code range} function invocation. + * + *

Instead of eagerly allocating an array with all elements of the sequence, this class uses + * simple math to compute a value at each index. This is particularly useful when range is huge or + * only a few elements from it are used. + * + *

Eventually {@code range} function should produce an instance of the {@code range} type as is + * the case in Python 3, but for now to preserve backwards compatibility with Python 2, {@code list} + * is returned. + */ +@SkylarkModule( + name = "range", + category = SkylarkModuleCategory.BUILTIN, + doc = + "A language built-in type to support ranges. Example of range literal:
" + + "

x = range(1, 10, 3)
" + + "Accessing elements is possible using indexing (starts from 0):
" + + "
e = x[1]   # e == 2
" + + "Ranges do not support the + operator for concatenation." + + "Similar to strings, ranges support slice operations:" + + "
range(10)[1:3]   # range(1, 3)\n"
+            + "range(10)[::2]  # range(0, 10, 2)\n"
+            + "range(10)[3:0:-1]  # range(3, 0, -1)
" + + "Ranges are immutable, as in Python 3.") +public final class RangeList extends SkylarkList { + + private final int step; + private final int start; + + private static int computeItem(int start, int step, int index) { + return start + step * index; + } + + /** Provides access to range elements based on their index. */ + private static class RangeListView extends AbstractList { + + /** Iterator for increasing/decreasing sequences. */ + private static class RangeListIterator extends UnmodifiableIterator { + private final int stop; + private final int step; + + private int cursor; + + private RangeListIterator(int start, int stop, int step) { + this.cursor = start; + this.stop = stop; + this.step = step; + } + + @Override + public boolean hasNext() { + return (step > 0) ? cursor < stop : cursor > stop; + } + + @Override + public Integer next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + int current = cursor; + cursor += step; + return current; + } + } + + /** + * @return The size of the range specified by {@code start}, {@code stop} and {@code step}. + * Python version: + * https://github.com/python/cpython/blob/09bb918a61031377d720f1a0fa1fe53c962791b6/Objects/rangeobject.c#L144 + */ + private static int computeSize(int start, int stop, int step) { + // low and high represent bounds of the interval with only one of the sides being open. + int low; + int high; + if (step > 0) { + low = start; + high = stop; + } else { + low = stop; + high = start; + step = -step; + } + if (low >= high) { + return 0; + } + + int diff = high - low - 1; + return diff / step + 1; + } + + private final int start; + private final int stop; + private final int step; + private final int size; + + private RangeListView(int start, int stop, int step) { + this.start = start; + this.stop = stop; + this.step = step; + this.size = computeSize(start, stop, step); + } + + @Override + public Integer get(int index) { + if (index < 0 || index >= size()) { + throw new ArrayIndexOutOfBoundsException(index); + } + return computeItem(start, step, index); + } + + @Override + public int size() { + return size; + } + + /** + * Returns an iterator optimized for traversing range elements, since it's the most frequent + * operation for which ranges are used. + */ + @Override + public Iterator iterator() { + return new RangeListIterator(start, stop, step); + } + + /** @return the start of the range. */ + public int getStart() { + return start; + } + + /** @return the stop element (next after the last one) of the range. */ + public int getStop() { + return stop; + } + + /** @return the step between each element of the range. */ + public int getStep() { + return step; + } + } + + private final RangeListView contents; + + private RangeList(int start, int stop, int step) { + this.step = step; + this.start = start; + this.contents = new RangeListView(start, stop, step); + } + + @Override + public boolean isTuple() { + return false; + } + + @Override + public ImmutableList getImmutableList() { + return ImmutableList.copyOf(contents); + } + + @Override + public SkylarkList getSlice( + Object start, Object end, Object step, Location loc, Mutability mutability) + throws EvalException { + Slice slice = Slice.from(size(), start, end, step, loc); + int substep = slice.step * this.step; + int substart = computeItem(this.start, this.step, slice.start); + int substop = computeItem(this.start, this.step, slice.stop); + return RangeList.of(substart, substop, substep); + } + + @Override + public SkylarkList repeat(int times, Mutability mutability) { + throw new UnsupportedOperationException("Ranges do not support repetition."); + } + + @Override + protected List getContentsUnsafe() { + return contents; + } + + @Override + public Mutability mutability() { + return Mutability.IMMUTABLE; + } + + @Override + public void repr(SkylarkPrinter printer) { + if (contents.getStep() == 1) { + printer.format("range(%d, %d)", contents.getStart(), contents.getStop()); + } else { + printer.format( + "range(%d, %d, %d)", contents.getStart(), contents.getStop(), contents.getStep()); + } + } + + /** + * Converts this range sequence into a materialized list. + * + *

Usage of this method is not recommended, since it completely defeats the purpose of lazy + * computation by eagerly computing the result. + * + * @return A materialized version of the range that can be used as a + * 

list
+ * type. + */ + MutableList toMutableList(Environment env) { + return MutableList.copyOf(env, contents); + } + + /** + * @return A half-opened range defined by its starting value (inclusive), stop value (exclusive) + * and a step from previous value to the next one. + */ + public static RangeList of(int start, int stop, int step) { + Preconditions.checkArgument(step != 0); + return new RangeList(start, stop, step); + } + + /** + * Represents a slice produced by applying {@code [start:end:step]} to a {@code range}. + * + *

{@code start} and {@code stop} define a half-open interval + * + * 

[start, stop)
+ */ + private static class Slice { + + private final int start; + private final int stop; + private final int step; + + private Slice(int start, int stop, int step) { + this.start = start; + this.stop = stop; + this.step = step; + } + + /** + * Computes slice indices for the requested range slice. + * + *

The implementation is based on CPython + * https://github.com/python/cpython/blob/09bb918a61031377d720f1a0fa1fe53c962791b6/Objects/sliceobject.c#L366-L509 + */ + public static Slice from( + int length, Object startObj, Object endObj, Object stepObj, Location loc) + throws EvalException { + int start; + int stop; + int step; + + if (stepObj == Runtime.NONE) { + step = 1; + } else if (stepObj instanceof Integer) { + step = (Integer) stepObj; + } 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"); + } + + int upper; // upper bound for stop (exclusive) + int lower; // lower bound for start (inclusive) + if (step < 0) { + lower = -1; + upper = length - 1; + } else { + lower = 0; + upper = length; + } + + if (startObj == Runtime.NONE) { + start = step < 0 ? upper : lower; + } else if (startObj instanceof Integer) { + start = (Integer) startObj; + if (start < 0) { + start += length; + start = Math.max(start, lower); + } else { + start = Math.min(start, upper); + } + } else { + throw new EvalException( + loc, String.format("slice start must be an integer, not '%s'", startObj)); + } + if (endObj == Runtime.NONE) { + stop = step < 0 ? lower : upper; + } else if (endObj instanceof Integer) { + stop = (Integer) endObj; + if (stop < 0) { + stop += length; + stop = Math.max(stop, lower); + } else { + stop = Math.min(stop, upper); + } + } else { + throw new EvalException( + loc, String.format("slice end must be an integer, not '%s'", endObj)); + } + return new Slice(start, stop, step); + } + } +} 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 6be38d5f8f..8900397476 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 @@ -116,7 +116,8 @@ public abstract class SkylarkList extends BaseMutableList @Override public boolean equals(Object object) { return (this == object) - || ((object != null) && (this.getClass() == object.getClass()) + || ((object != null) + && (this.getClass() == object.getClass()) && getContentsUnsafe().equals(((SkylarkList) object).getContentsUnsafe())); } @@ -345,7 +346,7 @@ public abstract class SkylarkList extends BaseMutableList return new MutableList<>(newContents, mutability); } - /** More efficient {@link List#addAll} replacement when both lists are {@link ArrayList}s. */ + /** More efficient {@link List#addAll} replacement when both lists are {@link ArrayList}s. */ private static void addAll(ArrayList addTo, ArrayList addFrom) { // Hot code path, skip iterator. for (int i = 0; i < addFrom.size(); i++) { @@ -614,7 +615,7 @@ public abstract class SkylarkList extends BaseMutableList * Creates a {@code Tuple} from an {@link ImmutableList}, reusing the empty instance if * applicable. */ - private static Tuple create(ImmutableList contents) { + private static Tuple create(ImmutableList contents) { if (contents.isEmpty()) { return empty(); } diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java index fc7afa45ca..814a847081 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSemantics.java @@ -71,6 +71,8 @@ public abstract class SkylarkSemantics { public abstract boolean incompatiblePackageNameIsAFunction(); + public abstract boolean incompatibleRangeType(); + public abstract boolean incompatibleRemoveNativeGitRepository(); public abstract boolean incompatibleRemoveNativeHttpArchive(); @@ -110,6 +112,7 @@ public abstract class SkylarkSemantics { .incompatibleNewActionsApi(false) .incompatibleNoSupportToolsInActionInputs(false) .incompatiblePackageNameIsAFunction(false) + .incompatibleRangeType(false) .incompatibleRemoveNativeGitRepository(false) .incompatibleRemoveNativeHttpArchive(false) .incompatibleStringIsNotIterable(false) @@ -153,6 +156,8 @@ public abstract class SkylarkSemantics { public abstract Builder incompatiblePackageNameIsAFunction(boolean value); + public abstract Builder incompatibleRangeType(boolean value); + public abstract Builder incompatibleRemoveNativeGitRepository(boolean value); public abstract Builder incompatibleRemoveNativeHttpArchive(boolean value); diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java index a96d928283..893d5d44a5 100644 --- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java +++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java @@ -135,6 +135,7 @@ public class SkylarkSemanticsConsistencyTest { "--incompatible_new_actions_api=" + rand.nextBoolean(), "--incompatible_no_support_tools_in_action_inputs=" + rand.nextBoolean(), "--incompatible_package_name_is_a_function=" + rand.nextBoolean(), + "--incompatible_range_type=" + rand.nextBoolean(), "--incompatible_remove_native_git_repository=" + rand.nextBoolean(), "--incompatible_remove_native_http_archive=" + rand.nextBoolean(), "--incompatible_string_is_not_iterable=" + rand.nextBoolean(), @@ -164,6 +165,7 @@ public class SkylarkSemanticsConsistencyTest { .incompatibleNewActionsApi(rand.nextBoolean()) .incompatibleNoSupportToolsInActionInputs(rand.nextBoolean()) .incompatiblePackageNameIsAFunction(rand.nextBoolean()) + .incompatibleRangeType(rand.nextBoolean()) .incompatibleRemoveNativeGitRepository(rand.nextBoolean()) .incompatibleRemoveNativeHttpArchive(rand.nextBoolean()) .incompatibleStringIsNotIterable(rand.nextBoolean()) diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java index 072b9c8e1c..103a35d137 100644 --- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java +++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java @@ -486,6 +486,14 @@ public class MethodLibraryTest extends EvaluationTestCase { .testStatement("str(range(5, 0, -1))", "[5, 4, 3, 2, 1]") .testStatement("str(range(5, 0, -10))", "[5]") .testStatement("str(range(0, -3, -2))", "[0, -2]") + .testStatement("str(range(5)[1:])", "[1, 2, 3, 4]") + .testStatement("len(range(5)[1:])", 4) + .testStatement("str(range(5)[:2])", "[0, 1]") + .testStatement("str(range(10)[1:9:2])", "[1, 3, 5, 7]") + .testStatement("str(range(10)[1:10:2])", "[1, 3, 5, 7, 9]") + .testStatement("str(range(10)[1:11:2])", "[1, 3, 5, 7, 9]") + .testStatement("str(range(0, 10, 2)[::2])", "[0, 4, 8]") + .testStatement("str(range(0, 10, 2)[::-2])", "[8, 4, 0]") .testIfErrorContains("step cannot be 0", "range(2, 3, 0)"); } @@ -499,6 +507,51 @@ public class MethodLibraryTest extends EvaluationTestCase { runRangeIsListAssertions("range(4)[:3]"); } + @Test + public void testRangeType() throws Exception { + new BothModesTest("--incompatible_range_type=true") + .setUp("a = range(3)") + .testStatement("len(a)", 3) + .testStatement("str(a)", "range(0, 3)") + .testStatement("str(range(1,2,3))", "range(1, 2, 3)") + .testStatement("repr(a)", "range(0, 3)") + .testStatement("repr(range(1,2,3))", "range(1, 2, 3)") + .testStatement("type(a)", "range") + .testIfErrorContains("unsupported operand type(s) for +: 'range' and 'range'", "a + a") + .testIfErrorContains("type 'range' has no method append(int)", "a.append(3)") + .testStatement("str(list(range(5)))", "[0, 1, 2, 3, 4]") + .testStatement("str(list(range(0)))", "[]") + .testStatement("str(list(range(1)))", "[0]") + .testStatement("str(list(range(-2)))", "[]") + .testStatement("str(list(range(-3, 2)))", "[-3, -2, -1, 0, 1]") + .testStatement("str(list(range(3, 2)))", "[]") + .testStatement("str(list(range(3, 3)))", "[]") + .testStatement("str(list(range(3, 4)))", "[3]") + .testStatement("str(list(range(3, 5)))", "[3, 4]") + .testStatement("str(list(range(-3, 5, 2)))", "[-3, -1, 1, 3]") + .testStatement("str(list(range(-3, 6, 2)))", "[-3, -1, 1, 3, 5]") + .testStatement("str(list(range(5, 0, -1)))", "[5, 4, 3, 2, 1]") + .testStatement("str(list(range(5, 0, -10)))", "[5]") + .testStatement("str(list(range(0, -3, -2)))", "[0, -2]") + .testStatement("range(3)[-1]", 2) + .testIfErrorContains( + "index out of range (index is 3, but sequence has 3 elements)", "range(3)[3]") + .testStatement("str(range(5)[1:])", "range(1, 5)") + .testStatement("len(range(5)[1:])", 4) + .testStatement("str(range(5)[:2])", "range(0, 2)") + .testStatement("str(range(10)[1:9:2])", "range(1, 9, 2)") + .testStatement("str(list(range(10)[1:9:2]))", "[1, 3, 5, 7]") + .testStatement("str(range(10)[1:10:2])", "range(1, 10, 2)") + .testStatement("str(range(10)[1:11:2])", "range(1, 10, 2)") + .testStatement("str(range(0, 10, 2)[::2])", "range(0, 10, 4)") + .testStatement("str(range(0, 10, 2)[::-2])", "range(8, -2, -4)") + .testStatement("str(range(5)[1::-1])", "range(1, -1, -1)") + .testIfErrorContains("step cannot be 0", "range(2, 3, 0)") + .testIfErrorContains( + "unsupported operand type(s) for *: 'range' and 'int'", "range(3) * 3"); + ; + } + /** * Helper function for testRangeIsList that expects a range or range slice expression producing * the range value containing [0, 1, 2]. -- cgit v1.2.3