Low-Level Design

The previous chapter is the high-level design: crates, subsystems, and how they fit together, in plain language. This one is the opposite: it is the implementation contract. Exact byte layouts, exact algorithm parameters, exact failure modes, and the invariants a change must not break. Written for someone about to open a pull request.

how to read this Every constant, formula, and threshold below was read from the Rust source and is cited with its file. Where a value is tunable at runtime the environment variable is given. Where a decision has an RFC or ADR behind it, that document is named, because changing the value without updating the document is treated as a defect in this codebase.

Contents

1. Design invariants
2. Identity & the data model
3. Storage design
4. Indexing pipeline
5. Plugin & sandbox design
6. Retrieval design
7. MCP interface
8. Process & concurrency model
9. Threat model
10. Failure modes & degradation
11. Performance envelope
12. Extension points

1 · Design invariants

These are the load-bearing rules. Everything else in this document is a consequence of one of them. A change that breaks one of these is an architectural change, not a bug fix, and needs an RFC.

System map

Five tiers. Dependencies flow strictly downward: no tier calls upward, and no cycles exist in the crate graph.

Solid arrows are compile-time crate dependencies; the dashed arrow is a runtime relationship. travsr-plugin-host is outlined in red because it is the only component that executes code originating outside the repository's own binary.

2 · Identity & the data model

Four types carry the whole system. They live in travsr-core, the only crate every other crate depends on.

VName: the address

A Kythe-style five-tuple. It is the universal address space: stable across repositories, languages, and time.

struct VName {
    corpus:    String,   // "github.com/acme/foo" (canonicalised, see below)
    root:      String,   // build root / branch (usually "")
    path:      String,   // "src/payment.ts" (repo-relative, always)
    language:  String,   // "typescript"
    signature: String,   // "method:PaymentService.charge"
}

Corpus canonicalisation (ARCH-102) reduces every git remote URL form to host/org/repo: lowercase, no scheme, no .git, no trailing slash. https://github.com/acme/foo.git, git@github.com:acme/foo.git and ssh://git@github.com/acme/foo all become github.com/acme/foo. A repo with no remote gets local/<basename>, and cross-repo exports edges are impossible for it by definition.

NodeId: the hash

The SQLite primary key. BLAKE3 over a deliberately unambiguous byte stream, truncated to 64 bits.

EdgeKind: the typed relation lattice

Eleven kinds. Each carries a PageRank transition weight, and those weights are the entire reason travsr's PageRank is semantic rather than merely topological: a direct call propagates 3.3× the mass of a method override.

scale is irrelevant, ratios are not Weights are normalised per source node at every PageRank iteration (w(u→v) / Σ w(u→·)), so only the ratios between kinds affect the result. Doubling every weight changes nothing. Governed by ADR-003.

Node & Edge

struct Node {
    id:            NodeId,   // BLAKE3(VName), the primary key
    vname:         VName,
    kind:          String,   // "function" | "method" | "class" | "import" | "file" | …
    package:       String,   // sub-unit identity (ADR-005); NOT part of the hash input
    line:          Option<u32>,   // 1-based start; None for synthetic nodes
    end_line:      Option<u32>,   // span end, required by G2 attribution
}

struct Edge {
    src: NodeId, dst: NodeId, kind: EdgeKind,
    confidence: Option<u8>,   // 0–100 for ffi/call (RFC-005); None otherwise
}

provenance and language are columns, not struct fields edges.provenance ("tree-sitter" | "lsif"; lsif wins on conflict, ADR-002) and edges.language live in SQLite, set at write time, not on the in-memory Edge struct. Likewise access_corpus (RBAC scope) is a nodes column added by migration v7, not a Node field.

why kind is a String, not an enum Node kinds come from fifteen different grammars and from SCIP symbol descriptors. A closed enum would force a workspace-wide change every time a grammar introduced a new construct. EdgeKind, by contrast, is a closed enum: edges are the semantic contract of the graph and adding one must be a deliberate, compiler-enforced decision.

3 · Storage design

SQLite in WAL mode, two files. No server, no daemon required for reads, nothing to configure. Current schema version: v20.

