rustc_abi/

wrapping_range.rs

use std::ops::RangeFull;
use std::{fmt, iter};

use crate::Size;
#[cfg(feature = "nightly")]
use crate::StableHash;

/// Inclusive wrap-around range of valid values, that is, if
/// start > end, it represents `start..=MAX`, followed by `0..=end`.
///
/// That is, for an i8 primitive, a range of `254..=2` means following
/// sequence:
///
///    254 (-2), 255 (-1), 0, 1, 2
///
/// This is intended specifically to mirror LLVM’s `!range` metadata semantics.
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "nightly", derive(StableHash))]
pub struct WrappingRange {
    pub start: u128,
    pub end: u128,
}

impl WrappingRange {
    pub(crate) fn debug_as(&self, size: Size, is_signed: bool) -> impl fmt::Debug {
        let range = *self;
        fmt::from_fn(move |f| {
            if range == WrappingRange::full(size) {
                // This is intentionally not using `is_full_for` so that we ensure
                // different values always debug-print differently.
                // We don't need the full details when it's the canonical full range,
                // but if one is looking at the debug output it might be that seeing
                // `u8 is (..=0) | (1..)` instead of `u8 is ..` is the information
                // you needed because the problem is that despite being *a* full
                // range it's not *the* canonical one you expected it was.
                f.write_str("..")
            } else if is_signed {
                let start = size.sign_extend(range.start);
                let end = size.sign_extend(range.end);
                if start > end {
                    write!(f, "(..={}) | ({}..)", end, start)
                } else {
                    write!(f, "{}..={}", start, end)
                }
            } else {
                write!(f, "{:?}", range)
            }
        })
    }

    pub fn full(size: Size) -> Self {
        Self { start: 0, end: size.unsigned_int_max() }
    }

    /// Returns `true` if `v` is contained in the range.
    #[inline(always)]
    pub fn contains(&self, v: u128) -> bool {
        if self.start <= self.end {
            self.start <= v && v <= self.end
        } else {
            self.start <= v || v <= self.end
        }
    }

    /// Returns `true` if all the values in `other` are contained in this range,
    /// when the values are considered as having width `size`.
    #[inline(always)]
    pub fn contains_range(&self, other: Self, size: Size) -> bool {
        if self.is_full_for(size) {
            true
        } else {
            let trunc = |x| size.truncate(x);

            let delta = self.start;
            let max = trunc(self.end.wrapping_sub(delta));

            let other_start = trunc(other.start.wrapping_sub(delta));
            let other_end = trunc(other.end.wrapping_sub(delta));

            // Having shifted both input ranges by `delta`, now we only need to check
            // whether `0..=max` contains `other_start..=other_end`, which can only
            // happen if the other doesn't wrap since `self` isn't everything.
            (other_start <= other_end) && (other_end <= max)
        }
    }

    /// Returns `self` with replaced `start`
    #[inline(always)]
    pub(crate) fn with_start(mut self, start: u128) -> Self {
        self.start = start;
        self
    }

    /// Returns `self` with replaced `end`
    #[inline(always)]
    pub(crate) fn with_end(mut self, end: u128) -> Self {
        self.end = end;
        self
    }

    /// The wrapping distance from `self.start` to `self.end`.
    fn width(&self, size: Size) -> u128 {
        size.truncate(u128::wrapping_sub(self.end, self.start))
    }

    /// Returns `true` if `size` completely fills the range.
    ///
    /// Note that this is *not* the same as `self == WrappingRange::full(size)`.
    /// Niche calculations can produce full ranges which are not the canonical one;
    /// for example `Option<NonZero<u16>>` gets `valid_range: (..=0) | (1..)`.
    #[inline]
    pub fn is_full_for(&self, size: Size) -> bool {
        let max_value = size.unsigned_int_max();
        debug_assert!(self.start <= max_value && self.end <= max_value);
        self.start == (self.end.wrapping_add(1) & max_value)
    }

    /// Checks whether this range is considered non-wrapping when the values are
    /// interpreted as *unsigned* numbers of width `size`.
    ///
    /// Returns `Ok(true)` if there's no wrap-around, `Ok(false)` if there is,
    /// and `Err(..)` if the range is full so it depends how you think about it.
    #[inline]
    pub fn no_unsigned_wraparound(&self, size: Size) -> Result<bool, RangeFull> {
        if self.is_full_for(size) { Err(..) } else { Ok(self.start <= self.end) }
    }

