Part 2 Implementation for new 'subpackages()` built-in helper function.

Design proposal: https://docs.google.com/document/d/13UOT0GoQofxDW40ILzH2sWpUOmuYy6QZ7CUmhej9vgk/edit#

Overview:

Add StarlarkNativeModule 'subpackages' function with parameters that mirror glob()

PiperOrigin-RevId: 422652954
diff --git a/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm b/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
index 4824b14..08634cf 100644
--- a/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
+++ b/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
@@ -19,6 +19,7 @@
     <li><a href="#exports_files">exports_files</a></li>
     <li><a href="#glob">glob</a></li>
     <li><a href="#select">select</a></li>
+    <li><a href="#subpackages">subpackages</a></li>
   </ul>
 </div>
 #end
@@ -636,48 +637,53 @@
   <li><code>select</code> works with most, but not all, attributes. Incompatible
   attributes are marked <code>nonconfigurable</code> in their documentation.
 
-  </li>
-</ul>
+<!-- =================================================================
+                        subpackages()
+     =================================================================
+  -->
 
-By default, Bazel produces the following error when no conditions match:
-<pre class="code">
-Configurable attribute "foo" doesn't match this configuration (would a default
-condition help?).
-Conditions checked:
- //pkg:conditionA.
- //pkg:conditionB.
-</pre>
+<h2 id="subpackages">subpackages</h2>
 
-You can signal more precise errors with <code>no_match_error</code>.
-
-<h3 id="select_example">Examples</h3>
-
-<pre class="code">
-config_setting(
-    name = "windows",
-    values = {
-        "crosstool_top": "//crosstools/windows",
-    },
-)
-
-cc_binary(
-    name = "multiplatform_app",
-    ...
-    linkopts = select({
-        ":windows": [
-            "-Wl,windows_support1.lib",
-            "-Wl,windows_support2.lib",
-        ],
-        "//conditions:default": [],
-    ...
-)
-</pre>
-
-<p>In the above example, <code>multiplatform_app</code> links with additional
-  options when invoked with <code>bazel build //pkg:multiplatform_app
-  --crosstool_top=//crosstools/windows </code>.
+<pre>subpackages(include, exclude=[], allow_empty=True)</pre>
 
 <p>
+  <code>subpackages()</code> is a helper function, similar to <code>glob()</code>
+  that lists subpackages instead of files and directories.  It uses the same
+  path patterns as <code>glob()</code> and can match any subpackage that is a
+  direct decendant of the currently loading BUILD file.  See <a
+  href="#glob">glob</a> for detailed explinations and example of include and
+  exclude patterns.
+</p>
+
+<p>
+  The resulting list of subpackages returned is in sorted order and contains a
+  paths relative to the current loading package that match the given patterns in
+  <code>include</code> and not those in <code>exclude</code>.
+
+<h3 id=subpackages_example">Example</h3>
+
+<p>
+  The following example lists all the direct subpackages for the package <code>foo/BUILD</code>
+
+<pre class="code">
+# The following BUILD files exist:
+# foo/BUILD
+# foo/bar/baz/BUILD
+# foo/sub/BUILD
+# foo/sub/deeper/BUILD
+#
+# In foo/BUILD a call to
+subs = subpackages(include = ["**"])
+
+# results in subs == ["sub", "foo/bar/baz"]`
+#
+# foo/sub/deeper is not included because it is a subpackage of 'foo/sub' not of
+# 'foo'
+</pre>
+
+    <p>
+    In general it is preferred that instead of calling this function directly
+    that users use the 'subpackages' module of
 
 #if (!$singlePage)
 #parse("com/google/devtools/build/docgen/templates/be/footer.vm")
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index c1e86cc..b0e9567 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -601,6 +601,7 @@
       Program buildFileProgram,
       ImmutableList<String> globs,
       ImmutableList<String> globsWithDirs,
+      ImmutableList<String> subpackages,
       ImmutableMap<String, Object> predeclared,
       ImmutableMap<String, Module> loadedModules,
       StarlarkSemantics starlarkSemantics,
@@ -613,6 +614,8 @@
         globber.runAsync(globs, ImmutableList.of(), Globber.Operation.FILES, allowEmpty);
         globber.runAsync(
             globsWithDirs, ImmutableList.of(), Globber.Operation.FILES_AND_DIRS, allowEmpty);
+        globber.runAsync(
+            subpackages, ImmutableList.of(), Globber.Operation.SUBPACKAGES, allowEmpty);
       } catch (BadGlobException ex) {
         logger.atWarning().withCause(ex).log(
             "Suppressing exception for globs=%s, globsWithDirs=%s", globs, globsWithDirs);
@@ -734,6 +737,7 @@
       StarlarkFile file,
       Collection<String> globs,
       Collection<String> globsWithDirs,
+      Collection<String> subpackages,
       Map<Location, String> generatorNameByLocation,
       Consumer<SyntaxError> errors) {
     final boolean[] success = {true};
@@ -747,11 +751,16 @@
           // Extract literal glob patterns from calls of the form:
           //   glob(include = ["pattern"])
           //   glob(["pattern"])
-          // This may spuriously match user-defined functions named glob;
-          // that's ok, it's only a heuristic.
+          //   subpackages(include = ["pattern"])
+          // This may spuriously match user-defined functions named glob or
+          // subpackages; that's ok, it's only a heuristic.
           void extractGlobPatterns(CallExpression call) {
-            if (call.getFunction() instanceof Identifier
-                && ((Identifier) call.getFunction()).getName().equals("glob")) {
+            if (call.getFunction() instanceof Identifier) {
+              String functionName = ((Identifier) call.getFunction()).getName();
+              if (!functionName.equals("glob") && !functionName.equals("subpackages")) {
+                return;
+              }
+
               Expression excludeDirectories = null, include = null;
               List<Argument> arguments = call.getArguments();
               for (int i = 0; i < arguments.size(); i++) {
@@ -779,7 +788,11 @@
                         exclude = false;
                       }
                     }
-                    (exclude ? globs : globsWithDirs).add(pattern);
+                    if (functionName.equals("glob")) {
+                      (exclude ? globs : globsWithDirs).add(pattern);
+                    } else {
+                      subpackages.add(pattern);
+                    }
                   }
                 }
               }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkNativeModule.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkNativeModule.java
index 9209f9d..916f312 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkNativeModule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkNativeModule.java
@@ -102,7 +102,6 @@
     Globber.Operation op =
         excludeDirs.signum() != 0 ? Globber.Operation.FILES : Globber.Operation.FILES_AND_DIRS;
 
-    List<String> matches;
     boolean allowEmpty;
     if (allowEmptyArgument == Starlark.UNBOUND) {
       allowEmpty =
@@ -114,35 +113,7 @@
           "expected boolean for argument `allow_empty`, got `%s`", allowEmptyArgument);
     }
 
