diff options
author | 2015-02-25 16:45:20 +0100 | |
---|---|---|
committer | 2015-02-25 16:45:20 +0100 | |
commit | d08b27fa9701fecfdb69e1b0d1ac2459efc2129b (patch) | |
tree | 5d50963026239ca5aebfb47ea5b8db7e814e57c8 /src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java |
Update from Google.
--
MOE_MIGRATED_REVID=85702957
Diffstat (limited to 'src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java')
-rw-r--r-- | src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java | 134 |
1 files changed, 134 insertions, 0 deletions
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java new file mode 100644 index 0000000000..9764f4df53 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java @@ -0,0 +1,134 @@ +// Copyright 2014 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.lib.collect.nestedset; + +import static org.junit.Assert.assertEquals; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; + +import junit.framework.TestCase; + +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.LinkedHashSet; +import java.util.List; +import java.util.Random; + +/** + * Tests for {@link RecordingUniqueifier}. + */ +@RunWith(JUnit4.class) +public class RecordingUniqueifierTest extends TestCase { + + private static final Random RANDOM = new Random(); + + private static final int VERY_SMALL = 3; // one byte + private static final int SMALL = 11; // two bytes + private static final int MEDIUM = 18; // three bytes -- unmemoed + // For this one, the "* 8" is a bytes to bits (1 memo is 1 bit) + private static final int LARGE = (RecordingUniqueifier.LENGTH_THRESHOLD * 8) + 3; + + private static final int[] SIZES = new int[] {VERY_SMALL, SMALL, MEDIUM, LARGE}; + + private void doTest(int uniqueInputs, int deterministicHeadSize) throws Exception { + Preconditions.checkArgument(deterministicHeadSize <= uniqueInputs, + "deterministicHeadSize must be smaller than uniqueInputs"); + + // Setup + + List<Integer> inputList = new ArrayList<>(uniqueInputs); + Collection<Integer> inputsDeduped = new LinkedHashSet<>(uniqueInputs); + + for (int i = 0; i < deterministicHeadSize; i++) { // deterministic head + inputList.add(i); + inputsDeduped.add(i); + } + + while (inputsDeduped.size() < uniqueInputs) { // random selectees + Integer i = RANDOM.nextInt(uniqueInputs); + inputList.add(i); + inputsDeduped.add(i); + } + + // Unmemoed run + + List<Integer> firstList = new ArrayList<>(uniqueInputs); + RecordingUniqueifier recordingUniqueifier = new RecordingUniqueifier(); + for (Integer i : inputList) { + if (recordingUniqueifier.isUnique(i)) { + firstList.add(i); + } + } + + // Potentially memo'ed run + + List<Integer> secondList = new ArrayList<>(uniqueInputs); + Object memo = recordingUniqueifier.getMemo(); + Uniqueifier uniqueifier = RecordingUniqueifier.createReplayUniqueifier(memo); + for (Integer i : inputList) { + if (uniqueifier.isUnique(i)) { + secondList.add(i); + } + } + + // Evaluate results + + inputsDeduped = ImmutableList.copyOf(inputsDeduped); + assertEquals("Unmemo'ed run has unexpected contents", inputsDeduped, firstList); + assertEquals("Memo'ed run has unexpected contents", inputsDeduped, secondList); + } + + private void doTestWithLucidException(int uniqueInputs, int deterministicHeadSize) + throws Exception { + try { + doTest(uniqueInputs, deterministicHeadSize); + } catch (Exception e) { + throw new Exception("Failure in size: " + uniqueInputs, e); + } + } + + @Test + public void noInputs() throws Exception { + doTestWithLucidException(0, 0); + } + + @Test + public void allUnique() throws Exception { + for (int size : SIZES) { + doTestWithLucidException(size, size); + } + } + + @Test + public void fuzzedWithDeterministic2() throws Exception { + // The way that it is used, we know that the first two additions are not equal. + // Optimizations were made for this case in small memos. + for (int size : SIZES) { + doTestWithLucidException(size, 2); + } + } + + @Test + public void fuzzedWithDeterministic2_otherSizes() throws Exception { + for (int i = 0; i < 100; i++) { + int size = RANDOM.nextInt(10000) + 2; + doTestWithLucidException(size, 2); + } + } +} |