vfs: support recursive readdir in ZipProvider · nodejs/node@9656992 · GitHub
Skip to content

Commit 9656992

Browse files
pipobscureaduh95
pipobscure
authored and
aduh95
committed
vfs: support recursive readdir in ZipProvider
ZipProvider threw ERR_METHOD_NOT_IMPLEMENTED for readdir() with `{ recursive: true }`, although an archive already stores every member under its full path, so a recursive listing is the same scan of the entry names as a flat one, keeping the whole path below the directory instead of only its first segment. List every member below the directory, and every directory their paths pass through, whether the archive holds an entry for it or only implies it. Names are relative to the listed directory and joined with `/`, as MemoryProvider returns them, so VirtualFileSystem reports the right parentPath for each Dirent. A name that is both a member and a directory is listed once, as a directory, as a flat listing already did. The entries are now collected in a map rather than looked up in an array, so listing a directory no longer takes time quadratic in the number of its children. Signed-off-by: Philipp Dunkel <pip@pipobscure.com> PR-URL: #66127 Reviewed-By: James M Snell <jasnell@gmail.com> Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
1 parent 9fd0a10 commit 9656992

4 files changed

Lines changed: 113 additions & 36 deletions

File tree

‎doc/api/vfs.md‎

Lines changed: 5 additions & 5 deletions

‎lib/internal/vfs/providers/ziparchive.js‎

Lines changed: 20 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
'use strict';
22

