call-graph-soundness

name	call-graph-soundness
description	Call graph soundness framework: 9 pattern families, 10 safety vetoes, soundness-vs-precision tradeoffs. Use before changing merge.rs, analyzer, or prune pipeline.
allowed-tools	Read, Write, Edit, Grep, Glob, Bash

Call Graph Soundness — Decision Framework

Purpose

Scalpel targets practical 100% reachability for security-grade pruning. Static-only reachability is theoretically incomplete (Rice). Scalpel closes the gap via multi-signal union. This skill encodes the taxonomy and decision rules so every merge/prune change stays sound.

Definitions:

• Sound: every true edge is present. Missing edges = bug.
• Complete: no spurious edges. Extra edges = precision loss, not safety bug.
• Soundy (Livshits 2015): sound except for explicitly-documented dynamic features.

Scalpel bias: over-approximate aggressively. False retain (kept but unused) is harmless. False prune (used but removed) is catastrophic.

The 9 Pattern Families

Every call site belongs to one family. Use this to classify unresolved calls:

Family	Patterns	Example	Resolution
A. Direct	Bare, imported, qualified, aliased, star, nested, re-export	foo(), m.foo()	Trivial-Easy
B. Method dispatch	Static, class, self, inherited, virtual, MRO, abstract, interface, trait, super, constructor, __new__, bound method	x.method()	Medium — CHA / type inference
C. First-class functions	Var, callback, returned, in container, attr, closure, partial, map/filter/reduce, lambda, method-ref	f=foo; f(), handlers[k]()	Hard — points-to analysis
D. Dynamic dispatch / reflection	getattr(obj,'n')(), eval, Method.invoke, send, __call__, Proxy, fn.call/apply/bind, subscript with dynamic key	getattr(o,n)()	Impossible statically; runtime only
E. Metaprogramming	Decorators (passthrough/wrap), monkey patch, metaclass, __init_subclass__, descriptors, property, staticmethod, singledispatch, functools.wraps, ABC.register, __slots__, dataclass/NamedTuple synthesis, mixins, Protocol	@retry def f	Varies; some resolvable with decorator modeling
F. Implicit dunders	Cls(x) → __init__, obj.x → __getattribute__, obj[k] → __getitem__, with x: → __enter__, a==b → __eq__, hash(obj) → __hash__, for x in y → __iter__, a+b → __add__, etc. (33 total)	with f: ...	Blanket rule: keep all dunders on reachable classes
G. Async/concurrency	await, create_task, .then, generators, goroutines, channel dispatch, thread pool, event emitter, pub/sub	await coro()	Medium; event/topic matching needed
H. Framework dispatch	Route decorators, signals, DI containers, plugins, CLI commands, fixtures, ORM hooks, GraphQL resolvers	@app.route('/x') def h()	Medium; per-framework model
I. Cross-boundary	FFI, subprocess, HTTP/gRPC, SQL, MQ, serverless, WASM, JNI	requests.get()	Runtime or schema-contract only

The 10 Safety Veto Layers

Every prune decision passes this gauntlet. ANY veto fires → retain.

1. MustKeep tags: error handlers, shutdown hooks, module-level side effects, magic names (__init__, __main__, main, setup, teardown)
2. Public API surface: __all__, non-underscore top-level names, __init__.py exports, stub files
3. String-reference scan: function name appears as string literal anywhere → keep (catches dynamic dispatch)
4. Framework entrypoint heuristics: @app.route, @receiver, @task, test_*, @fixture, @command
5. Class-tree preservation: reachable class → all dunders + all referenced methods + MRO inheritance
6. Runtime observation: any runtime event = ConfirmedUsed = absolute veto
7. SCC atomicity: circular dependency groups are atomic
8. Side-effect modules: module has import-time side effect → whole module kept if any symbol used
9. scalpelignore: explicit user-declared keep boundaries
10. Confidence tier: only Confidence::Unreachable is prunable. Others retained.

Pruning happens ONLY if all 10 layers clear.

Operating Rules

When editing merge.rs or scalpel-analyze:

1. Identify which pattern family you're touching.
2. For each unresolved case, explicitly log which family's resolution applies.
3. Default to over-approximation: if ambiguous, add edges to ALL candidates (not just one).
4. Never silently drop edges — classify as unresolved and track in EdgeResolutionReport.

When changing prune decision:

1. Walk the 10 safety layers in order.
2. Every retained function must record WHICH layer kept it (audit trail).
3. Every pruned function must show zero signals across all layers.

When adding new language support:

1. Map the language's dispatch patterns to families A-I.
2. For I-family (cross-boundary): document as soundy concession, not bug.
3. Framework models (H-family) per-framework.

Academic References

Use these for design decisions. Cite in commit messages for precision changes:

• PyCG (Salis et al. ICSE 2021) — Python static call graph, 99.2% precision / 69.9% recall
• JARVIS (Yan et al. 2023) — application-centered, +84% precision / +20% recall over PyCG
• CHA (Dean et al.) — Class Hierarchy Analysis for virtual dispatch
• RTA (Bacon & Sweeney 1996) — Rapid Type Analysis, filters CHA by instantiated types
• Andersen 1994 — inclusion-based points-to (subset constraints)
• Steensgaard 1996 — unification-based points-to (equality, near-linear)
• k-CFA (Shivers 1991) — context-sensitive flow analysis
• Soundiness Manifesto (Livshits et al. CACM 2015) — explicitly document concessions

Current Project State (update when things change)

• Edge resolution rate across 7 Python projects: 25-35%
• Top unresolved pattern: C-family variable.method() (~40% of unresolved)
• Safety fallback: value-reference scan + 10-layer vetoes → 0 scalpel RuntimeErrors on 6 projects
• Next: probe-to-genome name normalization (Increment 1.5)

Checklist for Merge/Prune PRs

Before merging:

• Pattern family identified for the change
• Over-approximation preserved (no silent edge drops)
• Safety layer vetoes unchanged OR explicitly strengthened
• Multi-project prune safety test still 0 scalpel errors
• If weakening a layer: cite runtime/external evidence that justifies it
• Audit trail documents which signals fire per decision

Anti-Patterns

• Silently rejecting unresolved edges because they're ambiguous (miss edges = safety bug)
• Aggressive heuristics (e.g., "prune anything without explicit import") without layered vetoes
• Pattern families left unclassified in the report — then the rate-of-fix is unmeasurable
• Calling soundness "overkill" — security pruning requires it