-    try {
-      Globber.Token globToken = context.globber.runAsync(includes, excludes, op, allowEmpty);
-      matches = context.globber.fetchUnsorted(globToken);
-    } catch (IOException e) {
-      logger.atWarning().withCause(e).log(
-          "Exception processing includes=%s, excludes=%s)", includes, excludes);
-      String errorMessage =
-          String.format(
-              "error globbing [%s]%s: %s",
-              Joiner.on(", ").join(includes),
-              excludes.isEmpty() ? "" : " - [" + Joiner.on(", ").join(excludes) + "]",
-              e.getMessage());
-      Location loc = thread.getCallerLocation();
-      Event error =
-          Package.error(
-              loc,
-              errorMessage,
-              // If there are other IOExceptions that can result from user error, they should be
-              // tested for here. Currently FileNotFoundException is not one of those, because globs
-              // only encounter that error in the presence of an inconsistent filesystem.
-              e instanceof FileSymlinkException
-                  ? Code.EVAL_GLOBS_SYMLINK_ERROR
-                  : Code.GLOB_IO_EXCEPTION);
-      context.eventHandler.handle(error);
-      context.pkgBuilder.setIOException(e, errorMessage, error.getProperty(DetailedExitCode.class));
-      matches = ImmutableList.of();
-    } catch (BadGlobException e) {
-      throw new EvalException(e);
-    }
+    List<String> matches = runGlobOperation(context, thread, includes, excludes, op, allowEmpty);
 
     ArrayList<String> result = new ArrayList<>(matches.size());
     for (String match : matches) {
@@ -751,4 +722,62 @@
       super(msg);
     }
   }
+
+  @Override
+  public Sequence<?> subpackages(
+      Sequence<?> include, Sequence<?> exclude, boolean allowEmpty, StarlarkThread thread)
+      throws EvalException, InterruptedException {
+    BazelStarlarkContext.from(thread).checkLoadingPhase("native.subpackages");
+    PackageContext context = getContext(thread);
+
+    List<String> includes = Type.STRING_LIST.convert(include, "'subpackages' argument");
+    List<String> excludes = Type.STRING_LIST.convert(exclude, "'subpackages' argument");
+
+    List<String> matches =
+        runGlobOperation(
+            context, thread, includes, excludes, Globber.Operation.SUBPACKAGES, allowEmpty);
+    matches.sort(naturalOrder());
+
+    return StarlarkList.copyOf(thread.mutability(), matches);
+  }
+
+  private List<String> runGlobOperation(
+      PackageContext context,
+      StarlarkThread thread,
+      List<String> includes,
+      List<String> excludes,
+      Globber.Operation operation,
+      boolean allowEmpty)
+      throws EvalException, InterruptedException {
+    try {
+      Globber.Token globToken = context.globber.runAsync(includes, excludes, operation, allowEmpty);
+      return context.globber.fetchUnsorted(globToken);
+    } catch (IOException e) {
+      logger.atWarning().withCause(e).log(
+          "Exception processing includes=%s, excludes=%s)", includes, excludes);
+      String errorMessage =
+          String.format(
+              "error globbing [%s]%s op=%s: %s",
+              Joiner.on(", ").join(includes),
+              excludes.isEmpty() ? "" : " - [" + Joiner.on(", ").join(excludes) + "]",
+              operation,
+              e.getMessage());
+      Location loc = thread.getCallerLocation();
+      Event error =
+          Package.error(
+              loc,
+              errorMessage,
+              // If there are other IOExceptions that can result from user error, they should be
+              // tested for here. Currently FileNotFoundException is not one of those, because globs
+              // only encounter that error in the presence of an inconsistent filesystem.
+              e instanceof FileSymlinkException
+                  ? Code.EVAL_GLOBS_SYMLINK_ERROR
+                  : Code.GLOB_IO_EXCEPTION);
+      context.eventHandler.handle(error);
+      context.pkgBuilder.setIOException(e, errorMessage, error.getProperty(DetailedExitCode.class));
+      return ImmutableList.of();
+    } catch (BadGlobException e) {
+      throw new EvalException(e);
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
index 7e7c547..963956d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
@@ -146,8 +146,9 @@
       List<String> globs = new ArrayList<>(); // unused
       if (PackageFactory.checkBuildSyntax(
           file,
-          globs,
-          globs,
+          /*globs=*/ globs,
+          /*globsWithDirs=*/ globs,
+          /*subpackages=*/ globs,
           new HashMap<>(),
           error ->
               localReporter.handle(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
index 5aef741..2885689 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
@@ -84,19 +84,32 @@
     // Note that the glob's package is assumed to exist which implies that the package's BUILD file
     // exists which implies that the package's directory exists.
     if (!globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
+      PathFragment subDirFragment =
+          glob.getPackageId().getPackageFragment().getRelative(globSubdir);
+
       PackageLookupValue globSubdirPkgLookupValue =
           (PackageLookupValue)
               env.getValue(
-                  PackageLookupValue.key(
-                      PackageIdentifier.create(
-                          repositoryName,
-                          glob.getPackageId().getPackageFragment().getRelative(globSubdir))));
+                  PackageLookupValue.key(PackageIdentifier.create(repositoryName, subDirFragment)));
       if (globSubdirPkgLookupValue == null) {
         return null;
       }
+
       if (globSubdirPkgLookupValue.packageExists()) {
         // We crossed the package boundary, that is, pkg/subdir contains a BUILD file and thus
-        // defines another package, so glob expansion should not descend into that subdir.
+        // defines another package, so glob expansion should not descend into
+        // that subdir.
+        //
+        // For SUBPACKAGES, we encounter this when the pattern is a recursive ** and we are a
+        // terminal package for that pattern. In that case we should include the subDirFragment
+        // PathFragment (relative to the glob's package) in the GlobValue.getMatches,
+        // otherwise for file/dir matching return EMPTY;
+        if (globberOperation == Globber.Operation.SUBPACKAGES) {
+          return new GlobValue(
+              NestedSetBuilder.<PathFragment>stableOrder()
+                  .add(subDirFragment.relativeTo(glob.getPackageId().getPackageFragment()))
+                  .build());
+        }
         return GlobValue.EMPTY;
       } else if (globSubdirPkgLookupValue
           instanceof PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue) {
@@ -215,7 +228,7 @@
           if (keyToRequest != null) {
             subdirMap.put(keyToRequest, dirent);
           }
-        } else if (globMatchesBareFile) {
+        } else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
           sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName));
         }
       }
@@ -272,7 +285,7 @@
             if (keyToRequest != null) {
               symlinkSubdirMap.put(keyToRequest, dirent);
             }
-          } else if (globMatchesBareFile) {
+          } else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
             sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName));
           }
         } else {
@@ -314,7 +327,7 @@
               addToMatches(fileMatches, matches);
             }
           }
