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

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