/**
* The file list a vdrive is published from must be deterministic.
*
* publishTree writes files in exactly the order it is handed them, and the
* order lands in the drive's merkle tree. Measured on the real path with
* hyper-overlay's chunker, against a real 6-file release:
*
* same bytes, same order -> tree 0997c75b… (identical across stores)
* same bytes, REVERSED order -> tree dacbc54b… (1844 blocks either way)
*
* `walk()` fed that list straight from `readdir`, whose order is filesystem
* defined — hash order on ext4, and not stable across filesystems, inode
* layouts, or a directory rewritten in a different sequence.
*
* Today only one machine ever builds a drive, so nothing notices. The moment a
* second machine builds the same release — the premise of seeding by
* reproduction rather than replication — it silently produces a DIFFERENT
* drive from identical artifacts. Under a content-derived (manifest) key that
* is worse than a mismatch: two machines would claim the same key for
* different content.
*
* hyper-overlay's own tree format already requires this ("Entries MUST be
* sorted byte-wise by name"), so sorting here removes an inconsistency between
* the two layers rather than inventing a rule.
*/
import test from 'brittle'
import fs from '#node:fs'
import path from '#node:path'
import os from '#node:os'
import { walkForTest as walk, sortDriveNames } from '../lib/vdrive-publish.js'
function mktemp () {
return fs.mkdtempSync(path.join(os.tmpdir(), 'vdrive-walk-'))
}
function isByteSorted (names) {
for (let i = 1; i < names.length; i++) {
if (Buffer.compare(Buffer.from(names[i - 1]), Buffer.from(names[i])) >= 0) return false
}
return true
}
test('walk returns a byte-wise sorted list regardless of creation order', async (t) => {
const dir = mktemp()
t.teardown(() => fs.rmSync(dir, { recursive: true, force: true }))
// Created in deliberately reverse-ish order, across nested dirs, so any
// filesystem that reports creation or hash order shows it.
fs.mkdirSync(path.join(dir, 'zeta'), { recursive: true })
fs.mkdirSync(path.join(dir, 'alpha'), { recursive: true })
fs.writeFileSync(path.join(dir, 'zzz.txt'), 'z')
fs.writeFileSync(path.join(dir, 'zeta', 'b.bin'), 'zb')
fs.writeFileSync(path.join(dir, 'mmm.txt'), 'm')
fs.writeFileSync(path.join(dir, 'alpha', 'a.bin'), 'aa')
fs.writeFileSync(path.join(dir, 'aaa.txt'), 'a')
const names = await walk(dir)
t.is(names.length, 5, 'found every file')
t.ok(isByteSorted(names), 'byte-wise sorted: ' + JSON.stringify(names))
})
test('walk sorts even when readdir does not — many files', async (t) => {
const dir = mktemp()
t.teardown(() => fs.rmSync(dir, { recursive: true, force: true }))
// A handful of files can come back alphabetical by luck — ext4 returns hash
// order, which only diverges visibly once the directory is large. That luck
// is exactly why this bug stayed invisible: the real 6-file ifsrenderer
// release walks in sorted order on this machine, so nothing looked wrong.
const names = []
for (let i = 0; i < 200; i++) {
const n = 'file-' + String(i).padStart(3, '0') + '-' + 'abcdefghij'[i % 10] + '.bin'
fs.writeFileSync(path.join(dir, n), 'x')
names.push('/' + n)
}
// NB: no assertion that readdir is unsorted — ext4's hash order is
// per-directory, so that is luck and made this test flaky. The invariant
// below holds either way; sortDriveNames is tested directly for the case
// the filesystem will not reliably produce.
const walked = await walk(dir)
t.is(walked.length, 200, 'found every file')
t.ok(isByteSorted(walked), 'walk output is sorted despite readdir order')
})
test('walk is stable across two calls on the same tree', async (t) => {
const dir = mktemp()
t.teardown(() => fs.rmSync(dir, { recursive: true, force: true }))
fs.mkdirSync(path.join(dir, 'dist'), { recursive: true })
fs.mkdirSync(path.join(dir, 'by-arch', 'linux-x64'), { recursive: true })
fs.writeFileSync(path.join(dir, 'build.log'), 'log')
fs.writeFileSync(path.join(dir, 'dist', 'b.AppImage'), 'B')
fs.writeFileSync(path.join(dir, 'dist', 'a.tar.gz'), 'A')
fs.writeFileSync(path.join(dir, 'by-arch', 'linux-x64', 'app.bin'), 'X')
fs.writeFileSync(path.join(dir, 'package.json'), '{}')
const first = await walk(dir)
const second = await walk(dir)
t.alike(second, first, 'two walks agree')
t.ok(isByteSorted(first), 'and are sorted')
// The property that actually matters: a nested path sorts as a whole path,
// so the order cannot depend on which directory was descended into first.
const expected = [...first].sort((a, b) => Buffer.compare(Buffer.from(a), Buffer.from(b)))
t.alike(first, expected, 'matches an independent byte-wise sort')
})
test('sortDriveNames orders byte-wise, deterministically', (t) => {
// The case the filesystem will not reliably hand us. Deliberately scrambled,
// with nested paths, so ordering cannot depend on descent order.
const scrambled = [
'/zzz.txt', '/dist/b.AppImage', '/aaa.txt', '/by-arch/linux-x64/app.bin',
'/dist/a.tar.gz', '/manifest.json', '/Build.log'
]
const sorted = sortDriveNames(scrambled)
t.ok(isByteSorted(sorted), 'sorted: ' + JSON.stringify(sorted))
t.is(sorted.length, scrambled.length, 'nothing lost')
t.alike(sortDriveNames([...scrambled].reverse()), sorted, 'input order is irrelevant')
// Uppercase sorts before lowercase byte-wise; a locale-aware sort would not.
t.is(sorted[0], '/Build.log', 'byte-wise, not locale-aware')
})