Open source tests for android/ziputils.

--
MOS_MIGRATED_REVID=97677526

1 files changed, 345 insertions, 0 deletions

diff --git a/src/test/java/com/google/devtools/build/android/ziputils/SplitterTest.java b/src/test/java/com/google/devtools/build/android/ziputils/SplitterTest.java
new file mode 100644
index 0000000000..7b791c0f75
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/android/ziputils/SplitterTest.java
@@ -0,0 +1,345 @@
+// Copyright 2015 Google Inc. 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.android.ziputils;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.Range;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Unit tests for {@link Splitter}.
+ */
+@RunWith(JUnit4.class)
+public class SplitterTest {
+
+  private static final String ARCHIVE_DIR_SUFFIX = "/";
+  private static final String ARCHIVE_FILE_SEPARATOR = "/";
+  private static final String CLASS_SUFFIX = ".class";
+
+  @Test
+  public void testAssign() {
+
+    int size = 10;
+
+    Collection<String> input;
+    ArrayList<String> filter;
+    Map<String, Integer> output;
+
+    input = genEntries(size, size);
+    filter = new ArrayList<>(10);
+    for (int i = 0; i < size; i++) {
+      filter.add("dir" + i + ARCHIVE_FILE_SEPARATOR + "file" + i + CLASS_SUFFIX);
+    }
+    Splitter splitter = new Splitter(size + 1, input.size());
+    splitter.assign(filter);
+    splitter.nextShard();
+    output = new LinkedHashMap<>();
+    for (String path : input) {
+      output.put(path, splitter.assign(path));
+    }
+
+    for (int i = 0; i < size; i++) {
+      for (int j = 0; j < size; j++) {
+        String path = "dir" + i + ARCHIVE_FILE_SEPARATOR + "file" + j + CLASS_SUFFIX;
+        if (i == j) {
+          assertThat(output.get(path)).isEqualTo(0);
+        } else {
+          assertThat(output.get(path)).isEqualTo(i + 1);
+        }
+      }
+    }
+  }
+
+
+  /**
+   * Test splitting of single-ile packages. Note, this is also testing for the situation
+   * where input entries are unordered, and thus appearing to be in different packages,
+   * to the implementation that only confiders the previous file to determine package
+   * boundaries.
+   */
+  @Test
+  public void testSingleFilePackages() {
+    int[][] params = {
+      { 1, 1, 1},  // one shard, for one package with one file
+      {1, 2, 1},   // one shard, for two packages, with one file each
+      {1, 10, 1},  // one shard, for ten packages, with one file each
+      {2, 2, 1},   // ...
+      {2, 10, 1},
+      {2, 100, 1},
+      {10, 10, 1},
+      {10, 15, 1},
+      {10, 95, 1},
+      {97, 10000, 1},
+    };
+    comboRunner(params);
+  }
+
+  /**
+   * Test cases where the number of shards is less than the number
+   * of packages. This implies that the package size is less than
+   * the average shard size. We expect shards to be multiple of
+   * package size.
+   */
+  @Test
+  public void testPackageSplit() {
+    int[][] params = {
+      {2, 3, 2},  // two shards, for three packages, with two files each
+      {2, 3, 9},  // ...
+      {2, 3, 10},
+      {2, 3, 11},
+      {2, 3, 19},
+
+      {2, 10, 2},
+      {2, 10, 9},
+      {2, 10, 10},
+      {2, 10, 11},
+      {2, 10, 19},
+
+      {10, 11, 2},
+      {10, 11, 9},
+      {10, 11, 10},
+      {10, 11, 11},
+      {10, 11, 19},
+
+      {10, 111, 2},
+      {10, 111, 9},
+      {10, 111, 10},
+      {10, 111, 11},
+      {10, 111, 19},
+
+      {25, 1000, 8},
+      {25, 1000, 10},
+      {25, 1000, 19},
+
+      {250, 10000, 19},
+    };
+    comboRunner(params);
+  }
+
+  /**
+   * Tests situations where the number of shards exceeds the number of
+   * packages (but not the number of files). That is, the implementation
+   * must split at least one package.
+   */
+  @Test
+  public void testForceSplit() {
+    int[][] params = {
+      {2, 1, 2},  // two shards, for one package, with two files
+      {2, 1, 9},  // ...
+      {2, 1, 10},
+      {2, 1, 11},
+
+      {3, 2, 2},
+      {10, 9, 2},
+      {10, 2, 9},
+      {10, 9, 9},
+      {10, 2, 10},
+      {10, 9, 10},
+      {10, 2, 11},
+      {10, 9, 11},
+      {10, 2, 111},
+      {10, 9, 111},
+
+      {100, 12, 9},
+      {100, 12, 9},
+      {100, 10, 10},
+      {100, 10, 10},
+      {100, 10, 11},
+      {100, 20, 111},
+    };
+    comboRunner(params);
+  }
+
+  /**
+   * Tests situation where the number of shards requested exceeds the
+   * the number of files. Empty shards are expected.
+   */
+  @Test
+  public void testEmptyShards() {
+    int[][] params = {
+      {2, 1, 1},  // two shards, for one package, with one files
+      {10, 2, 2},
+      {100, 10, 9},
+      {100, 9, 10},
+    };
+    comboRunner(params);
+  }
+
+  /**
+   * Run multiple test for sets of test specifications consisting of
+   * "number of shards", "number of packages", "package size".
+   */
+  private void comboRunner(int[][] params) {
+
+    Collection<String> input;
+    Map<String, Integer> output;
+
+    for (int[] param : params) {
+      input = genEntries(param[1], param[2]);
+      output = runOne(param[0], input);
+      splitAsserts(param[0], param[1], param[2],
+          commonAsserts(param[0], param[1], param[2], input, output));
+    }
+  }
+
+  private Map<String, Integer> runOne(int shards, Collection<String> entries) {
+    Splitter splitter = new Splitter(shards, entries.size());
+    Map<String, Integer> result = new LinkedHashMap<>();
+    for (String entry : entries) {
+      result.put(entry, splitter.assign(entry));
+    }
+    return result;
+  }
+
+  private Collection<String> genEntries(int packages, int files) {
+    List<String> entries = new ArrayList<>();
+    for (int dir = 0; dir < packages; dir++) {
+      for (int file = 0; file < files; file++) {
+        entries.add("dir" + dir + ARCHIVE_FILE_SEPARATOR + "file" + file + CLASS_SUFFIX);
+      }
+    }
+    return entries;
+  }
+
+  private int[] assertAndCountMappings(int shards, int packageSize,
+    Map<String, Integer> output) {
+    int[] counts = new int[shards + 1];
+    String prevPath = null;
+    int prev = -2;
+    for (Map.Entry<String, Integer> entry : output.entrySet()) {
+      String path = entry.getKey();
+      int assignment = entry.getValue();
+      assertThat(assignment).isIn(Range.closed(0, shards));
+      counts[assignment + 1]++;
+      if (path.endsWith(CLASS_SUFFIX)) {
+        if (prev == -2) {
+          assertThat(assignment).isEqualTo(0);
+        } else if (prev > 0 && prev != assignment) {
+          String prevDir = prevPath.substring(0, prevPath.lastIndexOf(ARCHIVE_DIR_SUFFIX));
+          String dir = path.substring(0, path.lastIndexOf(ARCHIVE_DIR_SUFFIX));
+          assertThat(assignment).isEqualTo(prev + 1); // shard index increasing
+          // package boundary, or partial package
+          assertThat(!prevDir.equals(dir) || counts[prev + 1] % packageSize != 0).isTrue();
+        }
+        prevPath = path;
+      }
+      prev = assignment;
+    }
+    return counts;
+  }
+
+  /**
+   * Validate that generated mapping maintains input order.
+   */
+  private void assertMaintainOrder(Collection<String> input, Map<String, Integer> output) {
+    assertThat(output.keySet()).containsExactlyElementsIn(input).inOrder();
+  }
+
+  /**
+   * Verifies that packages have not been unnecessarily split.
+   */
+  private void assertNoSplit(int packageSize, int[] counts) {
+    for (int i = 1; i < counts.length; i++) {
+      assertThat(counts[i] % packageSize).isEqualTo(0);
+    }
+  }
+
+  /**
+   * Verifies the presence of package-split in the tailing shards.
+   */
+  private void assertHasSplit(int packageSize, int[] counts) {
+    for (int i = 1; i < counts.length - 1; i++) {
+      if (counts[i + 1] <= 1) {
+        continue;
+      }
+      assertThat(counts[i] % packageSize).isEqualTo(0);
+    }
+  }
+
+  /**
+   * Verify the presence of tailing empty shards, if unavoidable.
+   */
+  private void assertHasEmpty(int[] counts, boolean expectEmpty) {
+    boolean hasEmpty = false;
+    for (int i = 1; i < counts.length; i++) {
+      if (counts[i] == 0) {
+        hasEmpty = true;
+      } else {
+        assertThat(!hasEmpty || counts[i] == 0).isTrue();
+      }
+    }
+    assertThat(hasEmpty).isEqualTo(expectEmpty);
+  }
+
+  /**
+   * Validates that each chard meets expected minimal and maximum size requirements,
+   * to ensure that shards are reasonably evenly sized.
+   */
+  private void assertBalanced(int shards, int packageCount, int packageSize, int entries,
+      int[] counts) {
+    int classes = packageSize * packageCount;
+    int noneClass = entries - counts[0] - classes;
+    int idealSize = Math.max(1, classes / shards);
+    int superSize = Math.max(1, entries / shards);
+    int almostFull = Math.min(Math.min(10, (idealSize + 3) >> 2), (int) Math.log(shards));
+    int lowerBound =  idealSize -  almostFull;
+    int upperBound = superSize + Math.max(packageSize, (int) (Math.log(shards)) * 10);
+    for (int i = 1; i < counts.length; i++) {
+      int adjusted = i == 1 ? counts[i] - noneClass : counts[i];
+      if (i < shards && counts[i + 1] > 1) {
+        assertThat(counts[i]).isIn(Range.closed(packageSize, entries));
+        if (noneClass == 0 && counts[0] == 0) {
+          assertThat(counts[i]).isIn(Range.closed(lowerBound, entries));
+        }
+      }
+      assertThat(adjusted).isIn(Range.closed(0, upperBound));
+    }
+  }
+
+  /**
+   * Verifies that packages are only split as expected, and that no unexpected
+   * empty shards are generated.
+   */
+  private void splitAsserts(int shards, int packageCount, int packageSize, int[] counts) {
+    boolean emptyExpected = packageCount * packageSize < shards;
+    boolean splitExpected = shards > packageCount;
+    if (splitExpected) {
+      assertHasSplit(packageSize, counts);
+    } else {
+      assertNoSplit(packageSize, counts);
+    }
+    assertHasEmpty(counts, emptyExpected);
+  }
+
+  /**
+   * Checks assert applicable to all tests.
+   */
+  private int[] commonAsserts(int shards, int packageCount, int packageSize,
+      Collection<String> input, Map<String, Integer> output) {
+    assertMaintainOrder(input, output);
+    int[] counts = assertAndCountMappings(shards, packageSize, output);
+    assertBalanced(shards, packageCount, packageSize, input.size(), counts);
+    return counts;
+  }
+}