1 //! The [`Ranges`] type stores a list of contiguous index ranges that
2 //! span some other list's full length.
3 
4 use alloc::vec::Vec;
5 use core::ops::Range;
6 
7 /// A list of contiguous index ranges.
8 #[derive(Default)]
9 pub struct Ranges {
10     ranges: Vec<u32>,
11     reverse: bool,
12 }
13 
14 impl Ranges {
15     /// Constructs a new, empty, list of ranges with at least the
16     /// specified capacity.
with_capacity(capacity: usize) -> Self17     pub fn with_capacity(capacity: usize) -> Self {
18         let mut new = Ranges::default();
19         new.reserve(capacity);
20         new
21     }
22 
23     /// Add a new range which begins at the end of the previous range
24     /// and ends at the specified offset, exclusive.
push_end(&mut self, end: usize)25     pub fn push_end(&mut self, end: usize) {
26         debug_assert!(!self.reverse);
27         // To keep this implementation simple we explicitly store the
28         // starting index, which is always 0, so that all ranges are
29         // represented by adjacent pairs in the list. But we add it
30         // lazily so that an empty list doesn't have to allocate.
31         if self.ranges.is_empty() {
32             self.ranges.push(0);
33         }
34         self.ranges.push(u32::try_from(end).unwrap());
35     }
36 
37     /// Number of ranges in this list.
len(&self) -> usize38     pub fn len(&self) -> usize {
39         self.ranges.len().saturating_sub(1)
40     }
41 
42     /// Reserves capacity for at least `additional` more ranges to be
43     /// added to this list.
reserve(&mut self, mut additional: usize)44     pub fn reserve(&mut self, mut additional: usize) {
45         if additional > 0 && self.ranges.is_empty() {
46             additional = additional.saturating_add(1);
47         }
48         self.ranges.reserve(additional);
49     }
50 
51     /// Get the range at the specified index.
get(&self, index: usize) -> Range<usize>52     pub fn get(&self, index: usize) -> Range<usize> {
53         let len = self.len();
54         assert!(index < len, "index {index} is too big for length {len}");
55         let index = self.map_index(index);
56         self.ranges[index] as usize..self.ranges[index + 1] as usize
57     }
58 
59     /// Visit ranges in unspecified order, paired with the index each
60     /// range occurs at.
iter( &self, ) -> impl DoubleEndedIterator<Item = (usize, Range<usize>)> + ExactSizeIterator + '_61     pub fn iter(
62         &self,
63     ) -> impl DoubleEndedIterator<Item = (usize, Range<usize>)> + ExactSizeIterator + '_ {
64         self.ranges
65             .windows(2)
66             .enumerate()
67             .map(|(index, range)| (self.map_index(index), range[0] as usize..range[1] as usize))
68     }
69 
70     /// Reverse this list of ranges, so that the first range is at the
71     /// last index and the last range is at the first index.
72     ///
73     /// ```ignore
74     /// use cranelift_codegen::ranges::Ranges;
75     /// let mut ranges = Ranges::default();
76     /// ranges.push_end(4);
77     /// ranges.push_end(6);
78     /// ranges.reverse_index();
79     /// assert_eq!(ranges.get(0), 4..6);
80     /// assert_eq!(ranges.get(1), 0..4);
81     /// ```
reverse_index(&mut self)82     pub fn reverse_index(&mut self) {
83         // We can't easily change the order of the endpoints in
84         // self.ranges: they need to be in ascending order or our
85         // compressed representation gets complicated. So instead we
86         // change our interpretation of indexes using map_index below,
87         // controlled by a simple flag. As a bonus, reversing the list
88         // is constant-time!
89         self.reverse = !self.reverse;
90     }
91 
map_index(&self, index: usize) -> usize92     fn map_index(&self, index: usize) -> usize {
93         if self.reverse {
94             // These subtractions can't overflow because callers
95             // enforce that 0 <= index < self.len()
96             self.len() - 1 - index
97         } else {
98             index
99         }
100     }
101 
102     /// Update these ranges to reflect that the list they refer to has
103     /// been reversed. Afterwards, the ranges will still be indexed
104     /// in the same order, but the first range will refer to the
105     /// same-length range at the end of the target list instead of at
106     /// the beginning, and subsequent ranges will proceed backwards
107     /// from there.
108     ///
109     /// ```ignore
110     /// use cranelift_codegen::ranges::Ranges;
111     /// let mut ranges = Ranges::default();
112     /// ranges.push_end(4);
113     /// ranges.push_end(6);
114     /// ranges.reverse_target(6);
115     /// assert_eq!(ranges.get(0), 2..6);
116     /// assert_eq!(ranges.get(1), 0..2);
117     /// ```
reverse_target(&mut self, target_len: usize)118     pub fn reverse_target(&mut self, target_len: usize) {
119         let target_len = u32::try_from(target_len).unwrap();
120         // The last endpoint added should be the same as the current
121         // length of the target list.
122         debug_assert_eq!(target_len, *self.ranges.last().unwrap_or(&0));
123         for end in self.ranges.iter_mut() {
124             *end = target_len - *end;
125         }
126         // Put the endpoints back in ascending order, but that means
127         // now our indexes are backwards.
128         self.ranges.reverse();
129         self.reverse_index();
130     }
131 }
132