brick/docs/research/cpp-rust-resolution.md

C/C++ and Rust call resolution for agents

Problem

A dead-code audit of a real C++ repository found that 93% of symbols had no resolved incoming edge. Brick could not tell "unresolved" from "unused", so reporting those symbols as dead would have produced the false findings the audit was looking for. The audit on 2026-09-22 found these root causes:

Cause	Where
C++ bare calls resolved only within one file; #include never authorized a cross-file call	scan.rs owner-chain lookup
Header prototypes not recorded; out-of-line A::f named "A::f" with a file owner	source.rs declaration
T& f() named "& f(...)" (fieldless reference_declarator)	source.rs
Every member call (obj.f(), this->f(), self.m()) External	scan.rs
Calls inside Rust macros (assert!, format!, vec!) dropped (token_tree skipped)	source.rs
std::lock_guard<M> g(f()); hides f() (most vexing parse)	tree-sitter-cpp
static_cast<T>(x) recorded as a call	source.rs
No unresolved reason; per-caller External identity; no coverage metric	model
Linear node/edge scans and per-node ancestor walks	scan.rs, source.rs

Literature (paperbridge, arXiv/OpenAlex, 2026-09-22)

• Murphy, Notkin et al., "An empirical study of static call graph extractors", TOSEM 1998, doi:10.1145/279310.279314. Extractors disagree widely, so each edge keeps its backend and the resolution method that produced it.
• Grove, DeFouw, Dean, Chambers, "Call graph construction in object-oriented languages", OOPSLA 1997, doi:10.1145/263698.264352; Grove and Chambers, TOPLAS 2001, doi:10.1145/506315.506316. Receiver type sets bound dispatch. Brick uses declared static types only, and treats virtual and trait targets as unknown rather than enumerating overrides.
• Srivastava, "Unreachable procedures in object-oriented programming", LOPLAS 1992, doi:10.1145/161494.161517. Deadness is relative to roots and dispatch assumptions. brick_callers therefore names its reasons and its evidence basis instead of issuing a verdict.
• Creager and van Antwerpen, "Stack graphs: Name resolution at scale", arXiv:2211.01224. This is file-local, build-free scope resolution. The C++ include-closure lookup and the Rust impl index follow the same idea at much lower fidelity.
• Cai and Zhang, "A Cocktail Approach to Practical Call Graph Construction", OOPSLA 2023, doi:10.1145/3622833, and Li, He et al., Rupta, CC 2024, doi:10.1145/3640537.3641574. Function pointers (C) and trait/dyn dispatch (Rust) need pointer or MIR analysis. That work belongs to Fold's compiler lane, not to syntax.
• LocAgent (ACL 2025, doi:10.18653/v1/2025.acl-long.426) and CodexGraph (NAACL 2025). Agents navigate code graphs effectively, which makes edge provenance and uncertainty part of the agent contract.

Experiment contract

{
  "hypothesis": "Include-visible C++ lookup, declared-receiver typing, Rust impl indexing and macro re-parsing raise labeled call recall without clean-negative regressions, and reasons make zero-caller symbols distinguishable from unresolved ones",
  "owner": "source extractor and heuristic resolver; caller-status query",
  "fixtures": ["tests/fixtures/cpp_xtu", "tests/fixtures/rust_methods", "tests/fixtures/languages", "tests/fixtures/rust_imports"],
  "expected": {
    "increases": ["labeled C++/Rust relationship precision and recall", "resolved call-site share on unlabeled repositories"],
    "preserves": ["schema 4 reader contract", "Heuristic lane and 0.65 confidence", "existing labeled corpora", "stable IDs of unrelated and out-of-line C++ declarations"]
  },
  "decision": "promote in the default extractor"
}

Results

The labeled corpora were authored before the implementation. Each has 3 repeats with stable full-model JSON, and the quality gate runs both.

Corpus	Baseline (050b1b1) relationships	Candidate
cpp_xtu (headers, out-of-line methods, namespaces, overloads, internal linkage, macros, receivers, bases, a duplicate-program clean negative, std::string / untyped receiver negatives)	12/17, 6 unexpected (first label version)	24/24 exact
rust_methods (Self::, fallible constructors, Arc fields, macro bodies, dyn trait, competing trait impls, std::fs::File shadowing a repository File, generics)	13/23, precision 0.65	23/23 exact
source_languages, rust_imports	exact	exact

Coverage on unlabeled repositories. These are coverage observations, not precision claims:

Repository	Functions with no resolved caller	Resolved call sites	Scan time
Fold src/+include/ (C++, 2341 functions)	66.3% → 39.0%	9.5% → 23.1%	8.8 s → 2.3 s
Paperbridge (Rust, 1175 functions)	66.7% → 50.6%	985 → 1606 sites	2.5 s → 0.8 s
Brick (Rust, 329 functions)	45.3% → 28.9%	575 → 723 sites	1.2 s → 0.4 s

