1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
use alloc::vec::Vec;
use crate::rustc_data_structures::iter_ext::SliceExt as _;
use core::ops::RangeFull;
use core::{fmt, iter};
use crate::rustc_abi::Size;
#[cfg(feature = "nightly")]
use crate::rustc_abi::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 frontend::rustc_abi::{Size, WrappingRange};
///
/// let chain = core::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
.windows_array::<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(())
}
}