Update from Google.

--
MOE_MIGRATED_REVID=85702957

6 files changed, 912 insertions, 0 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpanderTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpanderTest.java
new file mode 100644
index 0000000000..926ce2d77d
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpanderTest.java
@@ -0,0 +1,64 @@
+// 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 com.google.common.collect.ImmutableList;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.List;
+
+/**
+ * Tests for {@link CompileOrderExpander}.
+ */
+@RunWith(JUnit4.class)
+public class CompileOrderExpanderTest extends ExpanderTestBase {
+
+  @Override
+  protected Order expanderOrder() {
+    return Order.COMPILE_ORDER;
+  }
+
+  @Override
+  protected List<String> nestedResult() {
+    return ImmutableList.of("c", "a", "e", "b", "d");
+  }
+
+  @Override
+  protected List<String> nestedDuplicatesResult() {
+    return ImmutableList.of("c", "a", "e", "b", "d");
+  }
+
+  @Override
+  protected List<String> chainResult() {
+    return ImmutableList.of("c", "b", "a");
+  }
+
+  @Override
+  protected List<String> diamondResult() {
+    return ImmutableList.of("d", "b", "c", "a");
+  }
+
+  @Override
+  protected List<String> extendedDiamondResult() {
+    return ImmutableList.of("d", "e", "b", "c", "a");
+  }
+
+  @Override
+  protected List<String> extendedDiamondRightArmResult() {
+    return ImmutableList.of("d", "e", "b", "c2", "c", "a");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
new file mode 100644
index 0000000000..25448c6434
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
@@ -0,0 +1,330 @@
+// 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 static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+
+import junit.framework.TestCase;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Base class for tests of {@link NestedSetExpander} implementations.
+ *
+ * <p>This class provides test cases for representative nested set structures; the expected
+ * results must be provided by overriding the corresponding methods.
+ */
+public abstract class ExpanderTestBase extends TestCase  {
+
+  /**
+   * Returns the type of the expander under test.
+   */
+  protected abstract Order expanderOrder();
+
+  @Test
+  public void simple() {
+    NestedSet<String> s = prepareBuilder("c", "a", "b").build();
+
+    assertTrue(Arrays.equals(simpleResult().toArray(), s.directMembers()));
+    assertSetContents(simpleResult(), s);
+  }
+
+  @Test
+  public void simpleNoDuplicates() {
+    NestedSet<String> s = prepareBuilder("c", "a", "a", "a", "b").build();
+
+    assertTrue(Arrays.equals(simpleResult().toArray(), s.directMembers()));
+    assertSetContents(simpleResult(), s);
+  }
+
+  @Test
+  public void nesting() {
+    NestedSet<String> subset = prepareBuilder("c", "a", "e").build();
+    NestedSet<String> s = prepareBuilder("b", "d").addTransitive(subset).build();
+
+    assertSetContents(nestedResult(), s);
+  }
+
+  @Test
+  public void builderReuse() {
+    NestedSetBuilder<String> builder = prepareBuilder();
+    assertSetContents(Collections.<String>emptyList(), builder.build());
+
+    builder.add("b");
+    assertSetContents(ImmutableList.of("b"), builder.build());
+
+    builder.addAll(ImmutableList.of("d"));
+    Collection<String> expected = ImmutableList.copyOf(prepareBuilder("b", "d").build());
+    assertSetContents(expected, builder.build());
+
+    NestedSet<String> child = prepareBuilder("c", "a", "e").build();
+    builder.addTransitive(child);
+    assertSetContents(nestedResult(), builder.build());
+  }
+
+  @Test
+  public void builderChaining() {
+    NestedSet<String> s = prepareBuilder().add("b").addAll(ImmutableList.of("d"))
+        .addTransitive(prepareBuilder("c", "a", "e").build()).build();
+    assertSetContents(nestedResult(), s);
+  }
+
+  @Test
+  public void addAllOrdering() {
+    NestedSet<String> s1 = prepareBuilder().add("a").add("c").add("b").build();
+    NestedSet<String> s2 = prepareBuilder().addAll(ImmutableList.of("a", "c", "b")).build();
+
+    assertTrue(Arrays.equals(s1.directMembers(), s2.directMembers()));
+    assertCollectionsEqual(s1.toCollection(), s2.toCollection());
+    assertCollectionsEqual(s1.toList(), s2.toList());
+    assertCollectionsEqual(Lists.newArrayList(s1), Lists.newArrayList(s2));
+  }
+
+  @Test
+  public void mixedAddAllOrdering() {
+    NestedSet<String> s1 = prepareBuilder().add("a").add("b").add("c").add("d").build();
+    NestedSet<String> s2 = prepareBuilder().add("a").addAll(ImmutableList.of("b", "c")).add("d")
+        .build();
+
+    assertTrue(Arrays.equals(s1.directMembers(), s2.directMembers()));
+    assertCollectionsEqual(s1.toCollection(), s2.toCollection());
+    assertCollectionsEqual(s1.toList(), s2.toList());
+    assertCollectionsEqual(Lists.newArrayList(s1), Lists.newArrayList(s2));
+  }
+
+  @Test
+  public void transitiveDepsHandledSeparately() {
+    NestedSet<String> subset = prepareBuilder("c", "a", "e").build();
+    NestedSetBuilder<String> b = prepareBuilder();
+    // The fact that we add the transitive subset between the add("b") and add("d") calls should
+    // not change the result.
+    b.add("b");
+    b.addTransitive(subset);
+    b.add("d");
+    NestedSet<String> s = b.build();
+
+    assertSetContents(nestedResult(), s);
+  }
+
+  @Test
+  public void nestingNoDuplicates() {
+    NestedSet<String> subset = prepareBuilder("c", "a", "e").build();
+    NestedSet<String> s = prepareBuilder("b", "d", "e").addTransitive(subset).build();
+
+    assertSetContents(nestedDuplicatesResult(), s);
+  }
+
+  @Test
+  public void chain() {
+    NestedSet<String> c = prepareBuilder("c").build();
+    NestedSet<String> b = prepareBuilder("b").addTransitive(c).build();
+    NestedSet<String> a = prepareBuilder("a").addTransitive(b).build();
+
+    assertTrue(Arrays.equals(new String[]{"a"}, a.directMembers()));
+    assertSetContents(chainResult(), a);
+  }
+
+  @Test
+  public void diamond() {
+    NestedSet<String> d = prepareBuilder("d").build();
+    NestedSet<String> c = prepareBuilder("c").addTransitive(d).build();
+    NestedSet<String> b = prepareBuilder("b").addTransitive(d).build();
+    NestedSet<String> a = prepareBuilder("a").addTransitive(b).addTransitive(c).build();
+
+    assertTrue(Arrays.equals(new String[]{"a"}, a.directMembers()));
+    assertSetContents(diamondResult(), a);
+  }
+
+  @Test
+  public void extendedDiamond() {
+    NestedSet<String> d = prepareBuilder("d").build();
+    NestedSet<String> e = prepareBuilder("e").build();
+    NestedSet<String> b = prepareBuilder("b").addTransitive(d).addTransitive(e).build();
+    NestedSet<String> c = prepareBuilder("c").addTransitive(e).addTransitive(d).build();
+    NestedSet<String> a = prepareBuilder("a").addTransitive(b).addTransitive(c).build();
+    assertSetContents(extendedDiamondResult(), a);
+  }
+
+  @Test
+  public void extendedDiamondRightArm() {
+    NestedSet<String> d = prepareBuilder("d").build();
+    NestedSet<String> e = prepareBuilder("e").build();
+    NestedSet<String> b = prepareBuilder("b").addTransitive(d).addTransitive(e).build();
+    NestedSet<String> c2 = prepareBuilder("c2").addTransitive(e).addTransitive(d).build();
+    NestedSet<String> c = prepareBuilder("c").addTransitive(c2).build();
+    NestedSet<String> a = prepareBuilder("a").addTransitive(b).addTransitive(c).build();
+    assertSetContents(extendedDiamondRightArmResult(), a);
+  }
+
+  @Test
+  public void orderConflict() {
+    NestedSet<String> child1 = prepareBuilder("a", "b").build();
+    NestedSet<String> child2 = prepareBuilder("b", "a").build();
+    NestedSet<String> parent = prepareBuilder().addTransitive(child1).addTransitive(child2).build();
+    assertSetContents(orderConflictResult(), parent);
+  }
+
+  @Test
+  public void orderConflictNested() {
+    NestedSet<String> a = prepareBuilder("a").build();
+    NestedSet<String> b = prepareBuilder("b").build();
+    NestedSet<String> child1 = prepareBuilder().addTransitive(a).addTransitive(b).build();
+    NestedSet<String> child2 = prepareBuilder().addTransitive(b).addTransitive(a).build();
+    NestedSet<String> parent = prepareBuilder().addTransitive(child1).addTransitive(child2).build();
+    assertSetContents(orderConflictResult(), parent);
+  }
+
+  @Test
+  public void getOrderingEmpty() {
+    NestedSet<String> s = prepareBuilder().build();
+    assertTrue(s.isEmpty());
+    assertEquals(expanderOrder(), s.getOrder());
+  }
+
+  @Test
+  public void getOrdering() {
+    NestedSet<String> s = prepareBuilder("a", "b").build();
+    assertTrue(!s.isEmpty());
+    assertEquals(expanderOrder(), s.getOrder());
+  }
+
+  /**
+   * In case we have inner NestedSets with different order (allowed by the builder). We should
+   * maintain the order of the top-level NestedSet.
+   */
+  @Test
+  public void regressionOnOneTransitiveDep() {
+    NestedSet<String> subsub = NestedSetBuilder.<String>stableOrder().add("c").add("a").add("e")
+        .build();
+    NestedSet<String> sub = NestedSetBuilder.<String>stableOrder().add("b").add("d")
+        .addTransitive(subsub).build();
+    NestedSet<String> top = prepareBuilder().addTransitive(sub).build();
+    assertSetContents(nestedResult(), top);
+  }
+
+  @Test
+  public void nestingValidation() {
+    for (Order ordering : Order.values()) {
+      NestedSet<String> a = prepareBuilder("a", "b").build();
+      NestedSetBuilder<String> b = new NestedSetBuilder<>(ordering);
+      try {
+        b.addTransitive(a);
+        if (ordering != expanderOrder() && ordering != Order.STABLE_ORDER) {
+          fail();  // An exception was expected.
+        }
+      } catch (IllegalStateException e) {
+        if (ordering == expanderOrder() || ordering == Order.STABLE_ORDER) {
+          fail();  // No exception was expected.
+        }
+      }
+    }
+  }
+
+  private NestedSetBuilder<String> prepareBuilder(String... directMembers) {
+    NestedSetBuilder<String> builder = new NestedSetBuilder<>(expanderOrder());
+    builder.addAll(Lists.newArrayList(directMembers));
+    return builder;
+  }
+
+  protected final void assertSetContents(Collection<String> expected, NestedSet<String> set) {
+    assertEquals(expected, Lists.newArrayList(set));
+    assertEquals(expected, Lists.newArrayList(set.toCollection()));
+    assertEquals(expected, Lists.newArrayList(set.toList()));
+    assertEquals(expected, Lists.newArrayList(set.toSet()));
+  }
+
+  protected final void assertCollectionsEqual(
+      Collection<String> expected, Collection<String> actual) {
+    assertEquals(Lists.newArrayList(expected), Lists.newArrayList(actual));
+  }
+
+  /**
+   * Returns the enumeration of the nested set {"c", "a", "b"} in the
+   * implementation's enumeration order.
+   *
+   * @see #testSimple()
+   * @see #testSimpleNoDuplicates()
+   */
+  protected List<String> simpleResult() {
+    return ImmutableList.of("c", "a", "b");
+  }
+
+  /**
+   * Returns the enumeration of the nested set {"b", "d", {"c", "a", "e"}} in
+   * the implementation's enumeration order.
+   *
+   * @see #testNesting()
+   */
+  protected abstract List<String> nestedResult();
+
+  /**
+   * Returns the enumeration of the nested set {"b", "d", "e", {"c", "a", "e"}} in
+   * the implementation's enumeration order.
+   *
+   * @see #testNestingNoDuplicates()
+   */
+  protected abstract List<String> nestedDuplicatesResult();
+
+  /**
+   * Returns the enumeration of nested set {"a", {"b", {"c"}}} in the
+   * implementation's enumeration order.
+   *
+   * @see #testChain()
+   */
+  protected abstract List<String> chainResult();
+
+  /**
+   * Returns the enumeration of the nested set {"a", {"b", D}, {"c", D}}, where
+   * D is {"d"}, in the implementation's enumeration order.
+   *
+   * @see #testDiamond()
+   */
+  protected abstract List<String> diamondResult();
+
+  /**
+   * Returns the enumeration of the nested set {"a", {"b", E, D}, {"c", D, E}}, where
+   * D is {"d"} and E is {"e"}, in the implementation's enumeration order.
+   *
+   * @see #testExtendedDiamond()
+   */
+  protected abstract List<String> extendedDiamondResult();
+
+  /**
+   * Returns the enumeration of the nested set {"a", {"b", E, D}, {"c", C2}}, where
+   * D is {"d"}, E is {"e"} and C2 is {"c2", D, E}, in the implementation's enumeration order.
+   *
+   * @see #testExtendedDiamondRightArm()
+   */
+  protected abstract List<String> extendedDiamondRightArmResult();
+
+  /**
+   * Returns the enumeration of the nested set {{"a", "b"}, {"b", "a"}}.
+   *
+   * @see #testOrderConflict()
+   * @see #testOrderConflictNested()
+   */
+  protected List<String> orderConflictResult() {
+    return ImmutableList.of("a", "b");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpanderTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpanderTest.java
new file mode 100644
index 0000000000..5d6988270a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpanderTest.java
@@ -0,0 +1,69 @@
+// 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 com.google.common.collect.ImmutableList;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.List;
+
+/**
+ * Tests for {@link LinkOrderExpander}.
+ */
+@RunWith(JUnit4.class)
+public class LinkOrderExpanderTest extends ExpanderTestBase {
+
+  @Override
+  protected Order expanderOrder() {
+    return Order.LINK_ORDER;
+  }
+
+  @Override
+  protected List<String> nestedResult() {
+    return ImmutableList.of("b", "d", "c", "a", "e");
+  }
+
+  @Override
+  protected List<String> nestedDuplicatesResult() {
+    return ImmutableList.of("b", "d", "c", "a", "e");
+  }
+
+  @Override
+  protected List<String> chainResult() {
+    return ImmutableList.of("a", "b", "c");
+  }
+
+  @Override
+  protected List<String> diamondResult() {
+    return ImmutableList.of("a", "b", "c", "d");
+  }
+
+  @Override
+  protected List<String> orderConflictResult() {
+    // Rightmost branch determines the order.
+    return ImmutableList.of("b", "a");
+  }
+
+  @Override
+  protected List<String> extendedDiamondResult() {
+    return ImmutableList.of("a", "b", "c", "e", "d");
+  }
+
+  @Override
+  protected List<String> extendedDiamondRightArmResult() {
+    return ImmutableList.of("a", "b", "c", "c2", "e", "d");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpanderTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpanderTest.java
new file mode 100644
index 0000000000..80faf7a392
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpanderTest.java
@@ -0,0 +1,70 @@
+// 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 com.google.common.collect.ImmutableList;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.List;
+
+/**
+ * Tests for {@link NaiveLinkOrderExpander}.
+ */
+@RunWith(JUnit4.class)
+public class NaiveLinkOrderExpanderTest extends ExpanderTestBase {
+
+  @Override
+  protected Order expanderOrder() {
+    return Order.NAIVE_LINK_ORDER;
+  }
+
+  @Override
+  protected List<String> nestedResult() {
+    return ImmutableList.of("b", "d", "c", "a", "e");
+  }
+
+  @Override
+  protected List<String> nestedDuplicatesResult() {
+    return ImmutableList.of("b", "d", "e", "c", "a");
+  }
+
+  @Override
+  protected List<String> chainResult() {
+    return ImmutableList.of("a", "b", "c");
+  }
+
+  @Override
+  protected List<String> diamondResult() {
+    // This case illustrates why this implementation is called "naive".
+    return ImmutableList.of("a", "b", "d", "c");
+  }
+
+  @Override
+  protected List<String> orderConflictResult() {
+    // Leftmost branch determines the order.
+    return ImmutableList.of("a", "b");
+  }
+
+  @Override
+  protected List<String> extendedDiamondResult() {
+    return ImmutableList.of("a", "b", "d", "e", "c");
+  }
+
+  @Override
+  protected List<String> extendedDiamondRightArmResult() {
+    return ImmutableList.of("a", "b", "d", "e", "c", "c2");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
new file mode 100644
index 0000000000..e5cfae33cf
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
@@ -0,0 +1,245 @@
+// 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 static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+import com.google.common.testing.EqualsTester;
+
+import junit.framework.TestCase;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.Arrays;
+
+/**
+ * Tests for {@link com.google.devtools.build.lib.collect.nestedset.NestedSet}.
+ */
+@RunWith(JUnit4.class)
+public class NestedSetImplTest extends TestCase {
+  @SafeVarargs
+  private static NestedSetBuilder<String> nestedSetBuilder(String... directMembers) {
+    NestedSetBuilder<String> builder = NestedSetBuilder.stableOrder();
+    builder.addAll(Lists.newArrayList(directMembers));
+    return builder;
+  }
+
+  @Test
+  public void simple() {
+    NestedSet<String> set = nestedSetBuilder("a").build();
+
+    assertTrue(Arrays.equals(new String[]{"a"}, set.directMembers()));
+    assertEquals(0, set.transitiveSets().length);
+    assertEquals(false, set.isEmpty());
+  }
+
+  @Test
+  public void flatToString() {
+    assertEquals("{}", nestedSetBuilder().build().toString());
+    assertEquals("{a}", nestedSetBuilder("a").build().toString());
+    assertEquals("{a, b}", nestedSetBuilder("a", "b").build().toString());
+  }
+
+  @Test
+  public void nestedToString() {
+    NestedSet<String> b = nestedSetBuilder("b").build();
+    NestedSet<String> c = nestedSetBuilder("c").build();
+
+    assertEquals("{a, {b}}",
+      nestedSetBuilder("a").addTransitive(b).build().toString());
+    assertEquals("{a, {b}, {c}}",
+      nestedSetBuilder("a").addTransitive(b).addTransitive(c).build().toString());
+
+    assertEquals("{b}", nestedSetBuilder().addTransitive(b).build().toString());
+  }
+
+  @Test
+  public void isEmpty() {
+    NestedSet<String> triviallyEmpty = nestedSetBuilder().build();
+    assertTrue(triviallyEmpty.isEmpty());
+
+    NestedSet<String> emptyLevel1 = nestedSetBuilder().addTransitive(triviallyEmpty).build();
+    assertTrue(emptyLevel1.isEmpty());
+
+    NestedSet<String> emptyLevel2 = nestedSetBuilder().addTransitive(emptyLevel1).build();
+    assertTrue(emptyLevel2.isEmpty());
+
+    NestedSet<String> triviallyNonEmpty = nestedSetBuilder("mango").build();
+    assertFalse(triviallyNonEmpty.isEmpty());
+
+    NestedSet<String> nonEmptyLevel1 = nestedSetBuilder().addTransitive(triviallyNonEmpty).build();
+    assertFalse(nonEmptyLevel1.isEmpty());
+
+    NestedSet<String> nonEmptyLevel2 = nestedSetBuilder().addTransitive(nonEmptyLevel1).build();
+    assertFalse(nonEmptyLevel2.isEmpty());
+  }
+
+  @Test
+  public void canIncludeAnyOrderInStableOrderAndViceVersa() {
+    NestedSetBuilder.stableOrder()
+        .addTransitive(NestedSetBuilder.compileOrder()
+            .addTransitive(NestedSetBuilder.stableOrder().build()).build())
+        .addTransitive(NestedSetBuilder.linkOrder()
+            .addTransitive(NestedSetBuilder.stableOrder().build()).build())
+        .addTransitive(NestedSetBuilder.naiveLinkOrder()
+            .addTransitive(NestedSetBuilder.stableOrder().build()).build()).build();
+    try {
+      NestedSetBuilder.compileOrder().addTransitive(NestedSetBuilder.linkOrder().build()).build();
+      fail("Shouldn't be able to include a non-stable order inside a different non-stable order!");
+    } catch (IllegalStateException e) {
+      // Expected.
+    }
+  }
+
+  /**
+   * A handy wrapper that allows us to use EqualsTester to test shallowEquals and shallowHashCode.
+   */
+  private static class SetWrapper<E> {
+    NestedSet<E> set;
+
+    SetWrapper(NestedSet<E> wrapped) {
+      set = wrapped;
+    }
+
+    @Override
+    public int hashCode() {
+      return set.shallowHashCode();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (!(o instanceof SetWrapper)) {
+        return false;
+      }
+      try {
+        @SuppressWarnings("unchecked")
+        SetWrapper<E> other = (SetWrapper<E>) o;
+        return set.shallowEquals(other.set);
+      } catch (ClassCastException e) {
+        return false;
+      }
+    }
+  }
+
+  @SafeVarargs
+  private static <E> SetWrapper<E> flat(E... directMembers) {
+    NestedSetBuilder<E> builder = NestedSetBuilder.stableOrder();
+    builder.addAll(Lists.newArrayList(directMembers));
+    return new SetWrapper<E>(builder.build());
+  }
+
+  // Same as flat(), but allows duplicate elements.
+  @SafeVarargs
+  private static <E> SetWrapper<E> flatWithDuplicates(E... directMembers) {
+    return new SetWrapper<E>(
+        NestedSetBuilder.wrap(Order.STABLE_ORDER, ImmutableList.copyOf(directMembers)));
+  }
+
+  @SafeVarargs
+  private static <E> SetWrapper<E> nest(SetWrapper<E>... nested) {
+    NestedSetBuilder<E> builder = NestedSetBuilder.stableOrder();
+    for (SetWrapper<E> wrap : nested) {
+      builder.addTransitive(wrap.set);
+    }
+    return new SetWrapper<E>(builder.build());
+  }
+
+  @SafeVarargs
+  // Restricted to <Integer> to avoid ambiguity with the other nest() function.
+  private static SetWrapper<Integer> nest(Integer elem, SetWrapper<Integer>... nested) {
+    NestedSetBuilder<Integer> builder = NestedSetBuilder.stableOrder();
+    builder.add(elem);
+    for (SetWrapper<Integer> wrap : nested) {
+      builder.addTransitive(wrap.set);
+    }
+    return new SetWrapper<Integer>(builder.build());
+  }
+
+  @Test
+  public void shallowEquality() {
+    // Used below to check that inner nested sets can be compared by reference equality.
+    SetWrapper<Integer> myRef = nest(nest(flat(7, 8)), flat(9));
+
+    // Each "equality group" contains elements that are equal to one another
+    // (according to equals() and hashCode()), yet distinct from all elements
+    // of all other equality groups.
+    new EqualsTester()
+      .addEqualityGroup(flat(),
+                        flat(),
+                        nest(flat()))  // Empty set elision.
+      .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().build())
+      .addEqualityGroup(flat(3),
+                        flat(3),
+                        flat(3, 3))  // Element de-duplication.
+      .addEqualityGroup(flatWithDuplicates(3, 3))
+      .addEqualityGroup(flat(4),
+                        nest(flat(4))) // Automatic elision of one-element nested sets.
+      .addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().add(4).build())
+      .addEqualityGroup(nestedSetBuilder("4").build())  // Like flat("4").
+      .addEqualityGroup(flat(3, 4),
+                        flat(3, 4))
+      // Shallow equality means that {{3},{5}} != {{3},{5}}.
+      .addEqualityGroup(nest(flat(3), flat(5)))
+      .addEqualityGroup(nest(flat(3), flat(5)))
+      .addEqualityGroup(nest(myRef),
+                        nest(myRef),
+                        nest(myRef, myRef))  // Set de-duplication.
+      .addEqualityGroup(nest(3, myRef))
+      .addEqualityGroup(nest(4, myRef))
+      .testEquals();
+
+    // Some things that are not tested by the above:
+    //  - ordering among direct members
+    //  - ordering among transitive sets
+  }
+
+  /** Checks that the builder always return a nested set with the correct order. */
+  @Test
+  public void correctOrder() {
+    for (Order order : Order.values()) {
+      for (int numDirects = 0; numDirects < 3; numDirects++) {
+        for (int numTransitives = 0; numTransitives < 3; numTransitives++) {
+          assertEquals(order, createNestedSet(order, numDirects, numTransitives, order).getOrder());
+          // We allow mixing orders if one of them is stable. This tests that the top level order is
+          // the correct one.
+          assertEquals(order,
+              createNestedSet(order, numDirects, numTransitives, Order.STABLE_ORDER).getOrder());
+        }
+      }
+    }
+  }
+
+  private NestedSet<Integer> createNestedSet(Order order, int numDirects, int numTransitives,
+      Order transitiveOrder) {
+    NestedSetBuilder<Integer> builder = new NestedSetBuilder<>(order);
+
+    for (int direct = 0; direct < numDirects; direct++) {
+      builder.add(direct);
+    }
+    for (int transitive = 0; transitive < numTransitives; transitive++) {
+      builder.addTransitive(new NestedSetBuilder<Integer>(transitiveOrder).add(transitive).build());
+    }
+    return builder.build();
+  }
+}
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);
+    }
+  }
+}