fs: stop stat()ing every entry in recursive readdir · nodejs/node@262f0ec · GitHub
Skip to content

Commit 262f0ec

Browse files
codebytereaduh95
codebytere
authored and
aduh95
committed
fs: stop stat()ing every entry in recursive readdir
readdir({ recursive: true }) asked the binding for names only and then called internalModuleStat() on every entry to find the directories to descend into; with withFileTypes it built the Dirents and still stat()ed every entry that was not already a directory. Both variants also ran path.join() and path.relative() per entry to build the relative result. Ask the binding for file types in all cases, descend into directories directly, and only stat() symbolic links and entries of unknown type (which is what could point to a directory). The relative name is the parent's prefix plus the entry name. Results, their order and the symlink-following behavior are unchanged for fs.readdirSync, fs.readdir and fs.promises.readdir. The known_issues test for Buffer paths (#58892) called back without checking the error; the error now reaches the callback instead of being thrown from the completion handler, so the test asserts success to keep expressing the issue. Signed-off-by: Shelley Vohr <shelley.vohr@gmail.com> PR-URL: #65487 Reviewed-By: Yagiz Nizipli <yagiz@nizipli.com> Reviewed-By: Gürgün Dayıoğlu <hey@gurgun.day>
1 parent 5b7d02e commit 262f0ec

5 files changed

Lines changed: 112 additions & 150 deletions

File tree

‎benchmark/fs/bench-readdir.js‎

Lines changed: 4 additions & 2 deletions

‎benchmark/fs/bench-readdirSync.js‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,15 +8,17 @@ const bench = common.createBenchmark(main, {
88
n: [10],
99
dir: [ 'lib', 'test/parallel'],
1010
withFileTypes: ['true', 'false'],
11+
recursive: ['true', 'false'],
1112
});
1213

1314

14-
function main({ n, dir, withFileTypes }) {
15+
function main({ n, dir, withFileTypes, recursive }) {
1516
withFileTypes = withFileTypes === 'true';
17+
recursive = recursive === 'true';
1618
const fullPath = path.resolve(__dirname, '../../', dir);
1719
bench.start();
1820
for (let i = 0; i < n; i++) {
19-
fs.readdirSync(fullPath, { withFileTypes });
21+
fs.readdirSync(fullPath, { withFileTypes, recursive });
2022
}
2123
bench.end(n);
2224
}

‎lib/fs.js‎

Lines changed: 71 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,9 @@ const {
5757
F_OK,
5858
O_WRONLY,
5959
O_SYMLINK,
60+
UV_DIRENT_DIR,
61+
UV_DIRENT_LINK,
62+
UV_DIRENT_UNKNOWN,
6063
} = constants;
6164

6265
const pathModule = require('path');
@@ -1739,6 +1742,43 @@ function mkdirSync(path, options) {
17391742
}
17401743
}
17411744

