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
5 use rustc_target::abi::Size;
6 use std::ops::{Index, IndexMut, Range};
8 use rustc_const_eval::interpret::AllocRange;
10 #[derive(Clone, Debug)]
12 /// The range covered by this element; never empty.
14 /// The data stored for this element.
18 /// Index of an allocation within the map
19 type Position = usize;
21 #[derive(Clone, Debug)]
22 pub struct RangeObjectMap<T> {
26 #[derive(Clone, Debug, PartialEq)]
28 /// The access perfectly overlaps (same offset and range) with the exsiting allocation
29 PerfectlyOverlapping(Position),
30 /// The access does not touch any exising allocation
32 /// The access overlaps with one or more existing allocations
33 ImperfectlyOverlapping(Range<Position>),
36 impl<T> RangeObjectMap<T> {
37 pub fn new() -> Self {
38 Self { v: Vec::new() }
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
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
50 // No element contains the given offset. But the
51 // position is where such element should be placed at.
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
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
71 /// Determines whether a given access on `range` overlaps with
72 /// an existing allocation
73 pub fn access_type(&self, range: AllocRange) -> AccessType {
74 match self.find_offset(range.start) {
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)
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,
90 AccessType::ImperfectlyOverlapping(pos..end_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
99 // There's nothing between the start and the end, so the range thing is empty
100 AccessType::Empty(pos)
102 // Otherwise we have entirely covered an existing object
103 AccessType::ImperfectlyOverlapping(pos..end_pos)
105 // Otherwise at least part of it overlaps with something else
106 Ok(end_pos) => AccessType::ImperfectlyOverlapping(pos..end_pos + 1),
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
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 preivous element's end
120 assert!(self.v[pos - 1].range.end() <= range.start);
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);
128 pub fn remove_pos_range(&mut self, pos_range: Range<Position>) {
129 self.v.drain(pos_range);
132 pub fn remove_from_pos(&mut self, pos: Position) {
136 pub fn iter(&self) -> impl Iterator<Item = &T> {
137 self.v.iter().map(|e| &e.data)
141 impl<T> Index<Position> for RangeObjectMap<T> {
144 fn index(&self, pos: Position) -> &Self::Output {
149 impl<T> IndexMut<Position> for RangeObjectMap<T> {
150 fn index_mut(&mut self, pos: Position) -> &mut Self::Output {
151 &mut self.v[pos].data
157 use rustc_const_eval::interpret::alloc_range;
163 // FIXME: make Size::from_bytes const
164 let four = Size::from_bytes(4);
165 let map = RangeObjectMap::<()>::new();
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));
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));
176 fn no_overlapping_inserts() {
177 let four = Size::from_bytes(4);
179 let mut map = RangeObjectMap::<&str>::new();
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), "@");
191 let four = Size::from_bytes(4);
193 let mut map = RangeObjectMap::<&str>::new();
197 map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#");
200 assert_eq!(map.find_offset(four), Err(1));
201 // |#|#|#|#|_|_|_|_|_|...
203 assert_eq!(map.access_type(alloc_range(four, four)), AccessType::Empty(1));
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));
218 fn perfectly_overlapping() {
219 let four = Size::from_bytes(4);
221 let mut map = RangeObjectMap::<&str>::new();
225 map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#");
228 assert_eq!(map.find_offset(Size::ZERO), Ok(0));
230 map.access_type(alloc_range(Size::ZERO, four)),
231 AccessType::PerfectlyOverlapping(0)
234 // |#|#|#|#|@|@|@|@|_|...
236 map.insert_at_pos(1, alloc_range(four, four), "@");
237 // |#|#|#|#|@|@|@|@|_|...
239 assert_eq!(map.find_offset(four), Ok(1));
240 assert_eq!(map.access_type(alloc_range(four, four)), AccessType::PerfectlyOverlapping(1));
245 let four = Size::from_bytes(4);
247 let mut map = RangeObjectMap::<&str>::new();
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
255 map.access_type(alloc_range(Size::from_bytes(2), four)),
256 AccessType::ImperfectlyOverlapping(0..1)
258 // |_|_|_|_|#|#|#|#|_|_|_|_|...
259 // 0 1 2 3 4 5 ^ ^ ^ ^ a b c d
261 map.access_type(alloc_range(Size::from_bytes(6), four)),
262 AccessType::ImperfectlyOverlapping(0..1)
264 // |_|_|_|_|#|#|#|#|_|_|_|_|...
265 // 0 1 ^ ^ ^ ^ ^ ^ ^ ^ a b c d
267 map.access_type(alloc_range(Size::from_bytes(2), Size::from_bytes(8))),
268 AccessType::ImperfectlyOverlapping(0..1)
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 ^ ^ ^ ^ ^ ^ ^ ^
277 map.access_type(alloc_range(Size::from_bytes(6), Size::from_bytes(8))),
278 AccessType::ImperfectlyOverlapping(0..2)