diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
index 037f47b..44a79f9 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContext.java
@@ -69,6 +69,7 @@
   @Nullable private final Environment env;
 
   @Nullable private final FileSystem actionFileSystem;
+  @Nullable private final Object skyframeDepsResult;
 
   @Nullable private ImmutableList<FilesetOutputSymlink> outputSymlinks;
 
@@ -85,7 +86,8 @@
       ImmutableMap<PathFragment, ImmutableList<FilesetOutputSymlink>> inputFilesetMappings,
       @Nullable ArtifactExpander artifactExpander,
       @Nullable SkyFunction.Environment env,
-      @Nullable FileSystem actionFileSystem) {
+      @Nullable FileSystem actionFileSystem,
+      @Nullable Object skyframeDepsResult) {
     this.actionInputFileCache = actionInputFileCache;
     this.actionInputPrefetcher = actionInputPrefetcher;
     this.actionKeyContext = actionKeyContext;
@@ -97,6 +99,7 @@
     this.artifactExpander = artifactExpander;
     this.env = env;
     this.actionFileSystem = actionFileSystem;
+    this.skyframeDepsResult = skyframeDepsResult;
     this.pathResolver = ArtifactPathResolver.createPathResolver(actionFileSystem,
         // executor is only ever null in testing.
         executor == null ? null : executor.getExecRoot());
@@ -112,7 +115,8 @@
       Map<String, String> clientEnv,
       ImmutableMap<PathFragment, ImmutableList<FilesetOutputSymlink>> inputFilesetMappings,
       ArtifactExpander artifactExpander,
-      @Nullable FileSystem actionFileSystem) {
+      @Nullable FileSystem actionFileSystem,
+      @Nullable Object skyframeDepsResult) {
     this(
         executor,
         actionInputFileCache,
@@ -124,7 +128,8 @@
         inputFilesetMappings,
         artifactExpander,
         /*env=*/ null,
-        actionFileSystem);
+        actionFileSystem,
+        skyframeDepsResult);
   }
 
   public static ActionExecutionContext forInputDiscovery(
@@ -148,7 +153,8 @@
         ImmutableMap.of(),
         /*artifactExpander=*/ null,
         env,
-        actionFileSystem);
+        actionFileSystem,
+        /*skyframeDepsResult=*/ null);
   }
 
   public ActionInputPrefetcher getActionInputPrefetcher() {
@@ -278,6 +284,11 @@
     return artifactExpander;
   }
 
+  @Nullable
+  public Object getSkyframeDepsResult() {
+    return skyframeDepsResult;
+  }
+
   /**
    * Provide that {@code FileOutErr} that the action should use for redirecting the output and error
    * stream.
@@ -318,6 +329,7 @@
         inputFilesetMappings,
         artifactExpander,
         env,
-        actionFileSystem);
+        actionFileSystem,
+        skyframeDepsResult);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
index 75907d4..e7cbe12 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
@@ -16,7 +16,6 @@
 import com.google.auto.value.AutoValue;
 import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.base.Optional;
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
@@ -280,14 +279,14 @@
   Optional<DirectTraversal> getDirectTraversal();
 
   /**
-   * Returns the parameters of the nested traversal request, if any.
+   * Returns the Fileset Artifact of the nested traversal request, if any.
    *
    * <p>A nested traversal is the traversal of another Fileset referenced by FilesetEntry.srcdir.
    *
-   * <p>The value is non-empty when {@link #getDirectTraversal} is absent AND the nested Fileset has
-   * non-empty FilesetEntries.
+   * <p>The value is null when {@link #getDirectTraversal} is absent.
    */
-  ImmutableList<FilesetTraversalParams> getNestedTraversal();
+  @Nullable
+  Artifact getNestedArtifact();
 
   /** Adds the fingerprint of this traversal object. */
   void fingerprint(Fingerprint fp);
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
index f9585f3..6fd7cfa 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
@@ -17,9 +17,7 @@
 import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedSet;
-import com.google.common.collect.Iterables;
 import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.DirectTraversalRoot;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
