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

flux_middle/
call_graph.rs
