#!/usr/bin/env node
// wasmld-pool-select: GNU-ld archive-member selection for the coro arm's
// whole-program merge (ticket #8 root cause).
//
// The retired `llvm-link -only-needed` fixpoint was SYMBOL-granular: a pool
// member's functions imported across DIFFERENT fixpoint passes each dragged
// in a FRESH copy of the member's internal (static) globals — llvm-link
// renames the conflict (encodingTable + encodingTable.616) and the module
// ships with two half-initialized copies of what the C program declared as
// ONE object. First witnessed as Tcl 8.6's Tcl_CreateEncoding dispatching
// through a never-initialized copy of its static hash table (null function
// at .resume).
//
// This helper implements the semantics every real linker has: MEMBER
// granularity. A member is selected iff it defines a symbol that is
// currently undefined; selection brings the WHOLE member (internal state
// merges exactly once). The scan is left-to-right in pool order (first
// provider wins, musl-authoritative order preserved by the caller) and is
// iterated to a fixpoint over the selected set, so backward dependencies
// resolve like a --start-group/--end-group bracket around the pool.
//
// Usage:
//   wasmld-pool-select.mjs <llvm-nm> <merged.def> <merged.undef> <members.list>
//
//   <merged.def>/<merged.undef>: newline lists of the merged module's
//     defined / strongly-undefined symbol names (weak undefs excluded by
//     the caller — GNU ld does not extract members for weak undefs).
//   <members.list>: newline list of pool member paths, in pull order.
//
// Output: selected members, one per line, in pool order. A plain line is a
// member path pulled whole. A line of the form
//   <path>\t<sym1,sym2,...>
// is a PARTIAL-OVERLAP pull (issue linux-in-the-browser#49): the member is
// needed (it is the provider of a currently-undefined symbol) but ALSO
// strongly re-defines the listed symbols, which an earlier provider (a
// root or an earlier selection) already strongly supplies. The caller must
// DEMOTE the listed symbols to internal linkage (opt -passes=internalize)
// before linking the member, so the earlier definition keeps winning
// (first-provider-wins at SYMBOL granularity) while the member still joins
// whole exactly once (MEMBER granularity for its internal state). The
// pre-#49 behavior — skipping the member entirely, orphaning the symbols
// only it provides into phantom env.* imports (tcl's compat strtoul.o vs
// musl strtol.o's strtol/strtoull) — survives only behind the RED knob
// WASMLD_HWJS_POOL_PARTIAL_OVERLAP_SKIP=1 (the non-vacuity arm of
// test/pool-partial-overlap-pull.sh).
// Exit 0 with empty output = nothing to pull (converged). Exit 2 = a
// member's symbols could not be read (the caller must treat that as a
// loud refusal).
import fs from 'node:fs';
import { spawnSync } from 'node:child_process';

const [nmPath, defFile, undefFile, listFile] = process.argv.slice(2);
if (!nmPath || !defFile || !undefFile || !listFile) {
  console.error('usage: wasmld-pool-select.mjs <llvm-nm> <merged.def> <merged.undef> <members.list>');
  process.exit(2);
}

const readLines = (f) => fs.readFileSync(f, 'utf8').split('\n').map((s) => s.trim()).filter(Boolean);
const members = readLines(listFile);
// <merged.def> carries `KIND NAME` lines (see wasmld): ALL defined names
// satisfy references; only STRONG defs participate in collision detection
// (weak defs lose to a member's strong override — the 2b strong-override
// contract — and a member's weak aliases must never disqualify the member).
// Lowercase kinds are LOCAL (internal-linkage) symbols: invisible to
// linking, so they satisfy nothing and can never collide (musl's per-TU
// `static void dummy()` weak-alias donor is the canonical trap).
const isGlobalKind = (k) => /^[A-Z]$/.test(k);
const isWeakKind = (k) => k === 'W' || k === 'V';
const defined = new Set();
const definedStrong = new Set();
for (const line of readLines(defFile)) {
  const sp = line.indexOf(' ');
  const kind = sp > 0 ? line.slice(0, sp) : '?';
  const name = sp > 0 ? line.slice(sp + 1) : line;
  if (!isGlobalKind(kind)) continue;
  defined.add(name);
  if (!isWeakKind(kind)) definedStrong.add(name);
}
let undef = new Set(readLines(undefFile).filter((s) => !defined.has(s)));

