Graph Merge Engine¶

Verified against the code · 4d5c9b5781eaaa62048db19cd10dc7039e402c98 · 2026-10-20

956 D1b-2 (2026-10-20): 8 finding(s) fixed — graph_merge has no _strip_prefix (it lives in key_derivation and eidos_loader), the caller is eidos_loader.current_graph() not _load(), _build_ref is notation-first via derive_slug_segment (WP2), line pins corrected (graph_merge.py:48/82/144/194-198, eidos_loader.py:373-395/385/397/285), base_graph['relations'] is reassigned unconditionally. Re-verified against main 4d5c9b57. #935 S1 (2026-10-21): select_domain_root added; Pass 2 logs overlay_node_orphaned for a chain that reaches no tree root (attach outcome unchanged); line pins moved (graph_merge.py:214-218, eidos_loader.py:332/422/446). Checked against archon/issue-935. #935 S7 (2026-10-22): the merge starts from empty base dicts; select_domain_root is the root source for every domain since S5a. Checked against graph_merge.py and eidos_loader.py at a11d2636.¶

Layer: domain

Overview¶

The Graph Merge Engine is the domain layer component responsible for assembling the Effective Graph — the unified view of the knowledge graph that every API call and query operates against. It does this by applying a mutable overlay (user-created nodes, relations, and soft-deletes) on top of a base graph — empty in the running backend since #935 S5a (it was once the .eidos snapshot).

The engine lives in backend/domain/graph_merge.py and exposes a single public function: merge_overlay. It is a pure transform — no file I/O, no UUID derivation, no cache management. It takes two dicts and mutates the first in-place, returning it so callers can chain or extract fields.

