Review requested:

• @nodejs/test_runner

CC @isaacs @nodejs/test_runner

@isaacs might have good feedback on this too

Took a quick pass over it. I agree this is a good start. Tried to highlight a few issues that will likely be gotchas for Windows users.

This boils down to essentially the same algorithm that node-glob used until the recent rewrite; walk down the pattern adding each possible match to the task queue until it runs out. It's punishingly slow for advanced use cases and large folder trees. I definitely recommend a more advanced approach to caching and folder walking like what node-glob uses before making this available on the user-facing fs.glob. But good enough for this use case, and fewer moving parts.

This boils down to essentially the same algorithm that node-glob used until the recent rewrite

So . . . why wouldn’t we just import the latest version of node-glob?

So . . . why wouldn’t we just import the latest version of node-glob?

node-glob has many dependencies I am not sure we need/want in core, and it supports many options not really needed.
in addition, it also has issues raised on the PR vendoring minimatch - it does not use primordials and it does not use node errors.

I definitely recommend a more advanced approach to caching and folder walking

@isaacs I went over the code and I am not really sure what better caching and folder walking can be done, can you elaborate?

node-glob has many dependencies I am not sure we need/want in core, and it supports many options not really needed.
in addition, it also has issues raised on the PR vendoring minimatch - it does not use primordials and it does not use node errors.

If the (ultimate, not present) goal is to expose an fs.glob() functionality that's suitable for general purpose usage, then yes, pulling in node-glob is the way to go. (Fast-glob is another good option, but I think the hazards of diverging from posix shell semantics are probably not worth the increase in performance.)

node-glob is, at its core, path-scurry + minimatch. It uses minipass for streams and iteration, because it's the most performant way to do that, but streams could be swapped out (albeit at the loss of performance and synchronous streaming) with core streams, and iteration could be swapped out (with a significant performance penalty) with plain old JS generators. The dependencies on jackspeak and foreground-child are just for the glob CLI, but that probably shouldn't be included in node core.

The only thing that path-scurry depends on is lru-cache, which is just a very fast cache that prevents it from OOMing if you try to walk a directory with a million files and directories in it. (The child nodes created to reflect fs.readdir results are stored in the cache rather than attached directly to the parent object, which also helps prevent gc pauses from getting abusively long just by virtue of walking a very large object graph.)

@isaacs I went over the code and I am not really sure what better caching and folder walking can be done, can you elaborate?

Sure. In this approach, there's a queue of tasks which are effectively a tuple of {pattern, path}. (pattern is really "minimatch set + index", but same idea.) And then, serially, it walks over the task queue, adding new tasks for all the child entries if there's more pattern to be found there.

This blows up combinatorially in many common patterns. For example, consider: a/**/b/**/*/x.js, so we start with just that in the task queue.

Starting at the a folder, evaluating that pattern, we have a **, so we need to evaluate both the patterns **/b/**/*/x.js and b/**/*/x.js (since ** can match against nothing). Say that a has 3 children, a, b, and c. For each of those, we create 2 tasks, one for **/b/**/*/x.js and b/**/*/x.js. So now there's 6 more tasks in the queue, total of 7. Say that each of those have 2 children, so there's a/a/x, a/a/y, a/b/x, a/b/y, a/c/x, and a/c/y. For each of those, we need to test both **/b/**/*/x.js and b/**/*/x.js, so 12 more items in the queue, or 19 unprocessed items just to walk down the first part of a 1-3-2 tree. And we haven't even gotten to the second **. So, even though you're caching stats and readdirs, and not testing the same pattern against the same folder multiple times, it's still blowing up to a lot of unnecessary iterations. And, if a/b/c/x.js matches, you still have to process all the other patterns that could potentially match it.

That this is happening synchronously rather than in parallel, and making extra lstat calls rather than using the Dirents from readdir, makes it worse. Of course, that's maybe fine for this specific use case for the test runner, and easy enough to correct later.