-        } else if (globMatchesBareFile) {
+        } else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
           matches.add(glob.getSubdir().getRelative(fileName));
         }
       }
@@ -352,9 +365,10 @@
   private static void addToMatches(Object toAdd, NestedSetBuilder<PathFragment> matches) {
     if (toAdd instanceof PathFragment) {
       matches.add((PathFragment) toAdd);
-    } else {
+    } else if (toAdd instanceof NestedSet) {
       matches.addTransitive((NestedSet<PathFragment>) toAdd);
     }
+    // else Not actually a valid type and ignore.
   }
 
   /**
@@ -373,15 +387,17 @@
     if (subdirPattern == null) {
       if (glob.globberOperation() == Globber.Operation.FILES) {
         return null;
-      } else {
-        return PackageLookupValue.key(
-            PackageIdentifier.create(
-                glob.getPackageId().getRepository(),
-                glob.getPackageId()
-                    .getPackageFragment()
-                    .getRelative(glob.getSubdir())
-                    .getRelative(fileName)));
       }
+
+      // For FILES_AND_DIRS and SUBPACKAGES we want to maybe inspect a
+      // PackageLookupValue for it.
+      return PackageLookupValue.key(
+          PackageIdentifier.create(
+              glob.getPackageId().getRepository(),
+              glob.getPackageId()
+                  .getPackageFragment()
+                  .getRelative(glob.getSubdir())
+                  .getRelative(fileName)));
     } else {
       // There is some more pattern to match. Get the glob for the subdirectory. Note that this
       // directory may also match directly in the case of a pattern that starts with "**", but that
@@ -396,38 +412,55 @@
   }
 
   /**
-   * Returns matches coming from the directory {@code fileName} if appropriate, either an individual
-   * file or a nested set of files.
+   * Returns an Object indicating a match was found for the given fileName in the given
+   * valueRequested. The Object will be one of:
    *
-   * <p>{@code valueRequested} must be the SkyValue whose key was returned by
-   * {@link #getSkyKeyForSubdir} for these parameters.
+   * <ul>
+   *   <li>{@code null} if no matches for the given parameters exists
+   *   <li>{@code NestedSet<PathFragment>} if a match exists, either because we are looking for
+   *       files/directories or the SkyValue is a package and we're globbing for {@link
+   *       Globber.Operation.SUBPACKAGES}
+   * </ul>
+   *
+   * <p>{@code valueRequested} must be the SkyValue whose key was returned by {@link
+   * #getSkyKeyForSubdir} for these parameters.
    */
   @Nullable
   private static Object getSubdirMatchesFromSkyValue(
-      String fileName,
-      GlobDescriptor glob,
-      SkyValue valueRequested) {
+      String fileName, GlobDescriptor glob, SkyValue valueRequested) {
     if (valueRequested instanceof GlobValue) {
       return ((GlobValue) valueRequested).getMatches();
-    } else {
-      Preconditions.checkState(
-          valueRequested instanceof PackageLookupValue,
-          "%s is not a GlobValue or PackageLookupValue (%s %s)",
-          valueRequested,
-          fileName,
-          glob);
-      PackageLookupValue packageLookupValue = (PackageLookupValue) valueRequested;
-      if (packageLookupValue.packageExists()) {
-        // This is a separate package, so ignore it.
-        return null;
-      } else if (packageLookupValue
-          instanceof PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue) {
-        // This is a separate repository, so ignore it.
-        return null;
-      } else {
-        return glob.getSubdir().getRelative(fileName);
-      }
     }
+
+    Preconditions.checkState(
+        valueRequested instanceof PackageLookupValue,
+        "%s is not a GlobValue or PackageLookupValue (%s %s)",
+        valueRequested,
+        fileName,
+        glob);
+
+    PackageLookupValue packageLookupValue = (PackageLookupValue) valueRequested;
+    if (packageLookupValue
+        instanceof PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue) {
+      // This is a separate repository, so ignore it.
+      return null;
+    }
+
+    boolean isSubpackagesOp = glob.globberOperation() == Globber.Operation.SUBPACKAGES;
+    boolean pkgExists = packageLookupValue.packageExists();
+
+    if (!isSubpackagesOp && pkgExists) {
+      // We're in our repo and fileName is a package. Since we're not doing SUBPACKAGES listing, we
+      // do not want to add it to the results.
+      return null;
+    } else if (isSubpackagesOp && !pkgExists) {
+      // We're in our repo and the package exists. Since we're doing SUBPACKAGES listing, we do
+      // want to add fileName to the results.
+      return null;
+    }
+
+    // The  fileName should be added to the results of the glob.
+    return glob.getSubdir().getRelative(fileName);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 74bf760..68bb140 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -135,6 +135,7 @@
     @Nullable private final Program prog;
     @Nullable private final ImmutableList<String> globs;
     @Nullable private final ImmutableList<String> globsWithDirs;
+    @Nullable private final ImmutableList<String> subpackages;
     @Nullable private final ImmutableMap<Location, String> generatorMap;
     @Nullable private final ImmutableMap<String, Object> predeclared;
 
@@ -147,11 +148,13 @@
         Program prog,
         ImmutableList<String> globs,
         ImmutableList<String> globsWithDirs,
+        ImmutableList<String> subpackages,
         ImmutableMap<Location, String> generatorMap,
         ImmutableMap<String, Object> predeclared) {
       this.errors = null;
       this.prog = prog;
       this.globs = globs;
+      this.subpackages = subpackages;
       this.globsWithDirs = globsWithDirs;
       this.generatorMap = generatorMap;
       this.predeclared = predeclared;
@@ -163,6 +166,7 @@
       this.prog = null;
       this.globs = null;
       this.globsWithDirs = null;
+      this.subpackages = null;
       this.generatorMap = null;
       this.predeclared = null;
     }
