diff --git a/src/main/java/com/google/devtools/build/lib/analysis/FileProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/FileProvider.java
index b94ef10..d71cf86 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/FileProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/FileProvider.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skylarkbuildapi.FileProviderApi;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /**
  * A representation of the concept "this transitive info provider builds these files".
@@ -42,20 +43,23 @@
   /**
    * Returns the set of artifacts that are the "output" of this rule.
    *
-   * <p>The term "output" is somewhat hazily defined; it is vaguely the set of files that are
-   * passed on to dependent rules that list the rule in their {@code srcs} attribute and the
-   * set of files that are built when a rule is mentioned on the command line. It does
-   * <b>not</b> include the runfiles; that is the bailiwick of {@code FilesToRunProvider}.
+   * <p>The term "output" is somewhat hazily defined; it is vaguely the set of files that are passed
+   * on to dependent rules that list the rule in their {@code srcs} attribute and the set of files
+   * that are built when a rule is mentioned on the command line. It does <b>not</b> include the
+   * runfiles; that is the bailiwick of {@code FilesToRunProvider}.
    *
    * <p>Note that the above definition is somewhat imprecise; in particular, when a rule is
-   * mentioned on the command line, some other files are also built
-   * {@code TopLevelArtifactHelper} and dependent rules are free to filter this set of artifacts
-   * e.g. based on their extension.
+   * mentioned on the command line, some other files are also built {@code TopLevelArtifactHelper}
+   * and dependent rules are free to filter this set of artifacts e.g. based on their extension.
    *
    * <p>Also, some rules may generate artifacts that are not listed here by way of defining other
    * implicit targets, for example, deploy jars.
    */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getFilesToBuildForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, filesToBuild);
+  }
+
   public NestedSet<Artifact> getFilesToBuild() {
     return filesToBuild;
   }
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 2fd9ef9..0efe6b5 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
@@ -39,6 +39,8 @@
 import com.google.devtools.build.lib.skylarkbuildapi.RunfilesApi;
 import com.google.devtools.build.lib.skylarkbuildapi.SymlinkEntryApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.BufferedReader;
@@ -336,6 +338,10 @@
    * pruning manifest candidates.
    */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getArtifactsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, getArtifacts());
+  }
+
   public NestedSet<Artifact> getArtifacts() {
     NestedSetBuilder<Artifact> allArtifacts = NestedSetBuilder.stableOrder();
     allArtifacts.addTransitive(unconditionalArtifacts);
@@ -347,11 +353,19 @@
 
   /** Returns the symlinks. */
   @Override
+  public SkylarkNestedSet /*<SymlinkEntry>*/ getSymlinksForStarlark() {
+    return SkylarkNestedSet.of(SymlinkEntry.class, symlinks);
+  }
+
   public NestedSet<SymlinkEntry> getSymlinks() {
     return symlinks;
   }
 
   @Override
+  public SkylarkNestedSet /*<String>*/ getEmptyFilenamesForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, getEmptyFilenames());
+  }
+
   public NestedSet<String> getEmptyFilenames() {
     Set<PathFragment> manifestKeys =
         Streams.concat(
@@ -574,6 +588,10 @@
 
   /** Returns the root symlinks. */
   @Override
+  public SkylarkNestedSet /*<SymlinkEntry>*/ getRootSymlinksForStarlark() {
+    return SkylarkNestedSet.of(SymlinkEntry.class, rootSymlinks);
+  }
+
   public NestedSet<SymlinkEntry> getRootSymlinks() {
     return rootSymlinks;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
index 19e4527..051cc78 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
@@ -110,6 +110,10 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<ParsedAndroidAssets>*/ getDirectParsedAssetsForStarlark() {
+    return SkylarkNestedSet.of(ParsedAndroidAssets.class, directParsedAssets);
+  }
+
   public NestedSet<ParsedAndroidAssets> getDirectParsedAssets() {
     return directParsedAssets;
   }
@@ -125,16 +129,28 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<ParsedAndroidAssets>*/ getTransitiveParsedAssetsForStarlark() {
+    return SkylarkNestedSet.of(ParsedAndroidAssets.class, transitiveParsedAssets);
+  }
+
   public NestedSet<ParsedAndroidAssets> getTransitiveParsedAssets() {
     return transitiveParsedAssets;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getAssetsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveAssets);
+  }
+
   public NestedSet<Artifact> getAssets() {
     return transitiveAssets;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getSymbolsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveSymbols);
+  }
+
   public NestedSet<Artifact> getSymbols() {
     return transitiveSymbols;
   }
@@ -146,7 +162,11 @@
   }
 
   @Override
-  public NestedSet<Artifact> getCompiledSymbols() {
+  public SkylarkNestedSet /*<Artifact>*/ getCompiledSymbolsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveCompiledSymbols);
+  }
+
+  NestedSet<Artifact> getCompiledSymbols() {
     return transitiveCompiledSymbols;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
index 1642ca8..a40b6ea 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidIdlProviderApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.SkylarkType;
 
 /**
  * Configured targets implementing this provider can contribute Android IDL information to the
@@ -51,22 +52,38 @@
   }
 
   @Override
-  public NestedSet<String> getTransitiveIdlImportRoots() {
+  public SkylarkNestedSet /*<String>*/ getTransitiveIdlImportRootsForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, transitiveIdlImportRoots);
+  }
+
+  NestedSet<String> getTransitiveIdlImportRoots() {
     return transitiveIdlImportRoots;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveIdlImports() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveIdlImportsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveIdlImports);
+  }
+
+  NestedSet<Artifact> getTransitiveIdlImports() {
     return transitiveIdlImports;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveIdlJars() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveIdlJarsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveIdlJars);
+  }
+
+  NestedSet<Artifact> getTransitiveIdlJars() {
     return transitiveIdlJars;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveIdlPreprocessed() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveIdlPreprocessedForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveIdlPreprocessed);
+  }
+
+  NestedSet<Artifact> getTransitiveIdlPreprocessed() {
     return transitiveIdlPreprocessed;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
index a3ce116..2617fc5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.packages.NativeInfo;
 import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidLibraryAarInfoApi;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import java.util.Objects;
 import javax.annotation.Nullable;
 
@@ -79,6 +80,10 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveAarArtifactsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveAarArtifacts);
+  }
+
   public NestedSet<Artifact> getTransitiveAarArtifacts() {
     return transitiveAarArtifacts;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
index 23be2e5..38074bc 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidLibraryResourceClassJarProviderApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
-import javax.annotation.Nonnull;
 
 /**
  * A provider which contains the resource class jars from android_library rules. See {@link
@@ -52,8 +51,11 @@
         target.get(AndroidLibraryResourceClassJarProvider.PROVIDER.getKey());
   }
 
-  @Nonnull
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getResourceClassJarsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, resourceClassJars);
+  }
+
   public NestedSet<Artifact> getResourceClassJars() {
     return resourceClassJars;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
index 2d6dcb3..eb9247c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
@@ -43,7 +43,11 @@
   }
 
   @Override
-  public NestedSet<Artifact> getNativeLibs() {
+  public SkylarkNestedSet /*<Artifact>*/ getNativeLibsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, nativeLibs);
+  }
+
+  NestedSet<Artifact> getNativeLibs() {
     return nativeLibs;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
index 08385a7..d931d07 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
@@ -111,52 +111,93 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<ValidatedAndroidResources>*/
+      getTransitiveAndroidResourcesForStarlark() {
+    return SkylarkNestedSet.of(ValidatedAndroidResources.class, transitiveAndroidResources);
+  }
+
   public NestedSet<ValidatedAndroidResources> getTransitiveAndroidResources() {
     return transitiveAndroidResources;
   }
 
   @Override
+  public SkylarkNestedSet /*<ValidatedAndroidResources>*/ getDirectAndroidResourcesForStarlark() {
+    return SkylarkNestedSet.of(ValidatedAndroidResources.class, directAndroidResources);
+  }
+
   public NestedSet<ValidatedAndroidResources> getDirectAndroidResources() {
     return directAndroidResources;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveResourcesForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveResources);
+  }
+
   public NestedSet<Artifact> getTransitiveResources() {
     return transitiveResources;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveManifestsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveManifests);
+  }
+
   public NestedSet<Artifact> getTransitiveManifests() {
     return transitiveManifests;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveAapt2RTxtForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveAapt2RTxt);
+  }
+
   public NestedSet<Artifact> getTransitiveAapt2RTxt() {
     return transitiveAapt2RTxt;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveAapt2ValidationArtifacts() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveAapt2ValidationArtifactsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveAapt2ValidationArtifacts);
+  }
+
+  NestedSet<Artifact> getTransitiveAapt2ValidationArtifacts() {
     return transitiveAapt2ValidationArtifacts;
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveSymbolsBinForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveSymbolsBin);
+  }
+
   public NestedSet<Artifact> getTransitiveSymbolsBin() {
     return transitiveSymbolsBin;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveCompiledSymbols() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveCompiledSymbolsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveCompiledSymbols);
+  }
+
+  NestedSet<Artifact> getTransitiveCompiledSymbols() {
     return transitiveCompiledSymbols;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveStaticLib() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveStaticLibForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveStaticLib);
+  }
+
+  NestedSet<Artifact> getTransitiveStaticLib() {
     return transitiveStaticLib;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveRTxt() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveRTxtForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveRTxt);
+  }
+
+  NestedSet<Artifact> getTransitiveRTxt() {
     return transitiveRTxt;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkApiProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkApiProvider.java
index b32a0c5..bc2ae90 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkApiProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkApiProvider.java
@@ -97,8 +97,9 @@
   }
 
   @Override
