// 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.util;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
import java.lang.annotation.ElementType;
import java.lang.annotation.Target;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
import org.checkerframework.framework.qual.DefaultQualifierInHierarchy;
import org.checkerframework.framework.qual.LiteralKind;
import org.checkerframework.framework.qual.QualifierForLiterals;
import org.checkerframework.framework.qual.SubtypeOf;

/**
 * Encapsulates a list of groups.
 *
 * <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
 * list. Users are responsible for not trying to add the same element to a GroupedList twice.
 *
 * <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined to
 * treat groups as unordered.
 *
 * <p>The generic type {@code T} <em>must not</em> be a {@link List}.
 */
public final class GroupedList<T> implements Iterable<List<T>> {

  /**
   * Indicates that the annotated element is a compressed {@link GroupedList}, so that it can be
   * safely passed to {@link #create} and friends.
   */
  @SubtypeOf(DefaultObject.class)
  @Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
  @QualifierForLiterals(LiteralKind.NULL)
  public @interface Compressed {}

  /** Default annotation for type-safety checks of {@link Compressed}. */
  @DefaultQualifierInHierarchy
  @SubtypeOf({})
  @Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
  private @interface DefaultObject {}

  // Total number of items in the list. At least elements.size(), but might be larger if there are
  // any nested lists.
  private int size = 0;
  // Items in this GroupedList. Each element is either of type T or List<T>.
  private final ArrayList<Object> elements;

  private final CollectionView collectionView = new CollectionView();

  public GroupedList() {
    // We optimize for small lists.
    this.elements = new ArrayList<>(1);
  }

  private GroupedList(int size, Object[] elements) {
    this.size = size;
    this.elements = Lists.newArrayList(elements);
  }

  /**
   * Increases the capacity of the backing list to accommodate the given number of additional
   * groups.
   */
  public void ensureCapacityForAdditionalGroups(int additionalGroups) {
    elements.ensureCapacity(elements.size() + additionalGroups);
  }

  /**
   * Adds a new group with a single element.
   *
   * <p>The caller must ensure that the given element is not already present.
   */
  public void appendSingleton(T t) {
    checkArgument(!(t instanceof List), "Cannot created GroupedList of lists: %s", t);
    elements.add(t);
    size++;
  }

  /**
   * Adds a new group.
   *
   * <p>The caller must ensure that the new group is duplicate-free and does not contain any
   * elements which are already present.
   */
  public void appendGroup(ImmutableList<T> group) {
    addGroup(group, elements);
    size += group.size();
  }

  /**
   * Removes the elements in toRemove from this list. Takes time proportional to the size of the
   * list, so should not be called often.
   */
  public void remove(Set<T> toRemove) {
    if (!toRemove.isEmpty()) {
      size = removeAndGetNewSize(elements, toRemove);
    }
  }

  /**
   * Removes everything in {@code toRemove} from the list of lists, {@code elements}. Returns the
   * new number of elements.
   */
  private static int removeAndGetNewSize(List<Object> elements, Set<?> toRemove) {
    int removedCount = 0;
    int newSize = 0;
    // elements.size is an upper bound of the needed size. Since normally removal happens just
    // before the list is finished and compressed, optimizing this size isn't a concern.
    List<Object> newElements = new ArrayList<>(elements.size());
    for (Object obj : elements) {
      if (obj instanceof List) {
        ImmutableList.Builder<Object> newGroup = new ImmutableList.Builder<>();
        List<?> oldGroup = (List<?>) obj;
        for (Object elt : oldGroup) {
          if (toRemove.contains(elt)) {
            removedCount++;
          } else {
            newGroup.add(elt);
            newSize++;
          }
        }
        addGroup(newGroup.build(), newElements);
      } else if (toRemove.contains(obj)) {
        removedCount++;
      } else {
        newElements.add(obj);
        newSize++;
      }
    }
    // removedCount can be larger if elements had duplicates and the duplicate was also in toRemove.
    checkState(
        removedCount >= toRemove.size(),
        "Requested removal of absent element(s) (toRemove=%s, elements=%s)",
        toRemove,
        elements);
    elements.clear();
    elements.addAll(newElements);
    return newSize;
  }

  /** Returns the group at position {@code i}. {@code i} must be less than {@link #listSize()}. */
  @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
  public ImmutableList<T> get(int i) {
    Object obj = elements.get(i);
    if (obj instanceof List) {
      return (ImmutableList<T>) obj;
    }
    return ImmutableList.of((T) obj);
  }

