core/tests/rigor/complex-graph-reachability-crucible.test.js

/**
 * rigor/complex-graph-reachability-crucible.test.js — PLTC reachability
 * over the scale-free and community graphs, compared against ground-truth
 * directed DFS.
 *
 * The PLTC index is built from every relation in arbiter.relations (edge
 * src -> dst, deduplicated by pair), so the ground truth is the same edge
 * set: the generator's relations for community, and the live engine's
 * relation rows for scale-free (whose generator returns `relations:
 * null`). All of these relations are configured `direct`, so "direct
 * relations" and "all relations" coincide.
 *
 *   VERDICT-PARITY — a non-null isReachable verdict equals ground truth.
 *   FAST-FAIL-SOUNDNESS — isReachable(...) === true implies ground truth
 *     is true (PLTC must not manufacture reachability).
 *   NULL-DEFER — isReachable returns null when the PLTC index is
 *     unavailable; a null verdict is the documented "delegate to rules"
 *     contract and is skipped, never failed.
 */
import { describe, it } from 'node:test';
import assert from 'node:assert/strict';
import { rigor } from '@rigor/core';
import { makeCommunityGraph, makeScaleFreeGraph } from './complex-graphs.js';

const SAMPLES = 12;

const GENERATORS = [
  { name: 'community', make: makeCommunityGraph, opts: {} },
  // Default scale-free (150 users / 400 edges) is slow to build per case;
  // a 60-user power-law graph keeps the PLTC-vs-DFS comparison meaningful
  // without dominating the suite.
  { name: 'scale-free', make: makeScaleFreeGraph, opts: { users: 60, resources: 20, edges: 150 } }
];

function fail(message) {
  throw new Error(message);
}

function mulberry32(seed) {
  let a = seed >>> 0;
  return function () {
    a |= 0;
    a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function allNodeKeys(g) {
  const keys = [...g.users, ...(g.resources || []), ...(g.groups || []), ...(g.subGroups || [])];
  return keys.filter(k => g.arbiter.nodeIdByKey.has(k));
}

function groundTruthEdges(g) {
  const seen = new Set();
  const edges = [];
  const push = (s, d) => {
    const k = `${s}\u0000${d}`;
    if (!seen.has(k)) { seen.add(k); edges.push([s, d]); }
  };
  if (g.relations) {
    for (const r of g.relations) push(r.src, r.dst);
  } else {
    for (const r of g.arbiter.relations) {
      const sk = g.arbiter.keyByNodeId.get(r.src);
      const dk = g.arbiter.keyByNodeId.get(r.dst);
      if (sk !== undefined && dk !== undefined) push(sk, dk);
    }
  }
  return edges;
}

function buildAdjacency(keys, edges) {
  const adj = new Map();
  for (const k of keys) adj.set(k, []);
  for (const [s, d] of edges) {
    if (!adj.has(s)) adj.set(s, []);
    if (!adj.has(d)) adj.set(d, []);
    adj.get(s).push(d);
  }
  return adj;
}

function dfsReachable(adj, src, dst) {
  if (src === dst) return true;
  const visited = new Set([src]);
  const stack = [src];
  while (stack.length) {
    const cur = stack.pop();
    for (const next of adj.get(cur) || []) {
      if (next === dst) return true;
      if (!visited.has(next)) { visited.add(next); stack.push(next); }
    }
  }
  return false;
}

describe('Complex-graph PLTC reachability crucibles (rigor)', () => {
  it('VERDICT-PARITY + FAST-FAIL-SOUNDNESS against ground-truth DFS, with NULL-DEFER', async () => {
    async function check(args) {
      const { genKind, seed, srcIdx, dstIdx } = args;
      const spec = GENERATORS.find(g => g.name === genKind);
      const g = spec.make(seed, spec.opts);
      const keys = allNodeKeys(g);
      const adj = buildAdjacency(keys, groundTruthEdges(g));

      await g.arbiter.initializeReachabilityChecker();

      const rng = mulberry32(seed * 7919 + 17);
      // The campaign's srcIdx/dstIdx seed the first pair; the rest are
      // drawn from a per-case deterministic stream so every case samples
      // more than one edge of the graph.
      let nonNull = 0;
      let verdictChecks = 0;
      for (let i = 0; i < SAMPLES; i++) {
        const a = i === 0 ? keys[srcIdx % keys.length] : keys[Math.floor(rng() * keys.length)];
        const b = i === 0 ? keys[dstIdx % keys.length] : keys[Math.floor(rng() * keys.length)];
        const v = g.arbiter.isReachable(a, b);
        if (v === null) continue; // PLTC unavailable -> defer to rule eval
        nonNull++;
        const gt = dfsReachable(adj, a, b);
        verdictChecks++;
        if (v !== gt) {
          fail(`[verdict] ${genKind} seed=${seed}: isReachable(${a},${b})=${v} != ground truth ${gt}`);
        }
        if (v === true && gt !== true) {
          fail(`[soundness] ${genKind} seed=${seed}: PLTC false positive on ${a}->${b}`);
        }
      }
      // Vacuity guard: a case whose sampled pairs all hit the NULL-DEFER
      // path proves nothing about verdict parity.
      if (verdictChecks === 0) {
        fail(`[vacuity] no non-null PLTC verdicts sampled for ${genKind} seed=${seed}`);
      }
      return { nonNull, verdictChecks };
    }

    const report = await rigor.campaign(
      [
        rigor.fn('check', check, rigor.args(
          rigor.gen.object({
            genKind: rigor.gen.oneOf(GENERATORS.map(g => g.name)),
            seed: rigor.gen.int(1, 6),
            srcIdx: rigor.gen.int(0, 199),
            dstIdx: rigor.gen.int(0, 199)
          })
        ))
      ],
      rigor.crucible([
        rigor.invariant('verdict-parity', ({ actual }) => actual !== undefined),
        rigor.invariant('fast-fail-soundness', ({ actual }) => actual !== undefined),
        rigor.invariant('null-defer-contract', ({ actual }) => actual !== undefined)
      ])
    ).run({ effort: 200, seed: 'complex-graph-reachability-crucible', artifacts: { dir: '', persist: 'never' } });

    for (const name of ['verdict-parity', 'fast-fail-soundness', 'null-defer-contract']) {
      const inv = report.crucibleVerdict?.invariants?.find(i => i.name === name);
      assert.ok(inv, `invariant ${name} missing`);
      assert.equal(inv.passed, true, `reachability ${name} violated in ${inv.failureCount} cases`);
    }
  });
});