flux_middle/
call_graph.rs

1//! Data types for the no-panic call graph.
2//!
3//! The graph is *constructed* by the `flux-opt` crate (the `call_graph` query provider) but the
4//! types live here so they can be cached in `flux-middle` and consumed by both `flux-opt`
5//! (no-panic inference) and `flux-refineck` (the checker, which recovers the resolved callee at a
6//! call site by location).
7
8use std::fmt;
9
10use rustc_data_structures::{fx::FxIndexMap, unord::UnordMap};
11use rustc_hir::{def::DefKind, def_id::DefId};
12use rustc_macros::{TyDecodable, TyEncodable};
13use rustc_middle::{
14    mir::Location,
15    ty::{GenericArgs, Instance, InstanceKind, TyCtxt, TypeVisitableExt},
16};
17
18/// Identity of a call-graph node. Distinguishes an item *as defined in source* from a
19/// *monomorphization* synthesized while building the graph.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
21pub enum NodeKey<'tcx> {
22    /// An item as written in source (generic or not), identified by its `DefId`.
23    Item(DefId),
24    /// A generic item monomorphized at concrete type/const args while building the
25    /// call graph (e.g. `Vec::<i32>::push`). We must guarantee that the instance is fully
26    /// monomorphic, i.e., the `Instance`'s args are all concrete types/consts.
27    ///
28    /// Use `NodeKey::from_instance` to classify an `Instance` into a `NodeKey`.
29    Mono(Instance<'tcx>),
30}
31
32impl<'tcx> NodeKey<'tcx> {
33    /// Classifies an `Instance` into a `NodeKey`.
34    pub fn from_instance(instance: Instance<'tcx>) -> Self {
35        if let InstanceKind::Item(def_id) = instance.def
36            // - If `has_param()` is true then the instance is not fully monomorphic
37            // - If args is empty then is a non-generic item
38            && (instance.args.has_param() || instance.args.is_empty())
39        {
40            NodeKey::Item(def_id)
41        } else {
42            NodeKey::Mono(instance)
43        }
44    }
45
46    pub fn def_id(self) -> DefId {
47        match self {
48            NodeKey::Item(def_id) => def_id,
49            NodeKey::Mono(instance) => instance.def_id(),
50        }
51    }
52
53    /// The `Instance` this key denotes. For an [`Item`](NodeKey::Item) this rebuilds the identity
54    /// instance; for a [`Mono`](NodeKey::Mono) it is the stored instance.
55    pub fn instance(self, tcx: TyCtxt<'tcx>) -> Instance<'tcx> {
56        match self {
57            NodeKey::Item(def_id) => {
58                Instance::new_raw(def_id, GenericArgs::identity_for_item(tcx, def_id))
59            }
60            NodeKey::Mono(instance) => instance,
61        }
62    }
63
64    /// Whether this key denotes a locally-defined function item — the source item itself or a
65    /// monomorphization of it. Excludes foreign defs and non-`Item` instances (drop glue, fn-ptr
66    /// shims, etc.), which never carry a meaningful spec. Used to decide which specs a crate owns
67    /// and serializes into its own metadata.
68    #[allow(
69        clippy::disallowed_methods,
70        reason = "is responsibility of who builds the graph to filter out dummy extern spec items."
71    )]
72    pub fn is_local_item(self) -> bool {
73        self.def_id().is_local()
74            && match self {
75                NodeKey::Item(_) => true,
76                NodeKey::Mono(instance) => matches!(instance.def, InstanceKind::Item(_)),
77            }
78    }
79}
80
81/// A single call site observed in a function's MIR body.
82#[derive(Debug, Clone)]
83pub struct CallSite<'tcx> {
84    pub location: Location,
85    pub kind: CallSiteKind<'tcx>,
86}
87
88#[derive(Debug, Clone)]
89pub enum CallSiteKind<'tcx> {
90    /// `Call` terminator that resolved to a concrete callee node (a source item or a
91    /// monomorphization).
92    Resolved { callee: NodeKey<'tcx> },
93    /// Synthetic edge from an `Assert` terminator with a reachable unwind path —
94    /// represents the implicit call to `core::panicking::panic`.
95    SynthesizedPanic,
96    /// `Call` terminator on a `FnDef` where `Instance::try_resolve` failed.
97    Unresolved { def_id: DefId },
98    /// `Call` terminator on a non-`FnDef` type (function pointer, closure).
99    DynamicDispatch,
100}
101
102/// A node in the call graph. The node's provenance (source item vs monomorphization) is carried by
103/// its [`NodeKey`]; the node itself only records, when it has an analyzable body, the call sites
104/// observed in it.
105#[derive(Debug, Clone)]
106pub enum Node<'tcx> {
107    /// MIR was available and walked. `call_sites` are the Call/Assert terminators observed.
108    Analyzed { call_sites: Vec<CallSite<'tcx>> },
109    /// External crate function — panic spec looked up from crate metadata.
110    ExternalCrate,
111    /// Function with no analyzable body (no Rust body by design, MIR unavailable,
112    /// or a non-`Item` instance such as a shim or virtual dispatch stub).
113    /// Conservatively treated as `MightPanic`.
114    Leaf(DefKind),
115}
116
117impl<'tcx> Node<'tcx> {
118    /// Call sites observed in this node's body. Empty for non-`Analyzed` nodes.
119    fn call_sites(&self) -> &[CallSite<'tcx>] {
120        match self {
121            Node::Analyzed { call_sites } => call_sites,
122            Node::ExternalCrate | Node::Leaf(_) => &[],
123        }
124    }
125
126    /// The callee nodes of this node's resolved call sites (skipping unresolved/dynamic ones).
127    pub fn resolved_callees(&self) -> impl Iterator<Item = NodeKey<'tcx>> {
128        self.call_sites().iter().filter_map(|site| {
129            match site.kind {
130                CallSiteKind::Resolved { callee } => Some(callee),
131                _ => None,
132            }
133        })
134    }
135}
136
137pub struct CallGraph<'tcx> {
138    pub nodes: FxIndexMap<NodeKey<'tcx>, Node<'tcx>>,
139    pub callers: UnordMap<NodeKey<'tcx>, Vec<NodeKey<'tcx>>>,
140}
141
142impl<'tcx> CallGraph<'tcx> {
143    pub fn new(nodes: FxIndexMap<NodeKey<'tcx>, Node<'tcx>>) -> Self {
144        let mut callers: UnordMap<_, Vec<_>> = UnordMap::default();
145        for (&caller, node) in &nodes {
146            for callee in node.resolved_callees() {
147                callers.entry(callee).or_default().push(caller);
148            }
149        }
150        CallGraph { nodes, callers }
151    }
152
153    /// The callee node resolved for the `Call` terminator at `location` in the body of `caller`.
154    /// Returns `None` for call sites that did not resolve to a concrete node (unresolved trait
155    /// calls, dynamic dispatch) or whose body is not in the graph.
156    pub fn resolved_callee(&self, caller: DefId, location: Location) -> Option<NodeKey<'tcx>> {
157        let node = self.nodes.get(&NodeKey::Item(caller))?;
158        node.call_sites().iter().find_map(|site| {
159            match site.kind {
160                CallSiteKind::Resolved { callee } if site.location == location => Some(callee),
161                _ => None,
162            }
163        })
164    }
165}
166
167impl<'tcx> fmt::Display for NodeKey<'tcx> {
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        match self {
170            NodeKey::Item(def_id) => write!(f, "{def_id:?}"),
171            NodeKey::Mono(instance) => write!(f, "{instance}"),
172        }
173    }
174}
175
176impl<'tcx> fmt::Display for Node<'tcx> {
177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178        match self {
179            Node::Analyzed { .. } => write!(f, "Analyzed"),
180            Node::ExternalCrate => write!(f, "ExternalCrate"),
181            Node::Leaf(kind) => write!(f, "Leaf({kind:?})"),
182        }
183    }
184}
185
186impl<'tcx> fmt::Display for CallSiteKind<'tcx> {
187    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
188        match self {
189            CallSiteKind::Resolved { callee } => write!(f, "-> {callee}"),
190            CallSiteKind::SynthesizedPanic => write!(f, "-> panic"),
191            CallSiteKind::Unresolved { def_id: method } => write!(f, "-> trait {method:?}"),
192            CallSiteKind::DynamicDispatch => write!(f, "-> <dynamic>"),
193        }
194    }
195}
196
197impl<'tcx> fmt::Display for CallGraph<'tcx> {
198    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
199        writeln!(f, "call graph ({} nodes):", self.nodes.len())?;
200        let mut nodes: Vec<_> = self.nodes.iter().collect();
201        nodes.sort_by_key(|(key, _)| format!("{key}"));
202        for (key, node) in nodes {
203            writeln!(f, "  {key} [{node}]:")?;
204            for site in node.call_sites() {
205                writeln!(f, "    {} at {:?}", site.kind, site.location)?;
206            }
207        }
208        Ok(())
209    }
210}
flux_middle/call_graph.rs

flux_middle/
call_graph.rs