@@ -1335,6 +1339,7 @@
             compiled.prog,
             compiled.globs,
             compiled.globsWithDirs,
+            compiled.subpackages,
             compiled.predeclared,
             loadedModules,
             starlarkBuiltinsValue.starlarkSemantics,
@@ -1435,9 +1440,11 @@
     // - record the generator_name of each top-level macro call
     Set<String> globs = new HashSet<>();
     Set<String> globsWithDirs = new HashSet<>();
+    Set<String> subpackages = new HashSet<>();
     Map<Location, String> generatorMap = new HashMap<>();
     ImmutableList.Builder<SyntaxError> errors = ImmutableList.builder();
-    if (!PackageFactory.checkBuildSyntax(file, globs, globsWithDirs, generatorMap, errors::add)) {
+    if (!PackageFactory.checkBuildSyntax(
+        file, globs, globsWithDirs, subpackages, generatorMap, errors::add)) {
       return new CompiledBuildFile(errors.build());
     }
 
@@ -1485,6 +1492,7 @@
         prog,
         ImmutableList.copyOf(globs),
         ImmutableList.copyOf(globsWithDirs),
+        ImmutableList.copyOf(subpackages),
         ImmutableMap.copyOf(generatorMap),
         ImmutableMap.copyOf(predeclared));
   }
diff --git a/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkNativeModuleApi.java b/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkNativeModuleApi.java
index 4776b8d..efdb8e5 100644
--- a/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkNativeModuleApi.java
+++ b/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkNativeModuleApi.java
@@ -237,4 +237,41 @@
               + "<code>REPOSITORY_NAME</code>.",
       useStarlarkThread = true)
   String repositoryName(StarlarkThread thread) throws EvalException;
+
+  @StarlarkMethod(
+      name = "subpackages",
+      doc =
+          "Returns a new mutable list of every direct subpackage of the current package,"
+              + " regardless of file-system directory depth. List returned is sorted and contains"
+              + " the names of subpackages relative to the current package. It is advised to"
+              + " prefer using the methods in bazel_skylib.subpackages module rather than calling"
+              + " this function directly.",
+      parameters = {
+        @Param(
+            name = "include",
+            allowedTypes = {@ParamType(type = Sequence.class, generic1 = String.class)},
+            positional = false,
+            named = true,
+            doc = "The list of glob patterns to include in subpackages scan."),
+        @Param(
+            name = "exclude",
+            allowedTypes = {@ParamType(type = Sequence.class, generic1 = String.class)},
+            defaultValue = "[]",
+            positional = false,
+            named = true,
+            doc = "The list of glob patterns to exclude from subpackages scan."),
+        @Param(
+            name = "allow_empty",
+            defaultValue = "False",
+            positional = false,
+            named = true,
+            doc =
+                "Whether we fail if the call returns an empty list. By default empty list indicates"
+                    + " potential error in BUILD file where the call to subpackages() is"
+                    + " superflous.  Setting to true allows this function to succeed in that case.")
+      },
+      useStarlarkThread = true)
+  Sequence<?> subpackages(
+      Sequence<?> include, Sequence<?> exclude, boolean allowEmpty, StarlarkThread thread)
+      throws EvalException, InterruptedException;
 }
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeStarlarkNativeModuleApi.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeStarlarkNativeModuleApi.java
index c22d07c2de..b4fd592 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeStarlarkNativeModuleApi.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeStarlarkNativeModuleApi.java
@@ -77,6 +77,13 @@
     return "";
   }
 
