Your browser sucks, JavaScript disabled! Gunnar's console needs JavaScript and WebAssembly. Git over SSH on port 2222 does not.

nordisk/nornir

.nornir/manual-mimir/05-lenses-and-data-structures.md

5. Lenses and the data structures behind them

In short. Mímir has 24 lenses (18 table-fed lenses plus 6 clone-signal lenses). Every lens answers from three shared layers: the code room (one GraphBLAS sparse matrix per edge kind), the lake tables (Iceberg), and the exact pair index for vectors. This chapter says, per lens, what it reads, which in-memory structure it builds, its algorithm, and what its cost is.

State: nornir main 72567d4a (2026-10-17). subclone is a separate source-text lens without a gRPC verb and is listed last.

5.1 The shared layers

Layer What it is Where
Room The fold of the event log (code_node_events, code_edge_events, code_span_events, plus the binary stream) for one scope (repo → seq, dependencies on/off). crates/mimir-room
Name table One sorted string blob plus offsets; the ordinal is the lexicographic position, so two snapshots map monotonically into their union. mimir-room
Edge matrices One boolean CSR GrB_Matrix per edge kind (CALLS, USES_TYPE, READS_FIELD, CONTAINS, IMPLEMENTS, …). Unions, transposes and the Jikes matrix are built on first use and kept by kind mask. mimir-room, crates/mimir-graph
GraphBLAS ops reach, reverse_reach, min_hops, bottleneck, max_on_path, A·Aᵀ similarity, propagate, components, diff, union. crates/mimir-graph/src/ops.rs
Read-fast tables code_nodes_v, code_edges_v, code_spans_v: one row per version with [valid_from_seq, valid_to_seq), partitioned by repo; an anchor per repo says how far it is complete. The room fold reads these plus the event tail. Lenses never read them directly. crates/mimir-ingest/src/readfast.rs
Pair index Process-wide, exact (no approximate search): L2-normalised rows × dim f32, dedup by raw bits, every pair with cosine ≥ 0.80 kept as (u32, u32, f32). Incremental: new rows are joined against all rows. One index per space (text vectors, role). src/vector/pair_index.rs
Jera lanes Room-fed lenses run as mimir_lens_answer jobs on the lenses lane; the door answers queued/running with the job id. anomaly, generic_cost and binary_drift need no room and are answered inline. Room builds go one at a time. src/server_grpc.rs, src/mimir_lens/queued.rs
Caches Room snapshots: LRU of 4 per log identity + scope. Lens answers: AnswerCache (48) keyed by room version + lens + params, so a consume that moves the room drops the answer. fn_role_vectors keeps role vectors by stable id + feature hash; embeddings are keyed by content hash.

Words used in the tables:

5.2 Graph lenses (GraphBLAS reach and edge scans)

Lens Meaning Reads Structures Algorithm Cost
zombie_features Cargo features never built, or gating items nothing reaches room (feature nodes, ENABLES, GATED_BY, CALLS, USES_TYPE); bin_ingest_runs, binary_facts, section_sizes, symbol_sizes room masks; maps repo → declared/built feature sets, inbound counts, path → bytes declared − built = never built; gated items with 0 inbound CALLS/USES_TYPE = unreached a few edge scans + symbol loads; kept
change_risk Per-file risk = callers × churn (90 days) × (1 − coverage) room callables, CALLS, tests; coverage_fn; git_heat_facts callable list; map (repo, file) → facts span join to coverage, else test reach (BFS) as fallback one BFS from all tests + one CALLS scan + 2 table scans; kept
bench_gaps Hot modules with no bench room callables + module; git_heat_facts, bench_runs, bench_results map repo → module → facts hot = fan-in × churn × perf hint × coverage; gap = hot − benched − allowlist CALLS scan + test BFS + 3 scans; kept
weak_tests Tests that never went red while their code churned test_outcomes, bench_runs, git_heat_facts; room tests, CALLS map (repo, test) → nodes, churn per test per test: forward CALLS reach (BFS) → files → Σ commits; verdict from run history one BFS per test (dominant); kept
villa Impure call sites (process, exec, exit) room names, CALLS, edge sites; checkout text impure map, target mask, file text cache CALLS edges into the impure mask, one finding per site small edge scan + file reads; per repo; kept
trust Act / hold / refuse via the weakest link from entry points room callables, CALLS, impure items, test reach dense u64 weight vector, masks local trust → bottleneck (max, min) semiring fixpoint (vxm MAX_FIRST_UINT64 + eWise min) → min hops → witness path fixpoint over CALLS + one path per worst node; per repo; kept
name_collision CALLS landing on an id the fold merged room callables, CALLS, duplicate keys maps name → count, inbound edges per merged key against a leaf-name baseline CALLS scan + dup-key list; kept
symbol_identity Merged ids: repeated in a unit vs units disagree room duplicate keys, definitions, spans key fact list classify by duplicate rows / distinct payloads linear in dup keys; kept
undoc_api Public functions without docs, ranked by churn room callables + visibility/doc attrs, IMPLEMENTS; git_heat_facts API list, set of trait impls filter + join (repo, file) with commits linear; per repo; kept
reachable_vuln Advisories that our own code really uses at that version vuln_findings, sbom_components; room CALLS + USES_TYPE from own code map (repo, crate, version) → uses vuln ⋈ sbom, demoted when no own edge reaches the crate (one hop) edge scan + 2 scans; kept
data_reach Which code reaches which warehouse table room TOUCHES_TABLE (+ access), CALLS, visibility map toucher → reachers per toucher: reverse CALLS walk (BFS) inside own code one reverse BFS per toucher; kept
world_impact The last commit's changes ranked by ripple two as-of rooms (seq − 1, seq); current room; dep_graph_edges windows per (repo, seq), diff Room::diff (added = B⟨¬A⟩, removed = A⟨¬B⟩ per kind + payload hash) → dependents (reverse BFS over the Jikes kinds) two as-of room folds per repo (tens of seconds), memoised per (repo, seq)

