Skip to content

ADR-031: Source and Implementation Graph Augmentation

Date: 2026-06-09 Status: Accepted — implemented (phases 1–7). The graph schema + build-evidence graph + L4 public-reachability/source↔binary graph + Clang call (D4) and -MM include (D3) graphs + Kythe/CodeQL pre-captured backends (D5) are all collected via collect; graph compare and the verdict pipeline emit all six D6 findings; graph explain localizes a finding through the graph (D8). (The command names below were renamed from the original compare-graph/explain-finding to the graph compare/ graph explain subcommand group — see D8.) The compact single-file source_graph_summary.json plus external_graph_refs is the storage model (D7) — chunked SQLite/Parquet remains an optional future scaling optimization, not a capability gap. Extended by ADR-041 (2026-07-12): ADR-041 is the roadmap (with P0 slices already shipped) that populates the four edge kinds this ADR's schema reserved but left empty (DECL_REFERENCES_DECL/DECL_HAS_TYPE/ TYPE_HAS_FIELD_TYPE/TYPE_INHERITS), adds graph explain proof paths per finding, and correlates an L4 body/type-hash change with a new L5 edge in one finding — see 041-compiler-facts-semantic-impact-graph.md. Decision maker: Nikolay Petrov

Context

The build (ADR-029) and source (ADR-030) layers answer "what changed?" and "under which build context?". A graph layer can answer a different set of questions:

  • Which public ABI finding is reachable from which public header, target, source file, generated file, or build option?
  • Did a source change affect a public type only transitively?
  • Did a build option change affect the compile units that produced the changed binary symbol?
  • Which source declarations map to which exported binary symbols and debug types?
  • What changed between old and new call/type/include/build graphs?
  • Which findings are likely implementation-only and which reach the API surface?

However, full whole-program graph analysis is heavy, and it is approximate — especially for virtual dispatch, function pointers, templates, generated code, link-time optimization, and dynamic loading. The graph layer must therefore be optional and explanatory-first (L5 in the ADR-028 model).

Decision

D1. Add optional L5 graph evidence at two levels

Level Artifact Purpose Default
summary graph/source_graph_summary.json Compact graph facts relevant to ABI/API decisions Optional, CI-friendly
full external graph store or chunked graph pack Deep graph-to-graph queries and exploration Nightly/deep mode only

The primary abicheck snapshot stores only a reference and coverage summary, never the full graph (ADR-028 D8).

D2. abicheck-owned graph schema for ABI/API-relevant facts

Node kinds:

file, header, source, compile_unit, target, link_unit,
binary_symbol, debug_type, source_decl, record_type, enum_type,
typedef, macro, build_option, toolchain, generated_file,
external_dependency

Edge kinds:

TARGET_HAS_SOURCE, TARGET_HAS_PUBLIC_HEADER, TARGET_DEPENDS_ON,
COMPILE_UNIT_BUILDS_SOURCE, COMPILE_UNIT_USES_OPTION,
COMPILE_UNIT_INCLUDES_FILE, FILE_GENERATED_FROM,
SOURCE_DECLARES, SOURCE_DEFINES, DECL_HAS_TYPE,
DECL_CALLS_DECL, DECL_REFERENCES_DECL,
TYPE_HAS_FIELD_TYPE, TYPE_INHERITS,
BINARY_EXPORTS_SYMBOL, SOURCE_DECL_MAPS_TO_SYMBOL,
SOURCE_TYPE_MAPS_TO_DEBUG_TYPE,
BUILD_OPTION_AFFECTS_DECL, BUILD_OPTION_AFFECTS_SYMBOL,
FINDING_LOCALIZES_TO_DECL, FINDING_CAUSED_BY_OPTION

Every edge carries provenance and confidence.

D3. Start with the graph summary, not a full call graph

The MVP graph summary collects:

  • target → source/header/output edges from BuildEvidence (ADR-029);
  • compile unit → include edges from depfiles, compiler -M* output, or source parsing;
  • public header → declaration edges from L2/L4;
  • declaration → type reference edges from L2/L4;
  • exported symbol → source declaration mappings from L0/L1/L2/L4;
  • generated-file edges from build-system metadata;
  • finding → declaration/source/build-option localization.

