diff --git a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanFactory.java b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanFactory.java
index f8b96e8..d7de649 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanFactory.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.actions;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.CollectionUtils;
@@ -22,7 +21,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import java.util.Iterator;
 import javax.annotation.Nullable;
 
 /**
@@ -41,29 +39,6 @@
   }
 
   /**
-   * Creates a {@link MiddlemanType#AGGREGATING_MIDDLEMAN aggregating} middleman.
-   *
-   * @param owner the owner of the action that will be created; must not be null
-   * @param purpose the purpose for which this middleman is created. This should be a string which
-   *     is suitable for use as a filename. A single rule may have many middlemen with distinct
-   *     purposes.
-   * @param inputs the set of artifacts for which the created artifact is to be the middleman.
-   * @param middlemanDir the directory in which to place the middleman.
-   * @return null iff {@code inputs} is empty; the single element of {@code inputs} if there's only
-   *     one; a new aggregating middleman for the {@code inputs} otherwise
-   */
-  public Artifact createAggregatingMiddleman(
-      ActionOwner owner, String purpose, Iterable<Artifact> inputs, ArtifactRoot middlemanDir) {
-    if (hasExactlyOneInput(inputs)) { // Optimization: No middleman for just one input.
-      return Iterables.getOnlyElement(inputs);
-    }
-    Pair<Artifact, Action> result = createMiddleman(
-        owner, Label.print(owner.getLabel()), purpose, inputs, middlemanDir,
-        MiddlemanType.AGGREGATING_MIDDLEMAN);
-    return result == null ? null : result.getFirst();
-  }
-
-  /**
    * Returns <code>null</code> iff inputs is empty. Returns the sole element of inputs iff <code>
    * inputs.size()==1</code>. Otherwise, returns a middleman artifact and creates a middleman action
    * that generates that artifact.
@@ -81,12 +56,12 @@
   public Artifact createRunfilesMiddleman(
       ActionOwner owner,
       @Nullable Artifact owningArtifact,
-      Iterable<Artifact> inputs,
+      NestedSet<Artifact> inputs,
       ArtifactRoot middlemanDir,
       String tag) {
     Preconditions.checkArgument(middlemanDir.isMiddlemanRoot());
-    if (hasExactlyOneInput(inputs)) { // Optimization: No middleman for just one input.
-      return Iterables.getOnlyElement(inputs);
+    if (inputs.isSingleton()) { // Optimization: No middleman for just one input.
+      return inputs.getSingleton();
     }
     String middlemanPath = owningArtifact == null
        ? Label.print(owner.getLabel())
@@ -95,18 +70,6 @@
         MiddlemanType.RUNFILES_MIDDLEMAN).getFirst();
   }
 
-  private <T> boolean hasExactlyOneInput(Iterable<T> iterable) {
-    if (iterable instanceof NestedSet) {
-      return ((NestedSet) iterable).isSingleton();
-    }
-    Iterator<T> it = iterable.iterator();
-    if (!it.hasNext()) {
-      return false;
-    }
-    it.next();
-    return !it.hasNext();
-  }
-
   /**
    * Creates a {@link MiddlemanType#SCHEDULING_DEPENDENCY_MIDDLEMAN scheduling dependency}
    * middleman.
@@ -131,7 +94,7 @@
       Iterable<Artifact> inputs,
       ArtifactRoot middlemanDir) {
     Preconditions.checkArgument(inputs != null);
-    Preconditions.checkArgument(!Iterables.isEmpty(inputs));
+    Preconditions.checkArgument(!CollectionUtils.isEmpty(inputs));
     // We must always create this middleman even if there is only one input.
     return createMiddleman(
             owner,
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 38116fb..614cd11 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -1318,9 +1318,9 @@
   private Artifact transitiveInfoCollectionToArtifact(
       String attributeName, TransitiveInfoCollection target) {
     if (target != null) {
-      Iterable<Artifact> artifacts = target.getProvider(FileProvider.class).getFilesToBuild();
-      if (Iterables.size(artifacts) == 1) {
-        return Iterables.getOnlyElement(artifacts);
+      NestedSet<Artifact> artifacts = target.getProvider(FileProvider.class).getFilesToBuild();
+      if (artifacts.isSingleton()) {
+        return artifacts.getSingleton();
       } else {
         attributeError(attributeName, target.getLabel() + " expected a single artifact");
       }
@@ -1730,7 +1730,7 @@
     private boolean validateFilesetEntry(FilesetEntry filesetEntry, ConfiguredTargetAndData src) {
       NestedSet<Artifact> filesToBuild =
           src.getConfiguredTarget().getProvider(FileProvider.class).getFilesToBuild();
-      if (filesToBuild.isSingleton() && Iterables.getOnlyElement(filesToBuild).isFileset()) {
+      if (filesToBuild.isSingleton() && filesToBuild.getSingleton().isFileset()) {
         return true;
       }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
index fef0eca..a6d3b71 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.RunUnder;
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget.Mode;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.TargetUtils;
@@ -286,7 +287,7 @@
    * PruningManifest. This means the returned set may be an overapproximation of the actual set of
    * runfiles (see {@link Runfiles.PruningManifest}).
    */
