commit a0a2f954aae3f7a7c95a7978c8fef491bf0c3d5a parent b781ce704ed8ce70634811d369cbad10ba3477dd Author: Erich Gubler <erichdongubler@gmail.com> Date: Thu, 2 Oct 2025 18:09:19 +0000 Bug 1991226 - upgrade `hashbrown` 0.15.2 → 0.16.0 r=glandium Differential Revision: https://phabricator.services.mozilla.com/D266857 Diffstat:
34 files changed, 1157 insertions(+), 462 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock @@ -2213,9 +2213,9 @@ dependencies = [ [[package]] name = "foldhash" -version = "0.1.5" +version = "0.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d9c4f5dac5e15c24eb999c26181a6ca40b39fe946cbe4c263c7209467bc83af2" +checksum = "77ce24cb58228fbb8aa041425bb1050850ac19177686ea6e0f41a70416f56fdb" [[package]] name = "foreign-types" @@ -2847,7 +2847,7 @@ checksum = "b89c83349105e3732062a895becfc71a8f921bb71ecbbdd8ff99263e3b53a0ca" dependencies = [ "bitflags 2.9.0", "gpu-descriptor-types", - "hashbrown 0.15.2", + "hashbrown 0.15.999", ] [[package]] @@ -2919,21 +2919,28 @@ dependencies = [ name = "hashbrown" version = "0.13.999" dependencies = [ - "hashbrown 0.15.2", + "hashbrown 0.15.999", ] [[package]] name = "hashbrown" version = "0.14.999" dependencies = [ - "hashbrown 0.15.2", + "hashbrown 0.15.999", ] [[package]] name = "hashbrown" -version = "0.15.2" +version = "0.15.999" +dependencies = [ + "hashbrown 0.16.0", +] + +[[package]] +name = "hashbrown" +version = "0.16.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "bf151400ff0baff5465007dd2f3e717f3fe502074ca563069ce3a6629d07b289" +checksum = "5419bdc4f6a9207fbeba6d11b604d481addf78ecd10c11ad51e76c2f6482748d" dependencies = [ "allocator-api2", "equivalent", @@ -2946,7 +2953,7 @@ name = "hashlink" version = "0.10.0" source = "git+https://github.com/erichdongubler-contrib/hashlink?rev=76dc47a12af5829c1e8bf4834e38b410dec2aeff#76dc47a12af5829c1e8bf4834e38b410dec2aeff" dependencies = [ - "hashbrown 0.15.2", + "hashbrown 0.15.999", ] [[package]] @@ -3369,7 +3376,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "4b0f83760fb341a774ed326568e19f5a863af4a952def8c39f9ab92fd95b88e5" dependencies = [ "equivalent", - "hashbrown 0.15.2", + "hashbrown 0.15.999", "serde", "serde_core", ] @@ -4669,7 +4676,7 @@ dependencies = [ "cfg_aliases", "codespan-reporting", "half 2.5.0", - "hashbrown 0.15.2", + "hashbrown 0.15.999", "hexf-parse", "indexmap", "libm", @@ -7744,7 +7751,7 @@ dependencies = [ "bytemuck", "cfg_aliases", "document-features", - "hashbrown 0.15.2", + "hashbrown 0.15.999", "indexmap", "log", "naga", @@ -7796,7 +7803,7 @@ dependencies = [ "gpu-alloc", "gpu-allocator", "gpu-descriptor", - "hashbrown 0.15.2", + "hashbrown 0.15.999", "libc", "libloading", "log", diff --git a/Cargo.toml b/Cargo.toml @@ -185,7 +185,10 @@ memoffset = { path = "build/rust/memoffset" } hashbrown_0_13 = { package = "hashbrown", path = "build/rust/hashbrown-0.13" } # Patch `hashbrown` 0.14.* to depend on 0.15.* -hashbrown_0_14 = { package = "hashbrown", path = "build/rust/hashbrown" } +hashbrown_0_14 = { package = "hashbrown", path = "build/rust/hashbrown-0.14" } + +# Patch `hashbrown` 0.15.* to depend on 0.16.* +hashbrown_0_15 = { package = "hashbrown", path = "build/rust/hashbrown" } # Patch `thiserror` 1 to 2. thiserror = { path = "build/rust/thiserror" } diff --git a/build/rust/hashbrown/Cargo.toml b/build/rust/hashbrown-0.14/Cargo.toml diff --git a/build/rust/hashbrown/lib.rs b/build/rust/hashbrown-0.14/lib.rs diff --git a/build/rust/hashbrown/Cargo.toml b/build/rust/hashbrown/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "hashbrown" -version = "0.14.999" +version = "0.15.999" edition = "2021" [lib] @@ -9,16 +9,11 @@ path = "lib.rs" [features] default = ["hashbrown/default"] allocator-api2 = ["hashbrown/allocator-api2"] -ahash = [ - # No direct equivalent in 0.15.*. However, the `ahash` feature made it so `DefaultHashBuilder` - # was a real struct that implemented `BuildHasher`, `Default`, etc. - # Enable 0.15.* `default-hasher` feature, which does the same. - "hashbrown/default-hasher" -] +default-hasher = ["hashbrown/default-hasher"] inline-more = ["hashbrown/inline-more"] raw = ["hashbrown/raw-entry"] serde = ["hashbrown/serde"] [dependencies.hashbrown] -version = "0.15.2" +version = "0.16.0" default-features = false diff --git a/build/rust/hashbrown/lib.rs b/build/rust/hashbrown/lib.rs @@ -2,10 +2,3 @@ * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ pub use hashbrown::*; - -// `hashbrown` 0.15.0 moved `DefaultHashBuilder` from the `hash_map` module to the root, so let's -// "undo" that. -pub mod hash_map { - pub use hashbrown::hash_map::*; - pub use hashbrown::DefaultHashBuilder; -} diff --git a/third_party/rust/foldhash/.cargo-checksum.json b/third_party/rust/foldhash/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.lock":"bed725327fa6f840ba753d5adf9b3b6ee9deba237912c002a6db8678b22e182e","Cargo.toml":"73f8a9098a796d870371f47aaace67ba93a1786b7d54f93c1122223dced77ea3","LICENSE":"b1181a40b2a7b25cf66fd01481713bc1005df082c53ef73e851e55071b102744","README.md":"fe47dcae2123a581799544a577b3a464962f3b51323b5495c53903b3bd3cd4ed","src/convenience.rs":"60338e1ca7bfc781724819cd82ef4a9bd61f4f5c17772b3c0f776fb2257c60dc","src/fast.rs":"99eb2a8e23446afc160ae70464a15fc9bb2006fbe9d0714f08ff936a7e069e1d","src/lib.rs":"8a5551c3568c0e52b4150cfee5c44fe176af0a11b02f5846ff9c635779a41e7c","src/quality.rs":"77a7edda8f0314d0ab1ebf9d08ec1b039d0d630988bfd8460149350b2a4b6f36","src/seed.rs":"358937fa085dcc5ca5ca488ff1767a7f0c371ebbca81355f44cbb848cb6dd698"},"package":"d9c4f5dac5e15c24eb999c26181a6ca40b39fe946cbe4c263c7209467bc83af2"} -\ No newline at end of file +{"files":{"Cargo.lock":"3bddb04a5cd4ee4b4f45de88c49f57af71ed19a2d4882ba48f160c4adea7a5cb","Cargo.toml":"0a76cc29da1c33f4bdb505f5828ecdc20859c4cb9faa402e000f5f10511a27cc","LICENSE":"b1181a40b2a7b25cf66fd01481713bc1005df082c53ef73e851e55071b102744","README.md":"e96613be984ff637c725f3f9abba366eb2d03a772695bed2d49dc61d330027ac","src/convenience.rs":"60338e1ca7bfc781724819cd82ef4a9bd61f4f5c17772b3c0f776fb2257c60dc","src/fast.rs":"807f098a619303f9e4d5cf582e0eb3b25c14451a36fa4e7a4ab440d3c95bf29e","src/lib.rs":"777319e7f2919bede856e13594169cfc4bdbaf2e541463da58c86e7e832dc45f","src/quality.rs":"33073e1869642a0c8689cfe3e8a1ecdc0a5c939b4e0a9ba03c111babf5b92849","src/seed.rs":"d4abbbbd7ca41f1dec07c0da3463b767ebdd953c0140eb94db617a7e3151cbe3"},"package":"77ce24cb58228fbb8aa041425bb1050850ac19177686ea6e0f41a70416f56fdb"} +\ No newline at end of file diff --git a/third_party/rust/foldhash/Cargo.lock b/third_party/rust/foldhash/Cargo.lock @@ -1,18 +1,18 @@ # This file is automatically @generated by Cargo. # It is not intended for manual editing. -version = 4 +version = 3 [[package]] name = "ahash" -version = "0.8.11" +version = "0.8.12" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e89da841a80418a9b391ebaea17f5c112ffaaa96f621d2c285b5174da76b9011" +checksum = "5a15f179cd60c4584b8a8c596927aadc462e27f2ca70c04e0071964a73ba7a75" dependencies = [ "cfg-if", - "getrandom", + "getrandom 0.3.3", "once_cell", "version_check", - "zerocopy 0.7.35", + "zerocopy", ] [[package]] @@ -53,21 +53,27 @@ checksum = "4b46cbb362ab8752921c97e041f5e366ee6297bd428a31275b9fcf1e380f7299" [[package]] name = "anstyle" -version = "1.0.10" +version = "1.0.11" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "55cc3b69f167a1ef2e161439aa98aed94e6028e5f9a59be9a6ffb47aef1651f9" +checksum = "862ed96ca487e809f1c8e5a8447f6ee2cf102f846893800b20cebdf541fc6bbd" [[package]] name = "autocfg" -version = "1.4.0" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8" + +[[package]] +name = "bitflags" +version = "2.9.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ace50bade8e6234aa140d9a2f552bbee1db4d353f69b8217bc503490fc1a9f26" +checksum = "1b8e56985ec62d17e9c1001dc89c88ecd7dc08e47eba5ec7c29c7b5eeecde967" [[package]] name = "bumpalo" -version = "3.17.0" +version = "3.19.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1628fb46dfa0b37568d12e5edd512553eccf6a22a78e8bde00bb4aed84d5bdbf" +checksum = "46c5e41b57b8bba42a04676d81cb89e9ee8e859a1a66f80a5a72e1cb76b34d43" [[package]] name = "byteorder" @@ -83,24 +89,24 @@ checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5" [[package]] name = "cc" -version = "1.2.16" +version = "1.2.31" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "be714c154be609ec7f5dad223a33bf1482fff90472de28f7362806e6d4832b8c" +checksum = "c3a42d84bb6b69d3a8b3eaacf0d88f179e1929695e1ad012b6cf64d9caaa5fd2" dependencies = [ "shlex", ] [[package]] name = "cfg-if" -version = "1.0.0" +version = "1.0.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" +checksum = "9555578bc9e57714c812a1f84e4fc5b4d21fcb063490c624de019f7464c91268" [[package]] name = "chrono" -version = "0.4.40" +version = "0.4.41" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1a7964611d71df112cb1730f2ee67324fcf4d0fc6606acbbe9bfe06df124637c" +checksum = "c469d952047f47f91b68d1cba3f10d63c11d73e4636f24f08daf0278abf01c4d" dependencies = [ "android-tzdata", "iana-time-zone", @@ -139,18 +145,18 @@ dependencies = [ [[package]] name = "clap" -version = "4.5.32" +version = "4.3.24" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "6088f3ae8c3608d19260cd7445411865a485688711b78b5be70d78cd96136f83" +checksum = "fb690e81c7840c0d7aade59f242ea3b41b9bc27bcd5997890e7702ae4b32e487" dependencies = [ "clap_builder", ] [[package]] name = "clap_builder" -version = "4.5.32" +version = "4.3.24" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "22a7ef7f676155edfb82daa97f99441f3ebf4a58d5e32f295a56259f1b6facc8" +checksum = "5ed2e96bc16d8d740f6f48d663eddf4b8a0983e79210fd55479b7bcd0a69860e" dependencies = [ "anstyle", "clap_lex", @@ -158,9 +164,9 @@ dependencies = [ [[package]] name = "clap_lex" -version = "0.7.4" +version = "0.5.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "f46ad14479a25103f283c0f10005961cf086d8dc42205bb44c46ac563475dca6" +checksum = "cd7cc57abe963c6d3b9d8be5b06ba7c8957a930305ca90304f24ef040aa6f961" [[package]] name = "core-foundation-sys" @@ -231,9 +237,9 @@ checksum = "d0a5c400df2834b80a4c3327b3aad3a4c4cd4de0629063962b03235697506a28" [[package]] name = "crunchy" -version = "0.2.3" +version = "0.2.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "43da5946c66ffcc7745f48db692ffbb10a83bfe0afd96235c5c2a4fb23994929" +checksum = "460fbee9c2c2f33933d720630a6a0bac33ba7053db5344fac858d4b8952d77d5" [[package]] name = "either" @@ -242,8 +248,20 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "48c757948c5ede0e46177b7add2e67155f70e33c07fea8284df6576da70b3719" [[package]] +name = "equivalent" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "877a4ace8713b0bcf2a4e7eec82529c029f1d0619886d18145fea96c3ffe5c0f" + +[[package]] name = "foldhash" version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9c4f5dac5e15c24eb999c26181a6ca40b39fe946cbe4c263c7209467bc83af2" + +[[package]] +name = "foldhash" +version = "0.2.0" dependencies = [ "ahash", "chrono", @@ -251,6 +269,7 @@ dependencies = [ "fxhash", "hashbrown", "rand", + "rapidhash", "uuid", ] @@ -265,20 +284,32 @@ dependencies = [ [[package]] name = "getrandom" -version = "0.2.15" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "335ff9f135e4384c8150d6f27c6daed433577f86b4750418338c01a1a2528592" +dependencies = [ + "cfg-if", + "libc", + "wasi 0.11.1+wasi-snapshot-preview1", +] + +[[package]] +name = "getrandom" +version = "0.3.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c4567c8db10ae91089c99af84c68c38da3ec2f087c3f82960bcdbf3656b6f4d7" +checksum = "26145e563e54f2cadc477553f1ec5ee650b00862f0a58bcd12cbdc5f0ea2d2f4" dependencies = [ "cfg-if", "libc", - "wasi", + "r-efi", + "wasi 0.14.2+wasi-0.2.4", ] [[package]] name = "half" -version = "2.5.0" +version = "2.4.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "7db2ff139bba50379da6aa0766b52fdcb62cb5b263009b09ed58ba604e14bbd1" +checksum = "6dd08c532ae367adf81c312a4580bc67f1d0fe8bc9c460520283f4c0ff277888" dependencies = [ "cfg-if", "crunchy", @@ -286,30 +317,32 @@ dependencies = [ [[package]] name = "hashbrown" -version = "0.14.5" +version = "0.15.5" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e5274423e17b7c9fc20b6e7e208532f9b19825d82dfd615708b70edd83df41f1" +checksum = "9229cfe53dfd69f0609a49f65461bd93001ea1ef889cd5529dd176593f5338a1" dependencies = [ - "ahash", "allocator-api2", + "equivalent", + "foldhash 0.1.5", ] [[package]] name = "hermit-abi" -version = "0.5.0" +version = "0.5.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "fbd780fe5cc30f81464441920d82ac8740e2e46b29a6fad543ddd075229ce37e" +checksum = "fc0fef456e4baa96da950455cd02c081ca953b141298e41db3fc7e36b1da849c" [[package]] name = "iana-time-zone" -version = "0.1.61" +version = "0.1.63" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "235e081f3925a06703c2d0117ea8b91f042756fd6e7a6e5d901e8ca1a996b220" +checksum = "b0c919e5debc312ad217002b8048a17b7d83f80703865bbfcfebb0458b0b27d8" dependencies = [ "android_system_properties", "core-foundation-sys", "iana-time-zone-haiku", "js-sys", + "log", "wasm-bindgen", "windows-core", ] @@ -361,21 +394,21 @@ dependencies = [ [[package]] name = "libc" -version = "0.2.171" +version = "0.2.174" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c19937216e9d3aa9956d9bb8dfc0b0c8beb6058fc4f7a4dc4d850edf86a237d6" +checksum = "1171693293099992e19cddea4e8b849964e9846f4acee11b3948bcc337be8776" [[package]] name = "log" -version = "0.4.26" +version = "0.4.27" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "30bde2b3dc3671ae49d8e2e9f044c7c005836e7a023ee57cffa25ab82764bb9e" +checksum = "13dc2df351e3202783a1fe0d44375f7295ffb4049267b0f3018346dc122a1d94" [[package]] name = "memchr" -version = "2.7.4" +version = "2.7.5" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "78ca9ab1a0babb1e7d5695e3530886289c18cf2f87ec19a575a0abdce112e3a3" +checksum = "32a282da65faaf38286cf3be983213fcf1d2e2a58700e808f83f4ea9a4804bc0" [[package]] name = "num-traits" @@ -388,9 +421,9 @@ dependencies = [ [[package]] name = "once_cell" -version = "1.21.1" +version = "1.21.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d75b0bedcc4fe52caa0e03d9f1151a323e4aa5e2d78ba3580400cd3c9e2bc4bc" +checksum = "42f5e15c9953c5e4ccceeb2e7382a716482c34515315f7b03532b8b4e8393d2d" [[package]] name = "oorandom" @@ -432,14 +465,14 @@ version = "0.2.21" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9" dependencies = [ - "zerocopy 0.8.23", + "zerocopy", ] [[package]] name = "proc-macro2" -version = "1.0.94" +version = "1.0.95" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "a31971752e70b8b2686d7e46ec17fb38dad4051d94024c88df49b667caea9c84" +checksum = "02b3e5e68a3a1a02aad3ec490a98007cbc13c37cbe84a3cd7b8e406d76e7f778" dependencies = [ "unicode-ident", ] @@ -454,6 +487,12 @@ dependencies = [ ] [[package]] +name = "r-efi" +version = "5.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "69cdb34c158ceb288df11e18b4bd39de994f6657d83847bdffdbd7f346754b0f" + +[[package]] name = "rand" version = "0.8.5" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -480,10 +519,16 @@ version = "0.6.4" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" dependencies = [ - "getrandom", + "getrandom 0.2.16", ] [[package]] +name = "rapidhash" +version = "3.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "efee4b7317469c6c6e7fdeee3d094313af846a97678d6ed971d83a852d730083" + +[[package]] name = "rayon" version = "1.10.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -534,9 +579,9 @@ checksum = "2b15c43186be67a4fd63bee50d0303afffcef381492ebe2c5d87f324e1b8815c" [[package]] name = "rustversion" -version = "1.0.20" +version = "1.0.21" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "eded382c5f5f786b989652c49544c4877d9f015cc22e145a5ea8ea66c2921cd2" +checksum = "8a0d197bd2c9dc6e53b84da9556a69ba4cdfab8619eb41a8bd1cc2027a0f6b1d" [[package]] name = "ryu" @@ -575,9 +620,9 @@ dependencies = [ [[package]] name = "serde_json" -version = "1.0.140" +version = "1.0.142" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "20068b6e96dc6c9bd23e01df8827e6c7e1f2fddd43c21810382803c136b99373" +checksum = "030fedb782600dcbd6f02d479bf0d817ac3bb40d644745b769d6a96bc3afc5a7" dependencies = [ "itoa", "memchr", @@ -593,9 +638,9 @@ checksum = "0fda2ff0d084019ba4d7c6f371c95d8fd75ce3524c3cb8fb653a3023f6323e64" [[package]] name = "syn" -version = "2.0.100" +version = "2.0.104" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "b09a44accad81e1ba1cd74a32461ba89dee89095ba17b32f5d03683b1b1fc2a0" +checksum = "17b6f705963418cdb9927482fa304bc562ece2fdd4f616084c50b7023b435a40" dependencies = [ "proc-macro2", "quote", @@ -620,9 +665,13 @@ checksum = "5a5f39404a5da50712a4c1eecf25e90dd62b613502b7e925fd4e4d19b5c96512" [[package]] name = "uuid" -version = "1.16.0" +version = "1.17.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "458f7a779bf54acc9f347480ac654f68407d3aab21269a6e3c9f922acd9e2da9" +checksum = "3cf4199d1e5d15ddd86a694e4d0dffa9c323ce759fea589f00fef9d81cc1931d" +dependencies = [ + "js-sys", + "wasm-bindgen", +] [[package]] name = "version_check" @@ -642,9 +691,18 @@ dependencies = [ [[package]] name = "wasi" -version = "0.11.0+wasi-snapshot-preview1" +version = "0.11.1+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ccf3ec651a847eb01de73ccad15eb7d99f80485de043efb2f370cd654f4ea44b" + +[[package]] +name = "wasi" +version = "0.14.2+wasi-0.2.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" +checksum = "9683f9a5a998d873c0d21fcbe3c083009670149a8fab228644b8bd36b2c48cb3" +dependencies = [ + "wit-bindgen-rt", +] [[package]] name = "wasm-bindgen" @@ -725,18 +783,62 @@ dependencies = [ [[package]] name = "windows-core" -version = "0.52.0" +version = "0.61.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "33ab640c8d7e35bf8ba19b884ba838ceb4fba93a4e8c65a9059d08afcfc683d9" +checksum = "c0fdd3ddb90610c7638aa2b3a3ab2904fb9e5cdbecc643ddb3647212781c4ae3" dependencies = [ - "windows-targets", + "windows-implement", + "windows-interface", + "windows-link", + "windows-result", + "windows-strings", +] + +[[package]] +name = "windows-implement" +version = "0.60.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a47fddd13af08290e67f4acabf4b459f647552718f683a7b415d290ac744a836" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "windows-interface" +version = "0.59.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bd9211b69f8dcdfa817bfd14bf1c97c9188afa36f4750130fcdf3f400eca9fa8" +dependencies = [ + "proc-macro2", + "quote", + "syn", ] [[package]] name = "windows-link" -version = "0.1.0" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5e6ad25900d524eaabdbbb96d20b4311e1e7ae1699af4fb28c17ae66c80d798a" + +[[package]] +name = "windows-result" +version = "0.3.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "56f42bd332cc6c8eac5af113fc0c1fd6a8fd2aa08a0119358686e5160d0586c6" +dependencies = [ + "windows-link", +] + +[[package]] +name = "windows-strings" +version = "0.4.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "6dccfd733ce2b1753b03b6d3c65edf020262ea35e20ccdf3e288043e6dd620e3" +checksum = "56e6c93f3a0c3b36176cb1327a4958a0353d5d166c2a35cb268ace15e91d3b57" +dependencies = [ + "windows-link", +] [[package]] name = "windows-sys" @@ -812,39 +914,28 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "589f6da84c646204747d1270a2a5661ea66ed1cced2631d546fdfb155959f9ec" [[package]] -name = "zerocopy" -version = "0.7.35" +name = "wit-bindgen-rt" +version = "0.39.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1b9b4fd18abc82b8136838da5d50bae7bdea537c574d8dc1a34ed098d6c166f0" +checksum = "6f42320e61fe2cfd34354ecb597f86f413484a798ba44a8ca1165c58d42da6c1" dependencies = [ - "zerocopy-derive 0.7.35", + "bitflags", ] [[package]] name = "zerocopy" -version = "0.8.23" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "fd97444d05a4328b90e75e503a34bad781f14e28a823ad3557f0750df1ebcbc6" -dependencies = [ - "zerocopy-derive 0.8.23", -] - -[[package]] -name = "zerocopy-derive" -version = "0.7.35" +version = "0.8.26" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "fa4f8080344d4671fb4e831a13ad1e68092748387dfc4f55e356242fae12ce3e" +checksum = "1039dd0d3c310cf05de012d8a39ff557cb0d23087fd44cad61df08fc31907a2f" dependencies = [ - "proc-macro2", - "quote", - "syn", + "zerocopy-derive", ] [[package]] name = "zerocopy-derive" -version = "0.8.23" +version = "0.8.26" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "6352c01d0edd5db859a63e2605f4ea3183ddbd15e2c4a9e7d32184df75e4f154" +checksum = "9ecf5b4cc5364572d7f4c329661bcc82724222973f2cab6f050a4e5c22f75181" dependencies = [ "proc-macro2", "quote", diff --git a/third_party/rust/foldhash/Cargo.toml b/third_party/rust/foldhash/Cargo.toml @@ -13,7 +13,7 @@ edition = "2021" rust-version = "1.60" name = "foldhash" -version = "0.1.5" +version = "0.2.0" authors = ["Orson Peters <orsonpeters@gmail.com>"] build = false exclude = [ @@ -42,6 +42,7 @@ repository = "https://github.com/orlp/foldhash" [features] default = ["std"] +nightly = [] std = [] [lib] @@ -64,11 +65,14 @@ version = "0.5" version = "0.2" [dev-dependencies.hashbrown] -version = "0.14" +version = "0.15" [dev-dependencies.rand] version = "0.8" +[dev-dependencies.rapidhash] +version = "3.1.0" + [dev-dependencies.uuid] version = "1.8" diff --git a/third_party/rust/foldhash/README.md b/third_party/rust/foldhash/README.md @@ -275,3 +275,9 @@ outputs, and feasible to derive the secret values from indirect observation of hashes, such as through timing attacks or hash table iteration. Once an attacker knows the secret values, they can once again create infinite hash collisions with ease. + + +## Acknowledgements + +We thank Liam Gray for their suggestions on improving string hashing +performance. diff --git a/third_party/rust/foldhash/src/fast.rs b/third_party/rust/foldhash/src/fast.rs @@ -3,7 +3,7 @@ use core::hash::{BuildHasher, Hasher}; use crate::seed::{gen_per_hasher_seed, GlobalSeed, SharedSeed}; -use crate::{folded_multiply, hash_bytes_long, hash_bytes_medium, rotate_right, ARBITRARY3}; +use crate::{folded_multiply, hash_bytes_long, hash_bytes_short, rotate_right, ARBITRARY3}; /// A [`Hasher`] instance implementing foldhash, optimized for speed. /// @@ -11,29 +11,23 @@ use crate::{folded_multiply, hash_bytes_long, hash_bytes_medium, rotate_right, A /// most likely want to use [`RandomState`], [`SeedableRandomState`] or /// [`FixedState`] to create [`FoldHasher`]s. #[derive(Clone)] -pub struct FoldHasher { +pub struct FoldHasher<'a> { accumulator: u64, sponge: u128, sponge_len: u8, - fold_seed: u64, - expand_seed: u64, - expand_seed2: u64, - expand_seed3: u64, + seeds: &'a [u64; 6], } -impl FoldHasher { +impl<'a> FoldHasher<'a> { /// Initializes this [`FoldHasher`] with the given per-hasher seed and /// [`SharedSeed`]. #[inline] - pub fn with_seed(per_hasher_seed: u64, shared_seed: &SharedSeed) -> FoldHasher { + pub const fn with_seed(per_hasher_seed: u64, shared_seed: &'a SharedSeed) -> FoldHasher<'a> { FoldHasher { accumulator: per_hasher_seed, sponge: 0, sponge_len: 0, - fold_seed: shared_seed.seeds[0], - expand_seed: shared_seed.seeds[1], - expand_seed2: shared_seed.seeds[2], - expand_seed3: shared_seed.seeds[3], + seeds: &shared_seed.seeds, } } @@ -43,7 +37,7 @@ impl FoldHasher { if self.sponge_len as usize + bits > 128 { let lo = self.sponge as u64; let hi = (self.sponge >> 64) as u64; - self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed); + self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.seeds[0]); self.sponge = x.into(); self.sponge_len = bits as u8; } else { @@ -53,7 +47,7 @@ impl FoldHasher { } } -impl Hasher for FoldHasher { +impl<'a> Hasher for FoldHasher<'a> { #[inline(always)] fn write(&mut self, bytes: &[u8]) { // We perform overlapping reads in the byte hash which could lead to @@ -62,41 +56,14 @@ impl Hasher for FoldHasher { // which costs only a single cycle (or none if executed with // instruction-level parallelism). let len = bytes.len(); - let base_seed = rotate_right(self.accumulator, len as u32); + self.accumulator = rotate_right(self.accumulator, len as u32); if len <= 16 { - let mut s0 = base_seed; - let mut s1 = self.expand_seed; - // XOR the input into s0, s1, then multiply and fold. - if len >= 8 { - s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap()); - s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap()); - } else if len >= 4 { - s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64; - s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64; - } else if len > 0 { - let lo = bytes[0]; - let mid = bytes[len / 2]; - let hi = bytes[len - 1]; - s0 ^= lo as u64; - s1 ^= ((hi as u64) << 8) | mid as u64; - } - self.accumulator = folded_multiply(s0, s1); - } else if len < 256 { - self.accumulator = hash_bytes_medium( - bytes, - base_seed, - base_seed.wrapping_add(self.expand_seed), - self.fold_seed, - ); + self.accumulator = hash_bytes_short(bytes, self.accumulator, self.seeds); } else { - self.accumulator = hash_bytes_long( - bytes, - base_seed, - base_seed.wrapping_add(self.expand_seed), - base_seed.wrapping_add(self.expand_seed2), - base_seed.wrapping_add(self.expand_seed3), - self.fold_seed, - ); + unsafe { + // SAFETY: we checked that the length is > 16 bytes. + self.accumulator = hash_bytes_long(bytes, self.accumulator, self.seeds); + } } } @@ -124,7 +91,7 @@ impl Hasher for FoldHasher { fn write_u128(&mut self, i: u128) { let lo = i as u64; let hi = (i >> 64) as u64; - self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed); + self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.seeds[0]); } #[inline(always)] @@ -136,12 +103,19 @@ impl Hasher for FoldHasher { self.write_num(i as u64); } + #[cfg(feature = "nightly")] + #[inline(always)] + fn write_str(&mut self, s: &str) { + // Our write function already handles length differences. + self.write(s.as_bytes()) + } + #[inline(always)] fn finish(&self) -> u64 { if self.sponge_len > 0 { let lo = self.sponge as u64; let hi = (self.sponge >> 64) as u64; - folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed) + folded_multiply(lo ^ self.accumulator, hi ^ self.seeds[0]) } else { self.accumulator } @@ -149,7 +123,7 @@ impl Hasher for FoldHasher { } /// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly initialized. -#[derive(Copy, Clone, Debug)] +#[derive(Clone, Debug)] pub struct RandomState { per_hasher_seed: u64, global_seed: GlobalSeed, @@ -166,10 +140,10 @@ impl Default for RandomState { } impl BuildHasher for RandomState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher::with_seed(self.per_hasher_seed, self.global_seed.get()) } } @@ -179,7 +153,7 @@ impl BuildHasher for RandomState { /// /// This can be useful for e.g. testing, but the downside is that this type /// has a size of 16 bytes rather than the 8 bytes [`RandomState`] is. -#[derive(Copy, Clone, Debug)] +#[derive(Clone, Debug)] pub struct SeedableRandomState { per_hasher_seed: u64, shared_seed: &'static SharedSeed, @@ -224,10 +198,10 @@ impl SeedableRandomState { } impl BuildHasher for SeedableRandomState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher::with_seed(self.per_hasher_seed, self.shared_seed) } } @@ -235,7 +209,7 @@ impl BuildHasher for SeedableRandomState { /// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that always has the same fixed seed. /// /// Not recommended unless you absolutely need determinism. -#[derive(Copy, Clone, Debug)] +#[derive(Clone, Debug)] pub struct FixedState { per_hasher_seed: u64, } @@ -261,10 +235,10 @@ impl Default for FixedState { } impl BuildHasher for FixedState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher::with_seed(self.per_hasher_seed, SharedSeed::global_fixed()) } } diff --git a/third_party/rust/foldhash/src/lib.rs b/third_party/rust/foldhash/src/lib.rs @@ -101,8 +101,18 @@ //! [`RandomState`](fast::RandomState) by default but can be seeded in any manner. //! This state must include an explicit reference to a [`SharedSeed`], and thus //! this struct is 16 bytes as opposed to just 8 bytes for the previous two. +//! +//! ## Features +//! +//! This crate has the following features: +//! - `nightly`, this feature improves string hashing performance +//! slightly using the nightly-only Rust feature +//! [`hasher_prefixfree_extras`](https://github.com/rust-lang/rust/issues/96762), +//! - `std`, this enabled-by-default feature offers convenient aliases for `std` +//! containers, but can be turned off for `#![no_std]` crates. #![cfg_attr(all(not(test), not(feature = "std")), no_std)] +#![cfg_attr(feature = "nightly", feature(hasher_prefixfree_extras))] #![warn(missing_docs)] pub mod fast; @@ -126,6 +136,8 @@ const ARBITRARY6: u64 = 0xc0ac29b7c97c50dd; const ARBITRARY7: u64 = 0x3f84d5b5b5470917; const ARBITRARY8: u64 = 0x9216d5d98979fb1b; const ARBITRARY9: u64 = 0xd1310ba698dfb5ac; +const ARBITRARY10: u64 = 0x2ffd72dbd01adfb7; +const ARBITRARY11: u64 = 0xb8e1afed6a267e96; #[inline(always)] const fn folded_multiply(x: u64, y: u64) -> u64 { @@ -220,65 +232,119 @@ const fn rotate_right(x: u64, r: u32) -> u64 { } } -/// Hashes strings >= 16 bytes, has unspecified behavior when bytes.len() < 16. -fn hash_bytes_medium(bytes: &[u8], mut s0: u64, mut s1: u64, fold_seed: u64) -> u64 { - // Process 32 bytes per iteration, 16 bytes from the start, 16 bytes from - // the end. On the last iteration these two chunks can overlap, but that is - // perfectly fine. - let left_to_right = bytes.chunks_exact(16); - let mut right_to_left = bytes.rchunks_exact(16); - for lo in left_to_right { - let hi = right_to_left.next().unwrap(); - let unconsumed_start = lo.as_ptr(); - let unconsumed_end = hi.as_ptr_range().end; - if unconsumed_start >= unconsumed_end { - break; - } +#[cold] +fn cold_path() {} - let a = u64::from_ne_bytes(lo[0..8].try_into().unwrap()); - let b = u64::from_ne_bytes(lo[8..16].try_into().unwrap()); - let c = u64::from_ne_bytes(hi[0..8].try_into().unwrap()); - let d = u64::from_ne_bytes(hi[8..16].try_into().unwrap()); - s0 = folded_multiply(a ^ s0, c ^ fold_seed); - s1 = folded_multiply(b ^ s1, d ^ fold_seed); +/// Hashes strings <= 16 bytes, has unspecified behavior when bytes.len() > 16. +#[inline(always)] +fn hash_bytes_short(bytes: &[u8], accumulator: u64, seeds: &[u64; 6]) -> u64 { + let len = bytes.len(); + let mut s0 = accumulator; + let mut s1 = seeds[1]; + // XOR the input into s0, s1, then multiply and fold. + if len >= 8 { + s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap()); + s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap()); + } else if len >= 4 { + s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64; + s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64; + } else if len > 0 { + let lo = bytes[0]; + let mid = bytes[len / 2]; + let hi = bytes[len - 1]; + s0 ^= lo as u64; + s1 ^= ((hi as u64) << 8) | mid as u64; } + folded_multiply(s0, s1) +} - s0 ^ s1 +/// Load 8 bytes into a u64 word at the given offset. +/// +/// # Safety +/// You must ensure that offset + 8 <= bytes.len(). +#[inline(always)] +unsafe fn load(bytes: &[u8], offset: usize) -> u64 { + // In most (but not all) cases this unsafe code is not necessary to avoid + // the bounds checks in the below code, but the register allocation became + // worse if I replaced those calls which could be replaced with safe code. + unsafe { bytes.as_ptr().add(offset).cast::<u64>().read_unaligned() } } -/// Hashes strings >= 16 bytes, has unspecified behavior when bytes.len() < 16. +/// Hashes strings > 16 bytes. +/// +/// # Safety +/// v.len() must be > 16 bytes. #[cold] #[inline(never)] -fn hash_bytes_long( - bytes: &[u8], - mut s0: u64, - mut s1: u64, - mut s2: u64, - mut s3: u64, - fold_seed: u64, -) -> u64 { - let chunks = bytes.chunks_exact(64); - let remainder = chunks.remainder().len(); - for chunk in chunks { - let a = u64::from_ne_bytes(chunk[0..8].try_into().unwrap()); - let b = u64::from_ne_bytes(chunk[8..16].try_into().unwrap()); - let c = u64::from_ne_bytes(chunk[16..24].try_into().unwrap()); - let d = u64::from_ne_bytes(chunk[24..32].try_into().unwrap()); - let e = u64::from_ne_bytes(chunk[32..40].try_into().unwrap()); - let f = u64::from_ne_bytes(chunk[40..48].try_into().unwrap()); - let g = u64::from_ne_bytes(chunk[48..56].try_into().unwrap()); - let h = u64::from_ne_bytes(chunk[56..64].try_into().unwrap()); - s0 = folded_multiply(a ^ s0, e ^ fold_seed); - s1 = folded_multiply(b ^ s1, f ^ fold_seed); - s2 = folded_multiply(c ^ s2, g ^ fold_seed); - s3 = folded_multiply(d ^ s3, h ^ fold_seed); +unsafe fn hash_bytes_long(mut v: &[u8], accumulator: u64, seeds: &[u64; 6]) -> u64 { + let mut s0 = accumulator; + let mut s1 = s0.wrapping_add(seeds[1]); + + if v.len() > 128 { + cold_path(); + let mut s2 = s0.wrapping_add(seeds[2]); + let mut s3 = s0.wrapping_add(seeds[3]); + + if v.len() > 256 { + cold_path(); + let mut s4 = s0.wrapping_add(seeds[4]); + let mut s5 = s0.wrapping_add(seeds[5]); + loop { + unsafe { + // SAFETY: we checked the length is > 256, we index at most v[..96]. + s0 = folded_multiply(load(v, 0) ^ s0, load(v, 48) ^ seeds[0]); + s1 = folded_multiply(load(v, 8) ^ s1, load(v, 56) ^ seeds[0]); + s2 = folded_multiply(load(v, 16) ^ s2, load(v, 64) ^ seeds[0]); + s3 = folded_multiply(load(v, 24) ^ s3, load(v, 72) ^ seeds[0]); + s4 = folded_multiply(load(v, 32) ^ s4, load(v, 80) ^ seeds[0]); + s5 = folded_multiply(load(v, 40) ^ s5, load(v, 88) ^ seeds[0]); + } + v = &v[96..]; + if v.len() <= 256 { + break; + } + } + s0 ^= s4; + s1 ^= s5; + } + + loop { + unsafe { + // SAFETY: we checked the length is > 128, we index at most v[..64]. + s0 = folded_multiply(load(v, 0) ^ s0, load(v, 32) ^ seeds[0]); + s1 = folded_multiply(load(v, 8) ^ s1, load(v, 40) ^ seeds[0]); + s2 = folded_multiply(load(v, 16) ^ s2, load(v, 48) ^ seeds[0]); + s3 = folded_multiply(load(v, 24) ^ s3, load(v, 56) ^ seeds[0]); + } + v = &v[64..]; + if v.len() <= 128 { + break; + } + } + s0 ^= s2; + s1 ^= s3; } - s0 ^= s2; - s1 ^= s3; - if remainder > 0 { - hash_bytes_medium(&bytes[bytes.len() - remainder.max(16)..], s0, s1, fold_seed) - } else { - s0 ^ s1 + let len = v.len(); + unsafe { + // SAFETY: our precondition ensures our length is at least 16, and the + // above loops do not reduce the length under that. This protects our + // first iteration of this loop, the further iterations are protected + // directly by the checks on len. + s0 = folded_multiply(load(v, 0) ^ s0, load(v, len - 16) ^ seeds[0]); + s1 = folded_multiply(load(v, 8) ^ s1, load(v, len - 8) ^ seeds[0]); + if len >= 32 { + s0 = folded_multiply(load(v, 16) ^ s0, load(v, len - 32) ^ seeds[0]); + s1 = folded_multiply(load(v, 24) ^ s1, load(v, len - 24) ^ seeds[0]); + if len >= 64 { + s0 = folded_multiply(load(v, 32) ^ s0, load(v, len - 48) ^ seeds[0]); + s1 = folded_multiply(load(v, 40) ^ s1, load(v, len - 40) ^ seeds[0]); + if len >= 96 { + s0 = folded_multiply(load(v, 48) ^ s0, load(v, len - 64) ^ seeds[0]); + s1 = folded_multiply(load(v, 56) ^ s1, load(v, len - 56) ^ seeds[0]); + } + } + } } + s0 ^ s1 } diff --git a/third_party/rust/foldhash/src/quality.rs b/third_party/rust/foldhash/src/quality.rs @@ -4,7 +4,7 @@ use core::hash::{BuildHasher, Hasher}; use crate::seed::SharedSeed; -use crate::{fast, folded_multiply, ARBITRARY0, ARBITRARY8}; +use crate::{fast, folded_multiply, ARBITRARY0, ARBITRARY4}; /// A [`Hasher`] instance implementing foldhash, optimized for quality. /// @@ -12,22 +12,22 @@ use crate::{fast, folded_multiply, ARBITRARY0, ARBITRARY8}; /// most likely want to use [`RandomState`], [`SeedableRandomState`] or /// [`FixedState`] to create [`FoldHasher`]s. #[derive(Clone)] -pub struct FoldHasher { - pub(crate) inner: fast::FoldHasher, +pub struct FoldHasher<'a> { + pub(crate) inner: fast::FoldHasher<'a>, } -impl FoldHasher { +impl<'a> FoldHasher<'a> { /// Initializes this [`FoldHasher`] with the given per-hasher seed and /// [`SharedSeed`]. #[inline(always)] - pub fn with_seed(per_hasher_seed: u64, shared_seed: &SharedSeed) -> FoldHasher { + pub const fn with_seed(per_hasher_seed: u64, shared_seed: &'a SharedSeed) -> FoldHasher<'a> { FoldHasher { inner: fast::FoldHasher::with_seed(per_hasher_seed, shared_seed), } } } -impl Hasher for FoldHasher { +impl<'a> Hasher for FoldHasher<'a> { #[inline(always)] fn write(&mut self, bytes: &[u8]) { self.inner.write(bytes); @@ -63,6 +63,12 @@ impl Hasher for FoldHasher { self.inner.write_usize(i); } + #[cfg(feature = "nightly")] + #[inline(always)] + fn write_str(&mut self, s: &str) { + self.inner.write_str(s); + } + #[inline(always)] fn finish(&self) -> u64 { folded_multiply(self.inner.finish(), ARBITRARY0) @@ -70,16 +76,16 @@ impl Hasher for FoldHasher { } /// A [`BuildHasher`] for [`quality::FoldHasher`](FoldHasher) that is randomly initialized. -#[derive(Copy, Clone, Default, Debug)] +#[derive(Clone, Default, Debug)] pub struct RandomState { inner: fast::RandomState, } impl BuildHasher for RandomState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher { inner: self.inner.build_hasher(), } @@ -91,7 +97,7 @@ impl BuildHasher for RandomState { /// /// This can be useful for e.g. testing, but the downside is that this type /// has a size of 16 bytes rather than the 8 bytes [`RandomState`] is. -#[derive(Copy, Clone, Default, Debug)] +#[derive(Clone, Default, Debug)] pub struct SeedableRandomState { inner: fast::SeedableRandomState, } @@ -122,7 +128,7 @@ impl SeedableRandomState { // the quality hash to ensure better independence between seed // and hash. inner: fast::SeedableRandomState::with_seed( - folded_multiply(per_hasher_seed, ARBITRARY8), + folded_multiply(per_hasher_seed, ARBITRARY4), shared_seed, ), } @@ -130,10 +136,10 @@ impl SeedableRandomState { } impl BuildHasher for SeedableRandomState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher { inner: self.inner.build_hasher(), } @@ -143,7 +149,7 @@ impl BuildHasher for SeedableRandomState { /// A [`BuildHasher`] for [`quality::FoldHasher`](FoldHasher) that always has the same fixed seed. /// /// Not recommended unless you absolutely need determinism. -#[derive(Copy, Clone, Default, Debug)] +#[derive(Clone, Default, Debug)] pub struct FixedState { inner: fast::FixedState, } @@ -157,16 +163,16 @@ impl FixedState { // the quality hash to ensure better independence between seed // and hash. If the seed is zero the folded multiply is zero, // preserving with_seed(0) == default(). - inner: fast::FixedState::with_seed(folded_multiply(per_hasher_seed, ARBITRARY8)), + inner: fast::FixedState::with_seed(folded_multiply(per_hasher_seed, ARBITRARY4)), } } } impl BuildHasher for FixedState { - type Hasher = FoldHasher; + type Hasher = FoldHasher<'static>; #[inline(always)] - fn build_hasher(&self) -> FoldHasher { + fn build_hasher(&self) -> FoldHasher<'static> { FoldHasher { inner: self.inner.build_hasher(), } diff --git a/third_party/rust/foldhash/src/seed.rs b/third_party/rust/foldhash/src/seed.rs @@ -1,12 +1,22 @@ // These constants may end up unused depending on platform support. #[allow(unused)] -use crate::{ARBITRARY1, ARBITRARY9}; +use crate::{ARBITRARY1, ARBITRARY5}; -use super::{folded_multiply, ARBITRARY2, ARBITRARY4, ARBITRARY5, ARBITRARY6, ARBITRARY7}; +use super::{ + folded_multiply, ARBITRARY10, ARBITRARY11, ARBITRARY2, ARBITRARY6, ARBITRARY7, ARBITRARY8, + ARBITRARY9, +}; /// Used for FixedState, and RandomState if atomics for dynamic init are unavailable. const FIXED_GLOBAL_SEED: SharedSeed = SharedSeed { - seeds: [ARBITRARY4, ARBITRARY5, ARBITRARY6, ARBITRARY7], + seeds: [ + ARBITRARY6, + ARBITRARY7, + ARBITRARY8, + ARBITRARY9, + ARBITRARY10, + ARBITRARY11, + ], }; pub(crate) fn gen_per_hasher_seed() -> u64 { @@ -66,7 +76,7 @@ pub(crate) fn gen_per_hasher_seed() -> u64 { /// and [`SeedableRandomState::with_seed`](crate::fast::SeedableRandomState::with_seed). #[derive(Clone, Debug)] pub struct SharedSeed { - pub(crate) seeds: [u64; 4], + pub(crate) seeds: [u64; 6], } impl SharedSeed { @@ -92,7 +102,7 @@ impl SharedSeed { pub const fn from_u64(seed: u64) -> Self { macro_rules! mix { ($x: expr) => { - folded_multiply($x, ARBITRARY9) + folded_multiply($x, ARBITRARY5) }; } @@ -100,6 +110,8 @@ impl SharedSeed { let seed_b = mix!(mix!(mix!(seed_a))); let seed_c = mix!(mix!(mix!(seed_b))); let seed_d = mix!(mix!(mix!(seed_c))); + let seed_e = mix!(mix!(mix!(seed_d))); + let seed_f = mix!(mix!(mix!(seed_e))); // Zeroes form a weak-point for the multiply-mix, and zeroes tend to be // a common input. So we want our global seeds that are XOR'ed with the @@ -112,6 +124,8 @@ impl SharedSeed { seed_b | FORCED_ONES, seed_c | FORCED_ONES, seed_d | FORCED_ONES, + seed_e | FORCED_ONES, + seed_f | FORCED_ONES, ], } } @@ -124,7 +138,7 @@ mod global { use core::sync::atomic::{AtomicU8, Ordering}; fn generate_global_seed() -> SharedSeed { - let mix = |seed: u64, x: u64| folded_multiply(seed ^ x, ARBITRARY9); + let mix = |seed: u64, x: u64| folded_multiply(seed ^ x, ARBITRARY5); // Use address space layout randomization as our main randomness source. // This isn't great, but we don't advertise HashDoS resistance in the first @@ -180,7 +194,7 @@ mod global { static GLOBAL_SEED_STORAGE: GlobalSeedStorage = GlobalSeedStorage { state: AtomicU8::new(UNINIT), - seed: UnsafeCell::new(SharedSeed { seeds: [0; 4] }), + seed: UnsafeCell::new(SharedSeed { seeds: [0; 6] }), }; /// An object representing an initialized global seed. diff --git a/third_party/rust/hashbrown/.cargo-checksum.json b/third_party/rust/hashbrown/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"CHANGELOG.md":"99bd8c6f9a5754b9c3678280e3e902e1b91a23e18f5de4dc122b61752329cf5d","Cargo.lock":"f8dfd98d915cadcc77bc4b36d6375f799b9702481866cab0c8db1b82348933f7","Cargo.toml":"04ca9c21392dc5171b18af0630cae19af1a6896f9d2f61a9ab788a0511ebd63d","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ff8f68cb076caf8cefe7a6430d4ac086ce6af2ca8ce2c4e5a2004d4552ef52a2","README.md":"70391979c2398f00f79cf3af0fed9b58c5d0c568a6123c3c0ea6bd03fc3b13be","benches/bench.rs":"9e5da01f699980543d9ec0035f2b92d44d8a5b3c83b8f58e355e17b5678792dd","benches/insert_unique_unchecked.rs":"dfe644035cad6ff13b280e3d72c9df2569491ecddc84f7c2502daf940814a63e","benches/set_ops.rs":"936cd15055c25d42aabc6bde738e3135da541520b40633c4fba940eb73e06f4d","clippy.toml":"7535949f908c6d9aea4f9a9f3a7625552c93fc29e963d059d40f4def9d77ea7b","src/control/bitmask.rs":"53dcdac056620f02c475b618d33e69f34152ea559d86bd4545546144f017baa0","src/control/group/generic.rs":"939b2e35e6ea5430a606a054ffc8ea3e22b867d83f2afed15525cf59a617eb6e","src/control/group/mod.rs":"795443113ab125e2017db443a578084d6a588965070380f1951a513377545c4c","src/control/group/neon.rs":"bde7726d321bd036cb9001818f962784346b932087b9f655c85ab26667d55fbb","src/control/group/sse2.rs":"833da90ab3fd72d306d5b999de96a4b6b52aa1a16ee7273c89bd12c9ead3bc45","src/control/mod.rs":"83fede19e9c5a26fd2c7372e6cf92547d32ade4cd69fde8a0eaaeb1be6ddc2ba","src/control/tag.rs":"9c94ab42aad3918bd77ffafdeb253f7f773a8f98bf56e36b85ebdc7a11ef676b","src/external_trait_impls/mod.rs":"d69528827794524cfd9acbeacc1ac4f6131e3c7574311e6d919f818f65fbff07","src/external_trait_impls/rayon/helpers.rs":"ba105bf0853ebc45157f22116ad0f55d3bdab75e721d8e7a677c7b912d0c0c6d","src/external_trait_impls/rayon/map.rs":"e1e08653c6c3d2f0586638ab7baf082c06fdc5551b5852b0f9e73aa9484b4955","src/external_trait_impls/rayon/mod.rs":"126edc882501dddd25e442d9236508b5b386eb8c0a9f5d654f2dd081086c1616","src/external_trait_impls/rayon/raw.rs":"04012fb2e99648819b4bc0044107ed3cb94013e242b7865075c5bd9ebf1b6865","src/external_trait_impls/rayon/set.rs":"7539348ff7bc6e3cce6b3c019d62dc401eea0138c578fef729c2593e8ead1cfa","src/external_trait_impls/rayon/table.rs":"aebd92261f44aef2e4c13a80a566e0308655396a3cc6f973d330d2f5ba26fc45","src/external_trait_impls/serde.rs":"6dbe104dee16b453b6b048b541c6e02c6d067d970dfafd243fc4360288b0168c","src/lib.rs":"88334b30ce84e9efd572e9de11502d54fc79487d7686e216b0d9dfd666f05664","src/macros.rs":"98a26b908fc0fbe6a58d008a317e550013d615eb3cc17a5054a573c62c1d74cb","src/map.rs":"f7f86560e5c584268f59c50744aec74de9734a83167fbf873135f94efaaf37ee","src/raw/alloc.rs":"902f8588d0fdee3e5c3dc02410f41d4b38ac88843727387f929f3186b3a2d322","src/raw/mod.rs":"f23b52c26abd9df5da85a4631e422b3d1bbfa93798717bf65a72a8d8659f24ea","src/raw_entry.rs":"41f54fabf968b6ba19a6fbb41372f7e86e1ccd221622591816fe48bcc3797369","src/rustc_entry.rs":"b0e6b20d93fa79edb2950ecdffc1431f43a6819a326fe08891cc7bfc6cd73bd2","src/scopeguard.rs":"1a246e08a63c06cd8ad934bd7da229421bf804f991ae93cd7e242da27ca6c601","src/set.rs":"bab55589003d948b03f18119f11c8dbfc8851a59248f9b06e52f76a345740f85","src/table.rs":"85043980c76999eb2f6156ae7ecfe1eb1ba929515428dc7a3c444349acb09893","src/util.rs":"8fa74d2e0da6199e693b1b2d68aba6d80bff60dd599d51bef2dcd8ea77b1ffff","tests/equivalent_trait.rs":"84faa3fe9d67c375d03fec81f0f1412c47862477d42e84e7d235258236338d5b","tests/hasher.rs":"fd06130f011660743202904221f3f7487d8d143d8903c73cd3a76d079ebbe9fb","tests/rayon.rs":"39cb24ab45fce8087bb54948715c8b6973ebfba1a325292b5b3cd9aab50b5fd2","tests/serde.rs":"6bac8054db722dd049901b37a6e006535bac30f425eb5cd91af19b5bc1dfe78e","tests/set.rs":"9f8011c29d1059aadb54b6dd4623521d5178b4278b4a56021ef2cee4bbb19fd9"},"package":"bf151400ff0baff5465007dd2f3e717f3fe502074ca563069ce3a6629d07b289"} -\ No newline at end of file +{"files":{"CHANGELOG.md":"9994221204ce09d00472ac0fdc474114b38a51cd784189ef809b142e205fba24","Cargo.lock":"eb6d994edae20531c02356cd9847105a7d82332c01f28c74a4422e12c8adeb3a","Cargo.toml":"2717eef250ccf3312ecc26e608ecc3b0290dd102442777eeb441fdbcb781be5e","Cross.toml":"47aeebdfd782a5052346ce29bf750c225828e108aca723486c3839adba5d6901","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ff8f68cb076caf8cefe7a6430d4ac086ce6af2ca8ce2c4e5a2004d4552ef52a2","README.md":"34a16e7bc599e9d4ec600b477176a4a1328e6fb1f3f8d1525fb54f398553daef","benches/bench.rs":"288e88b0e3021a781a0b49a2a8ca4c390b76a63fd05cd7b524b64a7e988b841a","benches/insert_unique_unchecked.rs":"dfe644035cad6ff13b280e3d72c9df2569491ecddc84f7c2502daf940814a63e","benches/set_ops.rs":"936cd15055c25d42aabc6bde738e3135da541520b40633c4fba940eb73e06f4d","clippy.toml":"7535949f908c6d9aea4f9a9f3a7625552c93fc29e963d059d40f4def9d77ea7b","src/control/bitmask.rs":"53dcdac056620f02c475b618d33e69f34152ea559d86bd4545546144f017baa0","src/control/group/generic.rs":"939b2e35e6ea5430a606a054ffc8ea3e22b867d83f2afed15525cf59a617eb6e","src/control/group/lsx.rs":"99c308a2e07133dce18b88230fbb054d5d1edcf465b87ee9fb1f409eacc4f241","src/control/group/mod.rs":"03d5cacaf762fcb0c9878e9f56355c7c9d0935d688d01c5e0d12aa673e16795d","src/control/group/neon.rs":"bde7726d321bd036cb9001818f962784346b932087b9f655c85ab26667d55fbb","src/control/group/sse2.rs":"833da90ab3fd72d306d5b999de96a4b6b52aa1a16ee7273c89bd12c9ead3bc45","src/control/mod.rs":"83fede19e9c5a26fd2c7372e6cf92547d32ade4cd69fde8a0eaaeb1be6ddc2ba","src/control/tag.rs":"9c94ab42aad3918bd77ffafdeb253f7f773a8f98bf56e36b85ebdc7a11ef676b","src/external_trait_impls/mod.rs":"d69528827794524cfd9acbeacc1ac4f6131e3c7574311e6d919f818f65fbff07","src/external_trait_impls/rayon/helpers.rs":"ba105bf0853ebc45157f22116ad0f55d3bdab75e721d8e7a677c7b912d0c0c6d","src/external_trait_impls/rayon/map.rs":"e1e08653c6c3d2f0586638ab7baf082c06fdc5551b5852b0f9e73aa9484b4955","src/external_trait_impls/rayon/mod.rs":"126edc882501dddd25e442d9236508b5b386eb8c0a9f5d654f2dd081086c1616","src/external_trait_impls/rayon/raw.rs":"04012fb2e99648819b4bc0044107ed3cb94013e242b7865075c5bd9ebf1b6865","src/external_trait_impls/rayon/set.rs":"7539348ff7bc6e3cce6b3c019d62dc401eea0138c578fef729c2593e8ead1cfa","src/external_trait_impls/rayon/table.rs":"aebd92261f44aef2e4c13a80a566e0308655396a3cc6f973d330d2f5ba26fc45","src/external_trait_impls/serde.rs":"f83dae5dd2243c0a1b278f9f040023e98c0e2744c78ad0243a7bb5d877a8e8ee","src/hasher.rs":"939bc4f8c9e2d7e7ace266a8c121360ab4b44ad0540cdee06951e0197d96bc3c","src/lib.rs":"f6b7a5c1a5618bc0ec2ecf17c5c3a29c187f83c4689e9d14261b036a35142920","src/macros.rs":"98a26b908fc0fbe6a58d008a317e550013d615eb3cc17a5054a573c62c1d74cb","src/map.rs":"bf069e9f391abbbfca0918f5798229fd44380afc4f126ce64afd387b5401a8e3","src/raw/alloc.rs":"10474e218b922b0a32227578c09acd5b05c32ad223c4dbf0af3cbd7869c000f2","src/raw/mod.rs":"a88cd291be71cd2f6119a1f8b4030a0429b6b1f8771b7f2a8b140c1824788bed","src/raw_entry.rs":"41f54fabf968b6ba19a6fbb41372f7e86e1ccd221622591816fe48bcc3797369","src/rustc_entry.rs":"9c189a957af1ec5ff3549d15176c1608ca1c68330604a50b2ea19316a5dd14e2","src/scopeguard.rs":"1a246e08a63c06cd8ad934bd7da229421bf804f991ae93cd7e242da27ca6c601","src/set.rs":"cd7d05424d731f0ad5eb4cf255e9a4d970b96fb68398cc904481af942a106fb4","src/table.rs":"285620edfe390d0ea77983ae471943f145ea414caa81926010ef0de4647ef13e","src/util.rs":"c929f855589653727016bd8577db7ca234e7e0820f1f2dc0cfe49f13f5056168","tests/equivalent_trait.rs":"84faa3fe9d67c375d03fec81f0f1412c47862477d42e84e7d235258236338d5b","tests/hasher.rs":"fd06130f011660743202904221f3f7487d8d143d8903c73cd3a76d079ebbe9fb","tests/rayon.rs":"39cb24ab45fce8087bb54948715c8b6973ebfba1a325292b5b3cd9aab50b5fd2","tests/serde.rs":"6bac8054db722dd049901b37a6e006535bac30f425eb5cd91af19b5bc1dfe78e","tests/set.rs":"fd9ffc6f8a435f2fbcada826c33599d682d9f688f0f8dbb14fcd1e442d4c2647"},"package":"5419bdc4f6a9207fbeba6d11b604d481addf78ecd10c11ad51e76c2f6482748d"} +\ No newline at end of file diff --git a/third_party/rust/hashbrown/CHANGELOG.md b/third_party/rust/hashbrown/CHANGELOG.md @@ -1,12 +1,45 @@ -# Change Log +# Changelog All notable changes to this project will be documented in this file. -The format is based on [Keep a Changelog](https://keepachangelog.com/) -and this project adheres to [Semantic Versioning](https://semver.org/). +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). ## [Unreleased] +- Bump foldhash, the default hasher, to 0.2.0. + +## [0.15.5](https://github.com/rust-lang/hashbrown/compare/v0.15.4...v0.15.5) - 2025-08-07 + +### Added + +- Added `Entry::or_default_entry` and `Entry::or_insert_entry`. + +### Changed + +- Re-implemented likely/unlikely with `#[cold]` + +## [0.15.4](https://github.com/rust-lang/hashbrown/compare/v0.15.3...v0.15.4) - 2025-06-05 + +### Changed + +- Removed optional dependency on compiler-builtins. This only affects building as part of `std`. + +## [0.15.3](https://github.com/rust-lang/hashbrown/compare/v0.15.2...v0.15.3) - 2025-04-29 + +### Added + +- SIMD implementation for LoongArch (#592, requires nightly) + +### Changed + +- Optimized insertion path by avoiding an unnecessary `match_empty` (#607) +- Increased minimum table size for small types (#615) +- Dropped FnMut trait bounds from `ExtractIf` data structures (#616) +- Relaxed constraint in `hash_map::EntryRef` insertion methods `K: From<&Q>` to &Q: `Into<K>` (#611) +- Added allocator template argument for `rustc_iter` (#605) +- The `allocator-api2/nightly` feature is no longer enabled by `hashbrown/nightly` (#606) + ## [v0.15.2] - 2024-11-14 ### Added diff --git a/third_party/rust/hashbrown/Cargo.lock b/third_party/rust/hashbrown/Cargo.lock @@ -4,36 +4,30 @@ version = 3 [[package]] name = "allocator-api2" -version = "0.2.16" +version = "0.2.21" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "0942ffc6dcaadf03badf6e6a2d0228460359d5e34b57ccdc720b7382dfbd5ec5" +checksum = "683d7910e743518b0e34f1186f92494becacb047c7b6bf616c96772180fef923" [[package]] name = "bumpalo" -version = "3.15.3" +version = "3.19.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "8ea184aa71bb362a1157c896979544cc23974e08fd265f29ea96b59f0b4a555b" +checksum = "46c5e41b57b8bba42a04676d81cb89e9ee8e859a1a66f80a5a72e1cb76b34d43" dependencies = [ "allocator-api2", ] [[package]] name = "cfg-if" -version = "1.0.0" +version = "1.0.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" - -[[package]] -name = "compiler_builtins" -version = "0.1.108" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d68bc55329711cd719c2687bb147bc06211b0521f97ef398280108ccb23227e9" +checksum = "2fd1289c04a9ea8cb22300a459a72a385d7c73d3259e2ed7dcb2af674838cfa9" [[package]] name = "crossbeam-deque" -version = "0.8.5" +version = "0.8.6" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "613f8cc01fe9cf1a3eb3d7f488fd2fa8388403e97039e2f73692932e291a770d" +checksum = "9dd111b7b7f7d55b72c0a6ae361660ee5853c9af73f70c3c2ef6858b950e2e51" dependencies = [ "crossbeam-epoch", "crossbeam-utils", @@ -50,9 +44,9 @@ dependencies = [ [[package]] name = "crossbeam-utils" -version = "0.8.19" +version = "0.8.21" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "248e3bacc7dc6baa3b21e405ee045c3047101a49145e7e9eca583ab4c2ca5345" +checksum = "d0a5c400df2834b80a4c3327b3aad3a4c4cd4de0629063962b03235697506a28" [[package]] name = "doc-comment" @@ -62,15 +56,15 @@ checksum = "fea41bba32d969b513997752735605054bc0dfa92b4c56bf1189f2e174be7a10" [[package]] name = "either" -version = "1.10.0" +version = "1.15.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "11157ac094ffbdde99aa67b23417ebdd801842852b500e395a45a9c0aac03e4a" +checksum = "48c757948c5ede0e46177b7add2e67155f70e33c07fea8284df6576da70b3719" [[package]] name = "equivalent" -version = "1.0.1" +version = "1.0.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5" +checksum = "877a4ace8713b0bcf2a4e7eec82529c029f1d0619886d18145fea96c3ffe5c0f" [[package]] name = "fnv" @@ -80,28 +74,28 @@ checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1" [[package]] name = "foldhash" -version = "0.1.2" +version = "0.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "33d5ac82bdbbd872ce0dfea4e848a678cfcfdc0d210a5b20549b8c659fec0392" +checksum = "77ce24cb58228fbb8aa041425bb1050850ac19177686ea6e0f41a70416f56fdb" [[package]] name = "getrandom" -version = "0.2.12" +version = "0.3.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "190092ea657667030ac6a35e305e62fc4dd69fd98ac98631e5d3a2b1575a12b5" +checksum = "26145e563e54f2cadc477553f1ec5ee650b00862f0a58bcd12cbdc5f0ea2d2f4" dependencies = [ "cfg-if", "libc", + "r-efi", "wasi", ] [[package]] name = "hashbrown" -version = "0.15.2" +version = "0.16.0" dependencies = [ "allocator-api2", "bumpalo", - "compiler_builtins", "doc-comment", "equivalent", "fnv", @@ -117,56 +111,64 @@ dependencies = [ [[package]] name = "lazy_static" -version = "1.4.0" +version = "1.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" +checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe" [[package]] name = "libc" -version = "0.2.153" +version = "0.2.175" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9c198f91728a82281a64e1f4f9eeb25d82cb32a5de251c6bd1b5154d63a8e7bd" +checksum = "6a82ae493e598baaea5209805c49bbf2ea7de956d50d7da0da1164f9c6d28543" [[package]] name = "ppv-lite86" -version = "0.2.17" +version = "0.2.21" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de" +checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9" +dependencies = [ + "zerocopy", +] [[package]] name = "proc-macro2" -version = "1.0.78" +version = "1.0.101" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e2422ad645d89c99f8f3e6b88a9fdeca7fabeac836b1002371c4367c8f984aae" +checksum = "89ae43fd86e4158d6db51ad8e2b80f313af9cc74f5c0e03ccb87de09998732de" dependencies = [ "unicode-ident", ] [[package]] name = "quote" -version = "1.0.35" +version = "1.0.40" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef" +checksum = "1885c039570dc00dcb4ff087a89e185fd56bae234ddc7f056a945bf36467248d" dependencies = [ "proc-macro2", ] [[package]] +name = "r-efi" +version = "5.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "69cdb34c158ceb288df11e18b4bd39de994f6657d83847bdffdbd7f346754b0f" + +[[package]] name = "rand" -version = "0.8.5" +version = "0.9.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +checksum = "6db2770f06117d490610c7488547d543617b21bfa07796d7a12f6f1bd53850d1" dependencies = [ - "libc", "rand_chacha", "rand_core", ] [[package]] name = "rand_chacha" -version = "0.3.1" +version = "0.9.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +checksum = "d3022b5f1df60f26e1ffddd6c66e8aa15de382ae63b3a0c1bfc0e4d3e3f325cb" dependencies = [ "ppv-lite86", "rand_core", @@ -174,18 +176,18 @@ dependencies = [ [[package]] name = "rand_core" -version = "0.6.4" +version = "0.9.3" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" +checksum = "99d9a13982dcf210057a8a78572b2217b667c3beacbf3a0d8b454f6f82837d38" dependencies = [ "getrandom", ] [[package]] name = "rayon" -version = "1.9.0" +version = "1.11.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "e4963ed1bc86e4f3ee217022bd855b297cef07fb9eac5dfa1f788b220b49b3bd" +checksum = "368f01d005bf8fd9b1206fb6fa653e6c4a81ceb1466406b81792d87c5677a58f" dependencies = [ "either", "rayon-core", @@ -193,9 +195,9 @@ dependencies = [ [[package]] name = "rayon-core" -version = "1.12.1" +version = "1.13.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1465873a3dfdaa8ae7cb14b4383657caab0b3e8a0aa9ae8e04b044854c8dfce2" +checksum = "22e18b0f0062d30d4230b2e85ff77fdfe4326feb054b9783a3460d8435c8ab91" dependencies = [ "crossbeam-deque", "crossbeam-utils", @@ -203,30 +205,30 @@ dependencies = [ [[package]] name = "rustc-std-workspace-alloc" -version = "1.0.0" +version = "1.0.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ff66d57013a5686e1917ed6a025d54dd591fcda71a41fe07edf4d16726aefa86" +checksum = "f9d441c3b2ebf55cebf796bfdc265d67fa09db17b7bb6bd4be75c509e1e8fec3" [[package]] name = "rustc-std-workspace-core" -version = "1.0.0" +version = "1.0.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1956f5517128a2b6f23ab2dadf1a976f4f5b27962e7724c2bf3d45e539ec098c" +checksum = "aa9c45b374136f52f2d6311062c7146bff20fec063c3f5d46a410bd937746955" [[package]] name = "serde" -version = "1.0.197" +version = "1.0.219" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "3fb1c873e1b9b056a4dc4c0c198b24c3ffa059243875552b2bd0933b1aee4ce2" +checksum = "5f0e2c6ed6606019b4e29e69dbaba95b11854410e5347d525002456dbbb786b6" dependencies = [ "serde_derive", ] [[package]] name = "serde_derive" -version = "1.0.197" +version = "1.0.219" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "7eb0b34b42edc17f6b7cac84a52a1c5f0e1bb2227e997ca9011ea3dd34e8610b" +checksum = "5b0276cf7f2c73365f7157c8123c21cd9a50fbbd844757af28ca1f5925fc2a00" dependencies = [ "proc-macro2", "quote", @@ -235,18 +237,18 @@ dependencies = [ [[package]] name = "serde_test" -version = "1.0.176" +version = "1.0.177" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5a2f49ace1498612d14f7e0b8245519584db8299541dfe31a06374a828d620ab" +checksum = "7f901ee573cab6b3060453d2d5f0bae4e6d628c23c0a962ff9b5f1d7c8d4f1ed" dependencies = [ "serde", ] [[package]] name = "syn" -version = "2.0.52" +version = "2.0.106" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "b699d15b36d1f02c3e7c69f8ffef53de37aefae075d8488d4ba1a7788d574a07" +checksum = "ede7c438028d4436d71104916910f5bb611972c5cfd7f89b8300a8186e6fada6" dependencies = [ "proc-macro2", "quote", @@ -255,12 +257,41 @@ dependencies = [ [[package]] name = "unicode-ident" -version = "1.0.12" +version = "1.0.18" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" +checksum = "5a5f39404a5da50712a4c1eecf25e90dd62b613502b7e925fd4e4d19b5c96512" [[package]] name = "wasi" -version = "0.11.0+wasi-snapshot-preview1" +version = "0.14.3+wasi-0.2.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" +checksum = "6a51ae83037bdd272a9e28ce236db8c07016dd0d50c27038b3f407533c030c95" +dependencies = [ + "wit-bindgen", +] + +[[package]] +name = "wit-bindgen" +version = "0.45.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "052283831dbae3d879dc7f51f3d92703a316ca49f91540417d38591826127814" + +[[package]] +name = "zerocopy" +version = "0.8.26" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1039dd0d3c310cf05de012d8a39ff557cb0d23087fd44cad61df08fc31907a2f" +dependencies = [ + "zerocopy-derive", +] + +[[package]] +name = "zerocopy-derive" +version = "0.8.26" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9ecf5b4cc5364572d7f4c329661bcc82724222973f2cab6f050a4e5c22f75181" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] diff --git a/third_party/rust/hashbrown/Cargo.toml b/third_party/rust/hashbrown/Cargo.toml @@ -13,7 +13,7 @@ edition = "2021" rust-version = "1.65.0" name = "hashbrown" -version = "0.15.2" +version = "0.16.0" authors = ["Amanieu d'Antras <amanieu@gmail.com>"] build = false exclude = [ @@ -49,6 +49,29 @@ features = [ ] rustdoc-args = ["--generate-link-to-definition"] +[features] +default = [ + "default-hasher", + "inline-more", + "allocator-api2", + "equivalent", + "raw-entry", +] +default-hasher = ["dep:foldhash"] +inline-more = [] +nightly = [ + "foldhash?/nightly", + "bumpalo/allocator_api", +] +raw-entry = [] +rustc-dep-of-std = [ + "nightly", + "core", + "alloc", + "rustc-internal-api", +] +rustc-internal-api = [] + [lib] name = "hashbrown" path = "src/lib.rs" @@ -96,10 +119,6 @@ features = ["alloc"] optional = true default-features = false -[dependencies.compiler_builtins] -version = "0.1.2" -optional = true - [dependencies.core] version = "1.0.0" optional = true @@ -111,7 +130,7 @@ optional = true default-features = false [dependencies.foldhash] -version = "0.1.2" +version = "0.2.0" optional = true default-features = false @@ -138,7 +157,7 @@ version = "1.0.7" version = "1.4" [dev-dependencies.rand] -version = "0.8.3" +version = "0.9.0" features = ["small_rng"] [dev-dependencies.rayon] @@ -146,28 +165,3 @@ version = "1.2" [dev-dependencies.serde_test] version = "1.0" - -[features] -default = [ - "default-hasher", - "inline-more", - "allocator-api2", - "equivalent", - "raw-entry", -] -default-hasher = ["dep:foldhash"] -inline-more = [] -nightly = [ - "allocator-api2?/nightly", - "bumpalo/allocator_api", -] -raw-entry = [] -rustc-dep-of-std = [ - "nightly", - "core", - "compiler_builtins", - "alloc", - "rustc-internal-api", - "raw-entry", -] -rustc-internal-api = [] diff --git a/third_party/rust/hashbrown/Cross.toml b/third_party/rust/hashbrown/Cross.toml @@ -0,0 +1,3 @@ +# FIXME: Drop this config when cross is updated to support loongarch64-linux-gnu +[target.loongarch64-unknown-linux-gnu] +image = "ghcr.io/cross-rs/loongarch64-unknown-linux-gnu:edge" diff --git a/third_party/rust/hashbrown/README.md b/third_party/rust/hashbrown/README.md @@ -4,7 +4,7 @@ hashbrown [](https://github.com/rust-lang/hashbrown/actions) [](https://crates.io/crates/hashbrown) [](https://docs.rs/hashbrown) -[](https://github.com/rust-lang/hashbrown) +[](https://github.com/rust-lang/hashbrown) This crate is a Rust port of Google's high-performance [SwissTable] hash map, adapted to make it a drop-in replacement for Rust's standard `HashMap` diff --git a/third_party/rust/hashbrown/benches/bench.rs b/third_party/rust/hashbrown/benches/bench.rs @@ -16,6 +16,7 @@ use std::{ }; const SIZE: usize = 1000; +const OP_COUNT: usize = 500; // The default hashmap when using this crate directly. type FoldHashMap<K, V> = HashMap<K, V, DefaultHashBuilder>; @@ -45,9 +46,7 @@ impl Iterator for RandomKeys { // Just an arbitrary side effect to make the maps not shortcircuit to the non-dropping path // when dropping maps/entries (most real world usages likely have drop in the key or value) -lazy_static::lazy_static! { - static ref SIDE_EFFECT: AtomicUsize = AtomicUsize::new(0); -} +static SIDE_EFFECT: AtomicUsize = AtomicUsize::new(0); #[derive(Clone)] struct DropType(usize); @@ -78,6 +77,22 @@ macro_rules! bench_suite { }; } +macro_rules! bench_suite_2 { + ($bench_macro:ident, + $name0:ident, $size0:literal, $name1:ident, $size1:literal, $name2:ident, $size2:literal, + $name3:ident, $size3:literal, $name4:ident, $size4:literal, $name5:ident, $size5:literal, + $name6:ident, $size6:literal, $name7:ident, $size7:literal) => { + $bench_macro!($name0, $size0, FoldHashMap, RandomKeys::new()); + $bench_macro!($name1, $size1, FoldHashMap, RandomKeys::new()); + $bench_macro!($name2, $size2, FoldHashMap, RandomKeys::new()); + $bench_macro!($name3, $size3, FoldHashMap, RandomKeys::new()); + $bench_macro!($name4, $size4, FoldHashMap, RandomKeys::new()); + $bench_macro!($name5, $size5, FoldHashMap, RandomKeys::new()); + $bench_macro!($name6, $size6, FoldHashMap, RandomKeys::new()); + $bench_macro!($name7, $size7, FoldHashMap, RandomKeys::new()); + }; +} + macro_rules! bench_insert { ($name:ident, $maptype:ident, $keydist:expr) => { #[bench] @@ -224,6 +239,83 @@ bench_suite!( lookup_fail_std_random ); +macro_rules! bench_lookup_load_factor { + ($name:ident, $size:literal, $maptype:ident, $keydist:expr) => { + #[bench] + fn $name(b: &mut Bencher) { + let mut m = $maptype::default(); + for i in $keydist.take($size) { + m.insert(i, DropType(i)); + } + + b.iter(|| { + for i in $keydist.take(OP_COUNT) { + black_box(m.get(&i)); + } + }); + } + }; +} + +bench_suite_2!( + bench_lookup_load_factor, // same capacity of 32768 * 0.875 + loadfactor_lookup_14500, + 14500, + loadfactor_lookup_16500, + 16500, + loadfactor_lookup_18500, + 18500, + loadfactor_lookup_20500, + 20500, + loadfactor_lookup_22500, + 22500, + loadfactor_lookup_24500, + 24500, + loadfactor_lookup_26500, + 26500, + loadfactor_lookup_28500, + 28500 +); + +macro_rules! bench_lookup_fail_load_factor { + ($name:ident, $size:literal, $maptype:ident, $keydist:expr) => { + #[bench] + fn $name(b: &mut Bencher) { + let mut m = $maptype::default(); + let mut iter = $keydist; + for i in (&mut iter).take($size) { + m.insert(i, DropType(i)); + } + + b.iter(|| { + for i in (&mut iter).take(OP_COUNT) { + black_box(m.get(&i)); + } + }) + } + }; +} + +bench_suite_2!( + bench_lookup_fail_load_factor, // same capacity of 32768 * 0.875 + loadfactor_lookup_fail_14500, + 14500, + loadfactor_lookup_fail_16500, + 16500, + loadfactor_lookup_fail_18500, + 18500, + loadfactor_lookup_fail_20500, + 20500, + loadfactor_lookup_fail_22500, + 22500, + loadfactor_lookup_fail_24500, + 24500, + loadfactor_lookup_fail_26500, + 26500, + loadfactor_lookup_fail_28500, + 28500 +); + macro_rules! bench_iter { ($name:ident, $maptype:ident, $keydist:expr) => { #[bench] diff --git a/third_party/rust/hashbrown/src/control/group/lsx.rs b/third_party/rust/hashbrown/src/control/group/lsx.rs @@ -0,0 +1,128 @@ +use super::super::{BitMask, Tag}; +use core::mem; +use core::num::NonZeroU16; + +use core::arch::loongarch64::*; + +pub(crate) type BitMaskWord = u16; +pub(crate) type NonZeroBitMaskWord = NonZeroU16; +pub(crate) const BITMASK_STRIDE: usize = 1; +pub(crate) const BITMASK_MASK: BitMaskWord = 0xffff; +pub(crate) const BITMASK_ITER_MASK: BitMaskWord = !0; + +/// Abstraction over a group of control tags which can be scanned in +/// parallel. +/// +/// This implementation uses a 128-bit LSX value. +#[derive(Copy, Clone)] +pub(crate) struct Group(m128i); + +// FIXME: https://github.com/rust-lang/rust-clippy/issues/3859 +#[allow(clippy::use_self)] +impl Group { + /// Number of bytes in the group. + pub(crate) const WIDTH: usize = mem::size_of::<Self>(); + + /// Returns a full group of empty tags, suitable for use as the initial + /// value for an empty hash table. + /// + /// This is guaranteed to be aligned to the group size. + #[inline] + #[allow(clippy::items_after_statements)] + pub(crate) const fn static_empty() -> &'static [Tag; Group::WIDTH] { + #[repr(C)] + struct AlignedTags { + _align: [Group; 0], + tags: [Tag; Group::WIDTH], + } + const ALIGNED_TAGS: AlignedTags = AlignedTags { + _align: [], + tags: [Tag::EMPTY; Group::WIDTH], + }; + &ALIGNED_TAGS.tags + } + + /// Loads a group of tags starting at the given address. + #[inline] + #[allow(clippy::cast_ptr_alignment)] // unaligned load + pub(crate) unsafe fn load(ptr: *const Tag) -> Self { + Group(lsx_vld::<0>(ptr.cast())) + } + + /// Loads a group of tags starting at the given address, which must be + /// aligned to `mem::align_of::<Group>()`. + #[inline] + #[allow(clippy::cast_ptr_alignment)] + pub(crate) unsafe fn load_aligned(ptr: *const Tag) -> Self { + debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0); + Group(lsx_vld::<0>(ptr.cast())) + } + + /// Stores the group of tags to the given address, which must be + /// aligned to `mem::align_of::<Group>()`. + #[inline] + #[allow(clippy::cast_ptr_alignment)] + pub(crate) unsafe fn store_aligned(self, ptr: *mut Tag) { + debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0); + lsx_vst::<0>(self.0, ptr.cast()); + } + + /// Returns a `BitMask` indicating all tags in the group which have + /// the given value. + #[inline] + pub(crate) fn match_tag(self, tag: Tag) -> BitMask { + unsafe { + let cmp = lsx_vseq_b(self.0, lsx_vreplgr2vr_b(tag.0 as i32)); + BitMask(lsx_vpickve2gr_hu::<0>(lsx_vmskltz_b(cmp)) as u16) + } + } + + /// Returns a `BitMask` indicating all tags in the group which are + /// `EMPTY`. + #[inline] + pub(crate) fn match_empty(self) -> BitMask { + unsafe { + let cmp = lsx_vseqi_b::<{ Tag::EMPTY.0 as i8 as i32 }>(self.0); + BitMask(lsx_vpickve2gr_hu::<0>(lsx_vmskltz_b(cmp)) as u16) + } + } + + /// Returns a `BitMask` indicating all tags in the group which are + /// `EMPTY` or `DELETED`. + #[inline] + pub(crate) fn match_empty_or_deleted(self) -> BitMask { + unsafe { + // A tag is EMPTY or DELETED iff the high bit is set + BitMask(lsx_vpickve2gr_hu::<0>(lsx_vmskltz_b(self.0)) as u16) + } + } + + /// Returns a `BitMask` indicating all tags in the group which are full. + #[inline] + pub(crate) fn match_full(&self) -> BitMask { + unsafe { + // A tag is EMPTY or DELETED iff the high bit is set + BitMask(lsx_vpickve2gr_hu::<0>(lsx_vmskgez_b(self.0)) as u16) + } + } + + /// Performs the following transformation on all tags in the group: + /// - `EMPTY => EMPTY` + /// - `DELETED => EMPTY` + /// - `FULL => DELETED` + #[inline] + pub(crate) fn convert_special_to_empty_and_full_to_deleted(self) -> Self { + // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111 + // and high_bit = 0 (FULL) to 1000_0000 + // + // Here's this logic expanded to concrete values: + // let special = 0 > tag = 1111_1111 (true) or 0000_0000 (false) + // 1111_1111 | 1000_0000 = 1111_1111 + // 0000_0000 | 1000_0000 = 1000_0000 + unsafe { + let zero = lsx_vreplgr2vr_b(0); + let special = lsx_vslt_b(self.0, zero); + Group(lsx_vor_v(special, lsx_vreplgr2vr_b(Tag::DELETED.0 as i32))) + } + } +} diff --git a/third_party/rust/hashbrown/src/control/group/mod.rs b/third_party/rust/hashbrown/src/control/group/mod.rs @@ -24,6 +24,14 @@ cfg_if! { ))] { mod neon; use neon as imp; + } else if #[cfg(all( + feature = "nightly", + target_arch = "loongarch64", + target_feature = "lsx", + not(miri), + ))] { + mod lsx; + use lsx as imp; } else { mod generic; use generic as imp; diff --git a/third_party/rust/hashbrown/src/external_trait_impls/serde.rs b/third_party/rust/hashbrown/src/external_trait_impls/serde.rs @@ -186,7 +186,7 @@ mod set { where A: Allocator; - impl<'a, 'de, T, S, A> Visitor<'de> for SeqInPlaceVisitor<'a, T, S, A> + impl<'de, T, S, A> Visitor<'de> for SeqInPlaceVisitor<'_, T, S, A> where T: Deserialize<'de> + Eq + Hash, S: BuildHasher + Default, diff --git a/third_party/rust/hashbrown/src/hasher.rs b/third_party/rust/hashbrown/src/hasher.rs @@ -0,0 +1,77 @@ +#[cfg(feature = "default-hasher")] +use { + core::hash::{BuildHasher, Hasher}, + foldhash::fast::RandomState, +}; + +/// Default hash builder for the `S` type parameter of +/// [`HashMap`](crate::HashMap) and [`HashSet`](crate::HashSet). +/// +/// This only implements `BuildHasher` when the "default-hasher" crate feature +/// is enabled; otherwise it just serves as a placeholder, and a custom `S` type +/// must be used to have a fully functional `HashMap` or `HashSet`. +#[derive(Clone, Debug, Default)] +pub struct DefaultHashBuilder { + #[cfg(feature = "default-hasher")] + inner: RandomState, +} + +#[cfg(feature = "default-hasher")] +impl BuildHasher for DefaultHashBuilder { + type Hasher = DefaultHasher; + + #[inline(always)] + fn build_hasher(&self) -> Self::Hasher { + DefaultHasher { + inner: self.inner.build_hasher(), + } + } +} + +/// Default hasher for [`HashMap`](crate::HashMap) and [`HashSet`](crate::HashSet). +#[cfg(feature = "default-hasher")] +#[derive(Clone)] +pub struct DefaultHasher { + inner: <RandomState as BuildHasher>::Hasher, +} + +#[cfg(feature = "default-hasher")] +macro_rules! forward_writes { + ($( $write:ident ( $ty:ty ) , )*) => {$( + #[inline(always)] + fn $write(&mut self, arg: $ty) { + self.inner.$write(arg); + } + )*} +} + +#[cfg(feature = "default-hasher")] +impl Hasher for DefaultHasher { + forward_writes! { + write(&[u8]), + write_u8(u8), + write_u16(u16), + write_u32(u32), + write_u64(u64), + write_u128(u128), + write_usize(usize), + write_i8(i8), + write_i16(i16), + write_i32(i32), + write_i64(i64), + write_i128(i128), + write_isize(isize), + } + + // feature(hasher_prefixfree_extras) + #[cfg(feature = "nightly")] + forward_writes! { + write_length_prefix(usize), + write_str(&str), + } + + #[inline(always)] + fn finish(&self) -> u64 { + self.inner.finish() + } +} diff --git a/third_party/rust/hashbrown/src/lib.rs b/third_party/rust/hashbrown/src/lib.rs @@ -38,15 +38,18 @@ #![warn(missing_docs)] #![warn(rust_2018_idioms)] #![cfg_attr(feature = "nightly", warn(fuzzy_provenance_casts))] -#![cfg_attr(feature = "nightly", allow(internal_features))] - -/// Default hasher for [`HashMap`] and [`HashSet`]. -#[cfg(feature = "default-hasher")] -pub type DefaultHashBuilder = foldhash::fast::RandomState; - -/// Dummy default hasher for [`HashMap`] and [`HashSet`]. -#[cfg(not(feature = "default-hasher"))] -pub enum DefaultHashBuilder {} +#![cfg_attr( + feature = "nightly", + allow(clippy::incompatible_msrv, internal_features) +)] +#![cfg_attr( + all(feature = "nightly", target_arch = "loongarch64"), + feature(stdarch_loongarch) +)] +#![cfg_attr( + all(feature = "nightly", feature = "default-hasher"), + feature(hasher_prefixfree_extras) +)] #[cfg(test)] #[macro_use] @@ -64,6 +67,7 @@ doc_comment::doctest!("../README.md"); mod macros; mod control; +mod hasher; mod raw; mod util; @@ -77,6 +81,10 @@ mod scopeguard; mod set; mod table; +pub use crate::hasher::DefaultHashBuilder; +#[cfg(feature = "default-hasher")] +pub use crate::hasher::DefaultHasher; + pub mod hash_map { //! A hash map implemented with quadratic probing and SIMD lookup. pub use crate::map::*; diff --git a/third_party/rust/hashbrown/src/map.rs b/third_party/rust/hashbrown/src/map.rs @@ -1306,9 +1306,14 @@ where Q: Hash + Equivalent<K> + ?Sized, { // Avoid `Option::map` because it bloats LLVM IR. - match self.get_inner(k) { - Some((_, v)) => Some(v), - None => None, + if !self.table.is_empty() { + let hash = make_hash::<Q, S>(&self.hash_builder, k); + match self.table.get(hash, equivalent_key(k)) { + Some((_, v)) => Some(v), + None => None, + } + } else { + None } } @@ -1337,22 +1342,14 @@ where Q: Hash + Equivalent<K> + ?Sized, { // Avoid `Option::map` because it bloats LLVM IR. - match self.get_inner(k) { - Some((key, value)) => Some((key, value)), - None => None, - } - } - - #[inline] - fn get_inner<Q>(&self, k: &Q) -> Option<&(K, V)> - where - Q: Hash + Equivalent<K> + ?Sized, - { - if self.table.is_empty() { - None - } else { + if !self.table.is_empty() { let hash = make_hash::<Q, S>(&self.hash_builder, k); - self.table.get(hash, equivalent_key(k)) + match self.table.get(hash, equivalent_key(k)) { + Some((key, value)) => Some((key, value)), + None => None, + } + } else { + None } } @@ -1385,9 +1382,14 @@ where Q: Hash + Equivalent<K> + ?Sized, { // Avoid `Option::map` because it bloats LLVM IR. - match self.get_inner_mut(k) { - Some(&mut (ref key, ref mut value)) => Some((key, value)), - None => None, + if !self.table.is_empty() { + let hash = make_hash::<Q, S>(&self.hash_builder, k); + match self.table.get_mut(hash, equivalent_key(k)) { + Some(&mut (ref key, ref mut value)) => Some((key, value)), + None => None, + } + } else { + None } } @@ -1415,7 +1417,12 @@ where where Q: Hash + Equivalent<K> + ?Sized, { - self.get_inner(k).is_some() + if !self.table.is_empty() { + let hash = make_hash::<Q, S>(&self.hash_builder, k); + self.table.get(hash, equivalent_key(k)).is_some() + } else { + false + } } /// Returns a mutable reference to the value corresponding to the key. @@ -1447,22 +1454,14 @@ where Q: Hash + Equivalent<K> + ?Sized, { // Avoid `Option::map` because it bloats LLVM IR. - match self.get_inner_mut(k) { - Some(&mut (_, ref mut v)) => Some(v), - None => None, - } - } - - #[inline] - fn get_inner_mut<Q>(&mut self, k: &Q) -> Option<&mut (K, V)> - where - Q: Hash + Equivalent<K> + ?Sized, - { - if self.table.is_empty() { - None - } else { + if !self.table.is_empty() { let hash = make_hash::<Q, S>(&self.hash_builder, k); - self.table.get_mut(hash, equivalent_key(k)) + match self.table.get_mut(hash, equivalent_key(k)) { + Some(&mut (_, ref mut v)) => Some(v), + None => None, + } + } else { + None } } @@ -2596,10 +2595,7 @@ impl<K, V, A: Allocator> Drain<'_, K, V, A> { /// assert_eq!(map.len(), 1); /// ``` #[must_use = "Iterators are lazy unless consumed"] -pub struct ExtractIf<'a, K, V, F, A: Allocator = Global> -where - F: FnMut(&K, &mut V) -> bool, -{ +pub struct ExtractIf<'a, K, V, F, A: Allocator = Global> { f: F, inner: RawExtractIf<'a, (K, V), A>, } @@ -3527,6 +3523,38 @@ impl<'a, K, V, S, A: Allocator> Entry<'a, K, V, S, A> { } } + /// Ensures a value is in the entry by inserting the default if empty, + /// and returns an [`OccupiedEntry`]. + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashMap; + /// + /// let mut map: HashMap<&str, u32> = HashMap::new(); + /// + /// // nonexistent key + /// let entry = map.entry("poneyland").or_insert_entry(3); + /// assert_eq!(entry.key(), &"poneyland"); + /// assert_eq!(entry.get(), &3); + /// + /// // existing key + /// let mut entry = map.entry("poneyland").or_insert_entry(10); + /// assert_eq!(entry.key(), &"poneyland"); + /// assert_eq!(entry.get(), &3); + /// ``` + #[cfg_attr(feature = "inline-more", inline)] + pub fn or_insert_entry(self, default: V) -> OccupiedEntry<'a, K, V, S, A> + where + K: Hash, + S: BuildHasher, + { + match self { + Entry::Occupied(entry) => entry, + Entry::Vacant(entry) => entry.insert_entry(default), + } + } + /// Ensures a value is in the entry by inserting the result of the default function if empty, /// and returns a mutable reference to the value in the entry. /// @@ -4131,7 +4159,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> { #[cfg_attr(feature = "inline-more", inline)] pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S, A> where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { match self { @@ -4164,7 +4193,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> { #[cfg_attr(feature = "inline-more", inline)] pub fn or_insert(self, default: V) -> &'a mut V where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { match self { @@ -4194,7 +4224,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> { #[cfg_attr(feature = "inline-more", inline)] pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { match self { @@ -4225,7 +4256,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> { #[cfg_attr(feature = "inline-more", inline)] pub fn or_insert_with_key<F: FnOnce(&Q) -> V>(self, default: F) -> &'a mut V where - K: Hash + Borrow<Q> + From<&'b Q>, + K: Hash + Borrow<Q>, + &'b Q: Into<K>, S: BuildHasher, { match self { @@ -4320,7 +4352,8 @@ impl<'a, 'b, K, Q: ?Sized, V: Default, S, A: Allocator> EntryRef<'a, 'b, K, Q, V #[cfg_attr(feature = "inline-more", inline)] pub fn or_default(self) -> &'a mut V where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { match self { @@ -4328,6 +4361,39 @@ impl<'a, 'b, K, Q: ?Sized, V: Default, S, A: Allocator> EntryRef<'a, 'b, K, Q, V EntryRef::Vacant(entry) => entry.insert(Default::default()), } } + + /// Ensures a value is in the entry by inserting the default value if empty, + /// and returns an [`OccupiedEntry`]. + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashMap; + /// + /// let mut map: HashMap<String, Option<u32>> = HashMap::new(); + /// + /// // nonexistent key + /// let entry = map.entry_ref("poneyland").or_default_entry(); + /// assert_eq!(entry.key(), &"poneyland"); + /// assert_eq!(entry.get(), &None); + /// + /// // existing key + /// map.insert("horseland".to_string(), Some(3)); + /// let entry = map.entry_ref("horseland").or_default_entry(); + /// assert_eq!(entry.key(), &"horseland"); + /// assert_eq!(entry.get(), &Some(3)); + /// ``` + #[cfg_attr(feature = "inline-more", inline)] + pub fn or_default_entry(self) -> OccupiedEntry<'a, K, V, S, A> + where + K: Hash + From<&'b Q>, + S: BuildHasher, + { + match self { + EntryRef::Occupied(entry) => entry, + EntryRef::Vacant(entry) => entry.insert_entry(Default::default()), + } + } } impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> VacantEntryRef<'a, 'b, K, Q, V, S, A> { @@ -4368,7 +4434,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> VacantEntryRef<'a, 'b, K, Q, V, S #[cfg_attr(feature = "inline-more", inline)] pub fn insert(self, value: V) -> &'a mut V where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { let table = &mut self.table.table; @@ -4399,7 +4466,8 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> VacantEntryRef<'a, 'b, K, Q, V, S #[cfg_attr(feature = "inline-more", inline)] pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A> where - K: Hash + From<&'b Q>, + K: Hash, + &'b Q: Into<K>, S: BuildHasher, { let elem = self.table.table.insert( @@ -4690,9 +4758,9 @@ mod test_map { use super::Entry::{Occupied, Vacant}; use super::EntryRef; use super::HashMap; + use crate::raw::{AllocError, Allocator, Global}; use alloc::string::{String, ToString}; use alloc::sync::Arc; - use allocator_api2::alloc::{AllocError, Allocator, Global}; use core::alloc::Layout; use core::ptr::NonNull; use core::sync::atomic::{AtomicI8, Ordering}; @@ -5054,6 +5122,10 @@ mod test_map { Some(x) => *x = new, } assert_eq!(m.get(&5), Some(&new)); + let mut hashmap: HashMap<i32, String> = HashMap::default(); + let key = &1; + let result = hashmap.get_mut(key); + assert!(result.is_none()); } #[test] @@ -5446,8 +5518,7 @@ mod test_map { map.insert(2, 1); map.insert(3, 4); - #[allow(clippy::no_effect)] // false positive lint - map[&4]; + _ = map[&4]; } #[test] @@ -6156,7 +6227,7 @@ mod test_map { } for (k, v) in map { - println!("{}, {}", k, v); + println!("{k}, {v}"); } } @@ -6261,8 +6332,7 @@ mod test_map { for ((key, value), (panic_in_clone, panic_in_drop)) in guard.iter().zip(iter) { if *key != check_count { return Err(format!( - "key != check_count,\nkey: `{}`,\ncheck_count: `{}`", - key, check_count + "key != check_count,\nkey: `{key}`,\ncheck_count: `{check_count}`" )); } if value.dropped @@ -6289,8 +6359,7 @@ mod test_map { if count != check_count { return Err(format!( - "count != check_count,\ncount: `{}`,\ncheck_count: `{}`", - count, check_count + "count != check_count,\ncount: `{count}`,\ncheck_count: `{check_count}`" )); } core::mem::forget(guard); diff --git a/third_party/rust/hashbrown/src/raw/alloc.rs b/third_party/rust/hashbrown/src/raw/alloc.rs @@ -1,3 +1,5 @@ +#[cfg(test)] +pub(crate) use self::inner::AllocError; pub(crate) use self::inner::{do_alloc, Allocator, Global}; // Nightly-case. @@ -6,6 +8,8 @@ pub(crate) use self::inner::{do_alloc, Allocator, Global}; // This is used when building for `std`. #[cfg(feature = "nightly")] mod inner { + #[cfg(test)] + pub use crate::alloc::alloc::AllocError; use crate::alloc::alloc::Layout; pub use crate::alloc::alloc::{Allocator, Global}; use core::ptr::NonNull; @@ -28,6 +32,8 @@ mod inner { #[cfg(all(not(feature = "nightly"), feature = "allocator-api2"))] mod inner { use crate::alloc::alloc::Layout; + #[cfg(test)] + pub use allocator_api2::alloc::AllocError; pub use allocator_api2::alloc::{Allocator, Global}; use core::ptr::NonNull; diff --git a/third_party/rust/hashbrown/src/raw/mod.rs b/third_party/rust/hashbrown/src/raw/mod.rs @@ -12,6 +12,8 @@ use core::slice; use core::{hint, ptr}; mod alloc; +#[cfg(test)] +pub(crate) use self::alloc::AllocError; pub(crate) use self::alloc::{do_alloc, Allocator, Global}; #[inline] @@ -98,16 +100,51 @@ impl ProbeSeq { // Workaround for emscripten bug emscripten-core/emscripten-fastcomp#258 #[cfg_attr(target_os = "emscripten", inline(never))] #[cfg_attr(not(target_os = "emscripten"), inline)] -fn capacity_to_buckets(cap: usize) -> Option<usize> { +fn capacity_to_buckets(cap: usize, table_layout: TableLayout) -> Option<usize> { debug_assert_ne!(cap, 0); // For small tables we require at least 1 empty bucket so that lookups are // guaranteed to terminate if an element doesn't exist in the table. - if cap < 8 { + if cap < 15 { + // Consider a small TableLayout like { size: 1, ctrl_align: 16 } on a + // platform with Group::WIDTH of 16 (like x86_64 with SSE2). For small + // bucket sizes, this ends up wasting quite a few bytes just to pad to + // the relatively larger ctrl_align: + // + // | capacity | buckets | bytes allocated | bytes per item | + // | -------- | ------- | --------------- | -------------- | + // | 3 | 4 | 36 | (Yikes!) 12.0 | + // | 7 | 8 | 40 | (Poor) 5.7 | + // | 14 | 16 | 48 | 3.4 | + // | 28 | 32 | 80 | 3.3 | + // + // In general, buckets * table_layout.size >= table_layout.ctrl_align + // must be true to avoid these edges. This is implemented by adjusting + // the minimum capacity upwards for small items. This code only needs + // to handle ctrl_align which are less than or equal to Group::WIDTH, + // because valid layout sizes are always a multiple of the alignment, + // so anything with alignment over the Group::WIDTH won't hit this edge + // case. + + // This is brittle, e.g. if we ever add 32 byte groups, it will select + // 3 regardless of the table_layout.size. + let min_cap = match (Group::WIDTH, table_layout.size) { + (16, 0..=1) => 14, + (16, 2..=3) => 7, + (8, 0..=1) => 7, + _ => 3, + }; + let cap = min_cap.max(cap); // We don't bother with a table size of 2 buckets since that can only - // hold a single element. Instead we skip directly to a 4 bucket table + // hold a single element. Instead, we skip directly to a 4 bucket table // which can hold 3 elements. - return Some(if cap < 4 { 4 } else { 8 }); + return Some(if cap < 4 { + 4 + } else if cap < 8 { + 8 + } else { + 16 + }); } // Otherwise require 1/8 buckets to be empty (87.5% load) @@ -849,7 +886,7 @@ impl<T, A: Allocator> RawTable<T, A> { // elements. If the calculation overflows then the requested bucket // count must be larger than what we have right and nothing needs to be // done. - let min_buckets = match capacity_to_buckets(min_size) { + let min_buckets = match capacity_to_buckets(min_size, Self::TABLE_LAYOUT) { Some(buckets) => buckets, None => return, }; @@ -980,14 +1017,8 @@ impl<T, A: Allocator> RawTable<T, A> { /// * If `self.table.items != 0`, calling of this function with `capacity` /// equal to 0 (`capacity == 0`) results in [`undefined behavior`]. /// - /// * If `capacity_to_buckets(capacity) < Group::WIDTH` and - /// `self.table.items > capacity_to_buckets(capacity)` - /// calling this function results in [`undefined behavior`]. - /// - /// * If `capacity_to_buckets(capacity) >= Group::WIDTH` and - /// `self.table.items > capacity_to_buckets(capacity)` - /// calling this function are never return (will go into an - /// infinite loop). + /// * If `self.table.items > capacity_to_buckets(capacity, Self::TABLE_LAYOUT)` + /// calling this function are never return (will loop infinitely). /// /// See [`RawTableInner::find_insert_slot`] for more information. /// @@ -1477,8 +1508,8 @@ impl RawTableInner { // SAFETY: We checked that we could successfully allocate the new table, and then // initialized all control bytes with the constant `Tag::EMPTY` byte. unsafe { - let buckets = - capacity_to_buckets(capacity).ok_or_else(|| fallibility.capacity_overflow())?; + let buckets = capacity_to_buckets(capacity, table_layout) + .ok_or_else(|| fallibility.capacity_overflow())?; let mut result = Self::new_uninitialized(alloc, table_layout, buckets, fallibility)?; @@ -1687,18 +1718,20 @@ impl RawTableInner { insert_slot = self.find_insert_slot_in_group(&group, &probe_seq); } - // Only stop the search if the group contains at least one empty element. - // Otherwise, the element that we are looking for might be in a following group. - if likely(group.match_empty().any_bit_set()) { - // We must have found a insert slot by now, since the current group contains at - // least one. For tables smaller than the group width, there will still be an - // empty element in the current (and only) group due to the load factor. - unsafe { - // SAFETY: - // * Caller of this function ensures that the control bytes are properly initialized. - // - // * We use this function with the slot / index found by `self.find_insert_slot_in_group` - return Err(self.fix_insert_slot(insert_slot.unwrap_unchecked())); + if let Some(insert_slot) = insert_slot { + // Only stop the search if the group contains at least one empty element. + // Otherwise, the element that we are looking for might be in a following group. + if likely(group.match_empty().any_bit_set()) { + // We must have found a insert slot by now, since the current group contains at + // least one. For tables smaller than the group width, there will still be an + // empty element in the current (and only) group due to the load factor. + unsafe { + // SAFETY: + // * Caller of this function ensures that the control bytes are properly initialized. + // + // * We use this function with the slot / index found by `self.find_insert_slot_in_group` + return Err(self.fix_insert_slot(insert_slot)); + } } } @@ -4135,6 +4168,26 @@ impl<T, A: Allocator> RawExtractIf<'_, T, A> { mod test_map { use super::*; + #[test] + fn test_minimum_capacity_for_small_types() { + #[track_caller] + fn test_t<T>() { + let raw_table: RawTable<T> = RawTable::with_capacity(1); + let actual_buckets = raw_table.buckets(); + let min_buckets = Group::WIDTH / core::mem::size_of::<T>(); + assert!( + actual_buckets >= min_buckets, + "expected at least {min_buckets} buckets, got {actual_buckets} buckets" + ); + } + + test_t::<u8>(); + + // This is only "small" for some platforms, like x86_64 with SSE2, but + // there's no harm in running it on other platforms. + test_t::<u16>(); + } + fn rehash_in_place<T>(table: &mut RawTable<T>, hasher: impl Fn(&T) -> u64) { unsafe { table.table.rehash_in_place( @@ -4238,9 +4291,9 @@ mod test_map { /// ARE ZERO, EVEN IF WE HAVE `FULL` CONTROL BYTES. #[test] fn test_catch_panic_clone_from() { + use super::{AllocError, Allocator, Global}; use ::alloc::sync::Arc; use ::alloc::vec::Vec; - use allocator_api2::alloc::{AllocError, Allocator, Global}; use core::sync::atomic::{AtomicI8, Ordering}; use std::thread; diff --git a/third_party/rust/hashbrown/src/rustc_entry.rs b/third_party/rust/hashbrown/src/rustc_entry.rs @@ -550,7 +550,7 @@ impl<K, V> IterMut<'_, K, V> { } } -impl<K, V> IntoIter<K, V> { +impl<K, V, A: Allocator> IntoIter<K, V, A> { /// Returns a iterator of references over the remaining items. #[cfg_attr(feature = "inline-more", inline)] pub fn rustc_iter(&self) -> Iter<'_, K, V> { @@ -558,7 +558,7 @@ impl<K, V> IntoIter<K, V> { } } -impl<K, V> Drain<'_, K, V> { +impl<K, V, A: Allocator> Drain<'_, K, V, A> { /// Returns a iterator of references over the remaining items. #[cfg_attr(feature = "inline-more", inline)] pub fn rustc_iter(&self) -> Iter<'_, K, V> { diff --git a/third_party/rust/hashbrown/src/set.rs b/third_party/rust/hashbrown/src/set.rs @@ -1678,10 +1678,7 @@ pub struct Drain<'a, K, A: Allocator = Global> { /// [`extract_if`]: struct.HashSet.html#method.extract_if /// [`HashSet`]: struct.HashSet.html #[must_use = "Iterators are lazy unless consumed"] -pub struct ExtractIf<'a, K, F, A: Allocator = Global> -where - F: FnMut(&K) -> bool, -{ +pub struct ExtractIf<'a, K, F, A: Allocator = Global> { f: F, inner: RawExtractIf<'a, (K, ()), A>, } @@ -2758,6 +2755,22 @@ mod test_set { } #[test] + fn test_sub_assign() { + let mut a: HashSet<_> = vec![1, 2, 3, 4, 5].into_iter().collect(); + let b: HashSet<_> = vec![4, 5, 6].into_iter().collect(); + + a -= &b; + + let mut i = 0; + let expected = [1, 2, 3]; + for x in &a { + assert!(expected.contains(x)); + i += 1; + } + assert_eq!(i, expected.len()); + } + + #[test] fn test_union() { let mut a = HashSet::new(); let mut b = HashSet::new(); diff --git a/third_party/rust/hashbrown/src/table.rs b/third_party/rust/hashbrown/src/table.rs @@ -2343,10 +2343,7 @@ impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> { /// This `struct` is created by [`HashTable::extract_if`]. See its /// documentation for more. #[must_use = "Iterators are lazy unless consumed"] -pub struct ExtractIf<'a, T, F, A: Allocator = Global> -where - F: FnMut(&mut T) -> bool, -{ +pub struct ExtractIf<'a, T, F, A: Allocator = Global> { f: F, inner: RawExtractIf<'a, T, A>, } diff --git a/third_party/rust/hashbrown/src/util.rs b/third_party/rust/hashbrown/src/util.rs @@ -1,10 +1,34 @@ -// FIXME: Branch prediction hint. This is currently only available on nightly -// but it consistently improves performance by 10-15%. -#[cfg(not(feature = "nightly"))] -pub(crate) use core::convert::{identity as likely, identity as unlikely}; +// FIXME: Replace with `core::hint::{likely, unlikely}` once they are stable. #[cfg(feature = "nightly")] pub(crate) use core::intrinsics::{likely, unlikely}; +#[cfg(not(feature = "nightly"))] +#[inline(always)] +#[cold] +fn cold_path() {} + +#[cfg(not(feature = "nightly"))] +#[inline(always)] +pub(crate) fn likely(b: bool) -> bool { + if b { + true + } else { + cold_path(); + false + } +} + +#[cfg(not(feature = "nightly"))] +#[inline(always)] +pub(crate) fn unlikely(b: bool) -> bool { + if b { + cold_path(); + true + } else { + false + } +} + // FIXME: use strict provenance functions once they are stable. // Implement it with a transmute for now. #[inline(always)] diff --git a/third_party/rust/hashbrown/tests/set.rs b/third_party/rust/hashbrown/tests/set.rs @@ -1,7 +1,7 @@ #![cfg(not(miri))] // FIXME: takes too long use hashbrown::HashSet; -use rand::{distributions::Alphanumeric, rngs::SmallRng, Rng, SeedableRng}; +use rand::{distr::Alphanumeric, rngs::SmallRng, Rng, SeedableRng}; use std::iter; #[test]