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

```json
{
  "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`).