@@ -110,13 +108,11 @@
   }
 
   /**
-   * Creates traversal request parameters for a FilesetEntry wrapping another Fileset. If possible,
-   * the original {@code nested} is returned to avoid unnecessary object creation. In that case, the
-   * {@code ownerLabelForErrorMessages} may be ignored. Since the wrapping traversal could not have
-   * an error on its own, any error messages printed will still be correct.
+   * Creates traversal request parameters for a FilesetEntry wrapping another Fileset.
    *
    * @param ownerLabel the rule that created this object
-   * @param nested the list of traversal params that were used for the nested (inner) Fileset
+   * @param artifact the Fileset Artifact of traversal params that were used for the nested (inner)
+   *     Fileset
    * @param destPath path in the Fileset's output directory that will be the root of files coming
    *     from the nested Fileset
    * @param excludes optional; set of files directly below (not in a subdirectory of) the nested
@@ -124,16 +120,11 @@
    */
   public static FilesetTraversalParams nestedTraversal(
       Label ownerLabel,
-      ImmutableList<FilesetTraversalParams> nested,
+      Artifact artifact,
       PathFragment destPath,
       @Nullable Set<String> excludes) {
-    if (nested.size() == 1 && destPath.isEmpty() && (excludes == null || excludes.isEmpty())) {
-      // Wrapping the traversal here would not lead to a different result: the output location is
-      // the same and there are no additional excludes.
-      return Iterables.getOnlyElement(nested);
-    }
     // When srcdir is another Fileset, then files must be null so strip_prefix must also be null.
-    return NestedTraversalParams.getNestedTraversal(ownerLabel, nested, destPath, excludes);
+    return NestedTraversalParams.getNestedTraversal(ownerLabel, artifact, destPath, excludes);
   }
 
   private static ImmutableSortedSet<String> getOrderedExcludes(@Nullable Set<String> excludes) {
@@ -147,8 +138,8 @@
   @AutoValue
   abstract static class DirectoryTraversalParams implements FilesetTraversalParams {
     @Override
-    public ImmutableList<FilesetTraversalParams> getNestedTraversal() {
-      return ImmutableList.of();
+    public Artifact getNestedArtifact() {
+      return null;
     }
 
     @Memoized
@@ -218,7 +209,7 @@
       if (!getExcludedFiles().isEmpty()) {
         fp.addStrings(getExcludedFiles());
       }
-      getNestedTraversal().forEach(nestedTraversal -> nestedTraversal.fingerprint(fp));
+      fp.addPath(getNestedArtifact().getExecPath());
       return fp.digestAndReset();
     }
 
@@ -229,10 +220,10 @@
 
     static NestedTraversalParams getNestedTraversal(
         Label ownerLabel,
-        ImmutableList<FilesetTraversalParams> nested,
+        Artifact nestedArtifact,
         PathFragment destPath,
         @Nullable Set<String> excludes) {
-      return create(ownerLabel, destPath, getOrderedExcludes(excludes), nested);
+      return create(ownerLabel, destPath, getOrderedExcludes(excludes), nestedArtifact);
     }
 
     @AutoCodec.VisibleForSerialization
@@ -241,9 +232,9 @@
         Label ownerLabelForErrorMessages,
         PathFragment destPath,
         ImmutableSortedSet<String> excludedFiles,
-        ImmutableList<FilesetTraversalParams> nestedTraversal) {
+        Artifact nestedArtifact) {
       return new AutoValue_FilesetTraversalParamsFactory_NestedTraversalParams(
-          ownerLabelForErrorMessages, destPath, excludedFiles, nestedTraversal);
+          ownerLabelForErrorMessages, destPath, excludedFiles, nestedArtifact);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index 30861cd..dbce56b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -31,11 +31,9 @@
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 import com.google.devtools.build.lib.analysis.configuredtargets.EnvironmentGroupConfiguredTarget;
-import com.google.devtools.build.lib.analysis.configuredtargets.FilesetOutputConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.InputFileConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.OutputFileConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.PackageGroupConfiguredTarget;
-import com.google.devtools.build.lib.analysis.fileset.FilesetProvider;
 import com.google.devtools.build.lib.analysis.skylark.SkylarkRuleConfiguredTargetUtil;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -232,16 +230,7 @@
       }
       TransitiveInfoCollection rule = targetContext.findDirectPrerequisite(
           outputFile.getGeneratingRule().getLabel(), config);
