src/main/java/com/google/devtools/build/lib/syntax/RangeList.java

// 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.UnmodifiableIterator;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
import java.util.AbstractList;
import java.util.Iterator;
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.")
@Immutable
final class RangeList extends AbstractList<Integer> implements Sequence<Integer> {

  private final int start;
  private final int stop;
  private final int step;
  private final int size; // (derived)

  RangeList(int start, int stop, int step) {
    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;
    if (step > 0) {
      low = start;
      high = stop;
    } else {
      low = stop;
      high = start;
      step = -step;
    }
    if (low >= high) {
      this.size = 0;
    } else {
      int diff = high - low - 1;
      this.size = diff / step + 1;
    }
  }

  @Override
  public boolean contains(Object x) {
    if (!(x instanceof Integer)) {
      return false;
    }
    int i = (Integer) x;
    // 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;
    }
  }

  @Override
  public Integer get(int index) {
    if (index < 0 || index >= size()) {
      throw new ArrayIndexOutOfBoundsException(index + ":" + this);
    }
    return at(index);
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public int hashCode() {
    return 7873 ^ (5557 * start) ^ (3251 * step) ^ (1091 * size);
  }

  @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<Integer> iterator() {
    return new UnmodifiableIterator<Integer>() {
      int cursor = start;

      @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;
      }
    };
  }

  @Override
  public Sequence<Integer> getSlice(Mutability mu, int start, int stop, int step) {
    return new RangeList(at(start), at(stop), step * this.step);
  }

  // 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.format("range(%d, %d)", start, stop);
    } else {
      printer.format("range(%d, %d, %d)", start, stop, step);
    }
  }
}