dir-walk

#!/usr/bin/env node
/* dir-walk.js — walk a directory tree into a deterministic JSONL stream of entries.
   Dependency-free, deterministic, MIT. Runs in Node (the CLI reads the real filesystem)
   or a browser (the pure core walks an injected in-memory tree).

   WHAT IT IS. A SOURCE: it takes a directory in and emits a JSONL stream out — one record
   per file/directory found, in a stable, sorted, reproducible order — the front of a pipe
   that lets the fold/filter/transform gifts work on a filesystem:

     node dir-walk.js ./src | node schema-filter.js ...
     node dir-walk.js . --files-only --max-depth 2

   Each record is a fixed, portable shape: {"path":"src/a.js","name":"a.js","type":"file",
   "depth":1,"size":128}. It is the "give me this tree as data" adapter — a build/ops source.

   THE QUIET FAILURES IT FIXES. Everyone reaches for a recursive readdir and everyone gets
   it wrong in ways that only bite on another machine or another run:

     1. NON-DETERMINISTIC ORDER. `fs.readdirSync` returns entries in the filesystem's own
        order, which differs across OSes, filesystems, and even runs. A walk that emits in
        readdir order produces a DIFFERENT stream on every machine — un-diffable, un-
        pinnable, useless as a golden. dir-walk SORTS every directory's entries by name
        (byte order) before descending, so the same tree always yields the same stream.

     2. LEAKY, UNPORTABLE STAT. The raw `fs.Stats` object carries mtime, ino, mode, uid,
        blocks — values that change between runs and machines and would make the "same"
        tree hash differently every time. dir-walk emits only a FIXED, portable subset
        (path, name, type, depth, and size for files) — the fields that are a property of
        the tree's shape, not of the moment you looked at it. (size is opt-out with
        --no-size if you want shape-only.)

     3. SYMLINK CYCLES AND SURPRISE DESCENT. Naive recursion follows symlinks and can loop
        forever on a cycle, or wander out of the tree you meant. dir-walk does NOT follow
        symlinks by default — a symlink is reported as its own entry (type "symlink") and
        never descended — so a walk always terminates and stays inside the tree. (Depth is
        also boundable with --max-depth.)

   THE MODEL. The PURE CORE is `walk(provider, opts)`: it takes a PROVIDER (an object with
   `readdir(dirPath) -> [ {name, type} ]` sorted-or-not, `size(filePath) -> number`) and a
   root, and returns the sorted, deterministic array of entry records. The CLI supplies a
   real-filesystem provider (built-in `fs`); a test or a browser supplies an in-memory one.
   The impurity (touching the disk) lives ONLY in the provider — the walk itself is pure,
   so the same provider + opts always yield byte-identical output.

     --files-only        emit only file (and symlink) records, not directory records
     --dirs-only         emit only directory records
     --max-depth N       do not descend past depth N (root entries are depth 1)
     --no-size           omit the size field (shape-only; also skips the size() call)
     --root-name NAME    the label for the root in paths (default: the path you passed)

   DETERMINISM. walk(provider, opts) is a pure function of (provider's answers, opts). Given
   a provider that returns the same answers, the output is byte-identical on every run and
   every machine: entries are sorted by name within each directory, traversal is a stable
   pre-order (a directory record precedes its children), symlinks are not followed, and only
   portable fields are emitted. No clock, no randomness read into the OUTPUT.

   USAGE
     node dir-walk.js ./project
     node dir-walk.js . --files-only --max-depth 3
     node dir-walk.js src --no-size | node dedup-filter.js --key type
     node dir-walk.js --help

   Exit codes: 0 success (including an empty directory -> empty stream) · 2 usage error
   (unknown option, missing/duplicate root, bad --max-depth) · 3 the root does not exist or
   is not a directory. A clean one-line message on stderr, never a stack trace.

   Released under MIT. Its edge is printed in the README: dir-walk emits a SORTED, portable
   pre-order stream of {path,name,type,depth,size}. It does NOT follow symlinks (they are
   reported, never descended), does NOT emit mtime/ino/mode/uid (unportable, time-varying),
   does NOT match globs or filter by pattern (pipe into a filter gift), and does NOT read
   file CONTENTS (use line-source for that). The root record is not emitted; its children
   are depth 1.
*/
"use strict";

