src/test/java/com/google/devtools/build/android/ziputils/SplitterTest.java - bazel - Git at Google

 // 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.android.ziputils;

 import static com.google.common.truth.Truth.assertThat;
 import static com.google.common.truth.Truth.assertWithMessage;

 import com.google.common.collect.Range;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;

 /**
  * 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) {
           assertWithMessage(path).that(output.get(path)).isEqualTo(0);
         } else {
           assertWithMessage(path).that(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);
       String name = Arrays.toString(param);
       splitAsserts(name, param[0], param[1], param[2],
           commonAsserts(name, 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, boolean expectPackageBoundaryShards) {
     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) {
           assertThat(assignment).isEqualTo(prev + 1); // shard index increasing
           if (expectPackageBoundaryShards) {
             String prevDir = prevPath.substring(0, prevPath.lastIndexOf(ARCHIVE_DIR_SUFFIX));
             String dir = path.substring(0, path.lastIndexOf(ARCHIVE_DIR_SUFFIX));
             // package boundary, or full packages
             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(String name, int packageSize, int[] counts) {
     for (int i = 1; i < counts.length; i++) {
       assertWithMessage(name + " shard " + i).that(counts[i]).isAtLeast(0);
     }
   }

   /**
    * Verifies the presence of package-split in the tailing shards.
    */
   private void assertHasSplit(String name, int packageSize, int[] counts) {
     for (int i = 1; i < counts.length - 1; i++) {
       if (counts[i + 1] <= 1) {
         continue;
       }
       assertWithMessage(name + " shard " + i).that(counts[i]).isAtMost(packageSize);
     }
   }

   /**
    * Verify the presence of tailing empty shards, if unavoidable.
    */
   private void assertHasEmpty(String name, 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();
       }
     }
     assertWithMessage(name).that(hasEmpty).isEqualTo(expectEmpty);
   }

   /**
    * Validates that each shard meets expected minimal and maximum size requirements,
    * to ensure that shards are reasonably evenly sized.
    */
   private void assertBalanced(String name, 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 delta = Math.min(Math.min(10, (idealSize + 3) >> 2), (int) Math.log(shards));
     int lowerBound = idealSize - delta;
     int upperBound = idealSize + delta;
     for (int i = 1; i < counts.length; i++) {
       int adjusted = i == 1 ? counts[i] - noneClass : counts[i];
       if (i < shards && counts[i + 1] > 1) {
         if (shards <= packageCount) {
           // if there are fewer shards than packages, expect shards contain at least 1 full package
           assertWithMessage(name + " dense shard " + i)
               .that(counts[i])
               .isIn(Range.closed(packageSize, entries));
         } else {
           assertWithMessage(name + " sparse shard " + i)
               .that(counts[i])
               .isIn(Range.closed(0, packageSize));
         }
         if (noneClass == 0 && counts[0] == 0) {
           // Give some slack in minimal number of entries in a shard because Splitter recomputes
           // boundaries for each shard, so our computed bounds can be off for later shards.
           assertWithMessage(name + " shard " + i)
               .that(counts[i])
               .isIn(Range.closed(lowerBound - i, entries));
         }
       }
       // Give some slack in maximum number of entries in a shard because Splitter recomputes
       // boundaries for each shard, so our computed bounds can be off for later shards.
       assertWithMessage(name + " shard " + i).that(adjusted).isAtMost(upperBound + i);
     }
   }

   /**
    * Verifies that packages are only split as expected, and that no unexpected
    * empty shards are generated.
    */
   private void splitAsserts(String name, int shards, int packageCount, int packageSize,
       int[] counts) {
     boolean emptyExpected = packageCount * packageSize < shards;
     boolean splitExpected = shards > packageCount;
     if (splitExpected) {
       assertHasSplit(name, packageSize, counts);
     } else {
       assertNoSplit(name, packageSize, counts);
     }
     assertHasEmpty(name, counts, emptyExpected);
   }

   /**
    * Checks assert applicable to all tests.
    */
   private int[] commonAsserts(String name, int shards, int packageCount, int packageSize,
       Collection<String> input, Map<String, Integer> output) {
     assertMaintainOrder(input, output);
     int[] counts = assertAndCountMappings(shards, packageSize, output, packageCount <= shards);
     assertBalanced(name, shards, packageCount, packageSize, input.size(), counts);
     return counts;
   }
 }
	// 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.android.ziputils;

	import static com.google.common.truth.Truth.assertThat;
	import static com.google.common.truth.Truth.assertWithMessage;

	import com.google.common.collect.Range;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.LinkedHashMap;
	import java.util.List;
	import java.util.Map;
	import org.junit.Test;
	import org.junit.runner.RunWith;
	import org.junit.runners.JUnit4;

	/**
	* 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) {
	assertWithMessage(path).that(output.get(path)).isEqualTo(0);
	} else {
	assertWithMessage(path).that(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);
	String name = Arrays.toString(param);
	splitAsserts(name, param[0], param[1], param[2],
	commonAsserts(name, 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, boolean expectPackageBoundaryShards) {
	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) {
	assertThat(assignment).isEqualTo(prev + 1); // shard index increasing
	if (expectPackageBoundaryShards) {
	String prevDir = prevPath.substring(0, prevPath.lastIndexOf(ARCHIVE_DIR_SUFFIX));
	String dir = path.substring(0, path.lastIndexOf(ARCHIVE_DIR_SUFFIX));
	// package boundary, or full packages
	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(String name, int packageSize, int[] counts) {
	for (int i = 1; i < counts.length; i++) {
	assertWithMessage(name + " shard " + i).that(counts[i]).isAtLeast(0);
	}
	}

	/**
	* Verifies the presence of package-split in the tailing shards.
	*/
	private void assertHasSplit(String name, int packageSize, int[] counts) {
	for (int i = 1; i < counts.length - 1; i++) {
	if (counts[i + 1] <= 1) {
	continue;
	}
	assertWithMessage(name + " shard " + i).that(counts[i]).isAtMost(packageSize);
	}
	}

	/**
	* Verify the presence of tailing empty shards, if unavoidable.
	*/
	private void assertHasEmpty(String name, 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();
	}
	}
	assertWithMessage(name).that(hasEmpty).isEqualTo(expectEmpty);
	}

	/**
	* Validates that each shard meets expected minimal and maximum size requirements,
	* to ensure that shards are reasonably evenly sized.
	*/
	private void assertBalanced(String name, 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 delta = Math.min(Math.min(10, (idealSize + 3) >> 2), (int) Math.log(shards));
	int lowerBound = idealSize - delta;
	int upperBound = idealSize + delta;
	for (int i = 1; i < counts.length; i++) {
	int adjusted = i == 1 ? counts[i] - noneClass : counts[i];
	if (i < shards && counts[i + 1] > 1) {
	if (shards <= packageCount) {
	// if there are fewer shards than packages, expect shards contain at least 1 full package
	assertWithMessage(name + " dense shard " + i)
	.that(counts[i])
	.isIn(Range.closed(packageSize, entries));
	} else {
	assertWithMessage(name + " sparse shard " + i)
	.that(counts[i])
	.isIn(Range.closed(0, packageSize));
	}
	if (noneClass == 0 && counts[0] == 0) {
	// Give some slack in minimal number of entries in a shard because Splitter recomputes
	// boundaries for each shard, so our computed bounds can be off for later shards.
	assertWithMessage(name + " shard " + i)
	.that(counts[i])
	.isIn(Range.closed(lowerBound - i, entries));
	}
	}
	// Give some slack in maximum number of entries in a shard because Splitter recomputes
	// boundaries for each shard, so our computed bounds can be off for later shards.
	assertWithMessage(name + " shard " + i).that(adjusted).isAtMost(upperBound + i);
	}
	}

	/**
	* Verifies that packages are only split as expected, and that no unexpected
	* empty shards are generated.
	*/
	private void splitAsserts(String name, int shards, int packageCount, int packageSize,
	int[] counts) {
	boolean emptyExpected = packageCount * packageSize < shards;
	boolean splitExpected = shards > packageCount;
	if (splitExpected) {
	assertHasSplit(name, packageSize, counts);
	} else {
	assertNoSplit(name, packageSize, counts);
	}
	assertHasEmpty(name, counts, emptyExpected);
	}

	/**
	* Checks assert applicable to all tests.
	*/
	private int[] commonAsserts(String name, int shards, int packageCount, int packageSize,
	Collection<String> input, Map<String, Integer> output) {
	assertMaintainOrder(input, output);
	int[] counts = assertAndCountMappings(shards, packageSize, output, packageCount <= shards);
	assertBalanced(name, shards, packageCount, packageSize, input.size(), counts);
	return counts;
	}
	}