-  public Iterable<Artifact> getRunfilesArtifacts() {
+  public NestedSet<Artifact> getRunfilesArtifacts() {
     return runfiles.getArtifacts();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/collect/CollectionUtils.java b/src/main/java/com/google/devtools/build/lib/collect/CollectionUtils.java
index 4a314fd..63d17fe 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/CollectionUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/CollectionUtils.java
@@ -210,7 +210,7 @@
   }
 
   /**
-   * A variant of {@link com.google.common.collect.Iterables.isEmpty} that avoids expanding nested
+   * A variant of {@link com.google.common.collect.Iterables#isEmpty} that avoids expanding nested
    * sets.
    */
   public static <T> boolean isEmpty(Iterable<T> iterable) {
diff --git a/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java b/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
index 496f971..237d2fd 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
@@ -17,7 +17,6 @@
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
@@ -70,10 +69,7 @@
     public Builder<T> add(Iterable<? extends T> iterable) {
       CollectionUtils.checkImmutable(iterable);
       // Avoid unnecessarily expanding a NestedSet.
-      boolean isEmpty =
-          iterable instanceof NestedSet
-              ? ((NestedSet<?>) iterable).isEmpty()
-              : Iterables.isEmpty(iterable);
+      boolean isEmpty = CollectionUtils.isEmpty(iterable);
       if (!isEmpty) {
         iterables.add(iterable);
       }
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index e21e477..1cc7840 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -271,6 +271,12 @@
     return !(children instanceof Object[] || children instanceof ListenableFuture);
   }
 
+  /** Returns the single element; only call this if {@link #isSingleton} returns true. */
+  public E getSingleton() {
+    Preconditions.checkState(isSingleton());
+    return (E) children;
+  }
+
   /**
    * Returns an immutable list of all unique elements of the this set, similar to {@link #toList},
    * but will propagate an {@code InterruptedException} if one is thrown.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index 4b2b8d0..14b348a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -935,7 +935,7 @@
     // Because rules referencing .dwp targets may be invoked with or without fission, we need
     // to support .dwp generation even when fission is disabled. Since no actual functionality
     // is expected then, an empty file is appropriate.
-    if (Iterables.isEmpty(dwoFiles)) {
+    if (dwoFiles.isEmpty()) {
       context.registerAction(FileWriteAction.create(context, dwpOutput, "", false));
       return;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
index d3f53af..439cf85 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
@@ -34,7 +34,6 @@
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.DedupingIterable;
-import com.google.devtools.build.lib.collect.ImmutableIterable;
 import com.google.devtools.build.lib.collect.IterablesChain;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
@@ -810,7 +809,7 @@
         IterablesChain.<LinkerInput>builder()
             .add(objectFileInputs)
             .add(linkstampObjectFileInputs)
-            .add(ImmutableIterable.from(uniqueLibraries))
+            .add(uniqueLibraries)
             .add(
                 // Adding toolchain libraries without whole archive no-matter-what. People don't
                 // want to include whole libstdc++ in their binary ever.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java b/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
index e662a4c..44ad18c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
@@ -40,7 +40,6 @@
 import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import java.util.Iterator;
 import java.util.List;
 
 /**
@@ -108,14 +107,7 @@
    * Returns the single Artifact from filesToBuild or {@code null} if there are multiple elements.
    */
   private Artifact getExecutable(NestedSet<Artifact> filesToBuild) {
-    Iterator<Artifact> it = filesToBuild.iterator();
-    if (it.hasNext()) {
-      Artifact out = it.next();
-      if (!it.hasNext()) {
-        return out;
-      }
-    }
-    return null;
+    return filesToBuild.isSingleton() ? filesToBuild.getSingleton() : null;
   }
 
   private PathFragment getFilegroupPath(RuleContext ruleContext) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
index 8977915..dacae1b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
@@ -242,7 +242,7 @@
 
     // Collect the action inputs for the runfiles collector here because we need to access the
     // analysis environment, and that may no longer be safe when the runfiles collector runs.
-    Iterable<Artifact> dynamicRuntimeActionInputs =
+    NestedSet<Artifact> dynamicRuntimeActionInputs =
         CppHelper.getDefaultCcToolchainDynamicRuntimeInputs(ruleContext);
 
     Iterables.addAll(
@@ -509,7 +509,7 @@
       JavaCompilationArtifacts javaArtifacts,
       NestedSet<Artifact> filesToBuild,
       Artifact launcher,
-      Iterable<Artifact> dynamicRuntimeActionInputs) {
+      NestedSet<Artifact> dynamicRuntimeActionInputs) {
     // Convert to iterable: filesToBuild has a different order.
     builder.addArtifacts((Iterable<Artifact>) filesToBuild);
     builder.addArtifacts(javaArtifacts.getRuntimeJars());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
index 857c9b2..1d9c882 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
@@ -413,7 +413,10 @@
     builder.setSourceJars(attributes.getSourceJars());
     builder.setClasspathEntries(attributes.getCompileTimeClassPath());
     builder.setBootclasspathEntries(
-        ImmutableList.copyOf(Iterables.concat(getBootclasspathOrDefault(), getExtdirInputs())));
+        NestedSetBuilder.<Artifact>stableOrder()
+            .addTransitive(getBootclasspathOrDefault())
+            .addTransitive(getExtdirInputs())
+            .build());
 
     // only run API-generating annotation processors during header compilation
     JavaPluginInfo plugins = attributes.plugins().apiGeneratingPlugins();
@@ -761,8 +764,8 @@
   }
 
   /** Returns the extdir artifacts. */
-  private final ImmutableList<Artifact> getExtdirInputs() {
-    return javaToolchain.getExtclasspath().toList();
+  private final NestedSet<Artifact> getExtdirInputs() {
+    return javaToolchain.getExtclasspath();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileActionBuilder.java
index 074c40d..de48a02 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileActionBuilder.java
@@ -157,7 +157,7 @@
   private NestedSet<Artifact> bootclasspathEntries =
       NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
   private ImmutableList<Artifact> sourcePathEntries = ImmutableList.of();
-  private ImmutableList<Artifact> extdirInputs = ImmutableList.of();
+  private NestedSet<Artifact> extdirInputs = NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
   private FilesToRunProvider javaBuilder;
   private NestedSet<Artifact> toolsJars = NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
   private PathFragment sourceGenDirectory;
@@ -240,7 +240,7 @@
         .addTransitive(javabaseInputs)
         .addTransitive(bootclasspathEntries)
         .addAll(sourcePathEntries)
-        .addAll(extdirInputs);
+        .addTransitive(extdirInputs);
     if (coverageArtifact != null) {
       mandatoryInputs.add(coverageArtifact);
     }
@@ -463,8 +463,8 @@
     return this;
   }
 
-  public JavaCompileActionBuilder setExtdirInputs(Iterable<Artifact> extdirEntries) {
-    this.extdirInputs = ImmutableList.copyOf(extdirEntries);
+  public JavaCompileActionBuilder setExtdirInputs(NestedSet<Artifact> extdirEntries) {
+    this.extdirInputs = extdirEntries;
     return this;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
index 88e424c..ac0c7a7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileActionBuilder.java
@@ -83,7 +83,8 @@
   private ImmutableSet<Artifact> sourceFiles = ImmutableSet.of();
   private ImmutableList<Artifact> sourceJars = ImmutableList.of();
   private NestedSet<Artifact> classpathEntries = NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
-  private ImmutableList<Artifact> bootclasspathEntries = ImmutableList.of();
+  private NestedSet<Artifact> bootclasspathEntries =
+      NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
   @Nullable private Label targetLabel;
   @Nullable private String injectingRuleKind;
   private StrictDepsMode strictJavaDeps = StrictDepsMode.OFF;
@@ -163,7 +164,7 @@
 
   /** Sets the compilation bootclasspath entries. */
   public JavaHeaderCompileActionBuilder setBootclasspathEntries(
-      ImmutableList<Artifact> bootclasspathEntries) {
+      NestedSet<Artifact> bootclasspathEntries) {
     checkNotNull(bootclasspathEntries, "bootclasspathEntries must not be null");
     this.bootclasspathEntries = bootclasspathEntries;
     return this;
@@ -269,7 +270,7 @@
     NestedSetBuilder<Artifact> mandatoryInputs =
         NestedSetBuilder.<Artifact>stableOrder()
             .addTransitive(additionalInputs)
-            .addAll(bootclasspathEntries)
+            .addTransitive(bootclasspathEntries)
             .addAll(sourceJars)
             .addAll(sourceFiles)
             .addTransitive(toolsJars);