fs: fix glob early return skipping sibling entries

Project: nodejs/node | Language: JavaScript | Concepts: data-structures, algorithmic-optimization, testing-strategy | Difficulty: mid
Link: https://github.com/nodejs/node/pull/64895

The problem

The glob implementation in Node.js would sometimes skip processing some sibling directory entries if one of them had already been seen in a different pattern context. This could cause missing results depending on the directory iteration order, leading to flaky and incorrect glob results.

Why it's non-trivial

A naive fix that only checks if a path has been seen before could cause the traversal to stop processing further siblings, which is incorrect. The correct approach must ensure that all siblings are considered, and only actual reprocessing of the same path is avoided. The bug was also hard to catch because it depended on the order in which directory entries were read, making it non-deterministic and hard to test.

The approach

1. Remove the early return that skipped siblings:

The problematic code was:

-        if (this.#cache.seen(entryPath, pattern, index) || this.#cache.seen(entryPath, pattern, index + 1)) {
-          return;
-        }

This check would cause the traversal to return early for the entire method, dropping all remaining siblings if any one had been seen. The fix simply removes these lines in both the sync and async traversal methods, ensuring all siblings are processed.

2. Add a deterministic regression test:

A new test was added to test-fs-glob.mjs to pin the directory entry order and reliably trigger the bug:

+describe('glob - seen cache', function() {
+  test('does not skip siblings after a seen child path', () => {
+    // ... (setup omitted for brevity)
+    const reorder = (target, entries) => {
+      if (!Array.isArray(entries) || target !== a) return entries;
+      const names = ['c', 'b', 'x', 'z'];
+      return names.map((name) => entries.find((entry) => entry.name === name))
+        .filter(Boolean);
+    };
+    // Patch readdirSync and readdir to enforce order
+    fs.readdirSync = function(target, options) {
+      return reorder(target, originalReaddirSync.call(this, target, options));
+    };
+    fsPromises.readdir = async function(target, options) {
+      return reorder(target, await originalReaddir.call(this, target, options));
+    };
+    // ... (rest of test omitted)
+  });
+});

This test creates a directory structure and overrides the directory reading functions to force a specific order, making the bug deterministic and ensuring that all expected results are checked.

From the review thread

No notable review discussion on this PR.

Takeaways

• Avoid early returns in iterative algorithms that may skip processing of valid sibling entries; ensure each item is considered unless explicitly filtered.
• When fixing flaky bugs that depend on iteration order, write deterministic tests by controlling or mocking the order of traversal.
• Use caching and seen-path checks to prevent redundant work, but do not let them interfere with the processing of other independent paths.