git.bitcoin.ninja Git - rust-lightning/blob - fuzz/src/indexedmap.rs

   1 // This file is Copyright its original authors, visible in version control
   2 // history.
   3 //
   4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
   5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
   7 // You may not use this file except in accordance with one or both of these
   8 // licenses.
   9
  10 use lightning::util::indexed_map::{IndexedMap, self};
  11 use std::collections::{BTreeMap, btree_map};
  12 use hashbrown::HashSet;
  13
  14 use crate::utils::test_logger;
  15
  16 use std::ops::{RangeBounds, Bound};
  17
  18 struct ExclLowerInclUpper(u8, u8);
  19 impl RangeBounds<u8> for ExclLowerInclUpper {
  20         fn start_bound(&self) -> Bound<&u8> { Bound::Excluded(&self.0) }
  21         fn end_bound(&self) -> Bound<&u8> { Bound::Included(&self.1) }
  22 }
  23 struct ExclLowerExclUpper(u8, u8);
  24 impl RangeBounds<u8> for ExclLowerExclUpper {
  25         fn start_bound(&self) -> Bound<&u8> { Bound::Excluded(&self.0) }
  26         fn end_bound(&self) -> Bound<&u8> { Bound::Excluded(&self.1) }
  27 }
  28
  29 fn check_eq(btree: &BTreeMap<u8, u8>, mut indexed: IndexedMap<u8, u8>) {
  30         assert_eq!(btree.len(), indexed.len());
  31         assert_eq!(btree.is_empty(), indexed.is_empty());
  32
  33         let mut btree_clone = btree.clone();
  34         assert!(btree_clone == *btree);
  35         let mut indexed_clone = indexed.clone();
  36         assert!(indexed_clone == indexed);
  37
  38         for k in 0..=255 {
  39                 assert_eq!(btree.contains_key(&k), indexed.contains_key(&k));
  40                 assert_eq!(btree.get(&k), indexed.get(&k));
  41
  42                 let btree_entry = btree_clone.entry(k);
  43                 let indexed_entry = indexed_clone.entry(k);
  44                 match btree_entry {
  45                         btree_map::Entry::Occupied(mut bo) => {
  46                                 if let indexed_map::Entry::Occupied(mut io) = indexed_entry {
  47                                         assert_eq!(bo.get(), io.get());
  48                                         assert_eq!(bo.get_mut(), io.get_mut());
  49                                 } else { panic!(); }
  50                         },
  51                         btree_map::Entry::Vacant(_) => {
  52                                 if let indexed_map::Entry::Vacant(_) = indexed_entry {
  53                                 } else { panic!(); }
  54                         }
  55                 }
  56         }
  57
  58         const STRIDE: u8 = 16;
  59         for range_type in 0..4 {
  60                 for k in 0..=255/STRIDE {
  61                         let lower_bound = k * STRIDE;
  62                         let upper_bound = lower_bound + (STRIDE - 1);
  63                         macro_rules! range { ($map: expr) => {
  64                                 match range_type {
  65                                         0 => $map.range(lower_bound..upper_bound),
  66                                         1 => $map.range(lower_bound..=upper_bound),
  67                                         2 => $map.range(ExclLowerInclUpper(lower_bound, upper_bound)),
  68                                         3 => $map.range(ExclLowerExclUpper(lower_bound, upper_bound)),
  69                                         _ => unreachable!(),
  70                                 }
  71                         } }
  72                         let mut btree_iter = range!(btree);
  73                         let mut indexed_iter = range!(indexed);
  74                         loop {
  75                                 let b_v = btree_iter.next();
  76                                 let i_v = indexed_iter.next();
  77                                 assert_eq!(b_v, i_v);
  78                                 if b_v.is_none() { break; }
  79                         }
  80                 }
  81         }
  82
  83         let mut key_set = HashSet::with_capacity(256);
  84         for k in indexed.unordered_keys() {
  85                 assert!(key_set.insert(*k));
  86                 assert!(btree.contains_key(k));
  87         }
  88         assert_eq!(key_set.len(), btree.len());
  89
  90         key_set.clear();
  91         for (k, v) in indexed.unordered_iter() {
  92                 assert!(key_set.insert(*k));
  93                 assert_eq!(btree.get(k).unwrap(), v);
  94         }
  95         assert_eq!(key_set.len(), btree.len());
  96
  97         key_set.clear();
  98         for (k, v) in indexed_clone.unordered_iter_mut() {
  99                 assert!(key_set.insert(*k));
 100                 assert_eq!(btree.get(k).unwrap(), v);
 101         }
 102         assert_eq!(key_set.len(), btree.len());
 103 }
 104
 105 #[inline]
 106 pub fn do_test(data: &[u8]) {
 107         if data.len() % 2 != 0 { return; }
 108         let mut btree = BTreeMap::new();
 109         let mut indexed = IndexedMap::new();
 110
 111         // Read in k-v pairs from the input and insert them into the maps then check that the maps are
 112         // equivalent in every way we can read them.
 113         for tuple in data.windows(2) {
 114                 let prev_value_b = btree.insert(tuple[0], tuple[1]);
 115                 let prev_value_i = indexed.insert(tuple[0], tuple[1]);
 116                 assert_eq!(prev_value_b, prev_value_i);
 117         }
 118         check_eq(&btree, indexed.clone());
 119
 120         // Now, modify the maps in all the ways we have to do so, checking that the maps remain
 121         // equivalent as we go.
 122         for (k, v) in indexed.unordered_iter_mut() {
 123                 *v = *k;
 124                 *btree.get_mut(k).unwrap() = *k;
 125         }
 126         check_eq(&btree, indexed.clone());
 127
 128         for k in 0..=255 {
 129                 match btree.entry(k) {
 130                         btree_map::Entry::Occupied(mut bo) => {
 131                                 if let indexed_map::Entry::Occupied(mut io) = indexed.entry(k) {
 132                                         if k < 64 {
 133                                                 *io.get_mut() ^= 0xff;
 134                                                 *bo.get_mut() ^= 0xff;
 135                                         } else if k < 128 {
 136                                                 *io.into_mut() ^= 0xff;
 137                                                 *bo.get_mut() ^= 0xff;
 138                                         } else {
 139                                                 assert_eq!(bo.remove_entry(), io.remove_entry());
 140                                         }
 141                                 } else { panic!(); }
 142                         },
 143                         btree_map::Entry::Vacant(bv) => {
 144                                 if let indexed_map::Entry::Vacant(iv) = indexed.entry(k) {
 145                                         bv.insert(k);
 146                                         iv.insert(k);
 147                                 } else { panic!(); }
 148                         },
 149                 }
 150         }
 151         check_eq(&btree, indexed);
 152 }
 153
 154 pub fn indexedmap_test<Out: test_logger::Output>(data: &[u8], _out: Out) {
 155         do_test(data);
 156 }
 157
 158 #[no_mangle]
 159 pub extern "C" fn indexedmap_run(data: *const u8, datalen: usize) {
 160         do_test(unsafe { std::slice::from_raw_parts(data, datalen) });
 161 }