Index strategy

Indexes here are not decoration: several exist because their absence turned a query from minutes into hours on a monorepo. Each is justified:

Migration protocol

Nineteen migrations are registered, numbered 1–11 and 13–20. (v12 exists as a .sql file but was never registered; it was the sqlite-vec approach that v16 replaced with plain blobs.) The runner applies them in order and records progress per version.

Write paths

why foreign keys are mostly off NodeIds are content hashes written in large batches; enforcing referential integrity per row would dominate indexing cost. Integrity is maintained by the writer's logic plus the node_tombstones AFTER DELETE trigger. Only symbol_aliases carries a real ON DELETE CASCADE. Migration v20 exists precisely because this choice had a cost: edge_sites rows orphaned by pre-v20 deletions lingered and surfaced as phantom occurrences in find_references, so v20 purges the historical backlog while newer write paths clean up at the source.

4 · Indexing pipeline

Phase A vs Phase B

Rust, TypeScript, Python and Dart additionally have native Phase B: tree-sitter-derived call edges with no external tool download at all. Calls it cannot resolve (a bare cross-crate call whose target file is unknown, and the file path is part of the hash) are returned as UnresolvedCall and resolved by the daemon against Phase A nodes already in the store.

The unification problem: RFC-014

Phase B originally created a node population disjoint from the tree-sitter nodes every query resolves against. The 2026-06-11 forensics on a 613k-node kubernetes index:

tree-sitter fn/method nodes with ≥1 incoming ref/call:      14 / 139,114   (0.01%)
ref/call edges whose SRC is a file node:               405,648 / 420,134   (96.6%)
ref/call edges into SCIP anonymous locals:                 272,102        (64.8%)

A graph that was rich and unreachable. get_callers answered with anonymous file (file) rows. Three passes fixed it:

Pipeline, end to end

Phase A alone yields a complete structural graph: the tool is fully usable before Phase B ever runs. Phase B only adds call edges, and G1–G3 are what make those edges land on the same nodes Phase A created rather than on a parallel population.

Incremental re-index

git commit
  └─ .git/hooks/post-commit
       └─ travsr hook-run <changed files>
            └─ try_dispatch_to_daemon()          // unix socket / named pipe
                 ├─ daemon alive  → ControlMessage::ReindexCommit{sha}
                 └─ no daemon     → in-process reindex_files()
                      ├─ SHA-256 compare vs files table   // unchanged → skip
                      ├─ delete_nodes_for_path → DirtySet
                      ├─ re-parse + write_file_graphs_batch
                      ├─ enqueue_dirty_callers(DirtySet)   // Tier-0 re-resolution
                      └─ set_meta("last_commit", sha)

5 · Plugin & sandbox design

One Plugin contract, two transports. This is the trust boundary of the entire system (RFC-011 + ADR-017).

Wire format

Length-prefixed frames over the subprocess's stdio.

The boundary

Everything crossing the dashed line is length-prefixed and size-checked before allocation. Phase A stays on the left deliberately: it reads bytes and builds an AST, so paying IPC and sandbox cost for it would buy nothing: roughly 15 s of pure transport overhead on a 50k-file repo, for zero security gain.

Defence in depth

why one sandbox policy, not one per tool The pre-ADR-017 design required a separate ADR per language indexer (scip-java, scip-typescript, scip-kotlin…). The threat is identical in every case: a semantic tool executing the indexed repo's build scripts, so re-arguing it per language was process cost with no correctness benefit. One policy now covers all sixteen.

6 · Retrieval design

The read path is where quality is won or lost. This is the full get_context pipeline with exact parameters.

Stage order

get_context(query, token_budget)
 1  validate_mcp_arg          SEC-002, reject before touching the store
 2  embed warmup + KNN        600 ms circuit breaker
 3  build_seed_set            IDF anchors + BM25 + KNN → RRF fusion
 4  cross-encoder rerank      inside seed selection; feeds PPR weight (RFC-022); 1200 ms breaker
 5  ABSTAIN GATE            Confidence::None → return resolution map
 6  enrich_seeds_with_callers depth-1 (15), depth-2 (10)
 7  dedup_adjacent_seeds      protect PPR teleportation mass
 8  ppr_weighted              α = 0.85, ε = 1e-6, ≤ 50 iterations
 9  k-core shell boost        buried-middle recovery
