rapx/analysis/range_analysis/domain/
domain.rs

1#![allow(unused_imports)]
2#![allow(unused_variables)]
3#![allow(dead_code)]
4#![allow(unused_assignments)]
5#![allow(unused_parens)]
6#![allow(non_snake_case)]
7use rust_intervals::NothingBetween;
8
9use crate::analysis::range_analysis::domain::ConstraintGraph::ConstraintGraph;
10use crate::analysis::range_analysis::domain::SymbolicExpr::{
11    BasicInterval, IntervalType, IntervalTypeTrait, SymbExpr,
12};
13use crate::analysis::range_analysis::{Range, RangeType};
14use crate::compat::FxHashMap;
15use crate::{rap_debug, rap_trace};
16use num_traits::{Bounded, CheckedAdd, CheckedSub, One, ToPrimitive, Zero, ops};
17use rustc_abi::Size;
18use rustc_hir::def_id::DefId;
19use rustc_middle::mir::coverage::Op;
20use rustc_middle::mir::{
21    BasicBlock, BinOp, BorrowKind, CastKind, Const, Local, LocalDecl, Operand, Place, Rvalue,
22    Statement, StatementKind, Terminator, UnOp,
23};
24use rustc_middle::ty::ScalarInt;
25use rustc_span::sym::no_default_passes;
26use std::cell::RefCell;
27use std::cmp::PartialEq;
28use std::collections::{HashMap, HashSet};
29use std::fmt;
30use std::fmt::Debug;
31use std::hash::Hash;
32use std::ops::{Add, Mul, Sub};
33use std::rc::Rc;
34pub trait ConstConvert: Sized {
35    fn from_const(c: &Const) -> Option<Self>;
36}
37
38impl ConstConvert for u32 {
39    fn from_const(c: &Const) -> Option<Self> {
40        if let Some(scalar) = c.try_to_scalar_int() {
41            Some(scalar.to_bits(scalar.size()) as u32)
42        } else {
43            None
44        }
45    }
46}
47impl ConstConvert for usize {
48    fn from_const(c: &Const) -> Option<Self> {
49        if let Some(scalar) = c.try_to_scalar_int() {
50            Some(scalar.to_bits(scalar.size()) as usize)
51        } else {
52            None
53        }
54    }
55}
56impl ConstConvert for i32 {
57    fn from_const(c: &Const) -> Option<Self> {
58        if let Some(scalar) = c.try_to_scalar_int() {
59            Some(scalar.to_bits(scalar.size()) as i32)
60        } else {
61            None
62        }
63    }
64}
65
66impl ConstConvert for i64 {
67    fn from_const(c: &Const) -> Option<Self> {
68        if let Some(scalar) = c.try_to_scalar_int() {
69            Some(scalar.to_bits(scalar.size()) as i64)
70        } else {
71            None
72        }
73    }
74}
75impl ConstConvert for i128 {
76    fn from_const(c: &Const) -> Option<Self> {
77        if let Some(scalar) = c.try_to_scalar_int() {
78            Some(scalar.to_bits(scalar.size()) as i128)
79        } else {
80            None
81        }
82    }
83}
84pub trait IntervalArithmetic:
85    PartialOrd
86    + Clone
87    + Bounded
88    + Zero
89    + Copy
90    + One
91    + CheckedAdd
92    + CheckedSub
93    + Add<Output = Self>
94    + Sub<Output = Self>
95    + Mul<Output = Self>
96    + core::fmt::Debug
97    + PartialOrd
98    + PartialEq
99    + NothingBetween
100{
101}
102
103impl IntervalArithmetic for i32 {}
104impl IntervalArithmetic for usize {}
105impl IntervalArithmetic for i64 {}
106use rustc_middle::ty::Ty;
107
108// Define the basic operation trait
109pub trait Operation<T: IntervalArithmetic + ConstConvert + Debug> {
110    fn eval(&self) -> Range<T>; // Method to evaluate the range of the operation
111    fn print(&self, os: &mut dyn fmt::Write);
112}
113
114#[derive(Debug, Clone)]
115pub enum BasicOpKind<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
116    Unary(UnaryOp<'tcx, T>),
117    Binary(BinaryOp<'tcx, T>),
118    Essa(EssaOp<'tcx, T>),
119    ControlDep(ControlDep<'tcx, T>),
120    Phi(PhiOp<'tcx, T>),
121    Use(UseOp<'tcx, T>),
122    Call(CallOp<'tcx, T>),
123    Ref(RefOp<'tcx, T>),
124    Aggregate(AggregateOp<'tcx, T>),
125}
126
127impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> fmt::Display for BasicOpKind<'tcx, T> {
128    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
129        match self {
130            BasicOpKind::Unary(op) => write!(
131                f,
132                "UnaryOp: intersect {} sink:{:?} source:{:?} inst:{:?} ",
133                op.intersect, op.sink, op.source, op.inst
134            ),
135            BasicOpKind::Binary(op) => write!(
136                f,
137                "BinaryOp: intersect {} sink:{:?} source1:{:?} source2:{:?} inst:{:?} const_value:{} ",
138                op.intersect,
139                op.sink,
140                op.source1,
141                op.source2,
142                op.inst,
143                op.const_value.clone().unwrap()
144            ),
145            BasicOpKind::Essa(op) => write!(
146                f,
147                "EssaOp: intersect {} sink:{:?} source:{:?} inst:{:?} unresolved:{:?} ",
148                op.intersect, op.sink, op.source, op.inst, op.unresolved
149            ),
150            BasicOpKind::ControlDep(op) => write!(
151                f,
152                "ControlDep: intersect {} sink:{:?} source:{:?} inst:{:?}  ",
153                op.intersect, op.sink, op.source, op.inst
154            ),
155            BasicOpKind::Phi(op) => write!(
156                f,
157                "PhiOp: intersect {} sink:{:?} source:{:?} inst:{:?}  ",
158                op.intersect, op.sink, op.sources, op.inst
159            ),
160            BasicOpKind::Use(op) => write!(
161                f,
162                "UseOp: intersect {} sink:{:?} source:{:?} inst:{:?} ",
163                op.intersect, op.sink, op.source, op.inst
164            ),
165            BasicOpKind::Call(op) => write!(
166                f,
167                "CallOp: intersect {} sink:{:?} args:{:?} inst:{:?}",
168                op.intersect, op.sink, op.args, op.inst
169            ),
170            BasicOpKind::Ref(op) => write!(
171                f,
172                "RefOp: intersect {} sink:{:?} source:{:?} inst:{:?} borrowkind:{:?}",
173                op.intersect, op.sink, op.source, op.inst, op.borrowkind
174            ),
175            BasicOpKind::Aggregate(op) => write!(
176                f,
177                "AggregateOp: intersect {} sink:{:?} operands:{:?} inst:{:?}",
178                op.intersect, op.sink, op.operands, op.inst
179            ),
180        }
181    }
182}
183impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> BasicOpKind<'tcx, T> {
184    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
185        match self {
186            BasicOpKind::Unary(op) => op.eval(),
187            BasicOpKind::Binary(op) => op.eval(vars),
188            BasicOpKind::Essa(op) => op.eval(vars),
189            BasicOpKind::ControlDep(op) => op.eval(),
190            BasicOpKind::Phi(op) => op.eval(vars),
191            BasicOpKind::Use(op) => op.eval(vars),
192            BasicOpKind::Call(op) => op.eval(vars),
193            BasicOpKind::Ref(op) => op.eval(vars),
194            BasicOpKind::Aggregate(op) => op.eval(vars),
195        }
196    }
197    pub fn get_type_name(&self) -> &'static str {
198        match self {
199            BasicOpKind::Unary(_) => "Unary",
200            BasicOpKind::Binary(_) => "Binary",
201            BasicOpKind::Essa(_) => "Essa",
202            BasicOpKind::ControlDep(_) => "ControlDep",
203            BasicOpKind::Phi(_) => "Phi",
204            BasicOpKind::Use(_) => "Use",
205            BasicOpKind::Call(_) => "Call",
206            BasicOpKind::Ref(_) => "Ref",
207            BasicOpKind::Aggregate(_) => "Aggregate",
208        }
209    }
210    pub fn get_sink(&self) -> &'tcx Place<'tcx> {
211        match self {
212            BasicOpKind::Unary(op) => op.sink,
213            BasicOpKind::Binary(op) => op.sink,
214            BasicOpKind::Essa(op) => op.sink,
215            BasicOpKind::ControlDep(op) => op.sink,
216            BasicOpKind::Phi(op) => op.sink,
217            BasicOpKind::Use(op) => op.sink,
218            BasicOpKind::Call(op) => op.sink,
219            BasicOpKind::Ref(op) => op.sink,
220            BasicOpKind::Aggregate(op) => op.sink,
221        }
222    }
223    pub fn get_instruction(&self) -> Option<&'tcx Statement<'tcx>> {
224        match self {
225            BasicOpKind::Unary(op) => Some(op.inst),
226            BasicOpKind::Binary(op) => Some(op.inst),
227            BasicOpKind::Essa(op) => Some(op.inst),
228            BasicOpKind::ControlDep(op) => Some(op.inst),
229            BasicOpKind::Phi(op) => Some(op.inst),
230            BasicOpKind::Use(op) => Some(op.inst),
231            BasicOpKind::Call(op) => None,
232            BasicOpKind::Ref(op) => Some(op.inst),
233            BasicOpKind::Aggregate(op) => Some(op.inst),
234        }
235    }
236    pub fn get_intersect(&self) -> &IntervalType<'tcx, T> {
237        match self {
238            BasicOpKind::Unary(op) => &op.intersect,
239            BasicOpKind::Binary(op) => &op.intersect,
240            BasicOpKind::Essa(op) => &op.intersect,
241            BasicOpKind::ControlDep(op) => &op.intersect,
242            BasicOpKind::Phi(op) => &op.intersect,
243            BasicOpKind::Use(op) => &op.intersect,
244            BasicOpKind::Call(op) => &op.intersect,
245            BasicOpKind::Ref(op) => &op.intersect,
246            BasicOpKind::Aggregate(op) => &op.intersect,
247        }
248    }
249    pub fn op_fix_intersects(&mut self, v: &VarNode<'tcx, T>, sink: &VarNode<'tcx, T>) {
250        let intersect = self.get_intersect_mut();
251
252        if let IntervalType::Symb(symbi) = intersect {
253            let range = symbi.sym_fix_intersects(v, sink);
254            rap_trace!(
255                "from {:?} to {:?} fix_intersects: {:} -> {:?}\n",
256                v.get_value().clone(),
257                sink.get_value().clone(),
258                intersect.clone(),
259                range
260            );
261            self.set_intersect(range);
262        }
263    }
264    pub fn set_sink(&mut self, new_sink: &'tcx Place<'tcx>) {
265        match self {
266            BasicOpKind::Unary(op) => op.sink = new_sink,
267            BasicOpKind::Binary(op) => op.sink = new_sink,
268            BasicOpKind::Essa(op) => op.sink = new_sink,
269            BasicOpKind::ControlDep(op) => op.sink = new_sink,
270            BasicOpKind::Phi(op) => op.sink = new_sink,
271            BasicOpKind::Use(op) => op.sink = new_sink,
272            BasicOpKind::Call(op) => op.sink = new_sink,
273            BasicOpKind::Ref(op) => op.sink = new_sink,
274            BasicOpKind::Aggregate(op) => op.sink = new_sink,
275        }
276    }
277    pub fn set_intersect(&mut self, new_intersect: Range<T>) {
278        match self {
279            BasicOpKind::Unary(op) => op.intersect.set_range(new_intersect),
280            BasicOpKind::Binary(op) => op.intersect.set_range(new_intersect),
281            BasicOpKind::Essa(op) => op.intersect.set_range(new_intersect),
282            BasicOpKind::ControlDep(op) => op.intersect.set_range(new_intersect),
283            BasicOpKind::Phi(op) => op.intersect.set_range(new_intersect),
284            BasicOpKind::Use(op) => op.intersect.set_range(new_intersect),
285            BasicOpKind::Call(op) => op.intersect.set_range(new_intersect),
286            BasicOpKind::Ref(op) => op.intersect.set_range(new_intersect),
287            BasicOpKind::Aggregate(op) => op.intersect.set_range(new_intersect),
288        }
289    }
290    pub fn get_intersect_mut(&mut self) -> &mut IntervalType<'tcx, T> {
291        match self {
292            BasicOpKind::Unary(op) => &mut op.intersect,
293            BasicOpKind::Binary(op) => &mut op.intersect,
294            BasicOpKind::Essa(op) => &mut op.intersect,
295            BasicOpKind::ControlDep(op) => &mut op.intersect,
296            BasicOpKind::Phi(op) => &mut op.intersect,
297            BasicOpKind::Use(op) => &mut op.intersect,
298            BasicOpKind::Call(op) => &mut op.intersect,
299            BasicOpKind::Ref(op) => &mut op.intersect,
300            BasicOpKind::Aggregate(op) => &mut op.intersect,
301        }
302    }
303    pub fn get_sources(&self) -> Vec<&'tcx Place<'tcx>> {
304        match self {
305            BasicOpKind::Unary(op) => vec![op.source],
306            BasicOpKind::Binary(op) => {
307                let mut sources = Vec::new();
308
309                if let Some(src1) = op.source1 {
310                    sources.push(src1);
311                }
312
313                if let Some(src2) = op.source2 {
314                    sources.push(src2);
315                }
316
317                sources
318            }
319            BasicOpKind::Essa(op) => vec![op.source],
320            BasicOpKind::ControlDep(op) => vec![op.source],
321            BasicOpKind::Phi(op) => op.sources.clone(),
322            BasicOpKind::Use(op) => {
323                let mut sources = Vec::new();
324
325                if let Some(src1) = op.source {
326                    sources.push(src1);
327                }
328
329                sources
330            }
331            BasicOpKind::Call(op) => op.sources.clone(),
332            BasicOpKind::Ref(op) => vec![op.source],
333            BasicOpKind::Aggregate(_) => vec![],
334        }
335    }
336}
337#[derive(Debug, Clone)]
338pub struct CallOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
339    pub intersect: IntervalType<'tcx, T>,
340    pub sink: &'tcx Place<'tcx>,
341    pub inst: &'tcx Terminator<'tcx>,
342    pub args: Vec<Operand<'tcx>>,
343    pub def_id: DefId,
344    pub fun_path: String,
345    pub sources: Vec<&'tcx Place<'tcx>>,
346}
347
348impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> CallOp<'tcx, T> {
349    pub fn convert_const(c: &Const) -> Option<T> {
350        T::from_const(c)
351    }
352    pub fn new(
353        intersect: IntervalType<'tcx, T>,
354        sink: &'tcx Place<'tcx>,
355        inst: &'tcx Terminator<'tcx>,
356        args: Vec<Operand<'tcx>>,
357        def_id: DefId,
358        fun_path: String,
359        sources: Vec<&'tcx Place<'tcx>>,
360    ) -> Self {
361        Self {
362            intersect,
363            sink,
364            inst,
365            args,
366            sources,
367            def_id,
368            fun_path,
369        }
370    }
371
372    pub fn eval(&self, caller_vars: &VarNodes<'tcx, T>) -> Range<T> {
373        return Range::default(T::min_value());
374    }
375    pub fn eval_call(
376        &self,
377        caller_vars: &VarNodes<'tcx, T>,
378        cg_map: &FxHashMap<DefId, Rc<RefCell<ConstraintGraph<'tcx, T>>>>,
379        vars_map: &mut FxHashMap<DefId, Vec<RefCell<VarNodes<'tcx, T>>>>,
380    ) -> Range<T> {
381        match self.fun_path.as_str() {
382            "std::iter::IntoIterator::into_iter" => match self.args.first() {
383                Some(Operand::Copy(place)) | Some(Operand::Move(place)) => {
384                    rap_trace!(
385                        "Iterator detected on place {:?}, returning its range",
386                        place
387                    );
388                    if let Some(var_node) = caller_vars.get(place) {
389                        let range = var_node.get_range().clone();
390                        rap_trace!(
391                            "Iterator detected on place {:?}, returning its range: {:?}",
392                            place,
393                            range
394                        );
395                        return range;
396                    }
397                }
398                _ => {}
399            },
400            "std::iter::Iterator::next" => match self.args.first() {
401                Some(Operand::Copy(place)) | Some(Operand::Move(place)) => {
402                    rap_trace!(
403                        "Iterator next detected on place {:?}, returning its range",
404                        place
405                    );
406                    if let Some(var_node) = caller_vars.get(place) {
407                        let range = var_node.get_range().clone();
408                        rap_trace!(
409                            "Iterator next detected on place {:?}, returning its range: {:?}",
410                            place,
411                            range
412                        );
413                        return range;
414                    }
415                }
416                _ => {}
417            },
418            "core::slice::<impl [T]>::len" => {
419                let mut result = Range::default(T::min_value());
420                match self.args.last() {
421                    Some(Operand::Copy(place)) | Some(Operand::Move(place)) => {
422                        let range = caller_vars[place].get_range().clone();
423                        let len = range.get_upper().clone() - range.get_lower().clone();
424                        result = Range::new(len.clone(), len.clone(), RangeType::Regular);
425                    }
426                    Some(Operand::Constant(c)) => {}
427                    None => {}
428                    #[cfg(rapx_rustc_ge_196)]
429                    _ => {}
430                }
431                rap_trace!(
432                    "len() detected on place {:?}, returning its range: {:?}",
433                    self.sink,
434                    result
435                );
436                return result;
437            }
438            "std::ops::IndexMut::index_mut" => {
439                let mut result = Range::default(T::min_value());
440
441                match self.args.last() {
442                    Some(Operand::Copy(place)) | Some(Operand::Move(place)) => {
443                        result = caller_vars[place].get_range().clone();
444                    }
445                    Some(Operand::Constant(c)) => {}
446                    None => {}
447                    #[cfg(rapx_rustc_ge_196)]
448                    _ => {}
449                }
450
451                rap_trace!(
452                    "IndexMut detected on place {:?}, returning its range: {:?}",
453                    self.sink,
454                    result
455                );
456                return result;
457            }
458            "std::ops::Index::index" => {
459                let mut result = Range::default(T::min_value());
460
461                match self.args.last() {
462                    Some(Operand::Copy(place)) | Some(Operand::Move(place)) => {
463                        result = caller_vars[place].get_range().clone();
464                    }
465                    Some(Operand::Constant(c)) => {}
466                    None => {}
467                    #[cfg(rapx_rustc_ge_196)]
468                    _ => {}
469                }
470
471                rap_trace!(
472                    "Index detected on place {:?}, returning its range: {:?}",
473                    self.sink,
474                    result
475                );
476                return result;
477            }
478            "core::panicking::panic" | "std::panicking::panic" => {
479                rap_trace!("Panic call detected, returning bottom range.");
480                return Range::new(T::max_value(), T::min_value(), RangeType::Empty);
481            }
482            _ => {}
483        }
484        // 1. Find the callee's ConstraintGraph in the map.
485        if let Some(rc_callee_cg_cell) = cg_map.get(&self.def_id) {
486            rap_debug!(
487                "Evaluating call to {:?} with args {:?}",
488                self.def_id,
489                self.args
490            );
491            // 2. Try to get a mutable borrow of the callee's graph.
492            //    Using `try_borrow_mut` is safer than `borrow_mut` to avoid panicking on recursive calls.
493            if let Ok(mut callee_cg) = rc_callee_cg_cell.try_borrow_mut() {
494                // 3. Pass arguments from caller to callee.
495                //    This assumes arguments are in order and `_1`, `_2`, ... in the callee MIR.
496                for (i, caller_arg_operand) in self.args.iter().enumerate() {
497                    rap_debug!(
498                        "Processing argument {}: {:?} to callee {:?}",
499                        i,
500                        caller_arg_operand,
501                        self.def_id
502                    );
503                    match caller_arg_operand {
504                        Operand::Copy(caller_arg_place) | Operand::Move(caller_arg_place) => {
505                            // Add the variable node for the caller's argument.
506                            // Callee arguments are typically `_1`, `_2`, ...
507                            let callee_arg_local = rustc_middle::mir::Local::from_usize(i + 1);
508
509                            // Find the corresponding Place and VarNode in the callee.
510                            if let Some(callee_arg_node) = callee_cg.vars.values_mut().find(|v| {
511                                v.v.local == callee_arg_local && v.v.projection.is_empty()
512                            }) {
513                                // Get the range from the caller's variable and set it for the callee's argument.
514                                if let Some(caller_arg_node) = caller_vars.get(&caller_arg_place) {
515                                    let arg_range = caller_arg_node.get_range().clone();
516                                    callee_arg_node.set_range(arg_range);
517                                    rap_debug!(
518                                        "Passing argument from {:?} to callee {:?} : {:?} {:?} -> {:?}",
519                                        caller_arg_place,
520                                        self.def_id,
521                                        callee_arg_node.get_value(),
522                                        caller_arg_node.get_range(),
523                                        callee_arg_node.get_range()
524                                    );
525                                }
526                            }
527                        }
528                        Operand::Constant(const_operand) => {
529                            rap_debug!(
530                                "constant argument {:?} to callee {:?}",
531                                const_operand,
532                                self.def_id
533                            );
534                            let callee_arg_local = rustc_middle::mir::Local::from_usize(i + 1);
535                            if let Some(const_value) = Self::convert_const(&const_operand.const_) {
536                                if let Some(callee_arg_node) =
537                                    callee_cg.vars.values_mut().find(|v| {
538                                        v.v.local == callee_arg_local && v.v.projection.is_empty()
539                                    })
540                                {
541                                    // Get the range from the caller's variable and set it for the callee's argument.
542
543                                    let arg_range = Range::new(
544                                        const_value.clone(),
545                                        const_value.clone(),
546                                        RangeType::Regular,
547                                    );
548                                    callee_arg_node.set_range(arg_range.clone());
549                                    rap_debug!(
550                                        "Passing argument from {:?} to callee {:?} : {:?} {:?} -> {:?}",
551                                        const_value,
552                                        self.def_id,
553                                        callee_arg_node.get_value(),
554                                        arg_range,
555                                        callee_arg_node.get_range()
556                                    );
557                                }
558                            }
559                            // Find the corresponding Place and VarNode in the callee.
560                        }
561                        #[cfg(rapx_rustc_ge_196)]
562                        Operand::RuntimeChecks(_) => {}
563                    }
564                }
565
566                // 4. Run analysis on the callee.
567                //    NOTE: This is a simplification. A full implementation would use memoization
568                //    or a bottom-up analysis order to avoid re-analyzing functions repeatedly.
569                //    For now, we re-run it to ensure argument values are propagated.
570                callee_cg.find_intervals(cg_map, vars_map);
571
572                // 5. Retrieve the return value.
573                //    The return value is stored in `_0` (RETURN_PLACE).
574                let return_place_local = 0 as usize; // `_0` is typically the first local.
575                let mut return_range = Range::default(T::min_value());
576
577                // Find all variables that contribute to the return value.
578                // The `rerurn_places` set in the callee's graph tracks these.
579                if let Some(return_node) = callee_cg.vars.get_mut(&Place::return_place()) {
580                    return_range = return_node.get_range().clone();
581                    rap_debug!(" final return range {:?} ", return_range);
582                    return return_range;
583                }
584                let Some(callee_varnodes_vec) = vars_map.get_mut(&self.def_id) else {
585                    panic!(
586                        "No variable map entry for this function {:?}, skipping Nuutila\n",
587                        self.def_id
588                    );
589                };
590                callee_cg.reset_vars(callee_varnodes_vec);
591            } else {
592                // Recursive call detected or graph is already borrowed.
593                // Conservatively return a full range.
594                rap_trace!(
595                    "Recursive call or existing borrow for {:?}, returning top.",
596                    self.def_id
597                );
598                return Range::new(T::min_value(), T::max_value(), RangeType::Regular);
599            }
600        }
601
602        // Callee not found (e.g., external library function, function pointer).
603        // Return a conservative full range.
604        rap_trace!(
605            "Callee ConstraintGraph for {:?} not found, returning top.",
606            self.def_id
607        );
608        Range::new(T::min_value(), T::max_value(), RangeType::Regular)
609    }
610}
611#[derive(Debug, Clone)]
612pub enum AggregateOperand<'tcx> {
613    Place(&'tcx Place<'tcx>),
614    Const(Const<'tcx>),
615}
616#[derive(Debug, Clone)]
617
618pub struct AggregateOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
619    pub intersect: IntervalType<'tcx, T>,
620    pub sink: &'tcx Place<'tcx>,
621    pub inst: &'tcx Statement<'tcx>,
622    pub operands: Vec<AggregateOperand<'tcx>>,
623    pub unique_adt: usize,
624}
625
626impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> AggregateOp<'tcx, T> {
627    pub fn new(
628        intersect: IntervalType<'tcx, T>,
629        sink: &'tcx Place<'tcx>,
630        inst: &'tcx Statement<'tcx>,
631        operands: Vec<AggregateOperand<'tcx>>,
632        unique_adt: usize,
633    ) -> Self {
634        Self {
635            intersect,
636            sink,
637            inst,
638            operands,
639            unique_adt,
640        }
641    }
642
643    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
644        if self.operands.is_empty() {
645            return self.intersect.get_range().clone();
646        }
647
648        let mut result: Range<T> = Range::default(T::min_value());
649        match self.unique_adt {
650            0 => {
651                // If unique_adt is 0, we assume it's a regular array or slice.
652                // We can use the first operand's range as the initial result.
653                match self.operands.first() {
654                    Some(AggregateOperand::Place(place)) => {
655                        let range = vars[*place].get_range().clone();
656                        result = range;
657                    }
658                    Some(AggregateOperand::Const(c)) => {
659                        result = Range::new(
660                            T::from_const(c).unwrap_or(T::min_value()),
661                            T::from_const(c).unwrap_or(T::max_value()),
662                            RangeType::Regular,
663                        );
664                    }
665                    None => {}
666                }
667            }
668            1 => {
669                // If unique_adt is 1, we assume it's a Range with two operands.
670                let mut lower = T::min_value();
671                let mut upper = T::max_value();
672                match self.operands.first() {
673                    Some(AggregateOperand::Place(place)) => {
674                        lower = vars[*place].get_range().get_lower().clone();
675                    }
676                    Some(AggregateOperand::Const(c)) => {
677                        lower = T::from_const(c).unwrap_or(T::min_value());
678                    }
679                    None => {}
680                }
681                match self.operands.last() {
682                    Some(AggregateOperand::Place(place)) => {
683                        upper = vars[*place].get_range().get_upper().clone();
684                    }
685                    Some(AggregateOperand::Const(c)) => {
686                        upper = T::from_const(c).unwrap_or(T::max_value());
687                    }
688                    None => {}
689                }
690
691                result = Range::new(lower, upper, RangeType::Regular);
692            }
693            _ => {}
694        }
695        result
696    }
697}
698
699#[derive(Debug, Clone)]
700pub struct UseOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
701    pub intersect: IntervalType<'tcx, T>,
702    pub sink: &'tcx Place<'tcx>,
703    pub inst: &'tcx Statement<'tcx>,
704    pub source: Option<&'tcx Place<'tcx>>,
705    pub const_value: Option<Const<'tcx>>,
706}
707
708impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> UseOp<'tcx, T> {
709    pub fn new(
710        intersect: IntervalType<'tcx, T>,
711        sink: &'tcx Place<'tcx>,
712        inst: &'tcx Statement<'tcx>,
713        source: Option<&'tcx Place<'tcx>>,
714        const_value: Option<Const<'tcx>>,
715    ) -> Self {
716        Self {
717            intersect,
718            sink,
719            inst,
720            source,
721            const_value,
722        }
723    }
724
725    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
726        if let Some(source) = self.source {
727            let range = vars[source].get_range().clone();
728            let mut result = Range::default(T::min_value());
729            if range.is_regular() {
730                result = range
731            } else {
732            }
733            result
734        } else {
735            // If no source is provided, return the intersect range
736            self.intersect.get_range().clone()
737        }
738    }
739}
740#[derive(Debug, Clone)]
741pub struct UnaryOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
742    pub intersect: IntervalType<'tcx, T>,
743    pub sink: &'tcx Place<'tcx>,
744    pub inst: &'tcx Statement<'tcx>,
745    pub source: &'tcx Place<'tcx>,
746    pub op: UnOp,
747}
748
749impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> UnaryOp<'tcx, T> {
750    pub fn new(
751        intersect: IntervalType<'tcx, T>,
752        sink: &'tcx Place<'tcx>,
753        inst: &'tcx Statement<'tcx>,
754        source: &'tcx Place<'tcx>,
755        op: UnOp,
756    ) -> Self {
757        Self {
758            intersect,
759            sink,
760            inst,
761            source,
762            op,
763        }
764    }
765
766    pub fn eval(&self) -> Range<T> {
767        Range::default(T::min_value())
768    }
769}
770#[derive(Debug, Clone)]
771
772pub struct EssaOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
773    pub intersect: IntervalType<'tcx, T>,
774    pub sink: &'tcx Place<'tcx>,
775    pub inst: &'tcx Statement<'tcx>,
776    pub source: &'tcx Place<'tcx>,
777    pub opcode: u32,
778    pub unresolved: bool,
779}
780
781impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> EssaOp<'tcx, T> {
782    pub fn new(
783        intersect: IntervalType<'tcx, T>,
784        sink: &'tcx Place<'tcx>,
785        inst: &'tcx Statement<'tcx>,
786        source: &'tcx Place<'tcx>,
787        opcode: u32,
788        unresolved: bool,
789    ) -> Self {
790        Self {
791            intersect,
792            sink,
793            inst,
794            source,
795            opcode,
796            unresolved,
797        }
798    }
799
800    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
801        let source_range = vars[self.source].get_range().clone();
802        let result = source_range.intersectwith(self.intersect.get_range());
803        rap_trace!(
804            "EssaOp eval: {:?} {:?} intersectwith {:?} -> {:?}\n",
805            self.source,
806            self.intersect.get_range(),
807            source_range,
808            result
809        );
810        result
811    }
812    pub fn get_source(&self) -> &'tcx Place<'tcx> {
813        self.source
814    }
815    pub fn get_instruction(&self) -> &'tcx Statement<'tcx> {
816        self.inst
817    }
818    pub fn get_sink(&self) -> &'tcx Place<'tcx> {
819        self.sink
820    }
821    pub fn is_unresolved(&self) -> bool {
822        self.unresolved
823    }
824
825    pub fn mark_resolved(&mut self) {
826        self.unresolved = false;
827    }
828
829    pub fn mark_unresolved(&mut self) {
830        self.unresolved = true;
831    }
832    pub fn get_intersect(&self) -> &IntervalType<'tcx, T> {
833        &self.intersect
834    }
835}
836#[derive(Debug, Clone)]
837pub struct BinaryOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
838    pub intersect: IntervalType<'tcx, T>,
839    pub sink: &'tcx Place<'tcx>,
840    pub inst: &'tcx Statement<'tcx>,
841    pub source1: Option<&'tcx Place<'tcx>>,
842    pub source2: Option<&'tcx Place<'tcx>>,
843    pub const_value: Option<Const<'tcx>>,
844    pub op: BinOp,
845}
846
847impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> BinaryOp<'tcx, T> {
848    pub fn convert_const(c: &Const) -> Option<T> {
849        T::from_const(c)
850    }
851    pub fn new(
852        intersect: IntervalType<'tcx, T>,
853        sink: &'tcx Place<'tcx>,
854        inst: &'tcx Statement<'tcx>,
855        source1: Option<&'tcx Place<'tcx>>,
856        source2: Option<&'tcx Place<'tcx>>,
857        const_value: Option<Const<'tcx>>,
858
859        op: BinOp,
860    ) -> Self {
861        Self {
862            intersect,
863            sink,
864            inst,
865            source1,
866            source2,
867            const_value, // Default value, can be set later
868            op,
869        }
870    }
871
872    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
873        let op1 = vars[self.source1.unwrap()].get_range().clone();
874        let mut op2 = Range::default(T::min_value());
875        if let Some(const_value) = &self.const_value {
876            // If const_value is provided, use it as the second operand
877            let value = Self::convert_const(const_value).unwrap();
878            op2 = Range::new(value, value, RangeType::Regular);
879        } else {
880            op2 = vars[self.source2.unwrap()].get_range().clone();
881        }
882        let mut result = Range::default(T::min_value());
883        match &self.inst.kind {
884            StatementKind::Assign(assign) => {
885                let (place, rvalue) = &**assign;
886                match rvalue {
887                    Rvalue::BinaryOp(binop, _) => match binop {
888                        BinOp::Add | BinOp::AddUnchecked | BinOp::AddWithOverflow => {
889                            result = op1.add(&op2);
890                        }
891
892                        BinOp::SubUnchecked | BinOp::SubWithOverflow | BinOp::Sub => {
893                            result = op1.sub(&op2);
894                        }
895
896                        BinOp::MulUnchecked | BinOp::MulWithOverflow | BinOp::Mul => {
897                            result = op1.mul(&op2);
898                        }
899
900                        _ => {}
901                    },
902                    _ => {}
903                }
904            }
905            _ => {}
906        }
907
908        result
909    }
910}
911#[derive(Debug, Clone)]
912
913pub struct PhiOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
914    pub intersect: IntervalType<'tcx, T>,
915    pub sink: &'tcx Place<'tcx>,
916    pub inst: &'tcx Statement<'tcx>,
917    pub sources: Vec<&'tcx Place<'tcx>>,
918    pub opcode: u32,
919}
920
921impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> PhiOp<'tcx, T> {
922    pub fn new(
923        intersect: IntervalType<'tcx, T>,
924        sink: &'tcx Place<'tcx>,
925        inst: &'tcx Statement<'tcx>,
926        opcode: u32,
927    ) -> Self {
928        Self {
929            intersect,
930            sink,
931            inst,
932            sources: vec![],
933            opcode,
934        }
935    }
936
937    pub fn add_source(&mut self, src: &'tcx Place<'tcx>) {
938        self.sources.push(src);
939    }
940    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
941        let first = self.sources[0];
942        let mut result = vars[first].get_range().clone();
943        for &phisource in self.sources.iter() {
944            let node = &vars[phisource];
945            result = result.unionwith(node.get_range());
946            rap_trace!(
947                "PhiOp eval:  {:?} unionwith {:?} -> {:?}\n",
948                vars[first].get_range().clone(),
949                node.get_range(),
950                result
951            );
952        }
953        result
954    }
955    pub fn get_sources(&self) -> &[&'tcx Place<'tcx>] {
956        &self.sources
957    }
958}
959#[derive(Debug, Clone)]
960pub struct RefOp<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
961    pub intersect: IntervalType<'tcx, T>,
962    pub sink: &'tcx Place<'tcx>,
963    pub inst: &'tcx Statement<'tcx>,
964    pub source: &'tcx Place<'tcx>,
965    pub borrowkind: BorrowKind,
966}
967impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> RefOp<'tcx, T> {
968    pub fn new(
969        intersect: IntervalType<'tcx, T>,
970        sink: &'tcx Place<'tcx>,
971        inst: &'tcx Statement<'tcx>,
972        source: &'tcx Place<'tcx>,
973        borrowkind: BorrowKind,
974    ) -> Self {
975        Self {
976            intersect,
977            sink,
978            inst,
979            source,
980            borrowkind,
981        }
982    }
983
984    pub fn eval(&self, vars: &VarNodes<'tcx, T>) -> Range<T> {
985        let var_node = vars.get(self.source);
986        rap_trace!("RefOp eval: searching for {:?}\n", var_node);
987        if let Some(var_node) = var_node {
988            let range = var_node.get_range().clone();
989
990            rap_trace!(
991                "RefOp eval: {:?} {:?} intersectwith {:?}\n",
992                self.source,
993                self.intersect.get_range(),
994                range
995            );
996
997            range
998        } else {
999            rap_trace!(
1000                "RefOp eval: {:?} not found, returning intersect {:?}\n",
1001                self.source,
1002                self.intersect.get_range()
1003            );
1004            self.intersect.get_range().clone()
1005        }
1006    }
1007}
1008#[derive(Debug, Clone)]
1009
1010pub struct ControlDep<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
1011    pub intersect: IntervalType<'tcx, T>,
1012    pub sink: &'tcx Place<'tcx>,
1013    pub inst: &'tcx Statement<'tcx>,
1014    pub source: &'tcx Place<'tcx>,
1015}
1016
1017impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> ControlDep<'tcx, T> {
1018    pub fn new(
1019        intersect: IntervalType<'tcx, T>,
1020        sink: &'tcx Place<'tcx>,
1021        inst: &'tcx Statement<'tcx>,
1022        source: &'tcx Place<'tcx>,
1023    ) -> Self {
1024        Self {
1025            intersect,
1026            sink,
1027            inst,
1028            source,
1029        }
1030    }
1031
1032    pub fn eval(&self) -> Range<T> {
1033        Range::default(T::min_value())
1034    }
1035}
1036
1037#[derive(Debug, Clone)]
1038pub struct VarNode<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
1039    // The program variable which is represented.
1040    pub v: &'tcx Place<'tcx>,
1041    // A Range associated to the variable.
1042    pub interval: IntervalType<'tcx, T>,
1043    // Used by the crop meet operator.
1044    pub abstract_state: char,
1045}
1046impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> VarNode<'tcx, T> {
1047    pub fn new(v: &'tcx Place<'tcx>) -> Self {
1048        Self {
1049            v,
1050            interval: IntervalType::Basic(BasicInterval::new(Range::default(T::min_value()))),
1051            abstract_state: '?',
1052        }
1053    }
1054    pub fn new_symb(v: &'tcx Place<'tcx>, symb_expr: SymbExpr<'tcx>) -> Self {
1055        Self {
1056            v,
1057            interval: IntervalType::Basic(BasicInterval::new_symb(
1058                Range::default(T::min_value()),
1059                symb_expr.clone(),
1060                symb_expr.clone(),
1061            )),
1062            abstract_state: '?',
1063        }
1064    }
1065    pub fn get_range(&self) -> &Range<T> {
1066        self.interval.get_range()
1067    }
1068
1069    pub fn set_range(&mut self, new_interval: Range<T>) {
1070        self.interval.set_range(new_interval);
1071    }
1072
1073    pub fn set_interval(&mut self, new_interval: IntervalType<'tcx, T>) {
1074        self.interval = new_interval;
1075    }
1076
1077    pub fn get_interval(&self) -> &IntervalType<'tcx, T> {
1078        &self.interval
1079    }
1080
1081    pub fn set_default(&mut self) {
1082        let mut range = Range::default(T::min_value());
1083        range.set_default();
1084        self.interval.set_range(range);
1085    }
1086    pub fn get_value(&self) -> &'tcx Place<'tcx> {
1087        self.v
1088    }
1089    pub fn init(&mut self, outside: bool) {
1090        let value = self.get_value();
1091    }
1092}
1093
1094#[derive(Debug, Clone)]
1095pub struct ValueBranchMap<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
1096    v: &'tcx Place<'tcx>,         // The value associated with the branch
1097    bb_true: &'tcx BasicBlock,    // True side of the branch
1098    bb_false: &'tcx BasicBlock,   // False side of the branch
1099    itv_t: IntervalType<'tcx, T>, // Interval for the true side
1100    itv_f: IntervalType<'tcx, T>,
1101}
1102impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> ValueBranchMap<'tcx, T> {
1103    pub fn new(
1104        v: &'tcx Place<'tcx>,
1105        bb_false: &'tcx BasicBlock,
1106        bb_true: &'tcx BasicBlock,
1107        itv_f: IntervalType<'tcx, T>,
1108        itv_t: IntervalType<'tcx, T>,
1109    ) -> Self {
1110        Self {
1111            v,
1112            bb_false,
1113            bb_true,
1114            itv_f,
1115            itv_t,
1116        }
1117    }
1118
1119    /// Get the "false side" of the branch
1120    pub fn get_bb_false(&self) -> &BasicBlock {
1121        self.bb_false
1122    }
1123
1124    /// Get the "true side" of the branch
1125    pub fn get_bb_true(&self) -> &BasicBlock {
1126        self.bb_true
1127    }
1128
1129    /// Get the interval associated with the true side of the branch
1130    pub fn get_itv_t(&self) -> IntervalType<'tcx, T> {
1131        self.itv_t.clone()
1132    }
1133
1134    /// Get the interval associated with the false side of the branch
1135    pub fn get_itv_f(&self) -> IntervalType<'tcx, T> {
1136        self.itv_f.clone()
1137    }
1138
1139    /// Get the value associated with the branch
1140    pub fn get_v(&self) -> &'tcx Place<'tcx> {
1141        self.v
1142    }
1143
1144    // pub fn set_itv_t(&mut self, itv: &IntervalType<'tcx, T>) {
1145    //     self.itv_t = itv;
1146    // }
1147
1148    // /// Change the interval associated with the false side of the branch
1149    // pub fn set_itv_f(&mut self, itv: &IntervalType<'tcx, T>) {
1150    //     self.itv_f = itv;
1151    // }
1152
1153    // pub fn clear(&mut self) {
1154    //     self.itv_t = Box::new(EmptyInterval::new());
1155    //     self.itv_f = Box::new(EmptyInterval::new());
1156    // }
1157}
1158
1159pub type VarNodes<'tcx, T> = HashMap<&'tcx Place<'tcx>, VarNode<'tcx, T>>;
1160pub type GenOprs<'tcx, T> = Vec<BasicOpKind<'tcx, T>>;
1161pub type UseMap<'tcx> = HashMap<&'tcx Place<'tcx>, HashSet<usize>>;
1162pub type SymbMap<'tcx> = HashMap<&'tcx Place<'tcx>, HashSet<usize>>;
1163pub type DefMap<'tcx> = HashMap<&'tcx Place<'tcx>, usize>;
1164pub type ValuesBranchMap<'tcx, T> = HashMap<&'tcx Place<'tcx>, ValueBranchMap<'tcx, T>>;
rapx/analysis/range_analysis/domain/domain.rs

rapx/analysis/range_analysis/domain/
domain.rs
