// Copyright 2014 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.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.skylarkinterface.Param;
import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import javax.annotation.Nullable;

/** A StarlarkList is a mutable finite sequence of values. */
@SkylarkModule(
    name = "list",
    category = SkylarkModuleCategory.BUILTIN,
    doc =
        "The built-in list type. Example list expressions:<br>"
            + "<pre class=language-python>x = [1, 2, 3]</pre>"
            + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
            + "<pre class=language-python>e = x[1]   # e == 2</pre>"
            + "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
            + "<pre class=language-python>x = [1, 2] + [3, 4]   # x == [1, 2, 3, 4]\n"
            + "x = [\"a\", \"b\"]\n"
            + "x += [\"c\"]            # x == [\"a\", \"b\", \"c\"]</pre>"
            + "Similar to strings, lists support slice operations:"
            + "<pre class=language-python>['a', 'b', 'c', 'd'][1:3]   # ['b', 'c']\n"
            + "['a', 'b', 'c', 'd'][::2]  # ['a', 'c']\n"
            + "['a', 'b', 'c', 'd'][3:0:-1]  # ['d', 'c', 'b']</pre>"
            + "Lists are mutable, as in Python.")
public final class StarlarkList<E> extends AbstractList<E>
    implements Sequence<E>, StarlarkValue, Mutability.Freezable {

  // The implementation strategy is similar to ArrayList,
  // but without the extra indirection of using ArrayList.

  private int size;
  private Object[] elems = EMPTY_ARRAY; // elems[i] == null  iff  i >= size

  /** Final except for {@link #unsafeShallowFreeze}; must not be modified any other way. */
  private Mutability mutability;

  private static final Object[] EMPTY_ARRAY = {};

  private StarlarkList(@Nullable Mutability mutability, Object[] elems) {
    this.elems = elems;
    this.size = elems.length;
    this.mutability = mutability == null ? Mutability.IMMUTABLE : mutability;
  }

  /**
   * Takes ownership of the supplied array and returns a new StarlarkList instance that initially
   * wraps the array. The caller must not subsequently modify the array, but the StarlarkList
   * instance may do so.
   */
  static <T> StarlarkList<T> wrap(@Nullable Mutability mutability, Object[] elems) {
    return new StarlarkList<>(mutability, elems);
  }

  @Override
  public boolean isImmutable() {
    return mutability().isFrozen();
  }

  @Override
  public boolean isHashable() {
    return false; // even a frozen list is unhashable in Starlark
  }

  /**
   * A shared instance for the empty list with immutable mutability.
   *
   * <p>Other immutable empty list objects can exist, e.g. lists that were once mutable but whose
   * environments were then frozen. This instance is for empty lists that were always frozen from
   * the beginning.
   */
  private static final StarlarkList<?> EMPTY = wrap(Mutability.IMMUTABLE, EMPTY_ARRAY);

  /** Returns an empty frozen list of the desired type. */
  @SuppressWarnings("unchecked")
  public static <T> StarlarkList<T> empty() {
    return (StarlarkList<T>) EMPTY;
  }

  /** Returns a new, empty list with the specified Mutability. */
  public static <T> StarlarkList<T> newList(Mutability mutability) {
    return wrap(mutability, EMPTY_ARRAY);
  }

  /**
   * Returns a {@code StarlarkList} whose items are given by an iterable and which has the given
   * {@link Mutability}. If {@code mutability} is null, the list is immutable.
   */
  public static <T> StarlarkList<T> copyOf(
      @Nullable Mutability mutability, Iterable<? extends T> elems) {
    return wrap(mutability, Iterables.toArray(elems, Object.class));
  }

  /**
   * Returns an immutable list with the given elements. Equivalent to {@code copyOf(null, elems)}.
   */
  public static <T> StarlarkList<T> immutableCopyOf(Iterable<? extends T> elems) {
    return copyOf(null, elems);
  }

  /**
   * Returns a {@code StarlarkList} with the given items and the {@link Mutability}. If {@code
   * mutability} is null, the list is immutable.
   */
  public static <T> StarlarkList<T> of(@Nullable Mutability mutability, T... elems) {
    return wrap(mutability, Arrays.copyOf(elems, elems.length));
  }

  @Override
  public Mutability mutability() {
    return mutability;
  }

  @Override
  public void unsafeShallowFreeze() {
    Mutability.Freezable.checkUnsafeShallowFreezePrecondition(this);
    this.mutability = Mutability.IMMUTABLE;
  }

  @Override
  public ImmutableList<E> getImmutableList() {
    // Optimization: a frozen array needn't be copied.
    // If the entire array is full, we can wrap it directly.
    if (elems.length == size && mutability().isFrozen()) {
      return Tuple.wrapImmutable(elems);
    }

    return ImmutableList.copyOf(this);
  }

  /**
   * Returns a new {@code StarlarkList} that is the concatenation of two {@code StarlarkList}s. The
   * new list will have the given {@link Mutability}.
   */
  public static <T> StarlarkList<T> concat(
      StarlarkList<? extends T> x, StarlarkList<? extends T> y, Mutability mutability) {
    Object[] res = new Object[x.size + y.size];
    System.arraycopy(x.elems, 0, res, 0, x.size);
    System.arraycopy(y.elems, 0, res, x.size, y.size);
    return wrap(mutability, res);
  }

  @Override
  public boolean equals(Object that) {
    // This slightly violates the java.util.List equivalence contract
    // because it considers the class, not just the elements.
    return this == that || (that instanceof StarlarkList && sameElems(this, ((StarlarkList) that)));
  }

  private static boolean sameElems(StarlarkList<?> x, StarlarkList<?> y) {
    if (x.size != y.size) {
      return false;
    }
    for (int i = 0; i < x.size; i++) {
      if (!x.elems[i].equals(y.elems[i])) {
        return false;
      }
    }
    return true;
  }

  @Override
  public int hashCode() {
    // Roll our own hash code to avoid iterating through null part of elems.
    int result = 1;
    for (int i = 0; i < size; i++) {
      result = 31 * result + elems[i].hashCode();
    }
    return 6047 + 4673 * result;
  }

  @Override
  public void repr(Printer printer) {
    printer.printList(this, /*isTuple=*/ false);
  }

  // TODO(adonovan): StarlarkValue has 3 String methods yet still we need this fourth. Why?
  @Override
  public String toString() {
    return Starlark.repr(this);
  }

  /** Returns a new StarlarkList containing n consecutive repeats of this tuple. */
  public StarlarkList<E> repeat(int n, Mutability mutability) {
    if (n <= 0) {
      return wrap(mutability, EMPTY_ARRAY);
    }

    // TODO(adonovan): reject unreasonably large n.
    Object[] res = new Object[n * size];
    for (int i = 0; i < n; i++) {
      System.arraycopy(elems, 0, res, i * size, size);
    }
    return wrap(mutability, res);
  }

  @Override
  @SuppressWarnings("unchecked")
  public E get(int i) {
    return (E) elems[i]; // unchecked
  }

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

  @Override
  public StarlarkList<E> getSlice(Mutability mu, int start, int stop, int step) {
    RangeList indices = new RangeList(start, stop, step);
    int n = indices.size();
    Object[] res = new Object[n];
    if (step == 1) { // common case
      System.arraycopy(elems, indices.at(0), res, 0, n);
    } else {
      for (int i = 0; i < n; ++i) {
        res[i] = elems[indices.at(i)];
      }
    }
    return wrap(mu, res);
  }

  // Postcondition: elems.length >= mincap.
  private void grow(int mincap) {
    int oldcap = elems.length;
    if (oldcap < mincap) {
      int newcap = oldcap + (oldcap >> 1); // grow by at least 50%
      if (newcap < mincap) {
        newcap = mincap;
      }
      elems = Arrays.copyOf(elems, newcap);
    }
  }

  /**
   * Appends an element to the end of the list, after validating that mutation is allowed.
   *
   * @param element the element to add
   * @param unused a nonce value to select this overload, not List.add
   */
  public void add(E element, Location unused) throws EvalException {
    checkMutable();
    grow(size + 1);
    elems[size++] = element;
  }

  /**
   * Inserts an element at a given position to the list.
   *
   * @param index the new element's index
   * @param element the element to add
   * @param unused a nonce value to select this overload, not List.add
   */
  public void add(int index, E element, Location unused) throws EvalException {
    checkMutable();
    grow(size + 1);
    System.arraycopy(elems, index, elems, index + 1, size - index);
    elems[index] = element;
    size++;
  }

  /**
   * Appends all the elements to the end of the list.
   *
   * @param elements the elements to add
   * @param unused a nonce value to select this overload, not List.addAll
   */
  public void addAll(Iterable<? extends E> elements, Location unused) throws EvalException {
    checkMutable();
    if (elements instanceof StarlarkList) {
      StarlarkList<?> that = (StarlarkList) elements;
      // (safe even if this == that)
      grow(this.size + that.size);
      System.arraycopy(that.elems, 0, this.elems, this.size, that.size);
      this.size += that.size;
    } else if (elements instanceof Collection) {
      // collection of known size
      Collection<?> that = (Collection) elements;
      grow(size + that.size());
      for (Object x : that) {
        elems[size++] = x;
      }
    } else {
      // iterable
      for (Object x : elements) {
        grow(size + 1);
        elems[size++] = x;
      }
    }
  }

  /**
   * Removes the element at a given index. The index must already have been validated to be in
   * range.
   *
   * @param index the index of the element to remove
   * @param unused a nonce value to select this overload, not List.remove
   */
  public void remove(int index, Location unused) throws EvalException {
    checkMutable();
    int n = size - index - 1;
    if (n > 0) {
      System.arraycopy(elems, index + 1, elems, index, n);
    }
    elems[--size] = null; // aid GC
  }

  @SkylarkCallable(
      name = "remove",
      doc =
          "Removes the first item from the list whose value is x. "
              + "It is an error if there is no such item.",
      parameters = {@Param(name = "x", type = Object.class, doc = "The object to remove.")})
  public NoneType removeObject(Object x) throws EvalException {
    for (int i = 0; i < size; i++) {
      if (elems[i].equals(x)) {
        remove(i, (Location) null);
        return Starlark.NONE;
      }
    }
    throw Starlark.errorf("item %s not found in list", Starlark.repr(x));
  }

  /**
   * Sets the position at the given index to contain the given value. The index must already have
   * been validated to be in range.
   *
   * @param index the position to change
   * @param value the new value
   * @param unused a nonce value to select this overload, not List.set
   */
  public void set(int index, E value, Location unused) throws EvalException {
    checkMutable();
    elems[index] = value;
  }

  @SkylarkCallable(
      name = "append",
      doc = "Adds an item to the end of the list.",
      parameters = {
        @Param(name = "item", type = Object.class, doc = "Item to add at the end.", noneable = true)
      })
  @SuppressWarnings("unchecked")
  public NoneType append(Object item) throws EvalException {
    add((E) item, (Location) null); // unchecked
    return Starlark.NONE;
  }

  @SkylarkCallable(name = "clear", doc = "Removes all the elements of the list.")
  public NoneType clearMethod() throws EvalException {
    checkMutable();
    for (int i = 0; i < size; i++) {
      elems[i] = null; // aid GC
    }
    size = 0;
    return Starlark.NONE;
  }

  @SkylarkCallable(
      name = "insert",
      doc = "Inserts an item at a given position.",
      parameters = {
        @Param(name = "index", type = Integer.class, doc = "The index of the given position."),
        @Param(name = "item", type = Object.class, doc = "The item.", noneable = true)
      })
  @SuppressWarnings("unchecked")
  public NoneType insert(Integer index, Object item) throws EvalException {
    add(EvalUtils.toIndex(index, size), (E) item, (Location) null); // unchecked
    return Starlark.NONE;
  }

  @SkylarkCallable(
      name = "extend",
      doc = "Adds all items to the end of the list.",
      parameters = {@Param(name = "items", type = Object.class, doc = "Items to add at the end.")})
  public NoneType extend(Object items) throws EvalException {
    @SuppressWarnings("unchecked")
    Iterable<? extends E> src = (Iterable<? extends E>) Starlark.toIterable(items);
    addAll(src, (Location) null);
    return Starlark.NONE;
  }

  @SkylarkCallable(
      name = "index",
      doc =
          "Returns the index in the list of the first item whose value is x. "
              + "It is an error if there is no such item.",
      parameters = {
        @Param(name = "x", type = Object.class, doc = "The object to search."),
        @Param(
            name = "start",
            type = Integer.class,
            defaultValue = "None",
            noneable = true, // TODO(adonovan): this is wrong
            named = true,
            doc = "The start index of the list portion to inspect."),
        @Param(
            name = "end",
            type = Integer.class,
            defaultValue = "None",
            noneable = true, // TODO(adonovan): this is wrong
            named = true,
            doc = "The end index of the list portion to inspect.")
      })
  public Integer index(Object x, Object start, Object end) throws EvalException {
    int i = start == Starlark.NONE ? 0 : EvalUtils.toIndex((Integer) start, size);
    int j = end == Starlark.NONE ? size : EvalUtils.toIndex((Integer) end, size);
    for (; i < j; i++) {
      if (elems[i].equals(x)) {
        return i;
      }
    }
    throw Starlark.errorf("item %s not found in list", Starlark.repr(x));
  }

  @SkylarkCallable(
      name = "pop",
      doc =
          "Removes the item at the given position in the list, and returns it. "
              + "If no <code>index</code> is specified, "
              + "it removes and returns the last item in the list.",
      parameters = {
        @Param(
            name = "i",
            type = Integer.class,
            noneable = true, // TODO(adonovan): this is wrong
            defaultValue = "-1",
            doc = "The index of the item.")
      })
  public Object pop(Object i) throws EvalException {
    int arg = i == Starlark.NONE ? -1 : (Integer) i;
    int index = EvalUtils.getSequenceIndex(arg, size);
    Object result = elems[index];
    remove(index, (Location) null);
    return result;
  }
}