33
const {
4-
ArrayPrototypeIndexOf,
54
ArrayPrototypePush,
65
MathMax,
76
MathMin,
87
Number,
8+
SafeMap,
99
StringPrototypeIndexOf,
1010
StringPrototypeSlice,
1111
StringPrototypeStartsWith,
@@ -17,7 +17,6 @@ const { Buffer } = require('buffer');
1717
const {
1818
codes: {
1919
ERR_INVALID_ARG_TYPE,
20-
ERR_METHOD_NOT_IMPLEMENTED,
2120
},
2221
} = require('internal/errors');
2322
const { VirtualProvider } = require('internal/vfs/provider');
@@ -457,44 +456,42 @@ class ZipProvider extends VirtualProvider {
457456
if (!stats.isDirectory()) throw createENOTDIR('scandir', path);
458457
const prefix = name === '' ? '' : `${name}/`;
459458
const withFileTypes = options?.withFileTypes === true;
460-
const names = [];
461-
const isDir = [];
459+
const recursive = options?.recursive === true;
460+
// Each listed path, relative to the directory, mapped to whether it is a
461+
// directory.
462+
const children = new SafeMap();
462463
for (const key of this.#source.keys()) {
463464
if (!StringPrototypeStartsWith(key, prefix)) continue;
464465
const rest = StringPrototypeSlice(key, prefix.length);
465-
if (rest === '') continue; // The directory's own explicit entry
466-
const slash = StringPrototypeIndexOf(rest, '/');
467-
const childName = slash === -1 ? rest : StringPrototypeSlice(rest, 0, slash);
468-
const childIsDir = slash !== -1;
469-
const existingIndex = ArrayPrototypeIndexOf(names, childName);
470-
if (existingIndex !== -1) {
471-
if (childIsDir) isDir[existingIndex] = true;
472-
continue;
466+
// An archive need not hold entries for the directories above a member,
467+
// so every directory the member's path passes through is listed too.
468+
let start = 0;
469+
let slash = StringPrototypeIndexOf(rest, '/');
470+
while (slash !== -1) {
471+
children.set(StringPrototypeSlice(rest, 0, slash), true);
472+
if (!recursive) break;
473+
start = slash + 1;
474+
slash = StringPrototypeIndexOf(rest, '/', start);
475+
}
476+
if (slash === -1 && start < rest.length && !children.has(rest)) {
477+
children.set(rest, false);
473478
}
474-
ArrayPrototypePush(names, childName);
475-
ArrayPrototypePush(isDir, childIsDir);
476479
}
477480
const result = [];
478-
for (let i = 0; i < names.length; i++) {
481+
for (const { 0: childName, 1: isDir } of children) {
479482
if (withFileTypes) {
480-
ArrayPrototypePush(result, new Dirent(names[i], isDir[i] ? UV_DIRENT_DIR : UV_DIRENT_FILE, name));
483+
ArrayPrototypePush(result, new Dirent(childName, isDir ? UV_DIRENT_DIR : UV_DIRENT_FILE, name));
481484
} else {
482-
ArrayPrototypePush(result, names[i]);
485+
ArrayPrototypePush(result, childName);
483486
}
484487
}
485488
return result;
486489
}
487490
async readdir(path, options) {
488-
if (options?.recursive) {
489-
throw new ERR_METHOD_NOT_IMPLEMENTED('readdir with { recursive: true } on a ZipProvider');
490-
}
491491
const name = normalize(path);
492492
return this.#readdirEntries(path, name, options, await this.stat(path));
493493
}
494494
readdirSync(path, options) {
495-
if (options?.recursive) {
496-
throw new ERR_METHOD_NOT_IMPLEMENTED('readdirSync with { recursive: true } on a ZipProvider');
497-
}
498495
const name = normalize(path);
499496
return this.#readdirEntries(path, name, options, this.statSync(path));
500497
}

‎test/parallel/test-vfs-zip-provider-readdir-recursive.js‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
// Flags: --experimental-vfs
2+
'use strict';
3+
4+
// A recursive readdir() of a ZipProvider lists every member below the
5+
// directory, together with every directory their paths pass through, whether
6+
// or not the archive holds an entry for it.
7+
8+
const common = require('../common');
9+
const assert = require('assert');
10+
const fs = require('fs');
11+
const path = require('path');
12+
const zlib = require('zlib');
13+
const vfs = require('node:vfs');
14+
15+
async function buildArchive(entries) {
16+
const chunks = [];
17+
for await (const chunk of zlib.createZipArchive(entries)) chunks.push(chunk);
18+
return Buffer.concat(chunks);
19+
}
20+
21+
(async () => {
22+
const archive = await buildArchive([
23+
await zlib.ZipEntry.create('top.txt', Buffer.from('top')),
24+
// Directories only implied by a member's path, several levels deep.
25+
await zlib.ZipEntry.create('a/b/c/deep.txt', Buffer.from('deep')),
26+
// An explicit directory entry, before and after members inside it.
27+
await zlib.ZipEntry.create('a/b/', Buffer.alloc(0)),
28+
await zlib.ZipEntry.create('a/b/sibling.txt', Buffer.from('sibling')),
29+
await zlib.ZipEntry.create('empty/', Buffer.alloc(0)),
30+
]);
31+
const provider = new vfs.ZipProvider(new zlib.ZipBuffer(archive));
32+
33+
const all = [
34+
'a', 'a/b', 'a/b/c', 'a/b/c/deep.txt', 'a/b/sibling.txt', 'empty', 'top.txt',
35+
];
36+
const dirs = new Set(['a', 'a/b', 'a/b/c', 'empty']);
37+
38+
// Each directory is listed once, whether implied, explicit, or both.
39+
assert.deepStrictEqual(provider.readdirSync('/', { recursive: true }).sort(), all);
40+
assert.deepStrictEqual((await provider.readdir('/', { recursive: true })).sort(), all);
41+
42+
const dirents = provider.readdirSync('/', { recursive: true, withFileTypes: true });
43+
assert.deepStrictEqual(dirents.map((d) => d.name).sort(), all);
44+
for (const dirent of dirents) {
45+
assert.strictEqual(dirent.isDirectory(), dirs.has(dirent.name), dirent.name);
46+
assert.strictEqual(dirent.isFile(), !dirs.has(dirent.name), dirent.name);
47+
}
48+
49+
// Listing a subdirectory yields paths relative to it.
50+
assert.deepStrictEqual(provider.readdirSync('/a/b', { recursive: true }).sort(),
51+
['c', 'c/deep.txt', 'sibling.txt']);
52+
assert.deepStrictEqual(provider.readdirSync('/empty', { recursive: true }), []);
53+
assert.throws(() => provider.readdirSync('/top.txt', { recursive: true }),
54+
{ code: 'ENOTDIR' });
55+
assert.throws(() => provider.readdirSync('/missing', { recursive: true }),
56+
{ code: 'ENOENT' });
57+
58+
// A non-recursive listing is unchanged.
59+
assert.deepStrictEqual(provider.readdirSync('/').sort(), ['a', 'empty', 'top.txt']);
60+
assert.deepStrictEqual(provider.readdirSync('/a/b').sort(), ['c', 'sibling.txt']);
61+
62+
// A name that is both a member and a directory is listed as a directory.
63+
{
64+
const clash = new vfs.ZipProvider(new zlib.ZipBuffer(await buildArchive([
65+
await zlib.ZipEntry.create('x', Buffer.from('file')),
66+
await zlib.ZipEntry.create('x/y.txt', Buffer.from('nested')),
67+
])));
68+
const entries = clash.readdirSync('/', { recursive: true, withFileTypes: true });
69+
assert.deepStrictEqual(entries.map((d) => [d.name, d.isDirectory()]).sort(),
70+
[['x', true], ['x/y.txt', false]]);
71+
}
72+
73+
// Through node:fs, each Dirent reports its own parent directory.
74+
{
75+
const archiveVfs = vfs.create(provider);
76+
const mountPoint = archiveVfs.mount();
77+
const listed = fs.readdirSync(mountPoint, { recursive: true, withFileTypes: true })
78+
.map((d) => path.join(d.parentPath, d.name)).sort();
79+
assert.deepStrictEqual(listed, all.map((p) => path.join(mountPoint, p)).sort());
80+
assert.deepStrictEqual(fs.readdirSync(mountPoint, { recursive: true }).sort(), all);
81+
archiveVfs.unmount();
82+
}
83+
})().then(common.mustCall());

‎test/parallel/test-vfs-zip-provider.js‎

Lines changed: 5 additions & 8 deletions

0 commit comments

Comments
 (0)