1#![no_std]
36extern crate alloc;
37
38use {
39 crate::polyfill::*,
40 alloc::{
41 alloc::{alloc, dealloc, handle_alloc_error, Layout, LayoutErr},
42 boxed::Box,
43 rc::Rc,
44 sync::Arc,
45 },
46 core::{
47 cmp::{self, PartialEq},
48 fmt::{self, Debug},
49 hash,
50 marker::PhantomData,
51 mem::ManuallyDrop,
52 ops::{Deref, DerefMut},
53 ptr::{self, NonNull},
54 },
55};
56
57mod polyfill;
58
59pub type ErasedPtr = NonNull<priv_in_pub::Erased>;
61#[doc(hidden)]
62pub mod priv_in_pub {
63 pub struct Erased {
68 #[allow(unused)]
69 raw: u8,
70 }
71}
72
73#[repr(C)]
83#[derive(Debug, Eq, PartialEq, Hash)]
84pub struct ThinData<Head, SliceItem> {
85 len: usize,
96 pub head: Head,
98 pub slice: [SliceItem],
100}
101
102impl<Head, SliceItem> ThinData<Head, SliceItem> {
103 fn len(ptr: ErasedPtr) -> NonNull<usize> {
104 ptr.cast()
105 }
106
107 fn erase(ptr: NonNull<Self>) -> ErasedPtr {
108 ptr.cast()
109 }
110
111 unsafe fn fatten_const(ptr: ErasedPtr) -> NonNull<Self> {
112 let len = ptr::read(Self::len(ptr).as_ptr());
113 let slice = make_slice(ptr.cast::<SliceItem>().as_ptr(), len);
114 NonNull::new_unchecked(slice as *const Self as *mut Self)
115 }
116
117 unsafe fn fatten_mut(ptr: ErasedPtr) -> NonNull<Self> {
118 let len = ptr::read(Self::len(ptr).as_ptr());
119 let slice = make_slice_mut(ptr.cast::<SliceItem>().as_ptr(), len);
120 NonNull::new_unchecked(slice as *mut Self)
121 }
122}
123
124impl<SliceItem: PartialEq> PartialEq<[SliceItem]> for ThinData<(), SliceItem> {
125 fn eq(&self, other: &[SliceItem]) -> bool {
126 &self.slice == other
127 }
128}
129
130macro_rules! thin_holder {
131 ( #[nodrop] for $thin:ident<$($a:lifetime,)* Head, SliceItem> as $fat:ident<$($b:lifetime,)* ThinData<Head, SliceItem>> with $fatten:ident ) => {
132 impl<$($a,)* Head, SliceItem> $thin<$($a,)* Head, SliceItem> {
133 pub unsafe fn from_erased(ptr: ErasedPtr) -> Self {
139 Self {
140 raw: ptr,
141 marker: PhantomData,
142 }
143 }
144
145 pub fn erase(this: Self) -> ErasedPtr {
150 let this = ManuallyDrop::new(this);
151 this.raw
152 }
153 }
154
155 impl<$($a,)* Head, SliceItem> From<$fat<$($b,)* ThinData<Head, SliceItem>>> for $thin<$($a,)* Head, SliceItem> {
156 fn from(this: $fat<$($b,)* ThinData<Head, SliceItem>>) -> $thin<$($a,)* Head, SliceItem> {
157 unsafe {
158 let this = NonNull::new_unchecked($fat::into_raw(this) as *mut _);
159 Self::from_erased(ThinData::<Head, SliceItem>::erase(this))
160 }
161 }
162 }
163
164 impl<$($a,)* Head, SliceItem> Deref for $thin<$($a,)* Head, SliceItem>
165 where
166 $fat<$($b,)* ThinData<Head, SliceItem>>: Deref,
167 {
168 type Target = ThinData<Head, SliceItem>;
169 fn deref(&self) -> &ThinData<Head, SliceItem> {
170 unsafe { &*ThinData::fatten_const(self.raw).as_ptr() }
171 }
172 }
173
174 impl<$($a,)* Head, SliceItem> DerefMut for $thin<$($a,)* Head, SliceItem>
175 where
176 $fat<$($b,)* ThinData<Head, SliceItem>>: DerefMut,
177 {
178 fn deref_mut(&mut self) -> &mut ThinData<Head, SliceItem> {
179 unsafe { &mut *ThinData::fatten_mut(self.raw).as_ptr() }
180 }
181 }
182
183 impl<$($a,)* Head, SliceItem> Debug for $thin<$($a,)* Head, SliceItem>
184 where
185 $fat<$($b,)* ThinData<Head, SliceItem>>: Debug,
186 {
187 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
188 unsafe {
189 let this = ManuallyDrop::new($fat::from_raw(ThinData::fatten_const(self.raw).as_ptr()));
190 this.fmt(f)
191 }
192 }
193 }
194
195 unsafe impl<$($a,)* Head, SliceItem> Send for $thin<$($a,)* Head, SliceItem> where
196 $fat<$($b,)* ThinData<Head, SliceItem>>: Send
197 {
198 }
199 unsafe impl<$($a,)* Head, SliceItem> Sync for $thin<$($a,)* Head, SliceItem> where
200 $fat<$($b,)* ThinData<Head, SliceItem>>: Sync
201 {
202 }
203
204 impl<$($a,)* Head, SliceItem> cmp::Eq for $thin<$($a,)* Head, SliceItem> where
205 $fat<$($b,)* ThinData<Head, SliceItem>>: cmp::Eq,
206 {
207 }
208 impl<$($a,)* Head, SliceItem> PartialEq for $thin<$($a,)* Head, SliceItem>
209 where
210 $fat<$($b,)* ThinData<Head, SliceItem>>: PartialEq,
211 {
212 fn eq(&self, other: &Self) -> bool {
213 unsafe {
214 let other = ManuallyDrop::new($fat::from_raw(ThinData::fatten_const(other.raw).as_ptr()));
215 <Self as PartialEq<$fat<$($b,)* ThinData<Head, SliceItem>>>>::eq(self, &other)
216 }
217 }
218 }
219 impl<$($a,)* Head, SliceItem> PartialEq<$fat<$($b,)* ThinData<Head, SliceItem>>> for $thin<$($a,)* Head, SliceItem>
220 where
221 $fat<$($b,)* ThinData<Head, SliceItem>>: PartialEq,
222 {
223 fn eq(&self, other: &$fat<$($b,)* ThinData<Head, SliceItem>>) -> bool {
224 unsafe {
225 let this = ManuallyDrop::new($fat::from_raw(ThinData::fatten_const(self.raw).as_ptr()));
226 <$fat<$($b,)* ThinData<Head, SliceItem>> as PartialEq>::eq(&this, other)
227 }
228 }
229 }
230
231 impl<$($a,)* Head, SliceItem> hash::Hash for $thin<$($a,)* Head, SliceItem>
232 where
233 $fat<$($b,)* ThinData<Head, SliceItem>>: hash::Hash,
234 {
235 fn hash<H>(&self, state: &mut H)
236 where
237 H: hash::Hasher,
238 {
239 unsafe {
240 let this = ManuallyDrop::new($fat::from_raw(ThinData::fatten_const(self.raw).as_ptr()));
241 <$fat<$($b,)* ThinData<Head, SliceItem>> as hash::Hash>::hash(&this, state)
242 }
243 }
244 }
245 };
246 ( for $thin:ident<$($a:lifetime,)* Head, SliceItem> as $fat:ident<$($b:lifetime,)* ThinData<Head, SliceItem>> with $fatten:ident ) => {
247 impl<$($a,)* Head, SliceItem> Drop for $thin<$($a,)* Head, SliceItem> {
248 fn drop(&mut self) {
249 let this = unsafe { $fat::from_raw(ThinData::$fatten(self.raw).as_ptr()) };
250 drop::<$fat<$($b,)* ThinData<Head, SliceItem>>>(this)
251 }
252 }
253
254 thin_holder!(#[nodrop] for $thin<$($a,)* Head, SliceItem> as $fat<$($b,)* ThinData<Head, SliceItem>> with $fatten );
255 };
256}
257
258pub struct ThinBox<Head, SliceItem> {
262 raw: ErasedPtr,
263 marker: PhantomData<Box<ThinData<Head, SliceItem>>>,
264}
265
266thin_holder!(for ThinBox<Head, SliceItem> as Box<ThinData<Head, SliceItem>> with fatten_mut);
267
268impl<Head, SliceItem> ThinBox<Head, SliceItem> {
269 fn layout(len: usize) -> Result<(Layout, [usize; 3]), LayoutErr> {
270 let length_layout = Layout::new::<usize>();
271 let head_layout = Layout::new::<Head>();
272 let slice_layout = layout_array::<SliceItem>(len)?;
273 repr_c_3([length_layout, head_layout, slice_layout])
274 }
275
276 unsafe fn alloc(len: usize, layout: Layout) -> NonNull<ThinData<Head, SliceItem>> {
277 let ptr: ErasedPtr = NonNull::new(alloc(layout))
278 .unwrap_or_else(|| handle_alloc_error(layout))
279 .cast();
280 ptr::write(ThinData::<Head, SliceItem>::len(ptr).as_ptr(), len);
281 ThinData::fatten_mut(ptr.cast())
282 }
283
284 pub fn new<I>(head: Head, slice: I) -> Self
290 where
291 I: IntoIterator<Item = SliceItem>,
292 I::IntoIter: ExactSizeIterator, {
294 struct InProgress<Head, SliceItem> {
295 raw: NonNull<ThinData<Head, SliceItem>>,
296 written_len: usize,
297 layout: Layout,
298 head_offset: usize,
299 slice_offset: usize,
300 }
301
302 impl<Head, SliceItem> Drop for InProgress<Head, SliceItem> {
303 fn drop(&mut self) {
304 let raw_ptr = ThinData::erase(self.raw).as_ptr();
305 unsafe {
306 let slice = make_slice_mut(
307 raw_ptr.add(self.slice_offset).cast::<SliceItem>(),
308 self.written_len,
309 );
310 ptr::drop_in_place(slice);
311 dealloc(raw_ptr.cast(), self.layout);
312 }
313 }
314 }
315
316 impl<Head, SliceItem> InProgress<Head, SliceItem> {
317 fn raw_ptr(&self) -> ErasedPtr {
318 ThinData::erase(self.raw)
319 }
320
321 fn new(len: usize) -> Self {
322 let (layout, [_, head_offset, slice_offset]) =
323 ThinBox::<Head, SliceItem>::layout(len)
324 .unwrap_or_else(|e| panic!("oversize box: {}", e));
325 InProgress {
326 raw: unsafe { ThinBox::alloc(len, layout) },
327 written_len: 0,
328 layout,
329 head_offset,
330 slice_offset,
331 }
332 }
333
334 unsafe fn push(&mut self, item: SliceItem) {
335 self.raw_ptr()
336 .as_ptr()
337 .add(self.slice_offset)
338 .cast::<SliceItem>()
339 .add(self.written_len)
340 .write(item);
341 self.written_len += 1;
342 }
343
344 unsafe fn finish(self, head: Head) -> ThinBox<Head, SliceItem> {
345 let this = ManuallyDrop::new(self);
346 let ptr = this.raw_ptr();
347 ptr::write(ptr.as_ptr().add(this.head_offset).cast(), head);
348 let out = ThinBox::from_erased(ptr);
349 assert_eq!(this.layout, Layout::for_value(&*out));
350 out
351 }
352 }
353
354 let mut items = slice.into_iter();
355 let len = items.len();
356
357 unsafe {
358 let mut this = InProgress::new(len);
359
360 for _ in 0..len {
361 let slice_item = items
362 .next()
363 .expect("ExactSizeIterator over-reported length");
364 this.push(slice_item);
365 }
366 assert!(
367 items.next().is_none(),
368 "ExactSizeIterator under-reported length"
369 );
370
371 this.finish(head)
372 }
373 }
374}
375
376impl<Head, SliceItem> From<ThinBox<Head, SliceItem>> for Box<ThinData<Head, SliceItem>> {
377 fn from(this: ThinBox<Head, SliceItem>) -> Self {
378 unsafe {
379 let this = ManuallyDrop::new(this);
380 Box::from_raw(ThinData::fatten_mut(this.raw).as_ptr())
381 }
382 }
383}
384
385impl<Head, SliceItem> Clone for ThinBox<Head, SliceItem>
386where
387 Head: Clone,
388 SliceItem: Clone,
389{
390 fn clone(&self) -> Self {
393 ThinBox::new(self.head.clone(), self.slice.iter().cloned())
394 }
395}
396
397pub struct ThinArc<Head, SliceItem> {
401 raw: ErasedPtr,
402 marker: PhantomData<Arc<ThinData<Head, SliceItem>>>,
403}
404
405thin_holder!(for ThinArc<Head, SliceItem> as Arc<ThinData<Head, SliceItem>> with fatten_const);
406
407impl<Head, SliceItem> ThinArc<Head, SliceItem> {
408 pub fn new<I>(head: Head, slice: I) -> Self
423 where
424 I: IntoIterator<Item = SliceItem>,
425 I::IntoIter: ExactSizeIterator, {
427 let boxed: Box<ThinData<Head, SliceItem>> = ThinBox::new(head, slice).into();
430 let arc: Arc<ThinData<Head, SliceItem>> = boxed.into();
431 arc.into()
432 }
433}
434
435impl<Head, SliceItem> From<ThinArc<Head, SliceItem>> for Arc<ThinData<Head, SliceItem>> {
436 fn from(this: ThinArc<Head, SliceItem>) -> Self {
437 unsafe {
438 let this = ManuallyDrop::new(this);
439 Arc::from_raw(ThinData::fatten_const(this.raw).as_ptr())
440 }
441 }
442}
443
444impl<Head, SliceItem> Clone for ThinArc<Head, SliceItem>
445where
446 Arc<ThinData<Head, SliceItem>>: Clone,
447{
448 fn clone(&self) -> Self {
449 unsafe {
450 let this = ManuallyDrop::new(Arc::from_raw(ThinData::fatten_const(self.raw).as_ptr()));
451 ManuallyDrop::into_inner(ManuallyDrop::clone(&this)).into()
452 }
453 }
454}
455
456pub struct ThinRc<Head, SliceItem> {
460 raw: ErasedPtr,
461 marker: PhantomData<Rc<ThinData<Head, SliceItem>>>,
462}
463
464thin_holder!(for ThinRc<Head, SliceItem> as Rc<ThinData<Head, SliceItem>> with fatten_const);
465
466impl<Head, SliceItem> ThinRc<Head, SliceItem> {
467 pub fn new<I>(head: Head, slice: I) -> Self
482 where
483 I: IntoIterator<Item = SliceItem>,
484 I::IntoIter: ExactSizeIterator, {
486 let boxed: Box<ThinData<Head, SliceItem>> = ThinBox::new(head, slice).into();
489 let arc: Rc<ThinData<Head, SliceItem>> = boxed.into();
490 arc.into()
491 }
492}
493
494impl<Head, SliceItem> From<ThinRc<Head, SliceItem>> for Rc<ThinData<Head, SliceItem>> {
495 fn from(this: ThinRc<Head, SliceItem>) -> Self {
496 unsafe {
497 let this = ManuallyDrop::new(this);
498 Rc::from_raw(ThinData::fatten_const(this.raw).as_ptr())
499 }
500 }
501}
502
503impl<Head, SliceItem> Clone for ThinRc<Head, SliceItem>
504where
505 Rc<ThinData<Head, SliceItem>>: Clone,
506{
507 fn clone(&self) -> Self {
508 unsafe {
509 let this = ManuallyDrop::new(Rc::from_raw(ThinData::fatten_const(self.raw).as_ptr()));
510 ManuallyDrop::into_inner(ManuallyDrop::clone(&this)).into()
511 }
512 }
513}
514
515pub struct ThinRef<'a, Head, SliceItem> {
516 raw: ErasedPtr,
517 marker: PhantomData<&'a ThinData<Head, SliceItem>>,
518}
519
520thin_holder!(#[nodrop] for ThinRef<'a, Head, SliceItem> as Ref<'a, ThinData<Head, SliceItem>> with fatten_const);
521
522impl<'a, Head, SliceItem> Copy for ThinRef<'a, Head, SliceItem> where
523 &'a ThinData<Head, SliceItem>: Copy
524{
525}
526impl<'a, Head, SliceItem> Clone for ThinRef<'a, Head, SliceItem>
527where
528 &'a ThinData<Head, SliceItem>: Clone,
529{
530 fn clone(&self) -> Self {
531 *self
532 }
533}
534
535impl<'a, Head, SliceItem> From<ThinRef<'a, Head, SliceItem>> for &'a ThinData<Head, SliceItem> {
536 fn from(this: ThinRef<'a, Head, SliceItem>) -> Self {
537 unsafe { Ref::from_raw(ThinData::fatten_const(this.raw).as_ptr()) }
538 }
539}
540
541pub struct ThinRefMut<'a, Head, SliceItem> {
542 raw: ErasedPtr,
543 marker: PhantomData<&'a mut ThinData<Head, SliceItem>>,
544}
545
546thin_holder!(#[nodrop] for ThinRefMut<'a, Head, SliceItem> as Ref<'a, ThinData<Head, SliceItem>> with fatten_const);
547
548impl<'a, Head, SliceItem> From<ThinRefMut<'a, Head, SliceItem>>
549 for &'a mut ThinData<Head, SliceItem>
550{
551 fn from(this: ThinRefMut<'a, Head, SliceItem>) -> Self {
552 unsafe { RefMut::from_raw(ThinData::fatten_mut(this.raw).as_ptr()) }
553 }
554}
555
556pub struct ThinPtr<Head, SliceItem> {
557 raw: ErasedPtr,
558 marker: PhantomData<NonNull<ThinData<Head, SliceItem>>>,
559}
560
561thin_holder!(#[nodrop] for ThinPtr<Head, SliceItem> as NonNull<ThinData<Head, SliceItem>> with fatten_mut);
562
563impl<Head, SliceItem> Copy for ThinPtr<Head, SliceItem> where
564 NonNull<ThinData<Head, SliceItem>>: Copy
565{
566}
567impl<Head, SliceItem> Clone for ThinPtr<Head, SliceItem>
568where
569 NonNull<ThinData<Head, SliceItem>>: Clone,
570{
571 fn clone(&self) -> Self {
572 *self
573 }
574}
575
576impl<Head, SliceItem> From<ThinPtr<Head, SliceItem>> for NonNull<ThinData<Head, SliceItem>> {
577 fn from(this: ThinPtr<Head, SliceItem>) -> Self {
578 unsafe { ThinData::fatten_mut(this.raw) }
579 }
580}
581
582#[allow(
583 missing_docs,
584 clippy::missing_safety_doc,
585 clippy::should_implement_trait
586)]
587impl<Head, SliceItem> ThinPtr<Head, SliceItem> {
588 pub unsafe fn as_ptr(self) -> *mut ThinData<Head, SliceItem> {
589 let nn: NonNull<_> = self.into();
590 nn.as_ptr()
591 }
592 pub unsafe fn as_ref(&self) -> &ThinData<Head, SliceItem> {
593 &*self.as_ptr()
594 }
595 pub unsafe fn as_mut(&mut self) -> &mut ThinData<Head, SliceItem> {
596 &mut *self.as_ptr()
597 }
598}
599
600unsafe trait RawExt<T: ?Sized> {
603 unsafe fn from_raw(ptr: *const T) -> Self;
604 unsafe fn into_raw(self) -> *const T;
605}
606
607unsafe trait RawMutExt<T: ?Sized> {
608 unsafe fn from_raw(ptr: *mut T) -> Self;
609 unsafe fn into_raw(self) -> *mut T;
610}
611
612type Ref<'a, T> = &'a T;
613unsafe impl<'a, T: ?Sized> RawExt<T> for Ref<'a, T> {
614 unsafe fn from_raw(ptr: *const T) -> Self {
615 &*ptr
616 }
617
618 unsafe fn into_raw(self) -> *const T {
619 self
620 }
621}
622
623type RefMut<'a, T> = &'a mut T;
624unsafe impl<'a, T: ?Sized> RawMutExt<T> for RefMut<'a, T> {
625 unsafe fn from_raw(ptr: *mut T) -> Self {
626 &mut *ptr
627 }
628
629 unsafe fn into_raw(self) -> *mut T {
630 self
631 }
632}
633
634unsafe impl<T: ?Sized> RawMutExt<T> for NonNull<T> {
635 unsafe fn from_raw(ptr: *mut T) -> Self {
636 NonNull::new_unchecked(ptr)
637 }
638
639 unsafe fn into_raw(self) -> *mut T {
640 NonNull::as_ptr(self)
641 }
642}