The approach that both fast-glob and node-glob use is, instead of processing a queue of tasks each related to a single pattern and folder, is keep a set of patterns that might be applicable to a given path, and then just do a very efficient folder walk. Node-glob has full support for .. appearing in the pattern, so there are cases where it needs to back up the walk to the parent dir (which does some extra work, potentially processing a path a second time, so it loses some perf in exchange for that bit of correctness).

The caching approach implemented by path-scurry is also significantly more comprehensive and defensive. Within a given path-scurry object, it is nearly impossible to accidentally call lstat or readdir more than once on a given path. (Unless you have over 16*1024 items, in which case fs.readdir may have to be called again, because the cached items will be dropped to prevent OOM.) Path-scurry also caches resolve() calls, which in hot path globbing, will end up soaking up a lot of CPU cycles, since it's common to end up resolving a lot of the same paths over and over again, even if you're clever enough to avoid matching the same pattern against that resolved path.

There's nothing wrong necessarily with just caching each thing in its own standalone object or whatever, but path-scurry evolved from the frustration of juggling all these things and just wanting a simple read-only view of the filesystem which could guarantee that it would only perform the bare minimum of system operations required, and cache everything for the duration of the operation. Once you do take the step of parallelizing the walk, it becomes increasingly challenging to keep it all straight otherwise.

More precise in unrolled pseudocode:

1
path = a
pattern = **/b/**/*/x.js
queue = []
# add non-globstar form to queue
queue = [ {a, b/**/*/x.js} ]
children=[a b c]
queue = [
  {a, b/**/*/x.js}
  {a/a, **/b/**/*/x.js}
  {a/b, **/b/**/*/x.js}
  {a/c, **/b/**/*/x.js}
]
2
# shift queue
path = a
pattern = b/**/*/x.js
queue = [
  {a/a, **/b/**/*/x.js}
  {a/b, **/b/**/*/x.js}
  {a/c, **/b/**/*/x.js}
]
# string type, join and push
queue = [
  {a/a, **/b/**/*/x.js}
  {a/b, **/b/**/*/x.js}
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
]
3
# shift queue
path = a/a
pattern = **/b/**/*/x.js
# add non-globstar form to queue
queue = [
  {a/b, **/b/**/*/x.js}
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
]
children = [x y]
queue = [
  {a/b, **/b/**/*/x.js}
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
]
4
# shift queue
path = a/b
pattern = **/b/**/*/x.js
queue = [
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
]
# add non-globstar form to queue
queue = [
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
  {a/b, b/**/*/x.js}
]
children = [x y]
queue = [
  {a/c, **/b/**/*/x.js}
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
  {a/b, b/**/*/x.js}
  {a/b/y, **/b/**/*/x.js}
  {a/b/x, **/b/**/*/x.js}
]
5
# shift queue
path = a/c
pattern = **/b/**/*/x.js
queue = [
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
  {a/b, b/**/*/x.js}
  {a/b/y, **/b/**/*/x.js}
  {a/b/x, **/b/**/*/x.js}
]
# add non-globstar form to queue
queue = [
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
  {a/b, b/**/*/x.js}
  {a/b/y, **/b/**/*/x.js}
  {a/b/x, **/b/**/*/x.js}
  {a/c, b/**/*/x.js}
]
children = [x y]
queue = [
  {a/b, **/*/x.js}
  {a/a, b/**/*/x.js}
  {a/a/y, **/b/**/*/x.js}
  {a/a/x, **/b/**/*/x.js}
  {a/b, b/**/*/x.js}
  {a/b/y, **/b/**/*/x.js}
  {a/b/x, **/b/**/*/x.js}
  {a/c, b/**/*/x.js}
  {a/c/x, **/b/**/*/x.js}
  {a/c/y, **/b/**/*/x.js}
]
5 done so far, 10 tasks in the queue

So, for small folder trees, yeah, it's fine, because it can't get all that big without child nodes to have to process. But if you wanted to use it for any kind of large or time-sensitive job, the overhead will really start to hurt, because the number of required tests goes up so much faster than the number of items in the tree.

Conversely, by associating all the patterns relevant at a given point in the walk, you only have to visit each path once (barring unavoidable .. patterns), meaning all that path joining and children lookups only have to happen once, and associate all the possibly matching patterns with each child.

