1 //! Implements a map from allocation ranges to data. This is somewhat similar to RangeMap, but the 2 //! ranges and data are discrete and non-splittable -- they represent distinct "objects". An 3 //! allocation in the map will always have the same range until explicitly removed 4 5 use rustc_target::abi::Size; 6 use std::ops::{Index, IndexMut, Range}; 7 8 use rustc_const_eval::interpret::AllocRange; 9 10 #[derive(Clone, Debug)] 11 struct Elem<T> { 12 /// The range covered by this element; never empty. 13 range: AllocRange, 14 /// The data stored for this element. 15 data: T, 16 } 17 18 /// Index of an allocation within the map 19 type Position = usize; 20 21 #[derive(Clone, Debug)] 22 pub struct RangeObjectMap<T> { 23 v: Vec<Elem<T>>, 24 } 25 26 #[derive(Clone, Debug, PartialEq)] 27 pub enum AccessType { 28 /// The access perfectly overlaps (same offset and range) with the existing allocation 29 PerfectlyOverlapping(Position), 30 /// The access does not touch any existing allocation 31 Empty(Position), 32 /// The access overlaps with one or more existing allocations 33 ImperfectlyOverlapping(Range<Position>), 34 } 35 36 impl<T> RangeObjectMap<T> { new() -> Self37 pub fn new() -> Self { 38 Self { v: Vec::new() } 39 } 40 41 /// Finds the position of the allocation containing the given offset. If the offset is not 42 /// in an existing allocation, then returns Err containing the position 43 /// where such allocation should be inserted find_offset(&self, offset: Size) -> Result<Position, Position>44 fn find_offset(&self, offset: Size) -> Result<Position, Position> { 45 // We do a binary search. 46 let mut left = 0usize; // inclusive 47 let mut right = self.v.len(); // exclusive 48 loop { 49 if left == right { 50 // No element contains the given offset. But the 51 // position is where such element should be placed at. 52 return Err(left); 53 } 54 let candidate = left.checked_add(right).unwrap() / 2; 55 let elem = &self.v[candidate]; 56 if offset < elem.range.start { 57 // We are too far right (offset is further left). 58 debug_assert!(candidate < right); // we are making progress 59 right = candidate; 60 } else if offset >= elem.range.end() { 61 // We are too far left (offset is further right). 62 debug_assert!(candidate >= left); // we are making progress 63 left = candidate + 1; 64 } else { 65 // This is it! 66 return Ok(candidate); 67 } 68 } 69 } 70 71 /// Determines whether a given access on `range` overlaps with 72 /// an existing allocation access_type(&self, range: AllocRange) -> AccessType73 pub fn access_type(&self, range: AllocRange) -> AccessType { 74 match self.find_offset(range.start) { 75 Ok(pos) => { 76 // Start of the range belongs to an existing object, now let's check the overlapping situation 77 let elem = &self.v[pos]; 78 // FIXME: derive Eq for AllocRange in rustc 79 if elem.range.start == range.start && elem.range.size == range.size { 80 // Happy case: perfectly overlapping access 81 AccessType::PerfectlyOverlapping(pos) 82 } else { 83 // FIXME: add a last() method to AllocRange that returns the last inclusive offset (end() is exclusive) 84 let end_pos = match self.find_offset(range.end() - Size::from_bytes(1)) { 85 // If the end lands in an existing object, add one to get the exclusive position 86 Ok(inclusive_pos) => inclusive_pos + 1, 87 Err(exclusive_pos) => exclusive_pos, 88 }; 89 90 AccessType::ImperfectlyOverlapping(pos..end_pos) 91 } 92 } 93 Err(pos) => { 94 // Start of the range doesn't belong to an existing object 95 match self.find_offset(range.end() - Size::from_bytes(1)) { 96 // Neither does the end 97 Err(end_pos) => 98 if pos == end_pos { 99 // There's nothing between the start and the end, so the range thing is empty 100 AccessType::Empty(pos) 101 } else { 102 // Otherwise we have entirely covered an existing object 103 AccessType::ImperfectlyOverlapping(pos..end_pos) 104 }, 105 // Otherwise at least part of it overlaps with something else 106 Ok(end_pos) => AccessType::ImperfectlyOverlapping(pos..end_pos + 1), 107 } 108 } 109 } 110 } 111 112 /// Inserts an object and its occupied range at given position 113 // The Position can be calculated from AllocRange, but the only user of AllocationMap 114 // always calls access_type before calling insert/index/index_mut, and we don't 115 // want to repeat the binary search on each time, so we ask the caller to supply Position insert_at_pos(&mut self, pos: Position, range: AllocRange, data: T)116 pub fn insert_at_pos(&mut self, pos: Position, range: AllocRange, data: T) { 117 self.v.insert(pos, Elem { range, data }); 118 // If we aren't the first element, then our start must be greater than the previous element's end 119 if pos > 0 { 120 assert!(self.v[pos - 1].range.end() <= range.start); 121 } 122 // If we aren't the last element, then our end must be smaller than next element's start 123 if pos < self.v.len() - 1 { 124 assert!(range.end() <= self.v[pos + 1].range.start); 125 } 126 } 127 remove_pos_range(&mut self, pos_range: Range<Position>)128 pub fn remove_pos_range(&mut self, pos_range: Range<Position>) { 129 self.v.drain(pos_range); 130 } 131 remove_from_pos(&mut self, pos: Position)132 pub fn remove_from_pos(&mut self, pos: Position) { 133 self.v.remove(pos); 134 } 135 iter(&self) -> impl Iterator<Item = &T>136 pub fn iter(&self) -> impl Iterator<Item = &T> { 137 self.v.iter().map(|e| &e.data) 138 } 139 } 140 141 impl<T> Index<Position> for RangeObjectMap<T> { 142 type Output = T; 143 index(&self, pos: Position) -> &Self::Output144 fn index(&self, pos: Position) -> &Self::Output { 145 &self.v[pos].data 146 } 147 } 148 149 impl<T> IndexMut<Position> for RangeObjectMap<T> { index_mut(&mut self, pos: Position) -> &mut Self::Output150 fn index_mut(&mut self, pos: Position) -> &mut Self::Output { 151 &mut self.v[pos].data 152 } 153 } 154 155 #[cfg(test)] 156 mod tests { 157 use rustc_const_eval::interpret::alloc_range; 158 159 use super::*; 160 161 #[test] empty_map()162 fn empty_map() { 163 // FIXME: make Size::from_bytes const 164 let four = Size::from_bytes(4); 165 let map = RangeObjectMap::<()>::new(); 166 167 // Correctly tells where we should insert the first element (at position 0) 168 assert_eq!(map.find_offset(Size::from_bytes(3)), Err(0)); 169 170 // Correctly tells the access type along with the supposed position 171 assert_eq!(map.access_type(alloc_range(Size::ZERO, four)), AccessType::Empty(0)); 172 } 173 174 #[test] 175 #[should_panic] no_overlapping_inserts()176 fn no_overlapping_inserts() { 177 let four = Size::from_bytes(4); 178 179 let mut map = RangeObjectMap::<&str>::new(); 180 181 // |_|_|_|_|#|#|#|#|_|_|_|_|... 182 // 0 1 2 3 4 5 6 7 8 9 a b c d 183 map.insert_at_pos(0, alloc_range(four, four), "#"); 184 // |_|_|_|_|#|#|#|#|_|_|_|_|... 185 // 0 ^ ^ ^ ^ 5 6 7 8 9 a b c d 186 map.insert_at_pos(0, alloc_range(Size::from_bytes(1), four), "@"); 187 } 188 189 #[test] boundaries()190 fn boundaries() { 191 let four = Size::from_bytes(4); 192 193 let mut map = RangeObjectMap::<&str>::new(); 194 195 // |#|#|#|#|_|_|... 196 // 0 1 2 3 4 5 197 map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#"); 198 // |#|#|#|#|_|_|... 199 // 0 1 2 3 ^ 5 200 assert_eq!(map.find_offset(four), Err(1)); 201 // |#|#|#|#|_|_|_|_|_|... 202 // 0 1 2 3 ^ ^ ^ ^ 8 203 assert_eq!(map.access_type(alloc_range(four, four)), AccessType::Empty(1)); 204 205 let eight = Size::from_bytes(8); 206 // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|... 207 // 0 1 2 3 4 5 6 7 8 9 a b c d 208 map.insert_at_pos(1, alloc_range(eight, four), "@"); 209 // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|... 210 // 0 1 2 3 4 5 6 ^ 8 9 a b c d 211 assert_eq!(map.find_offset(Size::from_bytes(7)), Err(1)); 212 // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|... 213 // 0 1 2 3 ^ ^ ^ ^ 8 9 a b c d 214 assert_eq!(map.access_type(alloc_range(four, four)), AccessType::Empty(1)); 215 } 216 217 #[test] perfectly_overlapping()218 fn perfectly_overlapping() { 219 let four = Size::from_bytes(4); 220 221 let mut map = RangeObjectMap::<&str>::new(); 222 223 // |#|#|#|#|_|_|... 224 // 0 1 2 3 4 5 225 map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#"); 226 // |#|#|#|#|_|_|... 227 // ^ ^ ^ ^ 4 5 228 assert_eq!(map.find_offset(Size::ZERO), Ok(0)); 229 assert_eq!( 230 map.access_type(alloc_range(Size::ZERO, four)), 231 AccessType::PerfectlyOverlapping(0) 232 ); 233 234 // |#|#|#|#|@|@|@|@|_|... 235 // 0 1 2 3 4 5 6 7 8 236 map.insert_at_pos(1, alloc_range(four, four), "@"); 237 // |#|#|#|#|@|@|@|@|_|... 238 // 0 1 2 3 ^ ^ ^ ^ 8 239 assert_eq!(map.find_offset(four), Ok(1)); 240 assert_eq!(map.access_type(alloc_range(four, four)), AccessType::PerfectlyOverlapping(1)); 241 } 242 243 #[test] straddling()244 fn straddling() { 245 let four = Size::from_bytes(4); 246 247 let mut map = RangeObjectMap::<&str>::new(); 248 249 // |_|_|_|_|#|#|#|#|_|_|_|_|... 250 // 0 1 2 3 4 5 6 7 8 9 a b c d 251 map.insert_at_pos(0, alloc_range(four, four), "#"); 252 // |_|_|_|_|#|#|#|#|_|_|_|_|... 253 // 0 1 ^ ^ ^ ^ 6 7 8 9 a b c d 254 assert_eq!( 255 map.access_type(alloc_range(Size::from_bytes(2), four)), 256 AccessType::ImperfectlyOverlapping(0..1) 257 ); 258 // |_|_|_|_|#|#|#|#|_|_|_|_|... 259 // 0 1 2 3 4 5 ^ ^ ^ ^ a b c d 260 assert_eq!( 261 map.access_type(alloc_range(Size::from_bytes(6), four)), 262 AccessType::ImperfectlyOverlapping(0..1) 263 ); 264 // |_|_|_|_|#|#|#|#|_|_|_|_|... 265 // 0 1 ^ ^ ^ ^ ^ ^ ^ ^ a b c d 266 assert_eq!( 267 map.access_type(alloc_range(Size::from_bytes(2), Size::from_bytes(8))), 268 AccessType::ImperfectlyOverlapping(0..1) 269 ); 270 271 // |_|_|_|_|#|#|#|#|_|_|@|@|_|_|... 272 // 0 1 2 3 4 5 6 7 8 9 a b c d 273 map.insert_at_pos(1, alloc_range(Size::from_bytes(10), Size::from_bytes(2)), "@"); 274 // |_|_|_|_|#|#|#|#|_|_|@|@|_|_|... 275 // 0 1 2 3 4 5 ^ ^ ^ ^ ^ ^ ^ ^ 276 assert_eq!( 277 map.access_type(alloc_range(Size::from_bytes(6), Size::from_bytes(8))), 278 AccessType::ImperfectlyOverlapping(0..2) 279 ); 280 } 281 } 282