Stable structural node identity for the program graph — foundation for multi-agent editing

[PeterXMR]

Stable structural node identity for the program graph — foundation for multi-agent editing

Type: Tracking issue / RFC (spec-first; implementation gated on maintainer sign-off)
Scope: editing-time tooling. Not runtime concurrency (that is #20).

⚠️ Status update (2026-06-02): the foundational step has landed via #355.
#355 ("Stabilize program graph node identity") makes the primary node id
structurally derived (module + owner-edge chain + edge kind + sibling order) and
independent of content and source path — so a node's id now survives content
edits, and (via its collision / "ID-theft" handling) sibling inserts and reorders
too. So PR 1 below is done — on the primary id, not a separate pathId field
— which answers the first of this RFC's open questions below (the identity model).
My implementation PR #310 (pathId) is closed
as superseded (it duplicated #355's structural inputs, was less robust, and id
is already the patch handle). The TL;DR and "The problem" section below describe
the pre-#355 baseline and are kept for history. What remains open and unbuilt is
the actual goal of this issue: building on the stable id toward diffs,
collision detection, and safe multi-agent merge (PRs 2–8).

TL;DR

Today a graph node's ID changes whenever you edit the node (the ID is a hash of
the node's contents). That means an agent has no durable handle to "the same
node" across an edit, you can't express a real "what changed" diff, and there is
no foundation for ever combining two agents' edits safely.

This issue proposes a small, additive first step — give every node a stable
identity that survives content edits — and then a roadmap that builds on it:
real diffs → collision detection → automatic merge of non-overlapping edits. Each
step is an independent, useful PR. The first one is valuable on its own and maps
directly onto #151 (stable, deterministic identities for agents).

Background: how agent editing works today (for newcomers)

Zero is graph-first: the compiler turns .0 source into a ProgramGraph — the
program's meaning as connected nodes (functions, params, expressions, types),
each with an ID like #610c78bf — and agents edit that instead of raw text.
(README "Why Graph",
skill-data/graph.md)

The edit loop:

1. Inspect → get node IDs and a graphHash (a version stamp for the whole program).
2. Edit → e.g. set node="#610c78bf" field="value" expect="300" value="301",
   carrying the graphHash you inspected.
3. The compiler checks the stamp is current, validates, rewrites .0, re-checks.

The graphHash is described in the docs as "a stale-context check." It is the
only concurrency mechanism today: it can reject an edit built on stale
context. It cannot combine edits.

The problem

Resolved by #355 (kept for history). As of #355 this is no longer the case:
the content-hash graph_stable_node_id() is gone and id assignment now lives in
native/zero-c/src/program_graph_node_id.c (z_program_graph_assign_source_node_ids),
producing a structural, edit-stable id. The description below reflects the
pre-#355 baseline that motivated this RFC.

1. Node IDs are not stable across edits. graph_stable_node_id()
(program_graph_import.c:80)
sets id = "#" + hash(kind, name, type, value, flags). The ID is a fingerprint
of the node's current contents, so editing a node changes its ID:

let big: u32 = 300   →  node #a1b2c3d4
   (edit 300 → 301)
let big: u32 = 301   →  node #e5f60718   ← different ID for the same binding

The handle an agent was holding is now dead. There is no name that means "which
node," only "what the node currently is."

2. Because of (1), there is no path to combining edits. A "merge" of two
agents' work needs to recognize "both edited the same logical node" — but after
an edit, that node has a different ID in each version, so an ID-based comparison
sees unrelated add/removes and would silently keep both. Safe merge is impossible
without a stable identity first.

This is the gap behind the wider goal of multi-agent editing: today the docs
describe optimistic concurrency that rejects a colliding edit, but there is no
merge — no way for two agents on the same base to combine non-overlapping work,
and no structured conflict report when they do overlap.

Not in scope: runtime concurrency

To avoid confusion: this is about multiple agents editing source at the same
time (an editing/tooling concern, like git merge). It is not about Zero
programs running things in parallel (threads/async/coroutines) — that is the
separate, language-level #20 "Structured concurrency" and is unrelated here.

Proposal (identity-first)

Introduce a stable structural identity for graph nodes — derived from where
a node sits (its path from the module root: owner-edge chain + edge kind + sibling
order, falling back to the existing symbol_id for declared symbols), not from
its contents. Call it pathId.

let big: u32 = 300   →  #a1b2c3d4   pathId "main.body[0].init"
   (edit 300 → 301)
let big: u32 = 301   →  #e5f60718   pathId "main.body[0].init"   ← stable

The content hash (#id) still answers "what is this node?"; pathId answers
"which node is this?". With a stable "which," everything else becomes possible:
true diffs, collision detection, and eventually safe merge — each delivered as its
own PR below.

Why this design (short version)

• Explicit 3-way merge, not a CRDT. Edits arrive as discrete artifacts with a
  known common base and a hash precondition — the textbook case for 3-way merge.
  A CRDT is built to never surface a conflict (it silently picks a winner), which
  is the opposite of what an agent needs: we want to be able to refuse and explain.
• Detect before resolve. Syntactically-clean merges can still be semantically
  wrong ("compiles but broken"). So we report conflicts first and only
  auto-combine the provably-safe (non-overlapping) case; smarter resolution comes
  later, carefully.

(Full background — industry merge algorithms, the conflict taxonomy, and Zero's
exact internals — can be expanded in comments; kept short here for readability.)

Roadmap — one PR per item (each a candidate sub-issue)

Each item is independently shippable and useful. PRs 1–3 only read and report —
they cannot corrupt a graph. Check items off as they land.

• PR 1 — Stable structural node identity. ✅ Done via Stabilize program graph node identity #355.

  • Delivered as: the primary node id is now content/source-path-independent and edit-stable (structural hash of module + owner-edge chain + edge kind + sibling order, with collision and sibling-insert preservation), rather than a separate additive pathId field. Implementation in native/zero-c/src/program_graph_node_id.c. This answers the first open question below (identity is id-based).
  • Superseded: PR Add stable structural node identity (pathId) to the program graph #310 (pathId) closed as redundant — same structural inputs, less robust (raw order at every level → unstable under sibling inserts; no dedup), and id is already the patch handle.

• PR 2 — Node-level "what changed" diff.

  • Goal: compute a real changeset between two graph versions.
  • Scope: [{ pathId, change: added|removed|modified, fieldChanges }], keyed on PR 1's identity (today's compare reports only the first difference). Optional read-only zero graph diff --base <a> <b> --json.
  • Value alone: "what changed between two versions" for review/inspection.
  • Risk: low — read-only.
  • Acceptance: a value edit shows as one modified entry (not add+remove); add/delete classified correctly.
  • Tests: unit + conformance entry.

• PR 3 — 3-way collision detection (detect-only).

  • Goal: given base + two edited versions, report whether/how they conflict.
  • Scope: zero graph merge --base <base> <ours> <theirs> --json; build two changesets, classify overlaps (edit/edit, edit/delete, add/add, ancestor-coupling), emit a structured conflict report. Writes no merged graph. Defines GMG### codes + the conflict-report JSON shape (snapshot-tested, test: add diagnostic schema conformance snapshots #232 style).
  • Value alone: two agents learn if they collided, with actionable detail instead of a blunt reject.
  • Risk: low — read-only.
  • Acceptance: disjoint edits → "no conflict"; same-node divergent edits → reported with both sides; codes documented.

• PR 4 — Auto-combine non-overlapping edits (first real merge).

  • Goal: when two edits don't conflict, produce one merged program.
  • Scope: for the conflict-free case (disjoint pathIds and no ancestor coupling), emit the merged .0/artifact; refuse and report on any conflict; honor the base graphHash precondition; re-validate the result.
  • Value alone: the headline — two agents working in parallel on disjoint regions, merged safely.
  • Risk: moderate — first mutating path; guarded by the ancestor-coupling check.
  • Acceptance: A edits foo, B edits bar → merged graph contains both, validates; any overlap → no write, conflict report.

• PR 5 — Trivial convergences + order-insensitive lists.

  • Auto-resolve identical edits, delete/delete, identical add/add, and inserts into commutative lists (imports, params, fields, args).

• PR 6 — Field-level disjointness.

  • Rename + body-edit (or two edits to orthogonal fields of one node) compose instead of conflicting.

• PR 7 — Move-aware resolution.

  • Handle parent-moved/child-edited; detect move/move cycles.

• PR 8 — Semantic post-merge checks (detect-only).

  • Run zero graph check on the merged graph for reference/type integrity; report, don't auto-fix.

Alignment with existing direction

• How does Zero plan to guarantee deterministic, machine-stable compiler semantics for agents across compiler versions #151 (deterministic, machine-stable semantics; stable symbol identities) — PR 1 is a direct down payment.
• Stabilize machine-readable diagnostic and repair-plan contracts #173 (stable machine-readable contracts) — GMG codes/JSON adopt its versioning approach.
• Add agent-safe edit previews to fix-plan JSON #141 / feat: add structured edit previews to fix-plan JSON #137 / Add structured edit previews to fix-plan JSON #6 (structured edit previews) — the conflict report reuses that preview shape.
• test: add diagnostic schema conformance snapshots #232 (diagnostic schema snapshots) — new codes/shapes ship with snapshots.
• Foundations already documented: graph-as-interface and graphHash stale-check
  (README,
  graph.md,
  cli-reference.md).

Open questions for the maintainer

1. Is path-based identity (owner-edge chain + order, symbol_id fallback) the
   right model, and should pathId be a first-class field everywhere (helping
   How does Zero plan to guarantee deterministic, machine-stable compiler semantics for agents across compiler versions #151) or kept merge-internal?
2. Command surface: graph merge --base <b> <ours> <theirs>, or a patch-file
   form? Support a 2-way fallback (no explicit base) or require the base?
3. Is GMG the right error-code namespace? Adopt Stabilize machine-readable diagnostic and repair-plan contracts #173's versioning from day one?
4. Should merge always go through the source-backed path (write .0), or also
   support artifact-only merges for intermediate agent steps?

Non-goals

• Runtime concurrency / parallel execution (that is Structured concurrency #20).
• Full semantic auto-resolution of conflicting edits on day one (PRs 6–8, later).

---

Spec-first proposal. Happy to split each PR item above into its own linked
sub-issue if preferred.

[ctate]

Good call-out @PeterXMR. Stable ID's will be part of a larger effort to make zerolang graph-canonical. Should be landing this week or next

[PeterXMR]

Update: the foundational step (stable identity) has landed via #355.

#355 ("Stabilize program graph node identity") makes the primary node id structurally derived (module + owner-edge chain + edge kind + sibling order) and independent of content and source path, so a node's id now survives content edits — and, via its collision / "ID-theft" handling, sibling inserts and reorders too. The old content-hash graph_stable_node_id() is gone; id assignment now lives in native/zero-c/src/program_graph_node_id.c (z_program_graph_assign_source_node_ids).

Consequences for this RFC:

• PR 1 (stable identity) — ✅ done by Stabilize program graph node identity #355, on the primary id rather than a separate pathId field. This also answers the first of the "Open questions for the maintainer" below: identity is id-based, not a parallel pathId.
• My implementation PR Add stable structural node identity (pathId) to the program graph #310 (pathId) is closed as superseded — it duplicated Stabilize program graph node identity #355's structural inputs, was less robust (raw order at every level → unstable under sibling inserts; no collision handling), and id is already the patch handle.
• The original TL;DR / "The problem" framing is now outdated (IDs are no longer content fingerprints); I've updated the body with a status banner and marked the historical sections as pre-Stabilize program graph node identity #355.

Still open and unbuilt — the actual point of this issue: building on the stable id toward real multi-agent editing — diffs (PR 2), 3-way collision detection (PR 3), and safe auto-merge of non-overlapping edits + structured conflict reports (PR 4–8). Happy to re-anchor those on id and split them into sub-issues. @ctate — is merge tooling the next step you'd want, or is that subsumed by the broader graph-canonical effort?