-  public NestedSet<Artifact> getResources() {
-    return collectDirectArtifacts(ValidatedAndroidResources::getResources);
+  public SkylarkNestedSet /*<Artifact>*/ getResources() {
+    return SkylarkNestedSet.of(
+        Artifact.TYPE, collectDirectArtifacts(ValidatedAndroidResources::getResources));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
index 1462874..6e0bcbe 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.android.DataBindingV2ProviderApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import javax.annotation.Nullable;
 
 /**
@@ -75,6 +76,10 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveBRFilesForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveBRFiles);
+  }
+
   public NestedSet<Artifact> getTransitiveBRFiles() {
     return transitiveBRFiles;
   }
@@ -86,6 +91,11 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<LabelJavaPackagePair>*/
+      getTransitiveLabelAndJavaPackagesForStarlark() {
+    return SkylarkNestedSet.of(LabelJavaPackagePair.class, transitiveLabelAndJavaPackages);
+  }
+
   public NestedSet<LabelJavaPackagePair> getTransitiveLabelAndJavaPackages() {
     return transitiveLabelAndJavaPackages;
   }
@@ -96,6 +106,7 @@
       Artifact brFile,
       String label,
       String javaPackage,
+      // ugh these *Api types do not help one bit
       Iterable<? extends DataBindingV2ProviderApi<Artifact>> databindingV2ProvidersInDeps,
       Iterable<? extends DataBindingV2ProviderApi<Artifact>> databindingV2ProvidersInExports) {
 
@@ -126,7 +137,8 @@
 
     if (databindingV2ProvidersInDeps != null) {
 
-      for (DataBindingV2ProviderApi<Artifact> provider : databindingV2ProvidersInDeps) {
+      for (DataBindingV2ProviderApi<Artifact> p : databindingV2ProvidersInDeps) {
+        DataBindingV2Provider provider = (DataBindingV2Provider) p;
         brFiles.addTransitive(provider.getTransitiveBRFiles());
         transitiveLabelAndJavaPackages.addTransitive(provider.getTransitiveLabelAndJavaPackages());
       }
@@ -136,7 +148,8 @@
 
       // Add all of the information from providers from exported targets, so that targets which
       // depend on this target appear to depend on the exported targets.
-      for (DataBindingV2ProviderApi<Artifact> provider : databindingV2ProvidersInExports) {
+      for (DataBindingV2ProviderApi<Artifact> p : databindingV2ProvidersInExports) {
+        DataBindingV2Provider provider = (DataBindingV2Provider) p;
         setterStoreFiles.addAll(provider.getSetterStores());
         classInfoFiles.addAll(provider.getClassInfos());
         brFiles.addTransitive(provider.getTransitiveBRFiles());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcSkylarkApiProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcSkylarkApiProvider.java
index e7eb2fb..81969e4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcSkylarkApiProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcSkylarkApiProvider.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skylarkbuildapi.cpp.CcSkylarkApiProviderApi;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 /**
@@ -42,14 +43,22 @@
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveHeaders() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveHeadersForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, getTransitiveHeaders());
+  }
+
+  NestedSet<Artifact> getTransitiveHeaders() {
     CcCompilationContext ccCompilationContext =
         getInfo().get(CcInfo.PROVIDER).getCcCompilationContext();
     return ccCompilationContext.getDeclaredIncludeSrcs();
   }
 
   @Override
-  public NestedSet<Artifact> getLibraries() {
+  public SkylarkNestedSet /*<Artifact>*/ getLibrariesForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, getLibraries());
+  }
+
+  NestedSet<Artifact> getLibraries() {
     NestedSetBuilder<Artifact> libs = NestedSetBuilder.linkOrder();
     CcInfo ccInfo = getInfo().get(CcInfo.PROVIDER);
     if (ccInfo == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/GoogleLegacyStubs.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/GoogleLegacyStubs.java
index 5c90696..358c9e6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/GoogleLegacyStubs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/GoogleLegacyStubs.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.rules.cpp;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.RunfilesApi;
 import com.google.devtools.build.lib.skylarkbuildapi.SkylarkRuleContextApi;
@@ -239,7 +238,7 @@
     }
 
     @Override
-    public NestedSet<FileApi> getGopackageFiles(
+    public SkylarkNestedSet /*<FileApi>*/ getGopackageFilesForStarlark(
         SkylarkRuleContextApi skylarkRuleContext, FileApi skylarkGopkg) {
       return null;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaGenJarsProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaGenJarsProvider.java
index a0931d3..fc69382 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaGenJarsProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaGenJarsProvider.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skylarkbuildapi.java.JavaAnnotationProcessingApi;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import javax.annotation.Nullable;
 
 /** The collection of gen jars from the transitive closure. */
@@ -105,17 +106,29 @@
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveGenClassJars() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveGenClassJarsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveGenClassJars);
+  }
+
+  NestedSet<Artifact> getTransitiveGenClassJars() {
     return transitiveGenClassJars;
   }
 
   @Override
-  public NestedSet<Artifact> getTransitiveGenSourceJars() {
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveGenSourceJarsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveGenSourceJars);
+  }
+
+  NestedSet<Artifact> getTransitiveGenSourceJars() {
     return transitiveGenSourceJars;
   }
 
   @Override
-  public NestedSet<Artifact> getProcessorClasspath() {
+  public SkylarkNestedSet /*<Artifact>*/ getProcessorClasspathForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, processorClasspath);
+  }
+
+  NestedSet<Artifact> getProcessorClasspath() {
     return processorClasspath;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
index f2da42e..572fa14 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
@@ -39,6 +39,10 @@
   }
 
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveProguardSpecsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveProguardSpecs);
+  }
+
   public NestedSet<Artifact> getTransitiveProguardSpecs() {
     return transitiveProguardSpecs;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
index 4766f91..89c6823 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
@@ -71,6 +71,10 @@
 
   /** @return the proto jars used to generate the registry. */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getInputsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, inputs);
+  }
+
   public NestedSet<Artifact> getInputs() {
     return inputs;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
index 8620829..44c08ef 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
@@ -43,6 +43,7 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.Collections;
@@ -394,18 +395,26 @@
       ImmutableSet.<Key<?>>of(HEADER, MODULE_MAP, SOURCE);
 
   @Override
+  public SkylarkNestedSet /*<String>*/ defineForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, define());
+  }
+
   public NestedSet<String> define() {
     return get(DEFINE);
   }
 
   @Override
-  public NestedSet<Artifact> dynamicFrameworkFile() {
+  public SkylarkNestedSet /*<Artifact>*/ dynamicFrameworkFileForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, dynamicFrameworkFile());
+  }
+
+  NestedSet<Artifact> dynamicFrameworkFile() {
     return get(DYNAMIC_FRAMEWORK_FILE);
   }
 
   @Override
-  public NestedSet<Artifact> exportedDebugArtifacts() {
-    return get(EXPORTED_DEBUG_ARTIFACTS);
+  public SkylarkNestedSet /*<Artifact>*/ exportedDebugArtifacts() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(EXPORTED_DEBUG_ARTIFACTS));
   }
 
   @Override
@@ -414,12 +423,16 @@
   }
 
   @Override
-  public NestedSet<Artifact> forceLoadLibrary() {
-    return get(FORCE_LOAD_LIBRARY);
+  public SkylarkNestedSet /*<Artifact>*/ forceLoadLibrary() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(FORCE_LOAD_LIBRARY));
   }
 
   @Override
-  public NestedSet<Artifact> header() {
+  public SkylarkNestedSet /*<Artifact>*/ headerForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, header());
+  }
+
+  NestedSet<Artifact> header() {
     return get(HEADER);
   }
 
@@ -429,12 +442,12 @@
   }
 
   @Override
-  public NestedSet<Artifact> importedLibrary() {
-    return get(IMPORTED_LIBRARY);
+  public SkylarkNestedSet /*<Artifact>*/ importedLibrary() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(IMPORTED_LIBRARY));
   }
 
   @Override
-  public SkylarkNestedSet include() {
+  public SkylarkNestedSet /*<String>*/ include() {
     return ObjcProviderSkylarkConverters.convertPathFragmentsToSkylark(get(INCLUDE));
   }
 
@@ -449,48 +462,48 @@
   }
 
   @Override
-  public NestedSet<Artifact> j2objcLibrary() {
-    return get(J2OBJC_LIBRARY);
+  public SkylarkNestedSet /*<Artifact>*/ j2objcLibrary() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(J2OBJC_LIBRARY));
   }
 
   @Override
-  public NestedSet<Artifact> jreLibrary() {
-    return get(JRE_LIBRARY);
+  public SkylarkNestedSet /*<Artifact>*/ jreLibrary() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(JRE_LIBRARY));
   }
 
   @Override
-  public NestedSet<Artifact> library() {
-    return get(LIBRARY);
+  public SkylarkNestedSet /*<Artifact>*/ library() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(LIBRARY));
   }
 
   @Override
-  public NestedSet<Artifact> linkInputs() {
-    return get(LINK_INPUTS);
+  public SkylarkNestedSet /*<Artifact>*/ linkInputs() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(LINK_INPUTS));
   }
 
   @Override
-  public NestedSet<Artifact> linkedBinary() {
-    return get(LINKED_BINARY);
+  public SkylarkNestedSet /*<Artifact>*/ linkedBinary() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(LINKED_BINARY));
   }
 
   @Override
