Contract — P4.2.1 Circular Logic Detector

§1. Scope

P4.2.1 ships a pure, read-only DFS cycle detector over a graph derived from ζ ThoughtRecords, optionally augmented with caller-supplied rule-dependency edges. The detector emits a P4.1.1 Advisory envelope per distinct cycle. No state is mutated; no I/O is performed; no wall-clock is read; no randomness is consumed.

§2. Public surface (locked) 

export type CycleNodeKind = 'record' | 'rule';
export interface Cycle {
  readonly records: readonly string[];  // canonical-rotated path; length N
  readonly length: number;               // N (≥ 1)
}

export interface DirectedGraph {
  readonly nodes: ReadonlySet<string>;
  readonly edges: ReadonlyMap<string, readonly string[]>;
}

export interface BuildDagOptions {
  readonly getOutgoingEdges?: (
    record: Pick<ThoughtRecord, 'id' | 'prev_hash'>,
  ) => readonly string[];
  readonly registryEdges?: ReadonlyMap<string, readonly string[]>;
}

export interface DetectCircularLogicOptions extends BuildDagOptions {
  readonly lamportNow: bigint;
}

export function buildDag(
  records: readonly Pick<ThoughtRecord, 'id' | 'prev_hash'>[],
  options?: BuildDagOptions,
): DirectedGraph;

export function findCycles(
  records: readonly Pick<ThoughtRecord, 'id' | 'prev_hash'>[],
  options?: BuildDagOptions,
): readonly Cycle[];

export function detectCircularLogic(
  records: readonly Pick<ThoughtRecord, 'id' | 'prev_hash'>[],
  options: DetectCircularLogicOptions,
): readonly Advisory[];

The ThoughtRecord import is type-only — the detector accepts structural subtypes (e.g. ThoughtRecordWithSession) without modification.

§3. Behavior

§3.1 — buildDag

Builds a deterministic directed graph in three phases:

  1. Record nodes: every record contributes one node, ID record.id, raw — no prefix. Records are added in input array order.
  2. Record edges: for every record, the outgoing-edge list is:
    • options.getOutgoingEdges?.(record) ?? [record.prev_hash]
    • Filtered: ZERO_HASH is dropped (genesis sentinel, not a real parent). Any edge target that does NOT match an existing node ID in the graph is dropped (a back-pointer to a record that is not in records[] is treated as a dangling reference, not a graph edge — the detector cannot decide what to do with it without hydration).
  3. Rule edges: if options.registryEdges is provided, for every (ruleName, dependsOnNames) entry:
    • Add node rule:<ruleName>.
    • For each dep in dependsOnNames, add node rule:<dep>, then add an edge rule:<ruleName> → rule:<dep>.
    • Rule nodes and record nodes share the same node-ID namespace; the rule: prefix prevents collisions with raw record IDs. A record ID that begins with the literal substring 'rule:' would collide with a rule node and is the caller’s responsibility to avoid (P4.2.1 documents the namespace; future hardening could reject such IDs at validation time).

The graph is returned with Object.freeze-d structures; node iteration is sorted lexicographically by ID.

§3.2 — Default getOutgoingEdges

The default adapter is (record) => [record.prev_hash], with ZERO_HASH and unknown-hash filtering applied inside buildDag (not the adapter). This means a custom adapter does NOT bypass the zero-hash drop; the adapter only chooses the outgoing-edge set, and post-processing applies uniformly.

§3.3 — findCycles

Implements the integrity.md L40-51 pseudocode as an iterative DFS (explicit stack, no recursion) with the IN_PROGRESS / DONE two-color scheme:

for each node in sorted(graph.nodes):
    if color[node] == DONE: continue
    stack.push({ node, edgesPending: edges_from(node) })
    color[node] = IN_PROGRESS
    path.push(node); pathSet.add(node)
    while stack not empty:
        frame = stack.top()
        if frame.edgesPending empty:
            stack.pop()
            color[frame.node] = DONE
            path.pop(); pathSet.delete(frame.node)
            continue
        next = frame.edgesPending.shift()
        if pathSet.has(next):
            cycle = path[path.indexOf(next):] + [next]
            emit canonicalize(cycle)
        elif color[next] != DONE:
            color[next] = IN_PROGRESS
            path.push(next); pathSet.add(next)
            stack.push({ node: next, edgesPending: edges_from(next) })

