GeezerVison

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.

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

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]}

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 !

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?