-  public NestedSet<Artifact> linkmapFile() {
-    return get(LINKMAP_FILE);
+  public SkylarkNestedSet /*<Artifact>*/ linkmapFile() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(LINKMAP_FILE));
   }
 
   @Override
-  public NestedSet<String> linkopt() {
-    return get(LINKOPT);
+  public SkylarkNestedSet /*<String>*/ linkopt() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, get(LINKOPT));
   }
 
   @Override
-  public NestedSet<Artifact> mergeZip() {
-    return get(MERGE_ZIP);
+  public SkylarkNestedSet /*<Artifact>*/ mergeZip() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(MERGE_ZIP));
   }
 
   @Override
-  public NestedSet<Artifact> moduleMap() {
-    return get(MODULE_MAP);
+  public SkylarkNestedSet /*<Artifact>*/ moduleMap() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(MODULE_MAP));
   }
 
   @Override
@@ -499,23 +512,23 @@
   }
 
   @Override
-  public NestedSet<Artifact> multiArchDynamicLibraries() {
-    return get(MULTI_ARCH_DYNAMIC_LIBRARIES);
+  public SkylarkNestedSet /*<Artifact>*/ multiArchDynamicLibraries() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(MULTI_ARCH_DYNAMIC_LIBRARIES));
   }
 
   @Override
-  public NestedSet<Artifact> multiArchLinkedArchives() {
-    return get(MULTI_ARCH_LINKED_ARCHIVES);
+  public SkylarkNestedSet /*<Artifact>*/ multiArchLinkedArchives() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(MULTI_ARCH_LINKED_ARCHIVES));
   }
 
   @Override
-  public NestedSet<Artifact> multiArchLinkedBinaries() {
-    return get(MULTI_ARCH_LINKED_BINARIES);
+  public SkylarkNestedSet /*<Artifact>*/ multiArchLinkedBinaries() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(MULTI_ARCH_LINKED_BINARIES));
   }
 
   @Override
-  public NestedSet<String> sdkDylib() {
-    return get(SDK_DYLIB);
+  public SkylarkNestedSet /*<String>*/ sdkDylib() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, get(SDK_DYLIB));
   }
 
   @Override
@@ -525,7 +538,11 @@
   }
 
   @Override
-  public NestedSet<Artifact> source() {
+  public SkylarkNestedSet /*<Artifact>*/ sourceForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, source());
+  }
+
+  NestedSet<Artifact> source() {
     return get(SOURCE);
   }
 
@@ -535,13 +552,17 @@
   }
 
   @Override
-  public NestedSet<Artifact> staticFrameworkFile() {
+  public SkylarkNestedSet /*<Artifact>*/ staticFrameworkFileForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, staticFrameworkFile());
+  }
+
+  NestedSet<Artifact> staticFrameworkFile() {
     return get(STATIC_FRAMEWORK_FILE);
   }
 
   @Override
-  public NestedSet<Artifact> umbrellaHeader() {
-    return get(UMBRELLA_HEADER);
+  public SkylarkNestedSet /*<Artifact>*/ umbrellaHeader() {
+    return SkylarkNestedSet.of(Artifact.TYPE, get(UMBRELLA_HEADER));
   }
 
   @Override
@@ -936,22 +957,38 @@
   }
 
   @Override
-  public NestedSet<String> dynamicFrameworkNames() {
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkNamesForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, dynamicFrameworkNames());
+  }
+
+  NestedSet<String> dynamicFrameworkNames() {
     return getFrameworkNames(DYNAMIC_FRAMEWORK_FILE);
   }
 
   @Override
-  public NestedSet<String> dynamicFrameworkPaths() {
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkPathsForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, dynamicFrameworkPaths());
+  }
+
+  NestedSet<String> dynamicFrameworkPaths() {
     return getFrameworkPaths(DYNAMIC_FRAMEWORK_FILE);
   }
 
   @Override
-  public NestedSet<String> staticFrameworkNames() {
+  public SkylarkNestedSet /*<String>*/ staticFrameworkNamesForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, staticFrameworkNames());
+  }
+
+  NestedSet<String> staticFrameworkNames() {
     return getFrameworkNames(STATIC_FRAMEWORK_FILE);
   }
 
   @Override
-  public NestedSet<String> staticFrameworkPaths() {
+  public SkylarkNestedSet /*<String>*/ staticFrameworkPathsForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, staticFrameworkPaths());
+  }
+
+  NestedSet<String> staticFrameworkPaths() {
     return getFrameworkPaths(STATIC_FRAMEWORK_FILE);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
index e6008dd..3fb6b57 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
@@ -24,6 +24,8 @@
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skylarkbuildapi.ProtoInfoApi;
 import com.google.devtools.build.lib.skylarkbuildapi.proto.ProtoBootstrap;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.util.Pair;
 import javax.annotation.Nullable;
 
@@ -122,6 +124,10 @@
 
   /** The proto sources in the transitive closure of this rule. */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveProtoSourcesForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, getTransitiveProtoSources());
+  }
+
   public NestedSet<Artifact> getTransitiveProtoSources() {
     return transitiveProtoSources;
   }
@@ -131,14 +137,18 @@
    * {@code protoc} in the specified order, via the {@code --proto_path} flag.
    */
   @Override
+  public SkylarkNestedSet /*<String>*/ getTransitiveProtoSourceRootsForStarlark() {
+    return SkylarkNestedSet.of(SkylarkType.STRING, transitiveProtoSourceRoots);
+  }
+
   public NestedSet<String> getTransitiveProtoSourceRoots() {
     return transitiveProtoSourceRoots;
   }
 
   @Deprecated
   @Override
-  public NestedSet<Artifact> getTransitiveImports() {
-    return getTransitiveProtoSources();
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveImports() {
+    return getTransitiveProtoSourcesForStarlark();
   }
 
   /**
@@ -149,6 +159,10 @@
    * direct dependencies, but not from transitive ones)
    */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getStrictImportableProtoSourcesForDependentsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, strictImportableProtoSourcesForDependents);
+  }
+
   public NestedSet<Artifact> getStrictImportableProtoSourcesForDependents() {
     return strictImportableProtoSourcesForDependents;
   }
@@ -217,6 +231,10 @@
    * direct-srcs descriptor set)
    */
   @Override
