[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

2 files changed, 55 insertions, 0 deletions

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].