path: root/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.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);
    }
  }
}