This already enables graph-to-graph comparison at the useful ABI/API level without whole-program data-flow.

D4. Call graph as optional, approximate evidence

Call graph extraction may use:

  • Clang LibTooling AST traversal for direct calls;
  • GCC -fcallgraph-info when builds opt into compiler-emitted VCG callgraphs (ADR-029 D8);
  • CodeQL call-graph queries for resolved/virtual/points-to-based calls;
  • Kythe call/reference edges when using Kythe extraction;
  • LLVM IR/callgraph passes only in an explicitly instrumented build mode.

Call graph edges must be labeled:

{
  "edge": "DECL_CALLS_DECL",
  "call_kind": "direct|virtual|function_pointer|template_instantiation|unknown",
  "resolution": "exact|points_to|overapprox|underapprox|unknown",
  "confidence": "high|reduced|unknown"
}

Call graph differences can explain implementation impact, but they never decide ABI breakage alone.

D5. External graph backends are adapters, not core dependencies

Backend Integration model Strength Limitation
Clang LibTooling abicheck-owned extractor using the compile DB Fine-grained AST facts, direct edges, good CI control C++ frontend compatibility and maintenance burden
Kythe external extractor + .kzip + GraphStore Mature cross-reference graph and generated-code support Large artifacts; extraction/indexing overhead
CodeQL external DB + queries Strong query model, call/data-flow libraries Heavy DB creation; licensing/deployment considerations for some users
GCC callgraph compiler option output Direct compiler-emitted implementation signal Requires an opt-in compile flag or pre-existing files
LLVM pass compiler plugin / instrumented build Rich IR facts Incompatible with the no-rebuild MVP

All backends go through the ADR-032 extractor contract; the normalized graph summary remains abicheck-owned.

D6. Graph diffs for explanation, scoping, and triage

Graph-to-graph comparison produces secondary findings. Implemented ChangeKind entries (partitioned per ADR-011; see the current, larger L5 finding table — including entries added after this ADR shipped, e.g. by ADR-035 D4/ADR-041 — in docs/learn/build-source-data.md §"Source graph findings (L5)"):

Kind Partition Meaning
public_reachability_changed RISK_KINDS Entity entered/left the public-API reachability closure
source_to_binary_mapping_changed RISK_KINDS Declaration↔symbol mapping changed without a clear ABI diff
build_option_reaches_public_symbol RISK_KINDS A changed option affected a compile unit producing a public symbol
generated_header_reaches_public_api RISK_KINDS A generated file participates in the public declaration closure
call_graph_public_entry_reachability_changed COMPATIBLE_KINDS (quality) Implementation reachable from an exported entry point changed
include_graph_public_header_drift RISK_KINDS Public header include closure changed

These findings explain and prioritize. They must not suppress ABI break findings without explicit ADR-024-style demotion and disclosure in the surface ledger.

D7. Store compact graph summaries by default

source_graph_summary.json:

{
  "schema_version": 1,
  "graph_id": "sha256:...",
  "coverage": {
    "targets": 12,
    "compile_units": 142,
    "source_decls": 4110,
    "binary_symbol_mappings": 230,
    "include_edges": 19300,
    "call_edges": {"collected": false}
  },
  "nodes": [],
  "edges": [],
  "indexes": {
    "by_binary_symbol": {},
    "by_source_decl": {},
    "by_target": {},
    "by_file": {}
  },
  "external_graph_refs": []
}

For large projects, use chunked JSONL or SQLite/Parquet inside the evidence pack. A report must never require loading a huge full graph just to compare core ABI snapshots.

D8. Graph query commands

# Collect a compact graph summary.
abicheck collect --source-graph summary --build-dir build --output evidence/

# Fold in a pre-captured external backend (non-executing ingest).
abicheck collect --source-graph summary --kythe-entries kythe-entries.json --output evidence/
abicheck collect --source-graph summary --codeql-results codeql-results.json --output evidence/

# Explain one finding through graph evidence.
abicheck graph explain report.json --finding-id F123 --sources evidence/

# Compare graph summaries directly.
abicheck graph compare old.evidence/graph/source_graph_summary.json \
                       new.evidence/graph/source_graph_summary.json