The engine is invoked once per graph load cycle, inside eidos_loader.current_graph() (eidos_loader no longer has a _load(); it was removed by the loader API flip, #868 Slice 8), after the empty base dicts and the tree declaration are set up and the overlay has been scanned from mutation_store. The output of merge_overlay becomes the live in-memory graph that all routes, agents, and search features read from.

Understanding this engine is a prerequisite for understanding how deletions, user mutations, and cache invalidation work throughout the system.

merge_overlay — Full Signature and Semantics¶

Full Python Signature¶

def merge_overlay(base_graph: dict, overlay: dict) -> dict:

merge_overlay is found in backend/domain/graph_merge.py, line 48.

Parameter Table¶

base_graph — the assembled base graph dict. All keys are mutated in-place except relations, which may be replaced with a new list.

Key	Type	Description
`nodes`	`dict[str, dict]`	UUID → node entry. Mutated directly: tombstoned nodes are deleted, overlay nodes are upserted.
`relations`	`list[dict]`	Flat list of all relation entries. Replaced (not mutated) after tombstone filtering. Caller must read `base_graph["relations"]` after the call.
`trees`	`list[dict]`	Tree descriptor list. Each entry has `root` (UUID), `type`, `predicate`, and `children` (parent UUID → list of child UUIDs). `children` maps are extended for overlay nodes in Pass 2.
`parent_of`	`dict[str, str]`	Child UUID → parent UUID. Extended for overlay nodes, entries removed for tombstoned nodes.
`children_of`	`dict[str, list[str]]`	Parent UUID → list of child UUIDs. Extended for overlay nodes; stale child references removed for tombstoned nodes.
`ref_index`	`dict[str, str]`	Ref-path string → UUID. Both the exact ref and the alt-form (sigil-stripped, lowercased root) are indexed per node. Tombstoned nodes have their entries removed via `key_derivation.unindex_ref`.
`ref_by_uid`	`dict[str, str]`	UUID → ref-path string. Reverse of `ref_index`. Tombstoned nodes are popped; overlay nodes are added.
`rels_by_node`	`dict[str, list[dict]]`	UUID → list of relations touching that node (as `from` or `to`). Tombstoned relation entries are purged; overlay relations are appended.

overlay — the mutation layer loaded from mutation_store.load_overlay(). The function performs a shallow copy if it must filter overlay["nodes"] (to avoid mutating the cached _overlay_cache dict).

Key	Type	Description
`nodes`	`dict[str, dict]`	UUID → overlay node entry. Overlay nodes may or may not have a corresponding base node.
`relations`	`list[dict]`	Overlay relation entries, each tagged with `"_overlay": True`.
`tombstones`	`set[str]`	UUIDs of seeded (base-graph) relations that have been soft-deleted.
`node_tombstones`	`set[str]`	UUIDs of nodes that have been soft-deleted (BL-DM-001). Covers both base-graph and overlay nodes.

The Merge Algorithm Step by Step¶

The function executes exactly four ordered phases. The order is load-bearing: violating it produces ghost entries or premature removals.

Phase 1 — Pre-filter overlay nodes against node_tombstones (BL-FE-037)

Before any structural work, overlay nodes whose UUID appears in node_tombstones are stripped from overlay["nodes"]. Without this step, the overlay-add pass in Phase 4 would re-introduce a node that Phase 3 is about to delete. Because overlay is a reference to the cached dict, the function makes a shallow copy (overlay = dict(overlay)) before replacing overlay["nodes"] with the filtered version, so the cache is never corrupted.

Phase 2 — Apply relation tombstones

tombstones contains UUIDs of seeded (base-graph) relations that have been soft-deleted by the user. This phase rebuilds relations as a list comprehension that drops any entry whose source field matches a tombstone UUID, provided the entry is not an overlay relation (overlay relations are immune; they carry "_overlay": True). rels_by_node is purged in parallel — for every node bucket, entries matching the tombstone set are removed.

This phase runs even when overlay["nodes"] and overlay["relations"] are both empty, because tombstone-only changes (a deletion with no other mutations) must still take effect.

Phase 3 — Apply node tombstones (BL-DM-001)

Node tombstones propagate across every structural index:

Each tombstoned UUID is deleted from nodes.
relations is rebuilt (new list) dropping any entry where from or to is tombstoned.
rels_by_node entries for tombstoned nodes are deleted entirely; entries for surviving nodes have any relation that touches a tombstoned node purged from their bucket.
parent_of and children_of are cleaned: tombstoned entries are popped. Then every surviving children_of bucket has the tombstoned UIDs removed from its child list.
ref_index and ref_by_uid are cleaned via key_derivation.unindex_ref(ref_index, ref, nid), which removes both the exact ref key and the alt-form key, but only when the entry still points to the tombstoned UID (BL-DM-010 safety: a colliding key owned by a different node is never removed).

The overlay file and tombstone file both remain on disk after this phase. The layer stack preserves the full history ("existed, then deleted"). Rolling back a deletion means removing the tombstone file — no data migration required.

Phase 4 — Merge surviving overlay nodes and relations

This phase runs only if overlay["nodes"] or overlay["relations"] is non-empty after Phase 1.

Node merge (overlay-wins rule, CCR Rules 1 and 8):

Before calling nodes.update(overlay["nodes"]), two fields from the base node are preserved when the overlay entry does not override them:

engineering: the list of instance properties attached to the node. If the overlay entry omits engineering, the base node's value is copied into the overlay entry before the update.
productType: similarly copied if absent from the overlay entry and present on the base node.

After this preservation step, nodes.update(overlay["nodes"]) applies all overlay nodes, overwriting base entries for any shared UUID.

Structural index update — Pass 1 (parent_of and children_of):

For every overlay node that has a parent field, parent_of[uid] = parent is set and children_of[parent] is extended with uid (de-duplicated).

Structural index update — Pass 2 (tree children and ref indexes):

Because overlay nodes can be children of other overlay nodes, Pass 1 must complete for all overlay nodes before Pass 2 begins. Pass 2 walks the parent_of chain upward (bounded to 200 hops to prevent infinite loops on malformed data) to find the tree root, then locates the matching tree in trees and extends t["children"][parent] with the new child UID. When the chain reaches no declared tree root (an orphan — e.g. its parent id names no node), the node is still added to nodes, parent_of and children_of but to no tree, and a warning overlay_node_orphaned (uid, parent, chain_top) is logged (#935 S1). It also calls key_derivation.index_ref(ref_index, ref, uid) — which indexes both the exact ref and the alt-form key — and sets ref_by_uid[uid] = ref. The ref path itself is computed by _build_ref.

Relation merge:

Before the concat, the overlay relations are filtered against node_tombstones (graph_merge.py:214-218): any overlay relation whose from or to endpoint is tombstoned is dropped, so a cascade-delete cannot leave orphan edges in the composite view (Contract 06 §3.11 R37-R39). The filtered list is overlay_rels, and relations = relations + overlay_rels creates a new list (the existing list is never mutated). Each surviving overlay relation is appended to rels_by_node under r["from"], and under r["to"] only when r.get("to") is set.

Finally, base_graph["relations"] = relations writes the new list back into the dict so the caller sees it.

Return Value¶

merge_overlay returns base_graph — the same dict object passed in. All keys except relations have been mutated in-place. relations is always reassigned — to a new list when tombstones were filtered or overlay relations added, otherwise to the same list (see Empty overlay below). The caller in eidos_loader.current_graph() reads _base["relations"] after the call to obtain the updated relation list.

Internal Helpers¶

`_strip_prefix` (in `infra/key_derivation.py`)¶

def _strip_prefix(segment: str) -> str:
    return re.sub(r"^[^a-zA-Z0-9]+", "", segment)

Strips any leading non-alphanumeric characters from a single ref path segment. This normalises sigil-prefixed tree roots — for example, "+FFL" becomes "FFL", "&Disciplines" becomes "Disciplines" — so that cross-domain callers who address a node without knowing the source domain's sigil convention can still resolve it.

graph_merge.py has no _strip_prefix of its own. It imports infra.key_derivation, and its _build_ref reaches the rule through key_derivation.derive_slug_segment. The function itself lives in infra/key_derivation.py (line 280, used by derive_slug_segment, resolve_ref and _alt_ref) and, as a separate copy, in persistence/eidos_loader.py (line 26).

Example:

Input	Output
`"+FFL"`	`"FFL"`
`"&Disciplines"`	`"Disciplines"`
`"ELECT"`	`"ELECT"`
`"---legacy"`	`"legacy"`

`select_domain_root`¶

def select_domain_root(overlay_nodes: dict, *, world_uid: str, domain: str) -> str:

Returns the domain root of every domain (#935 S1; since S5a the overlay is the only root source): the one overlay node with no parent, other than world_uid. The id is read from the overlay as-is, never derived. Zero or several candidates raise OverlayRootConflictError (domain, sorted candidate_ids). A node whose parent is world_uid is not a candidate; when there is no parentless candidate but such nodes exist, the error carries them as sorted world_parented_ids and its message names that case. The chain is not repaired. Called on every rebuild by eidos_loader._overlay_only_tree(), with tombstoned nodes already removed.

`_build_ref`¶

def _build_ref(uid: str, nodes: dict, parent_of: dict) -> str:

Constructs the dotted ref-path for a node by walking the parent_of chain from the node up to the tree root, reversing it into root-first order, and joining the segments with .. Since WP2 (#951) each segment is the node's stored notation (skos:notation, surfaced as notation) when present, else key_derivation.derive_slug_segment(label, is_root=not segments) — the root label verbatim, every later label with _strip_prefix applied. Ancestors missing from nodes are skipped.

_build_ref exists in graph_merge.py because Phase 4 must index overlay nodes into ref_index using the same algorithm that eidos_loader.current_graph() uses for base nodes. The loader has a local _build_ref closure (line 332 of eidos_loader.py) that takes only uid as a parameter and closes over nodes and parent_of. The module-level version in graph_merge.py takes all three arguments explicitly to remain a pure function with no closure dependencies.

Example: given a node "CTP10" with label "CTP10", parent "FFL" with label "+FFL", no grandparent, and no stored notation on either:

parts = ["CTP10"]
Walk to "+FFL": parts = ["CTP10", "+FFL"]
Reverse: ["+FFL", "CTP10"]
Join: derive_slug_segment("+FFL", is_root=True) = "+FFL" (verbatim), derive_slug_segment("CTP10", is_root=False) = "CTP10" → "+FFL.CTP10"

key_derivation.index_ref then also stores "ffl.CTP10" (the alt-form) so that resolve_ref succeeds for cross-domain callers who use the stripped, lowercased form.

Data Contracts¶

base_graph Expected Keys¶

All eight keys listed in the parameter table are required. The function does not guard against missing keys — a KeyError on base_graph["nodes"] (line 82) is the first failure point if a key is absent. The caller (eidos_loader.current_graph) always constructs the dict with all eight keys before calling merge_overlay.

overlay Expected Keys¶

All four keys are optional at the dict level: the function uses .get(key, default) for each. An overlay with no user mutations is {"nodes": {}, "relations": [], "tombstones": set(), "node_tombstones": set()}.

Output EffectiveGraph Keys¶

After merge_overlay returns, base_graph contains the Effective Graph. The keys are identical to the input; only their values change:

Key	Post-call State
`nodes`	Base nodes minus tombstoned nodes, plus overlay nodes (overlay wins on collision).
`relations`	New list: base relations minus tombstoned relations, plus overlay relations.
`trees`	Same list object; `t["children"]` maps extended with overlay-node children.
`parent_of`	Extended with overlay parent links; tombstoned entries removed.
`children_of`	Extended with overlay children; tombstoned children removed from all buckets.
`ref_index`	Extended with overlay node ref and alt-form keys; tombstoned node keys removed.
`ref_by_uid`	Extended with overlay node entries; tombstoned node entries removed.
`rels_by_node`	Extended with overlay relations; tombstoned relation and tombstoned node buckets removed.

Edge Cases and Failure Modes¶

Empty base_graph¶

If base_graph["nodes"] is {} and base_graph["relations"] is [] (e.g., an uninitialised domain), merge_overlay completes without error. Tombstone phases iterate over empty collections and are no-ops. Phase 4 adds overlay nodes and builds ref_index entries from their parent_of chains. The resulting Effective Graph contains only overlay content.

Empty overlay¶

If overlay["nodes"] is {} and overlay["relations"] is [], and both tombstone sets are empty, the function reaches the if overlay["nodes"] or overlay["relations"] guard (line 144) and skips Phase 4. base_graph["relations"] = relations still runs unconditionally at the end (line 205, outside the Phase 4 guard); with no tombstones it reassigns the same list object, so the caller must not assume a new list was created.

ID Collision Handling¶

When an overlay node shares a UUID with a base node, nodes.update(overlay["nodes"]) overwrites the base entry (overlay-wins, CCR Rules 1 and 8). Before overwriting, engineering and productType are copied from the base entry into the overlay entry if the overlay does not set them, preventing silent data loss of instance properties and product type classifications.

If two overlay nodes share a UUID (which should not happen because UUIDs are content-derived via UUID v5), the last writer in dict iteration order wins — nodes.update provides no collision detection. The caller is responsible for ensuring overlay uniqueness before calling merge_overlay; the mutation pipeline enforces this via deterministic UUID derivation (CCR Rule 16).

For ref_index, if two nodes produce the same ref path or alt-form key, key_derivation.index_ref silently overwrites the earlier entry. This is a known collision risk for nodes with identical label paths in different subtrees. The loader logs a diagnostic when ref resolution fails, but merge_overlay itself does not detect ref collisions.

Node Tombstoned Before Its Overlay File Is Written¶

If a tombstone file exists for a node UUID that has no corresponding base or overlay entry (e.g., the overlay file was manually deleted), the tombstone phase simply attempts to del nodes[uid] for a non-existent key. This is guarded by iterating list(nodes) and checking if uid in node_tombstones before deleting — a missing key is never accessed, so no KeyError is raised. The tombstone is silently ignored, which is the correct behaviour for an already-absent node.

Integration¶

Which Engines Call merge_overlay and When¶

merge_overlay has exactly one call site in the production codebase: eidos_loader.current_graph() in backend/persistence/eidos_loader.py — the overlay-merge block at lines 373–395, with the merge_overlay call at line 385.

The call site pattern is:

from domain import graph_merge as _graph_merge
overlay = load_overlay()

_base = {
    "nodes": nodes, "relations": relations, "trees": trees,
    "parent_of": parent_of, "children_of": children_of,
    "ref_index": ref_index, "ref_by_uid": ref_by_uid,
    "rels_by_node": rels_by_node,
}
_graph_merge.merge_overlay(_base, overlay)
relations = _base["relations"]  # may be a new list after tombstone filter

The entire import and call is wrapped in try/except ImportError so that secondary backends that do not ship mutation_store or graph_merge can still load a base-only graph.

merge_overlay is called after all base-graph assembly is complete (nodes, relations, trees, parent_of, children_of, ref_index, ref_by_uid, rels_by_node are all fully built) and before the search corpus is built. This ordering is enforced by the comment at line 446 of eidos_loader.py and was the source of a production bug (BL-FE-080, 2026-05-28): when the search corpus was built before merge_overlay ran, overlay-only projects returned no results because the search index saw only base nodes.

The graph_crud_engine (backend/domain/graph_crud_engine.py) writes tombstone files via mutation_store.write_node_tombstone and writes overlay node/relation files via mutation_store. It does not call merge_overlay directly. Changes take effect on the next call to eidos_loader.current_graph() after cache invalidation.

How It Relates to the Cache-Coherence Workflow¶

eidos_loader maintains a cached Effective Graph. When a mutation or deletion is committed, the mutation engine invalidates the cache. The next read triggers a full current_graph() rebuild, which reads the overlay only (no .eidos file since #935 S5a) and calls merge_overlay on an empty base with the current overlay state from mutation_store.

This means merge_overlay is never called on a live, partially-mutated graph — it always operates on a freshly assembled base graph. The overlay read and the base graph assembly are not atomic with respect to concurrent mutations, but the cache-coherence contract (mutation_store._overlay_cache) ensures the overlay dict passed to merge_overlay is a consistent snapshot from a single load_overlay call. The shallow-copy guard in Phase 1 (overlay = dict(overlay)) is specifically to protect this cached dict from being mutated by the pre-filter step.

The additive invariant — that overlay files and tombstone files are never deleted by merge_overlay or by the cache cycle — means that a rollback of any mutation or deletion is always possible by removing the relevant file from the mutation store, without requiring any database migration or re-derivation of base-graph data.