1745+
/**
1746+
* Appends one directory's entries to `context.results` and the subdirectories
1747+
* still to visit to `context.dirs` (with the prefix their entries get in
1748+
* string results in `context.prefixes`). `result` is a `binding.readdir()`
1749+
* result with file types, so only symbolic links and entries of unknown type
1750+
* need a stat() to find out whether they lead to a directory.
1751+
* @param {string} dir
1752+
* @param {string} prefix
1753+
* @param {[string[], number[]]} result
1754+
* @param {{ withFileTypes: boolean, results: (string | Dirent)[], dirs: string[], prefixes: string[] }} context
1755+
*/
1756+
function collectRecursiveReaddirResult(dir, prefix, { 0: names, 1: types }, context) {
1757+
const { length } = names;
1758+
for (let i = 0; i < length; i++) {
1759+
const name = names[i];
1760+
const relative = prefix === '' ? name : `${prefix}${pathModule.sep}${name}`;
1761+
let isDirectory;
1762+
if (context.withFileTypes) {
1763+
const dirent = getDirent(dir, name, types[i]);
1764+
ArrayPrototypePush(context.results, dirent);
1765+
// Follow symbolic links to directories, see https://github.com/nodejs/node/issues/52663
1766+
isDirectory = dirent.isDirectory() ||
1767+
(dirent.isSymbolicLink() && binding.internalModuleStat(pathModule.join(dir, name)) === 1);
1768+
} else {
1769+
ArrayPrototypePush(context.results, relative);
1770+
const type = types[i];
1771+
isDirectory = type === UV_DIRENT_DIR ||
1772+
((type === UV_DIRENT_LINK || type === UV_DIRENT_UNKNOWN) &&
1773+
binding.internalModuleStat(pathModule.join(dir, name)) === 1);
1774+
}
1775+
if (isDirectory) {
1776+
ArrayPrototypePush(context.dirs, pathModule.join(dir, name));
1777+
ArrayPrototypePush(context.prefixes, relative);
1778+
}
1779+
}
1780+
}
1781+
17421782
/*
17431783
* An recursive algorithm for reading the entire contents of the `basePath` directory.
17441784
* This function does not validate `basePath` as a directory. It is passed directly to
@@ -1754,15 +1794,20 @@ function mkdirSync(path, options) {
17541794
function readdirRecursive(basePath, options, callback) {
17551795
const context = {
17561796
withFileTypes: Boolean(options.withFileTypes),
1757-
encoding: options.encoding,
1758-
basePath,
1759-
readdirResults: [],
1760-
pathsQueue: [basePath],
1797+
results: [],
1798+
dirs: [basePath],
1799+
prefixes: [''],
17611800
};
17621801

17631802
let i = 0;
17641803

1765-
function read(path) {
1804+
/**
1805+
* Reads one directory from `context.dirs` and then moves on to the next
1806+
* one, or calls back once none are left.
1807+
* @param {string} path
1808+
* @param {string} prefix path of this directory relative to `basePath`
1809+
*/
1810+
function read(path, prefix) {
17661811
const req = new FSReqCallback();
17671812
req.oncomplete = (err, result) => {
17681813
if (err) {
@@ -1771,68 +1816,28 @@ function readdirRecursive(basePath, options, callback) {
17711816
}
17721817

17731818
if (result === undefined) {
1774-
callback(null, context.readdirResults);
1819+
callback(null, context.results);
17751820
return;
17761821
}
17771822

1778-
processReaddirResult({
1779-
result,
1780-
currentPath: path,
1781-
context,
1782-
});
1823+
try {
1824+
collectRecursiveReaddirResult(path, prefix, result, context);
1825+
} catch (err) {
1826+
callback(err);
1827+
return;
1828+
}
17831829

1784-
if (i < context.pathsQueue.length) {
1785-
read(context.pathsQueue[i++]);
1830+
if (i < context.dirs.length) {
1831+
read(context.dirs[i], context.prefixes[i++]);
17861832
} else {
1787-
callback(null, context.readdirResults);
1833+
callback(null, context.results);
17881834
}
17891835
};
17901836

1791-
binding.readdir(
1792-
path,
1793-
context.encoding,
1794-
context.withFileTypes,
1795-
req,
1796-
);
1797-
}
1798-
1799-
read(context.pathsQueue[i++]);
1800-
}
1801-
1802-
// Calling `readdir` with `withFileTypes=true`, the result is an array of arrays.
1803-
// The first array is the names, and the second array is the types.
1804-
// They are guaranteed to be the same length; hence, setting `length` to the length
1805-
// of the first array within the result.
1806-
const processReaddirResult = (args) => (args.context.withFileTypes ? handleDirents(args) : handleFilePaths(args));
1807-
1808-
function handleDirents({ result, currentPath, context }) {
1809-
const { 0: names, 1: types } = result;
1810-
const { length } = names;
1811-
1812-
for (let i = 0; i < length; i++) {
1813-
// Avoid excluding symlinks, as they are not directories.
1814-
// Refs: https://github.com/nodejs/node/issues/52663
1815-
const fullPath = pathModule.join(currentPath, names[i]);
1816-
const dirent = getDirent(currentPath, names[i], types[i]);
1817-
ArrayPrototypePush(context.readdirResults, dirent);
1818-
1819-
if (dirent.isDirectory() || binding.internalModuleStat(fullPath) === 1) {
1820-
ArrayPrototypePush(context.pathsQueue, fullPath);
1821-
}
1837+
binding.readdir(path, options.encoding, true, req);
18221838
}
1823-
}
1824-
1825-
function handleFilePaths({ result, currentPath, context }) {
1826-
for (let i = 0; i < result.length; i++) {
1827-
const resultPath = pathModule.join(currentPath, result[i]);
1828-
const relativeResultPath = pathModule.relative(context.basePath, resultPath);
1829-
const stat = binding.internalModuleStat(resultPath);
1830-
ArrayPrototypePush(context.readdirResults, relativeResultPath);
18311839

1832-
if (stat === 1) {
1833-
ArrayPrototypePush(context.pathsQueue, resultPath);
1834-
}
1835-
}
1840+
read(context.dirs[i], context.prefixes[i++]);
18361841
}
18371842

18381843
/**
@@ -1846,35 +1851,20 @@ function handleFilePaths({ result, currentPath, context }) {
18461851
function readdirSyncRecursive(basePath, options) {
18471852
const context = {
18481853
withFileTypes: Boolean(options.withFileTypes),
1849-
encoding: options.encoding,
1850-
basePath,
1851-
readdirResults: [],
1852-
pathsQueue: [basePath],
1854+
results: [],
1855+
dirs: [basePath],
1856+
prefixes: [''],
18531857
};
18541858

1855-
function read(path) {
1856-
const readdirResult = binding.readdir(
1857-
path,
1858-
context.encoding,
1859-
context.withFileTypes,
1860-
);
1861-
1862-
if (readdirResult === undefined) {
1863-
return;
1859+
for (let i = 0; i < context.dirs.length; i++) {
1860+
const dir = context.dirs[i];
1861+
const result = binding.readdir(dir, options.encoding, true);
1862+
if (result !== undefined) {
1863+
collectRecursiveReaddirResult(dir, context.prefixes[i], result, context);
18641864
}
1865-
1866-
processReaddirResult({
1867-
result: readdirResult,
1868-
currentPath: path,
1869-
context,
1870-
});
1871-
}
1872-
1873-
for (let i = 0; i < context.pathsQueue.length; i++) {
1874-
read(context.pathsQueue[i]);
18751865
}
18761866

1877-
return context.readdirResults;
1867+
return context.results;
18781868
}
18791869

18801870
/**

‎lib/internal/fs/promises.js‎

Lines changed: 32 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,9 @@ const {
3232
O_WRONLY,
3333
S_IFMT,
3434
S_IFREG,
35+
UV_DIRENT_DIR,
36+
UV_DIRENT_LINK,
37+
UV_DIRENT_UNKNOWN,
3538
} = constants;
3639

3740
const binding = internalBinding('fs');
@@ -63,6 +66,7 @@ const {
6366
kWriteFileMaxChunkSize,
6467
},
6568
copyObject,
69+
getDirent,
6670
getDirents,
6771
getOptions,
6872
getStatFsFromBinding,
@@ -1638,73 +1642,37 @@ async function mkdir(path, options) {
16381642
}
16391643

16401644
async function readdirRecursive(originalPath, options) {
1645+
const withFileTypes = !!options.withFileTypes;
1646+
const readdirWithTypes = (path) => PromisePrototypeThen(
1647+
binding.readdir(path, options.encoding, true, kUsePromises),
1648+
undefined,
1649+
handleErrorFromBinding,
1650+
);
16411651
const result = [];
1642-
const queue = [
1643-
[
1644-
originalPath,
1645-
await PromisePrototypeThen(
1646-
binding.readdir(
1647-
originalPath,
1648-
options.encoding,
1649-
!!options.withFileTypes,
1650-
kUsePromises,
1651-
),
1652-
undefined,
1653-
handleErrorFromBinding,
1654-
),
1655-
],
1656-
];
1657-
1658-
1659-
if (options.withFileTypes) {
1660-
while (queue.length > 0) {
1661-
// If we want to implement BFS make this a `shift` call instead of `pop`
1662-
const { 0: path, 1: readdir } = ArrayPrototypePop(queue);
1663-
for (const dirent of getDirents(path, readdir)) {
1652+
const queue = [[originalPath, '', await readdirWithTypes(originalPath)]];
1653+
1654+
while (queue.length > 0) {
1655+
// If we want to implement BFS make this a `shift` call instead of `pop`
1656+
const { 0: path, 1: prefix, 2: { 0: names, 1: types } } = ArrayPrototypePop(queue);
1657+
for (let i = 0; i < names.length; i++) {
1658+
const name = names[i];
1659+
const relative = prefix === '' ? name : `${prefix}${pathModule.sep}${name}`;
1660+
let isDirectory;
1661+
if (withFileTypes) {
1662+
const dirent = getDirent(path, name, types[i]);
16641663
ArrayPrototypePush(result, dirent);
1665-
if (dirent.isDirectory()) {
1666-
const direntPath = pathModule.join(path, dirent.name);
1667-
ArrayPrototypePush(queue, [
1668-
direntPath,
1669-
await PromisePrototypeThen(
1670-
binding.readdir(
1671-
direntPath,
1672-
options.encoding,
1673-
true,
1674-
kUsePromises,
1675-
),
1676-
undefined,
1677-
handleErrorFromBinding,
1678-
),
1679-
]);
1680-
}
1664+
isDirectory = dirent.isDirectory();
1665+
} else {
1666+
ArrayPrototypePush(result, relative);
1667+
// Entries that are, or may be, symbolic links to directories are followed.
1668+
const type = types[i];
1669+
isDirectory = type === UV_DIRENT_DIR ||
1670+
((type === UV_DIRENT_LINK || type === UV_DIRENT_UNKNOWN) &&
1671+
binding.internalModuleStat(pathModule.join(path, name)) === 1);
16811672
}
1682-
}
1683-
} else {
1684-
while (queue.length > 0) {
1685-
const { 0: path, 1: readdir } = ArrayPrototypePop(queue);
1686-
for (const ent of readdir) {
1687-
const direntPath = pathModule.join(path, ent);
1688-
const stat = binding.internalModuleStat(direntPath);
1689-
ArrayPrototypePush(
1690-
result,
1691-
pathModule.relative(originalPath, direntPath),
1692-
);
1693-
if (stat === 1) {
1694-
ArrayPrototypePush(queue, [
1695-
direntPath,
1696-
await PromisePrototypeThen(
1697-
binding.readdir(
1698-
direntPath,
1699-
options.encoding,
1700-
false,
1701-
kUsePromises,
1702-
),
1703-
undefined,
1704-
handleErrorFromBinding,
1705-
),
1706-
]);
1707-
}
1673+
if (isDirectory) {
1674+
const direntPath = pathModule.join(path, name);
1675+
ArrayPrototypePush(queue, [direntPath, relative, await readdirWithTypes(direntPath)]);
17081676
}
17091677
}
17101678
}

‎test/known_issues/test-fs-readdir-recursive-with-buffer.js‎

Lines changed: 1 addition & 1 deletion

0 commit comments

Comments
 (0)