Cycles are canonicalized post-detection:

  • Length-1 self-loop (A → A): the raw cycle path is [A, A]; canonicalized to records: ['A'], length: 1.
  • Length-N (N ≥ 2): the raw cycle path is [A, B, C, A] (N+1 entries closing back to start). Canonicalized to drop the trailing duplicate, then rotated so the lex-smallest ID is first; final records has exactly N entries.
  • De-duplication: each unique cycle (by canonical key records.join('')) is emitted exactly once. The same cycle discovered from multiple DFS starts collapses to one report.

Output ordering: cycles are sorted by canonical key (records.join('')) ascending. This makes the output deterministic across all node-iteration orders.

§3.4 — detectCircularLogic

Calls findCycles(records, options); for each cycle, emits one Advisory:

{
  role: 'Sentinel',
  check: 'circular_logic',
  result: 'WARN',
  severity: 'HIGH',
  evidence: [{ kind: 'cycle_path', records: cycle.records, length: cycle.length }],
  recommendation: 'Cycle of length <N> detected in citation graph: <id1> → <id2> → ... → <id1>',
  decision_hash: computeDecisionHash('Sentinel', 'circular_logic', { records, length }, 'WARN'),
  timestamp_logical: options.lamportNow,
}

The advisory array is sorted in the same order as findCycles returns. Two cycles in the same input → two advisories, deterministic order.

The recommendation close uses → <id1> (the trailing repeat) to make the cyclic nature visible in the prose. For length-1, the recommendation is "Cycle of length 1 detected in citation graph: <id1> → <id1>".

§3.5 — Input validation

The detector trusts its input structurally. Specifically:

  • records[] may be empty → empty advisories.
  • records[].id is required to be a non-empty string (Zod-enforced upstream at the trail layer); the detector does NOT re-validate.
  • records[].prev_hash is required (always non-empty by the ζ schema); the detector treats ZERO_HASH specially per §3.2.
  • Duplicate ids across records: the detector treats them as a single node (Map collapses); this matches “graph identity is by node ID”. Callers wishing to detect duplicate-ID hazards should validate upstream.
  • options.registryEdges keys and values may be any strings (after the rule: prefix is applied). Empty values arrays are permitted.

The detector throws no errors on shape-valid input. The only error path is AdvisorySerializationError propagated from computeDecisionHash if a future caller injects un-representable evidence — the current evidence shape is plain-JSON-clean so this cannot happen with the in-process default.

§4. Invariants

ID Statement
I1 Determinism: identical inputs (records[], options) → byte-identical advisory arrays. No wall-clock, no randomness, no platform-dependent ordering.
I2 Read-only: the detector does not mutate records[], options.registryEdges, or any caller-supplied structure. Result types are frozen via Object.freeze.
I3 Diamond is not a cycle: A→B→D + A→C→D produces zero advisories. The DONE coloring distinguishes forward/cross edges from back-edges.
I4 Self-loops are cycles: A → A produces exactly one advisory with evidence.records = ['A'], length 1.
I5 De-duplication: a length-N cycle is emitted exactly once regardless of how many DFS starts re-discover it.
I6 Canonical start: each cycle’s records array begins with the lex-smallest ID.
I7 Cross-rule cycles work: a rule-dep map R1 → R2, R2 → R1 produces one advisory with evidence.records = ['rule:R1', 'rule:R2'] (or rotated to lex-smallest).
I8 No wall-clock: circular.ts body contains no Date.now, Date.UTC, Date.parse, new Date, performance.now, Math.random.
I9 No dotted-crypto: circular.ts body contains no \bcrypto\.[a-zA-Z]\b token (matching P4.1.1 NAMED-import convention).
I10 P4.1.1 reuse: circular.ts imports computeDecisionHash, AdvisoryRoleSchema / AdvisoryCheckSchema (or just uses them as constants) from ../schema.js. It does NOT re-import node:crypto directly; SHA-256 hashing flows through computeDecisionHash.
I11 FP profile: on 100 randomly-generated DAGs (deterministically seeded — see §6.3), findCycles returns []. False-positive rate is 0% on the corpus stub.

§5. Public errors