  /** Returns the number of groups in this list. */
  public int listSize() {
    return elements.size();
  }

  /**
   * Returns the number of individual elements of type {@code T} in this list, as opposed to the
   * number of groups -- equivalent to adding up the sizes of each group in this list.
   */
  public int numElements() {
    return size;
  }

  public static int numElements(@Compressed Object compressed) {
    if (compressed == EMPTY_LIST) {
      return 0;
    }
    if (compressed.getClass().isArray()) {
      int size = 0;
      for (Object item : (Object[]) compressed) {
        size += sizeOf(item);
      }
      return size;
    }
    // Just a single element.
    return 1;
  }

  /** Returns the number of groups in a compressed {@code GroupedList}. */
  public static int numGroups(@Compressed Object compressed) {
    if (compressed == EMPTY_LIST) {
      return 0;
    }
    if (compressed.getClass().isArray()) {
      return ((Object[]) compressed).length;
    }
    return 1;
  }

  /**
   * Expands a compressed {@code GroupedList} into an {@link Iterable}. Equivalent to {@link
   * #getAllElementsAsIterable()} but potentially more efficient.
   */
  @SuppressWarnings("unchecked")
  public static <T> Iterable<T> compressedToIterable(@Compressed Object compressed) {
    if (compressed == EMPTY_LIST) {
      return ImmutableList.of();
    }
    if (compressed.getClass().isArray()) {
      return GroupedList.<T>create(compressed).getAllElementsAsIterable();
    }
    checkState(!(compressed instanceof List), compressed);
    return ImmutableList.of((T) compressed);
  }

  /**
   * Casts an {@code Object} which is known to be {@link Compressed}.
   *
   * <p>This method should only be used when it is not possible to enforce the type via annotations.
   */
  public static @Compressed Object castAsCompressed(Object obj) {
    checkArgument(!(obj instanceof GroupedList), obj);
    return (@Compressed Object) obj;
  }

  /** Returns true if this list contains no elements. */
  public boolean isEmpty() {
    return elements.isEmpty();
  }

  /**
   * Returns true if this list contains {@code needle}. Takes time proportional to list size. Call
   * {@link #toSet} instead and use the result if doing multiple contains checks.
   */
  public boolean expensiveContains(T needle) {
    return contains(elements, needle);
  }

  private static boolean contains(List<Object> elements, Object needle) {
    for (Object obj : elements) {
      if (obj instanceof List) {
        if (((List<?>) obj).contains(needle)) {
          return true;
        }
      } else if (obj.equals(needle)) {
        return true;
      }
    }
    return false;
  }

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final @Compressed Object EMPTY_LIST = new Object();

  public @Compressed Object compress() {
    switch (numElements()) {
      case 0:
        return EMPTY_LIST;
      case 1:
        return Iterables.getOnlyElement(elements);
      default:
        return elements.toArray();
    }
  }

  @SuppressWarnings("unchecked")
  public ImmutableSet<T> toSet() {
    ImmutableSet.Builder<T> builder = ImmutableSet.builderWithExpectedSize(size);
    for (Object obj : elements) {
      if (obj instanceof List) {
        builder.addAll((List<T>) obj);
      } else {
        builder.add((T) obj);
      }
    }
    return builder.build();
  }

  private static int sizeOf(Object obj) {
    return obj instanceof List ? ((List<?>) obj).size() : 1;
  }

  public static <E> GroupedList<E> create(@Compressed Object compressed) {
    if (compressed == EMPTY_LIST) {
      return new GroupedList<>();
    }
    if (compressed.getClass().isArray()) {
      int size = 0;
      Object[] compressedArray = ((Object[]) compressed);
      for (Object item : compressedArray) {
        size += sizeOf(item);
      }
      return new GroupedList<>(size, compressedArray);
    }
    // Just a single element.
    return new GroupedList<>(1, new Object[] {compressed});
  }

  @Override
  public int hashCode() {
    // Hashing requires getting an order-independent hash for each element of this.elements. That
    // is too expensive for a hash code.
    throw new UnsupportedOperationException("Should not need to get hash for " + this);
  }

