ranges.rs

//! The [`Ranges`] type stores a list of contiguous index ranges that
//! span some other list's full length.

use alloc::vec::Vec;
use core::ops::Range;

/// A list of contiguous index ranges.
#[derive(Default)]
pub struct Ranges {
    ranges: Vec<u32>,
    reverse: bool,
}

impl Ranges {
    /// Constructs a new, empty, list of ranges with at least the
    /// specified capacity.
    pub fn with_capacity(capacity: usize) -> Self {
        let mut new = Ranges::default();
        new.reserve(capacity);
        new
    }

    /// Add a new range which begins at the end of the previous range
    /// and ends at the specified offset, exclusive.
    pub fn push_end(&mut self, end: usize) {
        debug_assert!(!self.reverse);
        // To keep this implementation simple we explicitly store the
        // starting index, which is always 0, so that all ranges are
        // represented by adjacent pairs in the list. But we add it
        // lazily so that an empty list doesn't have to allocate.
        if self.ranges.is_empty() {
            self.ranges.push(0);
        }
        self.ranges.push(u32::try_from(end).unwrap());
    }

    /// Number of ranges in this list.
    pub fn len(&self) -> usize {
        self.ranges.len().saturating_sub(1)
    }

    /// Reserves capacity for at least `additional` more ranges to be
    /// added to this list.
    pub fn reserve(&mut self, mut additional: usize) {
        if additional > 0 && self.ranges.is_empty() {
            additional = additional.saturating_add(1);
        }
        self.ranges.reserve(additional);
    }

    /// Get the range at the specified index.
    pub fn get(&self, index: usize) -> Range<usize> {
        let len = self.len();
        assert!(index < len, "index {index} is too big for length {len}");
        let index = self.map_index(index);
        self.ranges[index] as usize..self.ranges[index + 1] as usize
    }

    /// Visit ranges in unspecified order, paired with the index each
    /// range occurs at.
    pub fn iter(
        &self,
    ) -> impl DoubleEndedIterator<Item = (usize, Range<usize>)> + ExactSizeIterator + '_ {
        self.ranges
            .windows(2)
            .enumerate()
            .map(|(index, range)| (self.map_index(index), range[0] as usize..range[1] as usize))
    }

    /// Reverse this list of ranges, so that the first range is at the
    /// last index and the last range is at the first index.
    ///
    /// ```ignore
    /// use cranelift_codegen::ranges::Ranges;
    /// let mut ranges = Ranges::default();
    /// ranges.push_end(4);
    /// ranges.push_end(6);
    /// ranges.reverse_index();
    /// assert_eq!(ranges.get(0), 4..6);
    /// assert_eq!(ranges.get(1), 0..4);
    /// ```
    pub fn reverse_index(&mut self) {
        // We can't easily change the order of the endpoints in
        // self.ranges: they need to be in ascending order or our
        // compressed representation gets complicated. So instead we
        // change our interpretation of indexes using map_index below,
        // controlled by a simple flag. As a bonus, reversing the list
        // is constant-time!
        self.reverse = !self.reverse;
    }

    fn map_index(&self, index: usize) -> usize {
        if self.reverse {
            // These subtractions can't overflow because callers
            // enforce that 0 <= index < self.len()
            self.len() - 1 - index
        } else {
            index
        }
    }

    /// Update these ranges to reflect that the list they refer to has
    /// been reversed. Afterwards, the ranges will still be indexed
    /// in the same order, but the first range will refer to the
    /// same-length range at the end of the target list instead of at
    /// the beginning, and subsequent ranges will proceed backwards
    /// from there.
    ///
    /// ```ignore
    /// use cranelift_codegen::ranges::Ranges;
    /// let mut ranges = Ranges::default();
    /// ranges.push_end(4);
    /// ranges.push_end(6);
    /// ranges.reverse_target(6);
    /// assert_eq!(ranges.get(0), 2..6);
    /// assert_eq!(ranges.get(1), 0..2);
    /// ```
    pub fn reverse_target(&mut self, target_len: usize) {
        let target_len = u32::try_from(target_len).unwrap();
        // The last endpoint added should be the same as the current
        // length of the target list.
        debug_assert_eq!(target_len, *self.ranges.last().unwrap_or(&0));
        for end in self.ranges.iter_mut() {
            *end = target_len - *end;
        }
        // Put the endpoints back in ascending order, but that means
        // now our indexes are backwards.
        self.ranges.reverse();
        self.reverse_index();
    }
}