commit 9de215db31bc6e8f4becf7058d33fe1d82b0ac9f
author Taras Tsugrii <ttsugrii@fb.com> Tue Jul 17 08:56:13 2018 -0700
committer Copybara-Service <copybara-piper@google.com> Tue Jul 17 08:57:35 2018 -0700
tree a6d3c77e3215261fbfc1fb488426a972b2508671
parent 59f915949e262ac526e8f7e3153502400d95b0ff

[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