Skip to content

ARCHITECTURE.md

Latest commit

 

History

History
616 lines (511 loc) · 43.4 KB

ARCHITECTURE.md

File metadata and controls

616 lines (511 loc) · 43.4 KB
Raw

ripwire — architecture

This document is for a reader deciding whether to trust ripwire's output or extend its code. It describes the pipeline, the data model, the determinism contract, how ranking works, and — the part most tools leave out — the vocabulary the output uses to tell you what it does not know.

If you only want to use the tool, read README.md, docs/COMMANDS.md, or ./build/ripwire --help. If you are about to write C++ here, read CONTRIBUTING.md first.

1. The pipeline

ingest  →  graph  →  rank  →  serialize  →  cli / mcp

Five stages, in that order, with no back edges. Each stage's output is a plain data structure, so any stage can be tested in isolation and every verb is a different way of reading the same graph.

ingest — crawl and parse

A single-threaded directory crawl (collectSources, src/ingest_crawl.h) that produces a sorted file list, followed by parallel per-file tree-sitter extraction. The crawl is the cheap half and is deliberately not parallelized; the parse pool is where the threads are.

The stage is one translation unit with src/ingest.cpp as its spine — ingest() itself is now a ~120-line orchestrator that reads as the pipeline. Since the 2026-08-29 split, the stage's families live in src/ingest_*.h sections compiled into that one TU — the same section mechanism as src/main.cpp's verb families, guarded by RIPWIRE_INGEST_TU so no other file can include one: crawl + parse setup (ingest_crawl.h), the raw-facts model + incremental-cache codec (ingest_cache.h), structural metrics (ingest_metrics.h), cross-symbol relation capture (ingest_relations.h), the markdown section tier (ingest_docs.h), name resolution + capture policy (ingest_names.h), local-binding capture (ingest_binds.h), parse infrastructure + the fused side-capture passes (ingest_sidecap.h), and the --match/--lint query tail (ingest_astquery.h). The 2026-08-30 follow-on decomposed ingest()'s own body into four phase sections in call order: the lazy tags.scm prewarm (ingest_prewarm.h), the parallel parse pool (ingest_parsepool.h), the document post-pass (ingest_docpass.h), and the build-model tail — dedup, symbol assignment, span attribution, ordered emit (ingest_model.h).

Crawl order is deterministic, and that is load-bearing. The walk collects every candidate path first, sorts them lexicographically by byte, and only then assigns node IDs and parses. Node IDs are indices into that sorted list, so they are stable across runs of the same tree; if IDs followed directory order, node IDs, top-K cutoffs, and every diff-aware verb would churn between identical runs. The parse itself runs one tree-sitter parser per worker thread and merges per-thread result lists afterwards, which is safe precisely because the definitions and references are re-sorted before they are used — collection order never reaches the output.