Precision spot checks drew random samples of receiver-typed edges: 12 from Fold and 14 from Paperbridge. Every sampled edge was plausible, and the three Fold receiver declarations that were checked by hand were correct.

brick_uncalled on Fold (open world) lists 5 unreferenced functions, and grep confirms that all 5 have no uses. It first listed 8; the 3 false candidates were vexing-parse calls, which extraction now recovers.

On Paperbridge (open world) it lists 0 unreferenced functions. In closed world it lists 8, all of which are used only by the excluded tests/ directories. The candidates that exposed framework-attribute (#[tool], #[test]) and deserialize_with string uses are now reported as unknown with those reasons.

YAMS validation (C++, 15,607 functions including tests)

	Baseline (050b1b1)	Candidate
Scan time	575 s	23 s
Functions with no resolved caller	84.5%	49.7%
Resolved call sites	2.5%	13.9%
Files reported as incomplete syntax	616	316

The YAMS run exposed six defects, each fixed with a regression test:

1. tree-sitter-cpp 0.23.4 parses a = {} default argument as a compound literal with a zero-width MISSING type. The syntax is otherwise intact, so it is now benign. Before, it dropped every such prototype and flagged half the files. Of the 910 production files, 70 still have real errors, mostly #if blocks that split braces.
2. using namespace N; and using N::f; were ignored. They now extend C++ lookup through the include closure, which resolved about 4,500 more sites.
3. The receiver type of a template parameter (template <class Ptr> f(Ptr p) { p->g(); }) was classified as a foreign type. That is unsound, because it hid a real caller. Such receivers are now receiver-type-unknown. Type aliases and typedefs resolve to their target, through a smart pointer where applicable.
4. Functions reachable only through a macro body (#define dlopen dlopen_impl) now count as referenced by name. So do identifiers inside syntax-error regions.
5. A file with real syntax errors can misplace scope and linkage: the error recovery for an #if that splits a brace moved a public function into an anonymous namespace. Its functions now carry source.parse-incomplete, and brick_callers reports that reason.
6. These are now implicit-invocation: coroutine protocol members (await_ready, final_suspend, and the rest), range-for begin/end, ADL swap, and constructors of explicit specializations (Expected<void>). Out-of-line members of classes that are not in the repository (tinyfsm::Fsm<..>::set_initial_state) are outside-class-member.

brick_uncalled results after the fixes:

• Open world (default): 2 candidates, and both are unused. One is neutralText. The other is a Windows-only static describeProcess: every call is made inside a DaemonCommand method, where the static member of the same name wins under C++ class-scope lookup.
• Closed world: 357 candidates in src/ and include/.
  • The first random sample of 25 was 20 correct; its five errors led to fixes 3 and 6 above.
  • A second, independent sample of 30 was 29 correct, and the error was the specialization constructor, now fixed.
  • "Correct" means the function has no mentions outside its own declarations, comments, log strings, or unrelated same-named functions.

Model changes (schema 4, optional fields)

• Function node attributes:
  • source.parse-incomplete;
  • source.qualifier (out-of-line A::f, whose node name is now f; the ID still hashes A::f);
  • source.qualified-name (C++);
  • source.linkage: internal;
  • source.virtual;
  • source.implements (Rust trait impl);
  • source.attributes (Rust);
  • source.referenced-by-name.
• Call edge attributes:
  • source.unresolved-reason, with values not-visible, declared-only, ambiguous, macro, receiver-type-unknown, receiver-type-external, member-not-found, qualifier-unknown, member-receiver, not-in-repository and runtime-parameter-binding;
  • source.resolution (declared-receiver-type, self-receiver, impl-type, using-directive);
  • source.extraction (macro-reparse, vexing-parse).
• metrics.resolution: per language, the counts of call sites, resolved sites, unresolved sites by reason, functions, and functions without resolved callers.

Intentional identity changes

• C++ and Rust External targets now include the unresolved reason in their identity, so two differently failing sites never merge and lose a reason.
• Reference-returning C++ functions get correct names and therefore new IDs.
• The labeled-corpus runner renders source.qualifier in symbol identities.

Limits

• All inferred relationships remain Heuristic.
• C++: no preprocessing, overload resolution, template instantiation, ADL, auto inference beyond new T/make_unique<T>, or compile_commands.json include paths.
• Rust: types are matched by leaf name, and there is no Cargo workspace, mod tree, or re-export resolution.
• Dispatch: virtual and trait dispatch reach only the statically declared method; overrides and trait implementations are reported as unknown, never as dead.
• The compiler lane (Fold ProjectCallGraph, fold-rust MIR callees) and candidate edges are the next stages (see docs/ROADMAP.md).