Starlark: fail at range construction time if len exceeds maxint Alternative to #12675 Closes #12733. PiperOrigin-RevId: 419959983

diff --git a/src/main/java/net/starlark/java/eval/RangeList.java b/src/main/java/net/starlark/java/eval/RangeList.java
index 2a4c488..c0a6fc8 100644
--- a/src/main/java/net/starlark/java/eval/RangeList.java
+++ b/src/main/java/net/starlark/java/eval/RangeList.java

@@ -30,6 +30,8 @@
  * 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.
  *
+ * <p>The start, stop, step, and size of the range must all fit within 32-bit signed integers.
+ *
  * <p>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.
@@ -56,8 +58,7 @@
   private final int step;
   private final int size; // (derived)
 
-  // TODO(adonovan): use StarlarkInt computation, to avoid overflow.
-  RangeList(int start, int stop, int step) {
+  RangeList(int start, int stop, int step) throws EvalException {
     Preconditions.checkArgument(step != 0);
 
     this.start = start;
@@ -80,8 +81,12 @@
     if (low >= high) {
       this.size = 0;
     } else {
-      int diff = high - low - 1;
-      this.size = diff / step + 1;
+      long diff = (long) high - low - 1;
+      long size = diff / step + 1;
+      if ((int) size != size) {
+        throw Starlark.errorf("len(%s) exceeds signed 32-bit range", Starlark.repr(this));
+      }
+      this.size = (int) size;
     }
   }
 
@@ -171,7 +176,10 @@
   }
 
   @Override
-  public Sequence<StarlarkInt> getSlice(Mutability mu, int start, int stop, int step) {
+  public Sequence<StarlarkInt> getSlice(Mutability mu, int start, int stop, int step)
+      throws EvalException {
+    // TODO(arostovtsev): verify step * this.step doesn't overflow int. Otherwise, we can get a
+    // shorter or even zero step size (and the latter would fail a precondition check).
     return new RangeList(at(start), at(stop), step * this.step);
   }
 

diff --git a/src/main/java/net/starlark/java/eval/Sequence.java b/src/main/java/net/starlark/java/eval/Sequence.java
index 7242f5f..7d9a045 100644
--- a/src/main/java/net/starlark/java/eval/Sequence.java
+++ b/src/main/java/net/starlark/java/eval/Sequence.java

@@ -100,7 +100,7 @@
    * For negative strides ({@code step < 0}), {@code -1 <= stop <= start < size()}. <br>
    * The caller must ensure that the start and stop indices are valid and that step is non-zero.
    */
-  Sequence<E> getSlice(Mutability mu, int start, int stop, int step);
+  Sequence<E> getSlice(Mutability mu, int start, int stop, int step) throws EvalException;
 
   /**
    * Casts a non-null Starlark value {@code x} to a {@code Sequence<T>}, after checking that each

diff --git a/src/main/java/net/starlark/java/eval/StarlarkList.java b/src/main/java/net/starlark/java/eval/StarlarkList.java
index 6fce805..f46ac6a 100644
--- a/src/main/java/net/starlark/java/eval/StarlarkList.java
+++ b/src/main/java/net/starlark/java/eval/StarlarkList.java

@@ -315,7 +315,8 @@
   }
 
   @Override
-  public StarlarkList<E> getSlice(Mutability mu, int start, int stop, int step) {
+  public StarlarkList<E> getSlice(Mutability mu, int start, int stop, int step)
+      throws EvalException {
     RangeList indices = new RangeList(start, stop, step);
     int n = indices.size();
     Object[] res = new Object[n];

diff --git a/src/main/java/net/starlark/java/eval/StringModule.java b/src/main/java/net/starlark/java/eval/StringModule.java
index 0810825..f08113a 100644
--- a/src/main/java/net/starlark/java/eval/StringModule.java
+++ b/src/main/java/net/starlark/java/eval/StringModule.java

@@ -66,7 +66,7 @@
   private StringModule() {}
 
   // Returns s[start:stop:step], as if by Sequence.getSlice.
-  static String slice(String s, int start, int stop, int step) {
+  static String slice(String s, int start, int stop, int step) throws EvalException {
     RangeList indices = new RangeList(start, stop, step);
     int n = indices.size();
     if (n == 0) {

diff --git a/src/main/java/net/starlark/java/eval/Tuple.java b/src/main/java/net/starlark/java/eval/Tuple.java
index c6c6d66..f4429969 100644
--- a/src/main/java/net/starlark/java/eval/Tuple.java
+++ b/src/main/java/net/starlark/java/eval/Tuple.java

@@ -226,7 +226,7 @@
   }
 
   @Override
-  public Tuple getSlice(Mutability mu, int start, int stop, int step) {
+  public Tuple getSlice(Mutability mu, int start, int stop, int step) throws EvalException {
     RangeList indices = new RangeList(start, stop, step);
     int n = indices.size();
     if (step == 1) { // common case

diff --git a/src/test/java/net/starlark/java/eval/testdata/range.star b/src/test/java/net/starlark/java/eval/testdata/range.star
index 32c4aa4..8622f32 100644
--- a/src/test/java/net/starlark/java/eval/testdata/range.star
+++ b/src/test/java/net/starlark/java/eval/testdata/range.star

@@ -13,3 +13,13 @@
 assert_eq(list(range(5, 0, -10)), [5])
 assert_eq(list(range(0, -3, -2)), [0, -2])
 assert_fails(lambda: range(2, 3, 0), "step cannot be 0")
+
+maxint = (1 << 31) - 1
+minint = (-1) << 31
+
+assert_eq(maxint, len(range(0, maxint)))
+assert_eq(maxint, len(range(minint, maxint - 1, 2)))
+assert_fails(lambda: range(-1, maxint), "len\\(range\\(-1, 2147483647\\)\\) exceeds signed 32-bit range")
+assert_fails(lambda: range(minint - 1, minint), "got -2147483649 for start, want value in signed 32-bit range")
+assert_fails(lambda: range(maxint, maxint + 1), "got 2147483648 for stop, want value in signed 32-bit range")
+assert_fails(lambda: range(-1, maxint, maxint + 1), "got 2147483648 for step, want value in signed 32-bit range")