Update from Google.

--
MOE_MIGRATED_REVID=85702957

10 files changed, 1787 insertions, 0 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/collect/CollectionUtilsTest.java b/src/test/java/com/google/devtools/build/lib/collect/CollectionUtilsTest.java
new file mode 100644
index 0000000000..2505501371
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/CollectionUtilsTest.java
@@ -0,0 +1,175 @@
+// 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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.EnumSet;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Tests for {@link CollectionUtils}.
+ */
+
+@RunWith(JUnit4.class)
+public class CollectionUtilsTest {
+
+  @Test
+  public void testDuplicatedElementsOf() {
+    assertDups(ImmutableList.<Integer>of(), ImmutableSet.<Integer>of());
+    assertDups(ImmutableList.of(0), ImmutableSet.<Integer>of());
+    assertDups(ImmutableList.of(0, 0, 0), ImmutableSet.of(0));
+    assertDups(ImmutableList.of(1, 2, 3, 1, 2, 3), ImmutableSet.of(1, 2, 3));
+    assertDups(ImmutableList.of(1, 2, 3, 1, 2, 3, 4), ImmutableSet.of(1, 2, 3));
+    assertDups(ImmutableList.of(1, 2, 3, 4), ImmutableSet.<Integer>of());
+  }
+
+  private static void assertDups(List<Integer> collection, Set<Integer> dups) {
+    assertEquals(dups, CollectionUtils.duplicatedElementsOf(collection));
+  }
+
+  @Test
+  public void testIsImmutable() throws Exception {
+    assertTrue(CollectionUtils.isImmutable(ImmutableList.of(1, 2, 3)));
+    assertTrue(CollectionUtils.isImmutable(ImmutableSet.of(1, 2, 3)));
+
+    NestedSet<Integer> ns = NestedSetBuilder.<Integer>compileOrder()
+        .add(1).add(2).add(3).build();
+    assertTrue(CollectionUtils.isImmutable(ns));
+
+    NestedSet<Integer> ns2 = NestedSetBuilder.<Integer>linkOrder().add(1).add(2).add(3).build();
+    assertTrue(CollectionUtils.isImmutable(ns2));
+
+    IterablesChain<Integer> chain = IterablesChain.<Integer>builder().addElement(1).build();
+
+    assertTrue(CollectionUtils.isImmutable(chain));
+
+    assertFalse(CollectionUtils.isImmutable(Lists.newArrayList()));
+    assertFalse(CollectionUtils.isImmutable(Lists.newLinkedList()));
+    assertFalse(CollectionUtils.isImmutable(Sets.newHashSet()));
+    assertFalse(CollectionUtils.isImmutable(Sets.newLinkedHashSet()));
+
+    // The result of Iterables.concat() actually is immutable, but we have no way of checking if
+    // a given Iterable comes from concat().
+    assertFalse(CollectionUtils.isImmutable(Iterables.concat(ns, ns2)));
+
+    // We can override the check by using the ImmutableIterable wrapper.
+    assertTrue(CollectionUtils.isImmutable(
+        ImmutableIterable.from(Iterables.concat(ns, ns2))));
+  }
+
+  @Test
+  public void testCheckImmutable() throws Exception {
+    CollectionUtils.checkImmutable(ImmutableList.of(1, 2, 3));
+    CollectionUtils.checkImmutable(ImmutableSet.of(1, 2, 3));
+
+    try {
+      CollectionUtils.checkImmutable(Lists.newArrayList(1, 2, 3));
+    } catch (IllegalStateException e) {
+      return;
+    }
+    fail();
+  }
+
+  @Test
+  public void testMakeImmutable() throws Exception {
+    Iterable<Integer> immutableList = ImmutableList.of(1, 2, 3);
+    assertSame(immutableList, CollectionUtils.makeImmutable(immutableList));
+
+    Iterable<Integer> mutableList = Lists.newArrayList(1, 2, 3);
+    Iterable<Integer> converted = CollectionUtils.makeImmutable(mutableList);
+    assertNotSame(mutableList, converted);
+    assertEquals(mutableList, ImmutableList.copyOf(converted));
+  }
+
+  private static enum Small { ALPHA, BRAVO }
+  private static enum Large {
+    L0, L1, L2, L3, L4, L5, L6, L7, L8, L9,
+    L10, L11, L12, L13, L14, L15, L16, L17, L18, L19,
+    L20, L21, L22, L23, L24, L25, L26, L27, L28, L29,
+    L30, L31,
+  }
+
+  private static enum TooLarge {
+    T0, T1, T2, T3, T4, T5, T6, T7, T8, T9,
+    T10, T11, T12, T13, T14, T15, T16, T17, T18, T19,
+    T20, T21, T22, T23, T24, T25, T26, T27, T28, T29,
+    T30, T31, T32,
+  }
+
+  private static enum Medium {
+    ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT,
+  }
+
+  private <T extends Enum<T>> void assertAllDifferent(Class<T> clazz) throws Exception {
+    Set<EnumSet<T>> allSets = new HashSet<>();
+
+    int maxBits = 1 << clazz.getEnumConstants().length;
+    for (int i = 0; i < maxBits; i++) {
+      EnumSet<T> set = CollectionUtils.fromBits(i, clazz);
+      int back = CollectionUtils.toBits(set);
+      assertEquals(back, i);  // Assert that a roundtrip is idempotent
+      allSets.add(set);
+    }
+
+    assertEquals(maxBits, allSets.size());  // Assert that every decoded value is different
+  }
+
+  @Test
+  public void testEnumBitfields() throws Exception {
+    assertEquals(0, CollectionUtils.<Small>toBits());
+    assertEquals(EnumSet.noneOf(Small.class), CollectionUtils.fromBits(0, Small.class));
+    assertEquals(3, CollectionUtils.toBits(Small.ALPHA, Small.BRAVO));
+    assertEquals(10, CollectionUtils.toBits(Medium.TWO, Medium.FOUR));
+    assertEquals(EnumSet.of(Medium.SEVEN, Medium.EIGHT),
+        CollectionUtils.fromBits(192, Medium.class));
+
+    assertAllDifferent(Small.class);
+    assertAllDifferent(Medium.class);
+    assertAllDifferent(Large.class);
+
+    try {
+      CollectionUtils.toBits(TooLarge.T32);
+      fail();
+    } catch (IllegalArgumentException e) {
+      // good
+    }
+
+    try {
+      CollectionUtils.fromBits(0, TooLarge.class);
+      fail();
+    } catch (IllegalArgumentException e) {
+      // good
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyListMultimapTest.java b/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyListMultimapTest.java
new file mode 100644
index 0000000000..1249f6db14
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyListMultimapTest.java
@@ -0,0 +1,352 @@
+// 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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.HashMultiset;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.LinkedListMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.testing.google.UnmodifiableCollectionTests;
+import com.google.common.testing.EqualsTester;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.AbstractMap.SimpleImmutableEntry;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A test for {@link ImmutableSortedKeyListMultimap}. Started out as a copy of
+ * ImmutableListMultimapTest.
+ */
+@RunWith(JUnit4.class)
+public class ImmutableSortedKeyListMultimapTest {
+
+  @Test
+  public void builderPutAllIterable() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", Arrays.asList(1, 2, 3));
+    builder.putAll("bar", Arrays.asList(4, 5));
+    builder.putAll("foo", Arrays.asList(6, 7));
+    Multimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 3, 6, 7), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5), multimap.get("bar"));
+    assertEquals(7, multimap.size());
+  }
+
+  @Test
+  public void builderPutAllVarargs() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", 1, 2, 3);
+    builder.putAll("bar", 4, 5);
+    builder.putAll("foo", 6, 7);
+    Multimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 3, 6, 7), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5), multimap.get("bar"));
+    assertEquals(7, multimap.size());
+  }
+
+  @Test
+  public void builderPutAllMultimap() {
+    Multimap<String, Integer> toPut = LinkedListMultimap.create();
+    toPut.put("foo", 1);
+    toPut.put("bar", 4);
+    toPut.put("foo", 2);
+    toPut.put("foo", 3);
+    Multimap<String, Integer> moreToPut = LinkedListMultimap.create();
+    moreToPut.put("foo", 6);
+    moreToPut.put("bar", 5);
+    moreToPut.put("foo", 7);
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll(toPut);
+    builder.putAll(moreToPut);
+    Multimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 3, 6, 7), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5), multimap.get("bar"));
+    assertEquals(7, multimap.size());
+  }
+
+  @Test
+  public void builderPutAllWithDuplicates() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", 1, 2, 3);
+    builder.putAll("bar", 4, 5);
+    builder.putAll("foo", 1, 6, 7);
+    ImmutableSortedKeyListMultimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 3, 1, 6, 7), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5), multimap.get("bar"));
+    assertEquals(8, multimap.size());
+  }
+
+  @Test
+  public void builderPutWithDuplicates() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", 1, 2, 3);
+    builder.putAll("bar", 4, 5);
+    builder.put("foo", 1);
+    ImmutableSortedKeyListMultimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 3, 1), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5), multimap.get("bar"));
+    assertEquals(6, multimap.size());
+  }
+
+  @Test
+  public void builderPutAllMultimapWithDuplicates() {
+    Multimap<String, Integer> toPut = LinkedListMultimap.create();
+    toPut.put("foo", 1);
+    toPut.put("bar", 4);
+    toPut.put("foo", 2);
+    toPut.put("foo", 1);
+    toPut.put("bar", 5);
+    Multimap<String, Integer> moreToPut = LinkedListMultimap.create();
+    moreToPut.put("foo", 6);
+    moreToPut.put("bar", 4);
+    moreToPut.put("foo", 7);
+    moreToPut.put("foo", 2);
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll(toPut);
+    builder.putAll(moreToPut);
+    Multimap<String, Integer> multimap = builder.build();
+    assertEquals(Arrays.asList(1, 2, 1, 6, 7, 2), multimap.get("foo"));
+    assertEquals(Arrays.asList(4, 5, 4), multimap.get("bar"));
+    assertEquals(9, multimap.size());
+  }
+
+  @Test
+  public void builderPutNullKey() {
+    Multimap<String, Integer> toPut = LinkedListMultimap.create();
+    toPut.put("foo", null);
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    try {
+      builder.put(null, 1);
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll(null, Arrays.asList(1, 2, 3));
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll(null, 1, 2, 3);
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll(toPut);
+      fail();
+    } catch (NullPointerException expected) {}
+  }
+
+  @Test
+  public void builderPutNullValue() {
+    Multimap<String, Integer> toPut = LinkedListMultimap.create();
+    toPut.put(null, 1);
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    try {
+      builder.put("foo", null);
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll("foo", Arrays.asList(1, null, 3));
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll("foo", 1, null, 3);
+      fail();
+    } catch (NullPointerException expected) {}
+    try {
+      builder.putAll(toPut);
+      fail();
+    } catch (NullPointerException expected) {}
+  }
+
+  @Test
+  public void copyOf() {
+    ArrayListMultimap<String, Integer> input = ArrayListMultimap.create();
+    input.put("foo", 1);
+    input.put("bar", 2);
+    input.put("foo", 3);
+    Multimap<String, Integer> multimap = ImmutableSortedKeyListMultimap.copyOf(input);
+    assertEquals(multimap, input);
+    assertEquals(input, multimap);
+  }
+
+  @Test
+  public void copyOfWithDuplicates() {
+    ArrayListMultimap<String, Integer> input = ArrayListMultimap.create();
+    input.put("foo", 1);
+    input.put("bar", 2);
+    input.put("foo", 3);
+    input.put("foo", 1);
+    Multimap<String, Integer> multimap = ImmutableSortedKeyListMultimap.copyOf(input);
+    assertEquals(multimap, input);
+    assertEquals(input, multimap);
+  }
+
+  @Test
+  public void copyOfEmpty() {
+    ArrayListMultimap<String, Integer> input = ArrayListMultimap.create();
+    Multimap<String, Integer> multimap = ImmutableSortedKeyListMultimap.copyOf(input);
+    assertEquals(multimap, input);
+    assertEquals(input, multimap);
+  }
+
+  @Test
+  public void copyOfImmutableListMultimap() {
+    Multimap<String, Integer> multimap = createMultimap();
+    assertSame(multimap, ImmutableSortedKeyListMultimap.copyOf(multimap));
+  }
+
+  @Test
+  public void copyOfNullKey() {
+    ArrayListMultimap<String, Integer> input = ArrayListMultimap.create();
+    input.put(null, 1);
+    try {
+      ImmutableSortedKeyListMultimap.copyOf(input);
+      fail();
+    } catch (NullPointerException expected) {}
+  }
+
+  @Test
+  public void copyOfNullValue() {
+    ArrayListMultimap<String, Integer> input = ArrayListMultimap.create();
+    input.putAll("foo", Arrays.asList(1, null, 3));
+    try {
+      ImmutableSortedKeyListMultimap.copyOf(input);
+      fail();
+    } catch (NullPointerException expected) {}
+  }
+
+  @Test
+  public void emptyMultimapReads() {
+    Multimap<String, Integer> multimap = ImmutableSortedKeyListMultimap.of();
+    assertFalse(multimap.containsKey("foo"));
+    assertFalse(multimap.containsValue(1));
+    assertFalse(multimap.containsEntry("foo", 1));
+    assertTrue(multimap.entries().isEmpty());
+    assertTrue(multimap.equals(ArrayListMultimap.create()));
+    assertEquals(Collections.emptyList(), multimap.get("foo"));
+    assertEquals(0, multimap.hashCode());
+    assertTrue(multimap.isEmpty());
+    assertEquals(HashMultiset.create(), multimap.keys());
+    assertEquals(Collections.emptySet(), multimap.keySet());
+    assertEquals(0, multimap.size());
+    assertTrue(multimap.values().isEmpty());
+    assertEquals("{}", multimap.toString());
+  }
+
+  @Test
+  public void emptyMultimapWrites() {
+    Multimap<String, Integer> multimap = ImmutableSortedKeyListMultimap.of();
+    UnmodifiableCollectionTests.assertMultimapIsUnmodifiable(
+        multimap, "foo", 1);
+  }
+
+  private Multimap<String, Integer> createMultimap() {
+    return ImmutableSortedKeyListMultimap.<String, Integer>builder()
+        .put("foo", 1).put("bar", 2).put("foo", 3).build();
+  }
+
+  @Test
+  public void multimapReads() {
+    Multimap<String, Integer> multimap = createMultimap();
+    assertTrue(multimap.containsKey("foo"));
+    assertFalse(multimap.containsKey("cat"));
+    assertTrue(multimap.containsValue(1));
+    assertFalse(multimap.containsValue(5));
+    assertTrue(multimap.containsEntry("foo", 1));
+    assertFalse(multimap.containsEntry("cat", 1));
+    assertFalse(multimap.containsEntry("foo", 5));
+    assertFalse(multimap.entries().isEmpty());
+    assertEquals(3, multimap.size());
+    assertFalse(multimap.isEmpty());
+    assertEquals("{bar=[2], foo=[1, 3]}", multimap.toString());
+  }
+
+  @Test
+  public void multimapWrites() {
+    Multimap<String, Integer> multimap = createMultimap();
+    UnmodifiableCollectionTests.assertMultimapIsUnmodifiable(
+        multimap, "bar", 2);
+  }
+
+  @Test
+  public void multimapEquals() {
+    Multimap<String, Integer> multimap = createMultimap();
+    Multimap<String, Integer> arrayListMultimap
+        = ArrayListMultimap.create();
+    arrayListMultimap.putAll("foo", Arrays.asList(1, 3));
+    arrayListMultimap.put("bar", 2);
+
+    new EqualsTester()
+        .addEqualityGroup(multimap, createMultimap(), arrayListMultimap,
+            ImmutableSortedKeyListMultimap.<String, Integer>builder()
+                .put("bar", 2).put("foo", 1).put("foo", 3).build())
+        .addEqualityGroup(ImmutableSortedKeyListMultimap.<String, Integer>builder()
+            .put("bar", 2).put("foo", 3).put("foo", 1).build())
+        .addEqualityGroup(ImmutableSortedKeyListMultimap.<String, Integer>builder()
+            .put("foo", 2).put("foo", 3).put("foo", 1).build())
+        .addEqualityGroup(ImmutableSortedKeyListMultimap.<String, Integer>builder()
+            .put("bar", 2).put("foo", 3).build())
+        .testEquals();
+  }
+
+  @Test
+  public void asMap() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", Arrays.asList(1, 2, 3));
+    builder.putAll("bar", Arrays.asList(4, 5));
+    Map<String, Collection<Integer>> map = builder.build().asMap();
+    assertEquals(Arrays.asList(1, 2, 3), map.get("foo"));
+    assertEquals(Arrays.asList(4, 5), map.get("bar"));
+    assertEquals(2, map.size());
+    assertTrue(map.containsKey("foo"));
+    assertTrue(map.containsKey("bar"));
+    assertFalse(map.containsKey("notfoo"));
+  }
+
+  @Test
+  public void asMapEntries() {
+    ImmutableSortedKeyListMultimap.Builder<String, Integer> builder
+        = ImmutableSortedKeyListMultimap.builder();
+    builder.putAll("foo", Arrays.asList(1, 2, 3));
+    builder.putAll("bar", Arrays.asList(4, 5));
+    Set<Map.Entry<String, Collection<Integer>>> set = builder.build().asMap().entrySet();
+    Set<Map.Entry<String, Collection<Integer>>> other =
+        ImmutableSet.<Map.Entry<String, Collection<Integer>>>builder()
+        .add(new SimpleImmutableEntry<String, Collection<Integer>>("foo", Arrays.asList(1, 2, 3)))
+        .add(new SimpleImmutableEntry<String, Collection<Integer>>("bar", Arrays.asList(4, 5)))
+        .build();
+    assertEquals(other, set);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java b/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java
new file mode 100644
index 0000000000..c712695308
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java
@@ -0,0 +1,288 @@
+// 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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.Maps;
+import com.google.common.testing.NullPointerTester;
+import com.google.devtools.build.lib.collect.ImmutableSortedKeyMap.Builder;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.io.Serializable;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+
+/**
+ * A test for {@link ImmutableSortedKeyListMultimap}. Started out as a blatant copy of
+ * ImmutableListMapTest.
+ */
+@RunWith(JUnit4.class)
+public class ImmutableSortedKeyMapTest {
+
+  @Test
+  public void emptyBuilder() {
+    ImmutableSortedKeyMap<String, Integer> map
+        = ImmutableSortedKeyMap.<String, Integer>builder().build();
+    assertEquals(Collections.<String, Integer>emptyMap(), map);
+  }
+
+  @Test
+  public void singletonBuilder() {
+    ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder()
+        .put("one", 1)
+        .build();
+    assertMapEquals(map, "one", 1);
+  }
+
+  @Test
+  public void builder() {
+    ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder()
+        .put("one", 1)
+        .put("two", 2)
+        .put("three", 3)
+        .put("four", 4)
+        .put("five", 5)
+        .build();
+    assertMapEquals(map,
+        "five", 5, "four", 4, "one", 1, "three", 3, "two", 2);
+  }
+
+  @Test
+  public void builderPutAllWithEmptyMap() {
+    ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder()
+        .putAll(Collections.<String, Integer>emptyMap())
+        .build();
+    assertEquals(Collections.<String, Integer>emptyMap(), map);
+  }
+
+  @Test
+  public void builderPutAll() {
+    Map<String, Integer> toPut = new LinkedHashMap<>();
+    toPut.put("one", 1);
+    toPut.put("two", 2);
+    toPut.put("three", 3);
+    Map<String, Integer> moreToPut = new LinkedHashMap<>();
+    moreToPut.put("four", 4);
+    moreToPut.put("five", 5);
+
+    ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder()
+        .putAll(toPut)
+        .putAll(moreToPut)
+        .build();
+    assertMapEquals(map,
+        "five", 5, "four", 4, "one", 1, "three", 3, "two", 2);
+  }
+
+  @Test
+  public void builderReuse() {
+    ImmutableSortedKeyMap.Builder<String, Integer> builder =
+        ImmutableSortedKeyMap.<String, Integer>builder();
+    ImmutableSortedKeyMap<String, Integer> mapOne = builder
+        .put("one", 1)
+        .put("two", 2)
+        .build();
+    ImmutableSortedKeyMap<String, Integer> mapTwo = builder
+        .put("three", 3)
+        .put("four", 4)
+        .build();
+
+    assertMapEquals(mapOne, "one", 1, "two", 2);
+    assertMapEquals(mapTwo, "four", 4, "one", 1, "three", 3, "two", 2);
+  }
+
+  @Test
+  public void builderPutNullKey() {
+    Builder<String, Integer> builder = new Builder<>();
+    try {
+      builder.put(null, 1);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void builderPutNullValue() {
+    Builder<String, Integer> builder = new Builder<>();
+    try {
+      builder.put("one", null);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void builderPutNullKeyViaPutAll() {
+    Builder<String, Integer> builder = new Builder<>();
+    try {
+      builder.putAll(Collections.<String, Integer>singletonMap(null, 1));
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void builderPutNullValueViaPutAll() {
+    Builder<String, Integer> builder = new Builder<>();
+    try {
+      builder.putAll(Collections.<String, Integer>singletonMap("one", null));
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void of() {
+    assertMapEquals(
+        ImmutableSortedKeyMap.of("one", 1),
+        "one", 1);
+    assertMapEquals(
+        ImmutableSortedKeyMap.of("one", 1, "two", 2),
+        "one", 1, "two", 2);
+  }
+
+  @Test
+  public void ofNullKey() {
+    try {
+      ImmutableSortedKeyMap.of((String) null, 1);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+
+    try {
+      ImmutableSortedKeyMap.of("one", 1, null, 2);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void ofNullValue() {
+    try {
+      ImmutableSortedKeyMap.of("one", null);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+
+    try {
+      ImmutableSortedKeyMap.of("one", 1, "two", null);
+      fail();
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void copyOfEmptyMap() {
+    ImmutableSortedKeyMap<String, Integer> copy
+        = ImmutableSortedKeyMap.copyOf(Collections.<String, Integer>emptyMap());
+    assertEquals(Collections.<String, Integer>emptyMap(), copy);
+    assertSame(copy, ImmutableSortedKeyMap.copyOf(copy));
+  }
+
+  @Test
+  public void copyOfSingletonMap() {
+    ImmutableSortedKeyMap<String, Integer> copy
+        = ImmutableSortedKeyMap.copyOf(Collections.singletonMap("one", 1));
+    assertMapEquals(copy, "one", 1);
+    assertSame(copy, ImmutableSortedKeyMap.copyOf(copy));
+  }
+
+  @Test
+  public void copyOf() {
+    Map<String, Integer> original = new LinkedHashMap<>();
+    original.put("one", 1);
+    original.put("two", 2);
+    original.put("three", 3);
+
+    ImmutableSortedKeyMap<String, Integer> copy = ImmutableSortedKeyMap.copyOf(original);
+    assertMapEquals(copy, "one", 1, "three", 3, "two", 2);
+    assertSame(copy, ImmutableSortedKeyMap.copyOf(copy));
+  }
+
+  @Test
+  public void nullGet() {
+    ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.of("one", 1);
+    assertNull(map.get(null));
+  }
+
+  @Test
+  public void nullPointers() {
+    NullPointerTester tester = new NullPointerTester();
+    tester.testAllPublicStaticMethods(ImmutableSortedKeyMap.class);
+    tester.testAllPublicInstanceMethods(
+        new ImmutableSortedKeyMap.Builder<String, Object>());
+    tester.testAllPublicInstanceMethods(ImmutableSortedKeyMap.<String, Integer>of());
+    tester.testAllPublicInstanceMethods(ImmutableSortedKeyMap.of("one", 1));
+    tester.testAllPublicInstanceMethods(
+        ImmutableSortedKeyMap.of("one", 1, "two", 2));
+  }
+
+  private static <K, V> void assertMapEquals(Map<K, V> map,
+      Object... alternatingKeysAndValues) {
+    assertEquals(map.size(), alternatingKeysAndValues.length / 2);
+    int i = 0;
+    for (Entry<K, V> entry : map.entrySet()) {
+      assertEquals(alternatingKeysAndValues[i++], entry.getKey());
+      assertEquals(alternatingKeysAndValues[i++], entry.getValue());
+    }
+  }
+
+  private static class IntHolder implements Serializable {
+    public int value;
+
+    public IntHolder(int value) {
+      this.value = value;
+    }
+
+    @Override public boolean equals(Object o) {
+      return (o instanceof IntHolder) && ((IntHolder) o).value == value;
+    }
+
+    @Override public int hashCode() {
+      return value;
+    }
+
+    private static final long serialVersionUID = 5;
+  }
+
+  @Test
+  public void mutableValues() {
+    IntHolder holderA = new IntHolder(1);
+    IntHolder holderB = new IntHolder(2);
+    Map<String, IntHolder> map = ImmutableSortedKeyMap.of("a", holderA, "b", holderB);
+    holderA.value = 3;
+    assertTrue(map.entrySet().contains(
+        Maps.immutableEntry("a", new IntHolder(3))));
+    Map<String, Integer> intMap = ImmutableSortedKeyMap.of("a", 3, "b", 2);
+    assertEquals(intMap.hashCode(), map.entrySet().hashCode());
+    assertEquals(intMap.hashCode(), map.hashCode());
+  }
+
+  @Test
+  public void toStringTest() {
+    Map<String, Integer> map = ImmutableSortedKeyMap.of("a", 1, "b", 2);
+    assertEquals("{a=1, b=2}", map.toString());
+    map = ImmutableSortedKeyMap.of();
+    assertEquals("{}", map.toString());
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/IterablesChainTest.java b/src/test/java/com/google/devtools/build/lib/collect/IterablesChainTest.java
new file mode 100644
index 0000000000..734d801b98
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/IterablesChainTest.java
@@ -0,0 +1,60 @@
+// 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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.collect.ImmutableList;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.Arrays;
+
+/**
+ * A test for {@link IterablesChain}.
+ */
+@RunWith(JUnit4.class)
+public class IterablesChainTest {
+
+  @Test
+  public void addElement() {
+    IterablesChain.Builder<String> builder = IterablesChain.builder();
+    builder.addElement("a");
+    builder.addElement("b");
+    assertEquals(Arrays.asList("a", "b"), ImmutableList.copyOf(builder.build()));
+  }
+
+  @Test
+  public void add() {
+    IterablesChain.Builder<String> builder = IterablesChain.builder();
+    builder.add(ImmutableList.of("a", "b"));
+    assertEquals(Arrays.asList("a", "b"), ImmutableList.copyOf(builder.build()));
+  }
+
+  @Test
+  public void isEmpty() {
+    IterablesChain.Builder<String> builder = IterablesChain.builder();
+    assertTrue(builder.isEmpty());
+    builder.addElement("a");
+    assertFalse(builder.isEmpty());
+    builder = IterablesChain.builder();
+    assertTrue(builder.isEmpty());
+    builder.add(ImmutableList.of("a"));
+    assertFalse(builder.isEmpty());
+  }
+}
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);
+    }
+  }
+}