/* ==================================================================
   THE PURE CORE — walk(provider, opts) -> [entry, ...]
   The provider is the only impure boundary; the walk is pure.
     provider.readdir(dirPath) -> [ { name, type }, ... ]   (type: 'file'|'dir'|'symlink'|'other')
     provider.size(filePath)   -> number                    (only called for files when size wanted)
   ================================================================== */

// Join a parent path and a child name with a forward slash, normalizing so output is
// platform-independent ("src/a.js", never "src\\a.js"). Pure.
function joinPath(parent, name) {
  if (parent === "") return name;
  return parent + "/" + name;
}

// Sort directory entries by name in byte (code-unit) order — the determinism keystone.
// Pure; does not mutate the input.
function sortedByName(entries) {
  return entries.slice().sort(function (a, b) {
    if (a.name < b.name) return -1;
    if (a.name > b.name) return 1;
    return 0;
  });
}

// Build one entry record with the fixed, portable field set. Pure.
function makeRecord(relPath, name, type, depth, size) {
  var rec = { path: relPath, name: name, type: type, depth: depth };
  if (size !== undefined) rec.size = size;
  return rec;
}

// The deterministic pre-order walk. Pure function of the provider's answers and opts.
//   opts.filesOnly / opts.dirsOnly  — emit only files(+symlinks) / only dirs
//   opts.maxDepth                   — do not descend past this depth (root children = 1)
//   opts.withSize                   — include the size field for file records (default true)
//   opts.rootName                   — label for the root in paths (default "")
// Returns an array of entry records in stable pre-order (a dir precedes its children).
function walk(provider, opts) {
  opts = opts || {};
  var filesOnly = !!opts.filesOnly;
  var dirsOnly = !!opts.dirsOnly;
  var maxDepth = opts.maxDepth === undefined ? Infinity : opts.maxDepth;
  var withSize = opts.withSize === undefined ? true : !!opts.withSize;
  var rootLabel = opts.rootName === undefined ? "" : String(opts.rootName);

  if (filesOnly && dirsOnly) throw new Error("--files-only and --dirs-only are mutually exclusive");
  if (typeof maxDepth === "number" && maxDepth < 1 && maxDepth !== Infinity) {
    // maxDepth 0 means "emit nothing below root"; treat as an empty walk (root has no record)
  }

  var out = [];

  // recurse over a directory at absolute-ish `dirAbs` (what the provider understands),
  // whose path RELATIVE to the root is `relBase`, at `depth`.
  function descend(dirAbs, relBase, depth) {
    if (depth > maxDepth) return;
    var entries = sortedByName(provider.readdir(dirAbs));
    for (var i = 0; i < entries.length; i++) {
      var e = entries[i];
      var childAbs = joinPath(dirAbs, e.name);
      var childRel = joinPath(relBase, e.name);
      var type = e.type;
      if (type === "dir") {
        if (!filesOnly) out.push(makeRecord(childRel, e.name, "dir", depth));
        // descend only if within depth budget; a symlink-typed entry is never descended
        descend(childAbs, childRel, depth + 1);
      } else {
        // file, symlink, or other
        if (!dirsOnly) {
          var size = undefined; // reset each iteration (var is function-scoped; do not leak a prior file's size)
          if (withSize && type === "file") size = provider.size(childAbs);
          out.push(makeRecord(childRel, e.name, type, depth, size));
        }
      }
    }
  }

  descend(opts.__rootAbs === undefined ? "" : opts.__rootAbs, rootLabel, 1);
  return out;
}

// Render entry records as JSONL text (one JSON object per line, trailing newline per record).
function toJSONL(records) {
  var s = "";
  for (var i = 0; i < records.length; i++) s += JSON.stringify(records[i]) + "\n";
  return s;
}

