rapx/analysis/core/range_analysis/domain/
range.rs

1#![allow(unused_imports)]
2#![allow(unused_variables)]
3#![allow(dead_code)]
4#![allow(unused_assignments)]
5use std::{default, fmt};
6
7use bounds::Bound;
8use intervals::*;
9use num_traits::{Bounded, Num, Zero};
10use z3::ast::Int;
11// use std::ops::Range;
12use std::ops::{Add, Mul, Sub};
13
14use crate::rap_trace;
15
16use super::domain::*;
17use once_cell::sync::Lazy;
18
19static STR_MIN: Lazy<String> = Lazy::new(|| "Min".to_string());
20static STR_MAX: Lazy<String> = Lazy::new(|| "Max".to_string());
21#[derive(Debug, PartialEq, Eq, Hash, Clone)]
22pub enum RangeType {
23    Unknown,
24    Regular,
25    Empty,
26}
27impl fmt::Display for RangeType {
28    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
29        let s = match self {
30            RangeType::Unknown => "Unknown",
31            RangeType::Regular => "Regular",
32            RangeType::Empty => "Empty",
33        };
34        write!(f, "{}", s)
35    }
36}
37#[derive(Debug, PartialEq, Clone)]
38pub struct Range<T>
39where
40    T: PartialOrd + Clone,
41{
42    pub rtype: RangeType,
43    pub range: Closed<T>,
44}
45
46#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone)]
47enum UserType {
48    Unknown,
49    I32(i32),
50    I64(i64),
51    Usize(usize),
52    Empty,
53}
54impl<T> fmt::Display for Range<T>
55where
56    T: IntervalArithmetic,
57{
58    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59        let lower = if self.range.left.0 == T::min_value() {
60            &*STR_MIN
61        } else if self.range.left.0 == T::max_value() {
62            &*STR_MAX
63        } else {
64            return write!(
65                f,
66                "{} [{}, {}]",
67                self.rtype, self.range.left.0, self.range.right.0
68            );
69        };
70
71        let upper = if self.range.right.0 == T::min_value() {
72            &*STR_MIN
73        } else if self.range.right.0 == T::max_value() {
74            &*STR_MAX
75        } else {
76            return write!(
77                f,
78                "{} [{}, {}]",
79                self.rtype, self.range.left.0, self.range.right.0
80            );
81        };
82        write!(f, "{} [{}, {}]", self.rtype, lower, upper)
83    }
84}
85// fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
86//     let lower: &Lazy<String> = if self.range.left.0 == T::min_value() {
87//         &STR_MIN
88//     } else if self.range.left.0 == T::max_value() {
89//         &STR_MAX
90//     } else {
91//         static DUMMY: Lazy<String> = Lazy::new(|| String::new());
92//         let tmp = format!("{}", self.range.left.0);
93//         let tmp_clone = tmp.clone();
94//         let local = Lazy::new(|| tmp);
95//         return write!(
96//             f,
97//             "{} [{}, {}]",
98//             self.rtype,
99//             *local,
100//             if self.range.right.0 == T::min_value() {
101//                 &*STR_MIN
102//             } else if self.range.right.0 == T::max_value() {
103//                 &*STR_MAX
104//             } else {
105//                 return write!(f, "{} [{}, {}]", self.rtype, tmp_clone, self.range.right.0);
106//             }
107//         );
108//     };
109
110//     let upper: &Lazy<String> = if self.range.right.0 == T::min_value() {
111//         &STR_MIN
112//     } else if self.range.right.0 == T::max_value() {
113//         &STR_MAX
114//     } else {
115//         let tmp = format!("{}", self.range.right.0);
116//         let local = Lazy::new(|| tmp);
117//         return write!(f, "{} [{}, {}]", self.rtype, &**lower, *local);
118//     };
119
120//     write!(f, "{} [{}, {}]", self.rtype, &**lower, &**upper)
121// }
122
123impl<T> Range<T>
124where
125    T: IntervalArithmetic,
126{
127    // Parameterized constructor
128    pub fn new(lb: T, ub: T, rtype: RangeType) -> Self {
129        Self {
130            rtype,
131            range: Interval::new_unchecked(bounds::Closed(lb), bounds::Closed(ub)),
132        }
133    }
134    pub fn default(default: T) -> Self {
135        Self {
136            rtype: RangeType::Unknown,
137
138            range: Interval::new_unchecked(
139                bounds::Closed(T::min_value()),
140                bounds::Closed(T::max_value()),
141            ),
142        }
143    }
144    // Getter for lower bound
145    pub fn init(r: Closed<T>) -> Self {
146        Self {
147            rtype: RangeType::Regular,
148            range: r,
149        }
150    }
151    pub fn get_lower(&self) -> T {
152        self.range.left.0.clone()
153    }
154
155    // Getter for upper bound
156    pub fn get_upper(&self) -> T {
157        self.range.right.0.clone()
158    }
159
160    // Setter for lower bound
161    pub fn set_lower(&mut self, newl: T) {
162        self.range.left.0 = newl;
163    }
164
165    // Setter for upper bound
166    pub fn set_upper(&mut self, newu: T) {
167        self.range.right.0 = newu;
168    }
169
170    // Check if the range type is unknown
171    pub fn is_unknown(&self) -> bool {
172        self.rtype == RangeType::Unknown
173    }
174
175    // Set the range type to unknown
176    pub fn set_unknown(&mut self) {
177        self.rtype = RangeType::Unknown;
178    }
179
180    // Check if the range type is regular
181    pub fn is_regular(&self) -> bool {
182        self.rtype == RangeType::Regular
183    }
184
185    // Set the range type to regular
186    pub fn set_regular(&mut self) {
187        self.rtype = RangeType::Regular;
188    }
189
190    // Check if the range type is empty
191    pub fn is_empty(&self) -> bool {
192        self.rtype == RangeType::Empty
193    }
194
195    // Set the range type to empty
196    pub fn set_empty(&mut self) {
197        self.rtype = RangeType::Empty;
198    }
199    pub fn set_default(&mut self) {
200        self.rtype = RangeType::Regular;
201        self.range.left.0 = T::min_value();
202        self.range.right.0 = T::max_value();
203    }
204    pub fn add(&self, other: &Range<T>) -> Range<T> {
205        let a = self
206            .get_lower()
207            .clone()
208            .checked_add(&other.get_lower().clone())
209            .unwrap_or(T::max_value());
210
211        let b = self
212            .get_upper()
213            .clone()
214            .checked_add(&other.get_upper().clone())
215            .unwrap_or(T::max_value());
216
217        Range::new(a, b, RangeType::Regular)
218    }
219
220    pub fn sub(&self, other: &Range<T>) -> Range<T> {
221        let a = self
222            .get_lower()
223            .clone()
224            .checked_sub(&other.get_upper().clone())
225            .unwrap_or(T::min_value());
226
227        let b = self
228            .get_upper()
229            .clone()
230            .checked_sub(&other.get_lower().clone())
231            .unwrap_or(T::max_value());
232
233        Range::new(a, b, RangeType::Regular)
234    }
235
236    pub fn mul(&self, other: &Range<T>) -> Range<T> {
237        let candidates = vec![
238            self.get_lower().clone() * other.get_lower().clone(),
239            self.get_lower().clone() * other.get_upper().clone(),
240            self.get_upper().clone() * other.get_lower().clone(),
241            self.get_upper().clone() * other.get_upper().clone(),
242        ];
243        let min = candidates
244            .iter()
245            .cloned()
246            .min_by(|a, b| a.partial_cmp(b).unwrap())
247            .unwrap();
248        let max = candidates
249            .iter()
250            .cloned()
251            .max_by(|a, b| a.partial_cmp(b).unwrap())
252            .unwrap();
253        Range::new(min, max, RangeType::Regular)
254    }
255
256    pub fn intersectwith(&self, other: &Range<T>) -> Range<T> {
257        if self.is_unknown() {
258            return Range::new(
259                other.get_lower().clone(),
260                other.get_upper().clone(),
261                RangeType::Regular,
262            );
263        } else if other.is_unknown() {
264            return Range::new(
265                self.get_lower().clone(),
266                self.get_upper().clone(),
267                RangeType::Regular,
268            );
269        } else {
270            let result = self.range.clone().intersect(other.range.clone());
271
272            let range = Range::init(result.unwrap());
273            range
274            // let left = std::cmp::max_by(self.get_lower(), other.get_lower(), |a, b| {
275            //     a.partial_cmp(b).unwrap()
276            // });
277            // let right = std::cmp::min_by(self.get_upper(), other.get_upper(), |a, b| {
278            //     a.partial_cmp(b).unwrap()
279            // });
280            // if left <= right {
281            //     Range::new(left.clone(), right.clone(), RangeType::Regular)
282            // } else {
283            //     let empty = T::min_value();
284            //     Range::new(empty.clone(), empty, RangeType::Empty)
285            // }
286        }
287    }
288    pub fn unionwith(&self, other: &Range<T>) -> Range<T> {
289        if self.is_unknown() {
290            return Range::new(
291                other.get_lower().clone(),
292                other.get_upper().clone(),
293                RangeType::Regular,
294            );
295        } else if other.is_unknown() {
296            return Range::new(
297                self.get_lower().clone(),
298                self.get_upper().clone(),
299                RangeType::Regular,
300            );
301        } else {
302            let left = std::cmp::min_by(self.get_lower(), other.get_lower(), |a, b| {
303                a.partial_cmp(b).unwrap()
304            });
305            let right = std::cmp::max_by(self.get_upper(), other.get_upper(), |a, b| {
306                a.partial_cmp(b).unwrap()
307            });
308            Range::new(left.clone(), right.clone(), RangeType::Regular)
309        }
310    }
311    // Check if the range is the maximum range
312    // pub fn is_max_range(&self) -> bool {
313    //     self.range.lower() == T::min_value() && self.range.upper() == T::max_value()
314    // }
315
316    // // Print the range
317    // pub fn print(&self) {
318    //     println!("Range: [{} - {}]", self.get_lower(), self.get_upper());
319    // }
320
321    // // Arithmetic and bitwise operations (example for addition)
322    // pub fn add(&self, other: &Range<T>) -> Range<T> {
323    //     let lower = self.get_lower() + other.get_lower();
324    //     let upper = self.get_upper() + other.get_upper();
325    //     Range::with_bounds(lower, upper, RangeType::Regular)
326    // }
327}
328
329// Implement the comparison operators
330pub struct Meet;
331
332impl Meet {
333    pub fn widen<'tcx, T: IntervalArithmetic + fmt::Debug>(
334        op: &mut BasicOpKind<'tcx, T>,
335        constant_vector: &[T],
336        vars: &mut VarNodes<'tcx, T>,
337    ) -> bool {
338        // use crate::range_util::{get_first_less_from_vector, get_first_greater_from_vector};
339
340        // assert!(!constant_vector.is_empty(), "Invalid constant vector");
341
342        let old_interval = op.get_intersect().get_range().clone();
343        let new_interval = op.eval(vars);
344
345        let old_lower = old_interval.get_lower();
346        let old_upper = old_interval.get_upper();
347        let new_lower = new_interval.get_lower();
348        let new_upper = new_interval.get_upper();
349
350        // let nlconstant = get_first_less_from_vector(constant_vector, new_lower);
351        // let nuconstant = get_first_greater_from_vector(constant_vector, new_upper);
352        // let nlconstant = constant_vector
353        //     .iter()
354        //     .find(|&&c| c <= new_lower)
355        //     .cloned()
356        //     .unwrap_or(T::min_value());
357        // let nuconstant = constant_vector
358        //     .iter()
359        //     .find(|&&c| c >= new_upper)
360        //     .cloned()
361        //     .unwrap_or(T::max_value());
362        let nlconstant = new_lower.clone();
363        let nuconstant = new_upper.clone();
364        let updated = if old_interval.is_unknown() {
365            new_interval
366        } else if new_lower < old_lower && new_upper > old_upper {
367            Range::new(nlconstant, nuconstant, RangeType::Regular)
368        } else if new_lower < old_lower {
369            Range::new(nlconstant, old_upper.clone(), RangeType::Regular)
370        } else if new_upper > old_upper {
371            Range::new(old_lower.clone(), nuconstant, RangeType::Regular)
372        } else {
373            old_interval.clone()
374        };
375
376        op.set_intersect(updated.clone());
377
378        let sink = op.get_sink();
379        let new_sink_interval = op.get_intersect().get_range().clone();
380        vars.get_mut(sink)
381            .unwrap()
382            .set_range(new_sink_interval.clone());
383        rap_trace!(
384            "WIDEN::{:?}: {:?} -> {:?}",
385            sink,
386            old_interval,
387            new_sink_interval
388        );
389
390        old_interval != new_sink_interval
391    }
392    pub fn narrow<'tcx, T: IntervalArithmetic + Clone + PartialOrd + std::fmt::Debug>(
393        op: &mut BasicOpKind<'tcx, T>,
394        vars: &mut VarNodes<'tcx, T>,
395    ) -> bool {
396        let old_range = vars[op.get_sink()].get_range();
397        let o_lower = old_range.get_lower().clone();
398        let o_upper = old_range.get_upper().clone();
399
400        let new_range = op.eval(vars);
401        let n_lower = new_range.get_lower().clone();
402        let n_upper = new_range.get_upper().clone();
403
404        let mut has_changed = false;
405        let min = T::min_value();
406        let max = T::max_value();
407
408        let mut result_lower = o_lower.clone();
409        let mut result_upper = o_upper.clone();
410
411        if o_lower == min && n_lower != min {
412            result_lower = n_lower;
413            has_changed = true;
414        } else {
415            // let smin = o_lower.clone().min(n_lower.clone());
416            let smin = T::min_value();
417            if o_lower != smin {
418                result_lower = smin;
419                has_changed = true;
420            }
421        }
422
423        if o_upper == max && n_upper != max {
424            result_upper = n_upper;
425            has_changed = true;
426        } else {
427            // let smax = o_upper.clone().max(n_upper.clone());
428            let smax = T::max_value();
429            if o_upper != smax {
430                result_upper = smax;
431                has_changed = true;
432            }
433        }
434
435        if has_changed {
436            let new_sink_range = Range::new(
437                result_lower.clone(),
438                result_upper.clone(),
439                RangeType::Regular,
440            );
441            let sink_node = vars.get_mut(op.get_sink()).unwrap();
442            sink_node.set_range(new_sink_range.clone());
443
444            // println!(
445            //     "NARROW::{}: {:?} -> {:?}",
446            // ,
447            //     Range::new(o_lower, o_upper),
448            //     new_sink_range
449            // );
450        }
451
452        has_changed
453    }
454}