+  @Override
+  public Sequence<?> subpackages(
+      Sequence<?> include, Sequence<?> exclude, boolean allowEmpty, StarlarkThread thread)
+      throws EvalException, InterruptedException {
+    return StarlarkList.of(thread.mutability());
+  }
+
   @Nullable
   @Override
   public Object getValue(String name) throws EvalException {
diff --git a/src/test/java/com/google/devtools/build/lib/packages/BUILD b/src/test/java/com/google/devtools/build/lib/packages/BUILD
index 12a0a08..b19ea22 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/packages/BUILD
@@ -69,10 +69,12 @@
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/exec:test_policy",
         "//src/main/java/com/google/devtools/build/lib/packages",
+        "//src/main/java/com/google/devtools/build/lib/packages:configured_attribute_mapper",
         "//src/main/java/com/google/devtools/build/lib/packages:exec_group",
         "//src/main/java/com/google/devtools/build/lib/packages:globber",
         "//src/main/java/com/google/devtools/build/lib/pkgcache",
         "//src/main/java/com/google/devtools/build/lib/runtime/commands",
+        "//src/main/java/com/google/devtools/build/lib/skyframe:configured_target_and_data",
         "//src/main/java/com/google/devtools/build/lib/skyframe:tests_for_target_pattern_value",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/lib/util",
diff --git a/src/test/java/com/google/devtools/build/lib/packages/NativeGlobTest.java b/src/test/java/com/google/devtools/build/lib/packages/NativeGlobTest.java
new file mode 100644
index 0000000..19e40a9
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/packages/NativeGlobTest.java
@@ -0,0 +1,161 @@
+// Copyright 2021 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.packages;
+
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertThrows;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
+import com.google.devtools.build.lib.vfs.ModifiedFileSet;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
+import java.io.IOException;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@code native.glob} function. */
+@RunWith(JUnit4.class)
+public class NativeGlobTest extends BuildViewTestCase {
+
+  @Test
+  public void glob_simple() throws Exception {
+    makeFile("test/starlark/file1.txt");
+    makeFile("test/starlark/file2.txt");
+    makeFile("test/starlark/file3.txt");
+
+    makeGlobFilegroup("test/starlark/BUILD", "glob(['*'])");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark:BUILD",
+            "//test/starlark:file1.txt",
+            "//test/starlark:file2.txt",
+            "//test/starlark:file3.txt"));
+  }
+
+  @Test
+  public void glob_not_empty() throws Exception {
+
+    makeGlobFilegroup("test/starlark/BUILD", "glob(['foo*'], allow_empty=False)");
+
+    AssertionError e =
+        assertThrows(
+            AssertionError.class,
+            () -> assertAttrLabelList("//test/starlark:files", "srcs", ImmutableList.of()));
+    assertThat(e).hasMessageThat().contains("allow_empty");
+  }
+
+  @Test
+  public void glob_simple_subdirs() throws Exception {
+    makeFile("test/starlark/sub/file1.txt");
+    makeFile("test/starlark/sub2/file2.txt");
+    makeFile("test/starlark/sub3/file3.txt");
+
+    makeGlobFilegroup("test/starlark/BUILD", "glob(['**'])");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark:BUILD",
+            "//test/starlark:sub/file1.txt",
+            "//test/starlark:sub2/file2.txt",
+            "//test/starlark:sub3/file3.txt"));
+  }
+
+  @Test
+  public void glob_incremental() throws Exception {
+    makeFile("test/starlark/file1.txt");
+    makeGlobFilegroup("test/starlark/BUILD", "glob(['**'])");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of("//test/starlark:BUILD", "//test/starlark:file1.txt"));
+
+    scratch.file("test/starlark/file2.txt");
+    scratch.file("test/starlark/sub/subfile3.txt");
+
+    // Poke SkyFrame to tell it what changed.
+    invalidateSkyFrameFiles(
+        "test/starlark", "test/starlark/file2.txt", "test/starlark/sub/subfile3.txt");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark:BUILD",
+            "//test/starlark:file1.txt",
+            "//test/starlark:file2.txt",
+            "//test/starlark:sub/subfile3.txt"));
+  }
+
+  /**
+   * Constructs a BUILD file containing a single rule with uses glob() to list files look for a rule
+   * called :files in it.
+   */
+  private void makeGlobFilegroup(String buildPath, String glob) throws IOException {
+    scratch.file(buildPath, "filegroup(", "   name = 'files',", "   srcs = " + glob, ")");
+  }
+
+  private void assertAttrLabelList(String target, String attrName, List<String> expectedLabels)
+      throws Exception {
+    ConfiguredTargetAndData cfgTarget = getConfiguredTargetAndData(target);
+    assertThat(cfgTarget).isNotNull();
+
+    ImmutableList<Label> labels =
+        expectedLabels.stream().map(this::makeLabel).collect(toImmutableList());
+
+    ConfiguredAttributeMapper configuredAttributeMapper =
+        getMapperFromConfiguredTargetAndTarget(cfgTarget);
+    assertThat(configuredAttributeMapper.get(attrName, BuildType.LABEL_LIST))
+        .containsExactlyElementsIn(labels);
+  }
+
+  private Label makeLabel(String label) {
+    try {
+      return Label.parseAbsolute(label, ImmutableMap.of());
+    } catch (Exception e) {
+      // Always fails the test.
+      assertThat(e).isNull();
+      return null;
+    }
+  }
+
+  private void invalidateSkyFrameFiles(String... files) throws Exception {
+    ModifiedFileSet.Builder builder = ModifiedFileSet.builder();
+
+    for (String f : files) {
+      builder.modify(PathFragment.create(f));
+    }
+
+    getSkyframeExecutor()
+        .invalidateFilesUnderPathForTesting(
+            reporter, builder.build(), Root.fromPath(rootDirectory));
+  }
+
+  private void makeFile(String fileName) throws IOException {
+    scratch.file(fileName, "Content: " + fileName);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/packages/NativeSubpackagesTest.java b/src/test/java/com/google/devtools/build/lib/packages/NativeSubpackagesTest.java
new file mode 100644
index 0000000..15a648f
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/packages/NativeSubpackagesTest.java
@@ -0,0 +1,341 @@
+// Copyright 2021 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.packages;
+
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
+import com.google.devtools.build.lib.vfs.ModifiedFileSet;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
+import java.io.IOException;
+import java.util.List;
+import java.util.stream.Collectors;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@code native.subpackages} function. */
+@RunWith(JUnit4.class)
+public class NativeSubpackagesTest extends BuildViewTestCase {
+
+  private static final String ALL_SUBDIRS = "**";
+
+  @Test
+  public void subpackages_simple_subDir() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, null);
+    makeFilesSubPackage("test/starlark/sub");
+
+    assertAttrLabelList(
+        "//test/starlark:files", "srcs", ImmutableList.of("//test/starlark/sub:files"));
+  }
+
+  @Test
+  public void subpackages_simple_include() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", "sub1/**", null, null);
+
+    makeFilesSubPackage("test/starlark/sub");
+    makeFilesSubPackage("test/starlark/sub1");
+    makeFilesSubPackage("test/starlark/sub2");
+
+    assertAttrLabelList(
+        "//test/starlark:files", "srcs", ImmutableList.of("//test/starlark/sub1:files"));
+  }
+
+  @Test
+  public void subpackages_simple_exclude() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, "['sub2/**']", null);
+
+    makeFilesSubPackage("test/starlark/sub");
+    makeFilesSubPackage("test/starlark/sub1");
+    makeFilesSubPackage("test/starlark/sub2");
+    makeFilesSubPackage("test/starlark/sub3");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark/sub:files",
+            "//test/starlark/sub1:files",
+            "//test/starlark/sub3:files"));
+  }
+
+  @Test
+  public void subpackages_simple_empty_allow() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, true);
+    assertAttrLabelList("//test/starlark:files", "srcs", ImmutableList.of());
+  }
+
+  @Test
+  public void subpackages_simple_empty_disallow() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, null);
+
+    // force evaluation
+    AssertionError e =
+        assertThrows(AssertionError.class, () -> getConfiguredTarget("//test/starlark:files"));
+    assertThat(e).hasMessageThat().contains("subpackages pattern '**' didn't match anything");
+  }
+
+  @Test
+  public void subpackages_deeplyNested_withSubdirs() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, true);
+
+    // Setup a dir with 2 subdirs, 1 a package one not
+    makeFilesSubPackage("test/starlark/sub");
+    // Should be blocked by 'sub'
+    makeFilesSubPackage("test/starlark/sub/sub2");
+
+    makeFilesSubPackage("test/starlark/sub3");
+    makeFilesSubPackage("test/starlark/not_sub/sub_is_pkg/eventually");
+
+    scratch.file("test/starlark/not_sub/file1.txt");
+    scratch.file("test/starlark/not_sub/double_not_sub/file.txt");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark/sub:files",
+            "//test/starlark/sub3:files",
+            "//test/starlark/not_sub/sub_is_pkg/eventually:files"));
+  }
+
+  @Test
+  public void subpackages_incremental_addSubPkg() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, null);
+
+    // Setup a two subdirs one shallow and one deep
+    makeFilesSubPackage("test/starlark/sub");
+    makeFilesSubPackage("test/starlark/deep/1/2/3");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of("//test/starlark/sub:files", "//test/starlark/deep/1/2/3:files"));
+
+    // Add a 2nd shallow and 2nd deep mid
+    makeFilesSubPackage("test/starlark/sub2");
+
+    // Poke Skyframe by invalidating the dirent and files that changed.
+    invalidateSkyFrameFiles(
+        "test/starlark/sub2", "test/starlark/sub2/BUILD", "test/starlark/sub2/file.txt");
+
+    // We should now be aware of the new one via Skyframe invalidation.
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark/sub:files",
+            "//test/starlark/sub2:files",
+            "//test/starlark/deep/1/2/3:files"));
+  }
+
+  @Test
+  public void subpackages_incremental_delSubPkg() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, null);
+
+    // Setup a single subdir
+    makeFilesSubPackage("test/starlark/sub");
+    makeFilesSubPackage("test/starlark/sub2");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of("//test/starlark/sub:files", "//test/starlark/sub2:files"));
+
+    scratch.deleteFile("test/starlark/sub2/BUILD");
+    scratch.deleteFile("test/starlark/sub2/file.txt");
+
+    invalidateSkyFrameFiles("test/starlark/sub2/BUILD", "test/starlark/sub2/file.txt");
+
+    // We should now be aware of the new one.
+    assertAttrLabelList(
+        "//test/starlark:files", "srcs", ImmutableList.of("//test/starlark/sub:files"));
+  }
+
+  @Test
+  public void subpackages_incremental_convertSubDirToPkg() throws Exception {
+    makeSubpackageFileGroup("test/starlark/BUILD", ALL_SUBDIRS, null, null);
+
+    // Setup both immediate and deeply nested sub-dirs with BUILD files.
+    makeFilesSubPackage("test/starlark/sub");
+    scratch.file("test/starlark/sub2/file2.txt");
+
+    // Initially we have a subdir with 'sub/BUILD' and sub2/file2.txt"
+    assertAttrLabelList(
+        "//test/starlark:files", "srcs", ImmutableList.of("//test/starlark/sub:files"));
+
+    // Then we add a BUILD file to sub2 making it a package Skyframe should pick
+    // that up once invalidated.
+    makeFilesSubPackage("test/starlark/sub2");
+
+    // Poke Skyframe by invalidating the dirent and files that changed.
+    invalidateSkyFrameFiles("test/starlark/sub2/BUILD", "test/starlark/sub2/file.txt");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of("//test/starlark/sub:files", "//test/starlark/sub2:files"));
+  }
+
+  @Test
+  public void invalidPositionalParams() throws Exception {
+    scratch.file("foo/subdir/BUILD");
+    scratch.file("foo/BUILD", "[sh_library(name = p) for p in subpackages(['subdir'])]");
+
+    AssertionError e =
+        assertThrows(AssertionError.class, () -> getConfiguredTargetAndData("//foo:subdir"));
+    assertThat(e).hasMessageThat().contains("got unexpected positional argument");
+  }
+
+  @Test
+  public void invalidMissingInclude() throws Exception {
+    scratch.file("foo/subdir/BUILD");
+    scratch.file("foo/BUILD", "[sh_library(name = p) for p in subpackages()]");
+
+    AssertionError e =
+        assertThrows(AssertionError.class, () -> getConfiguredTargetAndData("//foo:subdir"));
+    assertThat(e).hasMessageThat().contains("missing 1 required named argument: include");
+  }
+
+  @Test
+  public void validNoWildCardInclude() throws Exception {
+    makeSubpackageFileGroup(
+        "test/starlark/BUILD", /*include=*/ ImmutableList.of("sub", "sub2/deep"), null, null);
+    makeFilesSubPackage("test/starlark/sub");
+    makeFilesSubPackage("test/starlark/sub2/deep");
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of("//test/starlark/sub:files", "//test/starlark/sub2/deep:files"));
+  }
+
+  @Test
+  public void includeValidMatchSubdir() throws Exception {
+    scratch.file("foo/subdir/BUILD");
+    scratch.file(
+        "foo/BUILD", "[sh_library(name = p) for p in subpackages(include = ['subdir/*'])]");
+
+    getConfiguredTargetAndData("//foo:subdir");
+  }
+
+  @Test
+  public void includeValidSubMatchSubdir() throws Exception {
+    makeFilesSubPackage("test/starlark/subdir/sub/deeper");
+    makeFilesSubPackage("test/starlark/subdir/sub2/deeper");
+    makeFilesSubPackage("test/starlark/subdir/sub3/deeper");
+
+    makeSubpackageFileGroup("test/starlark/BUILD", "subdir/*/deeper", null, null);
+
+    assertAttrLabelList(
+        "//test/starlark:files",
+        "srcs",
+        ImmutableList.of(
+            "//test/starlark/subdir/sub/deeper:files",
+            "//test/starlark/subdir/sub2/deeper:files",
+            "//test/starlark/subdir/sub3/deeper:files"));
+  }
+
+  /**
+   * Constructs a BUILD file with a single filegroup target whose srcs attribute is the list of all
+   * //p:files, where //p is a subpackage returned by a call to native.subpackages.
+   */
+  private void makeSubpackageFileGroup(
+      String buildPath, ImmutableList<String> include, String exclude, Boolean allowEmpty)
+      throws IOException {
+    StringBuilder subpackages = new StringBuilder();
+    subpackages.append("subpackages(include = [");
+    subpackages.append(include.stream().map(i -> "'" + i + "'").collect(Collectors.joining(", ")));
+    subpackages.append("]");
+
+    if (exclude != null) {
+      subpackages.append(", exclude = ");
+      subpackages.append(exclude);
+    }
+
+    if (allowEmpty != null) {
+      subpackages.append(", allow_empty = ");
+      subpackages.append(allowEmpty ? "True" : "False");
+    }
+    subpackages.append(")");
+
+    scratch.file(
+        buildPath,
+        "filegroup(",
+        "   name = 'files',",
+        "   srcs = [",
+        "     '//%s/%s:files' % (package_name(), s) for s in " + subpackages,
+        "   ],",
+        ")");
+  }
+
+  private void makeSubpackageFileGroup(
+      String buildPath, String include, String exclude, Boolean allowEmpty) throws IOException {
+    makeSubpackageFileGroup(buildPath, ImmutableList.of(include), exclude, allowEmpty);
+  }
+
+  /**
+   * Creates a BUILD file and single file at the given packagePath, the BUILD file will contain a
+   * single filegroup called 'files' which contains the created file.
+   */
+  private void makeFilesSubPackage(String packagePath) throws IOException {
+    scratch.file(packagePath + "/file.txt");
+    scratch.file(
+        packagePath + "/BUILD", "filegroup(", "   name = 'files',", "   srcs = glob(['*']),", ")");
+  }
+
+  private void assertAttrLabelList(String target, String attrName, List<String> expectedLabels)
+      throws Exception {
+    ConfiguredTargetAndData cfgTarget = getConfiguredTargetAndData(target);
+    assertThat(cfgTarget).isNotNull();
+
+    ImmutableList<Label> labels =
+        expectedLabels.stream().map(this::makeLabel).collect(toImmutableList());
+
+    ConfiguredAttributeMapper configuredAttributeMapper =
+        getMapperFromConfiguredTargetAndTarget(cfgTarget);
+    assertThat(configuredAttributeMapper.get(attrName, BuildType.LABEL_LIST))
+        .containsExactlyElementsIn(labels);
+  }
+
+  private Label makeLabel(String label) {
+    try {
+      return Label.parseAbsolute(label, ImmutableMap.of());
+    } catch (Exception e) {
+      fail("Unable to construct Label from " + label);
+      return null;
+    }
+  }
+
+  private void invalidateSkyFrameFiles(String... files) throws Exception {
+    ModifiedFileSet.Builder builder = ModifiedFileSet.builder();
+
+    for (String f : files) {
+      builder.modify(PathFragment.create(f));
+    }
+
+    getSkyframeExecutor()
+        .invalidateFilesUnderPathForTesting(
+            reporter, builder.build(), Root.fromPath(rootDirectory));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java b/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
index ee56bb8..e801662 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
@@ -752,7 +752,7 @@
         assertThrows(NoSuchPackageException.class, () -> loadPackage("pkg"));
     assertThat(ex)
         .hasMessageThat()
-        .contains("error globbing [globs/**]: " + dir + " (Permission denied)");
+        .contains("error globbing [globs/**] op=FILES: " + dir + " (Permission denied)");
   }
 
   @Test
