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
26pub 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#[derive(Debug, Clone)]
60pub struct PathTree {
61 root: Option<PathNode>,
62 len: usize,
63 block_fn: Vec<(DefId, usize)>,
65 call_bindings: FxHashMap<usize, CallBinding>,
67 call_parents: FxHashMap<usize, usize>,
69 expanded_call_blocks: FxHashSet<usize>,
71 truncated: bool,
74 structural: bool,
75 trait_impl_limited: bool,
76}
77
78#[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 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 pub fn block_fn_of(&self, block: usize) -> Option<(DefId, usize)> {
190 self.block_fn.get(block).copied()
191 }
192
193 pub fn block_fns(&self) -> &[(DefId, usize)] {
195 &self.block_fn
196 }
197
198 pub fn call_binding(&self, block: usize) -> Option<&CallBinding> {
200 self.call_bindings.get(&block)
201 }
202
203 pub fn call_parent_entry(&self, block: usize) -> Option<usize> {
205 self.call_parents.get(&block).copied()
206 }
207
208 pub fn is_expanded_call(&self, block: usize) -> bool {
210 self.expanded_call_blocks.contains(&block)
211 }
212
213 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 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 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 pub fn to_vecs(&self) -> Vec<Vec<usize>> {
287 self.iter().collect()
288 }
289
290 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 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 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
377pub 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
404pub 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}