10  knapsack                  0-1 DP, fits token_budget
11  sanitize + envelope       SEC-001

Reranking happens inside seed selection, before PageRank runs, not as a final re-sort. Its score feeds each seed's PPR personalization weight (RFC-022), so it shapes where PageRank starts rather than just reordering a finished list. Note where the two circuit breakers sit and what happens when they fire: neither aborts the request. The KNN result is discarded and lexical seeds carry the query; the reranker is skipped and seeds keep their RRF-fused weight. The only branch that terminates early is the abstention gate.

Seed selection & the confidence lattice

Three independent candidate sources are fused by Reciprocal Rank Fusion. RRF deliberately uses rank, not score, so sources with incomparable scales (BM25 vs cosine) can be combined without normalisation.

The fused set is then classified into one of four confidence levels, which decides whether the query is answered at all:

The two dashed overlays are what make this more than a threshold ladder. Promotion lets a purely conceptual query (one with no literal symbol in it) reach Strong on embedding evidence alone. Veto does the reverse: it demotes a Weak that rests only on coincidental lexical overlap when the embedding is confident nothing in the corpus is actually near the query. Veto is what stops "get the current weather forecast" from matching hundreds of get_* functions.

Personalized PageRank

Power iteration over a subgraph materialised once by BFS, so the inner loop never touches the store.

guarded constants MAX_ITERATIONS carries a compile-time const _: () = assert!(…) that fires on every build, not just in tests, so an accidental edit is caught before release. Degenerate weight vectors (sum ≤ 0 or non-finite) fall back to uniform rather than producing NaN scores. Dangling nodes are explicitly inserted into r_next so convergence is still checked against them.

Knapsack budget enforcement

The final stage picks the highest-value subset of ranked nodes that fits the caller's token budget, a 0-1 knapsack, not a truncation.

why a 2-D DP table A rolling 1-D array computes the optimal value in less memory but cannot reconstruct which items were chosen. Backtracking needs the full table, so the implementation keeps it, and switches to greedy only when the table would exceed the cell limit.

7 · MCP interface

MCP is the only external interface. No REST, no GraphQL. Framing is newline-delimited JSON-RPC 2.0 over stdin/stdout; all diagnostics go to stderr via tracing, because stdout is the protocol channel.

Input validation: SEC-002

Applied before any store access, on every tool argument.

Output sanitisation: SEC-001

Tool output is untrusted content from an untrusted repository heading directly into a language model's context. Four steps, in order:

known gap The SSE/HTTP transport still constructs an OpenFilter rather than a per-session RbacFilter; the TODO is marked in sse.rs. The session model, the access_corpus column and the leak-test suite all exist; only the wiring on that transport is outstanding.

8 · Process & concurrency model

Two databases exist for one reason: lock separation. Embedding writes are slow and bulky, and putting them in graph.db would have the embed sidecar holding the WAL writer lock exactly when a commit needs it. The dashed path is the no-daemon fallback: every read path works without any background process running.

Processes

Control-plane protocol

Unix domain socket at .travsr/daemon-<hex>.sock (Windows: named pipe). Messages are JSON tagged by an op field in kebab-case.

enum ControlMessage {          // {"op":"reindex-commit","sha":"…"}
    ReindexCommit { sha },
    ReindexPaths  { paths },
    Status, Shutdown,
    StopEmbed, ResumeEmbed,       // pause/resume auto-reindex + cancel in-flight embed
    Query { protocol, tool, args },
}

const QUERY_PROTOCOL_VERSION: u32 = 1;

Concurrency hazards & how each is contained

Error taxonomy: ADR-004

Libraries use thiserror with a closed enum per layer; the CLI uses anyhow. Errors do not cross layers untranslated.

