rapx/analysis/core/range_analysis/
mod.rs

1#![allow(non_snake_case)]
2#![allow(unused_variables)]
3#![allow(dead_code)]
4pub mod default;
5pub mod domain;
6use crate::{
7    analysis::{
8        Analysis,
9        core::range_analysis::domain::domain::{ConstConvert, IntervalArithmetic},
10    },
11    utils::source::get_fn_name_byid,
12};
13use once_cell::sync::Lazy;
14// use intervals::Closed;
15use rust_intervals::Interval;
16use rustc_data_structures::fx::FxHashMap;
17use rustc_hir::def_id::DefId;
18use rustc_middle::mir::{BinOp, Place};
19
20use std;
21use std::{
22    collections::HashMap,
23    fmt::{self, Debug, Display},
24};
25pub type RAResult<'tcx, T> = HashMap<Place<'tcx>, Range<T>>;
26pub type RAResultMap<'tcx, T> = FxHashMap<DefId, HashMap<Place<'tcx>, Range<T>>>;
27pub type RAVecResultMap<'tcx, T> = FxHashMap<DefId, Vec<HashMap<Place<'tcx>, Range<T>>>>;
28
29pub type PathConstraint<'tcx> = HashMap<Vec<usize>, Vec<(Place<'tcx>, Place<'tcx>, BinOp)>>;
30pub type PathConstraintMap<'tcx> =
31    FxHashMap<DefId, HashMap<Vec<usize>, Vec<(Place<'tcx>, Place<'tcx>, BinOp)>>>;
32pub struct RAResultWrapper<'tcx, T: IntervalArithmetic>(pub RAResult<'tcx, T>);
33pub struct RAResultMapWrapper<'tcx, T: IntervalArithmetic>(pub RAResultMap<'tcx, T>);
34pub struct RAVecResultMapWrapper<'tcx, T: IntervalArithmetic>(pub RAVecResultMap<'tcx, T>);
35pub struct PathConstraintWrapper<'tcx>(pub PathConstraint<'tcx>);
36pub struct PathConstraintMapWrapper<'tcx>(pub PathConstraintMap<'tcx>);
37
38/// The core trait for performing range analysis over Rust MIR.
39///
40/// This trait provides access to both intra-procedural and inter-procedural
41/// range results inferred through static interval analysis.
42pub trait RangeAnalysis<'tcx, T: IntervalArithmetic + ConstConvert + Debug>: Analysis {
43    /// The fucntion returns the range information for all local variables (Places) in a given
44    /// function specified by `def_id`.
45    fn get_fn_range(&self, def_id: DefId) -> Option<RAResult<'tcx, T>>;
46
47    /// The function returns the range analysis results for **each call instance** of the specified function.
48    /// This is useful in interprocedural or context-sensitive analyses,
49    /// where a function might be analyzed multiple times under different calling contexts.
50    fn get_fn_ranges_percall(&self, def_id: DefId) -> Option<Vec<RAResult<'tcx, T>>>;
51
52    /// The function returns the complete mapping of range information for all functions in the crate.
53    fn get_all_fn_ranges(&self) -> RAResultMap<'tcx, T>;
54
55    /// The function returns the range results for **every call instance** of every function in the crate.
56    fn get_all_fn_ranges_percall(&self) -> RAVecResultMap<'tcx, T>;
57
58    /// The function returns the inferred range for a specific variable (Place) in a specific function.
59    fn get_fn_local_range(&self, def_id: DefId, local: Place<'tcx>) -> Option<Range<T>>;
60
61    /// The function returns a mapping from feasible control-flow paths to symbolic constraints.
62    /// Each constraint is a triple of (`Place`, `Place`, `BinOp`) representing
63    /// path-sensitive relational information useful for pruning infeasible paths.
64    fn get_fn_path_constraints(&self, def_id: DefId) -> Option<PathConstraint<'tcx>>;
65
66    /// The function returns path constraints for all functions in the crate.
67    fn get_all_path_constraints(&self) -> PathConstraintMap<'tcx>;
68}
69
70impl<'tcx, T> Display for RAResultWrapper<'tcx, T>
71where
72    Place<'tcx>: Debug,
73    T: IntervalArithmetic + Clone + PartialOrd + Display,
74{
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        for (place, range) in &self.0 {
77            writeln!(f, "{:?} => {}", place, range)?;
78        }
79        Ok(())
80    }
81}
82impl<'tcx, T> Display for RAResultMapWrapper<'tcx, T>
83where
84    DefId: Debug,
85    Place<'tcx>: Debug,
86    T: IntervalArithmetic + Clone + PartialOrd + Display,
87{
88    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
89        writeln!(f, "=== Print range analysis resuts ===")?;
90        for (def_id, ra_result) in &self.0 {
91            let fn_name = get_fn_name_byid(def_id);
92            writeln!(f, "Function: {:?} =>", fn_name)?;
93
94            let mut sorted: Vec<_> = ra_result.iter().collect();
95            sorted.sort_by_key(|(place, _)| place.local.as_usize());
96
97            for (place, range) in sorted {
98                writeln!(f, "  {:?} => {}", place, range)?;
99            }
100        }
101        Ok(())
102    }
103}
104impl<'tcx, T> Display for RAVecResultMapWrapper<'tcx, T>
105where
106    DefId: Debug,
107    Place<'tcx>: Debug,
108    T: IntervalArithmetic + Clone + PartialOrd + Display,
109{
110    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
111        writeln!(f, "=== Print range analysis resuts ===")?;
112        for (def_id, vec_of_maps) in &self.0 {
113            let fn_name = get_fn_name_byid(def_id);
114            writeln!(f, "Function: {:?} =>", fn_name)?;
115
116            for (i, map) in vec_of_maps.iter().enumerate() {
117                writeln!(f, "  Result Set #{}:", i)?;
118
119                let mut sorted: Vec<_> = map.iter().collect();
120                sorted.sort_by_key(|(place, _)| place.local.as_usize());
121
122                for (place, range) in sorted {
123                    writeln!(f, "    {:?} => {}", place, range)?;
124                }
125            }
126        }
127        Ok(())
128    }
129}
130
131impl<'tcx> Display for PathConstraintWrapper<'tcx>
132where
133    Place<'tcx>: Debug,
134    BinOp: Debug,
135{
136    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
137        for (path, constraints) in &self.0 {
138            writeln!(f, "Path {:?}:", path)?;
139            for (p1, p2, op) in constraints {
140                writeln!(f, "    Constraint:{:?} {:?} {:?}", p1, op, p2)?;
141            }
142        }
143        Ok(())
144    }
145}
146
147impl<'tcx> Display for PathConstraintMapWrapper<'tcx>
148where
149    DefId: Debug,
150    Place<'tcx>: Debug,
151    BinOp: Debug,
152{
153    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
154        writeln!(f, "=== Print paths and constraints ===")?;
155        for (def_id, pc) in &self.0 {
156            let fn_name = get_fn_name_byid(def_id);
157            writeln!(f, "Function: {:?}:", fn_name)?;
158            for (path, constraints) in pc {
159                writeln!(f, "  Path {:?}:", path)?;
160                for (p1, p2, op) in constraints {
161                    writeln!(f, "    Constraint:{:?} {:?} {:?}", p1, op, p2)?;
162                }
163            }
164        }
165        Ok(())
166    }
167}
168#[derive(Debug, PartialEq, Eq, Hash, Clone)]
169pub enum RangeType {
170    Unknown,
171    Regular,
172    Empty,
173}
174impl fmt::Display for RangeType {
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        let s = match self {
177            RangeType::Unknown => "Unknown",
178            RangeType::Regular => "Regular",
179            RangeType::Empty => "Empty",
180        };
181        write!(f, "{}", s)
182    }
183}
184#[derive(Debug, Hash, Clone, PartialEq, Eq)]
185
186pub struct Range<T>
187where
188    T: IntervalArithmetic,
189{
190    pub rtype: RangeType,
191    pub range: Interval<T>,
192}
193static STR_MIN: Lazy<String> = Lazy::new(|| "Min".to_string());
194static STR_MAX: Lazy<String> = Lazy::new(|| "Max".to_string());
195impl<T> Display for Range<T>
196where
197    T: IntervalArithmetic + std::fmt::Display,
198{
199    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
200        let lower: String = if *self.range.lower().unwrap() == T::min_value() {
201            STR_MIN.clone()
202        } else if *self.range.lower().unwrap() == T::max_value() {
203            STR_MAX.clone()
204        } else {
205            self.range.lower().unwrap().to_string()
206        };
207
208        let upper: String = if *self.range.upper().unwrap() == T::min_value() {
209            STR_MIN.clone()
210        } else if *self.range.upper().unwrap() == T::max_value() {
211            STR_MAX.clone()
212        } else {
213            self.range.upper().unwrap().to_string()
214        };
215
216        write!(f, "{:?} [{}, {}]", self.rtype, lower, upper)
217    }
218}
rapx/analysis/core/range_analysis/mod.rs

rapx/analysis/core/range_analysis/
mod.rs