    /// Checks whether this range is considered non-wrapping when the values are
    /// interpreted as *signed* numbers of width `size`.
    ///
    /// This is heavily dependent on the `size`, as `100..=200` does wrap when
    /// interpreted as `i8`, but doesn't when interpreted as `i16`.
    ///
    /// Returns `Ok(true)` if there's no wrap-around, `Ok(false)` if there is,
    /// and `Err(..)` if the range is full so it depends how you think about it.
    #[inline]
    pub fn no_signed_wraparound(&self, size: Size) -> Result<bool, RangeFull> {
        if self.is_full_for(size) {
            Err(..)
        } else {
            let start: i128 = size.sign_extend(self.start);
            let end: i128 = size.sign_extend(self.end);
            Ok(start <= end)
        }
    }

    /// Returns a `WrappingRange` that contains all of the values from the iterator,
    /// when they're treated as values `size` wide.
    ///
    /// # Examples
    ///
    /// ```
    /// use rustc_abi::{Size, WrappingRange};
    ///
    /// let chain = std::iter::chain(10..20, 30..40);
    /// let range = WrappingRange::smallest_range_containing(chain, Size::from_bytes(2));
    /// assert_eq!(range.unwrap(), WrappingRange { start: 10, end: 39 });
    ///
    /// // Values don't need to be sorted nor unique
    /// let range = WrappingRange::smallest_range_containing([3, 5, 3, 1, 3], Size::from_bytes(2));
    /// assert_eq!(range.unwrap(), WrappingRange { start: 1, end: 5 });
    ///
    /// // The size matters because it changes where the wrapping can happen:
    /// let range = WrappingRange::smallest_range_containing([1, 254], Size::from_bytes(1));
    /// assert_eq!(range.unwrap(), WrappingRange { start: 254, end: 1 });
    /// let range = WrappingRange::smallest_range_containing([1, 254], Size::from_bytes(4));
    /// assert_eq!(range.unwrap(), WrappingRange { start: 1, end: 254 });
    /// ```
    pub fn smallest_range_containing(
        values: impl IntoIterator<Item = u128>,
        size: Size,
    ) -> Option<Self> {
        let mut values: Vec<_> = values.into_iter().collect();

        let (min, max) = values
            .iter()
            .copied()
            .map(|x| (x, x))
            .reduce(|a, b| (u128::min(a.0, b.0), u128::max(a.1, b.1)))?;

        // Just checking the max is enough to ensure that everything is in-range.
        assert!(max <= size.unsigned_int_max(), "Value {max:?} is too big for {size:?}");

        // The simple answer is the non-wraparound range `min..=max`.
        let obvious_range = WrappingRange { start: min, end: max };

        // It's very common that the input was only small non-negative integers and the
        // obvious range turns out to be the best we can do.
        // Every possible wraparound range must include at least `(...=min) | (max..)`,
        // so if what we found already is at least that good, just use it.
        //     WR(min, max).width() ≤ WR(max, min).width()
        //         (max - min) % 2ⁿ ≤ (min - max) % 2ⁿ
        //                max - min ≤ min - max + 2ⁿ
        //            2×(max - min) ≤ 2ⁿ
        //                max - min ≤ 2ⁿ⁻¹
        let half_range = 1 << (size.bits() - 1);
        if max - min <= half_range {
            return Some(obvious_range);
        }

        // But every `[.., end, start, ..]` is also a potential candidate for a wraparound
        // range `(..=end) | (start..)`, so long as `start` and `end` aren't duplicates.
        values.sort_unstable();
        let wraparound_ranges = values
            .array_windows::<2>()
            .filter_map(|&[end, start]| (start != end).then_some(WrappingRange { start, end }));

        // Pick whichever range is smallest. By putting the non-wraparound range first,
        // it'll be preferred over a wraparound range with the same width.
        iter::chain(iter::once(obvious_range), wraparound_ranges).min_by_key(|r| r.width(size))
    }
}

impl fmt::Debug for WrappingRange {
    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.start > self.end {
            write!(fmt, "(..={}) | ({}..)", self.end, self.start)?;
        } else {
            write!(fmt, "{}..={}", self.start, self.end)?;
        }
        Ok(())
    }
}