# Engine Internals

Immutable base CSR uses adaptive 1/2/4-byte relationship type storage selected
once from the validated registry maximum. Logical consumers use `EdgeTypeId`;
only artifact adapters encode the physical width.

`Engine` owns the backend-local active graph and all indexes used by traversal,
search composition, sync overlays, status reporting, and persistence.

## Engine Fields

<StructDiagram title="Engine" fields={[
  { name: 'node_store', type: 'NodeStore', desc: 'node metadata, active bits, table OIDs, primary keys' },
  { name: 'edge_store', type: 'EdgeStore', desc: 'forward CSR adjacency' },
  { name: 'reverse_edge_store', type: 'EdgeStore', desc: 'inbound CSR built from forward edges' },
  { name: 'filter_index', type: 'FilterIndex', desc: 'typed filter columns keyed by node index' },
  { name: 'edge_type_registry', type: 'Vec<String>', desc: 'edge label table; index 0 is reserved for untyped root edges' },
  { name: 'resolution_store', type: 'ResolutionStore', desc: 'builder, finalized bytes, or mmap-backed lookup backend' },
  { name: 'resolution_delta', type: 'ResolutionDeltaIndex', desc: 'indexed post-build inserts that cannot mutate finalized/mmap index' },
  { name: '_mmap', type: 'Option<Arc<Mmap>>', desc: 'retains the backend-local immutable artifact snapshot' },
  { name: 'edge_buffer', type: 'Vec<EdgeMutation>', desc: 'post-build edge insert/delete overlay' },
  { name: 'projection_mode', type: 'ProjectionMode', desc: 'csr_readonly or mutable_overlay runtime mode' },
  { name: 'tenant_membership', type: 'HashMap<String, RoaringBitmap>', desc: 'tenant to allowed node set' },
  { name: 'projection_snapshot', type: 'Option<LayeredSnapshot>', desc: 'decoded immutable durable segments pinned for the installed generation' }
]} />

## Resolution Backends

`ResolutionStore` has three modes:

| Mode | When used | Lookup behavior |
|---|---|---|
| `Builder` | During node ingestion | Compact build entries |
| `Finalized` | After `finalize_resolution()` | Binary search over sorted bytes |
| `MmapBacked` | After loading a persisted artifact | Binary search over the mmap resolution section |

`resolution_delta` is checked before the main backend. This keeps post-build
sync inserts resolvable without rewriting the immutable finalized or mmap
section. Unlike the build-time compact builder, the delta is keyed by
`(table_oid, pk_hash)` so sync-time lookups verify only matching candidates
instead of scanning every post-build insert.

<ProcessTree title="resolve(table_oid, pk)">
  <ProcessStep title="resolution_delta" />
  <ProcessStep title="Builder | Finalized | MmapBacked" />
  <ProcessStep title="node_store.is_active(node_idx)" />
</ProcessTree>

## Edge Type Registry

The registry starts as:

```text
index 0 = ""
index 1..1,000,000 = user relationship labels (subject to byte limits)
```

`Engine::register_edge_type()` returns existing IDs when labels are reused and
raises `EdgeTypeLimit` at the configured count or byte policies. Runtime
consumers use the checked logical `EdgeTypeId(u32)` authority. New v7 base CSR
uses adaptive 1/2/4-byte IDs; the v6 reader and mutable segment codecs retain
checked legacy readers. Mutable v7 segments are adaptive too. P8.2 durable sync
sorts and interns unseen committed labels under the writer lock, then publishes
the cumulative dictionary and matching segments in one generation.

## Traversal Dispatch

Engine traversal does:

1. Verify the engine is built.
2. Resolve the seed table+PK to `node_idx`.
3. Resolve the requested edge label strings to checked logical `EdgeTypeId`
   values.
4. Reserve candidate, overlay, frontier, and result workspace under the query
   governor.
