/**
* Tree — content-addressable directory hashing for hyper-overlay
*
* A tree is a canonical serialization of a directory's immediate entries.
* Each entry is one of: file, subdirectory, symlink. The tree's identity
* is blake2b-256 of its canonical bytes.
*
* Format (P.10 Phase 0.5a):
*
* tree := "pgh-tree-1\n" ||
* varint(n_entries) ||
* entry[0] || ... || entry[n-1]
*
* entry := u8(kind) || // 0=file, 1=dir, 2=symlink
* u8(exec) || // 0 or 1; always 0 for dir/symlink
* varint(name_len) || name || // UTF-8 NFC, no NUL, no "/"
* 32_bytes(child_hash)
*
* tree_hash := blake2b-256(tree_bytes)
*
* Identity fields (in the hash): kind, exec-bit, name, child_hash.
* Explicitly excluded: mtime, size, uid/gid, full mode.
*
* Entries MUST be sorted byte-wise by name (after NFC normalization).
* Encoders emit sorted; decoders reject unsorted trees.
*
* Symlinks: child_hash = blake2b-256 of the target path bytes (not followed).
* Empty directories: zero-entry tree, valid, deterministic.
*/
import fs from '#fs'
import path from '#path'
import crypto from 'hypercore-crypto'
import c from 'compact-encoding'
// ── Constants ─────────────────────────────────────────────────
export const MAGIC = Buffer.from('pgh-tree-1\n', 'utf8')
export const KIND_FILE = 0
export const KIND_DIR = 1
export const KIND_SYMLINK = 2
// Windows reserved device names (case-insensitive, with or without extension)
const WINDOWS_RESERVED = new Set([
'CON', 'PRN', 'AUX', 'NUL',
'COM1', 'COM2', 'COM3', 'COM4', 'COM5', 'COM6', 'COM7', 'COM8', 'COM9',
'LPT1', 'LPT2', 'LPT3', 'LPT4', 'LPT5', 'LPT6', 'LPT7', 'LPT8', 'LPT9'
])
// Chars forbidden in filenames on Windows (beyond format-layer rules)
// eslint-disable-next-line no-control-regex
const WINDOWS_FORBIDDEN = /[\\:*?"<>|\x00-\x1f]/
// Default skip list for walkTree — minimal, just obvious platform cruft.
// Consumers that want more (e.g. .git for pgh publish) pass their own.
export const DEFAULT_SKIP = new Set(['.DS_Store', 'Thumbs.db'])
// ── Name validation (format layer) ────────────────────────────
/**
* Normalize a filename for hashing and validate format-layer rules.
* Throws on unrepresentable names. Returns the canonical form.
*
* @param {string} name - single path component (no "/")
* @returns {string} NFC-normalized name
*/
export function normalizeName (name) {
if (typeof name !== 'string') {
throw new Error('tree entry name must be string, got ' + typeof name)
}
if (name.length === 0) {
throw new Error('tree entry name cannot be empty')
}
if (name === '.' || name === '..') {
throw new Error('tree entry name cannot be "." or ".."')
}
if (name.indexOf('/') !== -1) {
throw new Error('tree entry name cannot contain "/": ' + JSON.stringify(name))
}
if (name.indexOf('\x00') !== -1) {
throw new Error('tree entry name cannot contain NUL: ' + JSON.stringify(name))
}
const normalized = name.normalize('NFC')
// Verify the normalized form is valid UTF-8 that round-trips through
// Buffer (catches lone surrogates and other malformed sequences).
const asBytes = Buffer.from(normalized, 'utf8')
if (asBytes.toString('utf8') !== normalized) {
throw new Error('tree entry name is not valid UTF-8: ' + JSON.stringify(name))
}
return normalized
}
// ── Consumer-policy layer ─────────────────────────────────────
/**
* Check a name against Windows compatibility rules.
* Does NOT throw — returns a reason string (or null if the name is OK).
* Used by pgh publish for strict cross-platform validation.
*
* @param {string} name
* @returns {string|null} reason if incompatible, null if OK
*/
export function windowsIncompatibleReason (name) {
if (WINDOWS_FORBIDDEN.test(name)) {
return 'contains Windows-forbidden character (\\:*?"<>| or control code)'
}
const trimmed = name.replace(/\.+$/, '').replace(/ +$/, '')
if (trimmed !== name) {
return 'trailing "." or space (Windows strips these silently)'
}
// Reserved device names apply with any extension: AUX.log, PRN.txt etc.
const base = name.split('.')[0].toUpperCase()
if (WINDOWS_RESERVED.has(base)) {
return `"${base}" is a reserved Windows device name (even with extension)`
}
return null
}
// ── Canonical encoding ────────────────────────────────────────
/**
* Encode a single entry to its canonical byte representation.
*
* @param {object} state - compact-encoding state
* @param {{kind: number, exec: number, name: string, childHash: Buffer|string}} e
*/
function encodeEntry (state, e) {
if (e.kind !== KIND_FILE && e.kind !== KIND_DIR && e.kind !== KIND_SYMLINK) {
throw new Error('invalid entry kind: ' + e.kind)
}
if (e.exec !== 0 && e.exec !== 1) {
throw new Error('entry exec must be 0 or 1')
}
if (e.kind !== KIND_FILE && e.exec !== 0) {
throw new Error('non-file entry must have exec=0')
}
const hash = toBuffer32(e.childHash)
c.uint8.encode(state, e.kind)
c.uint8.encode(state, e.exec)
c.string.encode(state, e.name) // compact-encoding: varint len + utf8 bytes
state.buffer.set(hash, state.start)
state.start += 32
}
function preencodeEntry (state, e) {
c.uint8.preencode(state, e.kind)
c.uint8.preencode(state, e.exec)
c.string.preencode(state, e.name)
state.end += 32
}
/**
* Serialize a list of entries to canonical tree bytes.
* Entries are sorted + normalized as a side-effect of the call.
*
* @param {Array<{kind: number, exec: number, name: string, childHash: Buffer|string}>} entries
* @returns {Buffer}
*/
export function encodeTree (entries) {
const normalized = entries.map(e => ({
kind: e.kind,
exec: e.exec || 0,
name: normalizeName(e.name),
childHash: e.childHash
}))
normalized.sort(compareEntries)
// Sanity: no duplicate names after normalization
for (let i = 1; i < normalized.length; i++) {
if (normalized[i].name === normalized[i - 1].name) {
throw new Error('duplicate entry name after NFC normalization: ' + normalized[i].name)
}
}
const state = { start: 0, end: 0, buffer: null }
state.end += MAGIC.length
c.uint.preencode(state, normalized.length)
for (const e of normalized) preencodeEntry(state, e)
state.buffer = Buffer.alloc(state.end)
state.buffer.set(MAGIC, state.start)
state.start += MAGIC.length
c.uint.encode(state, normalized.length)
for (const e of normalized) encodeEntry(state, e)
return state.buffer
}
/**
* Byte-wise comparator for entry names (after NFC normalization).
*/
function compareEntries (a, b) {
const ab = Buffer.from(a.name, 'utf8')
const bb = Buffer.from(b.name, 'utf8')
return Buffer.compare(ab, bb)
}
/**
* Decode canonical tree bytes back to an entries list.
* Rejects unsorted or malformed trees.
*
* @param {Buffer} buf
* @returns {Array<{kind: number, exec: number, name: string, childHash: string}>}
*/
export function decodeTree (buf) {
if (!Buffer.isBuffer(buf)) throw new Error('decodeTree expects a Buffer')
if (buf.length < MAGIC.length) throw new Error('tree too short')
if (buf.compare(MAGIC, 0, MAGIC.length, 0, MAGIC.length) !== 0) {
throw new Error('tree magic mismatch (expected "pgh-tree-1")')
}
const state = { start: MAGIC.length, end: buf.length, buffer: buf }
const count = c.uint.decode(state)
const entries = []
let prevName = null
for (let i = 0; i < count; i++) {
const kind = c.uint8.decode(state)
const exec = c.uint8.decode(state)
const name = c.string.decode(state)
if (state.start + 32 > state.end) throw new Error('truncated tree: missing hash bytes')
const childHash = buf.subarray(state.start, state.start + 32).toString('hex')
state.start += 32
// Validate format rules on read — reject invalid trees rather than silently accept
const normalized = normalizeName(name)
if (normalized !== name) {
throw new Error('tree entry name not NFC-normalized: ' + JSON.stringify(name))
}
if (kind !== KIND_FILE && exec !== 0) {
throw new Error('non-file entry with exec=1 is invalid')
}
if (prevName !== null) {
const cmp = Buffer.compare(Buffer.from(prevName, 'utf8'), Buffer.from(name, 'utf8'))
if (cmp === 0) throw new Error('tree has duplicate entry: ' + name)
if (cmp > 0) throw new Error('tree entries not sorted: ' + prevName + ' before ' + name)
}
prevName = name
entries.push({ kind, exec, name, childHash })
}
if (state.start !== state.end) throw new Error('tree has trailing bytes after entries')
return entries
}
/**
* Compute the tree hash of an entries list.
*
* @param {Array<{kind: number, exec: number, name: string, childHash: Buffer|string}>} entries
* @returns {string} hex-encoded blake2b-256
*/
export function computeTreeHash (entries) {
const buf = encodeTree(entries)
return crypto.data(buf).toString('hex')
}
// ── Helpers ───────────────────────────────────────────────────
function toBuffer32 (hashOrBuf) {
if (Buffer.isBuffer(hashOrBuf)) {
if (hashOrBuf.length !== 32) throw new Error('childHash buffer must be 32 bytes')
return hashOrBuf
}
if (typeof hashOrBuf !== 'string') {
throw new Error('childHash must be Buffer or hex string')
}
if (hashOrBuf.length !== 64) throw new Error('childHash hex string must be 64 chars')
return Buffer.from(hashOrBuf, 'hex')
}
// ── Filesystem walk ───────────────────────────────────────────
/**
* Walk a directory recursively, producing tree hashes bottom-up.
*
* Returns a nested object keyed by path, where each entry has:
* { hash: hex, entries: [{kind, exec, name, childHash, size?}] }
*
* File entries carry their content hash as childHash (blake2b of bytes).
* Dir entries carry the subtree hash.
* Symlink entries carry blake2b of the link target bytes.
*
* @param {string} rootDir - absolute path to scan
* @param {object} [opts]
* @param {Set<string>} [opts.skip] - basenames to skip (default: DEFAULT_SKIP)
* @param {(relPath: string, baseName: string) => boolean} [opts.matcher]
* Optional gitignore-style matcher. Returns true to EXCLUDE an entry.
* Receives the path relative to rootDir plus the basename. Applies to
* all kinds (file/dir/symlink). Used by `pgh publish` for publishIgnore.
* @returns {Map<string, {hash: string, entries: Array, size: number}>}
* map keyed by relative path ('' = root); root tree is at key ''
*/
export function walkTree (rootDir, opts = {}) {
const skip = opts.skip || DEFAULT_SKIP
const matcher = opts.matcher || null
const trees = new Map()
function visit (relPath) {
const absPath = relPath === '' ? rootDir : path.join(rootDir, relPath)
const raw = fs.readdirSync(absPath)
const entries = []
let totalSize = 0
for (const name of raw) {
if (skip.has(name)) continue
const entryAbs = path.join(absPath, name)
const entryRel = relPath === '' ? name : relPath + '/' + name
if (matcher && matcher(entryRel, name)) continue
let stat
try {
stat = fs.lstatSync(entryAbs)
} catch {
continue
}
if (stat.isSymbolicLink()) {
const target = fs.readlinkSync(entryAbs)
const targetBytes = Buffer.from(target, 'utf8')
const childHash = crypto.data(targetBytes).toString('hex')
entries.push({
kind: KIND_SYMLINK,
exec: 0,
name: normalizeName(name),
childHash,
size: targetBytes.length,
linkTarget: target
})
totalSize += targetBytes.length
} else if (stat.isDirectory()) {
visit(entryRel)
const sub = trees.get(entryRel)
if (!sub) continue
entries.push({
kind: KIND_DIR,
exec: 0,
name: normalizeName(name),
childHash: sub.hash,
size: sub.size
})
totalSize += sub.size
} else if (stat.isFile()) {
const content = fs.readFileSync(entryAbs)
const childHash = crypto.data(content).toString('hex')
// Executable bit from stat.mode — works on POSIX; Windows always 0
const exec = (stat.mode & 0o100) ? 1 : 0
entries.push({
kind: KIND_FILE,
exec,
name: normalizeName(name),
childHash,
size: stat.size
})
totalSize += stat.size
}
// device files, sockets, fifos: silently skipped (unrepresentable)
}
entries.sort(compareEntries)
const hash = computeTreeHash(entries)
trees.set(relPath, { hash, entries, size: totalSize })
}
visit('')
return trees
}
// ── Publish-time validation (consumer policy) ─────────────────
/**
* Scan entries (recursively via walkTree output) for cross-platform-hostile
* names. Returns an array of {path, name, reason} for every problem found.
* Does NOT throw — caller decides how to present.
*
* @param {Map<string, {hash: string, entries: Array}>} trees - from walkTree
* @returns {Array<{path: string, name: string, reason: string}>}
*/
export function validateForPublish (trees) {
const problems = []
for (const [relPath, tree] of trees) {
for (const e of tree.entries) {
const reason = windowsIncompatibleReason(e.name)
if (reason) {
problems.push({
path: relPath ? relPath + '/' + e.name : e.name,
name: e.name,
reason
})
}
}
}
return problems
}