[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

1 files changed, 9 insertions, 0 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