/* ==================================================================
   EXPORTS (browser + Node)
   ================================================================== */
if (typeof window !== "undefined") {
  window.ForestGifts = window.ForestGifts || {};
  window.ForestGifts.dirWalk = { walk: walk, toJSONL: toJSONL, sortedByName: sortedByName };
}
if (typeof module !== "undefined" && module.exports) {
  module.exports = { walk: walk, toJSONL: toJSONL, sortedByName: sortedByName, joinPath: joinPath };
}

/* ==================================================================
   THE REAL-FILESYSTEM PROVIDER (Node CLI only) — the one impure edge
   ================================================================== */
function fsProvider(rootAbs) {
  var fs = require("fs");
  var path = require("path");
  return {
    // returns [{name, type}] for the directory; type via lstat so symlinks are seen as symlinks
    readdir: function (relDir) {
      var abs = relDir === "" ? rootAbs : path.join(rootAbs, relDir);
      var names = fs.readdirSync(abs);
      var out = [];
      for (var i = 0; i < names.length; i++) {
        var full = path.join(abs, names[i]);
        var st;
        try { st = fs.lstatSync(full); } catch (e) { st = null; }
        var type = "other";
        if (st) {
          if (st.isSymbolicLink()) type = "symlink";
          else if (st.isDirectory()) type = "dir";
          else if (st.isFile()) type = "file";
        }
        out.push({ name: names[i], type: type });
      }
      return out;
    },
    size: function (relFile) {
      var abs = relFile === "" ? rootAbs : path.join(rootAbs, relFile);
      try { return require("fs").statSync(abs).size; } catch (e) { return 0; }
    }
  };
}

/* ==================================================================
   CLI (runs only when invoked directly, never on require)
   ================================================================== */

function parseArgs(args) {
  var opts = { withSize: true };
  var root = null;
  var i = 0;
  while (i < args.length) {
    var a = args[i];
    if (a === "--files-only") { opts.filesOnly = true; i++; }
    else if (a === "--dirs-only") { opts.dirsOnly = true; i++; }
    else if (a === "--no-size") { opts.withSize = false; i++; }
    else if (a === "--max-depth") {
      var v = args[i + 1];
      if (v === undefined) throw new Error("--max-depth requires a number");
      var n = parseInt(v, 10);
      if (String(n) !== String(v).trim() || n < 0) throw new Error("--max-depth must be a non-negative integer");
      opts.maxDepth = n;
      i += 2;
    }
    else if (a === "--root-name") {
      var rn = args[i + 1];
      if (rn === undefined) throw new Error("--root-name requires a value");
      opts.rootName = rn;
      i += 2;
    }
    else if (a.charAt(0) === "-") { throw new Error("unknown option " + a); }
    else {
      if (root !== null) throw new Error("unexpected extra argument " + JSON.stringify(a) + " (dir-walk takes one root directory)");
      root = a;
      i++;
    }
  }
  if (opts.filesOnly && opts.dirsOnly) throw new Error("--files-only and --dirs-only are mutually exclusive");
  if (root === null) root = ".";
  opts.root = root;
  return opts;
}

var HELP =
  "dir-walk.js — walk a directory tree into a deterministic JSONL stream of entries.\n\n" +
  "  node dir-walk.js ./project\n" +
  "  node dir-walk.js . --files-only --max-depth 3\n" +
  "  node dir-walk.js src --no-size | node dedup-filter.js --key type\n" +
  "  node dir-walk.js --help\n\n" +
  "  --files-only    emit only file/symlink records, not directories\n" +
  "  --dirs-only     emit only directory records\n" +
  "  --max-depth N   do not descend past depth N (root's children are depth 1)\n" +
  "  --no-size       omit the size field (shape-only)\n" +
  "  --root-name NM  label for the root in emitted paths (default: none, paths are relative)\n\n" +
  "Emits one JSON object per entry: { path, name, type, depth[, size] }, entries SORTED by\n" +
  "name within each directory (deterministic across machines). Symlinks are reported but\n" +
  "never followed. Only portable fields are emitted (no mtime/ino/mode).\n\n" +
  "Edge: dir-walk does NOT follow symlinks, does NOT emit time/inode/mode, does NOT match\n" +
  "globs (pipe into a filter gift), and does NOT read file contents (use line-source).\n";

