path: root/src/main/java/com/google/devtools/build/lib/util/GroupedList.java

// 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 com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
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 java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * Encapsulates a list of groups. Is intended to be used in "batch" mode -- to set the value of a
 * GroupedList, users should first construct a {@link GroupedListHelper}, add elements to it, and
 * then {@link #append} the helper to a new GroupedList instance. The generic type T <i>must not</i>
 * be a {@link List}.
 *
 * <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.
 */
public class GroupedList<T> implements Iterable<Collection<T>> {
  // 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>.
  // Non-final only for #remove.
  private List<Object> elements;

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

  // 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).
  public GroupedList(int size, List<Object> elements) {
    this.size = size;
    this.elements = new ArrayList<>(elements);
  }

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

  /**
   * Appends the list constructed in {@code helper} to this list. Returns the elements of {@code
   * helper}, uniquified.
   */
  @SuppressWarnings("unchecked") // Cast to T and List<T>.
  public Set<T> append(GroupedListHelper<T> helper) {
    Preconditions.checkState(helper.currentGroup == null, "%s %s", this, helper);
    // Do a check to make sure we don't have lists here. Note that if helper.elements is empty,
    // Iterables.getFirst will return null, and null is not instanceof List.
    Preconditions.checkState(!(Iterables.getFirst(helper.elements, null) instanceof List),
        "Cannot make grouped list of lists: %s", helper);
    Set<T> uniquifier = CompactHashSet.createWithExpectedSize(helper.elements.size());
    for (Object item : helper.groupedList) {
      if (item instanceof List) {
        // Optimize for the case that elements in this list are unique.
        ImmutableList.Builder<T> dedupedList = null;
        List<T> list = (List<T>) item;
        Preconditions.checkState(
            list.size() > 1, "Helper should have compressed small list %s properly", list);
        for (int i = 0; i < list.size(); i++) {
          T elt = list.get(i);
          if (!uniquifier.add(elt)) {
            if (dedupedList == null) {
              dedupedList = ImmutableList.builder();
              dedupedList.addAll(list.subList(0, i));
            }
          } else if (dedupedList != null) {
            dedupedList.add(elt);
          }
        }
        if (dedupedList == null) {
          elements.add(list);
        } else {
          List<T> filteredList = dedupedList.build();
          addItem(filteredList, elements);
        }
      } else if (uniquifier.add((T) item)) {
        elements.add(item);
      }
    }
    size += uniquifier.size();
    return uniquifier;
  }

  // Use with caution as there are no checks in place for the integrity of the resulting object
  // (no de-duping).
  public void appendGroup(Collection<T> group) {
    // Do a check to make sure we don't have lists here. Note that if group is empty,
    // Iterables.getFirst will return null, and null is not instanceof List.
    Preconditions.checkState(!(Iterables.getFirst(group, null) instanceof List),
        "Cannot make grouped list of lists: %s", group);
    switch (group.size()) {
      case 0:
        return;
      case 1:
        elements.add(Iterables.getOnlyElement(group));
        break;
      default:
        elements.add(group);
        break;
    }
    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) {
    elements = remove(elements, toRemove);
    size -= toRemove.size();
  }

  /** 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 List<T> get(int i) {
    Object obj = elements.get(i);
    if (obj instanceof List) {
      return (List<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 {@link 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;
  }

  /** 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) {
    for (Object obj : elements) {
      if (obj instanceof List) {
        if (((List) obj).contains(needle)) {
          return true;
        }
      } else if (obj.equals(needle)) {
        return true;
      }
    }
    return false;
  }

  private static final Object EMPTY_LIST = new Object();

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

  @SuppressWarnings("unchecked")
  public Set<T> toSet() {
    ImmutableSet.Builder<T> builder = ImmutableSet.builderWithExpectedSize(numElements());
    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(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, ImmutableList.of(compressed));
  }

  public static int numElements(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;
  }

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

  /** An iterator that loops through every element in each group. */
  private class UngroupedIterator implements Iterator<T> {
    private final Iterator<Object> iter = elements.iterator();
    int counter = 0;
    List<T> currentGroup;
    int listCounter = 0;

    @Override
    public boolean hasNext() {
      return counter < size;
    }

    @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
    @Override
    public T next() {
      counter++;
      if (currentGroup != null && listCounter < currentGroup.size()) {
        return currentGroup.get(listCounter++);
      }
      Object nextGroup = iter.next();
      if (nextGroup instanceof List) {
        currentGroup = (List<T>) nextGroup;
        listCounter = 1;
        // GroupedLists shouldn't have empty lists stored.
        return currentGroup.get(0);
      } else {
        currentGroup = null;
        return (T) nextGroup;
      }
    }
  }

  @ThreadHostile
  public Iterable<T> getAllElementsAsIterable() {
    return UngroupedIterator::new;
  }

  @Override
  public boolean equals(Object other) {
    if (other == null) {
      return false;
    }
    if (this.getClass() != other.getClass()) {
      return false;
    }
    GroupedList<?> that = (GroupedList<?>) other;
    // We must check the deps, ignoring the ordering of deps in the same group.
    if (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<Collection<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 Collection<T> next() {
      Object obj = iter.next();
      if (obj instanceof List) {
        return (List<T>) obj;
      }
      return ImmutableList.of((T) obj);
    }
  }

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

  /**
   * Removes everything in toRemove from the list of lists, elements. Called both by GroupedList and
   * GroupedListHelper.
   */
  private static <E> List<Object> remove(List<Object> elements, Set<E> toRemove) {
    if (toRemove.isEmpty()) {
      return elements;
    }
    int removedCount = 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<E> newGroup = new ImmutableList.Builder<>();
        @SuppressWarnings("unchecked")
        List<E> oldGroup = (List<E>) obj;
        for (E elt : oldGroup) {
          if (toRemove.contains(elt)) {
            removedCount++;
          } else {
            newGroup.add(elt);
          }
        }
        ImmutableList<E> group = newGroup.build();
        addItem(group, newElements);
      } else {
        if (toRemove.contains(obj)) {
          removedCount++;
        } else {
          newElements.add(obj);
        }
      }
    }
    // removedCount can be larger if elements had duplicates and the duplicate was also in toRemove.
    Preconditions.checkState(
        removedCount >= toRemove.size(),
        "removedCount=%s, toRemove.size()=%s, elements=%s toRemove=%s newElements=%s",
        removedCount,
        toRemove.size(),
        elements,
        toRemove,
        newElements);
    return newElements;
  }

  /**
   * If {@param item} is empty, this function does nothing.
   *
   * <p>If it contains a single element, then that element must not be {@code null}, and that
   * element is added to {@param elements}.
   *
   * <p>If it contains more than one element, then an {@link ImmutableList} copy of {@param item} is
   * added as the next element of {@param elements}. (This means {@param 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 addItem(Collection<?> item, List<Object> elements) {
    switch (item.size()) {
      case 0:
        return;
      case 1:
        elements.add(Preconditions.checkNotNull(Iterables.getOnlyElement(item), elements));
        return;
      default:
        elements.add(ImmutableList.copyOf(item));
    }
  }

  /**
   * Builder-like object for GroupedLists. An already-existing grouped list is appended to by
   * constructing a helper, mutating it, and then appending that helper to the grouped list.
   *
   * <p>Duplicate elements may be encountered while iterating through this object.
   */
  public static class GroupedListHelper<E> implements Iterable<E> {
    // Non-final only for removal.
    private List<Object> groupedList;
    private List<E> currentGroup = null;
    private final List<E> elements;

    public GroupedListHelper() {
      // Optimize for short lists.
      groupedList = new ArrayList<>(1);
      elements = new ArrayList<>(1);
    }

    /** Create with a copy of the contents of {@param elements} as the initial group. */
    private GroupedListHelper(E element) {
      // Optimize for short lists.
      groupedList = new ArrayList<>(1);
      groupedList.add(element);
      this.elements = new ArrayList<>(1);
      this.elements.add(element);
    }

    /**
     * Add an element to this list. If in a group, will be added to the current group. Otherwise,
     * goes in a group of its own.
     */
    public void add(E elt) {
      elements.add(Preconditions.checkNotNull(elt, "%s %s", elt, this));
      if (currentGroup == null) {
        groupedList.add(elt);
      } else {
        currentGroup.add(elt);
      }
    }

    /**
     * Remove all elements of toRemove from this list. It is a fatal error if any elements of
     * toRemove are not present. Takes time proportional to the size of the list, so should not be
     * called often.
     */
    public void remove(Set<E> toRemove) {
      groupedList = GroupedList.remove(groupedList, toRemove);
      elements.removeAll(toRemove);
    }

    /**
     * Starts a group. All elements added until {@link #endGroup} will be in the same group. Each
     * call of startGroup must be paired with a following {@link #endGroup} call. Any duplicate
     * elements added to this group will be silently deduplicated.
     */
    public void startGroup() {
      Preconditions.checkState(currentGroup == null, this);
      currentGroup = new ArrayList<>();
    }

    /**
     * Starts a group with an initial capacity. All elements added until {@link #endGroup} will be
     * in the same group. Each call of startGroup must be paired with a following {@link #endGroup}
     * call. Any duplicate elements added to this group will be silently deduplicated.
     */
    public void startGroup(int expectedGroupSize) {
      Preconditions.checkState(currentGroup == null, this);
      currentGroup = new ArrayList<>(expectedGroupSize);
    }

    /** Ends a group started with {@link #startGroup}. */
    public void endGroup() {
      Preconditions.checkNotNull(currentGroup);
      addItem(currentGroup, groupedList);
      currentGroup = null;
    }

    /**
     * Returns true if elt is present in the list. Takes time proportional to the list size, so
     * should not be called routinely.
     */
    public boolean contains(E elt) {
      return elements.contains(elt);
    }

    @Override
    public Iterator<E> iterator() {
      return elements.iterator();
    }

    /** Create a GroupedListHelper from a single element. */
    public static <F> GroupedListHelper<F> create(F element) {
      return new GroupedListHelper<>(element);
    }

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