vendor/gimli-0.26.2/src/read/util.rs

   1 #[cfg(feature = "read")]
   2 use alloc::boxed::Box;
   3 #[cfg(feature = "read")]
   4 use alloc::vec::Vec;
   5 use core::fmt;
   6 use core::mem::MaybeUninit;
   7 use core::ops;
   8 use core::ptr;
   9 use core::slice;
  10
  11 mod sealed {
  12     // SAFETY: Implementer must not modify the content in storage.
  13     pub unsafe trait Sealed {
  14         type Storage;
  15
  16         fn new_storage() -> Self::Storage;
  17
  18         fn grow(_storage: &mut Self::Storage, _additional: usize) -> Result<(), CapacityFull> {
  19             Err(CapacityFull)
  20         }
  21     }
  22
  23     #[derive(Clone, Copy, Debug)]
  24     pub struct CapacityFull;
  25 }
  26
  27 use sealed::*;
  28
  29 /// Marker trait for types that can be used as backing storage when a growable array type is needed.
  30 ///
  31 /// This trait is sealed and cannot be implemented for types outside this crate.
  32 pub trait ArrayLike: Sealed {
  33     /// Type of the elements being stored.
  34     type Item;
  35
  36     #[doc(hidden)]
  37     fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<Self::Item>];
  38
  39     #[doc(hidden)]
  40     fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<Self::Item>];
  41 }
  42
  43 // Use macro since const generics can't be used due to MSRV.
  44 macro_rules! impl_array {
  45     () => {};
  46     ($n:literal $($rest:tt)*) => {
  47         // SAFETY: does not modify the content in storage.
  48         unsafe impl<T> Sealed for [T; $n] {
  49             type Storage = [MaybeUninit<T>; $n];
  50
  51             fn new_storage() -> Self::Storage {
  52                 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
  53                 unsafe { MaybeUninit::uninit().assume_init() }
  54             }
  55         }
  56
  57         impl<T> ArrayLike for [T; $n] {
  58             type Item = T;
  59
  60             fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
  61                 storage
  62             }
  63
  64             fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
  65                 storage
  66             }
  67         }
  68
  69         impl_array!($($rest)*);
  70     }
  71 }
  72
  73 impl_array!(0 1 2 3 4 8 16 32 64 128 192);
  74
  75 #[cfg(feature = "read")]
  76 unsafe impl<T> Sealed for Vec<T> {
  77     type Storage = Box<[MaybeUninit<T>]>;
  78
  79     fn new_storage() -> Self::Storage {
  80         Box::new([])
  81     }
  82
  83     fn grow(storage: &mut Self::Storage, additional: usize) -> Result<(), CapacityFull> {
  84         let mut vec: Vec<_> = core::mem::replace(storage, Box::new([])).into();
  85         vec.reserve(additional);
  86         // SAFETY: This is a `Vec` of `MaybeUninit`.
  87         unsafe { vec.set_len(vec.capacity()) };
  88         *storage = vec.into_boxed_slice();
  89         Ok(())
  90     }
  91 }
  92
  93 #[cfg(feature = "read")]
  94 impl<T> ArrayLike for Vec<T> {
  95     type Item = T;
  96
  97     fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
  98         storage
  99     }
 100
 101     fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
 102         storage
 103     }
 104 }
 105
 106 pub(crate) struct ArrayVec<A: ArrayLike> {
 107     storage: A::Storage,
 108     len: usize,
 109 }
 110
 111 impl<A: ArrayLike> ArrayVec<A> {
 112     pub fn new() -> Self {
 113         Self {
 114             storage: A::new_storage(),
 115             len: 0,
 116         }
 117     }
 118
 119     pub fn clear(&mut self) {
 120         let ptr: *mut [A::Item] = &mut **self;
 121         // Set length first so the type invariant is upheld even if `drop_in_place` panicks.
 122         self.len = 0;
 123         // SAFETY: `ptr` contains valid elements only and we "forget" them by setting the length.
 124         unsafe { ptr::drop_in_place(ptr) };
 125     }
 126
 127     pub fn try_push(&mut self, value: A::Item) -> Result<(), CapacityFull> {
 128         let mut storage = A::as_mut_slice(&mut self.storage);
 129         if self.len >= storage.len() {
 130             A::grow(&mut self.storage, 1)?;
 131             storage = A::as_mut_slice(&mut self.storage);
 132         }
 133
 134         storage[self.len] = MaybeUninit::new(value);
 135         self.len += 1;
 136         Ok(())
 137     }
 138
 139     pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityFull> {
 140         assert!(index <= self.len);
 141
 142         let mut storage = A::as_mut_slice(&mut self.storage);
 143         if self.len >= storage.len() {
 144             A::grow(&mut self.storage, 1)?;
 145             storage = A::as_mut_slice(&mut self.storage);
 146         }
 147
 148         // SAFETY: storage[index] is filled later.
 149         unsafe {
 150             let p = storage.as_mut_ptr().add(index);
 151             core::ptr::copy(p as *const _, p.add(1), self.len - index);
 152         }
 153         storage[index] = MaybeUninit::new(element);
 154         self.len += 1;
 155         Ok(())
 156     }
 157
 158     pub fn pop(&mut self) -> Option<A::Item> {
 159         if self.len == 0 {
 160             None
 161         } else {
 162             self.len -= 1;
 163             // SAFETY: this element is valid and we "forget" it by setting the length.
 164             Some(unsafe { A::as_slice(&mut self.storage)[self.len].as_ptr().read() })
 165         }
 166     }
 167
 168     pub fn swap_remove(&mut self, index: usize) -> A::Item {
 169         assert!(self.len > 0);
 170         A::as_mut_slice(&mut self.storage).swap(index, self.len - 1);
 171         self.pop().unwrap()
 172     }
 173 }
 174
 175 #[cfg(feature = "read")]
 176 impl<T> ArrayVec<Vec<T>> {
 177     pub fn into_vec(mut self) -> Vec<T> {
 178         let len = core::mem::replace(&mut self.len, 0);
 179         let storage = core::mem::replace(&mut self.storage, Box::new([]));
 180         let slice = Box::leak(storage);
 181         debug_assert!(len <= slice.len());
 182         // SAFETY: valid elements.
 183         unsafe { Vec::from_raw_parts(slice.as_mut_ptr() as *mut T, len, slice.len()) }
 184     }
 185 }
 186
 187 impl<A: ArrayLike> Drop for ArrayVec<A> {
 188     fn drop(&mut self) {
 189         self.clear();
 190     }
 191 }
 192
 193 impl<A: ArrayLike> Default for ArrayVec<A> {
 194     fn default() -> Self {
 195         Self::new()
 196     }
 197 }
 198
 199 impl<A: ArrayLike> ops::Deref for ArrayVec<A> {
 200     type Target = [A::Item];
 201
 202     fn deref(&self) -> &[A::Item] {
 203         let slice = &A::as_slice(&self.storage);
 204         debug_assert!(self.len <= slice.len());
 205         // SAFETY: valid elements.
 206         unsafe { slice::from_raw_parts(slice.as_ptr() as _, self.len) }
 207     }
 208 }
 209
 210 impl<A: ArrayLike> ops::DerefMut for ArrayVec<A> {
 211     fn deref_mut(&mut self) -> &mut [A::Item] {
 212         let slice = &mut A::as_mut_slice(&mut self.storage);
 213         debug_assert!(self.len <= slice.len());
 214         // SAFETY: valid elements.
 215         unsafe { slice::from_raw_parts_mut(slice.as_mut_ptr() as _, self.len) }
 216     }
 217 }
 218
 219 impl<A: ArrayLike> Clone for ArrayVec<A>
 220 where
 221     A::Item: Clone,
 222 {
 223     fn clone(&self) -> Self {
 224         let mut new = Self::default();
 225         for value in &**self {
 226             new.try_push(value.clone()).unwrap();
 227         }
 228         new
 229     }
 230 }
 231
 232 impl<A: ArrayLike> PartialEq for ArrayVec<A>
 233 where
 234     A::Item: PartialEq,
 235 {
 236     fn eq(&self, other: &Self) -> bool {
 237         **self == **other
 238     }
 239 }
 240
 241 impl<A: ArrayLike> Eq for ArrayVec<A> where A::Item: Eq {}
 242
 243 impl<A: ArrayLike> fmt::Debug for ArrayVec<A>
 244 where
 245     A::Item: fmt::Debug,
 246 {
 247     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 248         fmt::Debug::fmt(&**self, f)
 249     }
 250 }