numeric-domains 0.1.0

Abstract domains for fixed-width numeric values
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

use numeric_domains::{BitRange, RangeSet, Tnum, WrappedInterval};
use proptest::prelude::*;

#[test]
fn wrapped_interval_keeps_overflow_result_compact() {
    let near_max = WrappedInterval::new(u64::MAX - 2, u64::MAX);
    let result = near_max + WrappedInterval::from_value(2);

    assert_eq!(result.bounds(), Some((u64::MAX, 1)));
    assert!(result.is_wrapping());
    assert_eq!(result.cardinality(), 3);
    assert!(result.contains_value(u64::MAX));
    assert!(result.contains_value(0));
    assert!(result.contains_value(1));
    assert!(!result.contains_value(2));
}

#[test]
fn two_ranges_preserve_a_branch_disjunction() {
    let values = RangeSet::<2>::from_range(10, 15).union(RangeSet::from_range(20, 30));

    assert_eq!(values.ranges(), &[(10, 15), (20, 30)]);
    assert!(!values.contains_value(17));
    assert_eq!(values.cardinality(), 17);
}

#[test]
fn capacity_fills_the_smallest_gap_first() {
    let values = RangeSet::<2>::from_value(0)
        .union(RangeSet::from_value(10))
        .union(RangeSet::from_value(12));

    assert_eq!(values.ranges(), &[(0, 0), (10, 12)]);
    assert!(!values.contains_value(5));
}

#[test]
fn range_set_addition_preserves_wrapping_as_two_pieces() {
    let result = RangeSet::<2>::from_range(u64::MAX - 2, u64::MAX) + RangeSet::from_value(2);

    assert_eq!(result.ranges(), &[(0, 1), (u64::MAX, u64::MAX)]);
    assert_eq!(result.cardinality(), 3);
}

#[test]
fn reduced_product_is_stricter_than_either_component() {
    let value = BitRange::<2>::new(
        RangeSet::from_range(8, 11),
        Tnum::from_parts(0, u64::MAX - 1),
    );

    assert!(value.contains_value(8));
    assert!(!value.contains_value(9));
    assert!(value.contains_value(10));
    assert!(!value.contains_value(11));
}

#[test]
fn reduction_moves_common_prefix_bits_out_of_ranges() {
    let value = BitRange::<2>::from_ranges(RangeSet::from_range(0x1200, 0x12ff));
    let (known, unknown) = value.bits().parts().unwrap();

    assert_eq!(known, 0x1200);
    assert_eq!(unknown, 0xff);
}

#[test]
fn incompatible_components_reduce_to_empty() {
    let value = BitRange::<2>::new(RangeSet::from_range(0, 7), Tnum::from_parts(8, 0));
    assert!(value.is_empty());
}

#[test]
fn reduced_product_detects_disjoint_holey_components() {
    let ranges = RangeSet::<2>::from_range(1, 3).union(RangeSet::from_range(5, 7));
    let value = BitRange::new(ranges, Tnum::from_parts(0, 4));

    assert!(!value.contains_value(0));
    assert!(!value.contains_value(4));
    assert!(value.is_empty());
}

#[test]
fn addition_preserves_cross_component_emptiness() {
    let empty = BitRange::<2>::new(RangeSet::from_range(4, 8), Tnum::from_parts(2, 9));

    assert!(empty.is_empty());
    assert!((empty + BitRange::from_value(1)).is_empty());
    assert!((BitRange::from_value(1) + empty).is_empty());
}

proptest! {
    #[test]
    fn wrapped_add_contains_concrete_results(
        a_low: u64,
        a_len in 0_u16..1024,
        b_low: u64,
        b_len in 0_u16..1024,
        ai in 0_u16..1024,
        bi in 0_u16..1024,
    ) {
        let a_len = u64::from(a_len);
        let b_len = u64::from(b_len);
        let left = WrappedInterval::new(a_low, a_low.wrapping_add(a_len));
        let right = WrappedInterval::new(b_low, b_low.wrapping_add(b_len));
        let a = a_low.wrapping_add(u64::from(ai) % (a_len + 1));
        let b = b_low.wrapping_add(u64::from(bi) % (b_len + 1));

        prop_assert!((left + right).contains_value(a.wrapping_add(b)));
    }

    #[test]
    fn range_set_add_contains_concrete_results(
        a_low: u64,
        a_len in 0_u8..64,
        b_low: u64,
        b_len in 0_u8..64,
        ai in 0_u8..64,
        bi in 0_u8..64,
    ) {
        let a_high = a_low.saturating_add(u64::from(a_len));
        let b_high = b_low.saturating_add(u64::from(b_len));
        let left = RangeSet::<2>::from_range(a_low, a_high);
        let right = RangeSet::<2>::from_range(b_low, b_high);
        let a = a_low + u64::from(ai) % (a_high - a_low + 1);
        let b = b_low + u64::from(bi) % (b_high - b_low + 1);

        prop_assert!((left + right).contains_value(a.wrapping_add(b)));
    }
}