function main(argv) {
  var args = argv.slice(2);
  if (args.indexOf("--help") !== -1 || args.indexOf("-h") !== -1) {
    process.stdout.write(HELP);
    return 0;
  }
  var opts;
  try { opts = parseArgs(args); }
  catch (e) { process.stderr.write("dir-walk: " + e.message + "\n"); return 2; }

  var fs = require("fs");
  var st;
  try { st = fs.statSync(opts.root); }
  catch (e) { process.stderr.write("dir-walk: not found: " + opts.root + "\n"); return 3; }
  if (!st.isDirectory()) { process.stderr.write("dir-walk: not a directory: " + opts.root + "\n"); return 3; }

  var provider = fsProvider(opts.root);
  var records;
  try {
    records = walk(provider, {
      filesOnly: opts.filesOnly,
      dirsOnly: opts.dirsOnly,
      maxDepth: opts.maxDepth,
      withSize: opts.withSize,
      rootName: opts.rootName === undefined ? "" : opts.rootName,
      __rootAbs: ""
    });
  } catch (e) { process.stderr.write("dir-walk: " + e.message + "\n"); return 2; }

  process.stdout.write(toJSONL(records));
  return 0;
}

if (typeof require !== "undefined" && require.main === module) {
  process.exitCode = main(process.argv);
}

#!/usr/bin/env node
/* test_dir-walk.js — battery for the dir-walk gift.
   `node test_dir-walk.js` -> exit 0 PASS / non-zero FAIL.

   THE ORACLE IS INDEPENDENT AND TAKES A DIFFERENT ROUTE. The gift walks with a recursive
   pre-order descent. The oracle here does an EXPLICIT-STACK iterative pre-order, sorting
   with a hand comparator and building paths by a different accumulation — no shared code
   with the gift's recursion. Both are fed the SAME in-memory provider (a pure fixture
   tree), so the comparison is deterministic and disk-free. Plus frozen hand goldens for
   each quiet-failure case the gift exists to fix (sort order, portable-fields-only,
   symlinks-not-followed).
*/
"use strict";

var G = require("./dir-walk.js");

var pass = 0, fail = 0;
function ok(name, cond) { if (cond) { pass++; } else { fail++; console.error("FAIL: " + name); } }
function eq(name, got, want) {
  var g = JSON.stringify(got), w = JSON.stringify(want);
  if (g === w) { pass++; } else { fail++; console.error("FAIL: " + name + "\n  got:  " + g + "\n  want: " + w); }
}

/* ---- an in-memory provider builder from a nested spec --------------------- */
// spec: { name: { ... } } for a dir, { name: <size:number> } for a file, { name: "->" } symlink
// We flatten it into readdir()/size() maps.
function buildProvider(spec) {
  var dirs = {};   // dirPath -> [ {name,type} ]
  var sizes = {};  // filePath -> number
  function visit(node, relBase) {
    var entries = [];
    var keys = Object.keys(node);
    for (var i = 0; i < keys.length; i++) {
      var name = keys[i];
      var v = node[name];
      var childRel = relBase === "" ? name : relBase + "/" + name;
      if (v === "->") { entries.push({ name: name, type: "symlink" }); }
      else if (typeof v === "number") { entries.push({ name: name, type: "file" }); sizes[childRel] = v; }
      else if (v && typeof v === "object") { entries.push({ name: name, type: "dir" }); visit(v, childRel); }
    }
    dirs[relBase] = entries;
  }
  visit(spec, "");
  return {
    readdir: function (d) {
      // return UNSORTED (reversed) to prove the gift sorts, not the provider
      return (dirs[d] || []).slice().reverse();
    },
    size: function (f) { return sizes[f] || 0; }
  };
}