+  public SkylarkNestedSet /*<Artifact>*/ getTransitiveDescriptorSetsForStarlark() {
+    return SkylarkNestedSet.of(Artifact.TYPE, transitiveDescriptorSets);
+  }
+
   public NestedSet<Artifact> getTransitiveDescriptorSets() {
     return transitiveDescriptorSets;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/FileProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/FileProviderApi.java
index c645e58..e4c2700 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/FileProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/FileProviderApi.java
@@ -14,11 +14,11 @@
 
 package com.google.devtools.build.lib.skylarkbuildapi;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** A representation of the concept "this builds these files". */
 @SkylarkModule(
@@ -43,5 +43,5 @@
    * implicit targets, for example, deploy jars.
    */
   @SkylarkCallable(name = "files_to_build", documented = false, structField = true)
-  NestedSet<? extends FileApi> getFilesToBuild();
+  SkylarkNestedSet /*<? extends FileApi>*/ getFilesToBuildForStarlark();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/ProtoInfoApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/ProtoInfoApi.java
index 66d542b..3e61b2a 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/ProtoInfoApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/ProtoInfoApi.java
@@ -15,10 +15,10 @@
 package com.google.devtools.build.lib.skylarkbuildapi;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** Info object propagating information about protocol buffer sources. */
 @SkylarkModule(
@@ -43,7 +43,7 @@
       name = "transitive_imports",
       doc = "Transitive imports including weak dependencies.",
       structField = true)
-  public NestedSet<FileT> getTransitiveImports();
+  public SkylarkNestedSet /*<FileT>*/ getTransitiveImports();
 
   @SkylarkCallable(
       name = "transitive_sources",
@@ -52,7 +52,7 @@
   // TODO(bazel-team): The difference between transitive imports and transitive proto sources
   // should never be used by Skylark or by an Aspect. One of these two should be removed,
   // preferably soon, before Skylark users start depending on them.
-  public NestedSet<FileT> getTransitiveProtoSources();
+  public SkylarkNestedSet /*<FileT>*/ getTransitiveProtoSourcesForStarlark();
 
   @SkylarkCallable(
       name = "direct_sources",
@@ -67,7 +67,7 @@
               + "that has no sources, it contains the check_deps_sources "
               + "from this library's direct deps.",
       structField = true)
-  public NestedSet<FileT> getStrictImportableProtoSourcesForDependents();
+  public SkylarkNestedSet /*<FileT>*/ getStrictImportableProtoSourcesForDependentsForStarlark();
 
   @SkylarkCallable(
       name = "direct_descriptor_set",
@@ -87,13 +87,13 @@
               + " as passing --include_imports to proto-compiler. Will be empty if no"
               + " dependencies.",
       structField = true)
-  public NestedSet<FileT> getTransitiveDescriptorSets();
+  public SkylarkNestedSet /*<FileT>*/ getTransitiveDescriptorSetsForStarlark();
 
   @SkylarkCallable(
       name = "transitive_proto_path",
       doc = "A set of proto source roots collected from the transitive closure of this rule.",
       structField = true)
-  public NestedSet<String> getTransitiveProtoSourceRoots();
+  public SkylarkNestedSet /*<String>*/ getTransitiveProtoSourceRootsForStarlark();
 
   @SkylarkCallable(
       name = "proto_source_root",
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/RunfilesApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/RunfilesApi.java
index d868e33..c41e2b0 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/RunfilesApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/RunfilesApi.java
@@ -14,12 +14,12 @@
 
 package com.google.devtools.build.lib.skylarkbuildapi;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkinterface.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** An interface for a set of runfiles. */
 @SkylarkModule(
@@ -33,27 +33,25 @@
 public interface RunfilesApi extends SkylarkValue {
 
   @SkylarkCallable(
-    name = "files",
-    doc = "Returns the set of runfiles as files.",
-    structField = true
-  )
-  public NestedSet<? extends FileApi> getArtifacts();
+      name = "files",
+      doc = "Returns the set of runfiles as files.",
+      structField = true)
+  public SkylarkNestedSet /*<? extends FileApi>*/ getArtifactsForStarlark();
 
   @SkylarkCallable(name = "symlinks", doc = "Returns the set of symlinks.", structField = true)
-  public NestedSet<? extends SymlinkEntryApi> getSymlinks();
+  public SkylarkNestedSet /*<? extends SymlinkEntryApi>*/ getSymlinksForStarlark();
 
   @SkylarkCallable(
       name = "root_symlinks",
       doc = "Returns the set of root symlinks.",
       structField = true)
-  public NestedSet<? extends SymlinkEntryApi> getRootSymlinks();
+  public SkylarkNestedSet /*<? extends SymlinkEntryApi>*/ getRootSymlinksForStarlark();
 
   @SkylarkCallable(
-    name = "empty_filenames",
-    doc = "Returns names of empty files to create.",
-    structField = true
-  )
-  public NestedSet<String> getEmptyFilenames();
+      name = "empty_filenames",
+      doc = "Returns names of empty files to create.",
+      structField = true)
+  public SkylarkNestedSet /*<String>*/ getEmptyFilenamesForStarlark();
 
   @SkylarkCallable(
     name = "merge",
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidAssetsInfoApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidAssetsInfoApi.java
index 91867a0..a32a1d1 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidAssetsInfoApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidAssetsInfoApi.java
@@ -15,7 +15,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -62,7 +61,7 @@
   FileApi getValidationResult();
 
   @SkylarkCallable(name = "direct_parsed_assets", structField = true, doc = "", documented = false)
-  NestedSet<AssetsT> getDirectParsedAssets();
+  SkylarkNestedSet /*<AssetsT>*/ getDirectParsedAssetsForStarlark();
 
   /** Returns the local assets for the target. */
   @SkylarkCallable(
@@ -87,16 +86,16 @@
       structField = true,
       doc = "",
       documented = false)
-  NestedSet<AssetsT> getTransitiveParsedAssets();
+  SkylarkNestedSet /*<AssetsT>*/ getTransitiveParsedAssetsForStarlark();
 
   @SkylarkCallable(name = "assets", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getAssets();
+  SkylarkNestedSet /*<FileT>*/ getAssetsForStarlark();
 
   @SkylarkCallable(name = "symbols", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getSymbols();
+  SkylarkNestedSet /*<FileT>*/ getSymbolsForStarlark();
 
   @SkylarkCallable(name = "compiled_symbols", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getCompiledSymbols();
+  SkylarkNestedSet /*<FileT>*/ getCompiledSymbolsForStarlark();
 
   /** The provider implementing this can construct the AndroidAssetsInfo provider. */
   @SkylarkModule(
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidIdlProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidIdlProviderApi.java
index 2d57de2..f1ce426 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidIdlProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidIdlProviderApi.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -48,7 +47,7 @@
       structField = true,
       doc = "Returns a depset of strings of all the idl import roots.",
       documented = false)
-  NestedSet<String> getTransitiveIdlImportRoots();
+  SkylarkNestedSet /*<String>*/ getTransitiveIdlImportRootsForStarlark();
 
   /** The IDL files in the transitive closure. */
   @SkylarkCallable(
@@ -56,7 +55,7 @@
       structField = true,
       doc = "Returns a depset of artifacts of all the idl imports.",
       documented = false)
-  NestedSet<FileT> getTransitiveIdlImports();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveIdlImportsForStarlark();
 
   /** The IDL jars in the transitive closure, both class and source jars. */
   @SkylarkCallable(
@@ -64,7 +63,7 @@
       structField = true,
       doc = "Returns a depset of artifacts of all the idl class and source jars.",
       documented = false)
-  NestedSet<FileT> getTransitiveIdlJars();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveIdlJarsForStarlark();
 
   /** The preprocessed IDL files in the transitive closure. */
   @SkylarkCallable(
@@ -72,7 +71,7 @@
       structField = true,
       doc = "Returns a depset of artifacts of all the idl preprocessed files.",
       documented = false)
-  NestedSet<FileT> getTransitiveIdlPreprocessed();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveIdlPreprocessedForStarlark();
 
   /** The provider implementing this can construct the AndroidIdlInfo provider. */
   @SkylarkModule(
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryAarInfoApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryAarInfoApi.java
index d2467f9..229d9f1 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryAarInfoApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryAarInfoApi.java
@@ -13,12 +13,12 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** A target that can provide the aar artifact of Android libraries */
 @SkylarkModule(
@@ -47,5 +47,5 @@
       doc = "",
       documented = false,
       structField = true)
-  NestedSet<FileT> getTransitiveAarArtifacts();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveAarArtifactsForStarlark();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryResourceClassJarProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryResourceClassJarProviderApi.java
index 6b6a87f..5041f11 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryResourceClassJarProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidLibraryResourceClassJarProviderApi.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -40,7 +39,7 @@
   String NAME = "AndroidLibraryResourceClassJarProvider";
 
   @SkylarkCallable(name = "jars", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getResourceClassJars();
+  SkylarkNestedSet /*<FileT>*/ getResourceClassJarsForStarlark();
 
   /** The provider implementing this can construct the AndroidLibraryResourceClassJarProvider. */
   @SkylarkModule(
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidNativeLibsInfoApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidNativeLibsInfoApi.java
index d6781221..4b1b7f7 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidNativeLibsInfoApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidNativeLibsInfoApi.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -46,7 +45,7 @@
       doc = "Returns the native libraries produced by the rule.",
       documented = false,
       structField = true)
-  NestedSet<FileT> getNativeLibs();
+  SkylarkNestedSet /*<FileT>*/ getNativeLibsForStarlark();
 
   /** Provider for {@link AndroidNativeLibsInfoApi}. */
   @SkylarkModule(
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidResourcesInfoApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidResourcesInfoApi.java
index e13e67b..2ac36ba 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidResourcesInfoApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidResourcesInfoApi.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -74,7 +73,7 @@
       doc = "Returns the transitive ResourceContainers for the label.",
       documented = false,
       structField = true)
-  NestedSet<ValidatedAndroidDataT> getTransitiveAndroidResources();
+  SkylarkNestedSet /*<ValidatedAndroidDataT>*/ getTransitiveAndroidResourcesForStarlark();
 
   /** Returns the immediate ResourceContainers for the label. */
   @SkylarkCallable(
@@ -82,44 +81,44 @@
       doc = "Returns the immediate ResourceContainers for the label.",
       documented = false,
       structField = true)
-  NestedSet<ValidatedAndroidDataT> getDirectAndroidResources();
+  SkylarkNestedSet /*<ValidatedAndroidDataT>*/ getDirectAndroidResourcesForStarlark();
 
   @SkylarkCallable(name = "transitive_resources", doc = "", documented = false, structField = true)
-  NestedSet<FileT> getTransitiveResources();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveResourcesForStarlark();
 
   @SkylarkCallable(name = "transitive_manifests", doc = "", documented = false, structField = true)
-  NestedSet<FileT> getTransitiveManifests();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveManifestsForStarlark();
 
   @SkylarkCallable(
       name = "transitive_aapt2_r_txt",
       doc = "",
       documented = false,
       structField = true)
-  NestedSet<FileT> getTransitiveAapt2RTxt();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveAapt2RTxtForStarlark();
 
   // TODO(b/132383435): remove this
   @SkylarkCallable(name = "validation_artifacts", doc = "", documented = false, structField = true)
-  NestedSet<FileT> getTransitiveAapt2ValidationArtifacts();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveAapt2ValidationArtifactsForStarlark();
 
   @SkylarkCallable(
       name = "transitive_symbols_bin",
       doc = "",
       documented = false,
       structField = true)
-  NestedSet<FileT> getTransitiveSymbolsBin();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveSymbolsBinForStarlark();
 
   @SkylarkCallable(
       name = "transitive_compiled_symbols",
       doc = "",
       documented = false,
       structField = true)
-  NestedSet<FileT> getTransitiveCompiledSymbols();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveCompiledSymbolsForStarlark();
 
   @SkylarkCallable(name = "transitive_static_lib", doc = "", documented = false, structField = true)
-  NestedSet<FileT> getTransitiveStaticLib();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveStaticLibForStarlark();
 
   @SkylarkCallable(name = "transitive_r_txt", doc = "", documented = false, structField = true)
-  NestedSet<FileT> getTransitiveRTxt();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveRTxtForStarlark();
 
   /** Provider for {@link AndroidResourcesInfoApi}. */
   @SkylarkModule(
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidSkylarkApiProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidSkylarkApiProviderApi.java
index 5c3bf0f..90969a0 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidSkylarkApiProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/AndroidSkylarkApiProviderApi.java
@@ -15,7 +15,6 @@
 
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.java.OutputJarApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
@@ -125,7 +124,7 @@
       structField = true,
       doc = "Returns resources defined by this target.",
       documented = false)
-  NestedSet<FileT> getResources();
+  SkylarkNestedSet /*<FileT>*/ getResources();
 
   @SkylarkCallable(
       name = "resource_jar",
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/DataBindingV2ProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/DataBindingV2ProviderApi.java
index ee3544c..aee7c21 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/DataBindingV2ProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/android/DataBindingV2ProviderApi.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.skylarkbuildapi.android;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -25,6 +24,7 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import javax.annotation.Nullable;
 
 /**
@@ -92,18 +92,18 @@
 
   /** Returns the BR files from this rule and its dependencies. */
   @SkylarkCallable(name = "transitive_br_files", structField = true, doc = "", documented = false)
-  NestedSet<T> getTransitiveBRFiles();
+  SkylarkNestedSet /*<T>*/ getTransitiveBRFilesForStarlark();
 
   /**
    * Returns a NestedSet containing the label and java package for this rule and its transitive
    * dependencies.
-   * */
+   */
   @SkylarkCallable(
       name = "transitive_label_and_java_packages",
       structField = true,
       doc = "",
       documented = false)
-  NestedSet<LabelJavaPackagePair> getTransitiveLabelAndJavaPackages();
+  SkylarkNestedSet /*<LabelJavaPackagePair>*/ getTransitiveLabelAndJavaPackagesForStarlark();
 
   /**
    * Returns the label and java package for this rule and any rules that this rule exports.
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/apple/ObjcProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/apple/ObjcProviderApi.java
index 1e023fc..308d022 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/apple/ObjcProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/apple/ObjcProviderApi.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.skylarkbuildapi.apple;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
@@ -34,12 +33,13 @@
 )
 public interface ObjcProviderApi<FileApiT extends FileApi> extends SkylarkValue {
 
-  @SkylarkCallable(name = "define",
+  @SkylarkCallable(
+      name = "define",
       structField = true,
-      doc = "A set of strings from 'defines' attributes. These are to be passed as '-D' flags to "
-          + "all invocations of the compiler for this target and all depending targets."
-  )
-  public NestedSet<String> define();
+      doc =
+          "A set of strings from 'defines' attributes. These are to be passed as '-D' flags to "
+              + "all invocations of the compiler for this target and all depending targets.")
+  public SkylarkNestedSet /*<String>*/ defineForStarlark();
 
   @SkylarkCallable(
       name = "dynamic_framework_file",
@@ -47,32 +47,33 @@
       doc =
           "The library files in .framework directories belonging to a dynamically linked "
               + "framework.")
-  public NestedSet<FileApiT> dynamicFrameworkFile();
+  public SkylarkNestedSet /*<FileApiT>*/ dynamicFrameworkFileForStarlark();
 
-  @SkylarkCallable(name = "exported_debug_artifacts",
+  @SkylarkCallable(
+      name = "exported_debug_artifacts",
       structField = true,
-      doc = "Debug files that should be exported by the top-level target."
-  )
-  public NestedSet<FileApiT> exportedDebugArtifacts();
+      doc = "Debug files that should be exported by the top-level target.")
+  public SkylarkNestedSet /*<FileApiT>*/ exportedDebugArtifacts();
 
-  @SkylarkCallable(name = "framework_search_path_only",
+  @SkylarkCallable(
+      name = "framework_search_path_only",
       structField = true,
-      doc = "Exec paths of .framework directories corresponding to frameworks to include "
-          + "in search paths, but not to link."
-  )
-  public SkylarkNestedSet frameworkSearchPathOnly();
+      doc =
+          "Exec paths of .framework directories corresponding to frameworks to include "
+              + "in search paths, but not to link.")
+  public SkylarkNestedSet /*<String>*/ frameworkSearchPathOnly();
 
-  @SkylarkCallable(name = "force_load_library",
+  @SkylarkCallable(
+      name = "force_load_library",
       structField = true,
-      doc = "Libraries to load with -force_load."
-  )
-  public NestedSet<FileApiT> forceLoadLibrary();
+      doc = "Libraries to load with -force_load.")
+  public SkylarkNestedSet /*<FileApiT>*/ forceLoadLibrary();
 
-  @SkylarkCallable(name = "header",
+  @SkylarkCallable(
+      name = "header",
       structField = true,
-      doc = "All header files. These may be either public or private headers."
-  )
-  public NestedSet<FileApiT> header();
+      doc = "All header files. These may be either public or private headers.")
+  public SkylarkNestedSet /*<FileApiT>*/ headerForStarlark();
 
   @SkylarkCallable(
       name = "direct_headers",
@@ -82,11 +83,11 @@
               + "These may be either public or private headers.")
   public Sequence<FileApiT> directHeaders();
 
-  @SkylarkCallable(name = "imported_library",
+  @SkylarkCallable(
+      name = "imported_library",
       structField = true,
-      doc = "Imported precompiled static libraries (.a files) to be linked into the binary."
-  )
-  public NestedSet<FileApiT> importedLibrary();
+      doc = "Imported precompiled static libraries (.a files) to be linked into the binary.")
+  public SkylarkNestedSet /*<FileApiT>*/ importedLibrary();
 
   @SkylarkCallable(name = "include",
       structField = true,
@@ -107,51 +108,50 @@
   )
   public SkylarkNestedSet iquote();
 
-  @SkylarkCallable(name = "j2objc_library",
+  @SkylarkCallable(
+      name = "j2objc_library",
       structField = true,
-      doc = "Static libraries that are built from J2ObjC-translated Java code."
-  )
-  public NestedSet<FileApiT> j2objcLibrary();
+      doc = "Static libraries that are built from J2ObjC-translated Java code.")
+  public SkylarkNestedSet /*<FileApiT>*/ j2objcLibrary();
 
-  @SkylarkCallable(name = "jre_library",
+  @SkylarkCallable(
+      name = "jre_library",
       structField = true,
-      doc = "J2ObjC JRE emulation libraries and their dependencies."
-  )
-  public NestedSet<FileApiT> jreLibrary();
+      doc = "J2ObjC JRE emulation libraries and their dependencies.")
+  public SkylarkNestedSet /*<FileApiT>*/ jreLibrary();
 
-  @SkylarkCallable(name = "library",
+  @SkylarkCallable(
+      name = "library",
       structField = true,
-      doc = "Library (.a) files compiled by dependencies of the current target."
-  )
-  public NestedSet<FileApiT> library();
+      doc = "Library (.a) files compiled by dependencies of the current target.")
+  public SkylarkNestedSet /*<FileApiT>*/ library();
 
-  @SkylarkCallable(name = "link_inputs",
+  @SkylarkCallable(
+      name = "link_inputs",
       structField = true,
-      doc = "Link time artifacts from dependencies that do not fall into any other category such "
-          + "as libraries or archives. This catch-all provides a way to add arbitrary data (e.g. "
-          + "Swift AST files) to the linker. The rule that adds these is also responsible to "
-          + "add the necessary linker flags to 'linkopt'."
-  )
-  public NestedSet<FileApiT> linkInputs();
+      doc =
+          "Link time artifacts from dependencies that do not fall into any other category such as"
+              + " libraries or archives. This catch-all provides a way to add arbitrary data (e.g."
+              + " Swift AST files) to the linker. The rule that adds these is also responsible to"
+              + " add the necessary linker flags to 'linkopt'.")
+  public SkylarkNestedSet /*<FileApiT>*/ linkInputs();
 
-  @SkylarkCallable(name = "linked_binary",
+  @SkylarkCallable(
+      name = "linked_binary",
       structField = true,
-      doc = "Single-architecture linked binaries to be combined for the final multi-architecture "
-          + "binary."
-  )
-  public NestedSet<FileApiT> linkedBinary();
+      doc =
+          "Single-architecture linked binaries to be combined for the final multi-architecture "
+              + "binary.")
+  public SkylarkNestedSet /*<FileApiT>*/ linkedBinary();
 
-  @SkylarkCallable(name = "linkmap_file",
+  @SkylarkCallable(
+      name = "linkmap_file",
       structField = true,
-      doc = "Single-architecture link map for a binary."
-  )
-  public NestedSet<FileApiT> linkmapFile();
+      doc = "Single-architecture link map for a binary.")
+  public SkylarkNestedSet /*<FileApiT>*/ linkmapFile();
 
-  @SkylarkCallable(name = "linkopt",
-      structField = true,
-      doc = "Linking options."
-  )
-  public NestedSet<String> linkopt();
+  @SkylarkCallable(name = "linkopt", structField = true, doc = "Linking options.")
+  public SkylarkNestedSet /*<String>*/ linkopt();
 
   @SkylarkCallable(
       name = "merge_zip",
@@ -160,13 +160,13 @@
           "Merge zips to include in the bundle. The entries of these zip files are included "
               + "in the final bundle with the same path. The entries in the merge zips should not "
               + "include the bundle root path (e.g. 'Foo.app').")
-  public NestedSet<FileApiT> mergeZip();
+  public SkylarkNestedSet /*<FileApiT>*/ mergeZip();
 
-  @SkylarkCallable(name = "module_map",
+  @SkylarkCallable(
+      name = "module_map",
       structField = true,
-      doc = "Clang module maps, used to enforce proper use of private header files."
-  )
-  public NestedSet<FileApiT> moduleMap();
+      doc = "Clang module maps, used to enforce proper use of private header files.")
+  public SkylarkNestedSet /*<FileApiT>*/ moduleMap();
 
   @SkylarkCallable(
       name = "direct_module_maps",
@@ -176,29 +176,29 @@
               + "Used to enforce proper use of private header files and for Swift compilation.")
   public Sequence<FileApiT> directModuleMaps();
 
-  @SkylarkCallable(name = "multi_arch_dynamic_libraries",
+  @SkylarkCallable(
+      name = "multi_arch_dynamic_libraries",
       structField = true,
-      doc = "Combined-architecture dynamic libraries to include in the final bundle."
-  )
-  public NestedSet<FileApiT> multiArchDynamicLibraries();
+      doc = "Combined-architecture dynamic libraries to include in the final bundle.")
+  public SkylarkNestedSet /*<FileApiT>*/ multiArchDynamicLibraries();
 
-  @SkylarkCallable(name = "multi_arch_linked_archives",
+  @SkylarkCallable(
+      name = "multi_arch_linked_archives",
       structField = true,
-      doc = "Combined-architecture archives to include in the final bundle."
-  )
-  public NestedSet<FileApiT> multiArchLinkedArchives();
+      doc = "Combined-architecture archives to include in the final bundle.")
+  public SkylarkNestedSet /*<FileApiT>*/ multiArchLinkedArchives();
 
-  @SkylarkCallable(name = "multi_arch_linked_binaries",
+  @SkylarkCallable(
+      name = "multi_arch_linked_binaries",
       structField = true,
-      doc = "Combined-architecture binaries to include in the final bundle."
-  )
-  public NestedSet<FileApiT> multiArchLinkedBinaries();
+      doc = "Combined-architecture binaries to include in the final bundle.")
+  public SkylarkNestedSet /*<FileApiT>*/ multiArchLinkedBinaries();
 
-  @SkylarkCallable(name = "sdk_dylib",
+  @SkylarkCallable(
+      name = "sdk_dylib",
       structField = true,
-      doc = "Names of SDK .dylib libraries to link with. For instance, 'libz' or 'libarchive'."
-  )
-  public NestedSet<String> sdkDylib();
+      doc = "Names of SDK .dylib libraries to link with. For instance, 'libz' or 'libarchive'.")
+  public SkylarkNestedSet /*<String>*/ sdkDylib();
 
   @SkylarkCallable(name = "sdk_framework",
       structField = true,
@@ -206,11 +206,8 @@
   )
   public SkylarkNestedSet sdkFramework();
 
-  @SkylarkCallable(name = "source",
-      structField = true,
-      doc = "All transitive source files."
-  )
-  public NestedSet<FileApiT> source();
+  @SkylarkCallable(name = "source", structField = true, doc = "All transitive source files.")
+  public SkylarkNestedSet /*<FileApiT>*/ sourceForStarlark();
 
   @SkylarkCallable(
       name = "direct_sources",
@@ -222,14 +219,15 @@
       name = "static_framework_file",
       structField = true,
       doc = "The library files in .framework directories that should be statically linked.")
-  public NestedSet<FileApiT> staticFrameworkFile();
+  public SkylarkNestedSet /*<FileApiT>*/ staticFrameworkFileForStarlark();
 
-  @SkylarkCallable(name = "umbrella_header",
+  @SkylarkCallable(
+      name = "umbrella_header",
       structField = true,
-      doc = "Clang umbrella header. Public headers are #included in umbrella headers to be "
-          + "compatible with J2ObjC segmented headers."
-  )
-  public NestedSet<FileApiT> umbrellaHeader();
+      doc =
+          "Clang umbrella header. Public headers are #included in umbrella headers to be "
+              + "compatible with J2ObjC segmented headers.")
+  public SkylarkNestedSet /*<FileApiT>*/ umbrellaHeader();
 
   @SkylarkCallable(
       name = "weak_sdk_framework",
@@ -244,23 +242,23 @@
       name = "dynamic_framework_names",
       structField = true,
       doc = "Returns all names of dynamic frameworks in this provider.")
-  public NestedSet<String> dynamicFrameworkNames();
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkNamesForStarlark();
 
   @SkylarkCallable(
       name = "dynamic_framework_paths",
       structField = true,
       doc = "Returns all framework paths to dynamic frameworks in this provider.")
-  public NestedSet<String> dynamicFrameworkPaths();
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkPathsForStarlark();
 
   @SkylarkCallable(
       name = "static_framework_names",
       structField = true,
       doc = "Returns all names of static frameworks in this provider.")
-  public NestedSet<String> staticFrameworkNames();
+  public SkylarkNestedSet /*<String>*/ staticFrameworkNamesForStarlark();
 
   @SkylarkCallable(
       name = "static_framework_paths",
       structField = true,
       doc = "Returns all framework paths to static frameworks in this provider.")
-  public NestedSet<String> staticFrameworkPaths();
+  public SkylarkNestedSet /*<String>*/ staticFrameworkPathsForStarlark();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/CcSkylarkApiProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/CcSkylarkApiProviderApi.java
index 3788c1b..13869ef 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/CcSkylarkApiProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/CcSkylarkApiProviderApi.java
@@ -15,12 +15,12 @@
 package com.google.devtools.build.lib.skylarkbuildapi.cpp;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** Object with information about C++ rules. Every C++-related target should provide this. */
 @SkylarkModule(
@@ -39,7 +39,7 @@
           "Returns a <a href=\"depset.html\">depset</a> of headers that have been declared in the "
               + " <code>src</code> or <code>headers</code> attribute"
               + "(possibly empty but never <code>None</code>).")
-  public NestedSet<FileT> getTransitiveHeaders();
+  public SkylarkNestedSet /*<FileT>*/ getTransitiveHeadersForStarlark();
 
   @SkylarkCallable(
       name = "libs",
@@ -49,7 +49,7 @@
               + "<code>FULLY STATIC</code> mode (<code>linkopts=[\"-static\"]</code>) or "
               + "<code>MOSTLY STATIC</code> mode (<code>linkstatic=1</code>) "
               + "(possibly empty but never <code>None</code>)")
-  public NestedSet<FileT> getLibraries();
+  public SkylarkNestedSet /*<FileT>*/ getLibrariesForStarlark();
 
   @SkylarkCallable(
       name = "link_flags",
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/GoWrapCcHelperApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/GoWrapCcHelperApi.java
index 37d4010..c67f048 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/GoWrapCcHelperApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp/GoWrapCcHelperApi.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.skylarkbuildapi.cpp;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.RunfilesApi;
 import com.google.devtools.build.lib.skylarkbuildapi.SkylarkRuleContextApi;
@@ -30,6 +29,7 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.NoneType;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Tuple;
 
 /**
@@ -213,6 +213,6 @@
             named = true,
             allowedTypes = {@ParamType(type = NoneType.class), @ParamType(type = FileApi.class)}),
       })
-  public NestedSet<FileT> getGopackageFiles(
+  public SkylarkNestedSet /*<FileT>*/ getGopackageFilesForStarlark(
       SkylarkRuleContextT skylarkRuleContext, FileT skylarkGopkg);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/GeneratedExtensionRegistryProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/GeneratedExtensionRegistryProviderApi.java
index e5ecec9..633f427 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/GeneratedExtensionRegistryProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/GeneratedExtensionRegistryProviderApi.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.skylarkbuildapi.java;
 
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -49,7 +48,7 @@
   FileT getSrcJar();
 
   @SkylarkCallable(name = "inputs", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getInputs();
+  SkylarkNestedSet /*<FileT>*/ getInputsForStarlark();
 
   /** The provider implementing this can construct the GeneratedExtensionRegistryProvider. */
   @SkylarkModule(name = "Provider", doc = "", documented = false)
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/JavaAnnotationProcessingApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/JavaAnnotationProcessingApi.java
index 6be778c..9317502 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/JavaAnnotationProcessingApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/JavaAnnotationProcessingApi.java
@@ -15,12 +15,12 @@
 package com.google.devtools.build.lib.skylarkbuildapi.java;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import javax.annotation.Nullable;
 
 /**
@@ -59,29 +59,26 @@
   public FileTypeT getGenSourceJar();
 
   @SkylarkCallable(
-    name = "transitive_class_jars",
-    structField = true,
-    doc =
-        "Returns a transitive set of class file jars resulting from annotation "
-            + "processing of this rule and its dependencies."
-  )
-  public NestedSet<FileTypeT> getTransitiveGenClassJars();
+      name = "transitive_class_jars",
+      structField = true,
+      doc =
+          "Returns a transitive set of class file jars resulting from annotation "
+              + "processing of this rule and its dependencies.")
+  public SkylarkNestedSet /*<FileTypeT>*/ getTransitiveGenClassJarsForStarlark();
 
   @SkylarkCallable(
-    name = "transitive_source_jars",
-    structField = true,
-    doc =
-        "Returns a transitive set of source archives resulting from annotation processing "
-            + "of this rule and its dependencies."
-  )
-  public NestedSet<FileTypeT> getTransitiveGenSourceJars();
+      name = "transitive_source_jars",
+      structField = true,
+      doc =
+          "Returns a transitive set of source archives resulting from annotation processing "
+              + "of this rule and its dependencies.")
+  public SkylarkNestedSet /*<FileTypeT>*/ getTransitiveGenSourceJarsForStarlark();
 
   @SkylarkCallable(
-    name = "processor_classpath",
-    structField = true,
-    doc = "Returns a classpath of annotation processors applied to this rule."
-  )
-  public NestedSet<FileTypeT> getProcessorClasspath();
+      name = "processor_classpath",
+      structField = true,
+      doc = "Returns a classpath of annotation processors applied to this rule.")
+  public SkylarkNestedSet /*<FileTypeT>*/ getProcessorClasspathForStarlark();
 
   @SkylarkCallable(
     name = "processor_classnames",
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/ProguardSpecProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/ProguardSpecProviderApi.java
index 4e20a0f..8985e03 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/ProguardSpecProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java/ProguardSpecProviderApi.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skylarkbuildapi.java;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.ProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
@@ -35,7 +34,7 @@
   public static final String NAME = "ProguardSpecProvider";
 
   @SkylarkCallable(name = "specs", structField = true, doc = "", documented = false)
-  NestedSet<FileT> getTransitiveProguardSpecs();
+  SkylarkNestedSet /*<FileT>*/ getTransitiveProguardSpecsForStarlark();
 
   /** The provider implementing this can construct the ProguardSpecProvider. */
   @SkylarkModule(name = "Provider", doc = "", documented = false)
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/proto/ProtoRegistryProviderApi.java b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/proto/ProtoRegistryProviderApi.java
index e65decf..9e30dd7 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/proto/ProtoRegistryProviderApi.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkbuildapi/proto/ProtoRegistryProviderApi.java
@@ -14,13 +14,13 @@
 
 package com.google.devtools.build.lib.skylarkbuildapi.proto;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.StructApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /** Provides information about flavors for all built protos. */
 @SkylarkModule(
@@ -30,7 +30,7 @@
 public interface ProtoRegistryProviderApi<FileT extends FileApi> extends StructApi {
 
   @SkylarkCallable(name = "jars", documented = false, doc = "", structField = true)
-  NestedSet<FileT> getJars();
+  SkylarkNestedSet /*<FileT>*/ getJars();
 
   @SkylarkCallable(name = "flavors", documented = false, doc = "", structField = true)
   Sequence<String> getFlavors();
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkinterface/processor/SkylarkCallableProcessor.java b/src/main/java/com/google/devtools/build/lib/skylarkinterface/processor/SkylarkCallableProcessor.java
index d7930e3..64bb882 100644
--- a/src/main/java/com/google/devtools/build/lib/skylarkinterface/processor/SkylarkCallableProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/skylarkinterface/processor/SkylarkCallableProcessor.java
@@ -37,8 +37,11 @@
 import javax.lang.model.element.VariableElement;
 import javax.lang.model.type.DeclaredType;
 import javax.lang.model.type.MirroredTypeException;
+import javax.lang.model.type.TypeKind;
 import javax.lang.model.type.TypeMirror;
 import javax.lang.model.type.WildcardType;
+import javax.lang.model.util.Elements;
+import javax.lang.model.util.Types;
 import javax.tools.Diagnostic;
 
 /**
@@ -74,6 +77,8 @@
  *   <li>A method annotated with selfCall=true must have a non-empty name.
  *   <li>A method annotated with selfCall=true must have structField=false.
  *   <li>The method's class must implement SkylarkValue.
+ *   <li>The class of the declared result type, if final, must be accepted by {@link
+ *       Starlark#fromJava}.
  * </ul>
  *
  * <p>These properties can be relied upon at runtime without additional checks.
@@ -84,7 +89,6 @@
   "com.google.devtools.build.lib.skylarkinterface.SkylarkModule"
 })
 public final class SkylarkCallableProcessor extends AbstractProcessor {
-  private ProcessingEnvironment env;
   private Messager messager;
 
   // A set containing the names of all classes which have a method with @SkylarkCallable.selfCall.
@@ -93,6 +97,9 @@
   // that class (where "method name" is @SkylarkCallable.name").
   private SetMultimap<String, String> processedClassMethods;
 
+  private Types types;
+  private Elements elements;
+
   private static final String SKYLARK_LIST = "com.google.devtools.build.lib.syntax.Sequence<?>";
   private static final String SKYLARK_DICT = "com.google.devtools.build.lib.syntax.Dict<?,?>";
   private static final String LOCATION = "com.google.devtools.build.lib.events.Location";
@@ -101,8 +108,6 @@
       "com.google.devtools.build.lib.syntax.StarlarkThread";
   private static final String STARLARK_SEMANTICS =
       "com.google.devtools.build.lib.syntax.StarlarkSemantics";
-  private static final String SKYLARK_VALUE =
-      "com.google.devtools.build.lib.skylarkinterface.SkylarkValue";
 
   @Override
   public SourceVersion getSupportedSourceVersion() {
@@ -112,22 +117,30 @@
   @Override
   public synchronized void init(ProcessingEnvironment env) {
     super.init(env);
-    this.env = env;
+    this.types = env.getTypeUtils();
+    this.elements = env.getElementUtils();
     messager = env.getMessager();
     classesWithSelfcall = new HashSet<>();
     processedClassMethods = LinkedHashMultimap.create();
   }
 
+  private TypeMirror getType(String name) {
+    return elements.getTypeElement(name).asType();
+  }
+
   @Override
   public boolean process(Set<? extends TypeElement> annotations, RoundEnvironment roundEnv) {
+    TypeMirror stringType = getType("java.lang.String");
+    TypeMirror integerType = getType("java.lang.Integer");
+    TypeMirror booleanType = getType("java.lang.Boolean");
+    TypeMirror listType = getType("java.util.List");
+    TypeMirror mapType = getType("java.util.Map");
+    TypeMirror skylarkValueType =
+        getType("com.google.devtools.build.lib.skylarkinterface.SkylarkValue");
+
     // Ensure SkylarkModule-annotated classes implement SkylarkValue.
-    TypeElement skylarkValueType = env.getElementUtils().getTypeElement(SKYLARK_VALUE);
-    if (skylarkValueType == null) {
-      messager.printMessage(Diagnostic.Kind.ERROR, "no SkylarkValue type in compilation unit");
-      return true;
-    }
     for (Element cls : roundEnv.getElementsAnnotatedWith(SkylarkModule.class)) {
-      if (!env.getTypeUtils().isAssignable(cls.asType(), skylarkValueType.asType())) {
+      if (!types.isAssignable(cls.asType(), skylarkValueType)) {
         error(
             cls,
             String.format(
@@ -175,11 +188,31 @@
         error(exception.methodElement, exception.errorMessage);
       }
 
+      // Verify that result type, if final, might satisfy Starlark.fromJava.
+      // (If the type is non-final we can't prove that all subclasses are invalid.)
+      TypeMirror ret = methodElement.getReturnType();
+      if (ret.getKind() == TypeKind.DECLARED) {
+        DeclaredType obj = (DeclaredType) ret;
+        if (obj.asElement().getModifiers().contains(Modifier.FINAL)
+            && !types.isSameType(ret, stringType)
+            && !types.isSameType(ret, integerType)
+            && !types.isSameType(ret, booleanType)
+            && !types.isAssignable(obj, skylarkValueType)
+            && !types.isAssignable(obj, listType)
+            && !types.isAssignable(obj, mapType)) {
+          error(
+              methodElement,
+              String.format(
+                  "@SkylarkCallable-annotated method %s returns %s, which has no legal Starlark"
+                      + " values (see Starlark.fromJava)",
+                  methodElement.getSimpleName(), ret));
+        }
+      }
+
       // Check that the method's class is SkylarkGlobalLibrary-annotated,
       // or implements SkylarkValue, or an error has already been reported.
       Element cls = methodElement.getEnclosingElement();
-      if (okClasses.add(cls)
-          && !env.getTypeUtils().isAssignable(cls.asType(), skylarkValueType.asType())) {
+      if (okClasses.add(cls) && !types.isAssignable(cls.asType(), skylarkValueType)) {
         error(
             cls,
             String.format(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodDescriptor.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodDescriptor.java
index c1414a2..978075d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodDescriptor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodDescriptor.java
@@ -17,14 +17,10 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import java.lang.reflect.InvocationTargetException;
 import java.lang.reflect.Method;
-import java.lang.reflect.ParameterizedType;
-import java.lang.reflect.Type;
-import java.lang.reflect.WildcardType;
 import java.util.Arrays;
 
 /**
@@ -165,38 +161,10 @@
       }
     }
 
-    // TODO(adonovan): eliminate this hack.
-    // There are about a dozen methods that return NestedSet directly.
-    if (result instanceof NestedSet<?>) {
-      return SkylarkNestedSet.of(resultType(), (NestedSet<?>) result);
-    }
-
     // Careful: thread may be null when we are called by invokeStructField.
     return Starlark.fromJava(result, thread != null ? thread.mutability() : null);
   }
 
-  // legacy hack for NestedSet
-  private SkylarkType resultType() {
-    // This is where we can infer generic type information, so SkylarkNestedSets can be
-    // created in a safe way. Eventually we should probably do something with Lists and Maps too.
-    ParameterizedType t = (ParameterizedType) method.getGenericReturnType();
-    Type type = t.getActualTypeArguments()[0];
-    if (type instanceof Class) {
-      return SkylarkType.of((Class<?>) type);
-    }
-    if (type instanceof WildcardType) {
-      WildcardType wildcard = (WildcardType) type;
-      Type upperBound = wildcard.getUpperBounds()[0];
-      if (upperBound instanceof Class) {
-        // i.e. List<? extends SuperClass>
-        return SkylarkType.of((Class<?>) upperBound);
-      }
-    }
-    // It means someone annotated a method with @SkylarkCallable with no specific generic type info.
-    // We shouldn't annotate methods which return List<?> or List<T>.
-    throw new IllegalStateException("Cannot infer type from method signature " + method);
-  }
-
   /** @see SkylarkCallable#name() */
   public String getName() {
     return name;
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidNativeLibsInfo.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidNativeLibsInfo.java
index c93e0a4..539f495 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidNativeLibsInfo.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidNativeLibsInfo.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.skydoc.fakebuildapi.android;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidNativeLibsInfoApi;
@@ -28,7 +27,7 @@
 public class FakeAndroidNativeLibsInfo implements AndroidNativeLibsInfoApi<FileApi> {
 
   @Override
-  public NestedSet<FileApi> getNativeLibs() {
+  public SkylarkNestedSet /*<FileApi>*/ getNativeLibsForStarlark() {
     return null;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidResourcesInfo.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidResourcesInfo.java
index 87d706c..3e974a9 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidResourcesInfo.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/android/FakeAndroidResourcesInfo.java
@@ -15,7 +15,6 @@
 package com.google.devtools.build.skydoc.fakebuildapi.android;
 
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidManifestInfoApi;
@@ -53,52 +52,53 @@
   }
 
   @Override
-  public NestedSet<FakeValidatedAndroidDataApi> getTransitiveAndroidResources() {
+  public SkylarkNestedSet /*<FakeValidatedAndroidDataApi>*/
+      getTransitiveAndroidResourcesForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FakeValidatedAndroidDataApi> getDirectAndroidResources() {
+  public SkylarkNestedSet /*<FakeValidatedAndroidDataApi>*/ getDirectAndroidResourcesForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveResources() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveResourcesForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveManifests() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveManifestsForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveAapt2RTxt() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveAapt2RTxtForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveAapt2ValidationArtifacts() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveAapt2ValidationArtifactsForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveSymbolsBin() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveSymbolsBinForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveCompiledSymbols() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveCompiledSymbolsForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveStaticLib() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveStaticLibForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> getTransitiveRTxt() {
+  public SkylarkNestedSet /*<FileApi>*/ getTransitiveRTxtForStarlark() {
     return null;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/apple/FakeObjcProvider.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/apple/FakeObjcProvider.java
index 1a5f330..d463ed2 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/apple/FakeObjcProvider.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/apple/FakeObjcProvider.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.skydoc.fakebuildapi.apple;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.apple.ObjcProviderApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
@@ -27,17 +26,17 @@
 public class FakeObjcProvider implements ObjcProviderApi<FileApi> {
 
   @Override
-  public NestedSet<String> define() {
+  public SkylarkNestedSet /*<String>*/ defineForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> dynamicFrameworkFile() {
+  public SkylarkNestedSet /*<FileApi>*/ dynamicFrameworkFileForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> exportedDebugArtifacts() {
+  public SkylarkNestedSet /*<FileApi>*/ exportedDebugArtifacts() {
     return null;
   }
 
@@ -47,12 +46,12 @@
   }
 
   @Override
-  public NestedSet<FileApi> forceLoadLibrary() {
+  public SkylarkNestedSet /*<FileApi>*/ forceLoadLibrary() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> header() {
+  public SkylarkNestedSet /*<FileApi>*/ headerForStarlark() {
     return null;
   }
 
@@ -62,7 +61,7 @@
   }
 
   @Override
-  public NestedSet<FileApi> importedLibrary() {
+  public SkylarkNestedSet /*<FileApi>*/ importedLibrary() {
     return null;
   }
 
@@ -82,47 +81,47 @@
   }
 
   @Override
-  public NestedSet<FileApi> j2objcLibrary() {
+  public SkylarkNestedSet /*<FileApi>*/ j2objcLibrary() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> jreLibrary() {
+  public SkylarkNestedSet /*<FileApi>*/ jreLibrary() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> library() {
+  public SkylarkNestedSet /*<FileApi>*/ library() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> linkInputs() {
+  public SkylarkNestedSet /*<FileApi>*/ linkInputs() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> linkedBinary() {
+  public SkylarkNestedSet /*<FileApi>*/ linkedBinary() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> linkmapFile() {
+  public SkylarkNestedSet /*<FileApi>*/ linkmapFile() {
     return null;
   }
 
   @Override
-  public NestedSet<String> linkopt() {
+  public SkylarkNestedSet /*<String>*/ linkopt() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> mergeZip() {
+  public SkylarkNestedSet /*<FileApi>*/ mergeZip() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> moduleMap() {
+  public SkylarkNestedSet /*<FileApi>*/ moduleMap() {
     return null;
   }
 
@@ -132,22 +131,22 @@
   }
 
   @Override
-  public NestedSet<FileApi> multiArchDynamicLibraries() {
+  public SkylarkNestedSet /*<FileApi>*/ multiArchDynamicLibraries() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> multiArchLinkedArchives() {
+  public SkylarkNestedSet /*<FileApi>*/ multiArchLinkedArchives() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> multiArchLinkedBinaries() {
+  public SkylarkNestedSet /*<FileApi>*/ multiArchLinkedBinaries() {
     return null;
   }
 
   @Override
-  public NestedSet<String> sdkDylib() {
+  public SkylarkNestedSet /*<String>*/ sdkDylib() {
     return null;
   }
 
@@ -157,7 +156,7 @@
   }
 
   @Override
-  public NestedSet<FileApi> source() {
+  public SkylarkNestedSet /*<FileApi>*/ sourceForStarlark() {
     return null;
   }
 
@@ -167,12 +166,12 @@
   }
 
   @Override
-  public NestedSet<FileApi> staticFrameworkFile() {
+  public SkylarkNestedSet /*<FileApi>*/ staticFrameworkFileForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<FileApi> umbrellaHeader() {
+  public SkylarkNestedSet /*<FileApi>*/ umbrellaHeader() {
     return null;
   }
 
@@ -182,22 +181,22 @@
   }
 
   @Override
-  public NestedSet<String> dynamicFrameworkNames() {
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkNamesForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<String> dynamicFrameworkPaths() {
+  public SkylarkNestedSet /*<String>*/ dynamicFrameworkPathsForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<String> staticFrameworkNames() {
+  public SkylarkNestedSet /*<String>*/ staticFrameworkNamesForStarlark() {
     return null;
   }
 
   @Override
-  public NestedSet<String> staticFrameworkPaths() {
+  public SkylarkNestedSet /*<String>*/ staticFrameworkPathsForStarlark() {
     return null;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
index f12e540..4a297ef 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
@@ -112,7 +112,7 @@
 
   @Override
   public CcToolchainVariablesApi getCompileBuildVariables(
-      CcToolchainProviderApi ccToolchainProvider,
+      CcToolchainProviderApi<FeatureConfigurationApi> ccToolchainProvider,
       FeatureConfigurationApi featureConfiguration,
       Object sourceFile,
       Object outputFile,
@@ -129,12 +129,21 @@
   }
 
   @Override
-  public CcToolchainVariablesApi getLinkBuildVariables(CcToolchainProviderApi ccToolchainProvider,
-      FeatureConfigurationApi featureConfiguration, Object librarySearchDirectories,
-      Object runtimeLibrarySearchDirectories, Object userLinkFlags, Object outputFile,
-      Object paramFile, Object defFile, boolean isUsingLinkerNotArchiver,
-      boolean isCreatingSharedLibrary, boolean mustKeepDebug, boolean useTestOnlyFlags,
-      boolean isStaticLinkingMode) throws EvalException {
+  public CcToolchainVariablesApi getLinkBuildVariables(
+      CcToolchainProviderApi<FeatureConfigurationApi> ccToolchainProvider,
+      FeatureConfigurationApi featureConfiguration,
+      Object librarySearchDirectories,
+      Object runtimeLibrarySearchDirectories,
+      Object userLinkFlags,
+      Object outputFile,
+      Object paramFile,
+      Object defFile,
+      boolean isUsingLinkerNotArchiver,
+      boolean isCreatingSharedLibrary,
+      boolean mustKeepDebug,
+      boolean useTestOnlyFlags,
+      boolean isStaticLinkingMode)
+      throws EvalException {
     return null;
   }
 
@@ -144,7 +153,7 @@
   }
 
   @Override
-  public LibraryToLinkApi createLibraryLinkerInput(
+  public LibraryToLinkApi<FileApi> createLibraryLinkerInput(
       Object actions,
       Object featureConfiguration,
       Object ccToolchainProvider,
@@ -170,7 +179,7 @@
   }
 
   @Override
-  public CcLinkingContextApi createCcLinkingInfo(
+  public CcLinkingContextApi<FileApi> createCcLinkingInfo(
       Object linkerInputs,
       Object librariesToLinkObject,
       Object userLinkFlagsObject,
@@ -199,7 +208,8 @@
   }
 
   @Override
-  public String legacyCcFlagsMakeVariable(CcToolchainProviderApi ccToolchain) {
+  public String legacyCcFlagsMakeVariable(
+      CcToolchainProviderApi<FeatureConfigurationApi> ccToolchain) {
     return "";
   }
 
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeGoWrapCcHelper.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeGoWrapCcHelper.java
index 422c0dd..9e03434 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeGoWrapCcHelper.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeGoWrapCcHelper.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.skydoc.fakebuildapi.cpp;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkbuildapi.RunfilesApi;
 import com.google.devtools.build.lib.skylarkbuildapi.SkylarkRuleContextApi;
@@ -113,7 +112,7 @@
   }
 
   @Override
-  public NestedSet<FileApi> getGopackageFiles(
+  public SkylarkNestedSet /*<FileApi>*/ getGopackageFilesForStarlark(
       SkylarkRuleContextApi skylarkRuleContext, FileApi skylarkGopkg) {
     return null;
   }