-      if (isFileset) {
-        return new FilesetOutputConfiguredTarget(
-            targetContext,
-            outputFile,
-            rule,
-            artifact,
-            rule.getProvider(FilesetProvider.class).getTraversals());
-      } else {
         return new OutputFileConfiguredTarget(targetContext, outputFile, rule, artifact);
-      }
     } else if (target instanceof InputFile) {
       InputFile inputFile = (InputFile) target;
       SourceArtifact artifact =
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 3eebb2d..0cccfb8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -55,7 +55,6 @@
 import com.google.devtools.build.lib.analysis.config.transitions.SplitTransition;
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.analysis.constraints.ConstraintSemantics;
-import com.google.devtools.build.lib.analysis.fileset.FilesetProvider;
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
 import com.google.devtools.build.lib.analysis.stringtemplate.TemplateContext;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -1555,9 +1554,12 @@
     }
 
     private boolean validateFilesetEntry(FilesetEntry filesetEntry, ConfiguredTargetAndData src) {
-      if (src.getConfiguredTarget().getProvider(FilesetProvider.class) != null) {
+      NestedSet<Artifact> filesToBuild =
+          src.getConfiguredTarget().getProvider(FileProvider.class).getFilesToBuild();
+      if (filesToBuild.isSingleton() && Iterables.getOnlyElement(filesToBuild).isFileset()) {
         return true;
       }
+
       if (filesetEntry.isSourceFileset()) {
         return true;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
index 2fec10f..cd959fa 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMap;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMapBuilder;
 import com.google.devtools.build.lib.analysis.VisibilityProvider;
-import com.google.devtools.build.lib.analysis.fileset.FilesetProvider;
 import com.google.devtools.build.lib.analysis.test.InstrumentedFilesProvider;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -62,9 +61,6 @@
             .put(LicensesProvider.class, this)
             .add(fileProvider)
             .add(filesToRunProvider);
-    if (this instanceof FilesetProvider) {
-      builder.put(FilesetProvider.class, this);
-    }
     if (this instanceof InstrumentedFilesProvider) {
       builder.put(InstrumentedFilesProvider.class, this);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FilesetOutputConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FilesetOutputConfiguredTarget.java
deleted file mode 100644
index 08dc1ac..0000000
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FilesetOutputConfiguredTarget.java
+++ /dev/null
@@ -1,84 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.devtools.build.lib.analysis.configuredtargets;
-
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.FilesetTraversalParams;
-import com.google.devtools.build.lib.analysis.TargetContext;
-import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
-import com.google.devtools.build.lib.analysis.fileset.FilesetProvider;
-import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.packages.OutputFile;
-import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
-import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-
-/**
- * A configured target for output files generated by {@code Fileset} rules. They are almost the same
- * thing as output files except that they implement {@link FilesetProvider} so that {@code Fileset}
- * can figure out the link tree behind them.
- *
- * <p>In an ideal world, this would not be needed: Filesets would depend on other Filesets and not
- * their output directories. However, sometimes a Fileset depends on the output directory of another
- * Fileset. Thus, we need this hack.
- */
-@AutoCodec
-public final class FilesetOutputConfiguredTarget extends OutputFileConfiguredTarget
-    implements FilesetProvider {
-  private final ImmutableList<FilesetTraversalParams> filesetTraversals;
-
-  public FilesetOutputConfiguredTarget(
-      TargetContext targetContext,
-      OutputFile outputFile,
-      TransitiveInfoCollection generatingRule,
-      Artifact outputArtifact,
-      ImmutableList<FilesetTraversalParams> traversals) {
-    this(
-        targetContext.getLabel(),
-        targetContext.getConfigurationKey(),
-        targetContext.getVisibility(),
-        generatingRule,
-        outputArtifact,
-        traversals);
-    Preconditions.checkState(
-        outputFile.getLabel().equals(targetContext.getLabel()),
-        "mismatch: %s %s",
-        outputFile,
-        targetContext);
-  }
-
-  @AutoCodec.VisibleForSerialization
-  @AutoCodec.Instantiator
-  FilesetOutputConfiguredTarget(
-      Label label,
-      BuildConfigurationValue.Key configurationKey,
-      NestedSet<PackageGroupContents> visibility,
-      TransitiveInfoCollection generatingRule,
-      Artifact artifact,
-      ImmutableList<FilesetTraversalParams> traversals) {
-    super(label, configurationKey, visibility, artifact, generatingRule);
-    FilesetProvider provider = generatingRule.getProvider(FilesetProvider.class);
-    Preconditions.checkArgument(provider != null);
-    filesetTraversals = traversals;
-  }
-
-  @Override
-  public ImmutableList<FilesetTraversalParams> getTraversals() {
-    return filesetTraversals;
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/fileset/FilesetProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/fileset/FilesetProvider.java
deleted file mode 100644
index 225a40e..0000000
--- a/src/main/java/com/google/devtools/build/lib/analysis/fileset/FilesetProvider.java
+++ /dev/null
@@ -1,30 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.devtools.build.lib.analysis.fileset;
-
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.actions.FilesetTraversalParams;
-import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
-
-/**
- * Information needed by a Fileset to do the right thing when it depends on another Fileset.
- */
-public interface FilesetProvider extends TransitiveInfoProvider {
-  /**
-   * Returns a list of the traversals that went into this Fileset. Only used by Skyframe-native
-   * filesets, so will be null if Skyframe-native filesets are not enabled.
-   */
-  ImmutableList<FilesetTraversalParams> getTraversals();
-}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index 7bff8b0..0905cf1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -187,8 +187,9 @@
       return null;
     }
 
+    Object skyframeDepsResult;
     try {
-      establishSkyframeDependencies(env, action);
+      skyframeDepsResult = establishSkyframeDependencies(env, action);
     } catch (ActionExecutionException e) {
       throw new ActionExecutionFunctionException(e);
     }
@@ -213,7 +214,8 @@
     try {
       result =
           checkCacheAndExecuteIfNeeded(
-              action, state, env, clientEnv, actionLookupData, sharedActionAlreadyRan);
+              action, state, env, clientEnv, actionLookupData, sharedActionAlreadyRan,
+              skyframeDepsResult);
     } catch (ActionExecutionException e) {
       // Remove action from state map in case it's there (won't be unless it discovers inputs).
       stateMap.remove(action);
@@ -363,7 +365,8 @@
       Environment env,
       Map<String, String> clientEnv,
       ActionLookupData actionLookupData,
-      boolean sharedActionAlreadyRan)
+      boolean sharedActionAlreadyRan,
+      Object skyframeDepsResult)
       throws ActionExecutionException, InterruptedException {
     // If this is a shared action and the other action is the one that executed, we must use that
     // other action's value, provided here, since it is populated with metadata for the outputs.
@@ -496,7 +499,8 @@
             metadataHandler,
             Collections.unmodifiableMap(state.expandedArtifacts),
             filesets,
-            state.actionFileSystem)) {
+            state.actionFileSystem,
+            skyframeDepsResult)) {
       if (!state.hasExecutedAction()) {
         state.value =
             skyframeActionExecutor.executeAction(
@@ -597,7 +601,7 @@
     }
   }
 
-  private static void establishSkyframeDependencies(Environment env, Action action)
+  private static Object establishSkyframeDependencies(Environment env, Action action)
       throws ActionExecutionException, InterruptedException {
     // Before we may safely establish Skyframe dependencies, we must build all action inputs by
     // requesting their ArtifactValues.
@@ -614,11 +618,12 @@
       Preconditions.checkState(action.executeUnconditionally(), action);
 
       try {
-        ((SkyframeAwareAction) action).establishSkyframeDependencies(env);
+        return ((SkyframeAwareAction) action).establishSkyframeDependencies(env);
       } catch (SkyframeAwareAction.ExceptionBase e) {
         throw new ActionExecutionException(e, action, false);
       }
     }
+    return null;
   }
 
   private static Iterable<SkyKey> toKeys(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
index 22f5b31..aa155b1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
@@ -51,10 +51,95 @@
   public SkyValue compute(SkyKey key, Environment env)
       throws FilesetEntryFunctionException, InterruptedException {
     FilesetTraversalParams t = (FilesetTraversalParams) key.argument();
-    if (t.getDirectTraversal().isPresent()) {
-      Preconditions.checkState(
-          t.getNestedTraversal().isEmpty(),
-          "NestedTraversal must be empty if directTraversal is present: %s", t);
+    Preconditions.checkState(
+        t.getDirectTraversal().isPresent() && t.getNestedArtifact() == null,
+        "FilesetEntry does not support nested traversal: %s", t);
+
+    // The map of output symlinks. Each key is the path of a output symlink that the Fileset must
+    // create, relative to the Fileset.out directory, and each value specifies extra information
+    // about the link (its target, associated metadata and again its name).
+    Map<PathFragment, FilesetOutputSymlink> outputSymlinks = new LinkedHashMap<>();
+
+    // The "direct" traversal params are present, which is the case when the FilesetEntry
+    // specifies a package's BUILD file, a directory or a list of files.
+
+    // The root of the direct traversal is defined as follows.
+    //
+    // If FilesetEntry.files is specified, then a TraversalRequest is created for each entry, the
+    // root being the respective entry itself. These are all traversed for they may be
+    // directories or symlinks to directories, and we need to establish Skyframe dependencies on
+    // their contents for incremental correctness. If an entry is indeed a directory (but not when
+    // it's a symlink to one) then we have to create symlinks to each of their childen.
+    // (NB: there seems to be no good reason for this, it's just how legacy Fileset works. We may
+    // want to consider creating a symlink just for the directory and not for its child elements.)
+    //
+    // If FilesetEntry.files is not specified, then srcdir refers to either a BUILD file or a
+    // directory. For the former, the root will be the parent of the BUILD file. For the latter,
+    // the root will be srcdir itself.
+    DirectTraversal direct = t.getDirectTraversal().get();
+
+    RecursiveFilesystemTraversalValue rftv;
+    try {
+      // Traverse the filesystem to establish skyframe dependencies.
+      rftv = traverse(env, createErrorInfo(t), direct);
+    } catch (MissingDepException e) {
+      return null;
+    }
+
+    // The root can only be absent for the EMPTY rftv instance.
+    if (!rftv.getResolvedRoot().isPresent()) {
+      return FilesetEntryValue.EMPTY;
+    }
+
+    ResolvedFile resolvedRoot = rftv.getResolvedRoot().get();
+
+    // Handle dangling symlinks gracefully be returning empty results.
+    if (!resolvedRoot.getType().exists()) {
+      return FilesetEntryValue.EMPTY;
+    }
+
+    // The prefix to remove is the entire path of the root. This is OK:
+    // - when the root is a file, this removes the entire path, but the traversal's destination
+    //   path is actually the name of the output symlink, so this works out correctly
+    // - when the root is a directory or a symlink to one then we need to strip off the
+    //   directory's path from every result (this is how the output symlinks must be created)
+    //   before making them relative to the destination path
+    PathFragment prefixToRemove = direct.getRoot().getRelativePart();
+
+    Iterable<ResolvedFile> results = null;
+
+    if (direct.isRecursive()
+        || (resolvedRoot.getType().isDirectory() && !resolvedRoot.getType().isSymlink())) {
+      // The traversal is recursive (requested for an entire FilesetEntry.srcdir) or it was
+      // requested for a FilesetEntry.files entry which turned out to be a directory. We need to
+      // create an output symlink for every file in it and all of its subdirectories. Only
+      // exception is when the subdirectory is really a symlink to a directory -- no output
+      // shall be created for the contents of those.
+      // Now we create Dir objects to model the filesystem tree. The object employs a trick to
+      // find directory symlinks: directory symlinks have corresponding ResolvedFile entries and
+      // are added as files too, while their children, also added as files, contain the path of
+      // the parent. Finding and discarding the children is easy if we traverse the tree from
+      // root to leaf.
+      DirectoryTree root = new DirectoryTree();
+      for (ResolvedFile f : rftv.getTransitiveFiles().toCollection()) {
+        PathFragment path = f.getNameInSymlinkTree().relativeTo(prefixToRemove);
+        if (!path.isEmpty()) {
+          path = t.getDestPath().getRelative(path);
+          DirectoryTree dir = root;
+          for (int i = 0; i < path.segmentCount() - 1; ++i) {
+            dir = dir.addOrGetSubdir(path.getSegment(i));
+          }
+          dir.maybeAddFile(f);
+        }
+      }
+      // Here's where the magic happens. The returned iterable will yield all files in the
+      // directory that are not under symlinked directories, as well as all directory symlinks.
+      results = root.iterateFiles();
+    } else {
+      // If we're on this branch then the traversal was done for just one entry in
+      // FilesetEntry.files (which was not a directory, so it was either a file, a symlink to one
+      // or a symlink to a directory), meaning we'll have only one output symlink.
+      results = ImmutableList.of(resolvedRoot);
     }
 
     // Create the set of excluded files. Only top-level files can be excluded, i.e. ones that are
@@ -62,140 +147,33 @@
     Set<String> exclusions =
         Sets.filter(t.getExcludedFiles(), e -> PathFragment.create(e).segmentCount() == 1);
 
-    // The map of output symlinks. Each key is the path of a output symlink that the Fileset must
-    // create, relative to the Fileset.out directory, and each value specifies extra information
-    // about the link (its target, associated metadata and again its name).
-    Map<PathFragment, FilesetOutputSymlink> outputSymlinks = new LinkedHashMap<>();
+    // Create one output symlink for each entry in the results.
+    for (ResolvedFile f : results) {
+      // The linkName has to be under the traversal's root, which is also the prefix to remove.
+      PathFragment linkName = f.getNameInSymlinkTree().relativeTo(prefixToRemove);
 
-    if (!t.getDirectTraversal().isPresent()) {
-      // The absence of "direct" traversal indicates the presence of a "nested" fileset and
-      // getNestedTraversal will return the list FilesetTraversalParams corresponding to each
-      // FilesetEntry of the nested Fileset.
-      ImmutableList<SkyKey> nestedKeys = FilesetEntryKey.keys(t.getNestedTraversal());
-      Map<SkyKey, SkyValue> results = env.getValues(nestedKeys);
-      if (env.valuesMissing()) {
-        return null;
+      // Check whether the symlink is excluded before attempting to resolve it.
+      // It may be dangling, but excluding it is still fine.
+      // TODO(b/64754128): Investigate if we could have made the exclude earlier before
+      //                   unnecessarily iterating over all the files in an excluded directory.
+      if (linkName.segmentCount() > 0 && exclusions.contains(linkName.getSegment(0))) {
+        continue;
       }
 
-      for (SkyKey nestedKey : nestedKeys) {
-        FilesetEntryValue nested = (FilesetEntryValue) results.get(nestedKey);
-        for (FilesetOutputSymlink s : nested.getSymlinks()) {
-          if (!exclusions.contains(s.getName().getPathString())) {
-            maybeStoreSymlink(s, t.getDestPath(), outputSymlinks);
-          }
-        }
-      }
-    } else {
-      // The "direct" traversal params are present, which is the case when the FilesetEntry
-      // specifies a package's BUILD file, a directory or a list of files.
-
-      // The root of the direct traversal is defined as follows.
-      //
-      // If FilesetEntry.files is specified, then a TraversalRequest is created for each entry, the
-      // root being the respective entry itself. These are all traversed for they may be
-      // directories or symlinks to directories, and we need to establish Skyframe dependencies on
-      // their contents for incremental correctness. If an entry is indeed a directory (but not when
-      // it's a symlink to one) then we have to create symlinks to each of their childen.
-      // (NB: there seems to be no good reason for this, it's just how legacy Fileset works. We may
-      // want to consider creating a symlink just for the directory and not for its child elements.)
-      //
-      // If FilesetEntry.files is not specified, then srcdir refers to either a BUILD file or a
-      // directory. For the former, the root will be the parent of the BUILD file. For the latter,
-      // the root will be srcdir itself.
-      DirectTraversal direct = t.getDirectTraversal().get();
-
-      RecursiveFilesystemTraversalValue rftv;
+      PathFragment targetName;
       try {
-        // Traverse the filesystem to establish skyframe dependencies.
-        rftv = traverse(env, createErrorInfo(t), direct);
-      } catch (MissingDepException e) {
-        return null;
+        targetName = f.getTargetInSymlinkTree(direct.isFollowingSymlinks());
+      } catch (DanglingSymlinkException e) {
+        throw new FilesetEntryFunctionException(e);
       }
 
-      // The root can only be absent for the EMPTY rftv instance.
-      if (!rftv.getResolvedRoot().isPresent()) {
-        return FilesetEntryValue.EMPTY;
-      }
-
-      ResolvedFile resolvedRoot = rftv.getResolvedRoot().get();
-
-      // Handle dangling symlinks gracefully be returning empty results.
-      if (!resolvedRoot.getType().exists()) {
-        return FilesetEntryValue.EMPTY;
-      }
-
-      // The prefix to remove is the entire path of the root. This is OK:
-      // - when the root is a file, this removes the entire path, but the traversal's destination
-      //   path is actually the name of the output symlink, so this works out correctly
-      // - when the root is a directory or a symlink to one then we need to strip off the
-      //   directory's path from every result (this is how the output symlinks must be created)
-      //   before making them relative to the destination path
-      PathFragment prefixToRemove = direct.getRoot().getRelativePart();
-
-      Iterable<ResolvedFile> results = null;
-
-      if (direct.isRecursive()
-          || (resolvedRoot.getType().isDirectory() && !resolvedRoot.getType().isSymlink())) {
-        // The traversal is recursive (requested for an entire FilesetEntry.srcdir) or it was
-        // requested for a FilesetEntry.files entry which turned out to be a directory. We need to
-        // create an output symlink for every file in it and all of its subdirectories. Only
-        // exception is when the subdirectory is really a symlink to a directory -- no output
-        // shall be created for the contents of those.
-        // Now we create Dir objects to model the filesystem tree. The object employs a trick to
-        // find directory symlinks: directory symlinks have corresponding ResolvedFile entries and
-        // are added as files too, while their children, also added as files, contain the path of
-        // the parent. Finding and discarding the children is easy if we traverse the tree from
-        // root to leaf.
-        DirectoryTree root = new DirectoryTree();
-        for (ResolvedFile f : rftv.getTransitiveFiles().toCollection()) {
-          PathFragment path = f.getNameInSymlinkTree().relativeTo(prefixToRemove);
-          if (!path.isEmpty()) {
-            path = t.getDestPath().getRelative(path);
-            DirectoryTree dir = root;
-            for (int i = 0; i < path.segmentCount() - 1; ++i) {
-              dir = dir.addOrGetSubdir(path.getSegment(i));
-            }
-            dir.maybeAddFile(f);
-          }
-        }
-        // Here's where the magic happens. The returned iterable will yield all files in the
-        // directory that are not under symlinked directories, as well as all directory symlinks.
-        results = root.iterateFiles();
-      } else {
-        // If we're on this branch then the traversal was done for just one entry in
-        // FilesetEntry.files (which was not a directory, so it was either a file, a symlink to one
-        // or a symlink to a directory), meaning we'll have only one output symlink.
-        results = ImmutableList.of(resolvedRoot);
-      }
-
-      // Create one output symlink for each entry in the results.
-      for (ResolvedFile f : results) {
-        // The linkName has to be under the traversal's root, which is also the prefix to remove.
-        PathFragment linkName = f.getNameInSymlinkTree().relativeTo(prefixToRemove);
-
-        // Check whether the symlink is excluded before attempting to resolve it.
-        // It may be dangling, but excluding it is still fine.
-        // TODO(b/64754128): Investigate if we could have made the exclude earlier before
-        //                   unnecessarily iterating over all the files in an excluded directory.
-        if (linkName.segmentCount() > 0 && exclusions.contains(linkName.getSegment(0))) {
-          continue;
-        }
-
-        PathFragment targetName;
-        try {
-          targetName = f.getTargetInSymlinkTree(direct.isFollowingSymlinks());
-        } catch (DanglingSymlinkException e) {
-          throw new FilesetEntryFunctionException(e);
-        }
-
-        maybeStoreSymlink(
-            linkName,
-            targetName,
-            f.getMetadata(),
-            t.getDestPath(),
-            direct.isGenerated(),
-            outputSymlinks);
-      }
+      maybeStoreSymlink(
+          linkName,
+          targetName,
+          f.getMetadata(),
+          t.getDestPath(),
+          direct.isGenerated(),
+          outputSymlinks);
     }
 
     return FilesetEntryValue.of(ImmutableSet.copyOf(outputSymlinks.values()));
@@ -203,20 +181,6 @@
 
   /** Stores an output symlink unless it would overwrite an existing one. */
   private static void maybeStoreSymlink(
-      FilesetOutputSymlink nestedLink,
-      PathFragment destPath,
-      Map<PathFragment, FilesetOutputSymlink> result) {
-    maybeStoreSymlink(
-        nestedLink.getName(),
-        nestedLink.getTargetPath(),
-        nestedLink.getMetadata(),
-        destPath,
-        nestedLink.isGeneratedTarget(),
-        result);
-  }
-
-  /** Stores an output symlink unless it would overwrite an existing one. */
-  private static void maybeStoreSymlink(
       PathFragment linkName,
       PathFragment linkTarget,
       Object metadata,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 5fd47c7..3dcb461 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -519,7 +519,8 @@
       MetadataHandler metadataHandler,
       Map<Artifact, Collection<Artifact>> expandedInputs,
       ImmutableMap<PathFragment, ImmutableList<FilesetOutputSymlink>> inputFilesetMappings,
-      @Nullable FileSystem actionFileSystem) {
+      @Nullable FileSystem actionFileSystem,
+      @Nullable Object skyframeDepsResult) {
     FileOutErr fileOutErr = actionLogBufferPathGenerator.generate(
         ArtifactPathResolver.createPathResolver(actionFileSystem, executorEngine.getExecRoot()));
     return new ActionExecutionContext(
@@ -532,7 +533,8 @@
         clientEnv,
         inputFilesetMappings,
         new ArtifactExpanderImpl(expandedInputs),
-        actionFileSystem);
+        actionFileSystem,
+        skyframeDepsResult);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeAwareAction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeAwareAction.java
index c351cda..da81769 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeAwareAction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeAwareAction.java
@@ -68,6 +68,9 @@
    * <p>This method should not attempt to handle errors or missing dependencies (other than wrapping
    * exceptions); that is the responsibility of the caller. It should return as soon as possible,
    * ready to be called again at a later time if need be.
+   *
+   * <p>The return value will be incorporated into the
+   * {@link com.google.devtools.build.lib.actions.ActionExecutionContext}.
    */
-  void establishSkyframeDependencies(Environment env) throws ExceptionBase, InterruptedException;
+  Object establishSkyframeDependencies(Environment env) throws ExceptionBase, InterruptedException;
 }