5.3 Table lenses (no room or only a light one)

Lens Meaning Reads Structures Algorithm Cost
churn Band filter over change frequency × complexity git_heat_facts (all generations); room functions per file change series; map (repo, file) → fn count frequency band filter; hotspot = frequency × complexity heat table scan; per repo; kept
anomaly Outliers in the change series git_heat_facts only change series; mean/std, EWMA z-score of the latest interval against its own baseline + EWMA check one scan; no room, answered inline, not kept
generic_cost Monomorphisation cost per artifact bin_ingest_runs (Build Thing); binary_facts, section_sizes, symbol_sizes map (artifact, crate, generic) → (n, bytes) group instances by de-generic'd name; cost = total − total / N symbol table of the latest artifact per variant; inline, not kept
binary_drift The same artifact line diffed symbol by symbol over time as generic_cost map line → filings; reports per sha256 (memoised) dedup equal sha256; diff the last pairs 2 symbol loads per step; inline, not kept

5.4 Clone lenses (vectors, shapes, features)

Lens Meaning Reads Structures Algorithm Cost
exact_clones Same normalised body (names → roles, literals → kinds) fn_shape_events; room functions map exact key → members hash-group on the stored exact key (≥ 40 tokens) linear; shapes written per commit (changed bodies only)
near_clones MinHash Jaccard ≥ 0.80 of 5-token role shingles fn_shape_events (MinHash signature) 64-permutation MinHash; LSH 16 bands × 4 rows, buckets capped at 200 band buckets → estimate per candidate about linear; incremental per commit
structural_clones Unrelated names touching the same rare types, fields, callees room CONTAINS (param/return types), USES_TYPE, READS_FIELD, CALLS, FOR_TYPE per function a sorted list of u32 feature ids; df; idf = ln(1 + N/df); posting lists for rare features (df ≤ 64 and ≤ N/2) IDF-weighted Jaccard ≥ 0.5, ≥ 2 shared, ≥ 1 rare; candidates only from rare postings; up to 8 threads one pass over the postings; kept
role_neighbours Same role in the graph (FastRP vectors), cosine ≥ 0.90 room CALLS (both ways), USES_TYPE, READS_FIELD, CONTAINS; fn_role_vectors features; adjacency as a row-normalised GraphBLAS Matrix<f64>; 128-d f32 vectors; pair index space role sparse ±1 projection (IDF-weighted) X0, X1 = ·X0, X2 = ·X1 (mxv PLUS_TIMES_FP64); vector = ‖X0‖ + ‖X1‖ + ½‖X2‖ → exact cosine pairs incremental: stored vectors kept when the feature hash is unchanged; the 2-hop ball of changed functions recomputed (full when ≥ ¼ changed)
similar_code Copied, not moved (type-3) room functions + spans, CONTAINS, CALLS, IMPLEMENTS; embedding_node_events, embedding_node_runs, embeddings per function: dense f32 vector + callee set + signature; pair index exact cosine self-join ≥ 0.92 → structural gate (0.6 · signature + 0.4 · callee Jaccard ≥ 0.5) → union-find clusters the pair count: cold n²/2 over distinct vectors, then new × all per commit; kept
semantic_clones v2 rule: normalised-model cosine ≥ 0.90 AND (exact OR near OR structural) fn_shape_events, embeddings_norm; room CONTAINS, USES_TYPE, READS_FIELD, CALLS, FOR_TYPE exact groups, MinHash, structural features, map key → normalised vector candidates only from signals 1 + 2, then one dot product per candidate (no all-pairs) LSH + rare postings; dots on candidates only; kept
same_intent Raw-model (names included, labelled NAME-DRIVEN) type-4 clusters as similar_code vectors + pair index cosine ≥ 0.80 (or calibrated floor) AND structural ≤ 0.35, mutual kNN k = 8 + Louvain pair index; kept
semantic_twins v1 gates on v2: copy (cos ≥ 0.92 ∧ structural ≥ 0.50) / twin (cos ≥ 0.882 ∧ structural ≤ 0.35 ∧ mutual kNN 8) embedding_node_events, embeddings, fn_shape_events; room IMPLEMENTS, CONTAINS, structure edges pair index; map row → top-k; IDF features exact cosine pairs ≥ floor → mutual kNN → IDF-weighted Jaccard → MinHash body estimate per pair pair index; kept
subclone (no gRPC verb) Duplicate regions below item level checkout text + room item spans winnowing fingerprints winnowing over tokens per-repo source scan; needs a repo

5.5 Where the time goes, and what is planned

The cost of a cold ask is dominated by three things:

  1. The pair index (similar_code, same_intent, semantic_twins, role_neighbours): exact all-pairs cosine, n²/2 over about 100 000 vectors on the first run. Today it is an 8-lane dot product over all cores, compiled for plain x86-64 (SSE2).
  2. One BFS per item (weak_tests per test, data_reach per toucher).
  3. Two as-of room folds per repo (world_impact).

Ordered on 2026-10-17, under the rule that no hit may be lost (old and new answers must be identical, pair for pair, proven by a diff):

Not used by any lens today: the GPU kNN shader (knn.wgsl, feature vector-gpu) and STree64.

Where to look in the UI

Words