cranelift_codegen/
ranges.rs

1//! The [`Ranges`] type stores a list of contiguous index ranges that
2//! span some other list's full length.
3
4use alloc::vec::Vec;
5use core::ops::Range;
6
7/// A list of contiguous index ranges.
8#[derive(Default)]
9pub struct Ranges {
10    ranges: Vec<u32>,
11    reverse: bool,
12}
13
14impl Ranges {
15    /// Constructs a new, empty, list of ranges with at least the
16    /// specified capacity.
17    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.
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.
38    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.
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.
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.
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    /// ```
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
92    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    /// ```
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}
cranelift_codegen/ranges.rs

cranelift_codegen/
ranges.rs
