talc/
span.rs

1use core::ops::Range;
2
3use crate::ptr_utils::*;
4
5/// Represents an interval of memory `[base, acme)`
6///
7/// Use `get_base_acme` to retrieve `base` and `acme` directly.
8///
9/// # Empty Spans
10/// Note that where `base >= acme`, the [`Span`] is considered empty, in which case
11/// the specific values of `base` and `acme` are considered meaningless.
12/// * Empty spans contain nothing and overlap with nothing.
13/// * Empty spans are contained by any sized span.
14#[derive(Clone, Copy, Hash)]
15pub struct Span {
16    base: *mut u8,
17    acme: *mut u8,
18}
19
20unsafe impl Send for Span {}
21
22impl Default for Span {
23    fn default() -> Self {
24        Self::empty()
25    }
26}
27
28impl core::fmt::Debug for Span {
29    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
30        f.write_fmt(format_args!("{:p}..[{}]..{:p}", self.base, self.size(), self.acme))
31    }
32}
33
34impl core::fmt::Display for Span {
35    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
36        match self.get_base_acme() {
37            Some((base, acme)) => f.write_fmt(format_args!("{:p}..{:p}", base, acme)),
38            None => f.write_str("Empty Span"),
39        }
40    }
41}
42
43impl<T> From<Range<*mut T>> for Span {
44    fn from(value: Range<*mut T>) -> Self {
45        Self { base: value.start.cast(), acme: value.end.cast() }
46    }
47}
48
49// NOTE: This should be removed in a future release as it encouraged UB.
50//   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
51//   See: https://github.com/SFBdragon/talc/issues/33
52impl<T> From<Range<*const T>> for Span {
53    fn from(value: Range<*const T>) -> Self {
54        Self { base: value.start.cast_mut().cast(), acme: value.end.cast_mut().cast() }
55    }
56}
57
58impl<T> From<&mut [T]> for Span {
59    fn from(value: &mut [T]) -> Self {
60        Self::from(value.as_mut_ptr_range())
61    }
62}
63
64// NOTE: This should be removed in a future release as it encouraged UB.
65//   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
66//   See: https://github.com/SFBdragon/talc/issues/33
67impl<T> From<&[T]> for Span {
68    fn from(value: &[T]) -> Self {
69        Self::from(value.as_ptr_range())
70    }
71}
72
73impl<T, const N: usize> From<&mut [T; N]> for Span {
74    fn from(value: &mut [T; N]) -> Self {
75        Self::from(value as *mut [T; N])
76    }
77}
78
79// NOTE: This should be removed in a future release as it encouraged UB.
80//   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
81//   See: https://github.com/SFBdragon/talc/issues/33
82impl<T, const N: usize> From<&[T; N]> for Span {
83    fn from(value: &[T; N]) -> Self {
84        Self::from(value as *const [T; N])
85    }
86}
87
88#[cfg(feature = "nightly_api")]
89impl<T> From<*mut [T]> for Span {
90    fn from(value: *mut [T]) -> Self {
91        Self::from_slice(value)
92    }
93}
94
95// NOTE: This should be removed in a future release as it encouraged UB.
96//   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
97//   See: https://github.com/SFBdragon/talc/issues/33
98#[cfg(feature = "nightly_api")]
99impl<T> From<*const [T]> for Span {
100    fn from(value: *const [T]) -> Self {
101        #[expect(deprecated)] // This impl is 'deprecated' too.
102        Self::from_const_slice(value)
103    }
104}
105
106impl<T, const N: usize> From<*mut [T; N]> for Span {
107    fn from(value: *mut [T; N]) -> Self {
108        Self::from_array(value)
109    }
110}
111
112// NOTE: This should be removed in a future release as it encouraged UB.
113//   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
114//   See: https://github.com/SFBdragon/talc/issues/33
115impl<T, const N: usize> From<*const [T; N]> for Span {
116    fn from(value: *const [T; N]) -> Self {
117        Self::from_array(value.cast_mut())
118    }
119}
120
121impl PartialEq for Span {
122    fn eq(&self, other: &Self) -> bool {
123        self.is_empty() && other.is_empty() || self.base == other.base && self.acme == other.acme
124    }
125}
126impl Eq for Span {}
127
128impl Span {
129    /// Returns whether `base >= acme`.
130    #[inline]
131    pub fn is_empty(self) -> bool {
132        self.acme <= self.base
133    }
134
135    /// Returns whether `base < acme`.
136    #[inline]
137    pub fn is_sized(self) -> bool {
138        !self.is_empty()
139    }
140
141    /// Returns the size of the span, else zero if `base >= span`.
142    #[inline]
143    pub fn size(self) -> usize {
144        if self.is_empty() { 0 } else { self.acme as usize - self.base as usize }
145    }
146
147    /// If `self` isn't empty, returns `(base, acme)`
148    #[inline]
149    pub fn get_base_acme(self) -> Option<(*mut u8, *mut u8)> {
150        if self.is_empty() { None } else { Some((self.base, self.acme)) }
151    }
152
153    /// Create an empty span.
154    #[inline]
155    pub const fn empty() -> Self {
156        Self { base: core::ptr::null_mut(), acme: core::ptr::null_mut() }
157    }
158
159    /// Create a new span.
160    #[inline]
161    pub const fn new(base: *mut u8, acme: *mut u8) -> Self {
162        Self { base, acme }
163    }
164
165    /// Creates a [`Span`] given a `base` and a `size`.
166    ///
167    /// If `base + size` overflows, the result is empty.
168    #[inline]
169    pub const fn from_base_size(base: *mut u8, size: usize) -> Self {
170        Self { base, acme: base.wrapping_add(size) }
171    }
172
173    #[cfg(feature = "nightly_api")]
174    #[inline]
175    pub const fn from_slice<T>(slice: *mut [T]) -> Self {
176        Self {
177            base: slice as *mut T as *mut u8,
178            // SAFETY: pointing directly after an object is considered
179            // within the same object
180            acme: unsafe { (slice as *mut T).add(slice.len()).cast() },
181        }
182    }
183
184    // NOTE: This should be removed in a future release as it encouraged UB.
185    //   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
186    //   See: https://github.com/SFBdragon/talc/issues/33
187    #[deprecated = "Conversion from const references encourages UB. This will be removed in a future release."]
188    #[cfg(feature = "nightly_api")]
189    #[inline]
190    pub const fn from_const_slice<T>(slice: *const [T]) -> Self {
191        Self {
192            base: slice as *mut T as *mut u8,
193            // SAFETY: pointing directly after an object is considered
194            // within the same object
195            acme: unsafe { (slice as *mut T).add(slice.len()).cast() },
196        }
197    }
198
199    #[inline]
200    pub const fn from_array<T, const N: usize>(array: *mut [T; N]) -> Self {
201        Self {
202            base: array as *mut T as *mut u8,
203            // SAFETY: pointing directly after an object is considered
204            // within the same object
205            acme: unsafe { (array as *mut T).add(N).cast() },
206        }
207    }
208
209    // NOTE: This should be removed in a future release as it encouraged UB.
210    //   Once `const_mut_refs` is stabilized in Rust, this will no longer be useful anyway.
211    //   See: https://github.com/SFBdragon/talc/issues/33
212    #[deprecated = "Conversion from const references encourages UB. This will be removed in a future release."]
213    #[inline]
214    pub const fn from_const_array<T, const N: usize>(array: *const [T; N]) -> Self {
215        Self {
216            base: array as *mut T as *mut u8,
217            // SAFETY: pointing directly after an object is considered
218            // within the same object
219            acme: unsafe { (array as *mut T).add(N).cast() },
220        }
221    }
222
223    /// Returns `None` if `self` is empty.
224    #[inline]
225    pub fn to_ptr_range(self) -> Option<Range<*mut u8>> {
226        if self.is_empty() { None } else { Some(self.base..self.acme) }
227    }
228
229    /// Returns `None` if `self` is empty.
230    #[inline]
231    pub fn to_slice(self) -> Option<*mut [u8]> {
232        if self.is_empty() {
233            None
234        } else {
235            Some(core::ptr::slice_from_raw_parts_mut(self.base, self.size()))
236        }
237    }
238
239    /// Returns whether `self` contains `addr`.
240    ///
241    /// Empty spans contain nothing.
242    #[inline]
243    pub fn contains(self, ptr: *mut u8) -> bool {
244        // if self is empty, this always evaluates to false
245        self.base <= ptr && ptr < self.acme
246    }
247
248    /// Returns whether `self` contains `other`.
249    ///
250    /// Empty spans are contained by any span, even empty ones.
251    #[inline]
252    pub fn contains_span(self, other: Span) -> bool {
253        other.is_empty() || self.base <= other.base && other.acme <= self.acme
254    }
255
256    /// Returns whether some of `self` overlaps with `other`.
257    ///
258    /// Empty spans don't overlap with anything.
259    #[inline]
260    pub fn overlaps(self, other: Span) -> bool {
261        self.is_sized() && other.is_sized() && !(other.base >= self.acme || self.base >= other.acme)
262    }
263
264    /// Aligns `base` upward and `acme` downward by `align_of::<usize>()`.
265    #[inline]
266    pub fn word_align_inward(self) -> Self {
267        if ALIGN > usize::MAX - self.base as usize {
268            Self::empty()
269        } else {
270            Self { base: align_up(self.base), acme: align_down(self.acme) }
271        }
272    }
273    /// Aligns `base` downward and `acme` upward by `align_of::<usize>()`.
274    #[inline]
275    pub fn word_align_outward(self) -> Self {
276        if ALIGN > usize::MAX - self.acme as usize {
277            panic!("aligning acme upward would overflow!");
278        }
279
280        Self { base: align_down(self.base), acme: align_up(self.acme) }
281    }
282
283    /// Raises `base` if `base` is smaller than `min`.
284    #[inline]
285    pub fn above(self, min: *mut u8) -> Self {
286        Self { base: if min > self.base { min } else { self.base }, acme: self.acme }
287    }
288    /// Lowers `acme` if `acme` is greater than `max`.
289    #[inline]
290    pub fn below(self, max: *mut u8) -> Self {
291        Self { base: self.base, acme: if max < self.acme { max } else { self.acme } }
292    }
293
294    /// Returns the [`Span`]s of `self` below and above the `exclude` span, respectively.
295    /// Alternatively worded, the set difference `self`\\`exclude`.
296    /// 
297    /// If `exclude` is empty, `self` and an empty `Span` are returned.
298    #[inline]
299    pub fn except(self, exclude: Span) -> (Self, Self) {
300        match exclude.get_base_acme() {
301            Some((base, acme)) => (self.below(base), self.above(acme)),
302            None => (self, Span::empty()),
303        }
304    }
305
306    /// Returns a span that `other` contains by raising `base` or lowering `acme`.
307    ///
308    /// If `other` is empty, returns `other`.
309    #[inline]
310    pub fn fit_within(self, other: Span) -> Self {
311        if other.is_empty() {
312            other
313        } else {
314            Self {
315                base: if other.base > self.base { other.base } else { self.base },
316                acme: if other.acme < self.acme { other.acme } else { self.acme },
317            }
318        }
319    }
320    /// Returns a span that contains `other` by extending `self`.
321    ///
322    /// If `other` is empty, returns `self`, as all spans contain any empty span.
323    #[inline]
324    pub fn fit_over(self, other: Self) -> Self {
325        if other.is_empty() {
326            self
327        } else {
328            Self {
329                base: if other.base < self.base { other.base } else { self.base },
330                acme: if other.acme > self.acme { other.acme } else { self.acme },
331            }
332        }
333    }
334
335    /// Lower `base` by `low` and raise `acme` by `high`.
336    ///
337    /// Does nothing if `self` is empty.
338    ///
339    /// # Panics
340    /// Panics if lowering `base` by `low` or raising `acme` by `high` under/overflows.
341    #[inline]
342    pub fn extend(self, low: usize, high: usize) -> Self {
343        if self.is_empty() {
344            self
345        } else {
346            assert!((self.base as usize).checked_sub(low).is_some());
347            assert!((self.acme as usize).checked_add(high).is_some());
348
349            Self { base: self.base.wrapping_sub(low), acme: self.acme.wrapping_add(high) }
350        }
351    }
352
353    /// Raise `base` by `low` and lower `acme` by `high`.
354    ///
355    /// If `self` is empty, `self` is returned.
356    ///
357    /// If either operation would wrap around the address space, an empty span is returned.
358    #[inline]
359    pub fn truncate(self, low: usize, high: usize) -> Span {
360        if self.is_empty() {
361            self
362        } else if (self.base as usize).checked_add(low).is_none()
363            || (self.acme as usize).checked_sub(high).is_none()
364        {
365            Span::empty()
366        } else {
367            Self {
368                // if either boundary saturates, the span will be empty thereafter, as expected
369                base: self.base.wrapping_add(low),
370                acme: self.acme.wrapping_sub(high),
371            }
372        }
373    }
374}
375
376#[cfg(test)]
377mod test {
378    use super::*;
379
380    fn ptr(addr: usize) -> *mut u8 {
381        // don't ` as usize` to avoid upsetting miri too much
382        core::ptr::null_mut::<u8>().wrapping_add(addr)
383    }
384
385    #[test]
386    fn test_span() {
387        let base = 1234usize;
388        let acme = 5678usize;
389
390        let bptr = ptr(base);
391        let aptr = ptr(acme);
392
393        let span = Span::from(bptr..aptr);
394        assert!(!span.is_empty());
395        assert!(span.size() == acme - base);
396
397        assert!(
398            span.word_align_inward()
399                == Span::new(
400                    bptr.wrapping_add(ALIGN - 1)
401                        .wrapping_sub(bptr.wrapping_add(ALIGN - 1) as usize & (ALIGN - 1)),
402                    aptr.wrapping_sub(acme & (ALIGN - 1))
403                )
404        );
405        assert!(
406            span.word_align_outward()
407                == Span::new(
408                    bptr.wrapping_sub(base & (ALIGN - 1)),
409                    aptr.wrapping_add(ALIGN - 1)
410                        .wrapping_sub(aptr.wrapping_add(ALIGN - 1) as usize & (ALIGN - 1))
411                )
412        );
413
414        assert_eq!(span.above(ptr(2345)), Span::new(ptr(2345), aptr));
415        assert_eq!(span.below(ptr(7890)), Span::new(bptr, aptr));
416        assert_eq!(span.below(ptr(3456)), Span::new(bptr, ptr(3456)));
417        assert_eq!(span.below(ptr(0123)), Span::empty());
418        assert_eq!(span.above(ptr(7890)), Span::empty());
419
420        assert_eq!(
421            span.except(Span::new(ptr(base + 1111), ptr(acme - 1111))),
422            (Span::new(bptr, ptr(base + 1111)), Span::new(ptr(acme - 1111), aptr))
423        );
424        assert_eq!(
425            span.except(Span::new(ptr(base + 1111), ptr(acme + 1111))),
426            (Span::new(bptr, ptr(base + 1111)), Span::empty())
427        );
428        assert_eq!(
429            span.except(Span::new(ptr(base - 1111), ptr(acme + 1111))),
430            (Span::empty(), Span::empty())
431        );
432        assert_eq!(span.except(Span::empty()), (span, Span::empty()));
433
434        assert!(span.fit_over(Span::empty()) == span);
435        assert!(span.fit_within(Span::empty()).is_empty());
436        assert!(span.fit_within(Span::new(ptr(0), ptr(10000))) == span);
437        assert!(span.fit_over(Span::new(ptr(0), ptr(10000))) == Span::new(ptr(0), ptr(10000)));
438        assert!(span.fit_within(Span::new(ptr(4000), ptr(10000))) == Span::new(ptr(4000), aptr));
439        assert!(span.fit_over(Span::new(ptr(4000), ptr(10000))) == Span::new(bptr, ptr(10000)));
440
441        assert!(span.extend(1234, 1010) == Span::new(ptr(0), ptr(5678 + 1010)));
442        assert!(span.truncate(1234, 1010) == Span::new(ptr(1234 + 1234), ptr(5678 - 1010)));
443        assert!(span.truncate(235623, 45235772).is_empty());
444    }
445}
talc/span.rs

talc/
span.rs
