Skip to main content

rapx/analysis/
path.rs

1pub mod default;
2pub mod graph;
3
4use crate::util::source::get_fn_name_byid;
5use rustc_hir::def_id::DefId;
6use std::fmt::{self, Display};
7
8use crate::compat::{FxHashMap, FxHashSet};
9use graph::PathGraph;
10
11#[derive(Clone, Debug)]
12pub struct CallBinding {
13    pub args: Vec<CallArg>,
14    pub dest_local: usize,
15}
16
17#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub enum CallArg {
19    Local(usize),
20    Literal(u128),
21    Symbol(String),
22    FieldOffset,
23    Opaque,
24}
25
26/// Format a path slice with cleanup-block annotations.
27///
28/// Cleanup blocks (MIR unwind/drop paths) are marked with a `*` suffix.
29/// Example: `[0, 1, 2*, 3]` where block 2 is a cleanup block.
30pub fn format_path_annotated(path: &[usize], graph: &PathGraph<'_>) -> String {
31    let blocks: Vec<String> = path
32        .iter()
33        .map(|&b| {
34            if graph.is_cleanup_block(b) {
35                format!("{}*", b)
36            } else {
37                b.to_string()
38            }
39        })
40        .collect();
41    format!("[{}]", blocks.join(", "))
42}
43
44/// A prefix-tree (trie) of whole-CFG paths sharing common prefixes.
45///
46/// Paths are sequences of MIR block indices.  The trie compresses shared
47/// prefixes — if two paths `[0,1,2,5]` and `[0,1,2,6]` are both inserted,
48/// blocks 0→1→2 are stored once and branch at block 2.
49///
50/// Each node is a [`PathNode`]; a node with `is_path_end == true` marks the
51/// end of a complete path that exists in the tree.  The `len` field tracks
52/// the number of complete paths stored.
53///
54/// # Invariants
55/// - All paths inserted into a given tree start with the same root block
56///   (by construction, block 0 — the CFG entry).
57/// - Reachability is filtered during standard enumeration; verification can
58///   retain structural CFG paths and check feasibility in the symbolic VM.
59#[derive(Debug, Clone)]
60pub struct PathTree {
61    root: Option<PathNode>,
62    len: usize,
63    /// Per-block function ownership for composed verification paths.
64    block_fn: Vec<(DefId, usize)>,
65    /// Argument and return bindings for callee entry blocks.
66    call_bindings: FxHashMap<usize, CallBinding>,
67    /// Parent entry block of each callee entry block.
68    call_parents: FxHashMap<usize, usize>,
69    /// Caller blocks whose callee paths were composed into the tree.
70    expanded_call_blocks: FxHashSet<usize>,
71    /// Set when enumeration stopped at a path or depth limit, so the tree
72    /// holds only some of the paths.
73    truncated: bool,
74    structural: bool,
75    trait_impl_limited: bool,
76}
77
78/// A node in a [`PathTree`] trie.
79///
80/// `block` is the MIR block index for this node.  `children` holds
81/// successor blocks that appear after `block` in at least one stored
82/// path.  `is_path_end` is `true` when some path terminates at this
83/// node (i.e. this block is a CFG terminator for that path).
84#[derive(Debug, Clone)]
85pub struct PathNode {
86    pub block: usize,
87    pub children: Vec<PathNode>,
88    pub is_path_end: bool,
89}
90
91impl PathNode {
92    fn from_path(path: &[usize]) -> Self {
93        let mut node = PathNode {
94            block: path[0],
95            children: Vec::new(),
96            is_path_end: path.len() == 1,
97        };
98        if path.len() > 1 {
99            node.children.push(PathNode::from_path(&path[1..]));
100        }
101        node
102    }
103}
104
105impl PathTree {
106    pub fn new() -> Self {
107        PathTree {
108            root: None,
109            len: 0,
110            block_fn: Vec::new(),
111            call_bindings: FxHashMap::default(),
112            call_parents: FxHashMap::default(),
113            expanded_call_blocks: FxHashSet::default(),
114            truncated: false,
115            structural: false,
116            trait_impl_limited: false,
117        }
118    }
119
120    pub fn len(&self) -> usize {
121        self.len
122    }
123
124    pub fn is_truncated(&self) -> bool {
125        self.truncated
126    }
127
128    pub fn is_structural(&self) -> bool {
129        self.structural
130    }
131
132    pub fn is_trait_impl_limited(&self) -> bool {
133        self.trait_impl_limited
134    }
135
136    pub fn mark_trait_impl_limited(&mut self) {
137        self.trait_impl_limited = true;
138    }
139
140    pub fn mark_structural(&mut self) {
141        self.structural = true;
142    }
143
144    pub fn mark_truncated(&mut self) {
145        self.truncated = true;
146    }
147
148    pub fn is_empty(&self) -> bool {
149        self.len == 0
150    }
151
152    pub fn filter_paths(&self, keep: impl Fn(&[usize]) -> bool) -> Self {
153        let mut filtered = Self::new();
154        filtered.block_fn = self.block_fn.clone();
155        filtered.call_bindings = self.call_bindings.clone();
156        filtered.call_parents = self.call_parents.clone();
157        filtered.expanded_call_blocks = self.expanded_call_blocks.clone();
158        filtered.truncated = self.truncated;
159        filtered.structural = self.structural;
160        filtered.trait_impl_limited = self.trait_impl_limited;
161        for path in self.to_vecs() {
162            if keep(&path) {
163                filtered.insert(&path);
164            }
165        }
166        filtered
167    }
168
169    pub fn root(&self) -> Option<&PathNode> {
170        self.root.as_ref()
171    }
172
173    /// Set function ownership and callsite metadata for composed paths.
174    pub fn set_block_metadata(
175        &mut self,
176        map: Vec<(DefId, usize)>,
177        bindings: FxHashMap<usize, CallBinding>,
178        parents: FxHashMap<usize, usize>,
179        expanded_calls: FxHashSet<usize>,
180    ) {
181        self.block_fn = map;
182        self.call_bindings = bindings;
183        self.call_parents = parents;
184        self.expanded_call_blocks = expanded_calls;
185    }
186
187    /// Resolve `block` to `(def_id, local_index)`, or `None` for single-function
188    /// trees (where `block` is already a local index of the single function).
189    pub fn block_fn_of(&self, block: usize) -> Option<(DefId, usize)> {
190        self.block_fn.get(block).copied()
191    }
192
193    /// All `(def_id, local_index)` entries, indexed by global block number.
194    pub fn block_fns(&self) -> &[(DefId, usize)] {
195        &self.block_fn
196    }
197
198    /// Argument and return binding for a callee entry block.
199    pub fn call_binding(&self, block: usize) -> Option<&CallBinding> {
200        self.call_bindings.get(&block)
201    }
202
203    /// Parent entry block of a callee entry block.
204    pub fn call_parent_entry(&self, block: usize) -> Option<usize> {
205        self.call_parents.get(&block).copied()
206    }
207
208    /// Whether the call at `block` has callee paths in this tree.
209    pub fn is_expanded_call(&self, block: usize) -> bool {
210        self.expanded_call_blocks.contains(&block)
211    }
212
213    /// Insert a path into the tree. Returns `true` if the path was
214    /// newly added (not already present as a terminal path).
215    pub fn insert(&mut self, path: &[usize]) -> bool {
216        if path.is_empty() {
217            return false;
218        }
219
220        match &mut self.root {
221            None => {
222                self.root = Some(PathNode::from_path(path));
223                self.len = 1;
224                true
225            }
226            Some(root) => {
227                if root.block != path[0] {
228                    return false;
229                }
230                if Self::insert_into(root, &path[1..]) {
231                    self.len += 1;
232                    true
233                } else {
234                    false
235                }
236            }
237        }
238    }
239
240    fn insert_into(node: &mut PathNode, suffix: &[usize]) -> bool {
241        if suffix.is_empty() {
242            if node.is_path_end {
243                return false;
244            }
245            node.is_path_end = true;
246            return true;
247        }
248
249        let target = suffix[0];
250        for child in &mut node.children {
251            if child.block == target {
252                return Self::insert_into(child, &suffix[1..]);
253            }
254        }
255
256        node.children.push(PathNode::from_path(suffix));
257        true
258    }
259
260    /// Check whether the given path exists as a complete path in the tree.
261    pub fn contains(&self, path: &[usize]) -> bool {
262        let mut node = match self.root.as_ref() {
263            Some(n) => n,
264            None => return false,
265        };
266        if node.block != path[0] {
267            return false;
268        }
269        for &block in &path[1..] {
270            node = match node.children.iter().find(|c| c.block == block) {
271                Some(n) => n,
272                None => return false,
273            };
274        }
275        node.is_path_end
276    }
277
278    /// Enumerate all paths as owned `Vec<usize>`.
279    pub fn iter(&self) -> PathTreeIter<'_> {
280        PathTreeIter {
281            stack: self.root.as_ref().map(|r| vec![(r, vec![r.block])]).unwrap_or_default(),
282        }
283    }
284
285    /// Collect all paths into a flat `Vec<Vec<usize>>`.
286    pub fn to_vecs(&self) -> Vec<Vec<usize>> {
287        self.iter().collect()
288    }
289
290    /// Walk the tree and call `f` with each unique prefix that ends at
291    /// `target_block`. The walk stops at `target_block` (does not recurse
292    /// into its children), so the callback receives the path from the root
293    /// up to and including `target_block`.
294    ///
295    /// Returns `Some(())` if the walk completed, or `None` if `f` returned
296    /// `false` to request early termination.
297    pub fn walk_prefixes<F>(&self, target_block: usize, f: &mut F) -> Option<()>
298    where
299        F: FnMut(&[usize]) -> bool,
300    {
301        let Some(root) = self.root.as_ref() else {
302            return Some(());
303        };
304        let mut path = Vec::new();
305        Self::walk_prefixes_impl(root, &mut path, target_block, false, f)
306    }
307
308    /// Build a subtree holding only the prefixes that end at `target_block`,
309    /// preserving the block-function and inlining metadata so a sliced subtree
310    /// still resolves inlined-callee blocks.
311    pub fn subtree_to(&self, target_block: usize) -> PathTree {
312        let mut sub = PathTree::new();
313        sub.block_fn = self.block_fn.clone();
314        sub.call_bindings = self.call_bindings.clone();
315        sub.call_parents = self.call_parents.clone();
316        sub.expanded_call_blocks = self.expanded_call_blocks.clone();
317        sub.truncated = self.truncated;
318        sub.trait_impl_limited = self.trait_impl_limited;
319        sub.structural = self.structural;
320        let _ = self.walk_prefixes(target_block, &mut |prefix| {
321            sub.insert(prefix);
322            true
323        });
324        sub
325    }
326
327    /// Like [`Self::walk_prefixes`] but continues past the target block into
328    /// children, finding ALL occurrences (e.g. multiple iterations of the
329    /// same checkpoint block in a loop).
330    pub fn walk_all_prefixes<F>(&self, target_block: usize, f: &mut F) -> Option<()>
331    where
332        F: FnMut(&[usize]) -> bool,
333    {
334        let Some(root) = self.root.as_ref() else {
335            return Some(());
336        };
337        let mut path = Vec::new();
338        Self::walk_prefixes_impl(root, &mut path, target_block, true, f)
339    }
340
341    fn walk_prefixes_impl<F>(
342        node: &PathNode,
343        path: &mut Vec<usize>,
344        target_block: usize,
345        continue_past_target: bool,
346        f: &mut F,
347    ) -> Option<()>
348    where
349        F: FnMut(&[usize]) -> bool,
350    {
351        path.push(node.block);
352        if node.block == target_block {
353            let cont = f(path);
354            if !cont {
355                path.pop();
356                return None;
357            }
358            if !continue_past_target {
359                path.pop();
360                return Some(());
361            }
362        }
363        for child in &node.children {
364            Self::walk_prefixes_impl(child, path, target_block, continue_past_target, f)?;
365        }
366        path.pop();
367        Some(())
368    }
369}
370
371impl Default for PathTree {
372    fn default() -> Self {
373        Self::new()
374    }
375}
376
377/// DFS iterator over all complete paths in a [`PathTree`].
378///
379/// Yields each path as an owned `Vec<usize>`.  Internal nodes (where
380/// `is_path_end == false`) are skipped; only terminal path nodes are
381/// emitted.
382pub struct PathTreeIter<'a> {
383    stack: Vec<(&'a PathNode, Vec<usize>)>,
384}
385
386impl<'a> Iterator for PathTreeIter<'a> {
387    type Item = Vec<usize>;
388
389    fn next(&mut self) -> Option<Self::Item> {
390        loop {
391            let (node, path) = self.stack.pop()?;
392            for child in node.children.iter().rev() {
393                let mut child_path = path.clone();
394                child_path.push(child.block);
395                self.stack.push((child, child_path));
396            }
397            if node.is_path_end {
398                return Some(path);
399            }
400        }
401    }
402}
403
404/// Display wrapper that prints all paths for every function, annotated
405/// with cleanup-block markers via [`format_path_annotated`].
406pub struct PathMapWrapper<'a, 'tcx>(
407    pub FxHashMap<DefId, PathTree>,
408    pub &'a FxHashMap<DefId, PathGraph<'tcx>>,
409);
410
411impl Display for PathMapWrapper<'_, '_> {
412    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
413        writeln!(f, "=== Print path analysis results ===")?;
414        for (def_id, paths) in &self.0 {
415            let fn_name = get_fn_name_byid(def_id);
416            if fn_name.contains("__raw_ptr_deref_dummy") {
417                continue;
418            }
419            writeln!(f, "Function: {:?}:", fn_name)?;
420            let graph = self.1.get(def_id);
421            for path in paths.iter() {
422                if let Some(g) = graph {
423                    writeln!(f, "  Path {}", format_path_annotated(&path, g))?;
424                } else {
425                    writeln!(f, "  Path {:?}", path)?;
426                }
427            }
428        }
429        Ok(())
430    }
431}