  /**
   * Checks that two lists, neither of which may contain duplicates, have the same elements,
   * regardless of order.
   */
  private static boolean checkUnorderedEqualityWithoutDuplicates(List<?> first, List<?> second) {
    if (first.size() != second.size()) {
      return false;
    }
    // The order-sensitive comparison usually returns true. When it does, the CompactHashSet
    // doesn't need to be constructed.
    return first.equals(second) || CompactHashSet.create(first).containsAll(second);
  }

  /**
   * A grouping-unaware view of a {@code GroupedList} which does not support modifications.
   *
   * <p>This is implemented as a {@code Collection} so that calling {@link Iterables#size} on the
   * return value of {@link #getAllElementsAsIterable} will take constant time.
   */
  private final class CollectionView extends AbstractCollection<T> {

    @Override
    public Iterator<T> iterator() {
      return new UngroupedIterator<>(elements);
    }

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

  /** An iterator that loops through every element in each group. */
  private static final class UngroupedIterator<T> implements Iterator<T> {
    private final List<Object> elements;
    private int outerIndex = 0;
    @Nullable private List<T> currentGroup;
    private int innerIndex = 0;

    private UngroupedIterator(List<Object> elements) {
      this.elements = elements;
    }

    @Override
    public boolean hasNext() {
      return outerIndex < elements.size();
    }

    @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
    @Override
    public T next() {
      if (currentGroup != null) {
        return nextFromCurrentGroup();
      }
      Object next = elements.get(outerIndex);
      if (next instanceof List) {
        currentGroup = (List<T>) next;
        innerIndex = 0;
        return nextFromCurrentGroup();
      }
      return (T) elements.get(outerIndex++);
    }

    private T nextFromCurrentGroup() {
      T next = currentGroup.get(innerIndex++);
      if (innerIndex == currentGroup.size()) {
        outerIndex++;
        currentGroup = null;
      }
      return next;
    }
  }

  @ThreadHostile
  public Collection<T> getAllElementsAsIterable() {
    return collectionView;
  }

  @Override
  public boolean equals(Object other) {
    if (this == other) {
      return true;
    }
    if (!(other instanceof GroupedList)) {
      return false;
    }
    GroupedList<?> that = (GroupedList<?>) other;
    // We must check the deps, ignoring the ordering of deps in the same group.
    if (this.size != that.size || this.elements.size() != that.elements.size()) {
      return false;
    }
    for (int i = 0; i < this.elements.size(); i++) {
      Object thisElt = this.elements.get(i);
      Object thatElt = that.elements.get(i);
      if (thisElt == thatElt) {
        continue;
      }
      if (thisElt instanceof List) {
        // Recall that each inner item is either a List or a singleton element.
        if (!(thatElt instanceof List)) {
          return false;
        }
        if (!checkUnorderedEqualityWithoutDuplicates((List<?>) thisElt, (List<?>) thatElt)) {
          return false;
        }
      } else if (!thisElt.equals(thatElt)) {
        return false;
      }
    }
    return true;
  }

  @Override
  public String toString() {
    return MoreObjects.toStringHelper(this).add("elements", elements).add("size", size).toString();
  }

  /**
   * Iterator that returns the next group in elements for each call to {@link #next}. A custom
   * iterator is needed here because, to optimize memory, we store single-element lists as elements
   * internally, and so they must be wrapped before they're returned.
   */
  private class GroupedIterator implements Iterator<List<T>> {
    private final Iterator<Object> iter = elements.iterator();

    @Override
    public boolean hasNext() {
      return iter.hasNext();
    }

    @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
    @Override
    public List<T> next() {
      Object obj = iter.next();
      if (obj instanceof List) {
        return (List<T>) obj;
      }
      return ImmutableList.of((T) obj);
    }
  }

  @Override
  public Iterator<List<T>> iterator() {
    return new GroupedIterator();
  }

  /**
   * If {@code group} is empty, this function does nothing.
   *
   * <p>If it contains a single element, then that element is added to {@code elements}.
   *
   * <p>If it contains more than one element, then it is added as the next element of {@code
   * elements} (this means {@code elements} may contain both raw objects and {@link
   * ImmutableList}s).
   *
   * <p>Use with caution as there are no checks in place for the integrity of the resulting object
   * (no de-duping or verifying there are no nested lists).
   */
  private static void addGroup(ImmutableList<?> group, List<Object> elements) {
    switch (group.size()) {
      case 0:
        return;
      case 1:
        elements.add(group.get(0));
        return;
      default:
        elements.add(group);
    }
  }
}