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

rapx/analysis/core/range_analysis/
mod.rs