// One llvm-nm pass over all members; per member: allDefs (satisfy refs),
// strongDefs (collision candidates), strong undefs (propagate needs).
function nmScan() {
  const r = spawnSync(nmPath, [...members], { maxBuffer: 1 << 28, encoding: 'utf8' });
  if (r.status !== 0 && !r.stdout) {
    console.error(`wasmld-pool-select: ${nmPath} failed: ${r.stderr}`);
    process.exit(2);
  }
  const map = new Map();
  let cur = members.length === 1 ? members[0] : null;
  const ensure = (k) => {
    if (!map.has(k)) map.set(k, { all: new Set(), strong: new Set(), undef: new Set() });
    return map.get(k);
  };
  if (cur) ensure(cur);
  for (const line of r.stdout.split('\n')) {
    if (line.endsWith(':') && !line.startsWith(' ')) {
      cur = line.slice(0, -1);
      ensure(cur);
      continue;
    }
    const t = line.trim();
    if (!t || !cur) continue;
    const parts = t.split(/\s+/);
    const name = parts[parts.length - 1];
    const kind = parts.length >= 2 ? parts[parts.length - 2] : '';
    const g = ensure(cur);
    // Weak undefs ('w') pull too — wasm-ld refuses data/TLS relocations
    // against undefined symbols, so glibc's weak-extern idiom must be
    // satisfied whenever a provider exists (see wasmld's merged.undef note).
    if (kind === 'U' || kind === 'w') g.undef.add(name);
    else if (isGlobalKind(kind)) {                  // locals (lowercase) are invisible to linking
      g.all.add(name);
      if (!isWeakKind(kind)) g.strong.add(name);
    }
  }
  return map;
}

const syms = nmScan();
for (const m of members) {
  if (!syms.has(m)) {
    console.error(`wasmld-pool-select: no symbol table read for pool member '${m}' — cannot decide member pulls; refusing rather than guessing.`);
    process.exit(2);
  }
}

// RED knob (issue linux-in-the-browser#49 non-vacuity arm; registered in
// wasmld's HWJS_RED_KNOBS): restores the retired skip-on-partial-overlap
// behavior so test/pool-partial-overlap-pull.sh can prove the demotion
// pull is non-vacuous.
const redSkipPartialOverlap =
  (process.env.WASMLD_HWJS_POOL_PARTIAL_OVERLAP_SKIP ?? '0') !== '0';

const selected = new Map();          // member -> [] (whole) | [syms to demote]
const skippedCollisions = new Map(); // RED arm only
let progressed = true;
while (progressed) {
  progressed = false;
  for (const m of members) {
    if (selected.has(m) || skippedCollisions.has(m)) continue;
    const g = syms.get(m);
    let needed = false;
    for (const u of undef) {
      if (g.all.has(u)) { needed = true; break; }
    }
    if (!needed) continue;
    // FIRST-PROVIDER-WINS DEDUP (the pool's documented contract: "program
    // archives first, so a program-local definition wins the pull"). If
    // this member STRONGLY defines a symbol an earlier selection (or the
    // merged roots) already STRONGLY provides, linking it whole would be
    // a loud llvm-link duplicate-definition failure — the glibc pool's
    // partial-overlap twins (the iconv/intl/nss hash-string helper, the
    // malloc-hugepages subdir twins) are exactly this shape. STRONG defs
    // only, both sides: a member's weak aliases (musl's whole surface)
    // never disqualify it, and a member's strong override of a weak dummy
    // is the 2b contract, not a collision.
    //
    // The member is still NEEDED (by construction it provides a symbol
    // nothing selected so far defines), so it must not be skipped: the
    // pre-#49 skip orphaned the symbols only it provides into phantom
    // env.* imports (tcl's configure cross-fallback puts a strong compat
    // strtoul.o in libtcl8.6.a; musl's strtol.o — the SOLE provider of
    // strtol/strtoull/strtoll — then collided on strtoul and was skipped
    // whole). Instead, select it with the colliding symbols DEMOTED to
    // internal linkage (the caller internalizes them before the link):
    // the earlier provider keeps winning those names at SYMBOL
    // granularity, the member's other symbols join at MEMBER granularity
    // (internal state merges exactly once), and the member's own
    // references to a demoted symbol keep binding to its own copy —
    // self-consistent, and loudly NOTEd, never a silent misbind.
    const collisions = [];
    for (const d of g.strong) {
      if (definedStrong.has(d)) collisions.push(d);
    }
    if (collisions.length > 0 && redSkipPartialOverlap) {
      skippedCollisions.set(m, collisions[0]);
      console.error(`wasmld-pool-select: NOTE (RED knob WASMLD_HWJS_POOL_PARTIAL_OVERLAP_SKIP): skipping pool member '${m}' — it strongly defines '${collisions[0]}', already strongly provided by an earlier selection (the retired pre-#49 first-provider-wins member skip); its other symbols stay unresolved unless another member provides them.`);
      continue;
    }
    if (collisions.length > 0) {
      console.error(`wasmld-pool-select: NOTE: pool member '${m}' strongly re-defines [${collisions.join(', ')}], already strongly provided by an earlier provider (root or earlier selection) — pulling the member with those symbols DEMOTED to internal linkage (first-provider-wins at symbol granularity; issue linux-in-the-browser#49).`);
    }
    selected.set(m, collisions);
    progressed = true;
    const demoted = new Set(collisions);
    for (const d of g.all) { defined.add(d); undef.delete(d); }
    for (const d of g.strong) { if (!demoted.has(d)) definedStrong.add(d); }
    for (const u of g.undef) {
      if (!defined.has(u)) undef.add(u);
    }
  }
}

for (const m of members) {
  if (!selected.has(m)) continue;
  const collisions = selected.get(m);
  process.stdout.write(collisions.length > 0 ? `${m}\t${collisions.join(',')}\n` : m + '\n');
}