rapx/analysis/core/alias_analysis/mop/
mop.rs

1use super::graph::*;
2use super::*;
3use rustc_data_structures::fx::FxHashSet;
4use rustc_hir::def_id::DefId;
5use rustc_middle::mir::Operand::{Constant, Copy, Move};
6use rustc_middle::mir::TerminatorKind;
7use rustc_middle::ty::TypingEnv;
8use std::collections::{HashMap, HashSet};
9use std::env;
10
11impl<'tcx> MopGraph<'tcx> {
12    pub fn split_check(
13        &mut self,
14        bb_index: usize,
15        fn_map: &mut FnMap,
16        recursion_set: &mut HashSet<DefId>,
17    ) {
18        /* duplicate the status before visiting a path; */
19        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
20        let backup_constant = self.constant.clone();
21        let backup_alias_set = self.alias_set.clone();
22        self.check(bb_index, fn_map, recursion_set);
23        /* restore after visit */
24        self.alias_set = backup_alias_set;
25        self.values = backup_values;
26        self.constant = backup_constant;
27    }
28    pub fn split_check_with_cond(
29        &mut self,
30        bb_index: usize,
31        path_discr_id: usize,
32        path_discr_val: usize,
33        fn_map: &mut FnMap,
34        recursion_set: &mut HashSet<DefId>,
35    ) {
36        /* duplicate the status before visiting a path; */
37        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
38        let backup_constant = self.constant.clone();
39        let backup_alias_set = self.alias_set.clone();
40        /* add control-sensitive indicator to the path status */
41        self.constant.insert(path_discr_id, path_discr_val);
42        self.check(bb_index, fn_map, recursion_set);
43        /* restore after visit */
44        self.alias_set = backup_alias_set;
45        self.values = backup_values;
46        self.constant = backup_constant;
47    }
48
49    // the core function of the safedrop.
50    pub fn check(
51        &mut self,
52        bb_index: usize,
53        fn_map: &mut FnMap,
54        recursion_set: &mut HashSet<DefId>,
55    ) {
56        self.visit_times += 1;
57        if self.visit_times > VISIT_LIMIT {
58            return;
59        }
60        let cur_block = self.blocks[self.scc_indices[bb_index]].clone();
61        self.alias_bb(self.scc_indices[bb_index]);
62        self.alias_bbcall(self.scc_indices[bb_index], fn_map, recursion_set);
63
64        if self.child_scc.get(&self.scc_indices[bb_index]).is_some() {
65            let init_index = self.scc_indices[bb_index];
66            let (init_block, cur_targets, scc_block_set) =
67                self.child_scc.get(&init_index).unwrap().clone();
68
69            for enum_index in cur_targets.all_targets() {
70                let backup_values = self.values.clone();
71                let backup_constant = self.constant.clone();
72
73                let mut block_node = if bb_index == init_index {
74                    init_block.clone()
75                } else {
76                    self.blocks[bb_index].clone()
77                };
78
79                if !block_node.switch_stmts.is_empty() {
80                    let TerminatorKind::SwitchInt { discr: _, targets } =
81                        block_node.switch_stmts[0].kind.clone()
82                    else {
83                        unreachable!();
84                    };
85                    if cur_targets == targets {
86                        block_node.next = FxHashSet::default();
87                        block_node.next.insert(enum_index.index());
88                    }
89                }
90
91                let mut work_list = Vec::new();
92                let mut work_set = FxHashSet::<usize>::default();
93                work_list.push(bb_index);
94                work_set.insert(bb_index);
95                while !work_list.is_empty() {
96                    let current_node = work_list.pop().unwrap();
97                    block_node.scc_sub_blocks.push(current_node);
98                    let real_node = if current_node != init_index {
99                        self.blocks[current_node].clone()
100                    } else {
101                        init_block.clone()
102                    };
103
104                    if real_node.switch_stmts.is_empty() {
105                        for next in &real_node.next {
106                            block_node.next.insert(*next);
107                        }
108                    } else {
109                        let TerminatorKind::SwitchInt {
110                            discr: _,
111                            ref targets,
112                        } = real_node.switch_stmts[0].kind
113                        else {
114                            unreachable!();
115                        };
116
117                        if cur_targets == *targets {
118                            block_node.next.insert(enum_index.index());
119                        } else {
120                            for next in &real_node.next {
121                                block_node.next.insert(*next);
122                            }
123                        }
124                    }
125
126                    if real_node.switch_stmts.is_empty() {
127                        for next in &real_node.next {
128                            if scc_block_set.contains(next) && !work_set.contains(next) {
129                                work_set.insert(*next);
130                                work_list.push(*next);
131                            }
132                        }
133                    } else {
134                        let TerminatorKind::SwitchInt {
135                            discr: _,
136                            ref targets,
137                        } = real_node.switch_stmts[0].kind
138                        else {
139                            unreachable!();
140                        };
141
142                        if cur_targets == *targets {
143                            let next_index = enum_index.index();
144                            if scc_block_set.contains(&next_index)
145                                && !work_set.contains(&next_index)
146                            {
147                                work_set.insert(next_index);
148                                work_list.push(next_index);
149                            }
150                        } else {
151                            for next in &real_node.next {
152                                if scc_block_set.contains(next) && !work_set.contains(next) {
153                                    work_set.insert(*next);
154                                    work_list.push(*next);
155                                }
156                            }
157                        }
158                    }
159                }
160
161                /* remove next nodes which are already in the current SCC */
162                let mut to_remove = Vec::new();
163                for i in block_node.next.iter() {
164                    if self.scc_indices[*i] == init_index {
165                        to_remove.push(*i);
166                    }
167                }
168                for i in to_remove {
169                    block_node.next.remove(&i);
170                }
171
172                for i in block_node.scc_sub_blocks.clone() {
173                    self.alias_bb(i);
174                    self.alias_bbcall(i, fn_map, recursion_set);
175                }
176                /* Reach a leaf node, check bugs */
177                match block_node.next.len() {
178                    0 => {}
179                    _ => {
180                        /*
181                         * Equivalent to self.check(cur_block.next[0]..);
182                         * We cannot use [0] for FxHashSet.
183                         */
184                        for next in block_node.next {
185                            self.check(next, fn_map, recursion_set);
186                        }
187                    }
188                }
189
190                self.values = backup_values;
191                self.constant = backup_constant;
192            }
193
194            return;
195        }
196
197        let mut order = vec![];
198        order.push(vec![]);
199
200        /* Handle cases if the current block is a merged scc block with sub block */
201        if !cur_block.scc_sub_blocks.is_empty() {
202            match env::var_os("MOP") {
203                Some(val) if val == "0" => {
204                    order.push(cur_block.scc_sub_blocks.clone());
205                }
206                _ => {
207                    self.calculate_scc_order(
208                        &mut cur_block.scc_sub_blocks.clone(),
209                        &mut vec![],
210                        &mut order,
211                        &mut HashMap::new(),
212                        bb_index,
213                        bb_index,
214                        &mut HashSet::new(),
215                    );
216                }
217            }
218        }
219
220        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
221        let backup_constant = self.constant.clone();
222        let backup_alias_set = self.alias_set.clone();
223        let backup_fn_map = fn_map.clone();
224        let backup_recursion_set = recursion_set.clone();
225        for scc_each in order {
226            self.alias_set = backup_alias_set.clone();
227            self.values = backup_values.clone();
228            self.constant = backup_constant.clone();
229            *fn_map = backup_fn_map.clone();
230            *recursion_set = backup_recursion_set.clone();
231
232            if !scc_each.is_empty() {
233                for idx in scc_each {
234                    self.alias_bb(idx);
235                    self.alias_bbcall(idx, fn_map, recursion_set);
236                }
237            }
238
239            let cur_block = cur_block.clone();
240            /* Reach a leaf node, check bugs */
241            match cur_block.next.len() {
242                0 => {
243                    let results_nodes = self.values.clone();
244                    self.merge_results(results_nodes);
245                    return;
246                }
247                1 => {
248                    /*
249                     * Equivalent to self.check(cur_block.next[0]..);
250                     * We cannot use [0] for FxHashSet.
251                     */
252                    for next in cur_block.next {
253                        self.check(next, fn_map, recursion_set);
254                    }
255                    return;
256                }
257                _ => { // multiple blocks
258                }
259            }
260
261            /* Begin: handle the SwitchInt statement. */
262            let mut single_target = false;
263            let mut sw_val = 0;
264            let mut sw_target = 0; // Single target
265            let mut path_discr_id = 0; // To avoid analyzing paths that cannot be reached with one enum type.
266            let mut sw_targets = None; // Multiple targets of SwitchInt
267            if !cur_block.switch_stmts.is_empty() && cur_block.scc_sub_blocks.is_empty() {
268                if let TerminatorKind::SwitchInt {
269                    ref discr,
270                    ref targets,
271                } = cur_block.switch_stmts[0].clone().kind
272                {
273                    match discr {
274                        Copy(p) | Move(p) => {
275                            let place = self.projection(false, *p);
276                            if let Some(father) = self.disc_map.get(&self.values[place].local) {
277                                if let Some(constant) = self.constant.get(father) {
278                                    if *constant != usize::MAX {
279                                        single_target = true;
280                                        sw_val = *constant;
281                                    }
282                                }
283                                if self.values[place].local == place {
284                                    path_discr_id = *father;
285                                    sw_targets = Some(targets.clone());
286                                }
287                            }
288                        }
289                        Constant(c) => {
290                            single_target = true;
291                            let ty_env = TypingEnv::post_analysis(self.tcx, self.def_id);
292                            if let Some(val) = c.const_.try_eval_target_usize(self.tcx, ty_env) {
293                                sw_val = val as usize;
294                            }
295                        }
296                    }
297                    if single_target {
298                        /* Find the target based on the value;
299                         * Since sw_val is a const, only one target is reachable.
300                         * Filed 0 is the value; field 1 is the real target.
301                         */
302                        for iter in targets.iter() {
303                            if iter.0 as usize == sw_val {
304                                sw_target = iter.1.as_usize();
305                                break;
306                            }
307                        }
308                        /* No target found, choose the default target.
309                         * The default targets is not included within the iterator.
310                         * We can only obtain the default target based on the last item of all_targets().
311                         */
312                        if sw_target == 0 {
313                            let all_target = targets.all_targets();
314                            sw_target = all_target[all_target.len() - 1].as_usize();
315                        }
316                    }
317                }
318            }
319            /* End: finish handling SwitchInt */
320            // fixed path since a constant switchInt value
321            if single_target {
322                self.check(sw_target, fn_map, recursion_set);
323            } else {
324                // Other cases in switchInt terminators
325                if let Some(targets) = sw_targets {
326                    for iter in targets.iter() {
327                        if self.visit_times > VISIT_LIMIT {
328                            continue;
329                        }
330                        let next_index = iter.1.as_usize();
331                        let path_discr_val = iter.0 as usize;
332                        self.split_check_with_cond(
333                            next_index,
334                            path_discr_id,
335                            path_discr_val,
336                            fn_map,
337                            recursion_set,
338                        );
339                    }
340                    let all_targets = targets.all_targets();
341                    let next_index = all_targets[all_targets.len() - 1].as_usize();
342                    let path_discr_val = usize::MAX; // to indicate the default path;
343                    self.split_check_with_cond(
344                        next_index,
345                        path_discr_id,
346                        path_discr_val,
347                        fn_map,
348                        recursion_set,
349                    );
350                } else {
351                    for i in cur_block.next {
352                        if self.visit_times > VISIT_LIMIT {
353                            continue;
354                        }
355                        let next_index = i;
356                        self.split_check(next_index, fn_map, recursion_set);
357                    }
358                }
359            }
360        }
361    }
362
363    pub fn calculate_scc_order(
364        &mut self,
365        scc: &Vec<usize>,
366        path: &mut Vec<usize>,
367        ans: &mut Vec<Vec<usize>>,
368        disc_map: &mut HashMap<usize, usize>,
369        idx: usize,
370        root: usize,
371        visit: &mut HashSet<usize>,
372    ) {
373        if idx == root && !path.is_empty() {
374            ans.push(path.clone());
375            return;
376        }
377        visit.insert(idx);
378        let term = &self.terms[idx].clone();
379
380        match term {
381            TerminatorKind::SwitchInt {
382                ref discr,
383                ref targets,
384            } => match discr {
385                Copy(p) | Move(p) => {
386                    let place = self.projection(false, *p);
387                    if let Some(father) = self.disc_map.get(&self.values[place].local) {
388                        let father = *father;
389                        if let Some(constant) = disc_map.get(&father) {
390                            let constant = *constant;
391                            for t in targets.iter() {
392                                if t.0 as usize == constant {
393                                    let target = t.1.as_usize();
394                                    if path.contains(&target) {
395                                        continue;
396                                    }
397                                    path.push(target);
398                                    self.calculate_scc_order(
399                                        scc, path, ans, disc_map, target, root, visit,
400                                    );
401                                    path.pop();
402                                }
403                            }
404                        } else {
405                            for t in targets.iter() {
406                                let constant = t.0 as usize;
407                                let target = t.1.as_usize();
408                                if path.contains(&target) {
409                                    continue;
410                                }
411                                path.push(target);
412                                disc_map.insert(father, constant);
413                                self.calculate_scc_order(
414                                    scc, path, ans, disc_map, target, root, visit,
415                                );
416                                disc_map.remove(&father);
417                                path.pop();
418                            }
419                        }
420                    } else {
421                        if let Some(constant) = disc_map.get(&place) {
422                            let constant = *constant;
423                            for t in targets.iter() {
424                                if t.0 as usize == constant {
425                                    let target = t.1.as_usize();
426                                    if path.contains(&target) {
427                                        continue;
428                                    }
429                                    path.push(target);
430                                    self.calculate_scc_order(
431                                        scc, path, ans, disc_map, target, root, visit,
432                                    );
433                                    path.pop();
434                                }
435                            }
436                        } else {
437                            for t in targets.iter() {
438                                let constant = t.0 as usize;
439                                let target = t.1.as_usize();
440                                if path.contains(&target) {
441                                    continue;
442                                }
443                                path.push(target);
444                                disc_map.insert(place, constant);
445                                self.calculate_scc_order(
446                                    scc, path, ans, disc_map, target, root, visit,
447                                );
448                                disc_map.remove(&place);
449                                path.pop();
450                            }
451
452                            let constant = targets.iter().len();
453                            let target = targets.otherwise().as_usize();
454                            if !path.contains(&target) {
455                                path.push(target);
456                                disc_map.insert(place, constant);
457                                self.calculate_scc_order(
458                                    scc, path, ans, disc_map, target, root, visit,
459                                );
460                                disc_map.remove(&place);
461                                path.pop();
462                            }
463                        }
464                    }
465                }
466                _ => {}
467            },
468            _ => {
469                for bidx in self.blocks[idx].next.clone() {
470                    if !scc.contains(&bidx) && bidx != root {
471                        continue;
472                    }
473                    if bidx != root {
474                        path.push(bidx);
475                        self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
476                        path.pop();
477                    } else {
478                        self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
479                    }
480                }
481            }
482        }
483
484        visit.remove(&idx);
485    }
486}