rapx/analysis/core/range_analysis/domain/
range.rs1#![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;
11use 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}
85impl<T> Range<T>
124where
125 T: IntervalArithmetic,
126{
127 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 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 pub fn get_upper(&self) -> T {
157 self.range.right.0.clone()
158 }
159
160 pub fn set_lower(&mut self, newl: T) {
162 self.range.left.0 = newl;
163 }
164
165 pub fn set_upper(&mut self, newu: T) {
167 self.range.right.0 = newu;
168 }
169
170 pub fn is_unknown(&self) -> bool {
172 self.rtype == RangeType::Unknown
173 }
174
175 pub fn set_unknown(&mut self) {
177 self.rtype = RangeType::Unknown;
178 }
179
180 pub fn is_regular(&self) -> bool {
182 self.rtype == RangeType::Regular
183 }
184
185 pub fn set_regular(&mut self) {
187 self.rtype = RangeType::Regular;
188 }
189
190 pub fn is_empty(&self) -> bool {
192 self.rtype == RangeType::Empty
193 }
194
195 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 }
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 }
328
329pub 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 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 = 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 = 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 = 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 }
451
452 has_changed
453 }
454}