None. The detector is total over shape-valid input. Future hardening slices may add explicit InvalidGraphError for cases the detector currently silently absorbs (duplicate IDs, empty input). Out of scope for P4.2.1.

§6. Test plan

§6.1 — Group 1: Core graph shapes (AC1–AC6)

  • Empty graph (zero records) → 0 advisories.
  • Single record (no edges) → 0 advisories.
  • Linear chain A→B→C → 0 advisories.
  • Diamond A→{B,C}→D → 0 advisories (regression-guard for forward-edge classification).
  • Self-loop A→A → 1 advisory, length 1, evidence.records = ['A'].
  • Triangle A→B→C→A → 1 advisory, length 3, records canonical rotation.
  • Two disjoint cycles (A↔B + C→D→E→C) → 2 advisories, deterministic order.

§6.2 — Group 2: Cross-rule edges (AC7)

  • Pure record graph: empty graph + registryEdges = { R1: [R2], R2: [R1] } → 1 advisory, length 2, evidence.records = ['rule:R1', 'rule:R2'].
  • Mixed graph: record edge A→A + rule edge R1→R1 → 2 advisories.

§6.3 — Group 3: FP corpus stub (AC8)

A 100-element corpus of pseudorandom DAGs generated by a deterministic LCG (seeded constant). Each DAG has 5–20 nodes and is constructed as for i in 1..N: edges_from[i] = [j for j in some sample of 0..i-1] — i.e. forward edges only, by construction acyclic. findCycles returns [] on every DAG. Full corpus measurement lives in P4.7.1.

§6.4 — Group 4: Determinism (AC9)

  • Run findCycles on a fixed multi-cycle input 100 times → output array (canonical-key string) is identical across all 100 runs.
  • Same input × shuffled input order → same advisory order (the detector sorts).

§6.5 — Group 5: Advisory shape (AC10)

  • Validate the emitted advisories pass AdvisorySchema.safeParse.
  • Validate decision_hash matches DECISION_HASH_REGEX.
  • Validate identical cycles in different lamportNow calls produce identical decision_hash (timestamp is NOT part of the preimage).
  • Validate recommendation text format matches the contract.

§6.6 — Group 6: Static scanner (AC11–AC12)

Mirrors the P4.1.1 Group 9 / Group 10 style:

  • Forbidden-token scan on circular.ts (comment-stripped body): no Date.now, Date.UTC, Date.parse, new Date, performance.now, Math.random, JSON.stringify.
  • NAMED-import scanner: no dotted crypto.X token in body.
  • Imports section contains the relative '../schema.js' (P4.1.1 reuse) and nothing from 'node:crypto'.

§6.7 — Group 7: Reuse + I2 read-only

  • After running findCycles(records, options), snapshot JSON.stringify(records) and JSON.stringify(Array.from(options.registryEdges ?? [])) are unchanged.
  • findCycles result arrays are frozen.

§7. Acceptance criteria

# Criterion
AC1 Empty graph → 0 advisories
AC2 Linear chain → 0 advisories
AC3 Diamond DAG → 0 advisories
AC4 Self-loop → 1 advisory, length 1
AC5 Triangle → 1 advisory, length 3
AC6 Two disjoint cycles → 2 advisories
AC7 Cross-rule cycle via registryEdges → 1 advisory
AC8 FP corpus stub: 100 random DAGs → 0 cycles each
AC9 100-run determinism: identical canonical-key output array
AC10 Advisory shape passes AdvisorySchema.safeParse; matches contract
AC11 Static scanner — no wall-clock / RNG tokens
AC12 NAMED-import scanner — no dotted crypto.X
AC13 Build + lint + jest all green

§8. Out-of-scope

  • Persistence into mcp_advisories (P4.5.1).
  • MCP tool surface (integrity_* family) (P4.6.1).
  • Escalation FSM consuming advisories (P4.4.1).
  • κ AST-walking rule-dep extractor — P4.2.1 takes the dep map as a parameter.
  • Multi-edge refs[] on ThoughtRecord — adapter ready, but the upstream schema extension is not part of this slice.

§9. Backward-compatibility

P4.2.1 introduces a new module under src/domains/integrity/detectors/; no existing module is modified. There is no public-API churn.

Back to top

Colibri — documentation-first MCP runtime. Apache 2.0 + Commons Clause.

This site uses Just the Docs, a documentation theme for Jekyll.