| // 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 net.starlark.java.eval; |
| |
| import com.google.common.base.Preconditions; |
| import com.google.common.collect.UnmodifiableIterator; |
| import java.util.AbstractList; |
| import java.util.Iterator; |
| import java.util.NoSuchElementException; |
| import java.util.Objects; |
| import javax.annotation.concurrent.Immutable; |
| import net.starlark.java.annot.StarlarkBuiltin; |
| |
| /** |
| * 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>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. |
| */ |
| @StarlarkBuiltin( |
| name = "range", |
| category = "core", |
| 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.") |
| @Immutable |
| final class RangeList extends AbstractList<StarlarkInt> implements Sequence<StarlarkInt> { |
| |
| private final int start; |
| private final int stop; |
| private final int step; |
| private final int size; // (derived) |
| |
| RangeList(int start, int stop, int step) throws EvalException { |
| Preconditions.checkArgument(step != 0); |
| |
| this.start = start; |
| this.stop = stop; |
| this.step = step; |
| |
| // compute size. |
| // Python version: |
| // https://github.com/python/cpython/blob/09bb918a61031377d720f1a0fa1fe53c962791b6/Objects/rangeobject.c#L144 |
| int low; // [low,high) is a half-open interval |
| int high; |
| long absStep; |
| if (step > 0) { |
| low = start; |
| high = stop; |
| absStep = step; |
| } else { |
| low = stop; |
| high = start; |
| absStep = -(long) step; |
| } |
| if (low >= high) { |
| this.size = 0; |
| } else { |
| long diff = (long) high - low - 1; |
| long size = diff / absStep + 1; |
| if ((int) size != size) { |
| throw Starlark.errorf("len(%s) exceeds signed 32-bit range", Starlark.repr(this)); |
| } |
| this.size = (int) size; |
| } |
| } |
| |
| @Override |
| public boolean contains(Object x) { |
| if (!(x instanceof StarlarkInt)) { |
| return false; |
| } |
| try { |
| int i = ((StarlarkInt) x).toIntUnchecked(); |
| |
| // constant-time implementation |
| if (step > 0) { |
| return start <= i && i < stop && (i - start) % step == 0; |
| } else { |
| return stop < i && i <= start && (i - start) % step == 0; |
| } |
| } catch (IllegalArgumentException ex) { |
| return false; // x is not a signed 32-bit int |
| } |
| } |
| |
| @Override |
| public StarlarkInt get(int index) { |
| if (index < 0 || index >= size()) { |
| throw new ArrayIndexOutOfBoundsException(index + ":" + this); |
| } |
| return StarlarkInt.of(at(index)); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public int hashCode() { |
| if (size == 0) { |
| return 234982346; |
| } else if (size == 1) { |
| return Integer.hashCode(start); |
| } else { |
| return Objects.hash(start, size, step); |
| } |
| } |
| |
| @Override |
| public boolean equals(Object other) { |
| if (!(other instanceof RangeList)) { |
| return false; |
| } |
| RangeList that = (RangeList) other; |
| |
| // Two RangeLists compare equal if they denote the same sequence. |
| if (this.size != that.size) { |
| return false; // sequences differ in length |
| } |
| if (this.size == 0) { |
| return true; // both sequences are empty |
| } |
| if (this.start != that.start) { |
| return false; // first element differs |
| } |
| return this.size == 1 || this.step == that.step; |
| } |
| |
| @Override |
| public Iterator<StarlarkInt> iterator() { |
| return new UnmodifiableIterator<StarlarkInt>() { |
| long cursor = start; // returned by next() if hasNext() is true |
| |
| @Override |
| public boolean hasNext() { |
| return (step > 0) ? (cursor < stop) : (cursor > stop); |
| } |
| |
| @Override |
| public StarlarkInt next() { |
| if (!hasNext()) { |
| throw new NoSuchElementException(); |
| } |
| // If cursor is valid, it's guaranteed to be in [start, stop) range, thus a 32-bit value. |
| int current = (int) cursor; |
| cursor += step; |
| return StarlarkInt.of(current); |
| } |
| }; |
| } |
| |
| @Override |
| public Sequence<StarlarkInt> getSlice(Mutability mu, int start, int stop, int step) |
| throws EvalException { |
| long sliceStep = (long) step * (long) this.step; |
| if (sliceStep != (int) sliceStep) { |
| // It is not an error to take a slice of a RangeList such that the slice step * list step |
| // doesn't fit in a 32-bit int; the result ought to be a RangeList containing only one |
| // element (the start). Since difference between 2 successive elements of a RangeList must be |
| // a 32-bit int, clamping the step to Integer.MAX_VALUE or MIN_VALUE and moving stop to start |
| // +/- 1 gives us the 1-element RangeList we need. |
| sliceStep = sliceStep > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE; // note sliceStep != 0 |
| if (stop > start) { |
| stop = start + 1; |
| } else if (stop < start) { |
| stop = start - 1; |
| } |
| } |
| return new RangeList(at(start), at(stop), (int) sliceStep); |
| } |
| |
| // Like get, but without bounds check or Integer allocation. |
| int at(int i) { |
| return start + step * i; |
| } |
| |
| @Override |
| public void repr(Printer printer) { |
| if (step == 1) { |
| printer.append(String.format("range(%d, %d)", start, stop)); |
| } else { |
| printer.append(String.format("range(%d, %d, %d)", start, stop, step)); |
| } |
| } |
| } |