/* ---- independent oracle: explicit-stack iterative pre-order -------------- */
function oracleWalk(provider, opts) {
  opts = opts || {};
  var filesOnly = !!opts.filesOnly, dirsOnly = !!opts.dirsOnly;
  var maxDepth = opts.maxDepth === undefined ? Infinity : opts.maxDepth;
  var withSize = opts.withSize === undefined ? true : !!opts.withSize;
  var out = [];
  // stack frames: { dir, rel, depth }
  var stack = [{ dir: "", rel: "", depth: 1 }];
  // To get PRE-ORDER with an explicit stack we must process a directory's entries in order
  // and recurse immediately — so we use a recursion-free approach that mimics call order by
  // pushing a synthetic "expanded children" list. Simplest faithful different-route: gather
  // each dir's sorted entries, then interleave via an output-index insertion.
  function sortEntries(es) {
    var a = es.slice();
    a.sort(function (x, y) { return x.name < y.name ? -1 : x.name > y.name ? 1 : 0; });
    return a;
  }
  function rec(dir, rel, depth) {
    if (depth > maxDepth) return;
    var es = sortEntries(provider.readdir(dir));
    for (var i = 0; i < es.length; i++) {
      var e = es[i];
      var cRel = rel === "" ? e.name : rel + "/" + e.name;
      var cDir = dir === "" ? e.name : dir + "/" + e.name;
      if (e.type === "dir") {
        if (!filesOnly) out.push(mk(cRel, e.name, "dir", depth));
        rec(cDir, cRel, depth + 1);
      } else {
        if (!dirsOnly) {
          var rec2 = mk(cRel, e.name, e.type, depth);
          if (withSize && e.type === "file") rec2.size = provider.size(cDir);
          out.push(rec2);
        }
      }
    }
  }
  function mk(path, name, type, depth) { return { path: path, name: name, type: type, depth: depth }; }
  rec("", "", 1);
  return out;
}

/* ---- grid: gift == oracle across several trees x option sets ------------- */
var TREES = [
  {},                                                    // empty
  { "a.txt": 3 },                                        // one file
  { "z.txt": 1, "a.txt": 2, "m.txt": 3 },                // sort order matters
  { "dir": { "b.txt": 5 }, "a.txt": 1 },                 // nesting + sort across types
  { "link": "->", "a.txt": 1 },                          // symlink present
  { "a": { "b": { "c.txt": 9 } } },                      // deep
  { "d1": { "x.txt": 1 }, "d2": { "y.txt": 2 }, "f.txt": 3 }, // multiple dirs
  { "a.txt": 0, "empty": {} }                            // empty subdir + zero-size file
];
var OPTS = [
  {}, { filesOnly: true }, { dirsOnly: true }, { withSize: false },
  { maxDepth: 1 }, { maxDepth: 2 }, { filesOnly: true, maxDepth: 1 }
];
for (var ti = 0; ti < TREES.length; ti++) {
  for (var oi = 0; oi < OPTS.length; oi++) {
    var p = buildProvider(TREES[ti]);
    var giftOut = G.walk(p, Object.assign({ __rootAbs: "" }, OPTS[oi]));
    var oracleOut = oracleWalk(p, OPTS[oi]);
    eq("grid t" + ti + " o" + oi, giftOut, oracleOut);
  }
}

/* ---- frozen hand goldens: the three quiet failures ---------------------- */

// 1. Sort order — provider returns reversed, gift must emit sorted-by-name
var pSort = buildProvider({ "z.txt": 1, "a.txt": 1, "m.txt": 1 });
eq("golden: entries sorted by name regardless of provider order",
   G.walk(pSort, { __rootAbs: "" }).map(function (r) { return r.name; }),
   ["a.txt", "m.txt", "z.txt"]);

// 2. Portable fields only — a record has exactly {path,name,type,depth[,size]}, no mtime/ino/mode
var pFields = buildProvider({ "a.txt": 42 });
var rec = G.walk(pFields, { __rootAbs: "" })[0];
eq("golden: file record has exactly the portable field set",
   Object.keys(rec).sort(), ["depth", "name", "path", "size", "type"]);
