triomphe/
header.rs

1use alloc::alloc::Layout;
2use alloc::boxed::Box;
3use alloc::string::String;
4use alloc::vec::Vec;
5use core::cmp::Ordering;
6use core::iter::{ExactSizeIterator, Iterator};
7use core::marker::PhantomData;
8use core::mem::{self, ManuallyDrop};
9use core::ptr::{self, addr_of_mut};
10
11use super::{Arc, ArcInner};
12
13/// Structure to allow Arc-managing some fixed-sized data and a variably-sized
14/// slice in a single allocation.
15#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, PartialOrd, Ord)]
16#[repr(C)]
17pub struct HeaderSlice<H, T: ?Sized> {
18    /// The fixed-sized data.
19    pub header: H,
20
21    /// The dynamically-sized data.
22    pub slice: T,
23}
24
25impl<H, T> Arc<HeaderSlice<H, [T]>> {
26    /// Creates an Arc for a HeaderSlice using the given header struct and
27    /// iterator to generate the slice. The resulting Arc will be fat.
28    pub fn from_header_and_iter<I>(header: H, mut items: I) -> Self
29    where
30        I: Iterator<Item = T> + ExactSizeIterator,
31    {
32        assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST");
33
34        let num_items = items.len();
35
36        let inner = Arc::allocate_for_header_and_slice(num_items);
37
38        unsafe {
39            // Write the data.
40            //
41            // Note that any panics here (i.e. from the iterator) are safe, since
42            // we'll just leak the uninitialized memory.
43            ptr::write(&mut ((*inner.as_ptr()).data.header), header);
44            let mut current = (*inner.as_ptr()).data.slice.as_mut_ptr();
45            for _ in 0..num_items {
46                ptr::write(
47                    current,
48                    items
49                        .next()
50                        .expect("ExactSizeIterator over-reported length"),
51                );
52                current = current.offset(1);
53            }
54            assert!(
55                items.next().is_none(),
56                "ExactSizeIterator under-reported length"
57            );
58        }
59
60        // Safety: ptr is valid & the inner structure is fully initialized
61        Arc {
62            p: inner,
63            phantom: PhantomData,
64        }
65    }
66
67    /// Creates an Arc for a HeaderSlice using the given header struct and
68    /// iterator to generate the slice. The resulting Arc will be fat.
69    pub fn from_header_and_slice(header: H, items: &[T]) -> Self
70    where
71        T: Copy,
72    {
73        assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST");
74
75        let num_items = items.len();
76
77        let inner = Arc::allocate_for_header_and_slice(num_items);
78
79        unsafe {
80            // Write the data.
81            ptr::write(&mut ((*inner.as_ptr()).data.header), header);
82            let dst = (*inner.as_ptr()).data.slice.as_mut_ptr();
83            ptr::copy_nonoverlapping(items.as_ptr(), dst, num_items);
84        }
85
86        // Safety: ptr is valid & the inner structure is fully initialized
87        Arc {
88            p: inner,
89            phantom: PhantomData,
90        }
91    }
92
93    /// Creates an Arc for a HeaderSlice using the given header struct and
94    /// vec to generate the slice. The resulting Arc will be fat.
95    pub fn from_header_and_vec(header: H, mut v: Vec<T>) -> Self {
96        let len = v.len();
97
98        let inner = Arc::allocate_for_header_and_slice(len);
99
100        unsafe {
101            // Safety: inner is a valid pointer, so this can't go out of bounds
102            let dst = addr_of_mut!((*inner.as_ptr()).data.header);
103
104            // Safety: `dst` is valid for writes (just allocated)
105            ptr::write(dst, header);
106        }
107
108        unsafe {
109            let src = v.as_mut_ptr();
110
111            // Safety: inner is a valid pointer, so this can't go out of bounds
112            let dst = addr_of_mut!((*inner.as_ptr()).data.slice) as *mut T;
113
114            // Safety:
115            // - `src` is valid for reads for `len` (got from `Vec`)
116            // - `dst` is valid for writes for `len` (just allocated, with layout for appropriate slice)
117            // - `src` and `dst` don't overlap (separate allocations)
118            ptr::copy_nonoverlapping(src, dst, len);
119
120            // Deallocate vec without dropping `T`
121            //
122            // Safety: 0..0 elements are always initialized, 0 <= cap for any cap
123            v.set_len(0);
124        }
125
126        // Safety: ptr is valid & the inner structure is fully initialized
127        Arc {
128            p: inner,
129            phantom: PhantomData,
130        }
131    }
132}
133
134impl<H> Arc<HeaderSlice<H, str>> {
135    /// Creates an Arc for a HeaderSlice using the given header struct and
136    /// a str slice to generate the slice. The resulting Arc will be fat.
137    pub fn from_header_and_str(header: H, string: &str) -> Self {
138        let bytes = Arc::from_header_and_slice(header, string.as_bytes());
139
140        // Safety: `ArcInner` and `HeaderSlice` are `repr(C)`, `str` has the same layout as `[u8]`,
141        //         thus it's ok to "transmute" between `Arc<HeaderSlice<H, [u8]>>` and `Arc<HeaderSlice<H, str>>`.
142        //
143        //         `bytes` are a valid string since we've just got them from a valid `str`.
144        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(bytes) as _) }
145    }
146}
147
148/// Header data with an inline length. Consumers that use HeaderWithLength as the
149/// Header type in HeaderSlice can take advantage of ThinArc.
150#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
151#[repr(C)]
152pub struct HeaderWithLength<H> {
153    /// The fixed-sized data.
154    pub header: H,
155
156    /// The slice length.
157    pub length: usize,
158}
159
160impl<H> HeaderWithLength<H> {
161    /// Creates a new HeaderWithLength.
162    #[inline]
163    pub fn new(header: H, length: usize) -> Self {
164        HeaderWithLength { header, length }
165    }
166}
167
168impl<T: ?Sized> From<Arc<HeaderSlice<(), T>>> for Arc<T> {
169    fn from(this: Arc<HeaderSlice<(), T>>) -> Self {
170        debug_assert_eq!(
171            Layout::for_value::<HeaderSlice<(), T>>(&this),
172            Layout::for_value::<T>(&this.slice)
173        );
174
175        // Safety: `HeaderSlice<(), T>` and `T` has the same layout
176        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(this) as _) }
177    }
178}
179
180impl<T: ?Sized> From<Arc<T>> for Arc<HeaderSlice<(), T>> {
181    fn from(this: Arc<T>) -> Self {
182        // Safety: `T` and `HeaderSlice<(), T>` has the same layout
183        unsafe { Arc::from_raw_inner(Arc::into_raw_inner(this) as _) }
184    }
185}
186
187impl<T: Copy> From<&[T]> for Arc<[T]> {
188    fn from(slice: &[T]) -> Self {
189        Arc::from_header_and_slice((), slice).into()
190    }
191}
192
193impl From<&str> for Arc<str> {
194    fn from(s: &str) -> Self {
195        Arc::from_header_and_str((), s).into()
196    }
197}
198
199impl From<String> for Arc<str> {
200    fn from(s: String) -> Self {
201        Self::from(&s[..])
202    }
203}
204
205// FIXME: once `pointer::with_metadata_of` is stable or
206//        implementable on stable without assuming ptr layout
207//        this will be able to accept `T: ?Sized`.
208impl<T> From<Box<T>> for Arc<T> {
209    fn from(b: Box<T>) -> Self {
210        let layout = Layout::for_value::<T>(&b);
211
212        // Safety: the closure only changes the type of the pointer
213        let inner = unsafe { Self::allocate_for_layout(layout, |mem| mem as *mut ArcInner<T>) };
214
215        unsafe {
216            let src = Box::into_raw(b);
217
218            // Safety: inner is a valid pointer, so this can't go out of bounds
219            let dst = addr_of_mut!((*inner.as_ptr()).data);
220
221            // Safety:
222            // - `src` is valid for reads (got from `Box`)
223            // - `dst` is valid for writes (just allocated)
224            // - `src` and `dst` don't overlap (separate allocations)
225            ptr::copy_nonoverlapping(src, dst, 1);
226
227            // Deallocate box without dropping `T`
228            //
229            // Safety:
230            // - `src` has been got from `Box::into_raw`
231            // - `ManuallyDrop<T>` is guaranteed to have the same layout as `T`
232            drop(Box::<ManuallyDrop<T>>::from_raw(src as _));
233        }
234
235        Arc {
236            p: inner,
237            phantom: PhantomData,
238        }
239    }
240}
241
242impl<T> From<Vec<T>> for Arc<[T]> {
243    fn from(v: Vec<T>) -> Self {
244        Arc::from_header_and_vec((), v).into()
245    }
246}
247
248/// A type wrapping `HeaderSlice<HeaderWithLength<H>, T>` that is used internally in `ThinArc`.
249///
250/// # Safety
251///
252/// Safety-usable invariants:
253///
254/// - This is guaranteed to have the same representation as `HeaderSlice<HeaderWithLength<H>, [T]>`
255/// - The header length (`.length()`) is checked to be the slice length
256#[derive(Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
257#[repr(transparent)]
258pub struct HeaderSliceWithLengthProtected<H, T> {
259    // Invariant: the header's length field must be the slice length
260    inner: HeaderSliceWithLengthUnchecked<H, T>,
261}
262
263pub(crate) type HeaderSliceWithLengthUnchecked<H, T> = HeaderSlice<HeaderWithLength<H>, [T]>;
264
265impl<H, T> HeaderSliceWithLengthProtected<H, T> {
266    pub fn header(&self) -> &H {
267        &self.inner.header.header
268    }
269    pub fn header_mut(&mut self) -> &mut H {
270        // Safety: only the length is unsafe to mutate
271        &mut self.inner.header.header
272    }
273    pub fn length(&self) -> usize {
274        self.inner.header.length
275    }
276
277    pub fn slice(&self) -> &[T] {
278        &self.inner.slice
279    }
280    pub fn slice_mut(&mut self) -> &mut [T] {
281        // Safety: only the length is unsafe to mutate
282        &mut self.inner.slice
283    }
284    pub(crate) fn inner(&self) -> &HeaderSliceWithLengthUnchecked<H, T> {
285        // This is safe in an immutable context
286        &self.inner
287    }
288}
289
290impl<H: PartialOrd, T: ?Sized + PartialOrd> PartialOrd for HeaderSlice<HeaderWithLength<H>, T> {
291    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
292        (&self.header.header, &self.slice).partial_cmp(&(&other.header.header, &other.slice))
293    }
294}
295
296impl<H: Ord, T: ?Sized + Ord> Ord for HeaderSlice<HeaderWithLength<H>, T> {
297    fn cmp(&self, other: &Self) -> Ordering {
298        (&self.header.header, &self.slice).cmp(&(&other.header.header, &other.slice))
299    }
300}
301
302#[cfg(test)]
303mod tests {
304    use alloc::boxed::Box;
305    use alloc::string::String;
306    use alloc::vec;
307    use core::iter;
308
309    use crate::{Arc, HeaderSlice};
310
311    #[test]
312    fn from_header_and_iter_smoke() {
313        let arc = Arc::from_header_and_iter(
314            (42u32, 17u8),
315            IntoIterator::into_iter([1u16, 2, 3, 4, 5, 6, 7]),
316        );
317
318        assert_eq!(arc.header, (42, 17));
319        assert_eq!(arc.slice, [1, 2, 3, 4, 5, 6, 7]);
320    }
321
322    #[test]
323    fn from_header_and_slice_smoke() {
324        let arc = Arc::from_header_and_slice((42u32, 17u8), &[1u16, 2, 3, 4, 5, 6, 7]);
325
326        assert_eq!(arc.header, (42, 17));
327        assert_eq!(arc.slice, [1u16, 2, 3, 4, 5, 6, 7]);
328    }
329
330    #[test]
331    fn from_header_and_vec_smoke() {
332        let arc = Arc::from_header_and_vec((42u32, 17u8), vec![1u16, 2, 3, 4, 5, 6, 7]);
333
334        assert_eq!(arc.header, (42, 17));
335        assert_eq!(arc.slice, [1u16, 2, 3, 4, 5, 6, 7]);
336    }
337
338    #[test]
339    fn from_header_and_iter_empty() {
340        let arc = Arc::from_header_and_iter((42u32, 17u8), iter::empty::<u16>());
341
342        assert_eq!(arc.header, (42, 17));
343        assert_eq!(arc.slice, []);
344    }
345
346    #[test]
347    fn from_header_and_slice_empty() {
348        let arc = Arc::from_header_and_slice((42u32, 17u8), &[1u16; 0]);
349
350        assert_eq!(arc.header, (42, 17));
351        assert_eq!(arc.slice, []);
352    }
353
354    #[test]
355    fn from_header_and_vec_empty() {
356        let arc = Arc::from_header_and_vec((42u32, 17u8), vec![1u16; 0]);
357
358        assert_eq!(arc.header, (42, 17));
359        assert_eq!(arc.slice, []);
360    }
361
362    #[test]
363    fn issue_13_empty() {
364        crate::Arc::from_header_and_iter((), iter::empty::<usize>());
365    }
366
367    #[test]
368    fn issue_13_consumption() {
369        let s: &[u8] = &[0u8; 255];
370        crate::Arc::from_header_and_iter((), s.iter().copied());
371    }
372
373    #[test]
374    fn from_header_and_str_smoke() {
375        let a = Arc::from_header_and_str(
376            42,
377            "The answer to the ultimate question of life, the universe, and everything",
378        );
379        assert_eq!(a.header, 42);
380        assert_eq!(
381            &a.slice,
382            "The answer to the ultimate question of life, the universe, and everything"
383        );
384
385        let empty = Arc::from_header_and_str((), "");
386        assert_eq!(&empty.slice, "");
387    }
388
389    #[test]
390    fn erase_and_create_from_thin_air_header() {
391        let a: Arc<HeaderSlice<(), [u32]>> = Arc::from_header_and_slice((), &[12, 17, 16]);
392        let b: Arc<[u32]> = a.into();
393
394        assert_eq!(&*b, [12, 17, 16]);
395
396        let c: Arc<HeaderSlice<(), [u32]>> = b.into();
397
398        assert_eq!(&c.slice, [12, 17, 16]);
399    }
400
401    #[test]
402    fn from_box_and_vec() {
403        let b = Box::new(String::from("xxx"));
404        let b = Arc::<String>::from(b);
405        assert_eq!(&*b, "xxx");
406
407        let v = vec![String::from("1"), String::from("2"), String::from("3")];
408        let v = Arc::<[_]>::from(v);
409        assert_eq!(
410            &*v,
411            [String::from("1"), String::from("2"), String::from("3")]
412        );
413
414        let mut v = vec![String::from("1"), String::from("2"), String::from("3")];
415        v.reserve(10);
416        let v = Arc::<[_]>::from(v);
417        assert_eq!(
418            &*v,
419            [String::from("1"), String::from("2"), String::from("3")]
420        );
421    }
422
423    /// It’s possible to make a generic `Arc` wrapper that supports both:
424    ///
425    /// * `T: !Sized`
426    /// * `Arc::make_mut` if `T: Sized`
427    #[test]
428    fn dst_and_make_mut() {
429        struct MyArc<T: ?Sized>(Arc<HeaderSlice<MyHeader, T>>);
430
431        #[derive(Clone)]
432        struct MyHeader {
433            // Very interesting things go here
434        }
435
436        // MyArc<str> is possible
437        let dst: MyArc<str> = MyArc(Arc::from_header_and_str(MyHeader {}, "example"));
438        assert_eq!(&dst.0.slice, "example");
439
440        // `make_mut` is still available when `T: Sized`
441        let mut answer: MyArc<u32> = MyArc(Arc::new(HeaderSlice {
442            header: MyHeader {},
443            // Not actually a slice in this case,
444            // but `HeaderSlice` is required to use `from_header_and_str`
445            // and we want the same `MyArc` to support both cases.
446            slice: 6 * 9,
447        }));
448        let mut_ref = Arc::make_mut(&mut answer.0);
449        mut_ref.slice = 42;
450    }
451}
triomphe/header.rs

triomphe/
header.rs
