Refactor SkylarkStatistics to reduce size.

Does not save all Tasks anymore and generates TasksStatistics on the fly.
Adds an ArrayList implementation for primitive longs to efficiently save a lot
of task duration data. Necessary when loading lots of profile files.

--
MOS_MIGRATED_REVID=104656311

1 files changed, 285 insertions, 0 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/util/LongArrayList.java b/src/main/java/com/google/devtools/build/lib/util/LongArrayList.java
new file mode 100644
index 0000000000..d3ebb3cc18
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/LongArrayList.java
@@ -0,0 +1,285 @@
+// Copyright 2015 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.Preconditions;
+
+import java.util.Arrays;
+
+/**
+ * A list of primitive long values.
+ *
+ * <p>Grows its backing array internally when necessary and such that constant amortized addition of
+ * elements is guaranteed.
+ *
+ * <p>Does not shrink its array except by explicit calls to {@link #trim}.
+ */
+public class LongArrayList {
+
+  private static final int DEFAULT_CAPACITY = 12;
+
+  private long[] array;
+  private int size;
+
+  /**
+   * Initialize a new LongArrayList with default capacity.
+   */
+  public LongArrayList() {
+    this.array = new long[DEFAULT_CAPACITY];
+  }
+
+  /**
+   * Initialize a new LongArrayList with space for elements equal to the given capacity.
+   * @throws IndexOutOfBoundsException if the capacity is negative
+   */
+  public LongArrayList(int capacity) {
+    Preconditions.checkArgument(capacity >= 0, "Initial capacity must not be negative.");
+    this.array = new long[capacity];
+  }
+
+  /**
+   * Create a new LongArrayList backed by the given array. No copy is made.
+   */
+  public LongArrayList(long[] array) {
+    Preconditions.checkNotNull(array);
+    this.array = array;
+    this.size = array.length;
+  }
+
+  /**
+   * Add a value at a specific position to this list. All elements at larger indices will
+   * shift to the right by one.
+   * @param position may be any index within the array or equal to the size, to append at the end
+   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
+   */
+  public void add(int position, long value) {
+    Preconditions.checkPositionIndex(position, size);
+    copyBackAndGrow(position, 1);
+    set(position, value);
+  }
+
+  /**
+   * Add a value to the end of this list.
+   */
+  public void add(long value) {
+    add(size, value);
+  }
+
+  /**
+   * Add all elements from another LongArrayList at the end of this one.
+   * @see #addAll(LongArrayList, int)
+   */
+  public boolean addAll(LongArrayList other) {
+    return addAll(other.array, 0, other.size, size);
+  }
+
+  /**
+   * Add all elements from another LongArrayList at a certain position within or at the end of
+   * this one.
+   * @param other
+   * @param position at which position to add these elements, adds at the end if equal to the size
+   * @return whether this list changed
+   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()}]
+   */
+  public boolean addAll(LongArrayList other, int position) {
+    return addAll(other.array, 0, other.size, position);
+  }
+
+  /**
+   * Add all elements from the given array to the end of this array.
+   * @see #addAll(long[], int, int, int)
+   */
+  public boolean addAll(long[] array) {
+    return addAll(array, 0, array.length, size);
+  }
+
+  /**
+   * Add certain elements from the given array to the end of this array.
+   * @see #addAll(long[], int, int, int)
+   */
+  public boolean addAll(long[] array, int fromIndex, int length) {
+    return addAll(array, fromIndex, length, size);
+  }
+
+  /**
+   * Add certain elements from the given array at a certain position in this list.
+   * @param array the array from which to take the elements
+   * @param fromIndex the position of the first element to add
+   * @param length how many elements to add
+   * @param position at which position to add these elements, adds at the end if equal to the size
+   * @return whether this list has changed
+   * @throws IndexOutOfBoundsException if fromIndex and length violate the boundaries of the given
+   *    array or atIndex is not a valid index in this array or equal to the size
+   */
+  public boolean addAll(long[] array, int fromIndex, int length, int position) {
+    Preconditions.checkNotNull(array);
+    Preconditions.checkPositionIndex(fromIndex + length, array.length);
+    if (length == 0) {
+      return false;
+    }
+    // check other positions later to allow "adding" empty arrays anywhere within this array
+    Preconditions.checkElementIndex(fromIndex, array.length);
+    Preconditions.checkPositionIndex(position, size);
+    copyBackAndGrow(position, length);
+    System.arraycopy(array, fromIndex, this.array, position, length);
+    return true;
+  }
+
+  /**
+   * Resize the backing array to fit at least this many elements if necessary.
+   */
+  public void ensureCapacity(int capacity) {
+    if (capacity > array.length) {
+      long[] newArray = new long[growCapacity(capacity)];
+      System.arraycopy(array, 0, newArray, 0, size);
+      array = newArray;
+    }
+  }
+
+  /**
+   * @return the element at the specified index
+   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
+   */
+  public long get(int index) {
+    Preconditions.checkElementIndex(index, size);
+    return array[index];
+  }
+
+  /**
+   * Search for the first index at which the given value is found.
+   * @return -1 if the value is not found, the index at which it was found otherwise
+   */
+  public int indexOf(long value) {
+    for (int index = 0; index < size; index++) {
+      if (array[index] == value) {
+        return index;
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Remove the element at the specified index and shift all elements at higher indices down by
+   * one.
+   * @return the removed element
+   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
+   */
+  public long remove(int index) {
+    Preconditions.checkElementIndex(index, size);
+    long previous = array[index];
+    System.arraycopy(array, index + 1, array, index, size - index - 1);
+    size--;
+    return previous;
+  }
+
+  /**
+   * Remove the first occurrence of a value and shift all elements at higher indices down by one.
+   * @return true, if the list changed and thus contained the value, false otherwise
+   */
+  public boolean remove(long value) {
+    int index = indexOf(value);
+    if (index == -1) {
+      return false;
+    }
+    remove(index);
+    return true;
+  }
+
+  /**
+   * Overwrites the element at a certain index with the given value and returns the previous
+   * element.
+   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
+   */
+  public long set(int index, long value) {
+    Preconditions.checkElementIndex(index, size);
+    long previous = array[index];
+    array[index] = value;
+    return previous;
+  }
+
+  /**
+   * @return the amount of elements in this list
+   */
+  public int size() {
+    return size;
+  }
+
+  /**
+   * Sort the list in ascending order.
+   */
+  public void sort() {
+    Arrays.sort(array, 0, size);
+  }
+
+  /**
+   * Sort the sub list from the first index (inclusive) to the second index (exclusive) in
+   * ascending order.
+   * @see Arrays#sort(long[], int, int)
+   * @throws IndexOutOfBoundsException if fromIndex is outside the interval [0, {@link #size()})
+   * or toIndex is outside [0, {@link #size()}]
+   */
+  public void sort(int fromIndex, int toIndex) {
+    Arrays.sort(array, fromIndex, toIndex);
+  }
+
+  /**
+   * Build a String of the form [0, 1, 2]
+   */
+  @Override
+  public String toString() {
+    final StringBuilder sb = new StringBuilder("[");
+    String separator = "";
+    for (int index = 0; index < size; index++) {
+      sb.append(separator);
+      sb.append(array[index]);
+      separator = ", ";
+    }
+    sb.append("]");
+    return sb.toString();
+  }
+
+  /**
+   * Remove any excess capacity to save space.
+   */
+  public void trim() {
+    if (size < array.length) {
+      long[] newArray = new long[size];
+      System.arraycopy(array, 0, newArray, 0, size);
+      array = newArray;
+    }
+  }
+
+  /**
+   * Copy the end of the array from a certain index back to make room for length many items and
+   * adds length to the size.
+   *
+   * @param fromIndex may be equal to the current size, then no element needs to be copied, but the
+   *    array may grow
+   */
+  private void copyBackAndGrow(int fromIndex, int length) {
+    int newSize = size + length;
+    ensureCapacity(newSize);
+    System.arraycopy(array, fromIndex, array, fromIndex + length, size - fromIndex);
+    size = newSize;
+  }
+
+  /**
+   * The new capacity when growing the array to contain at least newSize many elements.
+   * Uses a growth factor of 1.5.
+   */
+  private int growCapacity(int newSize) {
+    return newSize + newSize >> 1;
+  }
+}
+