1
path = a
patterns = [**/b/**/*/x.js]
# add non-globstar form
patterns = [**/b/**/*/x.js, b/**/*/x.js]
queue = []
children = [a b c]
# filter down to the possibly matching patterns for each
queue = [
  {a/a, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/b, [**/b/**/*/x.js, **/*/x.js, b/**/*/x.js, */x.js]}
  {a/c, [**/b/**/*/x.js, b/**/*/x.js]}
]
2
path = a/a
patterns = [**/b/**/*/x.js, b/**/*/x.js]
queue = [
  {a/b, [**/b/**/*/x.js, **/*/x.js, b/**/*/x.js, */x.js]}
  {a/c, [**/b/**/*/x.js, b/**/*/x.js]}
]
children = [x y]
queue = [
  {a/b, [**/b/**/*/x.js, **/*/x.js, b/**/*/x.js, */x.js]}
  {a/c, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/x, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/y, [**/b/**/*/x.js, b/**/*/x.js]}
]
3
path = a/b
patterns = [**/b/**/*/x.js, **/*/x.js, b/**/*/x.js, */x.js]
queue = [
  {a/c, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/x, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/y, [**/b/**/*/x.js, b/**/*/x.js]}
]
children = [x y]
queue = [
  {a/c, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/x, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/y, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/b/x, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
  {a/b/y, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
]
4
path = a/c
patterns = [**/b/**/*/x.js, b/**/*/x.js]
queue = [
  {a/a/x, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/y, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/b/x, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
  {a/b/y, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
]
children = [x y]
queue = [
  {a/a/x, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/a/y, [**/b/**/*/x.js, b/**/*/x.js]}
  {a/b/x, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
  {a/b/y, [**/b/**/*/x.js, b/**/*/x.js, **/*/x.js, */x.js, x.js]}
  {a/c/x, [**/b/**/*/x.js, b/**/*/x.js]}

By filtering the pattern set down (and, in the case of globstar, potentially increasing it as well) at each iteration, you prevent the need to (almost) ever process the same path more than once, and it becomes a lot easier to reason about making it parallel.

The thing that node-glob uses to calculate which patterns are needed for each walk step, and the matches that should be recorded for each, is: https://github.com/isaacs/node-glob/blob/main/src/processor.ts

Note that there's also some special rules for when globstar is allowed to follow a symbolic link.

in addition, it also has issues raised on the PR vendoring minimatch - it does not use primordials and it does not use node errors.

I'm actively eager to use node errors when possible, I know @cjihrig is looking into making that more exposed for userland code.

I've got a polyfill for primordials that seems to work, but I haven't gotten around to porting path-scurry to use it. I figure that's the best first test, since path-scurry is almost zero-dep, and has a good suite of benchmarks to see whether the perf impact is too bad. If path-scurry, lru-cache, and minimatch all can be ported to use primordials without too much of a performance impact, then I think porting glob is going to be pretty easy. But that might be a pretty big "if".

@isaacs thanks for the detailed response. I will go over it later.
if there is anything I can do to help to get primordials in glob and minimatch LMK.
regarding errors I think that is a smaller issue but @cjihrig has closed the issue requesting to expose internal errors

This will enable interop with TypeScript, right? i.e.

node --test --loader=ts-node/esm "test/**/*.ts"

Just asking to be sure the requirement on file extensions being .js/.cjs/.mjs is gone after this PR :)

Thanks for all your hard work on the test runner @MoLow !

Amazing, thanks for this PR @MoLow and everyone else involved!

Does this go anywhere in the direction of getting --watch-path glob support?

• Support file globs with --watch-path #45182

Extremely unfortunate this can’t be backported to v20.

this is already part of v20

this is already part of v20

This only went out with v21 and it's semver-major, so cannot be backported to v20. Am I missing something?

this is already part of v20

I'm trying to use this change in V20.8 but it apparently doesn't seem to understand the glob pattern in node --experimental-test-coverage --import tsx --test './src/**/*.test.ts'

It gives me "Could not find ", am I missing something?