Composite View Assembly¶

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

The four-stage merge_overlay algorithm (tombstone-filter-first, then relation tombstones, node tombstones, overlay merge) is accurately described and matches backend/domain/graph_merge.py line-for-line for Steps 1-4d. Two divergences: the sources.files path is wrong, and Step 4e (append overlay relations) omits a tombstone-endpoint filter added to the code after the doc's verified_at_commit.

Divergences from the code — details

Sev	Where	Doc says	Code does	Evidence
MEDIUM	sources.files	sources.files lists the code file as `backend/graph_merge.py`.	That path does not exist on disk. The actual implementation lives at `backend/domain/graph_merge.py` (moved there by BL-ARCH-043, commit 1b0ab58a, well before the doc's verified_at_commit). The compiled .md page itself correctly cites `backend/domain/graph_merge.py` in its 'Module:' line and 'Related Files' section, so only the YAML's sources.files entry is stale.	`docs/manual/knowledge/workflows/composite-view-assembly.yaml:44`
MEDIUM	Step 4 — Merge remaining overlay nodes and relations / Step 4e — Append overlay relations	Step 4e ('Append overlay relations') is documented as an unconditional append: `relations = relations + overlay["relations"]` followed by unfiltered `rels_by_node` indexing of every overlay relation.	The current code (added in commit 0e0df882, 2026-08-19 — after the doc's verified_at_commit d50caf31, 2026-06-22) first filters overlay relations to drop any whose `from`/`to` endpoint is in `node_tombstones`, to prevent orphan edges pointing at removed nodes, and only appends/indexes the filtered `overlay_rels` list. The doc's code excerpt and prose do not mention this filter at all.	`backend/domain/graph_merge.py:171-185`

flowchart LR
%% generated_from: composite-view-assembly
%% verified_at_commit: d50caf3143612a76bde48787104e90a4ac202ff3
%% description: Composite View Assembly lifecycle
%% legend: owoc=overlay-wins-on-conflict
  subgraph domain
    filter-overlay-tombstones["Filter Overlay Tombstones · owoc"]
    apply-relation-tombstones["Apply Relation Tombstones"]
    apply-node-tombstones-to-base["Apply Node Tombstones To Base"]
    merge-overlay-into-base["Merge Overlay Into Base · owoc"]
  end
  filter-overlay-tombstones --> apply-relation-tombstones
  apply-relation-tombstones --> apply-node-tombstones-to-base
  apply-node-tombstones-to-base --> merge-overlay-into-base

The Composite View Assembly is the most critical operation in EIDOS: it is the function that turns raw data files into the live graph the application queries. Understanding its order of operations is essential for anyone working on the data layer or debugging graph inconsistencies.

The Problem It Solves¶

EIDOS separates immutable base data from mutable overlay data to enable crash-safe writes. But merging them is non-trivial. The naive approach — apply tombstones (deletions) to the base, then merge in the overlay — has a fatal flaw:

A node that was created in the overlay and then deleted also exists as a tombstone entry. If you apply tombstones only to the base, and then merge the raw overlay on top, you re-introduce the deleted node from the overlay layer. The node appears to be alive even though it was deleted.

This exact defect occurred as BL-FE-037 (2026-05-20). Nodes that had been overlay-created and then tombstoned continued to appear in /tree responses.

The Invariant¶

Tombstones are applied at the input boundary of the overlay layer, before any overlay-add merges into the base structures.

This is enforced as Step 1 of graph_merge.merge_overlay: filter node_tombstones from overlay["nodes"] before any subsequent step runs. If the code ever drifts from this order, the code is wrong.

Step-by-Step¶

Step 1 — Filter overlay tombstones Before touching the base at all, remove any UUID in node_tombstones from overlay["nodes"]. This prevents deleted overlay-created nodes from surviving into Step 4. A shallow copy of the overlay is made first so the original is not mutated.

Step 2 — Apply relation tombstones to base Filter out base relations and rels_by_node entries whose UUIDs appear in the tombstones set. Deleted relations must not appear in the output.

Step 3 — Apply node tombstones to base Remove tombstoned UIDs from all base index structures: nodes, parent_of, children_of, ref_index, ref_by_uid, rels_by_node, and all children-of-parent lists. After this step, the tombstoned nodes are completely absent from the base view.

Step 4 — Merge overlay into base With tombstones cleanly removed from both the overlay (Step 1) and the base (Steps 2–3), the merge is safe: - nodes.update(overlay["nodes"]) — overlay wins for identical IDs (CCR 1/8) - Populate parent_of and children_of for all overlay nodes (pass 1) - Walk the parent chain to the tree root, update tree structures and ref indexes (pass 2 — needed because overlay nodes may attach anywhere in the tree) - Append overlay relations and extend rels_by_node

Why Idempotency Matters¶

The EffectiveGraph is rebuilt on every cache miss — it is not maintained incrementally. This means merge_overlay must produce the same output given the same inputs, regardless of how many times it is called. Step 1's shallow copy ensures the input overlay is never mutated, satisfying this requirement.

`graph_merge` Engine — `merge_overlay`¶

Module: backend/domain/graph_merge.py Governing contracts: GCF Contract 06 §3.11 R37–R38 (composite-view assembly); GCF Contract 07 §3.3 (flow diagram requirement) Canonical flow diagram: docs/architecture/flow-merge-overlay.md

Purpose and Responsibilities¶

The graph_merge engine owns exactly one responsibility: applying a single overlay layer onto an already-assembled base graph to produce the effective, in-memory composite view.

What it owns:

Applying relation tombstones (soft-deletes of base-graph relations).
Applying node tombstones (soft-deletes of nodes and every relation touching them).
Merging overlay nodes and relations into the base graph structures.
Rebuilding structural indexes (parent_of, children_of, ref_index, ref_by_uid, rels_by_node, trees) for overlay-only nodes.

What it does NOT own:

File I/O — it never reads from disk. The caller (eidos_loader._load()) handles scanning for overlay files and tombstone files and passes the fully-assembled overlay dict in.
UUID derivation for new nodes or relations — that is owned by infra/key_derivation.py and domain/mutation_engine.py.
Cache management — merge_overlay must never mutate the overlay dict that the caller passed in if that dict is the cached mutation_store._overlay_cache value. (See the shallow-copy rule in Step 1 below.)
Base-graph assembly — the base graph must be fully built before this function is called.

Data Structures¶

`base_graph` (dict)¶

The mutable composite graph that merge_overlay operates on. Assembled by eidos_loader._load() before this function is called. All keys except relations are mutated in place; relations is reassigned.

Key	Type	Description
`"nodes"`	`dict[str, dict]`	Maps node UUID → node entry dict. The node entry contains at minimum `"label"`, optionally `"parent"`, `"engineering"`, and `"productType"`.
`"relations"`	`list[dict]`	All effective relations. Reassigned (not mutated in place) by this function — callers must read `base_graph["relations"]` after the call.
`"trees"`	`list[dict]`	List of tree objects. Each tree has `"root"` (UUID string) and `"children"` (dict mapping parent UUID → list of child UUIDs).
`"parent_of"`	`dict[str, str]`	Maps child UUID → parent UUID for every non-root node.
`"children_of"`	`dict[str, list[str]]`	Maps parent UUID → list of child UUIDs.
`"ref_index"`	`dict[str, str]`	Maps dotted ref path string (and its alt form) → node UUID. Used by `key_derivation.resolve_ref`.
`"ref_by_uid"`	`dict[str, str]`	Reverse map: node UUID → canonical dotted ref path.
`"rels_by_node"`	`dict[str, list[dict]]`	Maps node UUID → list of all relations where that node appears as `"from"` or `"to"`.

`overlay` (dict)¶

The overlay layer dict, typically the value of mutation_store._overlay_cache. Treated as read-only by this function except for a controlled shallow copy in Step 1.

Key	Type	Description
`"nodes"`	`dict[str, dict]`	Maps overlay node UUID → overlay node entry. Wins over base for identical UUIDs (CCR Rules 1, 8).
`"relations"`	`list[dict]`	Overlay relation entries. Each entry must have `"from"` and optionally `"to"`. Overlay relations carry `"_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).

Node entry dict¶

A node entry inside nodes has the following fields relevant to this engine:

Field	Type	Notes
`"label"`	`str`	Human-readable name. Used by `_build_ref` to construct the dotted ref path.
`"parent"`	`str` \| absent	UUID of this node's parent. If present, drives `parent_of` and `children_of` indexing.
`"engineering"`	`list`	Preserved from base when the overlay entry does not explicitly include it.
`"productType"`	`any` \| `None`	Preserved from base when the overlay entry does not explicitly include it and base value is not `None`.

Relation entry dict¶

Relation entries in relations and rels_by_node use:

Field	Type	Notes
`"from"`	`str`	Source node UUID. Used for tombstone filtering and `rels_by_node` keying.
`"to"`	`str` \| absent	Target node UUID. May be absent for open-ended relations.
`"source"`	`str`	UUID of the seeded relation (present on base-graph relations). Used to match against `tombstones`.
`"_overlay"`	`bool`	Present and `True` on overlay relations. Tombstone filtering skips these — a relation tombstone only targets seeded relations.

Key Functions¶

`merge_overlay`¶

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

Parameters:

base_graph — The assembled base graph dict (see structure above). Most keys are mutated in place. Must be fully assembled before this call: all base nodes loaded, parent_of/children_of/ref_index/ref_by_uid/rels_by_node/trees all built.
overlay — The overlay layer dict (see structure above). Must be treated as potentially shared/cached. This function will shallow-copy it if it needs to modify the "nodes" sub-dict.

Return value: dict — Returns base_graph (the same object). The return value is the same reference passed in. The only reason to capture the return value is for chaining; the caller's existing reference to base_graph is equally valid after the call.

Exceptions raised: None raised directly. However, if base_graph is missing required keys, a KeyError will propagate from the local variable assignments at the top of the function.

Typical usage:

# In eidos_loader._load(), after base-graph assembly and overlay scanning:
base_graph = merge_overlay(base_graph, overlay)
# base_graph["relations"] is now the effective relation list
effective_relations = base_graph["relations"]

`_build_ref` (private)¶

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

Constructs the canonical dotted ref path for a node by walking the parent_of chain from the node up to the tree root, collecting labels, then joining them.

The root segment is used verbatim. All subsequent (child) segments have their leading non-alphanumeric characters stripped via _strip_prefix. This means a node with label = "+FFL" at the root and a child with label = "CTP10" produces the ref "+FFL.CTP10", not "FFL.CTP10" — the sigil is preserved on the root only.

Not intended for use outside graph_merge.py. The public entry point for ref resolution is infra.key_derivation.resolve_ref.

`_strip_prefix` (private)¶

def _strip_prefix(segment: str) -> str:

Strips leading non-alphanumeric characters from a single path segment using re.sub(r"^[^a-zA-Z0-9]+", "", segment). Used by _build_ref when building child segments of a ref path.

Order of Operations¶

The order of the four steps inside merge_overlay is a hard contract. If the order changes, the result is incorrect. The canonical reference is docs/architecture/flow-merge-overlay.md.

Step 1 — Filter tombstoned entries from the overlay input (BL-FE-037, R37)¶

_node_tombstones_pre: set = overlay.get("node_tombstones", set())
if _node_tombstones_pre and overlay.get("nodes"):
    _filtered_overlay_nodes = {
        uid: n for uid, n in overlay["nodes"].items()
        if uid not in _node_tombstones_pre
    }
    if len(_filtered_overlay_nodes) != len(overlay["nodes"]):
        overlay = dict(overlay)           # shallow copy — do not mutate cached dict
        overlay["nodes"] = _filtered_overlay_nodes

Why this must come first: A node can have both an overlay file on disk (created by an earlier mutation) and a tombstone file on disk (created by a later delete). This is the create-then-delete lifecycle. If Step 1 were skipped or placed after Step 4, the later nodes.update(overlay["nodes"]) call would silently re-introduce the deleted node into the graph. This was the exact defect logged as BL-FE-037 (2026-05-20).

Why a shallow copy, not a deep copy: Only the "nodes" sub-dict is replaced. The other overlay keys ("relations", "tombstones", "node_tombstones") are only read, never written. A deep copy is unnecessary and would be expensive for large overlays.

Step 2 — Apply relation tombstones¶

tombstones: set = overlay.get("tombstones", set())
if tombstones:
    relations = [r for r in relations if r.get("_overlay") or r.get("source") not in tombstones]
    for nid in list(rels_by_node):
        rels_by_node[nid] = [r for r in rels_by_node[nid]
                             if r.get("_overlay") or r.get("source") not in tombstones]

Relation tombstones target base-graph (seeded) relations by their "source" UUID. Overlay relations ("_overlay": True) are never removed by relation tombstones — they have their own removal path (they simply would not have been added to overlay["relations"] in the first place). Both the flat relations list and the per-node rels_by_node index are filtered.

Step 3 — Apply node tombstones to base structures¶

node_tombstones: set = overlay.get("node_tombstones", set())
if node_tombstones:
    for uid in list(nodes):
        if uid in node_tombstones:
            del nodes[uid]
    relations = [r for r in relations
                 if r.get("from") not in node_tombstones
                 and r.get("to") not in node_tombstones]
    for nid in list(rels_by_node):
        if nid in node_tombstones:
            del rels_by_node[nid]
        else:
            rels_by_node[nid] = [r for r in rels_by_node[nid]
                                 if r.get("from") not in node_tombstones
                                 and r.get("to") not in node_tombstones]
    for nid in node_tombstones:
        parent_of.pop(nid, None)
        children_of.pop(nid, None)
        ref = ref_by_uid.pop(nid, None)
        if ref is not None:
            key_derivation.unindex_ref(ref_index, ref, nid)
    for kids in children_of.values():
        kids[:] = [k for k in kids if k not in node_tombstones]

A tombstoned node is removed from every structure: nodes, relations, rels_by_node, parent_of, children_of, ref_index, and ref_by_uid. The last loop also removes tombstoned UIDs from the children lists of non-tombstoned parents — without it, a parent node's children_of entry would still reference the deleted child.

key_derivation.unindex_ref is used for ref cleanup rather than a direct del ref_index[ref] because a ref key might collide with another node (BL-DM-010). unindex_ref takes the uid argument and only removes index entries that still point to that specific UID.

Note that the overlay file and tombstone file both remain on disk. The effective in-memory view is a projection; the on-disk layer stack preserves the full create-then-delete lifecycle (additive provenance invariant).

Step 4 — Merge remaining overlay nodes and relations¶

This step runs only if overlay["nodes"] or overlay["relations"] is non-empty after Step 1 filtering.

Step 4a — Preserve base fields not overridden by the overlay:

for uid, onode in overlay["nodes"].items():
    if "engineering" not in onode and uid in nodes:
        onode["engineering"] = nodes[uid].get("engineering", [])
    if "productType" not in onode and uid in nodes and nodes[uid].get("productType") is not None:
        onode["productType"] = nodes[uid]["productType"]

Overlay entries win for identical IDs (CCR Rules 1 and 8), but engineering and productType are populated from the base when the overlay did not explicitly write them. This preserves computed/inherited metadata that the overlay author did not intend to clear.

Step 4b — Merge nodes:

nodes.update(overlay["nodes"])

After field preservation above, the overlay wins for every key it does provide.

Step 4c and 4d — Two-pass structural index rebuild:

Pass 1 populates parent_of and children_of for all overlay nodes:

for uid, onode in overlay["nodes"].items():
    parent = onode.get("parent")
    if parent:
        parent_of[uid] = parent
        children_of.setdefault(parent, [])
        if uid not in children_of[parent]:
            children_of[parent].append(uid)

Pass 2 walks up the parent chain to find the tree root, then updates trees[i]["children"] and both ref indexes:

for uid, onode in overlay["nodes"].items():
    parent = onode.get("parent")
    if parent:
        tree_root = parent
        for _ in range(200):        # guard against cycles
            p = parent_of.get(tree_root)
            if not p:
                break
            tree_root = p
        for t in trees:
            if t["root"] == tree_root:
                t["children"].setdefault(parent, [])
                if uid not in t["children"][parent]:
                    t["children"][parent].append(uid)
                break
    ref = _build_ref(uid, nodes, parent_of)
    key_derivation.index_ref(ref_index, ref, uid)
    ref_by_uid[uid] = ref

Why two passes, not one: A single-pass approach would fail when an overlay file for a child node is processed before the overlay file for its parent node. During Pass 1, parent nodes that are themselves overlay-only may not yet have their parent_of entries populated, so chain-walking in the same pass would produce incorrect tree roots or incorrect ref paths. Pass 1 ensures all parent_of entries exist; Pass 2 can then safely walk any chain.

The range(200) guard prevents an infinite loop if a cycle exists in the parent chain.

key_derivation.index_ref inserts both the exact ref and the alt-form (sigil-stripped, lowercased root) into ref_index, matching the same code path used by eidos_loader._load for base nodes (BL-DM-010).

Step 4e — Append overlay relations:

relations = relations + overlay["relations"]
for r in overlay["relations"]:
    rels_by_node.setdefault(r["from"], []).append(r)
    if r.get("to"):
        rels_by_node.setdefault(r["to"], []).append(r)

Overlay relations are appended, not merged by UUID. A relation with a "to" field is indexed under both r["from"] and r["to"] in rels_by_node.

Design Constraints¶

base_graph must be fully assembled before calling merge_overlay. All base nodes must be in nodes, all base parent_of/children_of/ref_index/ref_by_uid/rels_by_node/trees entries must be built, and all base relations must be in relations. This function does not partially assemble the base graph.
Read base_graph["relations"] after the call, not a pre-call reference. The relations local variable is reassigned (not mutated in place) during Steps 2, 3, and 4e. Any caller variable that captured base_graph["relations"] before the call will refer to the old list. The function writes the new list back to base_graph["relations"] at the very end.
Never mutate the return value's relations list directly. Treat it as logically immutable after the call. Each call to merge_overlay produces a new list object for relations.
Do not pass the same overlay dict to concurrent calls. Step 1 may reassign overlay["nodes"] via a shallow copy. While the shallow-copy guard means the original cached dict is not mutated, if two concurrent calls reach the shallow-copy branch simultaneously with the same input object, a data race is possible in the local reassignment. eidos_loader serialises loads; do not bypass that serialisation.
Do not call merge_overlay more than once on the same base_graph without rebuilding it. The function mutates nodes, parent_of, children_of, rels_by_node, and the tree children dicts in place. A second call will see a partially-merged graph as its base, producing incorrect results.
Any new composite-view assembly engine or change to the order of operations requires a regression test before merge (GCF Contract 06 R38). See tests/test_node_tombstone.py.

Common Pitfalls¶

1. Holding a stale reference to relations before the call.

# WRONG — relations_before is now stale after merge_overlay runs
relations_before = base_graph["relations"]
merge_overlay(base_graph, overlay)
process(relations_before)   # does not include tombstone filtering or overlay relations

# CORRECT
merge_overlay(base_graph, overlay)
process(base_graph["relations"])

2. Forgetting that nodes IS mutated in place, but relations is NOT.

nodes.update(...) modifies the dict that was already in base_graph["nodes"]. A caller holding a reference to that dict will see the overlay nodes appear. But relations is a new list object after the call. This asymmetry is intentional (tombstone filtering and appending both produce new lists) but surprises developers who expect both to behave consistently.

3. Assuming overlay wins for ALL fields of an existing node.

Overlay wins for every key it explicitly provides, but engineering and productType are back-filled from the base when absent from the overlay entry (Step 4a). If you mutate an overlay node entry and remove "engineering" expecting to blank it in the effective graph, the base value will be restored. To truly blank a field, the overlay entry must explicitly set it to an empty value.

4. Adding overlay relations with a missing "from" key.

rels_by_node.setdefault(r["from"], []).append(r)

If an overlay relation entry has no "from" key, this line raises KeyError. Relations with a missing "to" are safe — the code checks if r.get("to") before indexing under "to".

5. Creating a cycle in the parent chain.

The two-pass index rebuild in Step 4d uses for _ in range(200) to guard against cycles. If a cycle exists (node A is parent of node B, node B is parent of node A), the walk will silently stop after 200 iterations. The node will be indexed under the wrong tree root or under no tree root at all. No exception is raised. Cycle detection must happen before mutation commands are committed, not here.

6. Expecting tombstoning to purge data from disk.

Step 3 removes nodes and relations from the in-memory effective view, but the overlay file (mutations/nodes/{uuid}.jsonld) and tombstone file (mutations/node_tombstones/{uuid}.jsonld) both remain on disk. The effective view is a projection. If you are debugging a node that should not appear in the graph but does, check whether the tombstone file actually exists on disk — merge_overlay can only apply tombstones that the caller passed in via overlay["node_tombstones"].

7. Placing any new logic between Step 1 and Step 4 that re-reads the original overlay variable.

Step 1 may rebind the local name overlay to a new shallow-copy dict. Any code added after Step 1 that reads overlay will correctly see the filtered version. But if new code were added that re-fetches the overlay from an external source (e.g., re-reading mutation_store._overlay_cache), it would bypass Step 1's filtering and reproduce the BL-FE-037 defect.

backend/domain/graph_merge.py — the implementation described in this section.
backend/infra/key_derivation.py — index_ref, unindex_ref, and resolve_ref.
docs/architecture/flow-merge-overlay.md — canonical Mermaid flow diagram with invariant rationale.
tests/test_node_tombstone.py — regression test for the create-then-delete lifecycle (BL-FE-037).
backlog/items/frontend/BL-FE-037.md — backlog item and triage history for the tombstone-merge defect.
backlog/items/data-model/BL-DM-001.md — node tombstone contract.
backlog/items/data-model/BL-DM-010.md — ref-index collision contract.

Stage Reference¶

Filter Overlay Tombstones¶

Engine: graph-merge — Zone: domain

merge_overlay — filter node_tombstones from overlay[nodes] before any merge

Invariants enforced: overlay-wins-on-conflict

Apply Relation Tombstones¶

Engine: graph-merge — Zone: domain

merge_overlay — filter base relations and rels_by_node by tombstones set

Apply Node Tombstones To Base¶

Engine: graph-merge — Zone: domain

merge_overlay — remove tombstoned UIDs from nodes, parent_of, children_of, ref_index, ref_by_uid, rels_by_node, children-of-parent lists

Merge Overlay Into Base¶

Engine: graph-merge — Zone: domain

merge_overlay — nodes.update(overlay[nodes]), overlay wins for identical IDs; populate parent_of + children_of for overlay nodes (pass 1); walk parent chain to tree root, update trees + ref indexes (pass 2); append overlay relations + extend rels_by_node

Invariants enforced: overlay-wins-on-conflict

Composite View Assembly¶

The Problem It Solves¶

The Invariant¶

Step-by-Step¶

Why Idempotency Matters¶

graph_merge Engine — merge_overlay¶

Purpose and Responsibilities¶

Data Structures¶

base_graph (dict)¶

overlay (dict)¶

Node entry dict¶

Relation entry dict¶

Key Functions¶

merge_overlay¶

_build_ref (private)¶

_strip_prefix (private)¶

Order of Operations¶

Step 1 — Filter tombstoned entries from the overlay input (BL-FE-037, R37)¶

Step 2 — Apply relation tombstones¶

Step 3 — Apply node tombstones to base structures¶

Step 4 — Merge remaining overlay nodes and relations¶

Design Constraints¶

Common Pitfalls¶

Related Files¶

Stage Reference¶

Filter Overlay Tombstones¶

Apply Relation Tombstones¶

Apply Node Tombstones To Base¶

Merge Overlay Into Base¶

`graph_merge` Engine — `merge_overlay`¶

`base_graph` (dict)¶

`overlay` (dict)¶

`merge_overlay`¶

`_build_ref` (private)¶

`_strip_prefix` (private)¶