From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- .../rust/generic-array/.cargo-checksum.json | 1 + third_party/rust/generic-array/CHANGELOG.md | 98 +++ third_party/rust/generic-array/Cargo.toml | 75 +++ third_party/rust/generic-array/LICENSE | 21 + third_party/rust/generic-array/README.md | 62 ++ third_party/rust/generic-array/build.rs | 5 + third_party/rust/generic-array/src/arr.rs | 125 ++++ third_party/rust/generic-array/src/functional.rs | 95 +++ third_party/rust/generic-array/src/hex.rs | 105 ++++ third_party/rust/generic-array/src/impl_serde.rs | 108 ++++ third_party/rust/generic-array/src/impl_zeroize.rs | 25 + third_party/rust/generic-array/src/impls.rs | 269 ++++++++ third_party/rust/generic-array/src/iter.rs | 251 ++++++++ third_party/rust/generic-array/src/lib.rs | 679 +++++++++++++++++++++ third_party/rust/generic-array/src/sequence.rs | 380 ++++++++++++ 15 files changed, 2299 insertions(+) create mode 100644 third_party/rust/generic-array/.cargo-checksum.json create mode 100644 third_party/rust/generic-array/CHANGELOG.md create mode 100644 third_party/rust/generic-array/Cargo.toml create mode 100644 third_party/rust/generic-array/LICENSE create mode 100644 third_party/rust/generic-array/README.md create mode 100644 third_party/rust/generic-array/build.rs create mode 100644 third_party/rust/generic-array/src/arr.rs create mode 100644 third_party/rust/generic-array/src/functional.rs create mode 100644 third_party/rust/generic-array/src/hex.rs create mode 100644 third_party/rust/generic-array/src/impl_serde.rs create mode 100644 third_party/rust/generic-array/src/impl_zeroize.rs create mode 100644 third_party/rust/generic-array/src/impls.rs create mode 100644 third_party/rust/generic-array/src/iter.rs create mode 100644 third_party/rust/generic-array/src/lib.rs create mode 100644 third_party/rust/generic-array/src/sequence.rs (limited to 'third_party/rust/generic-array') diff --git a/third_party/rust/generic-array/.cargo-checksum.json b/third_party/rust/generic-array/.cargo-checksum.json new file mode 100644 index 0000000000..f8ddf9aa70 --- /dev/null +++ b/third_party/rust/generic-array/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"e1d167ae44b01d58177842db72b8ddf754850756adc40ab87fef6af83ee7f759","Cargo.toml":"d75b1d3d662d67545bc43f331fdfbb95b8e9cb8522875608a7f8f2528e3325d3","LICENSE":"c09aae9d3c77b531f56351a9947bc7446511d6b025b3255312d3e3442a9a7583","README.md":"9e86d03b400dc818f44df68b76dafd1d89e42a51221bcb0de4259a6529ab6d84","build.rs":"08fa30c4a2c1ad24fe5f987e721dfb20131f45ea5b5dc3e836dcf88a8e33248c","src/arr.rs":"c115d6926deb769ced772e9c4e1c84baf1bdea4fe4b9eb2061658a63869eab62","src/functional.rs":"7dd6ddd5db3000054cbbd76959f745c7de73c8493cbfb745be80509b306e4a83","src/hex.rs":"091fb78f6d373a6ef1c467d85c461472fcdb1e91efc294039f4c870151c3ee9f","src/impl_serde.rs":"f046daba067522b4c3e79437d04f43a001e83353c81e6b2188c37a2e63dba7a3","src/impl_zeroize.rs":"b7825efdc72890ed05337f7ebdfb27cc6952126f1c94c855fdafaa24fab0bf2a","src/impls.rs":"18b285821421eea0cdbbcfcc896eef67bd55d72f8d85b5827cca6687e9c0fc27","src/iter.rs":"4f50253f4130caa0780984b64467ca1916a881410f631f7eb85a1724b3ab4ced","src/lib.rs":"163b24f691d59383c9e347126569205b03272145334cbce037cd562b93ad9f30","src/sequence.rs":"26679cfec035bae7298f067f37e8d42a1eda8fe241e9cf2c2977ba4bddddab1d"},"package":"bff49e947297f3312447abdca79f45f4738097cc82b06e72054d2223f601f1b9"} \ No newline at end of file diff --git a/third_party/rust/generic-array/CHANGELOG.md b/third_party/rust/generic-array/CHANGELOG.md new file mode 100644 index 0000000000..f7e0766bc1 --- /dev/null +++ b/third_party/rust/generic-array/CHANGELOG.md @@ -0,0 +1,98 @@ +* **`0.14.6`** + * Add an optional `Zeroize` impl for `GenericArray` (#126 and #112) + * Cleanup some unsafe (#125) and typos (#114) + * Use `include` in `Cargo.toml` to reduce package size + +* **`0.14.5`** + * Fix unsoundness behavior in `GenericArrayIter::clone` ([#120](https://github.com/fizyk20/generic-array/pull/120)) + +* **`0.14.4`** + * Update `typenum` to `1.12.0` + * Make `Drop` a no-op when the inner type does not require `Drop` (using `core::mem::needs_drop`) + +* **`0.14.3`** + * Improve behavior of `GenericArray::from_exact_iter` to assume `ExactIterator`s can lie. + * Fix alignment of zero-length `GenericArray`s + * Implement `From<&[T; N]> for &GenericArray` and its mutable variant + +* **`0.14.2`** + * Lower MSRV to `1.36.0` without `From<[T; N]>` implementations. + +* **`0.14.1`** + * Fix element conversions in `arr!` macro. + +* **`0.14.0`** + * Replace `Into` implementations with the more general `From`. + * Requires minumum Rust version of 1.41.0 + * Fix unsoundness in `arr!` macro. + * Fix meta variable misuse + * Fix Undefined Behavior across the crate by switching to `MaybeUninit` + * Improve some documentation and doctests + * Add `AsRef<[T; N]>` and `AsMut<[T; N]>` impls to `GenericArray` + * Add `Split` impl for `&GenericArray` and `&mut GenericArray` + +* **`0.13.2`** + * Add feature `more_lengths`, which adds more `From`/`Into` implementations for arrays of various lengths. + +* **`0.13.1`** + * Mark `GenericArray` as `#[repr(transparent)]` + * Implement `Into<[T; N]>` for `GenericArray` up to N=32 + +* **`0.13.0`** + * Allow `arr!` to be imported with use syntax. + * Requires minumum Rust version of 1.30.1 + +* **`0.12.2`** + * Implement `FusedIterator` for `GenericArrayIter` + +* **`0.12.1`** + * Use internal iteration where possible and provide more efficient internal iteration methods. + +* **`0.12.0`** + * Allow trailing commas in `arr!` macro. + * **BREAKING**: Serialize `GenericArray` using `serde` tuples, instead of variable-length sequences. This may not be compatible with old serialized data. + +* **`0.11.0`** + * **BREAKING** Redesign `GenericSequence` with an emphasis on use in generic type parameters. + * Add `MappedGenericSequence` and `FunctionalSequence` + * Implements optimized `map`, `zip` and `fold` for `GenericArray`, `&GenericArray` and `&mut GenericArray` + * **BREAKING** Remove `map_ref`, `zip_ref` and `map_slice` + * `map_slice` is now equivalent to `GenericArray::from_iter(slice.iter().map(...))` +* **`0.10.0`** + * Add `GenericSequence`, `Lengthen`, `Shorten`, `Split` and `Concat` traits. + * Redefine `transmute` to avert errors. +* **`0.9.0`** + * Rewrite construction methods to be well-defined in panic situations, correctly dropping elements. + * `NoDrop` crate replaced by `ManuallyDrop` as it became stable in Rust core. + * Add optimized `map`/`map_ref` and `zip`/`zip_ref` methods to `GenericArray` +* **`0.8.0`** + * Implement `AsRef`, `AsMut`, `Borrow`, `BorrowMut`, `Hash` for `GenericArray` + * Update `serde` to `1.0` + * Update `typenum` + * Make macro `arr!` non-cloning + * Implement `From<[T; N]>` up to `N=32` + * Fix #45 +* **`0.7.0`** + * Upgrade `serde` to `0.9` + * Make `serde` with `no_std` + * Implement `PartialOrd`/`Ord` for `GenericArray` +* **`0.6.0`** + * Fixed #30 + * Implement `Default` for `GenericArray` + * Implement `LowerHex` and `UpperHex` for `GenericArray` + * Use `precision` formatting field in hex representation + * Add `as_slice`, `as_mut_slice` + * Remove `GenericArray::new` in favor of `Default` trait + * Add `from_slice` and `from_mut_slice` + * `no_std` and `core` for crate. +* **`0.5.0`** + * Update `serde` + * remove `no_std` feature, fixed #19 +* **`0.4.0`** + * Re-export `typenum` +* **`0.3.0`** + * Implement `IntoIter` for `GenericArray` + * Add `map` method + * Add optional `serde` (de)serialization support feature. +* **`< 0.3.0`** + * Initial implementation in late 2015 diff --git a/third_party/rust/generic-array/Cargo.toml b/third_party/rust/generic-array/Cargo.toml new file mode 100644 index 0000000000..f04fc7bf73 --- /dev/null +++ b/third_party/rust/generic-array/Cargo.toml @@ -0,0 +1,75 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +name = "generic-array" +version = "0.14.6" +authors = [ + "Bartłomiej Kamiński ", + "Aaron Trent ", +] +include = [ + "src/**/*", + "LICENSE", + "README.md", + "CHANGELOG.md", + "build.rs", +] +description = "Generic types implementing functionality of arrays" +documentation = "http://fizyk20.github.io/generic-array/generic_array/" +readme = "README.md" +keywords = [ + "generic", + "array", +] +categories = [ + "data-structures", + "no-std", +] +license = "MIT" +repository = "https://github.com/fizyk20/generic-array.git" + +[package.metadata.docs.rs] +features = [ + "serde", + "zeroize", +] + +[lib] +name = "generic_array" + +[dependencies.serde] +version = "1.0" +optional = true +default-features = false + +[dependencies.typenum] +version = "1.12" + +[dependencies.zeroize] +version = "1" +optional = true +default-features = false + +[dev-dependencies.bincode] +version = "1.0" + +[dev-dependencies.serde_json] +version = "1.0" + +[build-dependencies.version_check] +version = "0.9" + +[features] +more_lengths = [] + +[badges.travis-ci] +repository = "fizyk20/generic-array" diff --git a/third_party/rust/generic-array/LICENSE b/third_party/rust/generic-array/LICENSE new file mode 100644 index 0000000000..6d318946df --- /dev/null +++ b/third_party/rust/generic-array/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2015 Bartłomiej Kamiński + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. \ No newline at end of file diff --git a/third_party/rust/generic-array/README.md b/third_party/rust/generic-array/README.md new file mode 100644 index 0000000000..cf54f40550 --- /dev/null +++ b/third_party/rust/generic-array/README.md @@ -0,0 +1,62 @@ +[![Crates.io](https://img.shields.io/crates/v/generic-array.svg)](https://crates.io/crates/generic-array) +[![Build Status](https://travis-ci.org/fizyk20/generic-array.svg?branch=master)](https://travis-ci.org/fizyk20/generic-array) +# generic-array + +This crate implements generic array types for Rust. + +**Requires minumum Rust version of 1.36.0, or 1.41.0 for `From<[T; N]>` implementations** + +[Documentation](http://fizyk20.github.io/generic-array/generic_array/) + +## Usage + +The Rust arrays `[T; N]` are problematic in that they can't be used generically with respect to `N`, so for example this won't work: + +```rust +struct Foo { + data: [i32; N] +} +``` + +**generic-array** defines a new trait `ArrayLength` and a struct `GenericArray>`, which let the above be implemented as: + +```rust +struct Foo> { + data: GenericArray +} +``` + +The `ArrayLength` trait is implemented by default for [unsigned integer types](http://fizyk20.github.io/generic-array/typenum/uint/index.html) from [typenum](http://fizyk20.github.io/generic-array/typenum/index.html) crate: + +```rust +use generic_array::typenum::U5; + +struct Foo> { + data: GenericArray +} + +fn main() { + let foo = Foo::{data: GenericArray::default()}; +} +``` + +For example, `GenericArray` would work almost like `[T; 5]`: + +```rust +use generic_array::typenum::U5; + +struct Foo> { + data: GenericArray +} + +fn main() { + let foo = Foo::{data: GenericArray::default()}; +} +``` + +In version 0.1.1 an `arr!` macro was introduced, allowing for creation of arrays as shown below: + +```rust +let array = arr![u32; 1, 2, 3]; +assert_eq!(array[2], 3); +``` diff --git a/third_party/rust/generic-array/build.rs b/third_party/rust/generic-array/build.rs new file mode 100644 index 0000000000..c27c7e3fa9 --- /dev/null +++ b/third_party/rust/generic-array/build.rs @@ -0,0 +1,5 @@ +fn main() { + if version_check::is_min_version("1.41.0").unwrap_or(false) { + println!("cargo:rustc-cfg=relaxed_coherence"); + } +} diff --git a/third_party/rust/generic-array/src/arr.rs b/third_party/rust/generic-array/src/arr.rs new file mode 100644 index 0000000000..cdcc038a3d --- /dev/null +++ b/third_party/rust/generic-array/src/arr.rs @@ -0,0 +1,125 @@ +//! Implementation for `arr!` macro. + +use super::ArrayLength; +use core::ops::Add; +use typenum::U1; + +/// Helper trait for `arr!` macro +pub trait AddLength>: ArrayLength { + /// Resulting length + type Output: ArrayLength; +} + +impl AddLength for N1 +where + N1: ArrayLength + Add, + N2: ArrayLength, + >::Output: ArrayLength, +{ + type Output = >::Output; +} + +/// Helper type for `arr!` macro +pub type Inc = >::Output; + +#[doc(hidden)] +#[macro_export] +macro_rules! arr_impl { + (@replace_expr $e:expr) => { 1 }; + ($T:ty; $N:ty, [$($x:expr),*], []) => ({ + const __ARR_LENGTH: usize = 0 $(+ $crate::arr_impl!(@replace_expr $x) )*; + + #[inline(always)] + fn __do_transmute>(arr: [T; __ARR_LENGTH]) -> $crate::GenericArray { + unsafe { $crate::transmute(arr) } + } + + let _: [(); <$N as $crate::typenum::Unsigned>::USIZE] = [(); __ARR_LENGTH]; + + __do_transmute::<$T, $N>([$($x as $T),*]) + }); + ($T:ty; $N:ty, [], [$x1:expr]) => ( + $crate::arr_impl!($T; $crate::arr::Inc<$T, $N>, [$x1], []) + ); + ($T:ty; $N:ty, [], [$x1:expr, $($x:expr),+]) => ( + $crate::arr_impl!($T; $crate::arr::Inc<$T, $N>, [$x1], [$($x),+]) + ); + ($T:ty; $N:ty, [$($y:expr),+], [$x1:expr]) => ( + $crate::arr_impl!($T; $crate::arr::Inc<$T, $N>, [$($y),+, $x1], []) + ); + ($T:ty; $N:ty, [$($y:expr),+], [$x1:expr, $($x:expr),+]) => ( + $crate::arr_impl!($T; $crate::arr::Inc<$T, $N>, [$($y),+, $x1], [$($x),+]) + ); +} + +/// Macro allowing for easy generation of Generic Arrays. +/// Example: `let test = arr![u32; 1, 2, 3];` +#[macro_export] +macro_rules! arr { + ($T:ty; $(,)*) => ({ + unsafe { $crate::transmute::<[$T; 0], $crate::GenericArray<$T, $crate::typenum::U0>>([]) } + }); + ($T:ty; $($x:expr),* $(,)*) => ( + $crate::arr_impl!($T; $crate::typenum::U0, [], [$($x),*]) + ); + ($($x:expr,)+) => (arr![$($x),+]); + () => ("""Macro requires a type, e.g. `let array = arr![u32; 1, 2, 3];`") +} + +mod doctests_only { + /// + /// # With ellision + /// + /// Testing that lifetimes aren't transmuted when they're ellided. + /// + /// ```compile_fail + /// #[macro_use] extern crate generic_array; + /// fn main() { + /// fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'static A { + /// arr![&A; a][0] + /// } + /// } + /// ``` + /// + /// ```rust + /// #[macro_use] extern crate generic_array; + /// fn main() { + /// fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'a A { + /// arr![&A; a][0] + /// } + /// } + /// ``` + /// + /// # Without ellision + /// + /// Testing that lifetimes aren't transmuted when they're specified explicitly. + /// + /// ```compile_fail + /// #[macro_use] extern crate generic_array; + /// fn main() { + /// fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'static A { + /// arr![&'a A; a][0] + /// } + /// } + /// ``` + /// + /// ```compile_fail + /// #[macro_use] extern crate generic_array; + /// fn main() { + /// fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'static A { + /// arr![&'static A; a][0] + /// } + /// } + /// ``` + /// + /// ```rust + /// #[macro_use] extern crate generic_array; + /// fn main() { + /// fn unsound_lifetime_extension<'a, A>(a: &'a A) -> &'a A { + /// arr![&'a A; a][0] + /// } + /// } + /// ``` + #[allow(dead_code)] + pub enum DocTests {} +} diff --git a/third_party/rust/generic-array/src/functional.rs b/third_party/rust/generic-array/src/functional.rs new file mode 100644 index 0000000000..2ddcc5c4c4 --- /dev/null +++ b/third_party/rust/generic-array/src/functional.rs @@ -0,0 +1,95 @@ +//! Functional programming with generic sequences +//! +//! Please see `tests/generics.rs` for examples of how to best use these in your generic functions. + +use super::ArrayLength; +use core::iter::FromIterator; + +use crate::sequence::*; + +/// Defines the relationship between one generic sequence and another, +/// for operations such as `map` and `zip`. +pub unsafe trait MappedGenericSequence: GenericSequence +where + Self::Length: ArrayLength, +{ + /// Mapped sequence type + type Mapped: GenericSequence; +} + +unsafe impl<'a, T, U, S: MappedGenericSequence> MappedGenericSequence for &'a S +where + &'a S: GenericSequence, + S: GenericSequence>::Length>, + >::Length: ArrayLength, +{ + type Mapped = >::Mapped; +} + +unsafe impl<'a, T, U, S: MappedGenericSequence> MappedGenericSequence for &'a mut S +where + &'a mut S: GenericSequence, + S: GenericSequence>::Length>, + >::Length: ArrayLength, +{ + type Mapped = >::Mapped; +} + +/// Accessor type for a mapped generic sequence +pub type MappedSequence = + <>::Mapped as GenericSequence>::Sequence; + +/// Defines functional programming methods for generic sequences +pub unsafe trait FunctionalSequence: GenericSequence { + /// Maps a `GenericSequence` to another `GenericSequence`. + /// + /// If the mapping function panics, any already initialized elements in the new sequence + /// will be dropped, AND any unused elements in the source sequence will also be dropped. + fn map(self, f: F) -> MappedSequence + where + Self: MappedGenericSequence, + Self::Length: ArrayLength, + F: FnMut(Self::Item) -> U, + { + FromIterator::from_iter(self.into_iter().map(f)) + } + + /// Combines two `GenericSequence` instances and iterates through both of them, + /// initializing a new `GenericSequence` with the result of the zipped mapping function. + /// + /// If the mapping function panics, any already initialized elements in the new sequence + /// will be dropped, AND any unused elements in the source sequences will also be dropped. + #[inline] + fn zip(self, rhs: Rhs, f: F) -> MappedSequence + where + Self: MappedGenericSequence, + Rhs: MappedGenericSequence>, + Self::Length: ArrayLength + ArrayLength, + Rhs: GenericSequence, + F: FnMut(Self::Item, Rhs::Item) -> U, + { + rhs.inverted_zip2(self, f) + } + + /// Folds (or reduces) a sequence of data into a single value. + /// + /// If the fold function panics, any unused elements will be dropped. + fn fold(self, init: U, f: F) -> U + where + F: FnMut(U, Self::Item) -> U, + { + self.into_iter().fold(init, f) + } +} + +unsafe impl<'a, T, S: GenericSequence> FunctionalSequence for &'a S +where + &'a S: GenericSequence, +{ +} + +unsafe impl<'a, T, S: GenericSequence> FunctionalSequence for &'a mut S +where + &'a mut S: GenericSequence, +{ +} diff --git a/third_party/rust/generic-array/src/hex.rs b/third_party/rust/generic-array/src/hex.rs new file mode 100644 index 0000000000..33c796f3c9 --- /dev/null +++ b/third_party/rust/generic-array/src/hex.rs @@ -0,0 +1,105 @@ +//! Generic array are commonly used as a return value for hash digests, so +//! it's a good idea to allow to hexlify them easily. This module implements +//! `std::fmt::LowerHex` and `std::fmt::UpperHex` traits. +//! +//! Example: +//! +//! ```rust +//! # #[macro_use] +//! # extern crate generic_array; +//! # extern crate typenum; +//! # fn main() { +//! let array = arr![u8; 10, 20, 30]; +//! assert_eq!(format!("{:x}", array), "0a141e"); +//! # } +//! ``` +//! + +use core::{fmt, str, ops::Add, cmp::min}; + +use typenum::*; + +use crate::{ArrayLength, GenericArray}; + +static LOWER_CHARS: &'static [u8] = b"0123456789abcdef"; +static UPPER_CHARS: &'static [u8] = b"0123456789ABCDEF"; + +impl> fmt::LowerHex for GenericArray +where + T: Add, + >::Output: ArrayLength, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let max_digits = f.precision().unwrap_or_else(|| self.len() * 2); + let max_hex = (max_digits >> 1) + (max_digits & 1); + + if T::USIZE < 1024 { + // For small arrays use a stack allocated + // buffer of 2x number of bytes + let mut res = GenericArray::>::default(); + + self.iter().take(max_hex).enumerate().for_each(|(i, c)| { + res[i * 2] = LOWER_CHARS[(c >> 4) as usize]; + res[i * 2 + 1] = LOWER_CHARS[(c & 0xF) as usize]; + }); + + f.write_str(unsafe { str::from_utf8_unchecked(&res[..max_digits]) })?; + } else { + // For large array use chunks of up to 1024 bytes (2048 hex chars) + let mut buf = [0u8; 2048]; + let mut digits_left = max_digits; + + for chunk in self[..max_hex].chunks(1024) { + chunk.iter().enumerate().for_each(|(i, c)| { + buf[i * 2] = LOWER_CHARS[(c >> 4) as usize]; + buf[i * 2 + 1] = LOWER_CHARS[(c & 0xF) as usize]; + }); + + let n = min(chunk.len() * 2, digits_left); + f.write_str(unsafe { str::from_utf8_unchecked(&buf[..n]) })?; + digits_left -= n; + } + } + Ok(()) + } +} + +impl> fmt::UpperHex for GenericArray +where + T: Add, + >::Output: ArrayLength, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let max_digits = f.precision().unwrap_or_else(|| self.len() * 2); + let max_hex = (max_digits >> 1) + (max_digits & 1); + + if T::USIZE < 1024 { + // For small arrays use a stack allocated + // buffer of 2x number of bytes + let mut res = GenericArray::>::default(); + + self.iter().take(max_hex).enumerate().for_each(|(i, c)| { + res[i * 2] = UPPER_CHARS[(c >> 4) as usize]; + res[i * 2 + 1] = UPPER_CHARS[(c & 0xF) as usize]; + }); + + f.write_str(unsafe { str::from_utf8_unchecked(&res[..max_digits]) })?; + } else { + // For large array use chunks of up to 1024 bytes (2048 hex chars) + let mut buf = [0u8; 2048]; + let mut digits_left = max_digits; + + for chunk in self[..max_hex].chunks(1024) { + chunk.iter().enumerate().for_each(|(i, c)| { + buf[i * 2] = UPPER_CHARS[(c >> 4) as usize]; + buf[i * 2 + 1] = UPPER_CHARS[(c & 0xF) as usize]; + }); + + let n = min(chunk.len() * 2, digits_left); + f.write_str(unsafe { str::from_utf8_unchecked(&buf[..n]) })?; + digits_left -= n; + } + } + Ok(()) + } +} diff --git a/third_party/rust/generic-array/src/impl_serde.rs b/third_party/rust/generic-array/src/impl_serde.rs new file mode 100644 index 0000000000..49c095a5de --- /dev/null +++ b/third_party/rust/generic-array/src/impl_serde.rs @@ -0,0 +1,108 @@ +//! Serde serialization/deserialization implementation + +use core::fmt; +use core::marker::PhantomData; +use serde::de::{self, SeqAccess, Visitor}; +use serde::{ser::SerializeTuple, Deserialize, Deserializer, Serialize, Serializer}; +use {ArrayLength, GenericArray}; + +impl Serialize for GenericArray +where + T: Serialize, + N: ArrayLength, +{ + #[inline] + fn serialize(&self, serializer: S) -> Result + where + S: Serializer, + { + let mut tup = serializer.serialize_tuple(N::USIZE)?; + for el in self { + tup.serialize_element(el)?; + } + + tup.end() + } +} + +struct GAVisitor { + _t: PhantomData, + _n: PhantomData, +} + +impl<'de, T, N> Visitor<'de> for GAVisitor +where + T: Deserialize<'de> + Default, + N: ArrayLength, +{ + type Value = GenericArray; + + fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str("struct GenericArray") + } + + fn visit_seq(self, mut seq: A) -> Result, A::Error> + where + A: SeqAccess<'de>, + { + let mut result = GenericArray::default(); + for i in 0..N::USIZE { + result[i] = seq + .next_element()? + .ok_or_else(|| de::Error::invalid_length(i, &self))?; + } + Ok(result) + } +} + +impl<'de, T, N> Deserialize<'de> for GenericArray +where + T: Deserialize<'de> + Default, + N: ArrayLength, +{ + fn deserialize(deserializer: D) -> Result, D::Error> + where + D: Deserializer<'de>, + { + let visitor = GAVisitor { + _t: PhantomData, + _n: PhantomData, + }; + deserializer.deserialize_tuple(N::USIZE, visitor) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use bincode; + use typenum; + + #[test] + fn test_serialize() { + let array = GenericArray::::default(); + let serialized = bincode::serialize(&array); + assert!(serialized.is_ok()); + } + + #[test] + fn test_deserialize() { + let mut array = GenericArray::::default(); + array[0] = 1; + array[1] = 2; + let serialized = bincode::serialize(&array).unwrap(); + let deserialized = bincode::deserialize::>(&serialized); + assert!(deserialized.is_ok()); + let array = deserialized.unwrap(); + assert_eq!(array[0], 1); + assert_eq!(array[1], 2); + } + + #[test] + fn test_serialized_size() { + let array = GenericArray::::default(); + let size = bincode::serialized_size(&array).unwrap(); + assert_eq!(size, 1); + } + +} diff --git a/third_party/rust/generic-array/src/impl_zeroize.rs b/third_party/rust/generic-array/src/impl_zeroize.rs new file mode 100644 index 0000000000..9937e4b150 --- /dev/null +++ b/third_party/rust/generic-array/src/impl_zeroize.rs @@ -0,0 +1,25 @@ +use {ArrayLength, GenericArray}; + +use zeroize::Zeroize; + +#[cfg_attr(docsrs, doc(cfg(feature = "zeroize")))] +impl> Zeroize for GenericArray { + fn zeroize(&mut self) { + self.as_mut_slice().iter_mut().zeroize() + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_zeroize() { + let mut array = GenericArray::::default(); + array[0] = 4; + array[1] = 9; + array.zeroize(); + assert_eq!(array[0], 0); + assert_eq!(array[1], 0); + } +} \ No newline at end of file diff --git a/third_party/rust/generic-array/src/impls.rs b/third_party/rust/generic-array/src/impls.rs new file mode 100644 index 0000000000..47ecc1d31d --- /dev/null +++ b/third_party/rust/generic-array/src/impls.rs @@ -0,0 +1,269 @@ +use core::borrow::{Borrow, BorrowMut}; +use core::cmp::Ordering; +use core::fmt::{self, Debug}; +use core::hash::{Hash, Hasher}; + +use super::{ArrayLength, GenericArray}; + +use crate::functional::*; +use crate::sequence::*; + +impl Default for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn default() -> Self { + Self::generate(|_| T::default()) + } +} + +impl Clone for GenericArray +where + N: ArrayLength, +{ + fn clone(&self) -> GenericArray { + self.map(Clone::clone) + } +} + +impl Copy for GenericArray +where + N: ArrayLength, + N::ArrayType: Copy, +{ +} + +impl PartialEq for GenericArray +where + N: ArrayLength, +{ + fn eq(&self, other: &Self) -> bool { + **self == **other + } +} +impl Eq for GenericArray where N: ArrayLength {} + +impl PartialOrd for GenericArray +where + N: ArrayLength, +{ + fn partial_cmp(&self, other: &GenericArray) -> Option { + PartialOrd::partial_cmp(self.as_slice(), other.as_slice()) + } +} + +impl Ord for GenericArray +where + N: ArrayLength, +{ + fn cmp(&self, other: &GenericArray) -> Ordering { + Ord::cmp(self.as_slice(), other.as_slice()) + } +} + +impl Debug for GenericArray +where + N: ArrayLength, +{ + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + self[..].fmt(fmt) + } +} + +impl Borrow<[T]> for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn borrow(&self) -> &[T] { + &self[..] + } +} + +impl BorrowMut<[T]> for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn borrow_mut(&mut self) -> &mut [T] { + &mut self[..] + } +} + +impl AsRef<[T]> for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn as_ref(&self) -> &[T] { + &self[..] + } +} + +impl AsMut<[T]> for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn as_mut(&mut self) -> &mut [T] { + &mut self[..] + } +} + +impl Hash for GenericArray +where + N: ArrayLength, +{ + fn hash(&self, state: &mut H) + where + H: Hasher, + { + Hash::hash(&self[..], state) + } +} + +macro_rules! impl_from { + ($($n: expr => $ty: ty),*) => { + $( + impl From<[T; $n]> for GenericArray { + #[inline(always)] + fn from(arr: [T; $n]) -> Self { + unsafe { $crate::transmute(arr) } + } + } + + #[cfg(relaxed_coherence)] + impl From> for [T; $n] { + #[inline(always)] + fn from(sel: GenericArray) -> [T; $n] { + unsafe { $crate::transmute(sel) } + } + } + + impl<'a, T> From<&'a [T; $n]> for &'a GenericArray { + #[inline] + fn from(slice: &[T; $n]) -> &GenericArray { + unsafe { &*(slice.as_ptr() as *const GenericArray) } + } + } + + impl<'a, T> From<&'a mut [T; $n]> for &'a mut GenericArray { + #[inline] + fn from(slice: &mut [T; $n]) -> &mut GenericArray { + unsafe { &mut *(slice.as_mut_ptr() as *mut GenericArray) } + } + } + + #[cfg(not(relaxed_coherence))] + impl Into<[T; $n]> for GenericArray { + #[inline(always)] + fn into(self) -> [T; $n] { + unsafe { $crate::transmute(self) } + } + } + + impl AsRef<[T; $n]> for GenericArray { + #[inline] + fn as_ref(&self) -> &[T; $n] { + unsafe { $crate::transmute(self) } + } + } + + impl AsMut<[T; $n]> for GenericArray { + #[inline] + fn as_mut(&mut self) -> &mut [T; $n] { + unsafe { $crate::transmute(self) } + } + } + )* + } +} + +impl_from! { + 1 => ::typenum::U1, + 2 => ::typenum::U2, + 3 => ::typenum::U3, + 4 => ::typenum::U4, + 5 => ::typenum::U5, + 6 => ::typenum::U6, + 7 => ::typenum::U7, + 8 => ::typenum::U8, + 9 => ::typenum::U9, + 10 => ::typenum::U10, + 11 => ::typenum::U11, + 12 => ::typenum::U12, + 13 => ::typenum::U13, + 14 => ::typenum::U14, + 15 => ::typenum::U15, + 16 => ::typenum::U16, + 17 => ::typenum::U17, + 18 => ::typenum::U18, + 19 => ::typenum::U19, + 20 => ::typenum::U20, + 21 => ::typenum::U21, + 22 => ::typenum::U22, + 23 => ::typenum::U23, + 24 => ::typenum::U24, + 25 => ::typenum::U25, + 26 => ::typenum::U26, + 27 => ::typenum::U27, + 28 => ::typenum::U28, + 29 => ::typenum::U29, + 30 => ::typenum::U30, + 31 => ::typenum::U31, + 32 => ::typenum::U32 +} + +#[cfg(feature = "more_lengths")] +impl_from! { + 33 => ::typenum::U33, + 34 => ::typenum::U34, + 35 => ::typenum::U35, + 36 => ::typenum::U36, + 37 => ::typenum::U37, + 38 => ::typenum::U38, + 39 => ::typenum::U39, + 40 => ::typenum::U40, + 41 => ::typenum::U41, + 42 => ::typenum::U42, + 43 => ::typenum::U43, + 44 => ::typenum::U44, + 45 => ::typenum::U45, + 46 => ::typenum::U46, + 47 => ::typenum::U47, + 48 => ::typenum::U48, + 49 => ::typenum::U49, + 50 => ::typenum::U50, + 51 => ::typenum::U51, + 52 => ::typenum::U52, + 53 => ::typenum::U53, + 54 => ::typenum::U54, + 55 => ::typenum::U55, + 56 => ::typenum::U56, + 57 => ::typenum::U57, + 58 => ::typenum::U58, + 59 => ::typenum::U59, + 60 => ::typenum::U60, + 61 => ::typenum::U61, + 62 => ::typenum::U62, + 63 => ::typenum::U63, + 64 => ::typenum::U64, + + 70 => ::typenum::U70, + 80 => ::typenum::U80, + 90 => ::typenum::U90, + + 100 => ::typenum::U100, + 200 => ::typenum::U200, + 300 => ::typenum::U300, + 400 => ::typenum::U400, + 500 => ::typenum::U500, + + 128 => ::typenum::U128, + 256 => ::typenum::U256, + 512 => ::typenum::U512, + + 1000 => ::typenum::U1000, + 1024 => ::typenum::U1024 +} diff --git a/third_party/rust/generic-array/src/iter.rs b/third_party/rust/generic-array/src/iter.rs new file mode 100644 index 0000000000..784ffa9068 --- /dev/null +++ b/third_party/rust/generic-array/src/iter.rs @@ -0,0 +1,251 @@ +//! `GenericArray` iterator implementation. + +use super::{ArrayLength, GenericArray}; +use core::iter::FusedIterator; +use core::mem::ManuallyDrop; +use core::{cmp, fmt, mem, ptr}; + +/// An iterator that moves out of a `GenericArray` +pub struct GenericArrayIter> { + // Invariants: index <= index_back <= N + // Only values in array[index..index_back] are alive at any given time. + // Values from array[..index] and array[index_back..] are already moved/dropped. + array: ManuallyDrop>, + index: usize, + index_back: usize, +} + +#[cfg(test)] +mod test { + use super::*; + + fn send(_iter: I) {} + + #[test] + fn test_send_iter() { + send(GenericArray::from([1, 2, 3, 4]).into_iter()); + } +} + +impl GenericArrayIter +where + N: ArrayLength, +{ + /// Returns the remaining items of this iterator as a slice + #[inline] + pub fn as_slice(&self) -> &[T] { + &self.array.as_slice()[self.index..self.index_back] + } + + /// Returns the remaining items of this iterator as a mutable slice + #[inline] + pub fn as_mut_slice(&mut self) -> &mut [T] { + &mut self.array.as_mut_slice()[self.index..self.index_back] + } +} + +impl IntoIterator for GenericArray +where + N: ArrayLength, +{ + type Item = T; + type IntoIter = GenericArrayIter; + + fn into_iter(self) -> Self::IntoIter { + GenericArrayIter { + array: ManuallyDrop::new(self), + index: 0, + index_back: N::USIZE, + } + } +} + +// Based on work in rust-lang/rust#49000 +impl fmt::Debug for GenericArrayIter +where + N: ArrayLength, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_tuple("GenericArrayIter") + .field(&self.as_slice()) + .finish() + } +} + +impl Drop for GenericArrayIter +where + N: ArrayLength, +{ + #[inline] + fn drop(&mut self) { + if mem::needs_drop::() { + // Drop values that are still alive. + for p in self.as_mut_slice() { + unsafe { + ptr::drop_in_place(p); + } + } + } + } +} + +// Based on work in rust-lang/rust#49000 +impl Clone for GenericArrayIter +where + N: ArrayLength, +{ + fn clone(&self) -> Self { + // This places all cloned elements at the start of the new array iterator, + // not at their original indices. + + let mut array = unsafe { ptr::read(&self.array) }; + let mut index_back = 0; + + for (dst, src) in array.as_mut_slice().into_iter().zip(self.as_slice()) { + unsafe { ptr::write(dst, src.clone()) }; + index_back += 1; + } + + GenericArrayIter { + array, + index: 0, + index_back, + } + } +} + +impl Iterator for GenericArrayIter +where + N: ArrayLength, +{ + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + if self.index < self.index_back { + let p = unsafe { Some(ptr::read(self.array.get_unchecked(self.index))) }; + + self.index += 1; + + p + } else { + None + } + } + + fn fold(mut self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + let ret = unsafe { + let GenericArrayIter { + ref array, + ref mut index, + index_back, + } = self; + + let remaining = &array[*index..index_back]; + + remaining.iter().fold(init, |acc, src| { + let value = ptr::read(src); + + *index += 1; + + f(acc, value) + }) + }; + + // ensure the drop happens here after iteration + drop(self); + + ret + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let len = self.len(); + (len, Some(len)) + } + + #[inline] + fn count(self) -> usize { + self.len() + } + + fn nth(&mut self, n: usize) -> Option { + // First consume values prior to the nth. + let ndrop = cmp::min(n, self.len()); + + for p in &mut self.array[self.index..self.index + ndrop] { + self.index += 1; + + unsafe { + ptr::drop_in_place(p); + } + } + + self.next() + } + + #[inline] + fn last(mut self) -> Option { + // Note, everything else will correctly drop first as `self` leaves scope. + self.next_back() + } +} + +impl DoubleEndedIterator for GenericArrayIter +where + N: ArrayLength, +{ + fn next_back(&mut self) -> Option { + if self.index < self.index_back { + self.index_back -= 1; + + unsafe { Some(ptr::read(self.array.get_unchecked(self.index_back))) } + } else { + None + } + } + + fn rfold(mut self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + let ret = unsafe { + let GenericArrayIter { + ref array, + index, + ref mut index_back, + } = self; + + let remaining = &array[index..*index_back]; + + remaining.iter().rfold(init, |acc, src| { + let value = ptr::read(src); + + *index_back -= 1; + + f(acc, value) + }) + }; + + // ensure the drop happens here after iteration + drop(self); + + ret + } +} + +impl ExactSizeIterator for GenericArrayIter +where + N: ArrayLength, +{ + fn len(&self) -> usize { + self.index_back - self.index + } +} + +impl FusedIterator for GenericArrayIter where N: ArrayLength {} + +// TODO: Implement `TrustedLen` when stabilized diff --git a/third_party/rust/generic-array/src/lib.rs b/third_party/rust/generic-array/src/lib.rs new file mode 100644 index 0000000000..43ab26ff56 --- /dev/null +++ b/third_party/rust/generic-array/src/lib.rs @@ -0,0 +1,679 @@ +//! This crate implements a structure that can be used as a generic array type. +//! Core Rust array types `[T; N]` can't be used generically with +//! respect to `N`, so for example this: +//! +//! ```rust{compile_fail} +//! struct Foo { +//! data: [T; N] +//! } +//! ``` +//! +//! won't work. +//! +//! **generic-array** exports a `GenericArray` type, which lets +//! the above be implemented as: +//! +//! ```rust +//! use generic_array::{ArrayLength, GenericArray}; +//! +//! struct Foo> { +//! data: GenericArray +//! } +//! ``` +//! +//! The `ArrayLength` trait is implemented by default for +//! [unsigned integer types](../typenum/uint/index.html) from +//! [typenum](../typenum/index.html): +//! +//! ```rust +//! # use generic_array::{ArrayLength, GenericArray}; +//! use generic_array::typenum::U5; +//! +//! struct Foo> { +//! data: GenericArray +//! } +//! +//! # fn main() { +//! let foo = Foo::{data: GenericArray::default()}; +//! # } +//! ``` +//! +//! For example, `GenericArray` would work almost like `[T; 5]`: +//! +//! ```rust +//! # use generic_array::{ArrayLength, GenericArray}; +//! use generic_array::typenum::U5; +//! +//! struct Foo> { +//! data: GenericArray +//! } +//! +//! # fn main() { +//! let foo = Foo::{data: GenericArray::default()}; +//! # } +//! ``` +//! +//! For ease of use, an `arr!` macro is provided - example below: +//! +//! ``` +//! # #[macro_use] +//! # extern crate generic_array; +//! # extern crate typenum; +//! # fn main() { +//! let array = arr![u32; 1, 2, 3]; +//! assert_eq!(array[2], 3); +//! # } +//! ``` + +#![deny(missing_docs)] +#![deny(meta_variable_misuse)] +#![no_std] + +#[cfg(feature = "serde")] +extern crate serde; + +#[cfg(feature = "zeroize")] +extern crate zeroize; + +#[cfg(test)] +extern crate bincode; + +pub extern crate typenum; + +mod hex; +mod impls; + +#[cfg(feature = "serde")] +mod impl_serde; + +#[cfg(feature = "zeroize")] +mod impl_zeroize; + +use core::iter::FromIterator; +use core::marker::PhantomData; +use core::mem::{MaybeUninit, ManuallyDrop}; +use core::ops::{Deref, DerefMut}; +use core::{mem, ptr, slice}; +use typenum::bit::{B0, B1}; +use typenum::uint::{UInt, UTerm, Unsigned}; + +#[cfg_attr(test, macro_use)] +pub mod arr; +pub mod functional; +pub mod iter; +pub mod sequence; + +use self::functional::*; +pub use self::iter::GenericArrayIter; +use self::sequence::*; + +/// Trait making `GenericArray` work, marking types to be used as length of an array +pub unsafe trait ArrayLength: Unsigned { + /// Associated type representing the array type for the number + type ArrayType; +} + +unsafe impl ArrayLength for UTerm { + #[doc(hidden)] + type ArrayType = [T; 0]; +} + +/// Internal type used to generate a struct of appropriate size +#[allow(dead_code)] +#[repr(C)] +#[doc(hidden)] +pub struct GenericArrayImplEven { + parent1: U, + parent2: U, + _marker: PhantomData, +} + +impl Clone for GenericArrayImplEven { + fn clone(&self) -> GenericArrayImplEven { + GenericArrayImplEven { + parent1: self.parent1.clone(), + parent2: self.parent2.clone(), + _marker: PhantomData, + } + } +} + +impl Copy for GenericArrayImplEven {} + +/// Internal type used to generate a struct of appropriate size +#[allow(dead_code)] +#[repr(C)] +#[doc(hidden)] +pub struct GenericArrayImplOdd { + parent1: U, + parent2: U, + data: T, +} + +impl Clone for GenericArrayImplOdd { + fn clone(&self) -> GenericArrayImplOdd { + GenericArrayImplOdd { + parent1: self.parent1.clone(), + parent2: self.parent2.clone(), + data: self.data.clone(), + } + } +} + +impl Copy for GenericArrayImplOdd {} + +unsafe impl> ArrayLength for UInt { + #[doc(hidden)] + type ArrayType = GenericArrayImplEven; +} + +unsafe impl> ArrayLength for UInt { + #[doc(hidden)] + type ArrayType = GenericArrayImplOdd; +} + +/// Struct representing a generic array - `GenericArray` works like [T; N] +#[allow(dead_code)] +#[repr(transparent)] +pub struct GenericArray> { + data: U::ArrayType, +} + +unsafe impl> Send for GenericArray {} +unsafe impl> Sync for GenericArray {} + +impl Deref for GenericArray +where + N: ArrayLength, +{ + type Target = [T]; + + #[inline(always)] + fn deref(&self) -> &[T] { + unsafe { slice::from_raw_parts(self as *const Self as *const T, N::USIZE) } + } +} + +impl DerefMut for GenericArray +where + N: ArrayLength, +{ + #[inline(always)] + fn deref_mut(&mut self) -> &mut [T] { + unsafe { slice::from_raw_parts_mut(self as *mut Self as *mut T, N::USIZE) } + } +} + +/// Creates an array one element at a time using a mutable iterator +/// you can write to with `ptr::write`. +/// +/// Increment the position while iterating to mark off created elements, +/// which will be dropped if `into_inner` is not called. +#[doc(hidden)] +pub struct ArrayBuilder> { + array: MaybeUninit>, + position: usize, +} + +impl> ArrayBuilder { + #[doc(hidden)] + #[inline] + pub unsafe fn new() -> ArrayBuilder { + ArrayBuilder { + array: MaybeUninit::uninit(), + position: 0, + } + } + + /// Creates a mutable iterator for writing to the array using `ptr::write`. + /// + /// Increment the position value given as a mutable reference as you iterate + /// to mark how many elements have been created. + #[doc(hidden)] + #[inline] + pub unsafe fn iter_position(&mut self) -> (slice::IterMut, &mut usize) { + ((&mut *self.array.as_mut_ptr()).iter_mut(), &mut self.position) + } + + /// When done writing (assuming all elements have been written to), + /// get the inner array. + #[doc(hidden)] + #[inline] + pub unsafe fn into_inner(self) -> GenericArray { + let array = ptr::read(&self.array); + + mem::forget(self); + + array.assume_init() + } +} + +impl> Drop for ArrayBuilder { + fn drop(&mut self) { + if mem::needs_drop::() { + unsafe { + for value in &mut (&mut *self.array.as_mut_ptr())[..self.position] { + ptr::drop_in_place(value); + } + } + } + } +} + +/// Consumes an array. +/// +/// Increment the position while iterating and any leftover elements +/// will be dropped if position does not go to N +#[doc(hidden)] +pub struct ArrayConsumer> { + array: ManuallyDrop>, + position: usize, +} + +impl> ArrayConsumer { + #[doc(hidden)] + #[inline] + pub unsafe fn new(array: GenericArray) -> ArrayConsumer { + ArrayConsumer { + array: ManuallyDrop::new(array), + position: 0, + } + } + + /// Creates an iterator and mutable reference to the internal position + /// to keep track of consumed elements. + /// + /// Increment the position as you iterate to mark off consumed elements + #[doc(hidden)] + #[inline] + pub unsafe fn iter_position(&mut self) -> (slice::Iter, &mut usize) { + (self.array.iter(), &mut self.position) + } +} + +impl> Drop for ArrayConsumer { + fn drop(&mut self) { + if mem::needs_drop::() { + for value in &mut self.array[self.position..N::USIZE] { + unsafe { + ptr::drop_in_place(value); + } + } + } + } +} + +impl<'a, T: 'a, N> IntoIterator for &'a GenericArray +where + N: ArrayLength, +{ + type IntoIter = slice::Iter<'a, T>; + type Item = &'a T; + + fn into_iter(self: &'a GenericArray) -> Self::IntoIter { + self.as_slice().iter() + } +} + +impl<'a, T: 'a, N> IntoIterator for &'a mut GenericArray +where + N: ArrayLength, +{ + type IntoIter = slice::IterMut<'a, T>; + type Item = &'a mut T; + + fn into_iter(self: &'a mut GenericArray) -> Self::IntoIter { + self.as_mut_slice().iter_mut() + } +} + +impl FromIterator for GenericArray +where + N: ArrayLength, +{ + fn from_iter(iter: I) -> GenericArray + where + I: IntoIterator, + { + unsafe { + let mut destination = ArrayBuilder::new(); + + { + let (destination_iter, position) = destination.iter_position(); + + iter.into_iter() + .zip(destination_iter) + .for_each(|(src, dst)| { + ptr::write(dst, src); + + *position += 1; + }); + } + + if destination.position < N::USIZE { + from_iter_length_fail(destination.position, N::USIZE); + } + + destination.into_inner() + } + } +} + +#[inline(never)] +#[cold] +fn from_iter_length_fail(length: usize, expected: usize) -> ! { + panic!( + "GenericArray::from_iter received {} elements but expected {}", + length, expected + ); +} + +unsafe impl GenericSequence for GenericArray +where + N: ArrayLength, + Self: IntoIterator, +{ + type Length = N; + type Sequence = Self; + + fn generate(mut f: F) -> GenericArray + where + F: FnMut(usize) -> T, + { + unsafe { + let mut destination = ArrayBuilder::new(); + + { + let (destination_iter, position) = destination.iter_position(); + + destination_iter.enumerate().for_each(|(i, dst)| { + ptr::write(dst, f(i)); + + *position += 1; + }); + } + + destination.into_inner() + } + } + + #[doc(hidden)] + fn inverted_zip( + self, + lhs: GenericArray, + mut f: F, + ) -> MappedSequence, B, U> + where + GenericArray: + GenericSequence + MappedGenericSequence, + Self: MappedGenericSequence, + Self::Length: ArrayLength + ArrayLength, + F: FnMut(B, Self::Item) -> U, + { + unsafe { + let mut left = ArrayConsumer::new(lhs); + let mut right = ArrayConsumer::new(self); + + let (left_array_iter, left_position) = left.iter_position(); + let (right_array_iter, right_position) = right.iter_position(); + + FromIterator::from_iter(left_array_iter.zip(right_array_iter).map(|(l, r)| { + let left_value = ptr::read(l); + let right_value = ptr::read(r); + + *left_position += 1; + *right_position += 1; + + f(left_value, right_value) + })) + } + } + + #[doc(hidden)] + fn inverted_zip2(self, lhs: Lhs, mut f: F) -> MappedSequence + where + Lhs: GenericSequence + MappedGenericSequence, + Self: MappedGenericSequence, + Self::Length: ArrayLength + ArrayLength, + F: FnMut(Lhs::Item, Self::Item) -> U, + { + unsafe { + let mut right = ArrayConsumer::new(self); + + let (right_array_iter, right_position) = right.iter_position(); + + FromIterator::from_iter( + lhs.into_iter() + .zip(right_array_iter) + .map(|(left_value, r)| { + let right_value = ptr::read(r); + + *right_position += 1; + + f(left_value, right_value) + }), + ) + } + } +} + +unsafe impl MappedGenericSequence for GenericArray +where + N: ArrayLength + ArrayLength, + GenericArray: GenericSequence, +{ + type Mapped = GenericArray; +} + +unsafe impl FunctionalSequence for GenericArray +where + N: ArrayLength, + Self: GenericSequence, +{ + fn map(self, mut f: F) -> MappedSequence + where + Self::Length: ArrayLength, + Self: MappedGenericSequence, + F: FnMut(T) -> U, + { + unsafe { + let mut source = ArrayConsumer::new(self); + + let (array_iter, position) = source.iter_position(); + + FromIterator::from_iter(array_iter.map(|src| { + let value = ptr::read(src); + + *position += 1; + + f(value) + })) + } + } + + #[inline] + fn zip(self, rhs: Rhs, f: F) -> MappedSequence + where + Self: MappedGenericSequence, + Rhs: MappedGenericSequence>, + Self::Length: ArrayLength + ArrayLength, + Rhs: GenericSequence, + F: FnMut(T, Rhs::Item) -> U, + { + rhs.inverted_zip(self, f) + } + + fn fold(self, init: U, mut f: F) -> U + where + F: FnMut(U, T) -> U, + { + unsafe { + let mut source = ArrayConsumer::new(self); + + let (array_iter, position) = source.iter_position(); + + array_iter.fold(init, |acc, src| { + let value = ptr::read(src); + + *position += 1; + + f(acc, value) + }) + } + } +} + +impl GenericArray +where + N: ArrayLength, +{ + /// Extracts a slice containing the entire array. + #[inline] + pub fn as_slice(&self) -> &[T] { + self.deref() + } + + /// Extracts a mutable slice containing the entire array. + #[inline] + pub fn as_mut_slice(&mut self) -> &mut [T] { + self.deref_mut() + } + + /// Converts slice to a generic array reference with inferred length; + /// + /// Length of the slice must be equal to the length of the array. + #[inline] + pub fn from_slice(slice: &[T]) -> &GenericArray { + slice.into() + } + + /// Converts mutable slice to a mutable generic array reference + /// + /// Length of the slice must be equal to the length of the array. + #[inline] + pub fn from_mut_slice(slice: &mut [T]) -> &mut GenericArray { + slice.into() + } +} + +impl<'a, T, N: ArrayLength> From<&'a [T]> for &'a GenericArray { + /// Converts slice to a generic array reference with inferred length; + /// + /// Length of the slice must be equal to the length of the array. + #[inline] + fn from(slice: &[T]) -> &GenericArray { + assert_eq!(slice.len(), N::USIZE); + + unsafe { &*(slice.as_ptr() as *const GenericArray) } + } +} + +impl<'a, T, N: ArrayLength> From<&'a mut [T]> for &'a mut GenericArray { + /// Converts mutable slice to a mutable generic array reference + /// + /// Length of the slice must be equal to the length of the array. + #[inline] + fn from(slice: &mut [T]) -> &mut GenericArray { + assert_eq!(slice.len(), N::USIZE); + + unsafe { &mut *(slice.as_mut_ptr() as *mut GenericArray) } + } +} + +impl GenericArray +where + N: ArrayLength, +{ + /// Construct a `GenericArray` from a slice by cloning its content + /// + /// Length of the slice must be equal to the length of the array + #[inline] + pub fn clone_from_slice(list: &[T]) -> GenericArray { + Self::from_exact_iter(list.iter().cloned()) + .expect("Slice must be the same length as the array") + } +} + +impl GenericArray +where + N: ArrayLength, +{ + /// Creates a new `GenericArray` instance from an iterator with a specific size. + /// + /// Returns `None` if the size is not equal to the number of elements in the `GenericArray`. + pub fn from_exact_iter(iter: I) -> Option + where + I: IntoIterator, + { + let mut iter = iter.into_iter(); + + unsafe { + let mut destination = ArrayBuilder::new(); + + { + let (destination_iter, position) = destination.iter_position(); + + destination_iter.zip(&mut iter).for_each(|(dst, src)| { + ptr::write(dst, src); + + *position += 1; + }); + + // The iterator produced fewer than `N` elements. + if *position != N::USIZE { + return None; + } + + // The iterator produced more than `N` elements. + if iter.next().is_some() { + return None; + } + } + + Some(destination.into_inner()) + } + } +} + +/// A reimplementation of the `transmute` function, avoiding problems +/// when the compiler can't prove equal sizes. +#[inline] +#[doc(hidden)] +pub unsafe fn transmute(a: A) -> B { + let a = ManuallyDrop::new(a); + ::core::ptr::read(&*a as *const A as *const B) +} + +#[cfg(test)] +mod test { + // Compile with: + // cargo rustc --lib --profile test --release -- + // -C target-cpu=native -C opt-level=3 --emit asm + // and view the assembly to make sure test_assembly generates + // SIMD instructions instead of a naive loop. + + #[inline(never)] + pub fn black_box(val: T) -> T { + use core::{mem, ptr}; + + let ret = unsafe { ptr::read_volatile(&val) }; + mem::forget(val); + ret + } + + #[test] + fn test_assembly() { + use crate::functional::*; + + let a = black_box(arr![i32; 1, 3, 5, 7]); + let b = black_box(arr![i32; 2, 4, 6, 8]); + + let c = (&a).zip(b, |l, r| l + r); + + let d = a.fold(0, |a, x| a + x); + + assert_eq!(c, arr![i32; 3, 7, 11, 15]); + + assert_eq!(d, 16); + } +} diff --git a/third_party/rust/generic-array/src/sequence.rs b/third_party/rust/generic-array/src/sequence.rs new file mode 100644 index 0000000000..0119d3db67 --- /dev/null +++ b/third_party/rust/generic-array/src/sequence.rs @@ -0,0 +1,380 @@ +//! Useful traits for manipulating sequences of data stored in `GenericArray`s + +use super::*; +use core::ops::{Add, Sub}; +use core::mem::MaybeUninit; +use core::ptr; +use typenum::operator_aliases::*; + +/// Defines some sequence with an associated length and iteration capabilities. +/// +/// This is useful for passing N-length generic arrays as generics. +pub unsafe trait GenericSequence: Sized + IntoIterator { + /// `GenericArray` associated length + type Length: ArrayLength; + + /// Concrete sequence type used in conjuction with reference implementations of `GenericSequence` + type Sequence: GenericSequence + FromIterator; + + /// Initializes a new sequence instance using the given function. + /// + /// If the generator function panics while initializing the sequence, + /// any already initialized elements will be dropped. + fn generate(f: F) -> Self::Sequence + where + F: FnMut(usize) -> T; + + #[doc(hidden)] + fn inverted_zip( + self, + lhs: GenericArray, + mut f: F, + ) -> MappedSequence, B, U> + where + GenericArray: GenericSequence + + MappedGenericSequence, + Self: MappedGenericSequence, + Self::Length: ArrayLength + ArrayLength, + F: FnMut(B, Self::Item) -> U, + { + unsafe { + let mut left = ArrayConsumer::new(lhs); + + let (left_array_iter, left_position) = left.iter_position(); + + FromIterator::from_iter(left_array_iter.zip(self.into_iter()).map( + |(l, right_value)| { + let left_value = ptr::read(l); + + *left_position += 1; + + f(left_value, right_value) + }, + )) + } + } + + #[doc(hidden)] + fn inverted_zip2(self, lhs: Lhs, mut f: F) -> MappedSequence + where + Lhs: GenericSequence + MappedGenericSequence, + Self: MappedGenericSequence, + Self::Length: ArrayLength + ArrayLength, + F: FnMut(Lhs::Item, Self::Item) -> U, + { + FromIterator::from_iter(lhs.into_iter().zip(self.into_iter()).map(|(l, r)| f(l, r))) + } +} + +/// Accessor for `GenericSequence` item type, which is really `IntoIterator::Item` +/// +/// For deeply nested generic mapped sequence types, like shown in `tests/generics.rs`, +/// this can be useful for keeping things organized. +pub type SequenceItem = ::Item; + +unsafe impl<'a, T: 'a, S: GenericSequence> GenericSequence for &'a S +where + &'a S: IntoIterator, +{ + type Length = S::Length; + type Sequence = S::Sequence; + + #[inline] + fn generate(f: F) -> Self::Sequence + where + F: FnMut(usize) -> T, + { + S::generate(f) + } +} + +unsafe impl<'a, T: 'a, S: GenericSequence> GenericSequence for &'a mut S +where + &'a mut S: IntoIterator, +{ + type Length = S::Length; + type Sequence = S::Sequence; + + #[inline] + fn generate(f: F) -> Self::Sequence + where + F: FnMut(usize) -> T, + { + S::generate(f) + } +} + +/// Defines any `GenericSequence` which can be lengthened or extended by appending +/// or prepending an element to it. +/// +/// Any lengthened sequence can be shortened back to the original using `pop_front` or `pop_back` +pub unsafe trait Lengthen: Sized + GenericSequence { + /// `GenericSequence` that has one more element than `Self` + type Longer: Shorten; + + /// Returns a new array with the given element appended to the end of it. + /// + /// Example: + /// + /// ```rust + /// # use generic_array::{arr, sequence::Lengthen}; + /// # fn main() { + /// let a = arr![i32; 1, 2, 3]; + /// + /// let b = a.append(4); + /// + /// assert_eq!(b, arr![i32; 1, 2, 3, 4]); + /// # } + /// ``` + fn append(self, last: T) -> Self::Longer; + + /// Returns a new array with the given element prepended to the front of it. + /// + /// Example: + /// + /// ```rust + /// # use generic_array::{arr, sequence::Lengthen}; + /// # fn main() { + /// let a = arr![i32; 1, 2, 3]; + /// + /// let b = a.prepend(4); + /// + /// assert_eq!(b, arr![i32; 4, 1, 2, 3]); + /// # } + /// ``` + fn prepend(self, first: T) -> Self::Longer; +} + +/// Defines a `GenericSequence` which can be shortened by removing the first or last element from it. +/// +/// Additionally, any shortened sequence can be lengthened by +/// appending or prepending an element to it. +pub unsafe trait Shorten: Sized + GenericSequence { + /// `GenericSequence` that has one less element than `Self` + type Shorter: Lengthen; + + /// Returns a new array without the last element, and the last element. + /// + /// Example: + /// + /// ```rust + /// # use generic_array::{arr, sequence::Shorten}; + /// # fn main() { + /// let a = arr![i32; 1, 2, 3, 4]; + /// + /// let (init, last) = a.pop_back(); + /// + /// assert_eq!(init, arr![i32; 1, 2, 3]); + /// assert_eq!(last, 4); + /// # } + /// ``` + fn pop_back(self) -> (Self::Shorter, T); + + /// Returns a new array without the first element, and the first element. + /// Example: + /// + /// ```rust + /// # use generic_array::{arr, sequence::Shorten}; + /// # fn main() { + /// let a = arr![i32; 1, 2, 3, 4]; + /// + /// let (head, tail) = a.pop_front(); + /// + /// assert_eq!(head, 1); + /// assert_eq!(tail, arr![i32; 2, 3, 4]); + /// # } + /// ``` + fn pop_front(self) -> (T, Self::Shorter); +} + +unsafe impl> Lengthen for GenericArray +where + N: Add, + Add1: ArrayLength, + Add1: Sub, + Sub1>: ArrayLength, +{ + type Longer = GenericArray>; + + fn append(self, last: T) -> Self::Longer { + let mut longer: MaybeUninit = MaybeUninit::uninit(); + + // Note this is *mut Self, so add(1) increments by the whole array + let out_ptr = longer.as_mut_ptr() as *mut Self; + + unsafe { + // write self first + ptr::write(out_ptr, self); + // increment past self, then write the last + ptr::write(out_ptr.add(1) as *mut T, last); + + longer.assume_init() + } + } + + fn prepend(self, first: T) -> Self::Longer { + let mut longer: MaybeUninit = MaybeUninit::uninit(); + + // Note this is *mut T, so add(1) increments by a single T + let out_ptr = longer.as_mut_ptr() as *mut T; + + unsafe { + // write the first at the start + ptr::write(out_ptr, first); + // increment past the first, then write self + ptr::write(out_ptr.add(1) as *mut Self, self); + + longer.assume_init() + } + } +} + +unsafe impl> Shorten for GenericArray +where + N: Sub, + Sub1: ArrayLength, + Sub1: Add, + Add1>: ArrayLength, +{ + type Shorter = GenericArray>; + + fn pop_back(self) -> (Self::Shorter, T) { + let whole = ManuallyDrop::new(self); + + unsafe { + let init = ptr::read(whole.as_ptr() as _); + let last = ptr::read(whole.as_ptr().add(Sub1::::USIZE) as _); + + (init, last) + } + } + + fn pop_front(self) -> (T, Self::Shorter) { + // ensure this doesn't get dropped + let whole = ManuallyDrop::new(self); + + unsafe { + let head = ptr::read(whole.as_ptr() as _); + let tail = ptr::read(whole.as_ptr().offset(1) as _); + + (head, tail) + } + } +} + +/// Defines a `GenericSequence` that can be split into two parts at a given pivot index. +pub unsafe trait Split: GenericSequence +where + K: ArrayLength, +{ + /// First part of the resulting split array + type First: GenericSequence; + /// Second part of the resulting split array + type Second: GenericSequence; + + /// Splits an array at the given index, returning the separate parts of the array. + fn split(self) -> (Self::First, Self::Second); +} + +unsafe impl Split for GenericArray +where + N: ArrayLength, + K: ArrayLength, + N: Sub, + Diff: ArrayLength, +{ + type First = GenericArray; + type Second = GenericArray>; + + fn split(self) -> (Self::First, Self::Second) { + unsafe { + // ensure this doesn't get dropped + let whole = ManuallyDrop::new(self); + + let head = ptr::read(whole.as_ptr() as *const _); + let tail = ptr::read(whole.as_ptr().add(K::USIZE) as *const _); + + (head, tail) + } + } +} + +unsafe impl<'a, T, N, K> Split for &'a GenericArray +where + N: ArrayLength, + K: ArrayLength + 'static, + N: Sub, + Diff: ArrayLength, +{ + type First = &'a GenericArray; + type Second = &'a GenericArray>; + + fn split(self) -> (Self::First, Self::Second) { + unsafe { + let ptr_to_first: *const T = self.as_ptr(); + let head = &*(ptr_to_first as *const _); + let tail = &*(ptr_to_first.add(K::USIZE) as *const _); + (head, tail) + } + } +} + +unsafe impl<'a, T, N, K> Split for &'a mut GenericArray +where + N: ArrayLength, + K: ArrayLength + 'static, + N: Sub, + Diff: ArrayLength, +{ + type First = &'a mut GenericArray; + type Second = &'a mut GenericArray>; + + fn split(self) -> (Self::First, Self::Second) { + unsafe { + let ptr_to_first: *mut T = self.as_mut_ptr(); + let head = &mut *(ptr_to_first as *mut _); + let tail = &mut *(ptr_to_first.add(K::USIZE) as *mut _); + (head, tail) + } + } +} + +/// Defines `GenericSequence`s which can be joined together, forming a larger array. +pub unsafe trait Concat: GenericSequence +where + M: ArrayLength, +{ + /// Sequence to be concatenated with `self` + type Rest: GenericSequence; + + /// Resulting sequence formed by the concatenation. + type Output: GenericSequence; + + /// Concatenate, or join, two sequences. + fn concat(self, rest: Self::Rest) -> Self::Output; +} + +unsafe impl Concat for GenericArray +where + N: ArrayLength + Add, + M: ArrayLength, + Sum: ArrayLength, +{ + type Rest = GenericArray; + type Output = GenericArray>; + + fn concat(self, rest: Self::Rest) -> Self::Output { + let mut output: MaybeUninit = MaybeUninit::uninit(); + + let out_ptr = output.as_mut_ptr() as *mut Self; + + unsafe { + // write all of self to the pointer + ptr::write(out_ptr, self); + // increment past self, then write the rest + ptr::write(out_ptr.add(1) as *mut _, rest); + + output.assume_init() + } + } +} -- cgit v1.2.3