Graph Merge Engine¶

Verified — minor divergences from the code — 2 finding(s) · 19d408be · 2026-08-25

The compiled doc page is unusually precise: merge_overlay's signature, the four-phase algorithm order, the exact line numbers for the function definition (line 30) and the Phase-4 guard (line 126), the _strip_prefix/_build_ref helpers and their worked examples, and the eidos_loader._load() call site (verified lines 361-382 match verbatim, including the ImportError guard and BL-FE-080 ordering rationale) all match backend/domain/graph_merge.py and backend/persistence/eidos_loader.py exactly as they exist on disk. Two divergences survive: the KM entity YAML's sources.files cites a nonexistent path for the module itself, and the 'Relation merge' prose omits a real protective filter the code applies to overlay relations.

Divergences from the code — details

Sev	Where	Doc says	Code does	Evidence
MEDIUM	sources.files	KM YAML sources.files lists the code file as "backend/graph_merge.py".	No such file exists. The module actually lives at backend/domain/graph_merge.py, which is the path the compiled doc page correctly and consistently cites throughout its own prose.	`docs/manual/knowledge/engines/graph-merge.yaml:19`
MEDIUM	Phase 4 — Merge surviving overlay nodes and relations / Relation merge	"Relation merge: `relations = relations + overlay["relations"]` creates a new list (the existing list is never mutated). Each overlay relation is also appended to `rels_by_node` under both `r["from"]` and `r["to"]`."	Before appending, the code filters overlay relations against `node_tombstones`, dropping any relation whose `from` or `to` endpoint is tombstoned (cascade-delete protection, per the code's own 'Contract 06 §3.11 R37-R39' comment) — not every overlay relation is unconditionally appended. The `rels_by_node[r["to"]]` append is also conditional on `r.get("to")` being truthy, not unconditional as described. Neither detail appears anywhere in the doc.	`backend/domain/graph_merge.py:176-185`

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 the read-only base graph (the .eidos snapshot files loaded from disk).

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._load(), after the base graph is fully assembled 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 30.

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. 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:

relations = relations + overlay["relations"] creates a new list (the existing list is never mutated). Each overlay relation is also appended to rels_by_node under both r["from"] and r["to"].

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 has been replaced with a new list. The caller in eidos_loader._load() reads _base["relations"] after the call to obtain the updated relation list.

Internal Helpers¶

`_strip_prefix`¶

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.

_strip_prefix exists identically in both graph_merge.py (used by _build_ref) and infra/key_derivation.py (used by resolve_ref and _alt_ref). The duplication is intentional: graph_merge is a domain module; importing from infra for a one-liner regex would create an undesirable coupling direction.

Example:

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

`_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, collecting labels at each step, reversing them into root-first order, and joining with .. The root label is used verbatim; every subsequent segment has _strip_prefix applied to its label before joining.

_build_ref exists in graph_merge.py because Phase 4 must index overlay nodes into ref_index using the same algorithm that eidos_loader._load() uses for base nodes. The loader has a local _build_ref closure (line 291 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", and no grandparent:

parts = ["CTP10"]
Walk to "+FFL": parts = ["CTP10", "+FFL"]
Reverse: ["+FFL", "CTP10"]
Join: parts[0] = "+FFL" (verbatim), _strip_prefix("CTP10") = "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 64) is the first failure point if a key is absent. The caller (eidos_loader._load) 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 126) and exits without entering Phase 4. base_graph["relations"] is not reassigned in this path, so the caller must not assume a new list was created — though _base["relations"] still evaluates correctly because it is the original list.

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._load() in backend/persistence/eidos_loader.py, lines 361–382.

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 384 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._load(), which is triggered by 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 _load() cycle, which re-assembles the base graph from .eidos snapshot files and then calls merge_overlay 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.