vendor/generic-array/src/sequence.rs

   1 //! Useful traits for manipulating sequences of data stored in `GenericArray`s
   2
   3 use super::*;
   4 use core::ops::{Add, Sub};
   5 use core::mem::MaybeUninit;
   6 use core::ptr;
   7 use typenum::operator_aliases::*;
   8
   9 /// Defines some sequence with an associated length and iteration capabilities.
  10 ///
  11 /// This is useful for passing N-length generic arrays as generics.
  12 pub unsafe trait GenericSequence<T>: Sized + IntoIterator {
  13     /// `GenericArray` associated length
  14     type Length: ArrayLength<T>;
  15
  16     /// Concrete sequence type used in conjuction with reference implementations of `GenericSequence`
  17     type Sequence: GenericSequence<T, Length = Self::Length> + FromIterator<T>;
  18
  19     /// Initializes a new sequence instance using the given function.
  20     ///
  21     /// If the generator function panics while initializing the sequence,
  22     /// any already initialized elements will be dropped.
  23     fn generate<F>(f: F) -> Self::Sequence
  24     where
  25         F: FnMut(usize) -> T;
  26
  27     #[doc(hidden)]
  28     fn inverted_zip<B, U, F>(
  29         self,
  30         lhs: GenericArray<B, Self::Length>,
  31         mut f: F,
  32     ) -> MappedSequence<GenericArray<B, Self::Length>, B, U>
  33     where
  34         GenericArray<B, Self::Length>: GenericSequence<B, Length = Self::Length>
  35             + MappedGenericSequence<B, U>,
  36         Self: MappedGenericSequence<T, U>,
  37         Self::Length: ArrayLength<B> + ArrayLength<U>,
  38         F: FnMut(B, Self::Item) -> U,
  39     {
  40         unsafe {
  41             let mut left = ArrayConsumer::new(lhs);
  42
  43             let (left_array_iter, left_position) = left.iter_position();
  44
  45             FromIterator::from_iter(left_array_iter.zip(self.into_iter()).map(
  46                 |(l, right_value)| {
  47                         let left_value = ptr::read(l);
  48
  49                         *left_position += 1;
  50
  51                         f(left_value, right_value)
  52                 },
  53             ))
  54         }
  55     }
  56
  57     #[doc(hidden)]
  58     fn inverted_zip2<B, Lhs, U, F>(self, lhs: Lhs, mut f: F) -> MappedSequence<Lhs, B, U>
  59     where
  60         Lhs: GenericSequence<B, Length = Self::Length> + MappedGenericSequence<B, U>,
  61         Self: MappedGenericSequence<T, U>,
  62         Self::Length: ArrayLength<B> + ArrayLength<U>,
  63         F: FnMut(Lhs::Item, Self::Item) -> U,
  64     {
  65         FromIterator::from_iter(lhs.into_iter().zip(self.into_iter()).map(|(l, r)| f(l, r)))
  66     }
  67 }
  68
  69 /// Accessor for `GenericSequence` item type, which is really `IntoIterator::Item`
  70 ///
  71 /// For deeply nested generic mapped sequence types, like shown in `tests/generics.rs`,
  72 /// this can be useful for keeping things organized.
  73 pub type SequenceItem<T> = <T as IntoIterator>::Item;
  74
  75 unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a S
  76 where
  77     &'a S: IntoIterator,
  78 {
  79     type Length = S::Length;
  80     type Sequence = S::Sequence;
  81
  82     #[inline]
  83     fn generate<F>(f: F) -> Self::Sequence
  84     where
  85         F: FnMut(usize) -> T,
  86     {
  87         S::generate(f)
  88     }
  89 }
  90
  91 unsafe impl<'a, T: 'a, S: GenericSequence<T>> GenericSequence<T> for &'a mut S
  92 where
  93     &'a mut S: IntoIterator,
  94 {
  95     type Length = S::Length;
  96     type Sequence = S::Sequence;
  97
  98     #[inline]
  99     fn generate<F>(f: F) -> Self::Sequence
 100     where
 101         F: FnMut(usize) -> T,
 102     {
 103         S::generate(f)
 104     }
 105 }
 106
 107 /// Defines any `GenericSequence` which can be lengthened or extended by appending
 108 /// or prepending an element to it.
 109 ///
 110 /// Any lengthened sequence can be shortened back to the original using `pop_front` or `pop_back`
 111 pub unsafe trait Lengthen<T>: Sized + GenericSequence<T> {
 112     /// `GenericSequence` that has one more element than `Self`
 113     type Longer: Shorten<T, Shorter = Self>;
 114
 115     /// Returns a new array with the given element appended to the end of it.
 116     ///
 117     /// Example:
 118     ///
 119     /// ```rust
 120     /// # use generic_array::{arr, sequence::Lengthen};
 121     /// # fn main() {
 122     /// let a = arr![i32; 1, 2, 3];
 123     ///
 124     /// let b = a.append(4);
 125     ///
 126     /// assert_eq!(b, arr![i32; 1, 2, 3, 4]);
 127     /// # }
 128     /// ```
 129     fn append(self, last: T) -> Self::Longer;
 130
 131     /// Returns a new array with the given element prepended to the front of it.
 132     ///
 133     /// Example:
 134     ///
 135     /// ```rust
 136     /// # use generic_array::{arr, sequence::Lengthen};
 137     /// # fn main() {
 138     /// let a = arr![i32; 1, 2, 3];
 139     ///
 140     /// let b = a.prepend(4);
 141     ///
 142     /// assert_eq!(b, arr![i32; 4, 1, 2, 3]);
 143     /// # }
 144     /// ```
 145     fn prepend(self, first: T) -> Self::Longer;
 146 }
 147
 148 /// Defines a `GenericSequence` which can be shortened by removing the first or last element from it.
 149 ///
 150 /// Additionally, any shortened sequence can be lengthened by
 151 /// appending or prepending an element to it.
 152 pub unsafe trait Shorten<T>: Sized + GenericSequence<T> {
 153     /// `GenericSequence` that has one less element than `Self`
 154     type Shorter: Lengthen<T, Longer = Self>;
 155
 156     /// Returns a new array without the last element, and the last element.
 157     ///
 158     /// Example:
 159     ///
 160     /// ```rust
 161     /// # use generic_array::{arr, sequence::Shorten};
 162     /// # fn main() {
 163     /// let a = arr![i32; 1, 2, 3, 4];
 164     ///
 165     /// let (init, last) = a.pop_back();
 166     ///
 167     /// assert_eq!(init, arr![i32; 1, 2, 3]);
 168     /// assert_eq!(last, 4);
 169     /// # }
 170     /// ```
 171     fn pop_back(self) -> (Self::Shorter, T);
 172
 173     /// Returns a new array without the first element, and the first element.
 174     /// Example:
 175     ///
 176     /// ```rust
 177     /// # use generic_array::{arr, sequence::Shorten};
 178     /// # fn main() {
 179     /// let a = arr![i32; 1, 2, 3, 4];
 180     ///
 181     /// let (head, tail) = a.pop_front();
 182     ///
 183     /// assert_eq!(head, 1);
 184     /// assert_eq!(tail, arr![i32; 2, 3, 4]);
 185     /// # }
 186     /// ```
 187     fn pop_front(self) -> (T, Self::Shorter);
 188 }
 189
 190 unsafe impl<T, N: ArrayLength<T>> Lengthen<T> for GenericArray<T, N>
 191 where
 192     N: Add<B1>,
 193     Add1<N>: ArrayLength<T>,
 194     Add1<N>: Sub<B1, Output = N>,
 195     Sub1<Add1<N>>: ArrayLength<T>,
 196 {
 197     type Longer = GenericArray<T, Add1<N>>;
 198
 199     fn append(self, last: T) -> Self::Longer {
 200         let mut longer: MaybeUninit<Self::Longer> = MaybeUninit::uninit();
 201
 202         // Note this is *mut Self, so add(1) increments by the whole array
 203         let out_ptr = longer.as_mut_ptr() as *mut Self;
 204
 205         unsafe {
 206             // write self first
 207             ptr::write(out_ptr, self);
 208             // increment past self, then write the last
 209             ptr::write(out_ptr.add(1) as *mut T, last);
 210
 211             longer.assume_init()
 212         }
 213     }
 214
 215     fn prepend(self, first: T) -> Self::Longer {
 216         let mut longer: MaybeUninit<Self::Longer> = MaybeUninit::uninit();
 217
 218         // Note this is *mut T, so add(1) increments by a single T
 219         let out_ptr = longer.as_mut_ptr() as *mut T;
 220
 221         unsafe {
 222             // write the first at the start
 223             ptr::write(out_ptr, first);
 224             // increment past the first, then write self
 225             ptr::write(out_ptr.add(1) as *mut Self, self);
 226
 227             longer.assume_init()
 228         }
 229     }
 230 }
 231
 232 unsafe impl<T, N: ArrayLength<T>> Shorten<T> for GenericArray<T, N>
 233 where
 234     N: Sub<B1>,
 235     Sub1<N>: ArrayLength<T>,
 236     Sub1<N>: Add<B1, Output = N>,
 237     Add1<Sub1<N>>: ArrayLength<T>,
 238 {
 239     type Shorter = GenericArray<T, Sub1<N>>;
 240
 241     fn pop_back(self) -> (Self::Shorter, T) {
 242         let whole = ManuallyDrop::new(self);
 243
 244         unsafe {
 245             let init = ptr::read(whole.as_ptr() as _);
 246             let last = ptr::read(whole.as_ptr().add(Sub1::<N>::USIZE) as _);
 247
 248             (init, last)
 249         }
 250     }
 251
 252     fn pop_front(self) -> (T, Self::Shorter) {
 253         // ensure this doesn't get dropped
 254         let whole = ManuallyDrop::new(self);
 255
 256         unsafe {
 257             let head = ptr::read(whole.as_ptr() as _);
 258             let tail = ptr::read(whole.as_ptr().offset(1) as _);
 259
 260             (head, tail)
 261         }
 262     }
 263 }
 264
 265 /// Defines a `GenericSequence` that can be split into two parts at a given pivot index.
 266 pub unsafe trait Split<T, K>: GenericSequence<T>
 267 where
 268     K: ArrayLength<T>,
 269 {
 270     /// First part of the resulting split array
 271     type First: GenericSequence<T>;
 272     /// Second part of the resulting split array
 273     type Second: GenericSequence<T>;
 274
 275     /// Splits an array at the given index, returning the separate parts of the array.
 276     fn split(self) -> (Self::First, Self::Second);
 277 }
 278
 279 unsafe impl<T, N, K> Split<T, K> for GenericArray<T, N>
 280 where
 281     N: ArrayLength<T>,
 282     K: ArrayLength<T>,
 283     N: Sub<K>,
 284     Diff<N, K>: ArrayLength<T>,
 285 {
 286     type First = GenericArray<T, K>;
 287     type Second = GenericArray<T, Diff<N, K>>;
 288
 289     fn split(self) -> (Self::First, Self::Second) {
 290         unsafe {
 291             // ensure this doesn't get dropped
 292             let whole = ManuallyDrop::new(self);
 293
 294             let head = ptr::read(whole.as_ptr() as *const _);
 295             let tail = ptr::read(whole.as_ptr().add(K::USIZE) as *const _);
 296
 297             (head, tail)
 298         }
 299     }
 300 }
 301
 302 unsafe impl<'a, T, N, K> Split<T, K> for &'a GenericArray<T, N>
 303 where
 304     N: ArrayLength<T>,
 305     K: ArrayLength<T> + 'static,
 306     N: Sub<K>,
 307     Diff<N, K>: ArrayLength<T>,
 308 {
 309     type First = &'a GenericArray<T, K>;
 310     type Second = &'a GenericArray<T, Diff<N, K>>;
 311
 312     fn split(self) -> (Self::First, Self::Second) {
 313         unsafe {
 314             let ptr_to_first: *const T = self.as_ptr();
 315             let head = &*(ptr_to_first as *const _);
 316             let tail = &*(ptr_to_first.add(K::USIZE) as *const _);
 317             (head, tail)
 318         }
 319     }
 320 }
 321
 322 unsafe impl<'a, T, N, K> Split<T, K> for &'a mut GenericArray<T, N>
 323 where
 324     N: ArrayLength<T>,
 325     K: ArrayLength<T> + 'static,
 326     N: Sub<K>,
 327     Diff<N, K>: ArrayLength<T>,
 328 {
 329     type First = &'a mut GenericArray<T, K>;
 330     type Second = &'a mut GenericArray<T, Diff<N, K>>;
 331
 332     fn split(self) -> (Self::First, Self::Second) {
 333         unsafe {
 334             let ptr_to_first: *mut T = self.as_mut_ptr();
 335             let head = &mut *(ptr_to_first as *mut _);
 336             let tail = &mut *(ptr_to_first.add(K::USIZE) as *mut _);
 337             (head, tail)
 338         }
 339     }
 340 }
 341
 342 /// Defines `GenericSequence`s which can be joined together, forming a larger array.
 343 pub unsafe trait Concat<T, M>: GenericSequence<T>
 344 where
 345     M: ArrayLength<T>,
 346 {
 347     /// Sequence to be concatenated with `self`
 348     type Rest: GenericSequence<T, Length = M>;
 349
 350     /// Resulting sequence formed by the concatenation.
 351     type Output: GenericSequence<T>;
 352
 353     /// Concatenate, or join, two sequences.
 354     fn concat(self, rest: Self::Rest) -> Self::Output;
 355 }
 356
 357 unsafe impl<T, N, M> Concat<T, M> for GenericArray<T, N>
 358 where
 359     N: ArrayLength<T> + Add<M>,
 360     M: ArrayLength<T>,
 361     Sum<N, M>: ArrayLength<T>,
 362 {
 363     type Rest = GenericArray<T, M>;
 364     type Output = GenericArray<T, Sum<N, M>>;
 365
 366     fn concat(self, rest: Self::Rest) -> Self::Output {
 367         let mut output: MaybeUninit<Self::Output> = MaybeUninit::uninit();
 368
 369         let out_ptr = output.as_mut_ptr() as *mut Self;
 370
 371         unsafe {
 372             // write all of self to the pointer
 373             ptr::write(out_ptr, self);
 374             // increment past self, then write the rest
 375             ptr::write(out_ptr.add(1) as *mut _, rest);
 376
 377             output.assume_init()
 378         }
 379     }
 380 }