5. Borrow the installed generation's pinned layered snapshot and build only
   sync and transaction-local edge overlay maps for the chosen
   direction.
6. Build `BfsConfig`.
7. Choose forward or reverse CSR based on direction.
8. Run BFS or DFS with work, elapsed, and PostgreSQL interrupt checks.
9. Convert node indices back to source coordinates and edge labels.

<PipelineDiagram>
  <PipelineStep title="request" />
  <PipelineStep title="resolve seed" />
  <PipelineStep title="edge type filter" />
  <PipelineStep title="sync + tx overlay" />
  <PipelineStep title="BfsConfig" />
  <PipelineStep title="strategy">
    - `bfs::execute`
    - `bfs::execute_dfs`
  </PipelineStep>
  <PipelineStep title="to_traversal_results" />
</PipelineDiagram>

## Overlay Semantics

`edge_buffer` contains ordered mutations:

```rust
pub struct EdgeMutation {
    pub source: u32,
    pub target: u32,
    pub type_id: EdgeTypeId,
    pub schema_reversed: bool,
    pub relationship_id: Option<RelationshipId>,
    pub kind: MutationKind,
}
```

Before traversal, the engine reduces the buffer into:

| Overlay | Type | Meaning |
|---|---|---|
| inserts | identity-aware neighbor rows by source node | Extra neighbors with direction and stable source-row relationship identity |
| deletes | identity-aware tombstones by source node | Exact source rows hidden from traversal; legacy wildcard tombstones remain explicit |

Insert after delete cancels the delete; delete after insert cancels the insert.
Transaction-local edge deltas use the same reduced insert/delete map shape and
are merged after `edge_buffer`, so reads in the current backend can observe
their own pending graph deltas without changing the immutable CSR stores.
Read-only GQL pattern expansion uses the same neighbor-source abstraction as
traversal and unweighted graph algorithms, so one-hop and bounded variable-length
relationship reads share overlay semantics with the SQL traversal APIs.
Clean CSR, pending overlay, and layered segment neighbors expose stable
relationship identity when the edge maps to a source row. This lets fixed and
wildcard path expansion preserve parallel same-type/same-endpoint source rows
as distinct matches. Hydration and writes fail closed when a mapped row lacks
the identity needed to recheck the authoritative PostgreSQL source row.
Mutable write operators use lazy transaction-delta snapshots for PostgreSQL
subtransactions. The first graph write at each active nesting level captures
the prior overlay; a subtransaction commit retains its changes, while an abort
restores the captured overlay. Callback registration seeds its depth from
PostgreSQL so a first extension call made inside an existing savepoint is safe.

## Status Computation

`Engine::status()` returns counts, memory estimates, sync status, schema state,
edge labels, projection mode, transaction-delta counts, pending sync state, and
read-only flags. Some fields are refreshed by SQL runtime helpers before
calling `Engine::status()`, including disabled trigger count, pending sync rows,
and schema drift.

## Important Invariants

| Invariant | Why it matters |
|---|---|
| `edge_type_registry[0] == ""` | Root/path formatting assumes ID 0 is reserved |
| `reverse_edge_store` matches `edge_store` | Inbound traversal must avoid scanning all edges |
| `resolution_delta` is checked first | Synced inserts shadow immutable base indexes |
| `resolution_delta` verifies candidates through `node_store` | Tombstones and hash collisions cannot resolve stale or wrong nodes |
| transaction edge deltas clear at transaction end | Uncommitted overlays must not leak across transactions or backends |
| Mapped stores retain their own `Arc<Mmap>` | Validated typed ranges cannot outlive the immutable snapshot, regardless of engine field/drop order |
| `node_store.is_active()` gates resolved nodes | Tombstones must not appear as live results |
| `edge_buffer.len() <= graph.edge_buffer_size` | Prevents unbounded overlay memory |
| Transaction deltas clear at transaction end | Rollback/commit must not leak uncommitted graph state across transactions |
