compiler/rustc_index/src/interval/tests.rs

   1 use super::*;
   2
   3 #[test]
   4 fn insert_collapses() {
   5     let mut set = IntervalSet::<u32>::new(10000);
   6     set.insert_range(9831..=9837);
   7     set.insert_range(43..=9830);
   8     assert_eq!(set.iter_intervals().collect::<Vec<_>>(), [43..9838]);
   9 }
  10
  11 #[test]
  12 fn contains() {
  13     let mut set = IntervalSet::new(300);
  14     set.insert(0u32);
  15     assert!(set.contains(0));
  16     set.insert_range(0..10);
  17     assert!(set.contains(9));
  18     assert!(!set.contains(10));
  19     set.insert_range(10..11);
  20     assert!(set.contains(10));
  21 }
  22
  23 #[test]
  24 fn insert() {
  25     for i in 0..30usize {
  26         let mut set = IntervalSet::new(300);
  27         for j in i..30usize {
  28             set.insert(j);
  29             for k in i..j {
  30                 assert!(set.contains(k));
  31             }
  32         }
  33     }
  34
  35     let mut set = IntervalSet::new(300);
  36     set.insert_range(0..1u32);
  37     assert!(set.contains(0), "{:?}", set.map);
  38     assert!(!set.contains(1));
  39     set.insert_range(1..1);
  40     assert!(set.contains(0));
  41     assert!(!set.contains(1));
  42
  43     let mut set = IntervalSet::new(300);
  44     set.insert_range(4..5u32);
  45     set.insert_range(5..10);
  46     assert_eq!(set.iter().collect::<Vec<_>>(), [4, 5, 6, 7, 8, 9]);
  47     set.insert_range(3..7);
  48     assert_eq!(set.iter().collect::<Vec<_>>(), [3, 4, 5, 6, 7, 8, 9]);
  49
  50     let mut set = IntervalSet::new(300);
  51     set.insert_range(0..10u32);
  52     set.insert_range(3..5);
  53     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  54
  55     let mut set = IntervalSet::new(300);
  56     set.insert_range(0..10u32);
  57     set.insert_range(0..3);
  58     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  59
  60     let mut set = IntervalSet::new(300);
  61     set.insert_range(0..10u32);
  62     set.insert_range(0..10);
  63     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  64
  65     let mut set = IntervalSet::new(300);
  66     set.insert_range(0..10u32);
  67     set.insert_range(5..10);
  68     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  69
  70     let mut set = IntervalSet::new(300);
  71     set.insert_range(0..10u32);
  72     set.insert_range(5..13);
  73     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]);
  74 }
  75
  76 #[test]
  77 fn insert_range() {
  78     #[track_caller]
  79     fn check<R>(range: R)
  80     where
  81         R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
  82     {
  83         let mut set = IntervalSet::new(300);
  84         set.insert_range(range.clone());
  85         for i in set.iter() {
  86             assert!(range.contains(&i));
  87         }
  88         for i in range.clone() {
  89             assert!(set.contains(i), "A: {} in {:?}, inserted {:?}", i, set, range);
  90         }
  91         set.insert_range(range.clone());
  92         for i in set.iter() {
  93             assert!(range.contains(&i), "{} in {:?}", i, set);
  94         }
  95         for i in range.clone() {
  96             assert!(set.contains(i), "B: {} in {:?}, inserted {:?}", i, set, range);
  97         }
  98     }
  99     check(10..10);
 100     check(10..100);
 101     check(10..30);
 102     check(0..5);
 103     check(0..250);
 104     check(200..250);
 105
 106     check(10..=10);
 107     check(10..=100);
 108     check(10..=30);
 109     check(0..=5);
 110     check(0..=250);
 111     check(200..=250);
 112
 113     for i in 0..30 {
 114         for j in i..30 {
 115             check(i..j);
 116             check(i..=j);
 117         }
 118     }
 119 }
 120
 121 #[test]
 122 fn insert_range_dual() {
 123     let mut set = IntervalSet::<u32>::new(300);
 124     set.insert_range(0..3);
 125     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2]);
 126     set.insert_range(5..7);
 127     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 5, 6]);
 128     set.insert_range(3..4);
 129     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 5, 6]);
 130     set.insert_range(3..5);
 131     assert_eq!(set.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6]);
 132 }
 133
 134 #[test]
 135 fn last_set_before_adjacent() {
 136     let mut set = IntervalSet::<u32>::new(300);
 137     set.insert_range(0..3);
 138     set.insert_range(3..5);
 139     assert_eq!(set.last_set_in(0..3), Some(2));
 140     assert_eq!(set.last_set_in(0..5), Some(4));
 141     assert_eq!(set.last_set_in(3..5), Some(4));
 142     set.insert_range(2..5);
 143     assert_eq!(set.last_set_in(0..3), Some(2));
 144     assert_eq!(set.last_set_in(0..5), Some(4));
 145     assert_eq!(set.last_set_in(3..5), Some(4));
 146 }
 147
 148 #[test]
 149 fn last_set_in() {
 150     fn easy(set: &IntervalSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
 151         let mut last_leq = None;
 152         for e in set.iter() {
 153             if needle.contains(&e) {
 154                 last_leq = Some(e);
 155             }
 156         }
 157         last_leq
 158     }
 159
 160     #[track_caller]
 161     fn cmp(set: &IntervalSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
 162         assert_eq!(
 163             set.last_set_in(needle.clone()),
 164             easy(set, needle.clone()),
 165             "{:?} in {:?}",
 166             needle,
 167             set
 168         );
 169     }
 170     let mut set = IntervalSet::new(300);
 171     cmp(&set, 50..=50);
 172     set.insert(64);
 173     cmp(&set, 64..=64);
 174     set.insert(64 - 1);
 175     cmp(&set, 0..=64 - 1);
 176     cmp(&set, 0..=5);
 177     cmp(&set, 10..100);
 178     set.insert(100);
 179     cmp(&set, 100..110);
 180     cmp(&set, 99..100);
 181     cmp(&set, 99..=100);
 182
 183     for i in 0..=30 {
 184         for j in i..=30 {
 185             for k in 0..30 {
 186                 let mut set = IntervalSet::new(100);
 187                 cmp(&set, ..j);
 188                 cmp(&set, i..);
 189                 cmp(&set, i..j);
 190                 cmp(&set, i..=j);
 191                 set.insert(k);
 192                 cmp(&set, ..j);
 193                 cmp(&set, i..);
 194                 cmp(&set, i..j);
 195                 cmp(&set, i..=j);
 196             }
 197         }
 198     }
 199 }