(As implemented, --source-graph itself only takes off|summary; an external Kythe/CodeQL backend is folded in via the separate --kythe-entries/--codeql-results pre-captured-file flags, both non-executing per ADR-032 D5/ADR-038 D0 — not --source-graph kythe|codeql or a --kythe-kzip/--codeql-db flag. The query/explain commands are the graph compare/graph explain subcommands, not the original compare-graph/explain-finding top-level names.)

D9. Confidence and approximation must be visible

Graph-derived output must say whether it came from:

  • direct AST facts;
  • generated compile/build metadata;
  • debug-source provenance;
  • points-to approximation;
  • virtual dispatch approximation;
  • an external graph backend;
  • stale or partial extraction.

Reports must avoid language like "all callers" unless extractor coverage proves it. Prefer "known static callers" or "observed graph edges".

Consequences

Positive

  • Enables true graph-to-graph comparison without making full source analysis mandatory.
  • Improves false-positive triage by showing whether a change reaches public API roots.
  • Makes invisible build/generated/transitive causes explainable to reviewers.
  • Provides a path to advanced source/binary correlation and impact analysis (feeding ADR-027 surface intelligence).

Negative / risks

  • Full graphs can be huge.
  • Call graphs are approximate for real C++.
  • External graph tools add install and runtime burden.
  • Users may misinterpret graph absence as safety unless reports show coverage clearly (D9).

Implementation plan

Phase Scope Output Status
1 Define node/edge schema and graph summary storage Empty/metadata graph summaries Done — buildsource/source_graph.py (SourceGraphSummary/GraphNode/GraphEdge, content-addressed graph_id, coverage block, indexes); stored as graph/source_graph_summary.json and round-tripped by BuildSourcePack (renamed from EvidencePack, ADR-028 amendment)
2 Build graph edges from ADR-029 BuildEvidence target/source/header/output graph Done — build_source_graph(); collect --source-graph summary collects it and flips the L5 coverage row to PRESENT
3 Header/type/declaration graph from L2/L4 public reachability graph Done — build_source_graph(build, source_abi=…) folds an ADR-030 SourceAbiSurface into source_decl/record_type/enum_type/typedef/macro nodes linked to their declaring public header via SOURCE_DECLARES
4 Source-to-binary mapping graph symbol/declaration/debug mapping explanations Done — SOURCE_DECL_MAPS_TO_SYMBOL, SOURCE_TYPE_MAPS_TO_DEBUG_TYPE, and BINARY_EXPORTS_SYMBOL edges from the surface mappings, completing the target → header → decl → exported-symbol closure
5 Graph diff and explain-finding graph-to-graph compare, finding localization Done — diff_source_graph() (structural delta) + diff_source_graph_findings() emit all six D6 ChangeKinds, surfaced by graph compare and folded into the compare --build-info verdict pipeline; localize_symbol() + the graph explain command localize a finding through the graph (D8)
6 Optional Clang direct-call extractor direct call graph summary Done — buildsource/call_graph.py: parse_clang_ast_calls() (pure AST-JSON parser, unit-tested) + ClangCallGraphExtractor (live clang -ast-dump=json, integration-only) emit DECL_CALLS_DECL edges labelled with call_kind/resolution (D4); folded automatically whenever --source-abi and --source-graph summary are both given (originally an explicit collect --call-graph flag, removed once the ADR-041 header-only-graph addendum's own automatic behavior made the flag redundant with dump --sources's equivalent) and the call_graph_public_entry_reachability_changed finding consumes them
7 Kythe/CodeQL adapters external graph backend summaries Done — buildsource/graph_backends.py: ingest_kythe_entries() (Kythe entries → DECL_CALLS_DECL/DECL_REFERENCES_DECL) and ingest_codeql_call_results() (CodeQL BQRS→JSON → DECL_CALLS_DECL), wired via collect --kythe-entries/--codeql-results; non-executing (pre-captured exports), with the store noted in external_graph_refs. Compile-unit include edges (D3) land via buildsource/include_graph.py (clang -MM)

Validation

  • Golden public-reachability fixtures.
  • Generated-header reachability fixture.
  • Public symbol mapping fixture with overloads/templates.
  • Callgraph fixture clearly separating direct, virtual, and function-pointer calls.
  • Large-project memory tests with chunked graph summary loading.

References