rapx/analysis/range/domain/constraint_graph/
mod.rs

1pub mod debug;
2pub mod graph;
3pub mod solver;
4
5use crate::analysis::range::domain::domain::*;
6use crate::analysis::range::Range;
7
8use crate::analysis::range::domain::symbolic_expr::*;
9use crate::analysis::path::PathTree;
10use rustc_abi::FieldIdx;
11use rustc_hir::def_id::DefId;
12use rustc_middle::{
13    mir::*,
14    ty::{self, TyCtxt},
15};
16
17use std::{
18    collections::{HashMap, HashSet, VecDeque},
19    fmt::Debug,
20};
21
22#[derive(Clone)]
23
24pub struct ConstraintGraph<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
25    pub tcx: TyCtxt<'tcx>,
26    pub body: &'tcx Body<'tcx>,
27    // Protected fields
28    pub self_def_id: DefId,      // The DefId of the function being analyzed
29    pub vars: VarNodes<'tcx, T>, // The variables of the source program
30
31    pub oprs: Vec<BasicOpKind<'tcx, T>>, // The operations of the source program
32
33    pub defmap: DefMap<'tcx>, // Map from variables to the operations that define them
34    pub usemap: UseMap<'tcx>, // Map from variables to operations where variables are used
35    pub symbmap: SymbMap<'tcx>, // Map from variables to operations where they appear as bounds
36    pub values_branchmap: HashMap<&'tcx Place<'tcx>, ValueBranchMap<'tcx, T>>, // Store intervals, basic blocks, and branches
37    constant_vector: Vec<T>, // Vector for constants from an SCC
38
39    pub essa: DefId,
40    pub ssa: DefId,
41    pub index: i32,
42    pub dfs: HashMap<&'tcx Place<'tcx>, i32>,
43    pub root: HashMap<&'tcx Place<'tcx>, &'tcx Place<'tcx>>,
44    pub in_component: HashSet<&'tcx Place<'tcx>>,
45    pub components: HashMap<&'tcx Place<'tcx>, HashSet<&'tcx Place<'tcx>>>,
46    pub worklist: VecDeque<&'tcx Place<'tcx>>,
47    pub numAloneSCCs: usize,
48    pub numSCCs: usize, // Add a stub for pre_update to resolve the missing method error.
49    pub final_vars: VarNodes<'tcx, T>,
50    pub rerurn_places: HashSet<&'tcx Place<'tcx>>,
51    pub switchbbs: HashMap<BasicBlock, (Place<'tcx>, Place<'tcx>)>,
52    pub const_func_place: HashMap<&'tcx Place<'tcx>, usize>,
53    pub unique_adt_path: HashMap<String, usize>,
54}
55
56
57
58impl<'tcx, T> ConstraintGraph<'tcx, T>
59where
60    T: IntervalArithmetic + ConstConvert + Debug,
61{
62    pub fn convert_const(c: &Const) -> Option<T> {
63        T::from_const(c)
64    }
65
66    pub fn new(
67        body: &'tcx Body<'tcx>,
68        tcx: TyCtxt<'tcx>,
69        self_def_id: DefId,
70        essa: DefId,
71        ssa: DefId,
72    ) -> Self {
73        let mut unique_adt_path: HashMap<String, usize> = HashMap::new();
74        unique_adt_path.insert("std::ops::Range".to_string(), 1);
75
76        Self {
77            tcx,
78            body,
79            self_def_id,
80            vars: VarNodes::new(),
81            oprs: GenOprs::new(),
82            defmap: DefMap::new(),
83            usemap: UseMap::new(),
84            symbmap: SymbMap::new(),
85            values_branchmap: ValuesBranchMap::new(),
86            constant_vector: Vec::new(),
87            essa,
88            ssa,
89            index: 0,
90            dfs: HashMap::new(),
91            root: HashMap::new(),
92            in_component: HashSet::new(),
93            components: HashMap::new(),
94            worklist: VecDeque::new(),
95            numAloneSCCs: 0,
96            numSCCs: 0,
97            final_vars: VarNodes::new(),
98            rerurn_places: HashSet::new(),
99            switchbbs: HashMap::new(),
100            const_func_place: HashMap::new(),
101            unique_adt_path: unique_adt_path,
102        }
103    }
104
105    pub fn new_without_ssa(body: &'tcx Body<'tcx>, tcx: TyCtxt<'tcx>, self_def_id: DefId) -> Self {
106        let mut unique_adt_path: HashMap<String, usize> = HashMap::new();
107        unique_adt_path.insert("std::ops::Range".to_string(), 1);
108        Self {
109            tcx,
110            body,
111            self_def_id,
112            vars: VarNodes::new(),
113
114            oprs: GenOprs::new(),
115            defmap: DefMap::new(),
116            usemap: UseMap::new(),
117            symbmap: SymbMap::new(),
118            values_branchmap: ValuesBranchMap::new(),
119            constant_vector: Vec::new(),
120            essa: self_def_id, // Assuming essa is the same as self_def_id
121            ssa: self_def_id,  // Assuming ssa is the same as self_def_id
122            index: 0,
123            dfs: HashMap::new(),
124            root: HashMap::new(),
125            in_component: HashSet::new(),
126            components: HashMap::new(),
127            worklist: VecDeque::new(),
128            numAloneSCCs: 0,
129            numSCCs: 0,
130            final_vars: VarNodes::new(),
131            rerurn_places: HashSet::new(),
132            switchbbs: HashMap::new(),
133            const_func_place: HashMap::new(),
134            unique_adt_path: unique_adt_path,
135        }
136    }
137
138    pub fn build_final_vars(
139        &mut self,
140        places_map: &HashMap<Place<'tcx>, HashSet<Place<'tcx>>>,
141    ) -> (VarNodes<'tcx, T>, Vec<Place<'tcx>>) {
142        let mut final_vars: VarNodes<'tcx, T> = HashMap::new();
143        let mut not_found: Vec<Place<'tcx>> = Vec::new();
144
145        for (&_key_place, place_set) in places_map {
146            for &place in place_set {
147                let found = self.vars.iter().find(|&(&p, _)| *p == place);
148
149                if let Some((&found_place, var_node)) = found {
150                    final_vars.insert(found_place, var_node.clone());
151                } else {
152                    not_found.push(place);
153                }
154            }
155        }
156        self.final_vars = final_vars.clone();
157        (final_vars, not_found)
158    }
159
160    pub fn filter_final_vars(
161        vars: &VarNodes<'tcx, T>,
162        places_map: &HashMap<Place<'tcx>, HashSet<Place<'tcx>>>,
163    ) -> HashMap<Place<'tcx>, Range<T>> {
164        let mut final_vars = HashMap::new();
165
166        for (&_key_place, place_set) in places_map {
167            for &place in place_set {
168                if let Some(var_node) = vars.get(&place) {
169                    final_vars.insert(place, var_node.get_range().clone());
170                }
171            }
172        }
173        final_vars
174    }
175
176    pub fn get_vars(&self) -> &VarNodes<'tcx, T> {
177        &self.vars
178    }
179
180    pub fn get_field_place(&self, adt_place: Place<'tcx>, field_index: FieldIdx) -> Place<'tcx> {
181        let adt_ty = adt_place.ty(&self.body.local_decls, self.tcx).ty;
182        let field_ty = match adt_ty.kind() {
183            ty::TyKind::Adt(adt_def, substs) => {
184                // Get the single variant of the struct using an iterator.
185                let Some(variant_def) = adt_def.variants().iter().next() else {
186                    rap_trace!("get_field_place: ADT has no variants\n");
187                    return adt_place;
188                };
189
190                // Get the field's definition from the variant.
191                let field_def = &variant_def.fields[field_index];
192
193                // Return the field's type as the result of this match arm.
194                // (The "let field_ty =" is removed from this line)
195                #[cfg(not(rapx_ge_99))]
196                let ft = field_def.ty(self.tcx, substs);
197                #[cfg(rapx_ge_99)]
198                let ft = field_def.ty(self.tcx, substs).skip_norm_wip();
199                ft
200            }
201            _ => {
202                panic!("get_field_place expected an ADT, but found {:?}", adt_ty);
203            }
204        };
205
206        let mut new_projection = adt_place.projection.to_vec();
207        new_projection.push(ProjectionElem::Field(field_index, field_ty));
208
209        let new_place = Place {
210            local: adt_place.local,
211            projection: self.tcx.mk_place_elems(&new_projection),
212        };
213        new_place
214    }
215
216    pub fn start_analyze_path_constraints(
217        &mut self,
218        body: &'tcx Body<'tcx>,
219        tree: &PathTree,
220    ) -> HashMap<Vec<usize>, Vec<(Place<'tcx>, Place<'tcx>, BinOp)>> {
221        self.build_value_maps(body);
222        let result = self.analyze_path_constraints(body, tree);
223        result
224    }
225
226    pub fn analyze_path_constraints(
227        &self,
228        body: &'tcx Body<'tcx>,
229        tree: &PathTree,
230    ) -> HashMap<Vec<usize>, Vec<(Place<'tcx>, Place<'tcx>, BinOp)>> {
231        let mut all_path_results: HashMap<Vec<usize>, Vec<(Place<'tcx>, Place<'tcx>, BinOp)>> =
232            HashMap::with_capacity(tree.len());
233
234        for path_indices in tree.iter() {
235            let mut current_path_constraints: Vec<(Place<'tcx>, Place<'tcx>, BinOp)> = Vec::new();
236
237            let path_bbs: Vec<BasicBlock> = path_indices
238                .iter()
239                .map(|&idx| BasicBlock::from_usize(idx))
240                .collect();
241
242            for window in path_bbs.windows(2) {
243                let current_bb = window[0];
244
245                if self.switchbbs.contains_key(&current_bb) {
246                    let next_bb = window[1];
247                    let current_bb_data = &body[current_bb];
248
249                    if let Some(Terminator {
250                        kind: TerminatorKind::SwitchInt { discr, .. },
251                        ..
252                    }) = &current_bb_data.terminator
253                    {
254                        let Some((constraint_place_1_ref, constraint_place_2_ref)) =
255                            self.switchbbs.get(&current_bb) else {
256                                rap_trace!("addvar_in_branches: bb {:?} not in switchbbs\n", current_bb);
257                                continue;
258                            };
259                        let constraint_place_1 = *constraint_place_1_ref;
260                        let constraint_place_2 = *constraint_place_2_ref;
261                        if let Some(vbm) = self.values_branchmap.get(&constraint_place_1) {
262                            let relevant_interval_opt = if next_bb == *vbm.get_bb_true() {
263                                Some(vbm.get_itv_t())
264                            } else if next_bb == *vbm.get_bb_false() {
265                                Some(vbm.get_itv_f())
266                            } else {
267                                None
268                            };
269
270                            if let Some(relevant_interval) = relevant_interval_opt {
271                                match relevant_interval {
272                                    IntervalType::Basic(basic_interval) => {}
273                                    IntervalType::Symb(symb_interval) => {
274                                        current_path_constraints.push((
275                                            constraint_place_1.clone(),
276                                            constraint_place_2.clone(),
277                                            symb_interval.get_operation().clone(),
278                                        ));
279                                    }
280                                }
281                            }
282                        }
283                    }
284                }
285            }
286
287            all_path_results.insert(path_indices, current_path_constraints);
288        }
289
290        all_path_results
291    }
292}
rapx/analysis/range/domain/constraint_graph/mod.rs

rapx/analysis/range/domain/constraint_graph/
mod.rs
