evidence-dsl/tests/Recursion.test.js

/**
 * tests/Recursion.test.js — bounded self-recursion (transitive closure).
 *
 * An evidence whose config contains a chain step referencing ITSELF is
 * unrolled at compile time into a bounded transitive closure: a union of
 * paths — base, hop+base, hop²+base, … — where `hop` is the recursive chain's
 * steps before the self-reference and the depth N comes from the pattern's
 * `limit N` (or the compiler's maxRecursionDepth default). The base (the
 * evidence's non-recursive statements) is verified as a condition step at each
 * path's terminal node.
 *
 * A pure recursion (no base case) cannot grant and is a compile-time error.
 */
import { describe, it } from 'node:test';
import assert from 'node:assert/strict';
import { Arbiter } from '@arbiter/core';
import { DSLCompiler } from '../src/DSLCompiler.js';

const BASE = `
  definition Employee { id: string }
  definition Doc { id: string }
  fact can_access(user: Employee, doc: Doc)
  fact reports_to(user: Employee, manager: Employee)
`;

const RECURSIVE = `
  evidence can_access_via(user: Employee, doc: Doc) {
    can_access(user, doc)
    reports_to(user, *m) { can_access_via(m, doc) } limit 3
  }
`;

function compile(dsl, name = 'rec') {
  const arb = new Arbiter();
  const result = new DSLCompiler(arb).compile(dsl, name);
  return { arb, result };
}

describe('Bounded self-recursion', () => {
  it('unrolls into a union of base + bounded hop chains', () => {
    const { arb, result } = compile(BASE + RECURSIVE);
    assert.ok(result.success, JSON.stringify(result.errors));
    const cfg = arb.relationConfigs.get('can_access_via');
    assert.equal(cfg.type, 'logical');
    assert.ok(cfg.union, 'recursion should compile to a union of paths');
    // base + 3 hops (limit 3)
    assert.equal(cfg.union.rules.length, 4);
  });

  it('grants through the base case and through multi-hop chains', () => {
    const { arb, result } = compile(BASE + RECURSIVE);
    assert.ok(result.success);
    arb.addNode('u:1', 'Employee'); arb.addNode('m:1', 'Employee'); arb.addNode('m2:1', 'Employee'); arb.addNode('doc:9', 'Doc');
    // base
    arb.addRelation('u:1', 'can_access', 'doc:9', { possibility: 1.0 });
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 1.0);
    // 1-hop: u -> m -> doc
    arb.removeRelation('u:1', 'can_access', 'doc:9');
    arb.addRelation('u:1', 'reports_to', 'm:1', { possibility: 1.0 });
    arb.addRelation('m:1', 'can_access', 'doc:9', { possibility: 0.7 });
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0.7);
    // 2-hop: u -> m -> m2 -> doc
    arb.addRelation('m:1', 'reports_to', 'm2:1', { possibility: 1.0 });
    arb.addRelation('m2:1', 'can_access', 'doc:9', { possibility: 0.5 });
    // union takes the best path: max(0.7, 0.5) = 0.7
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0.7);
    // 2-hop alone (remove the 1-hop can_access)
    arb.removeRelation('m:1', 'can_access', 'doc:9');
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0.5);
  });

  it('enforces the recursion depth limit', () => {
    const { arb, result } = compile(`
      ${BASE}
      evidence can_access_via(user: Employee, doc: Doc) {
        can_access(user, doc)
        reports_to(user, *m) { can_access_via(m, doc) } limit 2
      }
    `);
    assert.ok(result.success);
    arb.addNode('u:1', 'Employee'); arb.addNode('m:1', 'Employee'); arb.addNode('m2:1', 'Employee'); arb.addNode('m3:1', 'Employee'); arb.addNode('doc:9', 'Doc');
    arb.addRelation('u:1', 'reports_to', 'm:1', { possibility: 1.0 });
    arb.addRelation('m:1', 'reports_to', 'm2:1', { possibility: 1.0 });
    arb.addRelation('m2:1', 'reports_to', 'm3:1', { possibility: 1.0 });
    arb.addRelation('m2:1', 'can_access', 'doc:9', { possibility: 0.5 }); // 2 hops
    arb.addRelation('m3:1', 'can_access', 'doc:9', { possibility: 0.9 }); // 3 hops
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0.5);
    arb.removeRelation('m2:1', 'can_access', 'doc:9');
    // only the 3-hop path remains — beyond the limit -> denied
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0);
  });

  it('uses the compiler maxRecursionDepth default when no limit is given', () => {
    const dsl = `
      ${BASE}
      evidence can_access_via(user: Employee, doc: Doc) {
        can_access(user, doc)
        reports_to(user, *m) { can_access_via(m, doc) }
      }
    `;
    const { arb, result } = compile(dsl);
    assert.ok(result.success, JSON.stringify(result.errors));
    // default depth 3 -> base + 3 hops
    assert.equal(arb.relationConfigs.get('can_access_via').union.rules.length, 4);
    // a deeper path (4 hops) is not granted
    arb.addNode('u:1', 'Employee'); arb.addNode('m:1', 'Employee'); arb.addNode('m2:1', 'Employee'); arb.addNode('m3:1', 'Employee'); arb.addNode('m4:1', 'Employee'); arb.addNode('doc:9', 'Doc');
    arb.addRelation('u:1', 'reports_to', 'm:1', { possibility: 1.0 });
    arb.addRelation('m:1', 'reports_to', 'm2:1', { possibility: 1.0 });
    arb.addRelation('m2:1', 'reports_to', 'm3:1', { possibility: 1.0 });
    arb.addRelation('m3:1', 'reports_to', 'm4:1', { possibility: 1.0 });
    arb.addRelation('m4:1', 'can_access', 'doc:9', { possibility: 1.0 });
    assert.equal(arb.check('u:1', 'can_access_via', 'doc:9').possibility, 0, '4-hop path exceeds default depth');
  });

  it('rejects a pure recursion with no base case', () => {
    const { result } = compile(`
      ${BASE}
      evidence can_access_via(user: Employee, doc: Doc) {
        reports_to(user, *m) { can_access_via(m, doc) } limit 3
      }
    `);
    assert.equal(result.success, false);
    assert.ok(result.errors.some(e => /no base case/.test(e)), JSON.stringify(result.errors));
  });

  it('keeps mutual (non-self) cycles a compile error', () => {
    const { result } = compile(`
      ${BASE}
      fact peer(user: Employee, other: Employee)
      evidence a(user: Employee, doc: Doc) { peer(user, *p) { b(p, doc) } }
      evidence b(user: Employee, doc: Doc) { peer(user, *p) { a(p, doc) } }
    `);
    assert.equal(result.success, false);
    assert.ok(result.errors.some(e => /[Cc]yclic/.test(e)), JSON.stringify(result.errors));
  });
});