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 --- third_party/rust/fastrand/.cargo-checksum.json | 1 + third_party/rust/fastrand/CHANGELOG.md | 95 ++++ third_party/rust/fastrand/Cargo.toml | 67 +++ third_party/rust/fastrand/LICENSE-APACHE | 201 ++++++++ third_party/rust/fastrand/LICENSE-MIT | 23 + third_party/rust/fastrand/README.md | 105 ++++ third_party/rust/fastrand/benches/bench.rs | 98 ++++ third_party/rust/fastrand/src/global_rng.rs | 218 ++++++++ third_party/rust/fastrand/src/lib.rs | 679 +++++++++++++++++++++++++ third_party/rust/fastrand/tests/char.rs | 44 ++ third_party/rust/fastrand/tests/smoke.rs | 143 ++++++ 11 files changed, 1674 insertions(+) create mode 100644 third_party/rust/fastrand/.cargo-checksum.json create mode 100644 third_party/rust/fastrand/CHANGELOG.md create mode 100644 third_party/rust/fastrand/Cargo.toml create mode 100644 third_party/rust/fastrand/LICENSE-APACHE create mode 100644 third_party/rust/fastrand/LICENSE-MIT create mode 100644 third_party/rust/fastrand/README.md create mode 100644 third_party/rust/fastrand/benches/bench.rs create mode 100644 third_party/rust/fastrand/src/global_rng.rs create mode 100644 third_party/rust/fastrand/src/lib.rs create mode 100644 third_party/rust/fastrand/tests/char.rs create mode 100644 third_party/rust/fastrand/tests/smoke.rs (limited to 'third_party/rust/fastrand') diff --git a/third_party/rust/fastrand/.cargo-checksum.json b/third_party/rust/fastrand/.cargo-checksum.json new file mode 100644 index 0000000000..18aedbd357 --- /dev/null +++ b/third_party/rust/fastrand/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"a88b4ec120e965c0219c8d4a95e0868ed9396acb47d171ca864608eacda7efb8","Cargo.toml":"f0bc7071d293be9565d4a960fa914317f00f319901e9578e7a49a3a86959d90a","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"23f18e03dc49df91622fe2a76176497404e46ced8a715d9d2b67a7446571cca3","README.md":"ba09e4125cf5450a26d1bd2236bd079d668b118df639d9055e61eaa4d3c23336","benches/bench.rs":"95df618eeb6f3432e11295d75267c0ececcda35a6d230e9ca504e5d772fa2b62","src/global_rng.rs":"43a74ba2c3c15ebdbbacff65d6da5a90b4c062dedc43c6bf3fcf05499beaeece","src/lib.rs":"67568c53a27b34c5e2eb5e613a9656bcc9da1688a85070c4c36b60c216e3da8b","tests/char.rs":"a530b41837f5bf43701d983ef0267d9b44779d455f24cbf30b881cd348de9ee1","tests/smoke.rs":"8eac48144705364d142882538be43b8d69018959579404c3b1e638827888e62e"},"package":"6999dc1837253364c2ebb0704ba97994bd874e8f195d665c50b7548f6ea92764"} \ No newline at end of file diff --git a/third_party/rust/fastrand/CHANGELOG.md b/third_party/rust/fastrand/CHANGELOG.md new file mode 100644 index 0000000000..be0bf5c386 --- /dev/null +++ b/third_party/rust/fastrand/CHANGELOG.md @@ -0,0 +1,95 @@ +# Version 2.0.0 + +- **Breaking:** Remove interior mutability from `Rng`. (#47) +- Add a `fork()` method. (#49) +- Add a `no_std` mode. (#50) +- Add an iterator selection function. (#51) +- Add a `choose_multiple()` function for sampling several elements from an iterator. (#55) +- Use the `getrandom` crate for seeding on WebAssembly targets if the `js` feature is enabled. (#60) + +# Version 1.9.0 + +- Add `Rng::fill()` (#35, #43) +- Add `#[must_use]` to `Rng::with_seed()` (#46) + +# Version 1.8.0 + +- Add `get_seed()` and `Rng::get_seed()` (#33) + +# Version 1.7.0 + +- Add `char()` and `Rng::char()` (#25) + +# Version 1.6.0 + +- Implement `PartialEq` and `Eq` for `Rng` (#23) + +# Version 1.5.0 + +- Switch to Wyrand (#14) + +# Version 1.4.1 + +- Fix bug when generating a signed integer within a range (#16) + +# Version 1.4.0 + +- Add wasm support. + +# Version 1.3.5 + +- Reword docs. +- Add `Rng::with_seed()`. + +# Version 1.3.4 + +- Implement `Clone` for `Rng`. + +# Version 1.3.3 + +- Forbid unsafe code. + +# Version 1.3.2 + +- Support older Rust versions. + +# Version 1.3.1 + +- Tweak Cargo keywords. + +# Version 1.3.0 + +- Add `f32()` and `f64()`. +- Add `lowercase()`, `uppercase()`, `alphabetic()`, and `digit()`. + +# Version 1.2.4 + +- Switch to PCG XSH RR 64/32. +- Fix a bug in `gen_mod_u128`. +- Fix bias in ranges. + +# Version 1.2.3 + +- Support Rust 1.32.0 + +# Version 1.2.2 + +- Use `std::$t::MAX` rather than `$t::MAX` to support older Rust versions. + +# Version 1.2.1 + +- Inline all functions. + +# Version 1.2.0 + +- Add `Rng` struct. + +# Version 1.1.0 + +- Switch to PCG implementation. +- Add `alphanumeric()`. +- Add `seed()`. + +# Version 1.0.0 + +- Initial version diff --git a/third_party/rust/fastrand/Cargo.toml b/third_party/rust/fastrand/Cargo.toml new file mode 100644 index 0000000000..43f68ea353 --- /dev/null +++ b/third_party/rust/fastrand/Cargo.toml @@ -0,0 +1,67 @@ +# 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] +edition = "2018" +rust-version = "1.36" +name = "fastrand" +version = "2.0.0" +authors = ["Stjepan Glavina "] +exclude = ["/.*"] +description = "A simple and fast random number generator" +readme = "README.md" +keywords = [ + "simple", + "fast", + "rand", + "random", + "wyrand", +] +categories = ["algorithms"] +license = "Apache-2.0 OR MIT" +repository = "https://github.com/smol-rs/fastrand" + +[package.metadata.docs.rs] +all-features = true +rustdoc-args = [ + "--cfg", + "docsrs", +] + +[dev-dependencies.getrandom] +version = "0.2" + +[dev-dependencies.rand] +version = "0.8" + +[dev-dependencies.wyhash] +version = "0.5" + +[features] +alloc = [] +default = ["std"] +js = [ + "std", + "getrandom", +] +std = ["alloc"] + +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dependencies.getrandom] +version = "0.2" +features = ["js"] +optional = true + +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dev-dependencies.getrandom] +version = "0.2" +features = ["js"] + +[target."cfg(all(any(target_arch = \"wasm32\", target_arch = \"wasm64\"), target_os = \"unknown\"))".dev-dependencies.wasm-bindgen-test] +version = "0.3" diff --git a/third_party/rust/fastrand/LICENSE-APACHE b/third_party/rust/fastrand/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/fastrand/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/fastrand/LICENSE-MIT b/third_party/rust/fastrand/LICENSE-MIT new file mode 100644 index 0000000000..31aa79387f --- /dev/null +++ b/third_party/rust/fastrand/LICENSE-MIT @@ -0,0 +1,23 @@ +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. diff --git a/third_party/rust/fastrand/README.md b/third_party/rust/fastrand/README.md new file mode 100644 index 0000000000..70da00bc6d --- /dev/null +++ b/third_party/rust/fastrand/README.md @@ -0,0 +1,105 @@ +# fastrand + +[![Build](https://github.com/smol-rs/fastrand/workflows/Build%20and%20test/badge.svg)]( +https://github.com/smol-rs/fastrand/actions) +[![License](https://img.shields.io/badge/license-Apache--2.0_OR_MIT-blue.svg)]( +https://github.com/smol-rs/fastrand) +[![Cargo](https://img.shields.io/crates/v/fastrand.svg)]( +https://crates.io/crates/fastrand) +[![Documentation](https://docs.rs/fastrand/badge.svg)]( +https://docs.rs/fastrand) + +A simple and fast random number generator. + +The implementation uses [Wyrand](https://github.com/wangyi-fudan/wyhash), a simple and fast +generator but **not** cryptographically secure. + +## Examples + +Flip a coin: + +```rust +if fastrand::bool() { + println!("heads"); +} else { + println!("tails"); +} +``` + +Generate a random `i32`: + +```rust +let num = fastrand::i32(..); +``` + +Choose a random element in an array: + +```rust +let v = vec![1, 2, 3, 4, 5]; +let i = fastrand::usize(..v.len()); +let elem = v[i]; +``` + +Sample values from an array with `O(n)` complexity (`n` is the length of array): + +```rust +fastrand::choose_multiple(vec![1, 4, 5].iter(), 2); +fastrand::choose_multiple(0..20, 12); +``` + +Shuffle an array: + +```rust +let mut v = vec![1, 2, 3, 4, 5]; +fastrand::shuffle(&mut v); +``` + +Generate a random `Vec` or `String`: + +```rust +use std::iter::repeat_with; + +let v: Vec = repeat_with(|| fastrand::i32(..)).take(10).collect(); +let s: String = repeat_with(fastrand::alphanumeric).take(10).collect(); +``` + +To get reproducible results on every run, initialize the generator with a seed: + +```rust +// Pick an arbitrary number as seed. +fastrand::seed(7); + +// Now this prints the same number on every run: +println!("{}", fastrand::u32(..)); +``` + +To be more efficient, create a new `Rng` instance instead of using the thread-local +generator: + +```rust +use std::iter::repeat_with; + +let rng = fastrand::Rng::new(); +let mut bytes: Vec = repeat_with(|| rng.u8(..)).take(10_000).collect(); +``` + +# Features + +- `std` (enabled by default): Enables the `std` library. This is required for the global + generator and global entropy. Without this feature, [`Rng`] can only be instantiated using + the [`with_seed`](Rng::with_seed) method. + +## License + +Licensed under either of + + * Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0) + * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) + +at your option. + +#### Contribution + +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in the work by you, as defined in the Apache-2.0 license, shall be +dual licensed as above, without any additional terms or conditions. diff --git a/third_party/rust/fastrand/benches/bench.rs b/third_party/rust/fastrand/benches/bench.rs new file mode 100644 index 0000000000..a940aac480 --- /dev/null +++ b/third_party/rust/fastrand/benches/bench.rs @@ -0,0 +1,98 @@ +#![feature(test)] + +extern crate test; + +use rand::prelude::*; +use test::Bencher; +use wyhash::WyRng; + +#[bench] +fn shuffle_wyhash(b: &mut Bencher) { + let mut rng = WyRng::from_rng(thread_rng()).unwrap(); + let mut x = (0..100).collect::>(); + b.iter(|| { + x.shuffle(&mut rng); + x[0] + }) +} + +#[bench] +fn shuffle_fastrand(b: &mut Bencher) { + let mut rng = fastrand::Rng::new(); + let mut x = (0..100).collect::>(); + b.iter(|| { + rng.shuffle(&mut x); + x[0] + }) +} + +#[bench] +fn u8_wyhash(b: &mut Bencher) { + let mut rng = WyRng::from_rng(thread_rng()).unwrap(); + b.iter(|| { + let mut sum = 0u8; + for _ in 0..10_000 { + sum = sum.wrapping_add(rng.gen::()); + } + sum + }) +} + +#[bench] +fn u8_fastrand(b: &mut Bencher) { + let mut rng = fastrand::Rng::new(); + b.iter(|| { + let mut sum = 0u8; + for _ in 0..10_000 { + sum = sum.wrapping_add(rng.u8(..)); + } + sum + }) +} + +#[bench] +fn u32_wyhash(b: &mut Bencher) { + let mut rng = WyRng::from_rng(thread_rng()).unwrap(); + b.iter(|| { + let mut sum = 0u32; + for _ in 0..10_000 { + sum = sum.wrapping_add(rng.gen::()); + } + sum + }) +} + +#[bench] +fn u32_fastrand(b: &mut Bencher) { + let mut rng = fastrand::Rng::new(); + b.iter(|| { + let mut sum = 0u32; + for _ in 0..10_000 { + sum = sum.wrapping_add(rng.u32(..)); + } + sum + }) +} + +#[bench] +fn fill(b: &mut Bencher) { + let mut rng = fastrand::Rng::new(); + b.iter(|| { + // Pick a size that isn't divisble by 8. + let mut bytes = [0u8; 367]; + rng.fill(&mut bytes); + bytes + }) +} + +#[bench] +fn fill_naive(b: &mut Bencher) { + let mut rng = fastrand::Rng::new(); + b.iter(|| { + let mut bytes = [0u8; 367]; + for item in &mut bytes { + *item = rng.u8(..); + } + bytes + }) +} diff --git a/third_party/rust/fastrand/src/global_rng.rs b/third_party/rust/fastrand/src/global_rng.rs new file mode 100644 index 0000000000..f994902ec3 --- /dev/null +++ b/third_party/rust/fastrand/src/global_rng.rs @@ -0,0 +1,218 @@ +//! A global, thread-local random number generator. + +use crate::Rng; + +use std::cell::Cell; +use std::ops::RangeBounds; + +// Chosen by fair roll of the dice. +const DEFAULT_RNG_SEED: u64 = 0xef6f79ed30ba75a; + +impl Default for Rng { + /// Initialize the `Rng` from the system's random number generator. + /// + /// This is equivalent to [`Rng::new()`]. + #[inline] + fn default() -> Rng { + Rng::new() + } +} + +impl Rng { + /// Creates a new random number generator. + #[inline] + pub fn new() -> Rng { + try_with_rng(Rng::fork).unwrap_or_else(|_| Rng::with_seed(0x4d595df4d0f33173)) + } +} + +thread_local! { + static RNG: Cell = Cell::new(Rng(random_seed().unwrap_or(DEFAULT_RNG_SEED))); +} + +/// Run an operation with the current thread-local generator. +#[inline] +fn with_rng(f: impl FnOnce(&mut Rng) -> R) -> R { + RNG.with(|rng| { + let current = rng.replace(Rng(0)); + + let mut restore = RestoreOnDrop { rng, current }; + + f(&mut restore.current) + }) +} + +/// Try to run an operation with the current thread-local generator. +#[inline] +fn try_with_rng(f: impl FnOnce(&mut Rng) -> R) -> Result { + RNG.try_with(|rng| { + let current = rng.replace(Rng(0)); + + let mut restore = RestoreOnDrop { rng, current }; + + f(&mut restore.current) + }) +} + +/// Make sure the original RNG is restored even on panic. +struct RestoreOnDrop<'a> { + rng: &'a Cell, + current: Rng, +} + +impl Drop for RestoreOnDrop<'_> { + fn drop(&mut self) { + self.rng.set(Rng(self.current.0)); + } +} + +/// Initializes the thread-local generator with the given seed. +#[inline] +pub fn seed(seed: u64) { + with_rng(|r| r.seed(seed)); +} + +/// Gives back **current** seed that is being held by the thread-local generator. +#[inline] +pub fn get_seed() -> u64 { + with_rng(|r| r.get_seed()) +} + +/// Generates a random `bool`. +#[inline] +pub fn bool() -> bool { + with_rng(|r| r.bool()) +} + +/// Generates a random `char` in ranges a-z and A-Z. +#[inline] +pub fn alphabetic() -> char { + with_rng(|r| r.alphabetic()) +} + +/// Generates a random `char` in ranges a-z, A-Z and 0-9. +#[inline] +pub fn alphanumeric() -> char { + with_rng(|r| r.alphanumeric()) +} + +/// Generates a random `char` in range a-z. +#[inline] +pub fn lowercase() -> char { + with_rng(|r| r.lowercase()) +} + +/// Generates a random `char` in range A-Z. +#[inline] +pub fn uppercase() -> char { + with_rng(|r| r.uppercase()) +} + +/// Choose an item from an iterator at random. +/// +/// This function may have an unexpected result if the `len()` property of the +/// iterator does not match the actual number of items in the iterator. If +/// the iterator is empty, this returns `None`. +#[inline] +pub fn choice(iter: I) -> Option +where + I: IntoIterator, + I::IntoIter: ExactSizeIterator, +{ + with_rng(|r| r.choice(iter)) +} + +/// Generates a random digit in the given `base`. +/// +/// Digits are represented by `char`s in ranges 0-9 and a-z. +/// +/// Panics if the base is zero or greater than 36. +#[inline] +pub fn digit(base: u32) -> char { + with_rng(|r| r.digit(base)) +} + +/// Shuffles a slice randomly. +#[inline] +pub fn shuffle(slice: &mut [T]) { + with_rng(|r| r.shuffle(slice)) +} + +macro_rules! integer { + ($t:tt, $doc:tt) => { + #[doc = $doc] + /// + /// Panics if the range is empty. + #[inline] + pub fn $t(range: impl RangeBounds<$t>) -> $t { + with_rng(|r| r.$t(range)) + } + }; +} + +integer!(u8, "Generates a random `u8` in the given range."); +integer!(i8, "Generates a random `i8` in the given range."); +integer!(u16, "Generates a random `u16` in the given range."); +integer!(i16, "Generates a random `i16` in the given range."); +integer!(u32, "Generates a random `u32` in the given range."); +integer!(i32, "Generates a random `i32` in the given range."); +integer!(u64, "Generates a random `u64` in the given range."); +integer!(i64, "Generates a random `i64` in the given range."); +integer!(u128, "Generates a random `u128` in the given range."); +integer!(i128, "Generates a random `i128` in the given range."); +integer!(usize, "Generates a random `usize` in the given range."); +integer!(isize, "Generates a random `isize` in the given range."); +integer!(char, "Generates a random `char` in the given range."); + +/// Generates a random `f32` in range `0..1`. +pub fn f32() -> f32 { + with_rng(|r| r.f32()) +} + +/// Generates a random `f64` in range `0..1`. +pub fn f64() -> f64 { + with_rng(|r| r.f64()) +} + +/// Collects `amount` values at random from the iterator into a vector. +pub fn choose_multiple(source: T, amount: usize) -> Vec { + with_rng(|rng| rng.choose_multiple(source, amount)) +} + +#[cfg(not(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown" +)))] +fn random_seed() -> Option { + use std::collections::hash_map::DefaultHasher; + use std::hash::{Hash, Hasher}; + use std::thread; + use std::time::Instant; + + let mut hasher = DefaultHasher::new(); + Instant::now().hash(&mut hasher); + thread::current().id().hash(&mut hasher); + let hash = hasher.finish(); + Some((hash << 1) | 1) +} + +#[cfg(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown", + feature = "js" +))] +fn random_seed() -> Option { + // TODO(notgull): Failures should be logged somewhere. + let mut seed = [0u8; 8]; + getrandom::getrandom(&mut seed).ok()?; + Some(u64::from_ne_bytes(seed)) +} + +#[cfg(all( + any(target_arch = "wasm32", target_arch = "wasm64"), + target_os = "unknown", + not(feature = "js") +))] +fn random_seed() -> Option { + None +} diff --git a/third_party/rust/fastrand/src/lib.rs b/third_party/rust/fastrand/src/lib.rs new file mode 100644 index 0000000000..415aae9861 --- /dev/null +++ b/third_party/rust/fastrand/src/lib.rs @@ -0,0 +1,679 @@ +//! A simple and fast random number generator. +//! +//! The implementation uses [Wyrand](https://github.com/wangyi-fudan/wyhash), a simple and fast +//! generator but **not** cryptographically secure. +//! +//! # Examples +//! +//! Flip a coin: +//! +//! ``` +//! if fastrand::bool() { +//! println!("heads"); +//! } else { +//! println!("tails"); +//! } +//! ``` +//! +//! Generate a random `i32`: +//! +//! ``` +//! let num = fastrand::i32(..); +//! ``` +//! +//! Choose a random element in an array: +//! +//! ``` +//! let v = vec![1, 2, 3, 4, 5]; +//! let i = fastrand::usize(..v.len()); +//! let elem = v[i]; +//! ``` +//! +//! Sample values from an array with `O(n)` complexity (`n` is the length of array): +//! +//! ``` +//! fastrand::choose_multiple(vec![1, 4, 5].iter(), 2); +//! fastrand::choose_multiple(0..20, 12); +//! ``` +//! +//! +//! Shuffle an array: +//! +//! ``` +//! let mut v = vec![1, 2, 3, 4, 5]; +//! fastrand::shuffle(&mut v); +//! ``` +//! +//! Generate a random [`Vec`] or [`String`]: +//! +//! ``` +//! use std::iter::repeat_with; +//! +//! let v: Vec = repeat_with(|| fastrand::i32(..)).take(10).collect(); +//! let s: String = repeat_with(fastrand::alphanumeric).take(10).collect(); +//! ``` +//! +//! To get reproducible results on every run, initialize the generator with a seed: +//! +//! ``` +//! // Pick an arbitrary number as seed. +//! fastrand::seed(7); +//! +//! // Now this prints the same number on every run: +//! println!("{}", fastrand::u32(..)); +//! ``` +//! +//! To be more efficient, create a new [`Rng`] instance instead of using the thread-local +//! generator: +//! +//! ``` +//! use std::iter::repeat_with; +//! +//! let mut rng = fastrand::Rng::new(); +//! let mut bytes: Vec = repeat_with(|| rng.u8(..)).take(10_000).collect(); +//! ``` +//! +//! # Features +//! +//! - `std` (enabled by default): Enables the `std` library. This is required for the global +//! generator and global entropy. Without this feature, [`Rng`] can only be instantiated using +//! the [`with_seed`](Rng::with_seed) method. +//! - `js`: Assumes that WebAssembly targets are being run in a JavaScript environment. See the +//! [WebAssembly Notes](#webassembly-notes) section for more information. +//! +//! # WebAssembly Notes +//! +//! For non-WASI WASM targets, there is additional sublety to consider when utilizing the global RNG. +//! By default, `std` targets will use entropy sources in the standard library to seed the global RNG. +//! However, these sources are not available by default on WASM targets outside of WASI. +//! +//! If the `js` feature is enabled, this crate will assume that it is running in a JavaScript +//! environment. At this point, the [`getrandom`] crate will be used in order to access the available +//! entropy sources and seed the global RNG. If the `js` feature is not enabled, the global RNG will +//! use a predefined seed. +//! +//! [`getrandom`]: https://crates.io/crates/getrandom + +#![cfg_attr(not(feature = "std"), no_std)] +#![cfg_attr(docsrs, feature(doc_cfg))] +#![forbid(unsafe_code)] +#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)] + +#[cfg(feature = "alloc")] +extern crate alloc; + +use core::convert::{TryFrom, TryInto}; +use core::ops::{Bound, RangeBounds}; + +#[cfg(feature = "alloc")] +use alloc::vec::Vec; + +#[cfg(feature = "std")] +#[cfg_attr(docsrs, doc(cfg(feature = "std")))] +mod global_rng; + +#[cfg(feature = "std")] +pub use global_rng::*; + +/// A random number generator. +#[derive(Debug, PartialEq, Eq)] +pub struct Rng(u64); + +impl Clone for Rng { + /// Clones the generator by creating a new generator with the same seed. + fn clone(&self) -> Rng { + Rng::with_seed(self.0) + } +} + +impl Rng { + /// Generates a random `u32`. + #[inline] + fn gen_u32(&mut self) -> u32 { + self.gen_u64() as u32 + } + + /// Generates a random `u64`. + #[inline] + fn gen_u64(&mut self) -> u64 { + let s = self.0.wrapping_add(0xA0761D6478BD642F); + self.0 = s; + let t = u128::from(s) * u128::from(s ^ 0xE7037ED1A0B428DB); + (t as u64) ^ (t >> 64) as u64 + } + + /// Generates a random `u128`. + #[inline] + fn gen_u128(&mut self) -> u128 { + (u128::from(self.gen_u64()) << 64) | u128::from(self.gen_u64()) + } + + /// Generates a random `u32` in `0..n`. + #[inline] + fn gen_mod_u32(&mut self, n: u32) -> u32 { + // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ + let mut r = self.gen_u32(); + let mut hi = mul_high_u32(r, n); + let mut lo = r.wrapping_mul(n); + if lo < n { + let t = n.wrapping_neg() % n; + while lo < t { + r = self.gen_u32(); + hi = mul_high_u32(r, n); + lo = r.wrapping_mul(n); + } + } + hi + } + + /// Generates a random `u64` in `0..n`. + #[inline] + fn gen_mod_u64(&mut self, n: u64) -> u64 { + // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ + let mut r = self.gen_u64(); + let mut hi = mul_high_u64(r, n); + let mut lo = r.wrapping_mul(n); + if lo < n { + let t = n.wrapping_neg() % n; + while lo < t { + r = self.gen_u64(); + hi = mul_high_u64(r, n); + lo = r.wrapping_mul(n); + } + } + hi + } + + /// Generates a random `u128` in `0..n`. + #[inline] + fn gen_mod_u128(&mut self, n: u128) -> u128 { + // Adapted from: https://lemire.me/blog/2016/06/30/fast-random-shuffling/ + let mut r = self.gen_u128(); + let mut hi = mul_high_u128(r, n); + let mut lo = r.wrapping_mul(n); + if lo < n { + let t = n.wrapping_neg() % n; + while lo < t { + r = self.gen_u128(); + hi = mul_high_u128(r, n); + lo = r.wrapping_mul(n); + } + } + hi + } +} + +/// Computes `(a * b) >> 32`. +#[inline] +fn mul_high_u32(a: u32, b: u32) -> u32 { + (((a as u64) * (b as u64)) >> 32) as u32 +} + +/// Computes `(a * b) >> 64`. +#[inline] +fn mul_high_u64(a: u64, b: u64) -> u64 { + (((a as u128) * (b as u128)) >> 64) as u64 +} + +/// Computes `(a * b) >> 128`. +#[inline] +fn mul_high_u128(a: u128, b: u128) -> u128 { + // Adapted from: https://stackoverflow.com/a/28904636 + let a_lo = a as u64 as u128; + let a_hi = (a >> 64) as u64 as u128; + let b_lo = b as u64 as u128; + let b_hi = (b >> 64) as u64 as u128; + let carry = (a_lo * b_lo) >> 64; + let carry = ((a_hi * b_lo) as u64 as u128 + (a_lo * b_hi) as u64 as u128 + carry) >> 64; + a_hi * b_hi + ((a_hi * b_lo) >> 64) + ((a_lo * b_hi) >> 64) + carry +} + +macro_rules! rng_integer { + ($t:tt, $unsigned_t:tt, $gen:tt, $mod:tt, $doc:tt) => { + #[doc = $doc] + /// + /// Panics if the range is empty. + #[inline] + pub fn $t(&mut self, range: impl RangeBounds<$t>) -> $t { + let panic_empty_range = || { + panic!( + "empty range: {:?}..{:?}", + range.start_bound(), + range.end_bound() + ) + }; + + let low = match range.start_bound() { + Bound::Unbounded => core::$t::MIN, + Bound::Included(&x) => x, + Bound::Excluded(&x) => x.checked_add(1).unwrap_or_else(panic_empty_range), + }; + + let high = match range.end_bound() { + Bound::Unbounded => core::$t::MAX, + Bound::Included(&x) => x, + Bound::Excluded(&x) => x.checked_sub(1).unwrap_or_else(panic_empty_range), + }; + + if low > high { + panic_empty_range(); + } + + if low == core::$t::MIN && high == core::$t::MAX { + self.$gen() as $t + } else { + let len = high.wrapping_sub(low).wrapping_add(1); + low.wrapping_add(self.$mod(len as $unsigned_t as _) as $t) + } + } + }; +} + +impl Rng { + /// Creates a new random number generator with the initial seed. + #[inline] + #[must_use = "this creates a new instance of `Rng`; if you want to initialize the thread-local generator, use `fastrand::seed()` instead"] + pub fn with_seed(seed: u64) -> Self { + let mut rng = Rng(0); + + rng.seed(seed); + rng + } + + /// Clones the generator by deterministically deriving a new generator based on the initial + /// seed. + /// + /// # Example + /// + /// ``` + /// // Seed two generators equally, and clone both of them. + /// let mut base1 = fastrand::Rng::new(); + /// base1.seed(0x4d595df4d0f33173); + /// base1.bool(); // Use the generator once. + /// + /// let mut base2 = fastrand::Rng::new(); + /// base2.seed(0x4d595df4d0f33173); + /// base2.bool(); // Use the generator once. + /// + /// let mut rng1 = base1.clone(); + /// let mut rng2 = base2.clone(); + /// + /// assert_eq!(rng1.u64(..), rng2.u64(..), "the cloned generators are identical"); + /// ``` + #[inline] + #[must_use = "this creates a new instance of `Rng`"] + pub fn fork(&mut self) -> Self { + Rng::with_seed(self.gen_u64()) + } + + /// Generates a random `char` in ranges a-z and A-Z. + #[inline] + pub fn alphabetic(&mut self) -> char { + const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + *self.choice(CHARS).unwrap() as char + } + + /// Generates a random `char` in ranges a-z, A-Z and 0-9. + #[inline] + pub fn alphanumeric(&mut self) -> char { + const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; + *self.choice(CHARS).unwrap() as char + } + + /// Generates a random `bool`. + #[inline] + pub fn bool(&mut self) -> bool { + self.u8(..) % 2 == 0 + } + + /// Generates a random digit in the given `base`. + /// + /// Digits are represented by `char`s in ranges 0-9 and a-z. + /// + /// Panics if the base is zero or greater than 36. + #[inline] + pub fn digit(&mut self, base: u32) -> char { + if base == 0 { + panic!("base cannot be zero"); + } + if base > 36 { + panic!("base cannot be larger than 36"); + } + let num = self.u8(..base as u8); + if num < 10 { + (b'0' + num) as char + } else { + (b'a' + num - 10) as char + } + } + + /// Generates a random `f32` in range `0..1`. + pub fn f32(&mut self) -> f32 { + let b = 32; + let f = core::f32::MANTISSA_DIGITS - 1; + f32::from_bits((1 << (b - 2)) - (1 << f) + (self.u32(..) >> (b - f))) - 1.0 + } + + /// Generates a random `f64` in range `0..1`. + pub fn f64(&mut self) -> f64 { + let b = 64; + let f = core::f64::MANTISSA_DIGITS - 1; + f64::from_bits((1 << (b - 2)) - (1 << f) + (self.u64(..) >> (b - f))) - 1.0 + } + + /// Collects `amount` values at random from the iterator into a vector. + /// + /// The length of the returned vector equals `amount` unless the iterator + /// contains insufficient elements, in which case it equals the number of + /// elements available. + /// + /// Complexity is `O(n)` where `n` is the length of the iterator. + #[cfg(feature = "alloc")] + #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))] + pub fn choose_multiple(&mut self, mut source: T, amount: usize) -> Vec { + // Adapted from: https://docs.rs/rand/latest/rand/seq/trait.IteratorRandom.html#method.choose_multiple + let mut reservoir = Vec::with_capacity(amount); + + reservoir.extend(source.by_ref().take(amount)); + + // Continue unless the iterator was exhausted + // + // note: this prevents iterators that "restart" from causing problems. + // If the iterator stops once, then so do we. + if reservoir.len() == amount { + for (i, elem) in source.enumerate() { + let end = i + 1 + amount; + let k = self.usize(0..end); + if let Some(slot) = reservoir.get_mut(k) { + *slot = elem; + } + } + } else { + // If less than one third of the `Vec` was used, reallocate + // so that the unused space is not wasted. There is a corner + // case where `amount` was much less than `self.len()`. + if reservoir.capacity() > 3 * reservoir.len() { + reservoir.shrink_to_fit(); + } + } + reservoir + } + + rng_integer!( + i8, + u8, + gen_u32, + gen_mod_u32, + "Generates a random `i8` in the given range." + ); + + rng_integer!( + i16, + u16, + gen_u32, + gen_mod_u32, + "Generates a random `i16` in the given range." + ); + + rng_integer!( + i32, + u32, + gen_u32, + gen_mod_u32, + "Generates a random `i32` in the given range." + ); + + rng_integer!( + i64, + u64, + gen_u64, + gen_mod_u64, + "Generates a random `i64` in the given range." + ); + + rng_integer!( + i128, + u128, + gen_u128, + gen_mod_u128, + "Generates a random `i128` in the given range." + ); + + #[cfg(target_pointer_width = "16")] + rng_integer!( + isize, + usize, + gen_u32, + gen_mod_u32, + "Generates a random `isize` in the given range." + ); + #[cfg(target_pointer_width = "32")] + rng_integer!( + isize, + usize, + gen_u32, + gen_mod_u32, + "Generates a random `isize` in the given range." + ); + #[cfg(target_pointer_width = "64")] + rng_integer!( + isize, + usize, + gen_u64, + gen_mod_u64, + "Generates a random `isize` in the given range." + ); + + /// Generates a random `char` in range a-z. + #[inline] + pub fn lowercase(&mut self) -> char { + const CHARS: &[u8] = b"abcdefghijklmnopqrstuvwxyz"; + *self.choice(CHARS).unwrap() as char + } + + /// Initializes this generator with the given seed. + #[inline] + pub fn seed(&mut self, seed: u64) { + self.0 = seed; + } + + /// Gives back **current** seed that is being held by this generator. + #[inline] + pub fn get_seed(&self) -> u64 { + self.0 + } + + /// Choose an item from an iterator at random. + /// + /// This function may have an unexpected result if the `len()` property of the + /// iterator does not match the actual number of items in the iterator. If + /// the iterator is empty, this returns `None`. + #[inline] + pub fn choice(&mut self, iter: I) -> Option + where + I: IntoIterator, + I::IntoIter: ExactSizeIterator, + { + let mut iter = iter.into_iter(); + + // Get the item at a random index. + let len = iter.len(); + if len == 0 { + return None; + } + let index = self.usize(0..len); + + iter.nth(index) + } + + /// Shuffles a slice randomly. + #[inline] + pub fn shuffle(&mut self, slice: &mut [T]) { + for i in 1..slice.len() { + slice.swap(i, self.usize(..=i)); + } + } + + /// Fill a byte slice with random data. + #[inline] + pub fn fill(&mut self, slice: &mut [u8]) { + // We fill the slice by chunks of 8 bytes, or one block of + // WyRand output per new state. + let mut chunks = slice.chunks_exact_mut(core::mem::size_of::()); + for chunk in chunks.by_ref() { + let n = self.gen_u64().to_ne_bytes(); + // Safe because the chunks are always 8 bytes exactly. + chunk.copy_from_slice(&n); + } + + let remainder = chunks.into_remainder(); + + // Any remainder will always be less than 8 bytes. + if !remainder.is_empty() { + // Generate one last block of 8 bytes of entropy + let n = self.gen_u64().to_ne_bytes(); + + // Use the remaining length to copy from block + remainder.copy_from_slice(&n[..remainder.len()]); + } + } + + rng_integer!( + u8, + u8, + gen_u32, + gen_mod_u32, + "Generates a random `u8` in the given range." + ); + + rng_integer!( + u16, + u16, + gen_u32, + gen_mod_u32, + "Generates a random `u16` in the given range." + ); + + rng_integer!( + u32, + u32, + gen_u32, + gen_mod_u32, + "Generates a random `u32` in the given range." + ); + + rng_integer!( + u64, + u64, + gen_u64, + gen_mod_u64, + "Generates a random `u64` in the given range." + ); + + rng_integer!( + u128, + u128, + gen_u128, + gen_mod_u128, + "Generates a random `u128` in the given range." + ); + + #[cfg(target_pointer_width = "16")] + rng_integer!( + usize, + usize, + gen_u32, + gen_mod_u32, + "Generates a random `usize` in the given range." + ); + #[cfg(target_pointer_width = "32")] + rng_integer!( + usize, + usize, + gen_u32, + gen_mod_u32, + "Generates a random `usize` in the given range." + ); + #[cfg(target_pointer_width = "64")] + rng_integer!( + usize, + usize, + gen_u64, + gen_mod_u64, + "Generates a random `usize` in the given range." + ); + #[cfg(target_pointer_width = "128")] + rng_integer!( + usize, + usize, + gen_u128, + gen_mod_u128, + "Generates a random `usize` in the given range." + ); + + /// Generates a random `char` in range A-Z. + #[inline] + pub fn uppercase(&mut self) -> char { + const CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + *self.choice(CHARS).unwrap() as char + } + + /// Generates a random `char` in the given range. + /// + /// Panics if the range is empty. + #[inline] + pub fn char(&mut self, range: impl RangeBounds) -> char { + let panic_empty_range = || { + panic!( + "empty range: {:?}..{:?}", + range.start_bound(), + range.end_bound() + ) + }; + + let surrogate_start = 0xd800u32; + let surrogate_len = 0x800u32; + + let low = match range.start_bound() { + Bound::Unbounded => 0u8 as char, + Bound::Included(&x) => x, + Bound::Excluded(&x) => { + let scalar = if x as u32 == surrogate_start - 1 { + surrogate_start + surrogate_len + } else { + x as u32 + 1 + }; + char::try_from(scalar).unwrap_or_else(|_| panic_empty_range()) + } + }; + + let high = match range.end_bound() { + Bound::Unbounded => core::char::MAX, + Bound::Included(&x) => x, + Bound::Excluded(&x) => { + let scalar = if x as u32 == surrogate_start + surrogate_len { + surrogate_start - 1 + } else { + (x as u32).wrapping_sub(1) + }; + char::try_from(scalar).unwrap_or_else(|_| panic_empty_range()) + } + }; + + if low > high { + panic_empty_range(); + } + + let gap = if (low as u32) < surrogate_start && (high as u32) >= surrogate_start { + surrogate_len + } else { + 0 + }; + let range = high as u32 - low as u32 - gap; + let mut val = self.u32(0..=range) + low as u32; + if val >= surrogate_start { + val += gap; + } + val.try_into().unwrap() + } +} diff --git a/third_party/rust/fastrand/tests/char.rs b/third_party/rust/fastrand/tests/char.rs new file mode 100644 index 0000000000..0f48c57708 --- /dev/null +++ b/third_party/rust/fastrand/tests/char.rs @@ -0,0 +1,44 @@ +use std::convert::TryFrom; +use std::ops::RangeBounds; + +fn test_char_coverage(n: usize, range: R) +where + R: Iterator + RangeBounds + Clone, +{ + use std::collections::HashSet; + + let all: HashSet = range.clone().collect(); + let mut covered = HashSet::new(); + for _ in 0..n { + let c = fastrand::char(range.clone()); + assert!(all.contains(&c)); + covered.insert(c); + } + assert_eq!(covered, all); +} + +#[test] +fn test_char() { + // ASCII control chars. + let nul = 0u8 as char; + let soh = 1u8 as char; + let stx = 2u8 as char; + // Some undefined Hangul Jamo codepoints just before + // the surrogate area. + let last_jamo = char::try_from(0xd7ffu32).unwrap(); + let penultimate_jamo = char::try_from(last_jamo as u32 - 1).unwrap(); + // Private-use codepoints just after the surrogate area. + let first_private = char::try_from(0xe000u32).unwrap(); + let second_private = char::try_from(first_private as u32 + 1).unwrap(); + // Private-use codepoints at the end of Unicode space. + let last_private = std::char::MAX; + let penultimate_private = char::try_from(last_private as u32 - 1).unwrap(); + + test_char_coverage(100, nul..stx); + test_char_coverage(100, nul..=soh); + + test_char_coverage(400, penultimate_jamo..second_private); + test_char_coverage(400, penultimate_jamo..=second_private); + + test_char_coverage(100, penultimate_private..=last_private); +} diff --git a/third_party/rust/fastrand/tests/smoke.rs b/third_party/rust/fastrand/tests/smoke.rs new file mode 100644 index 0000000000..7c92ee52ef --- /dev/null +++ b/third_party/rust/fastrand/tests/smoke.rs @@ -0,0 +1,143 @@ +#[cfg(all(target_family = "wasm", not(target_os = "wasi")))] +use wasm_bindgen_test::wasm_bindgen_test as test; + +#[cfg(all(target_family = "wasm", not(target_os = "wasi")))] +wasm_bindgen_test::wasm_bindgen_test_configure!(run_in_browser); + +#[test] +fn bool() { + for x in &[false, true] { + while fastrand::bool() != *x {} + } +} + +#[test] +fn u8() { + for x in 0..10 { + while fastrand::u8(..10) != x {} + } + + for x in 200..=u8::MAX { + while fastrand::u8(200..) != x {} + } +} + +#[test] +fn i8() { + for x in -128..-120 { + while fastrand::i8(..-120) != x {} + } + + for x in 120..=127 { + while fastrand::i8(120..) != x {} + } +} + +#[test] +fn u32() { + for n in 1u32..10_000 { + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + if n != 0 { + for _ in 0..1000 { + assert!(fastrand::u32(..n) < n); + } + } + } +} + +#[test] +fn u64() { + for n in 1u64..10_000 { + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + if n != 0 { + for _ in 0..1000 { + assert!(fastrand::u64(..n) < n); + } + } + } +} + +#[test] +fn u128() { + for n in 1u128..10_000 { + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + let n = n.wrapping_mul(n); + if n != 0 { + for _ in 0..1000 { + assert!(fastrand::u128(..n) < n); + } + } + } +} + +#[test] +fn fill() { + let mut r = fastrand::Rng::new(); + let mut a = [0u8; 64]; + let mut b = [0u8; 64]; + + r.fill(&mut a); + r.fill(&mut b); + + assert_ne!(a, b); +} + +#[test] +fn rng() { + let mut r = fastrand::Rng::new(); + + assert_ne!(r.u64(..), r.u64(..)); + + r.seed(7); + let a = r.u64(..); + r.seed(7); + let b = r.u64(..); + assert_eq!(a, b); +} + +#[test] +fn rng_init() { + let mut a = fastrand::Rng::new(); + let mut b = fastrand::Rng::new(); + assert_ne!(a.u64(..), b.u64(..)); + + a.seed(7); + b.seed(7); + assert_eq!(a.u64(..), b.u64(..)); +} + +#[test] +fn with_seed() { + let mut a = fastrand::Rng::with_seed(7); + let mut b = fastrand::Rng::new(); + b.seed(7); + assert_eq!(a.u64(..), b.u64(..)); +} + +#[test] +fn choose_multiple() { + let mut a = fastrand::Rng::new(); + let mut elements = (0..20).collect::>(); + + while !elements.is_empty() { + let chosen = a.choose_multiple(0..20, 5); + for &x in &chosen { + elements.retain(|&y| y != x); + } + } +} + +#[test] +fn choice() { + let items = [1, 4, 9, 5, 2, 3, 6, 7, 8, 0]; + let mut r = fastrand::Rng::new(); + + for item in &items { + while r.choice(&items).unwrap() != item {} + } +} -- cgit v1.2.3