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