| use std::fmt; |
| use std::ops::RangeFull; |
| |
| 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 range = WrappingRange::smallest_range_containing([2, 6, 12, 4], Size::from_bytes(2)); |
| /// assert_eq!(range.unwrap(), WrappingRange { start: 2, end: 12 }); |
| /// |
| /// let range = WrappingRange::smallest_range_containing(0..=127, Size::from_bytes(1)); |
| /// assert_eq!(range.unwrap(), WrappingRange { start: 0, end: 127 }); |
| /// let range = WrappingRange::smallest_range_containing([129, 128, 127], Size::from_bytes(1)); |
| /// assert_eq!(range.unwrap(), WrappingRange { start: 127, end: 129 }); |
| /// |
| /// // 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 }); |
| /// |
| /// // Both `100..=228` and `..=228 | 100..` are the same size, but we pick the one without zero. |
| /// let range = WrappingRange::smallest_range_containing([100, 228], Size::from_bytes(1)); |
| /// assert_eq!(range.unwrap(), WrappingRange { start: 100, end: 228 }); |
| /// // These 4 values are evenly spaced so all 4 candidate ranges have length 193: |
| /// // `(..=32) | (96..)`, `(..=96) | (160..)`, `(..=160) | (224..)`, and `32..=224`. |
| /// // We pick the last one as the only one that doesn't contain zero. |
| /// let range = WrappingRange::smallest_range_containing([0xA0, 0xE0, 0x20, 0x60], Size::from_bytes(1)); |
| /// assert_eq!(range.unwrap(), WrappingRange { start: 0x20, end: 0xE0 }); |
| /// ``` |
| pub fn smallest_range_containing( |
| values: impl IntoIterator<Item = u128>, |
| size: Size, |
| ) -> Option<Self> { |
| let mut values: Vec<_> = values.into_iter().collect(); |
| let umax = size.unsigned_int_max(); |
| for value in &values { |
| debug_assert!(*value <= umax, "Value {value:?} is too big for {size:?}"); |
| } |
| values.sort_unstable(); |
| |
| // Having sorted all the values, every element is a possible start point for the |
| // range of values, up to the previous element (wrapping around the end of the vec). |
| // Look at all those candidates and pick the one that's as narrow as possible. |
| let pairs = std::iter::zip(values.iter().copied(), values.iter().copied().cycle().skip(1)); |
| let ranges = pairs.map(|(end, start)| WrappingRange { start, end }); |
| let smallest_range = ranges.min_by_key(|r| (r.width(size), r.start)); |
| smallest_range |
| } |
| } |
| |
| 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(()) |
| } |
| } |