.gitignore is consulted, after the denylist. Skipping starts from a fixed, committed denylist (kCrawlSkipDirs[] in src/ingest.h, shared with the CMake walk in darkflags.h so the two crawlers cannot disagree about what counts as source). In a git work tree the crawl then also honours git's own ignore verdict — one git ls-files --others --ignored --exclude-standard --directory fork per root, so the answer is git's and never a re-implemented matcher — and --no-ignore turns that half off. The denylist still prunes a build directory the repository happens not to ignore; what the repository ignores leaves the map and is disclosed as ignored_files= / ignored_dirs=, and the --grep unindexed scan reads none of it either (a gitignored file of an unindexed extension is in no class at all, the same treatment an --exclude'd one gets). What the denylist skips:

  • directories by NAME: .git, .claude, .hg, .svn, node_modules, vendor, third_party, .cache, build, dist, out, target, .venv, venv, __pycache__, .idea, .vscode, asan, build_prof, CMakeFiles, captures, and anything matching cmake-build-*;
  • any directory containing a CMakeCache.txt — a build-output tree, whatever it is called;
  • paths matching a --exclude=SUBSTR (repeatable), which prunes directories and drops files;
  • files over 4 MB (--max-file-size=N[K|M|G] overrides);
  • files whose first 4 KB contains a NUL byte — the binary sniff. There is no separate UTF-8 validity pass: the extractor slices names by byte offset and truncation backs off UTF-8 continuation bytes, so a codepoint is never split, but a file is not rejected for failing to decode;
  • JSON over 256 KB or nested deeper than 512 levels. The JSON lane indexes configuration keys; a large or degenerately nested .json file is data or a test corpus. The former explodes the symbol table; the latter drives tree-sitter's error recovery superlinear — 43 s measured on a 100 KB [[[[… file. Both cases were found live by benchmarking against real upstream repositories.

TOML has no lane-specific ceiling, and that is a measured decision rather than a missing sibling. Over 90 real public repositories (321 .toml files) the largest is 57 759 B — a quarter of the JSON ceiling and 1.4% of the generic 4 MB skip — so a TOML ceiling could not sit both above the observed maximum and below the generic one without being unreachable by construction. The substantive difference from JSON is pathology, not size: TOML is line-oriented, so a malformed line resynchronizes at the newline instead of nesting, and every adversarial probe stays linear ([×100 000 = 17.4 ms, 50 000 [[aot]] = 58.7 ms, a 2 MB unterminated string = 21.7 ms). .toml therefore rides the generic --max-file-size path only, whose drops are already disclosed through skipped_oversize=.

YAML gets JSON's hazard pair at its own calibration — and its nesting guard is memory-safety load-bearing, not just a perf guard. .yml wears JSON's problem (a machine-written data class behind a config extension), but JSON's 256 KB line would drop real hand-maintained config — NeMo's cicd-main.yml is 293 KB — so the YAML ceiling is 512 KB, counted into skipped_oversize= like its siblings. The nesting guard exists for a different reason than JSON's: tree-sitter-yaml's external scanner serialize() writes 4 bytes per open block indent level behind a loop guard that only proves 1 byte fits, so at ~254 levels it writes past the end of the 1024-byte serialization buffer — SIGABRT in a plain build, a silent corrupting write under NDEBUG. ripwire refuses such files before any parse via an O(n) indent prescan (kMaxYamlNestDepth, an over-approximation that can only over-count), and the vendored scanner additionally carries the one-line bounds fix under third_party/patches/yaml/, drift-gated so a grammar bump cannot silently revert it.

  • generated artifacts by filename: package-lock.json, npm-shrinkwrap.json, *.min.js, *_pb2.py, *.pb.go.

Ingest never throws — a bad file, a missing grammar or a corrupt cache degrades and prints a one-line DEGRADED_PATH_ALERT to stderr. The ordinary denylist prunes above are silent, deliberately: they are the normal state of every crawl and a note per skipped directory would be noise, not evidence. The size-ceiling drops sit between the two — silent on stderr, but counted into the header's skipped_oversize=N, so a corpus that shrank says so in the output rather than vanishing quietly.

Directory symlinks are not followed. The walk is a std::filesystem::recursive_directory_iterator opened with skip_permission_denied only — not follow_directory_symlink — so a symlinked directory is never descended into and a symlink cycle cannot arise. There is no inode tracking, because with symlink-following off there is nothing for it to do.

Extraction is query-driven, never hand-rolled. Each language contributes a vendored tree-sitter tags.scm query plus a small capture-name → NodeRole table. One query engine runs over every language, reading @definition.* captures as definitions and @reference.* captures as references, pulling the symbol name from the query's @name capture. A constexpr extension → { ts_language, tags.scm } table drives the whole thing. The alternative — a bespoke AST traversal per language — is forbidden here: it is five fragile walkers that break on every grammar bump instead of one query loop that survives them.

Concurrency: one tree-sitter parser per worker thread (parsers are not thread-safe), files dispatched as work items.

Supported languages and formats are listed in README.md.

Two of those carry a stated floor rather than a silence. PHP: dynamic dispatch — $fn(), $obj->$name(), call_user_func, __call magic, new $class — names its callee at run time, so those sites produce no edge; a use directive is captured for --uses/--deps but never narrows a call, because PSR-4 maps a namespace onto a directory through a composer.json block this tool does not read. Lua: inheritance is setmetatable( D, { __index = B } ), an ordinary runtime call over an ordinary table, so a Lua corpus correctly reports no inheritance edges at all. A bare require call is read the way package.path reads it: a string-literal argument that resolves to exactly one file adds a dependency edge. Dots become directory separators (require "a.b" finds a/b.lua), a package also resolves through its init.lua (require "pkg" finds pkg/init.lua), and the file is looked for from the requiring file's directory up to the crawl root, directly and under src/ and lua/. A qualified call (loader.require "x" is somebody's own function, not the loader), a dynamic or concatenated argument, an external module, or a name that more than one file answers adds no edge. Both floors are asserted from the outside by test/phpcheck.sh, test/luacheck.sh and test/luarequirecheck.sh so they stay decisions rather than drift.

Elixir .ex and .exs files use the vendored grammar and the shared tags-query engine. No Elixir, Mix, language server, compiler, or application execution is required. ingest_elixir.h interprets the grammar's ordinary call nodes as declarations and collects lexical facts; elixir_resolve.h uses those facts in the graph and CLI/MCP use-site queries. The existing binding and reference cache records carry the facts without adding fields to every language's symbols or references.

The extraction covers nested and explicitly rooted modules, structs/exceptions, protocols, single- and multi-target implementations (including an implicit enclosing-module target), public/private functions, macros, guards, delegates, operator definitions, guarded clauses, and literal ExUnit tests. Functions are identified by module, name and arity: MyApp.Work::run/1 selects one arity; the existing MyApp.Work::run selector selects all arities. Each written clause retains its source span. Default arguments add callable lookup arities that resolve to those source definitions, without fabricated bodies. defimpl P, for: [A, B] produces separate P.A and P.B scopes, each with its own calls.

Aliases (including groups and as:), require ... as:, nested-module aliases, __MODULE__ and Elixir. root qualification resolve in lexical source order. Imports support only, except, :functions and :macros; private functions are callable only locally. Local calls, static remote calls, zero-arity bare calls, pipes, named captures, executable defaults, and defdelegate to:/as: share the arity-aware resolver. Bound parameters and pattern variables are excluded as calls. A missing module, excluded import or wrong arity stays unresolved; an unrelated same-named function does not supply an edge. Multiple matching clauses remain candidate destinations.

Types (@type, @typep, @opaque) and callbacks (@callback, @macrocallback) are navigable declarations, named @type name/N and @callback name/N. Ordinary attributes are @name symbols; their expressions can carry calls and reads appear in --uses. Documentation, specs and other metadata do not become executable calls. Alias/import/require/use and behaviour declarations supply module dependencies resolved through declared module identities, regardless of umbrella/file layout. @behaviour and defimpl supply contract/implementation relationships for --uses and --lego.

Static limits: quoted AST and macro-generated definitions are not expanded. use records the dependency, but does not execute __using__; framework DSLs and generated Phoenix/Ecto functions therefore need an explicit source definition to appear. A call that only an injected import could answer has no lexical candidate: no edge is minted from a same-named function elsewhere, and the call is counted in the map header's unresolved= and every answer's graph_unresolved= when some definition spells the name (an undefined spelling has no header surface, as in every language). Runtime module receivers, apply, anonymous function dispatch, protocol dispatch by runtime argument type, and HEEx template execution are not inferred. Type expressions are indexed as declarations, not type-checked. Default-expression edges are narrowed by arity alone, and only where a bodyless head declares the defaults: a call that omits a defaulted argument reaches that head beside the clauses, a call that supplies every argument reaches the clauses alone (the fifth rule below), and a head that is reached carries every default expression it declares, whichever one the call omitted. A default written on a clause that has a body stays on that clause's symbol, so every call to it reaches the default expression, supplied argument or not. Metrics count written controls, clauses and boolean joins before macro expansion. These limits apply to CLI and MCP alike.

Five resolution rules, each reproduced against Elixir 1.20.3 / OTP 29 before the merge and each gated with its control in test/elixirnamearitycheck.sh (G)–(K) over test/elixirresolvefix: a later import M, except: [...] subtracts from the import M, only: [...] in force instead of replacing it, so a function the only-list never named stays un-imported and the refusal is counted (src/elixir_resolve.h); a dotted nested declaration such as defmodule Inner.Deep inside defmodule Outer aliases its first segment, Inner → Outer.Inner, from that point on, so a later Inner.Deep.target() names the nested module even beside a top-level Inner.Deep, and a call written before the declaration still names the top-level one (src/ingest_elixir.h); inside a multi-target defimpl, alias __MODULE__, as: Current binds each implementation's Current.f() to its OWN f, as __MODULE__.f() does, while a literal P.A.f() stays literal (src/ingest_elixir.h, src/ingest_sidecap.h); a named capture of an underscore-prefixed function (&_seed/0) is a call of that function — the underscore rule is for unused variables, and a bare _seed read still is one (src/ingest_elixir.h); and a call that omits a defaulted argument reaches the bodyless head that evaluates the default beside the clauses, so --path and --impact see the default expression's calls from that caller, while a call that supplies the argument reaches the clauses alone (src/elixir_resolve.h). One gap stays open: executable unquote(...) and bind_quoted: expressions under quote are omitted with the rest of the quoted-AST filter, so a helper called only from inside an unquote has no caller edge from its macro.

test/elixircheck.sh, test/eliximportcheck.sh and test/elixirsemanticcheck.sh cover extraction, metrics, exact target selection against decoys, lexical boundaries, contracts, CLI/MCP use-site parity, call-site mutation and cold/warm determinism; test/elixirnamearitycheck.sh covers what the name/N key must not cost the verbs around it (the counted use drop, pattern bindings on the right of =, --edit-check and --quality-delta across an arity change, --for by exact name) and the five resolution rules above. This extraction uses parser revision 95 (rich 96), mirrored in src/quality.h; record format 21 is unchanged. The quality key (pathQualifiedKey) folds the arity out of an Elixir name — run/1 and run/2 are one piece of source, as C++ overloads of f are — which is snapshot scheme 11. Dart extraction. tree-sitter-dart makes function_body a SIBLING of function_signature / method_signature, never a body field and never a child. The shared ancestor walk in ingest_sidecap.h therefore finds no body, the definition's span stops at the signature, and every call inside the body attributes to the nearest ENCLOSING symbol instead — measured on test/dartfix before the fix: square landed on the class Calculator rather than the method accumulate, and the three top-level edges were lost entirely (5 edges where 8 were expected). A Lang::Dart arm adopts the immediately-following function_body sibling and runs the span, the row extent and complexityOf through it — the same shape LB-E already uses for a test-macro block. An abstract member (void f();) has no such sibling, so it stays a declaration. Every other language is byte-identical across the change (verified against the pre-change binary on src/ and on the multi-language test/ fixture corpus). test/dartcheck.sh covers extraction, cascades, the constructor floor, call-site mutation, metrics and cold/warm determinism.

Kotlin extraction. tree-sitter-kotlin gives its declarations no named fields, so queries/kotlin/tags.scm captures positionally and two ingest arms follow. function_body, class_body and enum_class_body are positional CHILDREN, so the ObjC body fallback in ingest_sidecap.h covers Kotlin too — without it every Kotlin definition read as bodyless. And kotlinEnclosingScopeOf (ingest_names.h) walks class/object/companion owners by their positional type_identifier, so members carry scoped canonical ids. A bodyless Kotlin TYPE (data class User(val name: String), class Token, interface Marker) is still a definition — Kotlin has no forward declarations — so isDefinitionNotDeclaration (model.h) keeps the decl/def collapse from deleting it, and the collapse never lets a Kotlin body evict another language's declaration or the reverse. Kotlin and Java share one call graph through langCompatible, and keepOwnJvmLanguageCandidates (graph.h) lets a reference reach the other JVM language only when its own defines no candidate of that name, so adding .kt files never moves a Java edge (measured on square/retrofit: Response.body keeps its 279 callers). Stated floors: a navigation receiver (A.f()) does not narrow candidates, so a qualified call binds a same-named Kotlin definition over the Java class it names; that same own-language rule runs before the locality tiers, so a Kotlin call can lose a Java target in its own directory to Kotlin definitions elsewhere; an expect TYPE is a definition like any other, so a multiplatform expect/actual type pair is two candidates (measured on ktor against a build without the rule, it removes 138 Kotlin (caller, callee) pairs and adds 34; 48 of the removed and 4 of the added call a name ktor declares as an expect/actual class, interface or object); .kts is not a kLangTable row; and ev= is withheld (evCountedLang). A file whose string templates nest past kMaxKotlinStringNestDepth (128) is refused before the parse and rowed by --skipped, and the vendored scanner itself refuses a push past its 512-entry stack instead of aborting (third_party/patches/kotlin/001-stack-push-no-abort; 002 fixes a triple-quoted string that ends in an escaped $). test/kotlincheck.sh covers extraction, both bridge directions in flat and split layouts, the Java-edge invariant, the bodyless-type collapse, hostile nesting, metrics and determinism.

Elixir extraction landed at revision 78 (rich 79) — kParserVer in src/ingest_cache.h, mirrored by kIngestParserVerMirror in src/quality.h. The required qschemetrip source-change pin is refreshed for this extraction change; snapshot scheme 8 is unchanged.

The three config lanes are data, not code: they emit t="sec" symbols and zero call edges, and langCompatible keeps a config key from ever resolving a same-spelled code symbol. They differ in where the navigable unit sits. JSON cuts at document depth — top-level and second-level object keys. TOML cuts at the table header: [tool.ruff.lint] is one symbol under its full dotted name, and its keys are one level below it, whatever the header's dotted depth. Applying JSON's root-relative rule to TOML would capture 38.3% of keys in the 90-repo breadth corpus and miss every key under a 2-dotted table, which is the shape 1421 of 2561 observed headers actually have. YAML cuts at mapping depth ≤ 2 with sequence levels transparent: 25.3% of all real YAML keys sit directly inside a sequence element (the steps: / containers: / tasks: shape) and JSON's rule drops every one of them — sequence transparency lifts capture from 27.1% to 44.0% on the same corpus. Block and flow mappings count alike; anchors are part of the value they annotate; aliases and the <<: merge key are dropped, never expanded; each document of a multi-doc stream re-enters at depth 1; and a block scalar is one value token, so the 384 corpus block scalars containing key-like text can never mint symbols — the strongest argument for a real parser over a line regex. A dotted key in any of the three keeps its dots — a "lodash.merge" dependency, a tool.ruff.lint table and a YAML dotted.plain.key: are names, not scope paths.

graph — resolve references into edges

This is the hard part, and it is explicitly approximate. tree-sitter is syntax-only: no types, no name resolution, no cross-file knowledge. Linking a reference to the definitions it means is undecidable without a per-language semantic analyzer, and ripwire does not have one.

The base rule is one fixed precedence ladder, same-language only:

  1. a definition in the same file; else
  2. a definition in the same directory; else
  3. a unique same-language global definition; else
  4. drop the edge — no phantom node is ever invented.

If a name resolves to k > 1 candidates at the chosen tier, the resolver does not pick one: it emits k edges each weighted 1/k. PageRank tolerates the split and it removes an arbitrary tiebreak. That k > 1 event is what the output reports as amb="K" on a symbol, and what the header totals as ambiguous=N — the call-graph completeness gauge.

Above that base ladder sit precise tiers, added per language where the syntax makes resolution sound rather than heuristic: qualified calls of three or more segments and explicit-template calls in C++; scoped, turbofish and Self:: calls in Rust with a file-module guard; the ?. family in C#; qualified new in TypeScript, JavaScript and Java. Where a language's syntax does not support a sound rule, the tier is not shipped and the limit is stated — Go's qualified calls are rejected and fenced rather than guessed at. Where an external precise index exists, --scip=FILE overlays it and the affected edges are marked prov="scip".

False edges are expected and acceptable. The deliverable is an importance ranking, not a sound call graph, and the first XML comment in every run says so.

graph — the CSR

Nodes are symbols. Files are not nodes. A file is a serialization attribute. If files were nodes, their high degree would dominate the ranking.

PageRank propagates rank along incoming edges — a node is important if important nodes point at it — so the power iteration must multiply the transpose. The graph is therefore stored as an in-edge CSR:

  • rowOffsets[] — per-target start, size nodeCount + 1
  • colIndices[] — source node IDs
  • values[] — edge weight

This makes the sparse matrix-vector product a per-row gather with one sequential write per target: race-free, cache-friendly, parallel by row. A CSR keyed by source would force a scatter with random writes and write races — the opposite of what the layout rule wants.

The build is two passes: count in-degree per target and prefix-sum into rowOffsets, then scatter each (src → dst) edge into row = dst at col = src. A separate wOutDeg[] (weighted out-degree per source) carries the 1/outdeg normalization, plus a dangling mask for wOutDeg == 0.

Edge rules:

  • weight = mean per-reference confidence × the square root of the reference count, capped at 8 (src/graph.h, buildGraph). Each reference contributes a confidence — its resolution tier, deboosted for an over-common name (defined in ≥16 places) or a leading-underscore private one, and split evenly when it resolves ambiguously to k targets. Those contributions are accumulated per (src → dst) pair as a sum and a count, and the pair's weight is (confSum / nref) · √nref. The square root is the point: repeated calls should raise a weight sublinearly, so a hot loop strengthens an edge without letting call-site multiplicity alone dominate the ranking. The cap at 8 bounds the tail.
  • dedup is structural, not a merge pass — the accumulator is keyed by the (src, dst) pair, so a duplicate pair was never a second entry to collapse; it is the nref in the formula above. Duplicate columns would double-count in the product, and the CSR is built from that one-entry-per-pair list, sorted by (from, to);
  • self-loops are dropped — in the Google matrix they act as rank sinks that inflate the recursive node and steal mass.

rank — Personalized PageRank

Power iteration over the in-edge CSR, single-threaded. Every reduction (the dangling mass, the L1 residual) folds fixed contiguous blocks of kReductionBlockSize = 1024 in canonical index order, so the summation tree is a property of the source, never of thread count or timing. Constants live in a named configuration struct, not as literals in the loop: damping α = 0.85, L1 residual tolerance τ = 1e-6, maxIter = 100, diff-teleport concentration β = 0.7.

The teleport vector p (with Σp = 1) is where personalization lives — and only there. Uniform by default. With --map-diff, git-changed files are seeded: β / changedCount for symbols in changed files, (1 − β) / (nodeCount − changedCount) elsewhere, normalized.

Boosting the initial vector has zero effect at convergence — power iteration forgets its start — and post-multiplying final ranks by a constant is not personalization either. Both are forbidden; bias enters through p or it does not enter.

The per-iteration update:

D = Σ over dangling j of r[j]                              // deterministic block reduce
g[i] = Σ over in-edges (j→i) of w(j→i) · r[j] / wOutDeg[j] // gather
r_new[i] = α·g[i] + α·D·p[i] + (1−α)·p[i]

The α·D·p[i] term redistributes dangling mass through the teleport vector. Code graphs are mostly sinks — leaf functions, data structs — so without it, mass leaks every iteration, r stops being a probability vector, and the top-K biases toward the dense call core while architecturally central leaf interfaces collapse toward zero. This is the single thing naive PageRank implementations get wrong.

Convergence is a residual stop: iterate until ‖r_new − r‖₁ < τ, else stop at maxIter and use the last iterate. Teleport makes the operator strictly positive, hence primitive, so Perron–Frobenius guarantees a unique positive dominant eigenvector with λ₁ = 1 — the iteration is well-posed, not merely empirical.

The convergence disclosure contract

Those two exits produce documents that look identical and do not mean the same thing. The first is the fixed point the ranking claims to be. The second is a truncation of the computation — a rank vector caught mid-descent, carrying the same k= scores, the same ordering, the same confidence.

So the iteration reports itself, and every ranked document carries what it said:

attribute meaning
pr_iters="N" how many power iterations produced this document's ordering
pr_converged="0" that iteration stopped at maxIter with the residual still above τ

The absence rules are load-bearing and are the same absence rules the rest of the header uses. No pr_converged means it converged — there is no pr_converged="1", because the converged path is the overwhelming majority and must cost zero bytes. No pr_iters at all means the document was not ordered by a power iteration: a lexical --query/--for score, or a HITS hub/authority vector, both of which replace the PageRank vector outright. --rank-by=rrf does carry it, because PageRank is one of the three vectors it fuses. The map legend defines both names where the reader meets them; the prose explaining what to do about a truncated ranking is charged only to the map that actually took that exit. src/prconverge.h owns every spelling — XML, JSON, and the plain line the markdown report and the mermaid diagram emit instead, since neither has an attribute grammar to hang one on.

Why bother, when the truncating exit cannot fire at the shipped configuration? Because the reason it cannot fire is arithmetic about these constants, not a property of the method. The iteration is an α-contraction in L1 — the operator is column-stochastic and dangling mass is redistributed through the teleport prior — so residual_k ≤ 2·α^k, and 2·0.85^k < 1e-6 at k = 90, inside maxIter = 100 for any graph whatsoever. (E2 measured 28–52 iterations across four real corpora.) Lower τ, raise α toward 1, or hand the ranker a shape the contraction argument stops covering, and the attribute is what tells a reader before the ranking does.

The mechanism matters as much as the attribute. DEGRADED_PATH_ALERT still fires on the truncating exit and is still the only thing that names which site degraded — but it is #ifndef NDEBUG, so on every shipped Release binary it is not code at all. Before this contract, rankGraphTeleport discarded the kernel's return value, which meant a Release build emitted a ranking from an unfinished iteration with no alert, no attribute, and exit 0. A disclosure that lives only in an assertion is a disclosure that does not ship. Gate: test/prconvergecheck.sh, whose hard arm asserts the attribute appears in an NDEBUG build specifically.

The same CSR and the same product kernel serve the other graph lenses: HITS hubs and authorities (authorities are core APIs and base classes; hubs are entrypoints and orchestrators — a two-axis importance signal, not one scalar), co-citation and bibliographic-coupling similarity computed per query column rather than as a dense product, k-hop reach for blast radius, strongly-connected components for cycles, and community detection for the module views.

Retrieval ranking is a separate layer that consumes the graph. A confidence-gated query-shape router picks name-exact BM25 when the query names a symbol and subtoken+body BM25 otherwise, and prints which and why. Query-mention anchoring lifts a file, module, or Type.method named in the task text. A path-tier multiplier de-prioritizes fixture and generated-content paths. Every one of those is a measured change with a held-out number — see docs/EVALS.md.

serialize — minified XML

Nodes sort by (rank DESC, nodeId ASC). The node-ID tiebreak is required: near-equal scores would otherwise reorder between runs and make top-K and diff views churn. The index array is sorted with a radix sort against float keys without moving payloads; the top-K is taken from that.

XML escaping is a correctness requirement, not polish. C++ identifiers routinely contain <, >, &, and " — vector<int>, operator<, operator&&, std::pair<std::string,int> — and paths contain & and spaces. One escapeXml runs over every attribute value and text node, substituting & first so nothing double-escapes. A symbol named operator< in a path containing & must round-trip and parse cleanly; that is a required unit test, not an aspiration.

The document is streamed, never materialized. A stack-backed writer with a 64 KB buffer writes through to stdout on fill and on destruction: one write call per flush, no per-symbol syscall, no string accumulation of the final document.

The schema is terse by design — a legend comment once at the top, then <r> root, <f p> files, <s t n k> symbols, <c n> call edges. Token density is the point.

cli / mcp — two front doors, one renderer

The argument parser is hand-rolled and table-driven. A flagless run emits the core map; every flag is additive and gated by a Config field.

The MCP server exposes 31 verbs. All of them are a thin front door onto the same computation and the same renderer as a CLI sibling — one output shape, two surfaces. That is a deliberate constraint: a verb that rendered differently over MCP would be a second implementation to keep honest.

The three write verbs — replace_symbol_body, insert_before_symbol and insert_after_symbol (src/mcpedit.h) — also have CLI siblings (--replace-symbol-body, --insert-before-symbol, --insert-after-symbol, with --edit-payload). Both front doors share the same ambiguity refusal, staleness hash, symlink refusal, mode preservation and atomic-write transaction. CLI is the preferred zero-standing-schema path; MCP is the warm-index alternative.

2. Data model

Four types carry everything.

Type What it is
NodeId A 32-bit index into the symbol arrays. Not a pointer. IDs are assigned in sorted crawl order, so they are stable across runs of the same tree.
Symbol One definition: kind, name, canonical id, path, line span, language, plus the derived per-symbol metrics (complexity, fan-in, tested, churn). POD.
Reference One unresolved use site: name, kind (call / read / write / import / extends), position, and the file that contains it. Resolution turns references into edges.
IngestResult The output of the ingest stage — the symbol table, the reference list, per-file metadata — and the input to graph construction.

The graph itself is not an object graph. It is three parallel arrays (rowOffsets, colIndices, values) plus wOutDeg and the dangling mask: structure-of-arrays, 32-bit handles, no nodes, no pointers, no generic graph library. Everything else in the system is a different traversal of those arrays.

Caching is content-keyed. The parse cache is keyed by file content hash plus a parser version; an extraction change bumps the parser version and costs one cold re-parse. Warm output is asserted byte-identical to cold output by a gate — a cache that changes the answer is a bug, not a tradeoff.

Its blob holds ONE superset of records per tree and verb class, shared by every configuration run against that tree: the key deliberately ignores --exclude and --max-file-size, because keying on them instead was built, measured and reverted (docs/EVALS.md, "The auto-cache key ignores --exclude"). Sharing is made cheap by the blob's shape rather than by the key. A record offset table (pathHash → offset, length, contentHash, recordSum, ascending, binary-searched) lets a run deserialise only the records for the files it crawled, and a save carries over — byte for byte — the records for files it did not, so a narrower configuration can never truncate the blob a wider one built. The trailer's digest covers the header and the whole table and is verified on every open; each record's own digest lives in its table entry and is verified only when that record is read; and a trailer that does not exactly describe the file it sits in (fileSize == tableOffset + entryCount*32 + 24) is what catches a truncation that removed whole records. Any of those failing rejects the blob and self-heals to a full re-parse.

A second, much smaller cache sits beside it: the span-tier memo (ingest_astquery.h), which --grep's tier pass uses to skip re-parsing a hit file whose bytes have not changed. It is keyed by path + parser version, gated on the same (sizeBytes, mtimeNs, ctimeNs) stat triple and racy-mtime rule the parse cache's warm path uses, and it carries a measured size floor so it writes blobs only for files whose parse actually costs something. It obeys the same rules as everything else here: --no-cache turns it off, a blob that cannot be trusted is ignored rather than repaired, and test/grepfastcheck.sh pins cold output byte-identical to warm across the whole --grep option matrix.

3. The determinism contract

Output is a sorted top-K. A sort has no tolerance band, so the contract is byte-identity: the same tree produces the same bytes, on every run, regardless of thread count or scheduling.

Four rules hold it up:

  1. Fixed contiguous row-block partitioning — never dynamic work stealing over rows.
  2. Every global reduction (dangling mass, residual) sums fixed per-block partials in canonical block order. Never an atomic float add.
  3. The rank vector is double.
  4. The PageRank translation unit compiles without floating-point reassociation (a per-file flag), so add order is stable. The rest of the binary keeps the fast-math baseline.

Plus the ingest rule: sort candidate paths before assigning IDs.

Rule 1 means a compile-time constant, and a future maintainer will be tempted to make it a runtime one. Do not. The block size is kReductionBlockSize = 1024, a constexpr in src/pagerank.cpp. The obvious "improvement" is to derive it from the machine — hardware_concurrency(), a core count, a cache-size probe — so the partition matches the hardware it runs on. That change is invisible in review, passes every test on the machine that makes it, and silently destroys the contract this section is about.

Floating-point addition is not associative. A partition that varies by machine changes the summation tree, which changes the low bits of the dangling-mass and residual reductions, which changes ranks in the last digits, which reorders ties in a sort that has no tolerance band. Every symptom points away from the cause: each run is self-consistent, each run reproduces on its own host, the ranking always looks right, and only a byte-diff taken across two different machines shows anything at all — which is precisely the diff nobody runs, because the local determinism gate is green.

This is not hypothetical. A graph-database PageRank implementation surveyed in 2026-08 uses the same fixed-canonical-merge-order reduction strategy this one does — independent agreement that the strategy is right — and then partitions it by hardware_concurrency(), inheriting exactly this class. The strategy is only half the property; the partition has to be a property of the source.

The gate is ./build/ripwire DIR > a; ./build/ripwire DIR > b; diff -q a b, run three times. Anything that makes output depend on timing is a bug even when the ranking still looks right.

Tests follow from this. Float comparisons assert a tolerance band and the top-K order, never exact scores — fast-math and threaded reductions reorder sums. But a sort has no band, so sorted and serialized output uses the byte-identity gate instead.

4. The honesty contract

This is the part that distinguishes the output, and it is worth reading even if you skip everything else.

A zero is a measurement. Absent is not zero.

The call graph is extracted from source text by name. Dynamic dispatch, callbacks and function pointers, macro-generated call sites, and declarations that parse without a call expression contribute no edge. So a count of callers is a floor, never a total. Output says so, in the output, on the verbs where it is true:

  • counts_floor="1" appears on --callers, --callees, --uses, --impact, --edit-check and further surfaces. Read a 0 from those verbs as "none found", never as "none exists".
  • Counting units are named per verb, and --uses is the one that differs. --callers, --callees, --impact and --edit-check count distinct (caller, callee) pairs; --uses counts use SITES — every read, write, import and inheritance reference with its own file:line, so the same pair appearing twice is two rows. Two different numbers, two different names, deliberately: --uses is normally the larger, and comparing it against a caller count as though they measured the same thing is the mistake this row exists to prevent.
  • amb="K" on a symbol means K of its calls hit a name with multiple definitions and the resolver split the weight rather than choosing. The header's ambiguous=N totals it.
  • unresolved=N counts call names defined only in a language-incompatible file.
  • A refusal is not an answer of zero. A selector naming nothing indexed refuses with a did-you-mean computed from a real edit distance. A query whose names all resolve but that selects nothing reports count="0" — because that is a measurement.
  • Every truncation is disclosed. Headers carry total= (the true relevant count), shown= (what this run emitted), capped=, and truncated=; a document cut within itself carries its own marker; a bundle that could not fit its own floor says over_ceiling=1 rather than silently overshooting.
  • Token estimates are calibrated, never exact. No public tokenizer matches every model, so the estimate is a calibrated approximation and is labelled as one. The --pr-context estimate in particular is known to under-charge against a real tokenizer; treat it as a lower bound.
  • A negative result is published as a negative result. Two experimental ranking features are reachable only behind an environment variable, with --help entries removed, precisely because their own evaluations showed no confirmed lift.

The rule for anyone extending this code: do not add a surface that quietly rounds, guesses, or omits. If a number cannot be a total, name it a floor. If a lens dropped something, say what and why, in the output, where the caller reads it.

5. The two build flavours (a lesson worth inheriting)

CI builds and runs the full suite twice — once Release, once with no build type.

Release defines NDEBUG. Under NDEBUG, VERIFY lowers to __builtin_assume and DEGRADED_PATH_ALERT compiles away entirely. Both facts have teeth:

  • Release catches optimizer-only bugs. With __builtin_assume in play, a VERIFY( p != nullptr ) followed by a defensive if( p == nullptr ) return; licenses the optimizer to delete the defensive branch. Code that is correct at -O0 can be wrong at -O2, and only the Release build sees it.
  • The plain build catches degrade paths. A gate that asserts a degrade path asserts on DEGRADED_PATH_ALERT output. Compiled out, that gate cannot observe what it asserts — it passes while being blind. This happened here: for three development cycles, every degrade-path gate in CI was green for exactly that reason, and a real fix to one of them was invisible to CI until after it landed.

Neither flavour subsumes the other. If you add a degrade path, the plain run is what proves it; if you add an invariant, the Release run is what stresses it.

The same lesson generalizes, and it is the reason the gate discipline in CONTRIBUTING.md is written the way it is: a gate that cannot observe what it asserts is worse than no gate, because it reports confidence. Guard your probes — assert the thing you are about to search for actually exists, then assert the property.