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 a6296bd..72577cc 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
@@ -122,7 +122,7 @@
       NestedSet<Artifact> inputs,
       ArtifactRoot middlemanDir,
       MiddlemanType middlemanType) {
-    if (inputs == null || CollectionUtils.isEmpty(inputs)) {
+    if (inputs == null || inputs.isEmpty()) {
       return null;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PrerequisiteArtifacts.java b/src/main/java/com/google/devtools/build/lib/analysis/PrerequisiteArtifacts.java
index 9d62428..9289a18 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PrerequisiteArtifacts.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PrerequisiteArtifacts.java
@@ -17,7 +17,6 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -59,7 +58,7 @@
     }
     Set<Artifact> result = new LinkedHashSet<>();
     for (FileProvider target : prerequisites) {
-      Iterables.addAll(result, target.getFilesToBuild());
+      result.addAll(target.getFilesToBuild().toList());
     }
     return new PrerequisiteArtifacts(ruleContext, attributeName, ImmutableList.copyOf(result));
   }
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 0810a03..a2b2ca0 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
@@ -1548,7 +1548,7 @@
   public static boolean isVisible(Label label, TransitiveInfoCollection prerequisite) {
     // Check visibility attribute
     for (PackageGroupContents specification :
-        prerequisite.getProvider(VisibilityProvider.class).getVisibility()) {
+        prerequisite.getProvider(VisibilityProvider.class).getVisibility().toList()) {
       if (specification.containsPackage(label.getPackageIdentifier())) {
         return true;
       }
@@ -2018,15 +2018,15 @@
       // If we performed this check when allowedFileTypes == NO_FILE this would
       // always throw an error in those cases
       if (allowedFileTypes != FileTypeSet.NO_FILE) {
-        Iterable<Artifact> artifacts =
+        NestedSet<Artifact> artifacts =
             prerequisite.getConfiguredTarget().getProvider(FileProvider.class).getFilesToBuild();
-        if (attribute.isSingleArtifact() && Iterables.size(artifacts) != 1) {
+        if (attribute.isSingleArtifact() && !artifacts.isSingleton()) {
           attributeError(
               attribute.getName(),
               "'" + prerequisite.getTarget().getLabel() + "' must produce a single file");
           return;
         }
-        for (Artifact sourceArtifact : artifacts) {
+        for (Artifact sourceArtifact : artifacts.toList()) {
           if (allowedFileTypes.apply(sourceArtifact.getFilename())) {
             return;
           }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
index b2af011..b8cea4a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
@@ -649,9 +649,9 @@
     NestedSetBuilder<Artifact> allArtifacts = NestedSetBuilder.stableOrder();
     allArtifacts
         .addTransitive(unconditionalArtifacts)
-        .addAll(Iterables.transform(symlinks, TO_ARTIFACT))
-        .addAll(Iterables.transform(rootSymlinks, TO_ARTIFACT));
-    for (PruningManifest manifest : getPruningManifests()) {
+        .addAll(Iterables.transform(symlinks.toList(), TO_ARTIFACT))
+        .addAll(Iterables.transform(rootSymlinks.toList(), TO_ARTIFACT));
+    for (PruningManifest manifest : getPruningManifests().toList()) {
       allArtifacts.addTransitive(manifest.getCandidateRunfiles());
     }
     return allArtifacts.build();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
index a5a81f4..4d9f809 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
@@ -155,7 +155,7 @@
    */
   public static NestedSet<Artifact> getDependencies(Runfiles runfiles) {
     NestedSetBuilder<Artifact> builder = NestedSetBuilder.stableOrder();
-    for (Runfiles.PruningManifest manifest : runfiles.getPruningManifests()) {
+    for (Runfiles.PruningManifest manifest : runfiles.getPruningManifests().toList()) {
       builder.add(manifest.getManifestFile());
     }
     return builder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/LazyWritePathsFileAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/LazyWritePathsFileAction.java
index 3387e81..0470b5c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/LazyWritePathsFileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/LazyWritePathsFileAction.java
@@ -76,7 +76,7 @@
 
   private String getContents() {
     StringBuilder stringBuilder = new StringBuilder();
-    for (Artifact file : files) {
+    for (Artifact file : files.toList()) {
       if (file.isSourceArtifact() || includeDerivedArtifacts) {
         stringBuilder.append(file.getRootRelativePathString());
         stringBuilder.append("\n");
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java b/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
index ed1fd24..346308c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
@@ -643,7 +643,7 @@
     // words, the removed environment is no good, but some subset of it may be.
     for (EnvironmentWithGroup depEnv :
         depEnvironments.getRefinedEnvironments().getGroupedEnvironments()) {
-      for (Label fulfiller : depEnv.group().getFulfillers(depEnv.environment())) {
+      for (Label fulfiller : depEnv.group().getFulfillers(depEnv.environment()).toList()) {
         if (prunedEnvironmentsFromThisDep.contains(fulfiller)) {
           refinedEnvironmentsSoFar.add(depEnv);
         }
@@ -792,7 +792,7 @@
         // If the actual environments include members from the expected environment's group, we
         // need to either find the environment itself or another one that transitively fulfills it.
         if (actualEnvironmentLabels.contains(environment)
-            || intersect(actualEnvironmentLabels, group.getFulfillers(environment))) {
+            || intersect(actualEnvironmentLabels, group.getFulfillers(environment).toList())) {
           isSatisfied = true;
         }
       } else {
@@ -800,7 +800,7 @@
         // the group's defaults are implicitly included. So we need to check those defaults for
         // either the expected environment or another environment that transitively fulfills it.
         if (group.isDefault(environment)
-            || intersect(group.getFulfillers(environment), group.getDefaults())) {
+            || intersect(group.getFulfillers(environment).toList(), group.getDefaults())) {
           isSatisfied = true;
         }
       }
@@ -816,7 +816,8 @@
       if (!expectedEnvironments.getGroups().contains(group)) {
         for (Label expectedDefault : group.getDefaults()) {
           if (!actualEnvironmentLabels.contains(expectedDefault)
-              && !intersect(actualEnvironmentLabels, group.getFulfillers(expectedDefault))) {
+              && !intersect(
+                  actualEnvironmentLabels, group.getFulfillers(expectedDefault).toList())) {
             missingEnvironments.add(expectedDefault);
           }
         }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkActionFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkActionFactory.java
index ee0309c..4c72629 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkActionFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkActionFactory.java
@@ -502,7 +502,7 @@
     } else {
       NestedSet<Artifact> inputSet = ((Depset) inputs).getSetFromParam(Artifact.class, "inputs");
       builder.addTransitiveInputs(inputSet);
-      inputArtifacts = inputSet;
+      inputArtifacts = inputSet.toList();
     }
 
     List<Artifact> outputArtifacts = outputs.getContents(Artifact.class, "outputs");
@@ -536,7 +536,7 @@
       if (toolsUnchecked instanceof Sequence) {
         toolsIterable = ((Sequence<?>) toolsUnchecked).getContents(Object.class, "tools");
       } else {
-        toolsIterable = ((Depset) toolsUnchecked).getSet();
+        toolsIterable = ((Depset) toolsUnchecked).getSet().toList();
       }
       for (Object toolUnchecked : toolsIterable) {
         if (toolUnchecked instanceof Artifact) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkCommandLine.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkCommandLine.java
index 9872741..ffc11be 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkCommandLine.java
@@ -28,6 +28,6 @@
     NestedSet<Artifact> artifacts = files.getSetFromParam(Artifact.class, "files");
     // TODO(bazel-team): This method should be deprecated and strongly discouraged, as it
     // flattens a depset during analysis.
-    return Artifact.joinExecPaths(separator, artifacts);
+    return Artifact.joinExecPaths(separator, artifacts.toList());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
index 8d9ba30..1caa9a1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
@@ -1066,7 +1066,7 @@
     // TODO(lberki): This flattens a NestedSet.
     // However, we can't turn this into a Depset because it's an incompatible change to
     // Skylark.
-    Iterables.addAll(inputs, helper.getResolvedTools());
+    inputs.addAll(helper.getResolvedTools().toList());
 
     ImmutableMap<String, String> executionRequirements =
         ImmutableMap.copyOf(
@@ -1174,7 +1174,7 @@
     for (TransitiveInfoCollection current : knownLabels) {
       builder.put(
           AliasProvider.getDependencyLabel(current),
-          ImmutableList.copyOf(current.getProvider(FileProvider.class).getFilesToBuild()));
+          current.getProvider(FileProvider.class).getFilesToBuild().toList());
     }
 
     return builder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java b/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
index 0c7af11..95244b4 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/BaselineCoverageAction.java
@@ -66,7 +66,7 @@
 
   private Iterable<String> getInstrumentedFilePathStrings() {
     List<String> result = new ArrayList<>();
-    for (Artifact instrumentedFile : instrumentedFiles) {
+    for (Artifact instrumentedFile : instrumentedFiles.toList()) {
       result.add(instrumentedFile.getExecPathString());
     }
     return result;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
index 69ab77f..b242c16 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFileManifestAction.java
@@ -70,7 +70,7 @@
       public void writeOutputFile(OutputStream out) throws IOException {
         // Sort the exec paths before writing them out.
         String[] fileNames =
-            Iterables.toArray(Iterables.transform(files, TO_EXEC_PATH), String.class);
+            Iterables.toArray(Iterables.transform(files.toList(), TO_EXEC_PATH), String.class);
         Arrays.sort(fileNames);
         try (Writer writer = new OutputStreamWriter(out, ISO_8859_1)) {
           for (String name : fileNames) {
@@ -86,7 +86,7 @@
   protected void computeKey(ActionKeyContext actionKeyContext, Fingerprint fp) {
     fp.addString(GUID);
     // Not sorting here is probably cheaper, though it might lead to unnecessary re-execution.
-    fp.addStrings(Iterables.transform(files, TO_EXEC_PATH));
+    fp.addStrings(Iterables.transform(files.toList(), TO_EXEC_PATH));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesCollector.java b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesCollector.java
index 4bd6348..98348c1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesCollector.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesCollector.java
@@ -166,7 +166,7 @@
         if (!spec.splitLists && dep.get(InstrumentedFilesInfo.SKYLARK_CONSTRUCTOR) != null) {
           continue;
         }
-        for (Artifact artifact : dep.getProvider(FileProvider.class).getFilesToBuild()) {
+        for (Artifact artifact : dep.getProvider(FileProvider.class).getFilesToBuild().toList()) {
           if (artifact.isSourceArtifact() &&
               spec.instrumentedFileTypes.matches(artifact.getFilename())) {
             localSourcesBuilder.add(artifact);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
index 06c5741..01a9fc8 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
@@ -211,7 +211,7 @@
     public String getValue() {
       StringBuilder buffer = new StringBuilder();
       buffer.append("\"");
-      for (Artifact artifact : jars) {
+      for (Artifact artifact : jars.toList()) {
         if (buffer.length() > 1) {
           buffer.append(File.pathSeparatorChar);
         }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
index 8817271..7beb823 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
@@ -167,7 +167,7 @@
                 Substitution.of(
                     "%main%", common.determineMainExecutableSource(/*withWorkspaceName=*/ true)),
                 Substitution.of("%python_binary%", pythonBinary),
-                Substitution.of("%imports%", Joiner.on(":").join(common.getImports())),
+                Substitution.of("%imports%", Joiner.on(":").join(common.getImports().toList())),
                 Substitution.of("%workspace_name%", ruleContext.getWorkspaceName()),
                 Substitution.of("%is_zipfile%", boolToLiteral(isForZipFile)),
                 Substitution.of(
@@ -349,13 +349,13 @@
     // Creating __init__.py files under each directory
     argv.add("__init__.py=");
     argv.addDynamicString(getZipRunfilesPath("__init__.py", workspaceName) + "=");
-    for (String path : runfilesSupport.getRunfiles().getEmptyFilenames()) {
+    for (String path : runfilesSupport.getRunfiles().getEmptyFilenames().toList()) {
       argv.addDynamicString(getZipRunfilesPath(path, workspaceName) + "=");
     }
 
     // Read each runfile from execute path, add them into zip file at the right runfiles path.
     // Filter the executable file, cause we are building it.
-    for (Artifact artifact : runfilesSupport.getRunfilesArtifacts()) {
+    for (Artifact artifact : runfilesSupport.getRunfilesArtifacts().toList()) {
       if (!artifact.equals(executable) && !artifact.equals(zipFile)) {
         argv.addDynamicString(
             getZipRunfilesPath(artifact.getRunfilesPath(), workspaceName)
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index 9c718c4..e8201ea 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -59,7 +59,7 @@
 
   private <T> void addNestedSetToFingerprintSlow(
       MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet) {
-    for (T object : nestedSet) {
+    for (T object : nestedSet.toList()) {
       mapFn.expandToCommandLine(object, fingerprint);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/EnvironmentLabels.java b/src/main/java/com/google/devtools/build/lib/packages/EnvironmentLabels.java
index b35cee2..789fc02 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/EnvironmentLabels.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/EnvironmentLabels.java
@@ -110,7 +110,7 @@
    *
    * <p>If no environments fulfill the input, returns an empty set.
    */
-  public Iterable<Label> getFulfillers(Label environment) {
+  public NestedSet<Label> getFulfillers(Label environment) {
     checkInitialized();
     return fulfillersMap.get(environment);
   }
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 e1f5b78..9dac136 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
@@ -604,7 +604,7 @@
           createDynamicLibrariesCopyActions(
               ruleContext,
               LibraryToLink.getDynamicLibrariesForRuntime(
-                  isStaticMode, depsCcLinkingContext.getLibraries()));
+                  isStaticMode, depsCcLinkingContext.getLibraries().toList()));
     }
 
     // TODO(bazel-team): Do we need to put original shared libraries (along with
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index 91e6ac1..d737fc1 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -286,7 +286,8 @@
     Iterable<? extends TransitiveInfoCollection> providers =
         ruleContext.getPrerequisitesIf("srcs", Mode.TARGET, FileProvider.class);
     for (TransitiveInfoCollection provider : providers) {
-      for (Artifact artifact : provider.getProvider(FileProvider.class).getFilesToBuild()) {
+      for (Artifact artifact :
+          provider.getProvider(FileProvider.class).getFilesToBuild().toList()) {
         // TODO(bazel-team): We currently do not produce an error for duplicate headers and other
         // non-source artifacts with different labels, as that would require cleaning up the code
         // base without significant benefit; we should eventually make this consistent one way or
@@ -309,7 +310,8 @@
     Iterable<? extends TransitiveInfoCollection> providers =
         ruleContext.getPrerequisitesIf("srcs", Mode.TARGET, FileProvider.class);
     for (TransitiveInfoCollection provider : providers) {
-      for (Artifact artifact : provider.getProvider(FileProvider.class).getFilesToBuild()) {
+      for (Artifact artifact :
+          provider.getProvider(FileProvider.class).getFilesToBuild().toList()) {
         if (!CppFileTypes.CPP_HEADER.matches(artifact.getExecPath())) {
           Label oldLabel = map.put(artifact, provider.getLabel());
           if (SourceCategory.CC_AND_OBJC.getSourceTypes().matches(artifact.getExecPathString())
@@ -345,7 +347,7 @@
     for (TransitiveInfoCollection target :
         ruleContext.getPrerequisitesIf("hdrs", Mode.TARGET, FileProvider.class)) {
       FileProvider provider = target.getProvider(FileProvider.class);
-      for (Artifact artifact : provider.getFilesToBuild()) {
+      for (Artifact artifact : provider.getFilesToBuild().toList()) {
         if (CppRuleClasses.DISALLOWED_HDRS_FILES.matches(artifact.getFilename())) {
           ruleContext.attributeWarning("hdrs", "file '" + artifact.getFilename()
               + "' from target '" + target.getLabel() + "' is not allowed in hdrs");
@@ -668,7 +670,7 @@
           ruleContext.getPrerequisites("srcs", Mode.TARGET, FileProvider.class)) {
         prerequisites.addAll(
             FileType.filter(
-                provider.getFilesToBuild(), SourceCategory.CC_AND_OBJC.getSourceTypes()));
+                provider.getFilesToBuild().toList(), SourceCategory.CC_AND_OBJC.getSourceTypes()));
       }
     }
     prerequisites.addTransitive(ccCompilationContext.getDeclaredIncludeSrcs());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
index 785df63..ec24a07 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
@@ -1187,14 +1187,14 @@
 
     HashMap<String, Integer> count = new LinkedHashMap<>();
     HashMap<String, Integer> number = new LinkedHashMap<>();
-    for (Artifact source : sourceArtifacts) {
+    for (Artifact source : sourceArtifacts.toList()) {
       String outputName =
           FileSystemUtils.removeExtension(source.getRootRelativePath()).getBaseName();
       count.put(outputName.toLowerCase(),
           count.getOrDefault(outputName.toLowerCase(), 0) + 1);
     }
 
-    for (Artifact source : sourceArtifacts) {
+    for (Artifact source : sourceArtifacts.toList()) {
       String outputName =
           FileSystemUtils.removeExtension(source.getRootRelativePath()).getBaseName();
       if (count.getOrDefault(outputName.toLowerCase(), 0) > 1) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
index 4423c8e..a831082 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
@@ -378,12 +378,12 @@
   }
 
   public List<Artifact> getDynamicLibrariesForRuntime(boolean linkingStatically) {
-    return LibraryToLink.getDynamicLibrariesForRuntime(linkingStatically, getLibraries());
+    return LibraryToLink.getDynamicLibrariesForRuntime(linkingStatically, getLibraries().toList());
   }
 
   public NestedSet<LibraryToLink> getLibraries() {
     NestedSetBuilder<LibraryToLink> libraries = NestedSetBuilder.linkOrder();
-    for (LinkerInput linkerInput : linkerInputs) {
+    for (LinkerInput linkerInput : linkerInputs.toList()) {
       libraries.addAll(linkerInput.libraries);
     }
     return libraries.build();
@@ -420,14 +420,14 @@
 
   public NestedSet<LinkOptions> getUserLinkFlags() {
     NestedSetBuilder<LinkOptions> userLinkFlags = NestedSetBuilder.linkOrder();
-    for (LinkerInput linkerInput : linkerInputs) {
+    for (LinkerInput linkerInput : linkerInputs.toList()) {
       userLinkFlags.addAll(linkerInput.getUserLinkFlags());
     }
     return userLinkFlags.build();
   }
 
   public ImmutableList<String> getFlattenedUserLinkFlags() {
-    return Streams.stream(getUserLinkFlags())
+    return Streams.stream(getUserLinkFlags().toList())
         .map(LinkOptions::get)
         .flatMap(Collection::stream)
         .collect(ImmutableList.toImmutableList());
@@ -435,7 +435,7 @@
 
   public NestedSet<Linkstamp> getLinkstamps() {
     NestedSetBuilder<Linkstamp> linkstamps = NestedSetBuilder.linkOrder();
-    for (LinkerInput linkerInput : linkerInputs) {
+    for (LinkerInput linkerInput : linkerInputs.toList()) {
       linkstamps.addAll(linkerInput.getLinkstamps());
     }
     return linkstamps.build();
@@ -443,7 +443,7 @@
 
   public NestedSet<Artifact> getNonCodeInputs() {
     NestedSetBuilder<Artifact> nonCodeInputs = NestedSetBuilder.linkOrder();
-    for (LinkerInput linkerInput : linkerInputs) {
+    for (LinkerInput linkerInput : linkerInputs.toList()) {
       nonCodeInputs.addAll(linkerInput.getNonCodeInputs());
     }
     return nonCodeInputs.build();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
index 4a94814..4067873 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
@@ -363,7 +363,7 @@
   public CcLinkingContext buildCcLinkingContextFromLibrariesToLink(
       List<LibraryToLink> librariesToLink, CcCompilationContext ccCompilationContext) {
     ImmutableList.Builder<Linkstamp> linkstampBuilder = ImmutableList.builder();
-    for (Artifact linkstamp : linkstamps.build()) {
+    for (Artifact linkstamp : linkstamps.build().toList()) {
       linkstampBuilder.add(
           new Linkstamp(
               linkstamp,
@@ -879,7 +879,7 @@
       NestedSet<LibraryToLink> librariesToLink, boolean staticMode, boolean forDynamicLibrary) {
     ImmutableList.Builder<LinkerInputs.LibraryToLink> librariesToLinkBuilder =
         ImmutableList.builder();
-    for (LibraryToLink libraryToLink : librariesToLink) {
+    for (LibraryToLink libraryToLink : librariesToLink.toList()) {
       LinkerInputs.LibraryToLink staticLibraryToLink =
           libraryToLink.getStaticLibrary() == null ? null : libraryToLink.getStaticLibraryToLink();
       LinkerInputs.LibraryToLink picStaticLibraryToLink =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderHelper.java
index c91be9a..ff0e60e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderHelper.java
@@ -355,7 +355,7 @@
 
   private static ImmutableList<Artifact> getBuiltinIncludes(NestedSet<Artifact> libc) {
     ImmutableList.Builder<Artifact> result = ImmutableList.builder();
-    for (Artifact artifact : libc) {
+    for (Artifact artifact : libc.toList()) {
       for (PathFragment suffix : BUILTIN_INCLUDE_FILE_SUFFIXES) {
         if (artifact.getExecPath().endsWith(suffix)) {
           result.add(artifact);
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 82f2544..fc6ae16 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
@@ -319,7 +319,7 @@
     if (!ltoCompilationContext.isEmpty()) {
       return true;
     }
-    for (LinkerInputs.LibraryToLink lib : libraries.build()) {
+    for (LinkerInputs.LibraryToLink lib : libraries.build().toList()) {
       if (!lib.getLtoCompilationContext().isEmpty()) {
         return true;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java b/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
index 87630a8..0c00d11 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
@@ -16,7 +16,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.CommandLines;
@@ -122,7 +121,8 @@
       ruleContext.attributeError("outs", "Genrules without outputs don't make sense");
     }
     if (ruleContext.attributes().get("executable", Type.BOOLEAN)
-        && Iterables.size(filesToBuild) > 1) {
+        && !filesToBuild.isEmpty()
+        && !filesToBuild.isSingleton()) {
       ruleContext.attributeError(
           "executable",
           "if genrules produce executables, they are allowed only one output. "
@@ -290,10 +290,7 @@
     if (!ruleContext.attributes().get("executable", Type.BOOLEAN)) {
       return null;
     }
-    if (Iterables.size(filesToBuild) == 1) {
-      return Iterables.getOnlyElement(filesToBuild);
-    }
-    return null;
+    return filesToBuild.isSingleton() ? filesToBuild.getSingleton() : null;
   }
 
   /**
@@ -339,7 +336,7 @@
 
     private String lookupVariableImpl(String variableName) throws ExpansionException {
       if (variableName.equals("SRCS")) {
-        return Artifact.joinExecPaths(" ", resolvedSrcs);
+        return Artifact.joinExecPaths(" ", resolvedSrcs.toList());
       }
 
       if (variableName.equals("<")) {
@@ -347,7 +344,7 @@
       }
 
       if (variableName.equals("OUTS")) {
-        return Artifact.joinExecPaths(" ", filesToBuild);
+        return Artifact.joinExecPaths(" ", filesToBuild.toList());
       }
 
       if (variableName.equals("@")) {
@@ -374,8 +371,8 @@
         // multiple filenames, this variable instead expands to the
         // package's root directory in the genfiles tree, even if all the
         // generated files belong to the same subdirectory!
-        if (Iterables.size(filesToBuild) == 1) {
-          Artifact outputFile = Iterables.getOnlyElement(filesToBuild);
+        if (filesToBuild.isSingleton()) {
+          Artifact outputFile = filesToBuild.getSingleton();
           PathFragment relativeOutputFile = outputFile.getExecPath();
           if (relativeOutputFile.segmentCount() <= 1) {
             // This should never happen, since the path should contain at
@@ -396,18 +393,17 @@
      * Returns the path of the sole element "artifacts", generating an exception with an informative
      * error message iff the set is not a singleton. Used to expand "$<", "$@".
      */
-    private final String expandSingletonArtifact(Iterable<Artifact> artifacts,
-        String variable,
-        String artifactName)
+    private static final String expandSingletonArtifact(
+        NestedSet<Artifact> artifacts, String variable, String artifactName)
         throws ExpansionException {
-      if (Iterables.isEmpty(artifacts)) {
+      if (artifacts.isEmpty()) {
         throw new ExpansionException("variable '" + variable
             + "' : no " + artifactName);
-      } else if (Iterables.size(artifacts) > 1) {
+      } else if (!artifacts.isSingleton()) {
         throw new ExpansionException("variable '" + variable
             + "' : more than one " + artifactName);
       }
-      return Iterables.getOnlyElement(artifacts).getExecPathString();
+      return artifacts.getSingleton().getExecPathString();
     }
   }
 }
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 dacae1b..2db758a 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
@@ -565,7 +565,7 @@
         // Add symlinks to the C++ runtime libraries under a path that can be built
         // into the Java binary without having to embed the crosstool, gcc, and grte
         // version information contained within the libraries' package paths.
-        for (Artifact lib : dynamicRuntimeActionInputs) {
+        for (Artifact lib : dynamicRuntimeActionInputs.toList()) {
           PathFragment path = CPP_RUNTIMES.getRelative(lib.getExecPath().getBaseName());
           builder.addSymlink(path, lib);
         }
@@ -583,7 +583,7 @@
       Iterable<? extends TransitiveInfoCollection> deps) {
     NestedSet<LibraryToLink> linkerInputs =
         new NativeLibraryNestedSetBuilder().addJavaTargets(deps).build();
-    return LibraryToLink.getDynamicLibrariesForLinking(linkerInputs);
+    return LibraryToLink.getDynamicLibrariesForLinking(linkerInputs.toList());
   }
 
   private static boolean isJavaTestRule(RuleContext ruleContext) {
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 6357397..2fd30dc 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
@@ -423,8 +423,10 @@
     // It is used to allow Error Prone checks to load additional data,
     // and Error Prone doesn't run during header compilation.
     builder.addAllJavacOpts(getJavacOpts());
-    if (Iterables.contains(
-        plugins.processorClasses(), "dagger.internal.codegen.ComponentProcessor")) {
+    if (plugins
+        .processorClasses()
+        .toList()
+        .contains("dagger.internal.codegen.ComponentProcessor")) {
       // see b/31371210
       builder.addJavacOpt("-Aexperimental_turbine_hjar");
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
index 7e39c09..a72006d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
@@ -195,7 +195,7 @@
       if (JavaInfo.getProvider(JavaCompilationArgsProvider.class, info) != null) {
         ruleContext.attributeError("jars", "should not refer to Java rules");
       }
-      for (Artifact jar : info.getProvider(FileProvider.class).getFilesToBuild()) {
+      for (Artifact jar : info.getProvider(FileProvider.class).getFilesToBuild().toList()) {
         if (!JavaSemantics.JAR.matches(jar.getFilename())) {
           ruleContext.attributeError("jars", jar.getFilename() + " is not a .jar file");
         } else {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 5daf155..dd072ac 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -2597,7 +2597,7 @@
               "Unexpected Exception type from PackageValue for '"
                   + pkgName
                   + "'' with root causes: "
-                  + Iterables.toString(error.getRootCauses()),
+                  + error.getRootCauses().toList().toString(),
               e);
         }
         return result.get(key).getPackage();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
index fa72a5d..686d6d1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
@@ -21,7 +21,6 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.FileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
@@ -357,7 +356,7 @@
         "Unexpected Exception type from PackageValue for '"
             + pkgId
             + "'' with root causes: "
-            + Iterables.toString(error.getRootCauses()),
+            + error.getRootCauses().toList().toString(),
         e);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Depset.java b/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
index 43f16e4..84bb8d1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
@@ -387,7 +387,7 @@
   @Override
   public void repr(Printer printer) {
     printer.append("depset(");
-    printer.printList(set, "[", ", ", "]", null);
+    printer.printList(set.toList(), "[", ", ", "]", null);
     Order order = getOrder();
     if (order != Order.STABLE_ORDER) {
       printer.append(", order = ");
diff --git a/src/main/java/com/google/devtools/build/skyframe/ErrorInfo.java b/src/main/java/com/google/devtools/build/skyframe/ErrorInfo.java
index 7a2c416..0451008 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ErrorInfo.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ErrorInfo.java
@@ -202,10 +202,10 @@
   /**
    * The root causes of a value that failed to build are its descendant values that failed to build.
    * If a value's descendants all built successfully, but it failed to, its root cause will be
-   * itself. If a value depends on a cycle, but has no other errors, this method will return
-   * the empty set.
+   * itself. If a value depends on a cycle, but has no other errors, this method will return the
+   * empty set.
    */
-  public Iterable<SkyKey> getRootCauses() {
+  public NestedSet<SkyKey> getRootCauses() {
     return rootCauses;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java b/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
index d7b53c8..3d4ee92 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ValueWithMetadata.java
@@ -15,7 +15,6 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -160,8 +159,8 @@
     public String toString() {
       return MoreObjects.toStringHelper(this)
           .add("value", value)
-          .add("transitiveEvents size", Iterables.size(transitiveEvents))
-          .add("transitivePostables size", Iterables.size(transitivePostables))
+          .add("transitiveEvents size", transitiveEvents.toList().size())
+          .add("transitivePostables size", transitivePostables.toList().size())
           .toString();
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/EnvironmentGroupTest.java b/src/test/java/com/google/devtools/build/lib/packages/EnvironmentGroupTest.java
index 947723c..6ed979b 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/EnvironmentGroupTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/EnvironmentGroupTest.java
@@ -94,13 +94,22 @@
   @Test
   public void fulfillers() throws Exception {
     EnvironmentLabels unpackedGroup = group.getEnvironmentLabels();
-    assertThat(unpackedGroup.getFulfillers(Label.parseAbsolute("//pkg:baz", ImmutableMap.of())))
+    assertThat(
+            unpackedGroup
+                .getFulfillers(Label.parseAbsolute("//pkg:baz", ImmutableMap.of()))
+                .toList())
         .containsExactly(
             Label.parseAbsolute("//pkg:foo", ImmutableMap.of()),
             Label.parseAbsolute("//pkg:bar", ImmutableMap.of()));
-    assertThat(unpackedGroup.getFulfillers(Label.parseAbsolute("//pkg:bar", ImmutableMap.of())))
+    assertThat(
+            unpackedGroup
+                .getFulfillers(Label.parseAbsolute("//pkg:bar", ImmutableMap.of()))
+                .toList())
         .containsExactly(Label.parseAbsolute("//pkg:foo", ImmutableMap.of()));
-    assertThat(unpackedGroup.getFulfillers(Label.parseAbsolute("//pkg:foo", ImmutableMap.of())))
+    assertThat(
+            unpackedGroup
+                .getFulfillers(Label.parseAbsolute("//pkg:foo", ImmutableMap.of()))
+                .toList())
         .isEmpty();
   }