ok("golden: no mtime/ino/mode leaked", rec.mtime === undefined && rec.ino === undefined && rec.mode === undefined);
var pDir = buildProvider({ "d": { "x": 1 } });
var dirRec = G.walk(pDir, { __rootAbs: "" })[0];
eq("golden: dir record has no size", Object.keys(dirRec).sort(), ["depth", "name", "path", "type"]);

// 3. Symlinks reported but not followed (and carry no size)
var pLink = buildProvider({ "link": "->", "a.txt": 1 });
var links = G.walk(pLink, { __rootAbs: "" }).filter(function (r) { return r.type === "symlink"; });
eq("golden: symlink reported as its own entry", links.length, 1);
ok("golden: symlink carries no size", links[0].size === undefined);
ok("golden: symlink is depth 1, not descended", links[0].depth === 1);

/* ---- direct unit checks -------------------------------------------------- */
eq("empty tree -> empty stream", G.walk(buildProvider({}), { __rootAbs: "" }), []);
eq("max-depth 1 stops before nested files",
   G.walk(buildProvider({ "d": { "x.txt": 1 } }), { __rootAbs: "", maxDepth: 1 }).map(function (r) { return r.path; }),
   ["d"]);
eq("files-only drops dir records",
   G.walk(buildProvider({ "d": { "x.txt": 1 }, "a.txt": 2 }), { __rootAbs: "", filesOnly: true }).map(function (r) { return r.type; }),
   ["file", "file"]);
eq("dirs-only drops file records",
   G.walk(buildProvider({ "d": { "x.txt": 1 }, "a.txt": 2 }), { __rootAbs: "", dirsOnly: true }).map(function (r) { return r.type; }),
   ["dir"]);
eq("no-size omits size field",
   Object.keys(G.walk(buildProvider({ "a.txt": 9 }), { __rootAbs: "", withSize: false })[0]).sort(),
   ["depth", "name", "path", "type"]);
eq("depth increments with nesting",
   G.walk(buildProvider({ "a": { "b": { "c.txt": 1 } } }), { __rootAbs: "" }).map(function (r) { return r.depth; }),
   [1, 2, 3]);
eq("pre-order: dir precedes its children",
   G.walk(buildProvider({ "d": { "x.txt": 1 } }), { __rootAbs: "" }).map(function (r) { return r.path; }),
   ["d", "d/x.txt"]);

// sortedByName + toJSONL surfaces
eq("sortedByName sorts by name", G.sortedByName([{ name: "b" }, { name: "a" }]).map(function (e) { return e.name; }), ["a", "b"]);
ok("toJSONL ends every record with newline", G.toJSONL([{ path: "a", name: "a", type: "file", depth: 1 }]) === '{"path":"a","name":"a","type":"file","depth":1}\n');
ok("toJSONL of empty is empty string", G.toJSONL([]) === "");
eq("joinPath at root is bare name", G.joinPath("", "a"), "a");
eq("joinPath nests with slash", G.joinPath("a", "b"), "a/b");

/* ---- determinism --------------------------------------------------------- */
var pDet = buildProvider({ "z": { "y.txt": 1 }, "a.txt": 2, "link": "->" });
var d1 = G.toJSONL(G.walk(pDet, { __rootAbs: "" }));
var d2 = G.toJSONL(G.walk(pDet, { __rootAbs: "" }));
ok("deterministic across two runs", d1 === d2);

/* ---- fail-closed --------------------------------------------------------- */
function throws(fn) { try { fn(); return false; } catch (e) { return true; } }
ok("files-only + dirs-only throws", throws(function () { G.walk(buildProvider({}), { __rootAbs: "", filesOnly: true, dirsOnly: true }); }));

/* ---- report -------------------------------------------------------------- */
console.log("dir-walk battery: " + pass + " passed, " + fail + " failed");
process.exitCode = fail === 0 ? 0 : 1;