TravsrError          // public surface
  ├─ InvalidParams(String)
  ├─ Store(StoreError)        ├─ Database · Migration · Io
  ├─ Index(IndexError)        ├─ Parse{file,message} · Lsif · Io
  │                             ├─ PhaseNotSupported
  │                             ├─ ProtocolVersionMismatch{expected,got}
  │                             ├─ UnknownLanguage{reported}
  │                             └─ PluginCrashed{language}
  ├─ Retrieval(RetrievalError)├─ Traversal · Store
  │                             └─ PprDivergence{iterations}
  ├─ BudgetExceeded{requested, limit}
  └─ Internal

plugin errors are first-class Four of the index-error variants describe plugin misbehaviour specifically: wrong protocol version, unknown language, crash, unsupported phase. That is the type system encoding Invariant 6: a plugin is an untrusted peer, so every way it can misbehave gets a name rather than collapsing into a generic I/O error.

Observability

stdout is reserved Libraries may never println!. Stdout is the JSON-RPC channel; a stray print corrupts the protocol stream. All diagnostics go to stderr.

9 · Threat model

The adversary is a repository under index. It controls file contents, file names, directory structure, build manifests, and anything a semantic tool would execute. It does not control the user's CLI invocation.

10 · Failure modes & degradation

Every optional subsystem has a defined, visible failure behaviour. This table is the contract.

Why breakers measure after, not before

deliberate trade-off Both the KNN and rerank breakers time the call and discard the result if it ran long, rather than pre-empting it. A CPU-bound ONNX forward pass cannot be safely aborted mid-flight without unsafe thread termination, and unsafe is forbidden or denied in every crate. The real defence against cost is bounding the input: MAX_CANDIDATE_CHARS caps each candidate's tokenizer input, which is what made rerank cost roughly repo-independent. Before that fix, K=30 on kubernetes measured 2.5–9 s (40-line Go snippets blew past truncation and BatchLongest padding then inflated the whole batch); after, 700–950 ms.

11 · Performance envelope

Measured, not estimated. Small-repo numbers below are from indexing travsr's own tree with a release build on an Apple Silicon laptop; the kubernetes numbers are from the checked-in benchmark reports.

Retrieval quality: the honest numbers

Broken down by query category on kubernetes, the shape is unmistakable: literal queries 6/6 hit; conceptual queries 7/8 miss. Literal symbol lookup is solved. Conceptual recall is the open problem, and the abstention gate is currently tuned slightly too conservatively: it correctly refuses all nonsense, and also refuses conceptual queries it should answer.

Capacity limits & where it breaks

Configuration surface

Roughly 70 TRAVSR_* environment variables exist. They are an experimentation surface, not a production configuration API; ADR-003 says so explicitly for the PageRank group. The ones that matter for tuning:

Testing strategy

Alternatives considered and rejected

Known gaps

• Conceptual recall. 7 of 8 conceptual queries miss on kubernetes. The largest open quality problem.
• Abstention is over-tuned. Nonsense is refused 3/3, and so are conceptual queries that should be answered.
• Salad queries leak. Generic verbs (get, insert) still collide with real symbols; idf_coverage_min alone is not sufficient.
• SSE transport lacks per-session RBAC. Every other piece exists; only the wiring is missing.
• Objective-C has no fuzz target. The last of nine registry.rs TODOs still open.
• Synonym infrastructure is unused. Tables, MCP tools and CLI commands all ship, but the retrieval path barely exploits them, a ready-made lever for the recall problem above.

12 · Extension points

The four things most likely to be added, and what each one costs.

House rules, enforced by CI

• No unwrap() or expect() anywhere in crates/ except travsr-cli
• unsafe is forbidden or (in travsr-plugin-host, weaker on purpose) denied in every crate that declares the lint; the single override, Windows sandbox FFI, required an RFC
• No println! in libraries; tracing only, because stdout is the MCP channel
• cargo clippy --workspace --all-targets -- -D warnings must pass
• Constants traceable to an RFC or ADR may not be changed without updating that document

Everything on this page was read from the Rust source in crates/. Where a number is stated it was taken from the constant that defines it or from a checked-in benchmark report, not from a roadmap.