[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

10 files changed, 456 insertions, 54 deletions

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<SkylarkSemantics
     codedOut.writeBoolNoTag(semantics.incompatibleNewActionsApi());
     codedOut.writeBoolNoTag(semantics.incompatibleNoSupportToolsInActionInputs());
     codedOut.writeBoolNoTag(semantics.incompatiblePackageNameIsAFunction());
+    codedOut.writeBoolNoTag(semantics.incompatibleRangeType());
     codedOut.writeBoolNoTag(semantics.incompatibleRemoveNativeGitRepository());
     codedOut.writeBoolNoTag(semantics.incompatibleRemoveNativeHttpArchive());
     codedOut.writeBoolNoTag(semantics.incompatibleStringIsNotIterable());
@@ -87,6 +88,7 @@ public final class SkylarkSemanticsCodec implements ObjectCodec<SkylarkSemantics
     builder.incompatibleNewActionsApi(codedIn.readBool());
     builder.incompatibleNoSupportToolsInActionInputs(codedIn.readBool());
     builder.incompatiblePackageNameIsAFunction(codedIn.readBool());
+    builder.incompatibleRangeType(codedIn.readBool());
     builder.incompatibleRemoveNativeGitRepository(codedIn.readBool());
     builder.incompatibleRemoveNativeHttpArchive(codedIn.readBool());
     builder.incompatibleStringIsNotIterable(codedIn.readBool());
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
index 07989682a4..e48c1be9fa 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkSemanticsOptions.java
@@ -281,6 +281,18 @@ public class SkylarkSemanticsOptions extends OptionsBase implements Serializable
   public boolean incompatiblePackageNameIsAFunction;
 
   @Option(
+      name = "incompatible_range_type",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      metadataTags = {
+        OptionMetadataTag.INCOMPATIBLE_CHANGE,
+        OptionMetadataTag.TRIGGERED_BY_ALL_INCOMPATIBLE_CHANGES
+      },
+      help = "If set to true, range() will use the 'range' type instead of 'list'.")
+  public boolean incompatibleRangeType;
+
+  @Option(
     name = "incompatible_remove_native_git_repository",
     defaultValue = "false",
     documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
@@ -354,6 +366,7 @@ public class SkylarkSemanticsOptions extends OptionsBase implements Serializable
         .incompatibleNewActionsApi(incompatibleNewActionsApi)
         .incompatibleNoSupportToolsInActionInputs(incompatibleNoSupportToolsInActionInputs)
         .incompatiblePackageNameIsAFunction(incompatiblePackageNameIsAFunction)
+        .incompatibleRangeType(incompatibleRangeType)
         .incompatibleRemoveNativeGitRepository(incompatibleRemoveNativeGitRepository)
         .incompatibleRemoveNativeHttpArchive(incompatibleRemoveNativeHttpArchive)
         .incompatibleStringIsNotIterable(incompatibleStringIsNotIterable)
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index 283fd5720d..5ac2fb345f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -388,7 +388,7 @@ public final class BinaryOperatorExpression extends Expression {
       } else if (otherFactor instanceof String) {
         // Similar to Python, a factor < 1 leads to an empty string.
         return Strings.repeat((String) otherFactor, Math.max(0, number));
-      } else if (otherFactor instanceof SkylarkList) {
+      } else if (otherFactor instanceof SkylarkList && !(otherFactor instanceof RangeList)) {
         // Similar to Python, a factor < 1 leads to an empty string.
         return ((SkylarkList<?>) 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 <code>start</code> to <code>stop</code>, using a "
-            + "<code>step</code> increment. If a single argument is provided, items will "
-            + "range from 0 to that element."
-            + "<pre class=\"language-python\">range(4) == [0, 1, 2, 3]\n"
-            + "range(3, 9, 2) == [3, 5, 7]\n"
-            + "range(3, 0, -1) == [3, 2, 1]</pre>",
-    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 <i>not</i> to be included in the resulting "
-                + "list; generation of the list stops before <code>stop</code> 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 <code>start</code> to <code>stop</code>, using a "
+              + "<code>step</code> increment. If a single argument is provided, items will "
+              + "range from 0 to that element."
+              + "<pre class=\"language-python\">range(4) == [0, 1, 2, 3]\n"
+              + "range(3, 9, 2) == [3, 5, 7]\n"
+              + "range(3, 0, -1) == [3, 2, 1]</pre>",
+      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 <i>not</i> to be included in the resulting "
+                    + "list; generation of the list stops before <code>stop</code> 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<Integer> 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<Integer> 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.
+ *
+ * <p>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.
+ *
+ * <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.
+ */
+@SkylarkModule(
+    name = "range",
+    category = SkylarkModuleCategory.BUILTIN,
+    doc =
+        "A language built-in type to support ranges. Example of range literal:<br>"
+            + "<pre class=language-python>x = range(1, 10, 3)</pre>"
+            + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
+            + "<pre class=language-python>e = x[1]   # e == 2</pre>"
+            + "Ranges do not support the <code>+</code> operator for concatenation."
+            + "Similar to strings, ranges support slice operations:"
+            + "<pre class=language-python>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)</pre>"
+            + "Ranges are immutable, as in Python 3.")
+public final class RangeList extends SkylarkList<Integer> {
+
+  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<Integer> {
+
+    /** Iterator for increasing/decreasing sequences. */
+    private static class RangeListIterator extends UnmodifiableIterator<Integer> {
+      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<Integer> 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<Integer> getImmutableList() {
+    return ImmutableList.copyOf(contents);
+  }
+
+  @Override
+  public SkylarkList<Integer> 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<Integer> repeat(int times, Mutability mutability) {
+    throw new UnsupportedOperationException("Ranges do not support repetition.");
+  }
+
+  @Override
+  protected List<Integer> 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.
+   *
+   * <p>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
+   *     <pre>list</pre>
+   *     type.
+   */
+  MutableList<Integer> 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}.
+   *
+   * <p>{@code start} and {@code stop} define a half-open interval
+   *
+   * <pre>[start, stop)</pre>
+   */
+  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.
+     *
+     * <p>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<E> extends BaseMutableList<E>
   @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<E> extends BaseMutableList<E>
       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 <T> void addAll(ArrayList<T> addTo, ArrayList<? extends T> addFrom) {
       // Hot code path, skip iterator.
       for (int i = 0; i < addFrom.size(); i++) {
@@ -614,7 +615,7 @@ public abstract class SkylarkList<E> extends BaseMutableList<E>
      * Creates a {@code Tuple} from an {@link ImmutableList}, reusing the empty instance if
      * applicable.
      */
-    private static<T> Tuple<T> create(ImmutableList<T> contents) {
+    private static <T> Tuple<T> create(ImmutableList<T> 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].