@@ -1147,10 +1147,12 @@
                 "third_variable = glob(['c'], exclude_directories = 0)"));
     List<String> globs = new ArrayList<>();
     List<String> globsWithDirs = new ArrayList<>();
+    List<String> subpackages = new ArrayList<>();
     PackageFactory.checkBuildSyntax(
-        file, globs, globsWithDirs, new HashMap<>(), /*eventHandler=*/ null);
+        file, globs, globsWithDirs, subpackages, new HashMap<>(), /*eventHandler=*/ null);
     assertThat(globs).containsExactly("ab", "a", "**/*");
     assertThat(globsWithDirs).containsExactly("c");
+    assertThat(subpackages).isEmpty();
   }
 
   // Tests of BUILD file dialect checks:
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index c66ec8a..97eb1de 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -838,4 +838,148 @@
       return super.statIfFound(path, followSymlinks);
     }
   }
+
+  private void assertSubpackageMatches(String pattern, String... expecteds) throws Exception {
+    assertThat(
+            Iterables.transform(
+                runGlob(pattern, Globber.Operation.SUBPACKAGES).getMatches().toList(),
+                Functions.toStringFunction()))
+        .containsExactlyElementsIn(ImmutableList.copyOf(expecteds));
+  }
+
+  private void makeEmptyPackage(Path newPackagePath) throws Exception {
+    newPackagePath.createDirectoryAndParents();
+    FileSystemUtils.createEmptyFile(newPackagePath.getRelative("BUILD"));
+  }
+
+  private void makeEmptyPackage(String path) throws Exception {
+    makeEmptyPackage(pkgPath.getRelative(path));
+  }
+
+  @Test
+  public void subpackages_simple() throws Exception {
+    makeEmptyPackage("horse");
+    makeEmptyPackage("monkey");
+    makeEmptyPackage("horse/saddle");
+
+    // "horse/saddle" should not be in the results because horse/saddle is too deep. a2/b2 added by
+    // setup().
+    assertSubpackageMatches("**", /* => */ "a2/b2", "horse", "monkey");
+  }
+
+  @Test
+  public void subpackages_empty() throws Exception {
+    assertSubpackageMatches("foo/*");
+    assertSubpackageMatches("foo/**");
+  }
+
+  @Test
+  public void subpackages_oneLevelDeep() throws Exception {
+    makeEmptyPackage("base/sub");
+    makeEmptyPackage("base/sub2");
+    makeEmptyPackage("base/sub3");
+
+    assertSubpackageMatches("base/*", /* => */ "base/sub", "base/sub2", "base/sub3");
+    assertSubpackageMatches("base/**", /* => */ "base/sub", "base/sub2", "base/sub3");
+  }
+
+  @Test
+  public void subpackages_oneLevel_notDeepEnough() throws Exception {
+    makeEmptyPackage("base/sub/pkg");
+    makeEmptyPackage("base/sub2/pkg");
+    makeEmptyPackage("base/sub3/pkg");
+
+    // * doesn't go deep enough
+    assertSubpackageMatches("base/*");
+    // But if we go with ** it works fine.
+    assertSubpackageMatches("base/**", /* => */ "base/sub/pkg", "base/sub2/pkg", "base/sub3/pkg");
+  }
+
+  @Test
+  public void subpackages_deepRecurse() throws Exception {
+    makeEmptyPackage("base/sub/1");
+    makeEmptyPackage("base/sub/2");
+    makeEmptyPackage("base/sub2/3");
+    makeEmptyPackage("base/sub2/4");
+    makeEmptyPackage("base/sub3/5");
+    makeEmptyPackage("base/sub3/6");
+
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/bar/BUILD"));
+    // "foo/bar" should not be in the results because foo/bar is a separate package.
+    assertSubpackageMatches(
+        "base/*/*",
+        "base/sub/1",
+        "base/sub/2",
+        "base/sub2/3",
+        "base/sub2/4",
+        "base/sub3/5",
+        "base/sub3/6");
+
+    assertSubpackageMatches(
+        "base/**",
+        "base/sub/1",
+        "base/sub/2",
+        "base/sub2/3",
+        "base/sub2/4",
+        "base/sub3/5",
+        "base/sub3/6");
+  }
+
+  @Test
+  public void subpackages_middleWidlcard() throws Exception {
+    makeEmptyPackage("base/sub1/same");
+    makeEmptyPackage("base/sub2/same");
+    makeEmptyPackage("base/sub3/same");
+    makeEmptyPackage("base/sub4/same");
+    makeEmptyPackage("base/sub5/same");
+    makeEmptyPackage("base/sub6/same");
+
+    assertSubpackageMatches(
+        "base/*/same",
+        "base/sub1/same",
+        "base/sub2/same",
+        "base/sub3/same",
+        "base/sub4/same",
+        "base/sub5/same",
+        "base/sub6/same");
+
+    assertSubpackageMatches(
+        "base/**/same",
+        "base/sub1/same",
+        "base/sub2/same",
+        "base/sub3/same",
+        "base/sub4/same",
+        "base/sub5/same",
+        "base/sub6/same");
+  }
+
+  @Test
+  public void subpackages_noWildcard() throws Exception {
+    makeEmptyPackage("sub1");
+    makeEmptyPackage("sub2");
+    makeEmptyPackage("sub3/deep");
+    makeEmptyPackage("sub4/deeper/deeper");
+
+    assertSubpackageMatches("sub");
+    assertSubpackageMatches("sub1", "sub1");
+    assertSubpackageMatches("sub2", "sub2");
+    assertSubpackageMatches("sub3/deep", "sub3/deep");
+    assertSubpackageMatches("sub4/deeper/deeper", "sub4/deeper/deeper");
+  }
+
+  @Test
+  public void subpackages_testSymlinks() throws Exception {
+    Path newPackagePath = pkgPath.getRelative("path/to/pkg");
+    makeEmptyPackage(newPackagePath);
+
+    pkgPath.getRelative("symlinks").createDirectoryAndParents();
+    FileSystemUtils.ensureSymbolicLink(pkgPath.getRelative("symlinks/deeplink"), newPackagePath);
+    FileSystemUtils.ensureSymbolicLink(pkgPath.getRelative("shallowlink"), newPackagePath);
+
+    assertSubpackageMatches("**", "a2/b2", "symlinks/deeplink", "path/to/pkg", "shallowlink");
+    assertSubpackageMatches("*", "shallowlink");
+
+    assertSubpackageMatches("symlinks/**", "symlinks/deeplink");
+    assertSubpackageMatches("symlinks/*", "symlinks/deeplink");
+  }
 }