commit 4e386236cecc6986bf3c6cdb1290adf5af3b7b13
parent e3fddbb624b6c6e541c8c7d95bb8b8bc9fff5454
Author: Erich Gubler <erichdongubler@gmail.com>
Date: Thu, 2 Oct 2025 18:09:18 +0000
Bug 1991226 - chore(rust): upgrade `indexmap` 2.8.0 → 2.11.4 r=supply-chain-reviewers
Differential Revision: https://phabricator.services.mozilla.com/D266855
Diffstat:
31 files changed, 2399 insertions(+), 479 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
@@ -3365,13 +3365,14 @@ dependencies = [
[[package]]
name = "indexmap"
-version = "2.8.0"
+version = "2.11.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3954d50fe15b02142bf25d3b8bdadb634ec3948f103d04ffe3031bc8fe9d7058"
+checksum = "4b0f83760fb341a774ed326568e19f5a863af4a952def8c39f9ab92fd95b88e5"
dependencies = [
"equivalent",
"hashbrown 0.15.2",
"serde",
+ "serde_core",
]
[[package]]
diff --git a/third_party/rust/indexmap/.cargo-checksum.json b/third_party/rust/indexmap/.cargo-checksum.json
@@ -1 +1 @@
-{"files":{"Cargo.lock":"059abfeade15fcc933125acdfaae57a9ddaacdeac8def9638a75846c42748144","Cargo.toml":"f47b2601b06cf4a9944b990114c6341d3b748e2bddb2b1c6c868b05340773401","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"732583852f9bbea9c82701394ddaca19f68ae4986300a11187fe539e1b57f8f5","RELEASES.md":"7eef634d089d35cb487c65b364f49885c4eec28331c01d66e425d51c097db632","benches/bench.rs":"3b2900abbc9e8a60af78b0395222ee75e86bc68519a0f38477387d1572eed397","benches/faststring.rs":"5fdd6cdb19d0557ed58f241e809a240cf8939d9e5b87a72d5f127f81ab98380b","src/arbitrary.rs":"068713b1e8e762dbe9e4d19d555e77c17e59408335a40f4777d6100340605655","src/borsh.rs":"74121b426379d4f7365757ffd4f3dd469543fa1635193460fe268799a78a0706","src/lib.rs":"4fadf5fd465338571809fc7a1814ee560a6b0ad57f6e2d9902e1d727047d17b4","src/macros.rs":"3edbdc39dd0d4e9d161bb871487e8caded3a0740812a9fbba2fc892f4ae90115","src/map.rs":"e2f14b1b350c1c4b3da6449269648006fec8501ccebfb1c224ed6c499d446701","src/map/core.rs":"c40d189fba523dcd79ae8aced27db3bbcc225ccd6522e47ac3a1a9f6188e6231","src/map/core/entry.rs":"346a1f327fecc58f672f54d3bd6583eb4ca37158c0cce83dadf80cccebf1d9bb","src/map/core/raw_entry_v1.rs":"ed8d8e0b2bed1399a7aec7981299b8928b659e4e906a6e8d2e76bf0e662b4c0b","src/map/iter.rs":"80532a84d9dc9287b71db98b5360082dc9d412dc4a3317c258771ff72ec59111","src/map/mutable.rs":"36fc002d8396af4e7695d263c14d64b34234f4219440c6998910e5261bdbee05","src/map/serde_seq.rs":"ce06b5bb816c15ea8fe3d2c358baa90fe6f45ecb585623a69592d6de69319194","src/map/slice.rs":"37612b5f3e11a4b6da3e7c92d30deed9d85b9c6a01e6001cc764e7b233ac1bd1","src/map/tests.rs":"154e94016f3c62d58eaf70fb605dc812f4929e64dfc4a2ed1210a2ea145be8d9","src/rayon/map.rs":"0fad36851fdf6894695e526c684c9b3afeac82e29016e6a523eea68cc3b2d19d","src/rayon/mod.rs":"c0625603ee9b0cce5751af05c0d501019b902fbfd7ed3a181f8c9d6915d4242a","src/rayon/set.rs":"4b076dbfd9a7eb2fd65783f1c8a5acabe075403f3d05e30c337676acec25d8ee","src/serde.rs":"23fd6b5e8f6795e4121693ac16dab61e76c4d8c83e6da1b3ef26d081fae28e79","src/set.rs":"3eeab72c9c0ecebf216be593390ebba5597e1cac39a7190141f83da43dd9b16d","src/set/iter.rs":"1092f5367d1e609b6368d71282201f66534032446c303a3e475fca1031f29e63","src/set/mutable.rs":"42a4118b123b9bc8385e2023d9f1d48230e61b8fec2cfa60782836949b639aac","src/set/slice.rs":"9589b4b4d591eafcda113f469eccaedf6299974b12f12c98a6f617596f9d7b0a","src/set/tests.rs":"d9c182cd776ca9182b5284f06eacc70c5f33a66aff3021c35134ffd1d7630c05","src/util.rs":"a0e512cf0bc5ccdeff5a64629da2cd976d7f6586194cc6901c118bc8b6287132","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"9759dcc34d86d9635d9d18be6358f5f3e3c0f995874b64b5a7ca4b582f4acedb","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"3954d50fe15b02142bf25d3b8bdadb634ec3948f103d04ffe3031bc8fe9d7058"}
-\ No newline at end of file
+{"files":{"Cargo.lock":"1bf0f548cfb3a1a0ec7032c63df62f469d531b6535951a4327bf0d3960f5919b","Cargo.toml":"28e0d18a8dd2b95f6d29cfc7bd64422f7a14f5e1b1a3ee47f964a670087bb036","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"732583852f9bbea9c82701394ddaca19f68ae4986300a11187fe539e1b57f8f5","RELEASES.md":"95f60b24b38caa1e735334ce5b4cf43f60c9097685a230587f38bd4e49d9b7e6","benches/bench.rs":"21a5cd6f025ed2ef7bd4a8a08db330449e117228a406c14991e56a37589ee558","benches/faststring.rs":"109761adf3e9ad558f5022361d041fe821d8750284a5c6e8ab710f82877894de","src/arbitrary.rs":"068713b1e8e762dbe9e4d19d555e77c17e59408335a40f4777d6100340605655","src/borsh.rs":"66a6bca84297fa9afa5324fe63c2ed0ff70e02bd1f44af2f879be7868ac85e87","src/lib.rs":"e5161f20460d85c2467bee77bd178116c67ea843f4c7bcfa7fc55d765cbcb3d1","src/macros.rs":"3f173a3cdbed13d06eb4db5f143dab1f9861039915994e10390c2cb894891301","src/map.rs":"d1f97ab6d9104c10001a3324329cb02e2906c13d2b1462d37467658f54e39440","src/map/core.rs":"14e11cd8bc785e4ae2eb524704e10182cb6ebbd17e12f430a216983846353cb9","src/map/core/entry.rs":"6ce12ba164cddd72e8de9ff0c7131465fa69bc2bcbe01e4aea478ccf33f481c2","src/map/core/extract.rs":"f937d88e1a49db286b4020679b275d1184699665de41f9161f7485b9fc90998a","src/map/core/raw_entry_v1.rs":"5fd06b3e4bbd8a5e636a98e2e2dfc037a34ea5ad2dc40ad4e5d26f80a0dd345c","src/map/iter.rs":"01a8fb31b5103c8779b2d7f3d42bcadfe751dc9fa50b0191713177a4538c5012","src/map/mutable.rs":"d35a5dd5c4ac1b15111ac5da49971e08e7b21a4e7032679821fdf2cb13d7f1a4","src/map/serde_seq.rs":"25e7e38467477adf045958d24eb719ac155a381a32f754368124708cc66d5567","src/map/slice.rs":"dc3a80cdc34c96d36b9126f4fe3758b977d3103a2eac63fa54ffcfd7f5914928","src/map/tests.rs":"a46cbd29b2a0b104d8825c1727ea9fd4ae41e6b410bc0a5c44537f9c2eeee39a","src/rayon/map.rs":"de90ac3a107618dc7cfe966ae470b26b85e78a19b97e68fc41f71bf6af3f4496","src/rayon/mod.rs":"da256bc6ce16bd7aee261b60e27fcc15cb20fd400ff022aade7a8ab9f0033482","src/rayon/set.rs":"e72dba6752cb25d34aec6994c6c3920638e6a8811811c7ff4850b8be8e35d6d2","src/serde.rs":"7055abe4c2a3e9d8a0c205b0ec75759ee2f9edca46d8f63b42ec98c175a06929","src/set.rs":"28e9ddd53c4aa382ff92df40f73e062f6a4b3851498fb7fc392f13153c9acdc0","src/set/iter.rs":"c51fff3636b11c9a686542a4eb0e892476782a1c9384cee83a4b93ab26fc6e99","src/set/mutable.rs":"b402e0d9f221754a3192b6657d19302e4130d33216fc557ff505775d121ecdf1","src/set/slice.rs":"7d17cc582aa940617057b916b50518fc7671d5d7c2ab6bdeaf7bcfab4838de17","src/set/tests.rs":"9c64101fb9be53dc212a446b099db2f5757a97c991449b126e4fbdc6cf89cec2","src/sval.rs":"30474f4a6cd820ff348d7a28017226152171ca7921f90a10faf7301429c46abf","src/util.rs":"a0e512cf0bc5ccdeff5a64629da2cd976d7f6586194cc6901c118bc8b6287132","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"2b06823186694cd1c0446c757ae916d3b12b6b51a43c54eeb7ef76ce45f16e4c","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"4b0f83760fb341a774ed326568e19f5a863af4a952def8c39f9ab92fd95b88e5"}
+\ No newline at end of file
diff --git a/third_party/rust/indexmap/Cargo.lock b/third_party/rust/indexmap/Cargo.lock
@@ -4,30 +4,24 @@ version = 3
[[package]]
name = "arbitrary"
-version = "1.4.1"
+version = "1.4.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "dde20b3d026af13f561bdd0f15edf01fc734f0dafcedbaf42bba506a9517f223"
-
-[[package]]
-name = "bitflags"
-version = "2.9.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5c8214115b7bf84099f1309324e63141d4c5d7cc26862f97a0a857dbefe165bd"
+checksum = "c3d036a3c4ab069c7b410a2ce876bd74808d2d0888a82667669f8e783a898bf1"
[[package]]
name = "borsh"
-version = "1.5.5"
+version = "1.5.7"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5430e3be710b68d984d1391c854eb431a9d548640711faa54eecb1df93db91cc"
+checksum = "ad8646f98db542e39fc66e68a20b2144f6a732636df7c2354e74645faaa433ce"
dependencies = [
"cfg_aliases",
]
[[package]]
name = "cfg-if"
-version = "1.0.0"
+version = "1.0.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+checksum = "2fd1289c04a9ea8cb22300a459a72a385d7c73d3259e2ed7dcb2af674838cfa9"
[[package]]
name = "cfg_aliases"
@@ -73,56 +67,50 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "877a4ace8713b0bcf2a4e7eec82529c029f1d0619886d18145fea96c3ffe5c0f"
[[package]]
-name = "fnv"
-version = "1.0.7"
+name = "fastrand"
+version = "2.3.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
+checksum = "37909eebbb50d72f9059c3b6d82c0463f2ff062c9e95845c43a6c9c0355411be"
[[package]]
-name = "getrandom"
-version = "0.2.15"
+name = "fnv"
+version = "1.0.7"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c4567c8db10ae91089c99af84c68c38da3ec2f087c3f82960bcdbf3656b6f4d7"
-dependencies = [
- "cfg-if",
- "libc",
- "wasi 0.11.0+wasi-snapshot-preview1",
-]
+checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
[[package]]
name = "getrandom"
-version = "0.3.1"
+version = "0.2.16"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "43a49c392881ce6d5c3b8cb70f98717b7c07aabbdff06687b9030dbfbe2725f8"
+checksum = "335ff9f135e4384c8150d6f27c6daed433577f86b4750418338c01a1a2528592"
dependencies = [
"cfg-if",
"libc",
- "wasi 0.13.3+wasi-0.2.2",
- "windows-targets",
+ "wasi",
]
[[package]]
name = "hashbrown"
-version = "0.15.2"
+version = "0.15.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bf151400ff0baff5465007dd2f3e717f3fe502074ca563069ce3a6629d07b289"
+checksum = "9229cfe53dfd69f0609a49f65461bd93001ea1ef889cd5529dd176593f5338a1"
[[package]]
name = "indexmap"
-version = "2.8.0"
+version = "2.11.4"
dependencies = [
"arbitrary",
"borsh",
"equivalent",
+ "fastrand",
"fnv",
"hashbrown",
"itertools",
- "lazy_static",
"quickcheck",
- "rand 0.9.0",
"rayon",
"serde",
- "serde_derive",
+ "serde_core",
+ "sval",
]
[[package]]
@@ -135,31 +123,16 @@ dependencies = [
]
[[package]]
-name = "lazy_static"
-version = "1.5.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe"
-
-[[package]]
name = "libc"
-version = "0.2.170"
+version = "0.2.175"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "875b3680cb2f8f71bdcf9a30f38d48282f5d3c95cbf9b3fa57269bb5d5c06828"
-
-[[package]]
-name = "ppv-lite86"
-version = "0.2.21"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9"
-dependencies = [
- "zerocopy",
-]
+checksum = "6a82ae493e598baaea5209805c49bbf2ea7de956d50d7da0da1164f9c6d28543"
[[package]]
name = "proc-macro2"
-version = "1.0.94"
+version = "1.0.101"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a31971752e70b8b2686d7e46ec17fb38dad4051d94024c88df49b667caea9c84"
+checksum = "89ae43fd86e4158d6db51ad8e2b80f313af9cc74f5c0e03ccb87de09998732de"
dependencies = [
"unicode-ident",
]
@@ -170,14 +143,14 @@ version = "1.0.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "588f6378e4dd99458b60ec275b4477add41ce4fa9f64dcba6f15adccb19b50d6"
dependencies = [
- "rand 0.8.5",
+ "rand",
]
[[package]]
name = "quote"
-version = "1.0.39"
+version = "1.0.40"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c1f1914ce909e1658d9907913b4b91947430c7d9be598b15a1912935b8c04801"
+checksum = "1885c039570dc00dcb4ff087a89e185fd56bae234ddc7f056a945bf36467248d"
dependencies = [
"proc-macro2",
]
@@ -188,28 +161,7 @@ version = "0.8.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
dependencies = [
- "rand_core 0.6.4",
-]
-
-[[package]]
-name = "rand"
-version = "0.9.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3779b94aeb87e8bd4e834cee3650289ee9e0d5677f976ecdb6d219e5f4f6cd94"
-dependencies = [
- "rand_chacha",
- "rand_core 0.9.3",
- "zerocopy",
-]
-
-[[package]]
-name = "rand_chacha"
-version = "0.9.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d3022b5f1df60f26e1ffddd6c66e8aa15de382ae63b3a0c1bfc0e4d3e3f325cb"
-dependencies = [
- "ppv-lite86",
- "rand_core 0.9.3",
+ "rand_core",
]
[[package]]
@@ -218,23 +170,14 @@ version = "0.6.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
dependencies = [
- "getrandom 0.2.15",
-]
-
-[[package]]
-name = "rand_core"
-version = "0.9.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "99d9a13982dcf210057a8a78572b2217b667c3beacbf3a0d8b454f6f82837d38"
-dependencies = [
- "getrandom 0.3.1",
+ "getrandom",
]
[[package]]
name = "rayon"
-version = "1.10.0"
+version = "1.11.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b418a60154510ca1a002a752ca9714984e21e4241e804d32555251faf8b78ffa"
+checksum = "368f01d005bf8fd9b1206fb6fa653e6c4a81ceb1466406b81792d87c5677a58f"
dependencies = [
"either",
"rayon-core",
@@ -242,9 +185,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",
@@ -252,145 +195,59 @@ dependencies = [
[[package]]
name = "serde"
-version = "1.0.219"
+version = "1.0.225"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5f0e2c6ed6606019b4e29e69dbaba95b11854410e5347d525002456dbbb786b6"
+checksum = "fd6c24dee235d0da097043389623fb913daddf92c76e9f5a1db88607a0bcbd1d"
dependencies = [
+ "serde_core",
"serde_derive",
]
[[package]]
-name = "serde_derive"
-version = "1.0.219"
+name = "serde_core"
+version = "1.0.225"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5b0276cf7f2c73365f7157c8123c21cd9a50fbbd844757af28ca1f5925fc2a00"
+checksum = "659356f9a0cb1e529b24c01e43ad2bdf520ec4ceaf83047b83ddcc2251f96383"
dependencies = [
- "proc-macro2",
- "quote",
- "syn",
+ "serde_derive",
]
[[package]]
-name = "syn"
-version = "2.0.100"
+name = "serde_derive"
+version = "1.0.225"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b09a44accad81e1ba1cd74a32461ba89dee89095ba17b32f5d03683b1b1fc2a0"
+checksum = "0ea936adf78b1f766949a4977b91d2f5595825bd6ec079aa9543ad2685fc4516"
dependencies = [
"proc-macro2",
"quote",
- "unicode-ident",
-]
-
-[[package]]
-name = "unicode-ident"
-version = "1.0.18"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5a5f39404a5da50712a4c1eecf25e90dd62b613502b7e925fd4e4d19b5c96512"
-
-[[package]]
-name = "wasi"
-version = "0.11.0+wasi-snapshot-preview1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
-
-[[package]]
-name = "wasi"
-version = "0.13.3+wasi-0.2.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "26816d2e1a4a36a2940b96c5296ce403917633dff8f3440e9b236ed6f6bacad2"
-dependencies = [
- "wit-bindgen-rt",
-]
-
-[[package]]
-name = "windows-targets"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9b724f72796e036ab90c1021d4780d4d3d648aca59e491e6b98e725b84e99973"
-dependencies = [
- "windows_aarch64_gnullvm",
- "windows_aarch64_msvc",
- "windows_i686_gnu",
- "windows_i686_gnullvm",
- "windows_i686_msvc",
- "windows_x86_64_gnu",
- "windows_x86_64_gnullvm",
- "windows_x86_64_msvc",
+ "syn",
]
[[package]]
-name = "windows_aarch64_gnullvm"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "32a4622180e7a0ec044bb555404c800bc9fd9ec262ec147edd5989ccd0c02cd3"
-
-[[package]]
-name = "windows_aarch64_msvc"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "09ec2a7bb152e2252b53fa7803150007879548bc709c039df7627cabbd05d469"
-
-[[package]]
-name = "windows_i686_gnu"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8e9b5ad5ab802e97eb8e295ac6720e509ee4c243f69d781394014ebfe8bbfa0b"
-
-[[package]]
-name = "windows_i686_gnullvm"
-version = "0.52.6"
+name = "sval"
+version = "2.14.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0eee52d38c090b3caa76c563b86c3a4bd71ef1a819287c19d586d7334ae8ed66"
+checksum = "7cc9739f56c5d0c44a5ed45473ec868af02eb896af8c05f616673a31e1d1bb09"
[[package]]
-name = "windows_i686_msvc"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "240948bc05c5e7c6dabba28bf89d89ffce3e303022809e73deaefe4f6ec56c66"
-
-[[package]]
-name = "windows_x86_64_gnu"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "147a5c80aabfbf0c7d901cb5895d1de30ef2907eb21fbbab29ca94c5b08b1a78"
-
-[[package]]
-name = "windows_x86_64_gnullvm"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "24d5b23dc417412679681396f2b49f3de8c1473deb516bd34410872eff51ed0d"
-
-[[package]]
-name = "windows_x86_64_msvc"
-version = "0.52.6"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "589f6da84c646204747d1270a2a5661ea66ed1cced2631d546fdfb155959f9ec"
-
-[[package]]
-name = "wit-bindgen-rt"
-version = "0.33.0"
+name = "syn"
+version = "2.0.106"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3268f3d866458b787f390cf61f4bbb563b922d091359f9608842999eaee3943c"
+checksum = "ede7c438028d4436d71104916910f5bb611972c5cfd7f89b8300a8186e6fada6"
dependencies = [
- "bitflags",
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
]
[[package]]
-name = "zerocopy"
-version = "0.8.23"
+name = "unicode-ident"
+version = "1.0.19"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "fd97444d05a4328b90e75e503a34bad781f14e28a823ad3557f0750df1ebcbc6"
-dependencies = [
- "zerocopy-derive",
-]
+checksum = "f63a545481291138910575129486daeaf8ac54aee4387fe7906919f7830c7d9d"
[[package]]
-name = "zerocopy-derive"
-version = "0.8.23"
+name = "wasi"
+version = "0.11.1+wasi-snapshot-preview1"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6352c01d0edd5db859a63e2605f4ea3183ddbd15e2c4a9e7d32184df75e4f154"
-dependencies = [
- "proc-macro2",
- "quote",
- "syn",
-]
+checksum = "ccf3ec651a847eb01de73ccad15eb7d99f80485de043efb2f370cd654f4ea44b"
diff --git a/third_party/rust/indexmap/Cargo.toml b/third_party/rust/indexmap/Cargo.toml
@@ -13,7 +13,7 @@
edition = "2021"
rust-version = "1.63"
name = "indexmap"
-version = "2.8.0"
+version = "2.11.4"
build = false
autolib = false
autobins = false
@@ -34,6 +34,11 @@ categories = [
license = "Apache-2.0 OR MIT"
repository = "https://github.com/indexmap-rs/indexmap"
+[package.metadata.release]
+allow-branch = ["main"]
+sign-tag = true
+tag-name = "{{version}}"
+
[package.metadata.docs.rs]
features = [
"arbitrary",
@@ -41,19 +46,19 @@ features = [
"serde",
"borsh",
"rayon",
+ "sval",
]
rustdoc-args = [
"--cfg",
"docsrs",
]
-[package.metadata.release]
-allow-branch = ["main"]
-sign-tag = true
-tag-name = "{{version}}"
-
[features]
default = ["std"]
+serde = [
+ "dep:serde_core",
+ "dep:serde",
+]
std = []
test_debug = []
@@ -101,7 +106,7 @@ version = "1.0"
default-features = false
[dependencies.hashbrown]
-version = "0.15.0"
+version = ">= 0.15.0, < 0.17.0"
default-features = false
[dependencies.quickcheck]
@@ -113,30 +118,39 @@ default-features = false
version = "1.9"
optional = true
-[dependencies.serde]
-version = "1.0"
+[dependencies.serde_core]
+version = "1.0.220"
optional = true
default-features = false
+[dependencies.sval]
+version = "2"
+optional = true
+default-features = false
+
+[dev-dependencies.fastrand]
+version = "2"
+default-features = false
+
[dev-dependencies.fnv]
version = "1.0"
[dev-dependencies.itertools]
version = "0.14"
-[dev-dependencies.lazy_static]
-version = "1.3"
-
[dev-dependencies.quickcheck]
version = "1.0"
default-features = false
-[dev-dependencies.rand]
-version = "0.9"
-features = ["small_rng"]
-
-[dev-dependencies.serde_derive]
+[dev-dependencies.serde]
version = "1.0"
+features = ["derive"]
+default-features = false
+
+[target."cfg(any())".dependencies.serde]
+version = "1.0.220"
+optional = true
+default-features = false
[lints.clippy]
style = "allow"
diff --git a/third_party/rust/indexmap/RELEASES.md b/third_party/rust/indexmap/RELEASES.md
@@ -1,5 +1,50 @@
# Releases
+## 2.11.4 (2025-09-18)
+
+- Updated the `hashbrown` dependency to a range allowing 0.15 or 0.16.
+
+## 2.11.3 (2025-09-15)
+
+- Make the minimum `serde` version only apply when "serde" is enabled.
+
+## 2.11.2 (2025-09-15)
+
+- Switched the "serde" feature to depend on `serde_core`, improving build
+ parallelism in cases where other dependents have enabled "serde/derive".
+
+## 2.11.1 (2025-09-08)
+
+- Added a `get_key_value_mut` method to `IndexMap`.
+- Removed the unnecessary `Ord` bound on `insert_sorted_by` methods.
+
+## 2.11.0 (2025-08-22)
+
+- Added `insert_sorted_by` and `insert_sorted_by_key` methods to `IndexMap`,
+ `IndexSet`, and `VacantEntry`, like customizable versions of `insert_sorted`.
+- Added `is_sorted`, `is_sorted_by`, and `is_sorted_by_key` methods to
+ `IndexMap` and `IndexSet`, as well as their `Slice` counterparts.
+- Added `sort_by_key` and `sort_unstable_by_key` methods to `IndexMap` and
+ `IndexSet`, as well as parallel counterparts.
+- Added `replace_index` methods to `IndexMap`, `IndexSet`, and `VacantEntry`
+ to replace the key (or set value) at a given index.
+- Added optional `sval` serialization support.
+
+## 2.10.0 (2025-06-26)
+
+- Added `extract_if` methods to `IndexMap` and `IndexSet`, similar to the
+ methods for `HashMap` and `HashSet` with ranges like `Vec::extract_if`.
+- Added more `#[track_caller]` annotations to functions that may panic.
+
+## 2.9.0 (2025-04-04)
+
+- Added a `get_disjoint_mut` method to `IndexMap`, matching Rust 1.86's
+ `HashMap` method.
+- Added a `get_disjoint_indices_mut` method to `IndexMap` and `map::Slice`,
+ matching Rust 1.86's `get_disjoint_mut` method on slices.
+- Deprecated the `borsh` feature in favor of their own `indexmap` feature,
+ solving a cyclic dependency that occurred via `borsh-derive`.
+
## 2.8.0 (2025-03-10)
- Added `indexmap_with_default!` and `indexset_with_default!` to be used with
diff --git a/third_party/rust/indexmap/benches/bench.rs b/third_party/rust/indexmap/benches/bench.rs
@@ -1,12 +1,11 @@
#![feature(test)]
extern crate test;
-#[macro_use]
-extern crate lazy_static;
use fnv::FnvHasher;
use std::hash::BuildHasherDefault;
use std::hash::Hash;
+use std::sync::LazyLock;
type FnvBuilder = BuildHasherDefault<FnvHasher>;
use test::black_box;
@@ -16,14 +15,10 @@ use indexmap::IndexMap;
use std::collections::HashMap;
-use rand::rngs::SmallRng;
-use rand::seq::SliceRandom;
-use rand::SeedableRng;
-
/// Use a consistently seeded Rng for benchmark stability
-fn small_rng() -> SmallRng {
+fn small_rng() -> fastrand::Rng {
let seed = u64::from_le_bytes(*b"indexmap");
- SmallRng::seed_from_u64(seed)
+ fastrand::Rng::with_seed(seed)
}
#[bench]
@@ -280,7 +275,7 @@ where
{
let mut v = Vec::from_iter(iter);
let mut rng = small_rng();
- v.shuffle(&mut rng);
+ rng.shuffle(&mut v);
v
}
@@ -357,53 +352,45 @@ const LOOKUP_MAP_SIZE: u32 = 100_000_u32;
const LOOKUP_SAMPLE_SIZE: u32 = 5000;
const SORT_MAP_SIZE: usize = 10_000;
-// use lazy_static so that comparison benchmarks use the exact same inputs
-lazy_static! {
- static ref KEYS: Vec<u32> = shuffled_keys(0..LOOKUP_MAP_SIZE);
-}
+// use (lazy) statics so that comparison benchmarks use the exact same inputs
-lazy_static! {
- static ref HMAP_100K: HashMap<u32, u32> = {
- let c = LOOKUP_MAP_SIZE;
- let mut map = HashMap::with_capacity(c as usize);
- let keys = &*KEYS;
- for &key in keys {
- map.insert(key, key);
- }
- map
- };
-}
+static KEYS: LazyLock<Vec<u32>> = LazyLock::new(|| shuffled_keys(0..LOOKUP_MAP_SIZE));
-lazy_static! {
- static ref IMAP_100K: IndexMap<u32, u32> = {
- let c = LOOKUP_MAP_SIZE;
- let mut map = IndexMap::with_capacity(c as usize);
- let keys = &*KEYS;
- for &key in keys {
- map.insert(key, key);
- }
- map
- };
-}
+static HMAP_100K: LazyLock<HashMap<u32, u32>> = LazyLock::new(|| {
+ let c = LOOKUP_MAP_SIZE;
+ let mut map = HashMap::with_capacity(c as usize);
+ let keys = &*KEYS;
+ for &key in keys {
+ map.insert(key, key);
+ }
+ map
+});
-lazy_static! {
- static ref IMAP_SORT_U32: IndexMap<u32, u32> = {
- let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
- for &key in &KEYS[..SORT_MAP_SIZE] {
- map.insert(key, key);
- }
- map
- };
-}
-lazy_static! {
- static ref IMAP_SORT_S: IndexMap<String, String> = {
- let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
- for &key in &KEYS[..SORT_MAP_SIZE] {
- map.insert(format!("{:^16x}", &key), String::new());
- }
- map
- };
-}
+static IMAP_100K: LazyLock<IndexMap<u32, u32>> = LazyLock::new(|| {
+ let c = LOOKUP_MAP_SIZE;
+ let mut map = IndexMap::with_capacity(c as usize);
+ let keys = &*KEYS;
+ for &key in keys {
+ map.insert(key, key);
+ }
+ map
+});
+
+static IMAP_SORT_U32: LazyLock<IndexMap<u32, u32>> = LazyLock::new(|| {
+ let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
+ for &key in &KEYS[..SORT_MAP_SIZE] {
+ map.insert(key, key);
+ }
+ map
+});
+
+static IMAP_SORT_S: LazyLock<IndexMap<String, String>> = LazyLock::new(|| {
+ let mut map = IndexMap::with_capacity(SORT_MAP_SIZE);
+ for &key in &KEYS[..SORT_MAP_SIZE] {
+ map.insert(format!("{:^16x}", &key), String::new());
+ }
+ map
+});
#[bench]
fn lookup_hashmap_100_000_multi(b: &mut Bencher) {
@@ -523,7 +510,7 @@ fn hashmap_merge_shuffle(b: &mut Bencher) {
b.iter(|| {
let mut merged = first_map.clone();
v.extend(second_map.iter().map(|(&k, &v)| (k, v)));
- v.shuffle(&mut rng);
+ rng.shuffle(&mut v);
merged.extend(v.drain(..));
merged
@@ -550,7 +537,7 @@ fn indexmap_merge_shuffle(b: &mut Bencher) {
b.iter(|| {
let mut merged = first_map.clone();
v.extend(second_map.iter().map(|(&k, &v)| (k, v)));
- v.shuffle(&mut rng);
+ rng.shuffle(&mut v);
merged.extend(v.drain(..));
merged
@@ -562,7 +549,7 @@ fn swap_remove_indexmap_100_000(b: &mut Bencher) {
let map = IMAP_100K.clone();
let mut keys = Vec::from_iter(map.keys().copied());
let mut rng = small_rng();
- keys.shuffle(&mut rng);
+ rng.shuffle(&mut keys);
b.iter(|| {
let mut map = map.clone();
@@ -579,7 +566,7 @@ fn shift_remove_indexmap_100_000_few(b: &mut Bencher) {
let map = IMAP_100K.clone();
let mut keys = Vec::from_iter(map.keys().copied());
let mut rng = small_rng();
- keys.shuffle(&mut rng);
+ rng.shuffle(&mut keys);
keys.truncate(50);
b.iter(|| {
@@ -600,7 +587,7 @@ fn shift_remove_indexmap_2_000_full(b: &mut Bencher) {
map.insert(key, key);
}
let mut rng = small_rng();
- keys.shuffle(&mut rng);
+ rng.shuffle(&mut keys);
b.iter(|| {
let mut map = map.clone();
diff --git a/third_party/rust/indexmap/benches/faststring.rs b/third_party/rust/indexmap/benches/faststring.rs
@@ -8,19 +8,15 @@ use indexmap::IndexMap;
use std::collections::HashMap;
-use rand::rngs::SmallRng;
-use rand::seq::SliceRandom;
-use rand::SeedableRng;
-
use std::hash::{Hash, Hasher};
use std::borrow::Borrow;
use std::ops::Deref;
/// Use a consistently seeded Rng for benchmark stability
-fn small_rng() -> SmallRng {
+fn small_rng() -> fastrand::Rng {
let seed = u64::from_le_bytes(*b"indexmap");
- SmallRng::seed_from_u64(seed)
+ fastrand::Rng::with_seed(seed)
}
#[derive(PartialEq, Eq, Copy, Clone)]
@@ -68,7 +64,7 @@ where
{
let mut v = Vec::from_iter(iter);
let mut rng = small_rng();
- v.shuffle(&mut rng);
+ rng.shuffle(&mut v);
v
}
diff --git a/third_party/rust/indexmap/src/borsh.rs b/third_party/rust/indexmap/src/borsh.rs
@@ -12,6 +12,9 @@ use borsh::{BorshDeserialize, BorshSerialize};
use crate::map::IndexMap;
use crate::set::IndexSet;
+// NOTE: the real `#[deprecated]` attribute doesn't work for trait implementations,
+// but we can get close by mimicking the message style for documentation.
+/// <div class="stab deprecated"><span class="emoji">👎</span><span>Deprecated: use borsh's <code>indexmap</code> feature instead.</span></div>
impl<K, V, S> BorshSerialize for IndexMap<K, V, S>
where
K: BorshSerialize,
@@ -36,6 +39,7 @@ where
}
}
+/// <div class="stab deprecated"><span class="emoji">👎</span><span>Deprecated: use borsh's <code>indexmap</code> feature instead.</span></div>
impl<K, V, S> BorshDeserialize for IndexMap<K, V, S>
where
K: BorshDeserialize + Eq + Hash,
@@ -50,6 +54,7 @@ where
}
}
+/// <div class="stab deprecated"><span class="emoji">👎</span><span>Deprecated: use borsh's <code>indexmap</code> feature instead.</span></div>
impl<T, S> BorshSerialize for IndexSet<T, S>
where
T: BorshSerialize,
@@ -72,6 +77,7 @@ where
}
}
+/// <div class="stab deprecated"><span class="emoji">👎</span><span>Deprecated: use borsh's <code>indexmap</code> feature instead.</span></div>
impl<T, S> BorshDeserialize for IndexSet<T, S>
where
T: BorshDeserialize + Eq + Hash,
diff --git a/third_party/rust/indexmap/src/lib.rs b/third_party/rust/indexmap/src/lib.rs
@@ -35,23 +35,22 @@
//! to [`IndexMap`] and [`IndexSet`]. Alternative implementations for
//! (de)serializing [`IndexMap`] as an ordered sequence are available in the
//! [`map::serde_seq`] module.
-//! * `borsh`: Adds implementations for [`BorshSerialize`] and [`BorshDeserialize`]
-//! to [`IndexMap`] and [`IndexSet`]. **Note:** When this feature is enabled,
-//! you cannot enable the `derive` feature of [`borsh`] due to a cyclic
-//! dependency. Instead, add the `borsh-derive` crate as an explicit
-//! dependency in your Cargo.toml and import as e.g.
-//! `use borsh_derive::{BorshSerialize, BorshDeserialize};`.
//! * `arbitrary`: Adds implementations for the [`arbitrary::Arbitrary`] trait
//! to [`IndexMap`] and [`IndexSet`].
//! * `quickcheck`: Adds implementations for the [`quickcheck::Arbitrary`] trait
//! to [`IndexMap`] and [`IndexSet`].
+//! * `borsh` (**deprecated**): Adds implementations for [`BorshSerialize`] and
+//! [`BorshDeserialize`] to [`IndexMap`] and [`IndexSet`]. Due to a cyclic
+//! dependency that arose between [`borsh`] and `indexmap`, `borsh v1.5.6`
+//! added an `indexmap` feature that should be used instead of enabling the
+//! feature here.
//!
//! _Note: only the `std` feature is enabled by default._
//!
//! [feature flags]: https://doc.rust-lang.org/cargo/reference/manifest.html#the-features-section
//! [`no_std`]: #no-standard-library-targets
-//! [`Serialize`]: `::serde::Serialize`
-//! [`Deserialize`]: `::serde::Deserialize`
+//! [`Serialize`]: `::serde_core::Serialize`
+//! [`Deserialize`]: `::serde_core::Deserialize`
//! [`BorshSerialize`]: `::borsh::BorshSerialize`
//! [`BorshDeserialize`]: `::borsh::BorshDeserialize`
//! [`borsh`]: `::borsh`
@@ -109,8 +108,6 @@ extern crate alloc;
#[macro_use]
extern crate std;
-use alloc::vec::{self, Vec};
-
mod arbitrary;
#[macro_use]
mod macros;
@@ -118,6 +115,8 @@ mod macros;
mod borsh;
#[cfg(feature = "serde")]
mod serde;
+#[cfg(feature = "sval")]
+mod sval;
mod util;
pub mod map;
@@ -204,16 +203,6 @@ impl<K, V> Bucket<K, V> {
}
}
-trait Entries {
- type Entry;
- fn into_entries(self) -> Vec<Self::Entry>;
- fn as_entries(&self) -> &[Self::Entry];
- fn as_entries_mut(&mut self) -> &mut [Self::Entry];
- fn with_entries<F>(&mut self, f: F)
- where
- F: FnOnce(&mut [Self::Entry]);
-}
-
/// The error type for [`try_reserve`][IndexMap::try_reserve] methods.
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct TryReserveError {
@@ -269,3 +258,33 @@ impl core::fmt::Display for TryReserveError {
#[cfg(feature = "std")]
#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
impl std::error::Error for TryReserveError {}
+
+// NOTE: This is copied from the slice module in the std lib.
+/// The error type returned by [`get_disjoint_indices_mut`][`IndexMap::get_disjoint_indices_mut`].
+///
+/// It indicates one of two possible errors:
+/// - An index is out-of-bounds.
+/// - The same index appeared multiple times in the array.
+// (or different but overlapping indices when ranges are provided)
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum GetDisjointMutError {
+ /// An index provided was out-of-bounds for the slice.
+ IndexOutOfBounds,
+ /// Two indices provided were overlapping.
+ OverlappingIndices,
+}
+
+impl core::fmt::Display for GetDisjointMutError {
+ fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+ let msg = match self {
+ GetDisjointMutError::IndexOutOfBounds => "an index is out of bounds",
+ GetDisjointMutError::OverlappingIndices => "there were overlapping indices",
+ };
+
+ core::fmt::Display::fmt(msg, f)
+ }
+}
+
+#[cfg(feature = "std")]
+#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
+impl std::error::Error for GetDisjointMutError {}
diff --git a/third_party/rust/indexmap/src/macros.rs b/third_party/rust/indexmap/src/macros.rs
@@ -1,5 +1,5 @@
/// Create an [`IndexMap`][crate::IndexMap] from a list of key-value pairs
-/// and a `BuildHasherDefault`-wrapped custom hasher.
+/// and a [`BuildHasherDefault`][core::hash::BuildHasherDefault]-wrapped custom hasher.
///
/// ## Example
///
@@ -73,7 +73,7 @@ macro_rules! indexmap {
}
/// Create an [`IndexSet`][crate::IndexSet] from a list of values
-/// and a `BuildHasherDefault`-wrapped custom hasher.
+/// and a [`BuildHasherDefault`][core::hash::BuildHasherDefault]-wrapped custom hasher.
///
/// ## Example
///
diff --git a/third_party/rust/indexmap/src/map.rs b/third_party/rust/indexmap/src/map.rs
@@ -16,7 +16,8 @@ mod tests;
pub use self::core::raw_entry_v1::{self, RawEntryApiV1};
pub use self::core::{Entry, IndexedEntry, OccupiedEntry, VacantEntry};
pub use self::iter::{
- Drain, IntoIter, IntoKeys, IntoValues, Iter, IterMut, IterMut2, Keys, Splice, Values, ValuesMut,
+ Drain, ExtractIf, IntoIter, IntoKeys, IntoValues, Iter, IterMut, IterMut2, Keys, Splice,
+ Values, ValuesMut,
};
pub use self::mutable::MutableEntryKey;
pub use self::mutable::MutableKeys;
@@ -36,9 +37,9 @@ use alloc::vec::Vec;
#[cfg(feature = "std")]
use std::collections::hash_map::RandomState;
-use self::core::IndexMapCore;
+pub(crate) use self::core::{ExtractCore, IndexMapCore};
use crate::util::{third, try_simplify_range};
-use crate::{Bucket, Entries, Equivalent, HashValue, TryReserveError};
+use crate::{Bucket, Equivalent, GetDisjointMutError, HashValue, TryReserveError};
/// A hash table where the iteration order of the key-value pairs is independent
/// of the hash values of the keys.
@@ -113,32 +114,6 @@ where
}
}
-impl<K, V, S> Entries for IndexMap<K, V, S> {
- type Entry = Bucket<K, V>;
-
- #[inline]
- fn into_entries(self) -> Vec<Self::Entry> {
- self.core.into_entries()
- }
-
- #[inline]
- fn as_entries(&self) -> &[Self::Entry] {
- self.core.as_entries()
- }
-
- #[inline]
- fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
- self.core.as_entries_mut()
- }
-
- fn with_entries<F>(&mut self, f: F)
- where
- F: FnOnce(&mut [Self::Entry]),
- {
- self.core.with_entries(f);
- }
-}
-
impl<K, V, S> fmt::Debug for IndexMap<K, V, S>
where
K: fmt::Debug,
@@ -205,6 +180,28 @@ impl<K, V, S> IndexMap<K, V, S> {
}
}
+ #[inline]
+ pub(crate) fn into_entries(self) -> Vec<Bucket<K, V>> {
+ self.core.into_entries()
+ }
+
+ #[inline]
+ pub(crate) fn as_entries(&self) -> &[Bucket<K, V>] {
+ self.core.as_entries()
+ }
+
+ #[inline]
+ pub(crate) fn as_entries_mut(&mut self) -> &mut [Bucket<K, V>] {
+ self.core.as_entries_mut()
+ }
+
+ pub(crate) fn with_entries<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Bucket<K, V>]),
+ {
+ self.core.with_entries(f);
+ }
+
/// Return the number of elements the map can hold without reallocating.
///
/// This number is a lower bound; the map might be able to hold more,
@@ -307,6 +304,55 @@ impl<K, V, S> IndexMap<K, V, S> {
Drain::new(self.core.drain(range))
}
+ /// Creates an iterator which uses a closure to determine if an element should be removed,
+ /// for all elements in the given range.
+ ///
+ /// If the closure returns true, the element is removed from the map and yielded.
+ /// If the closure returns false, or panics, the element remains in the map and will not be
+ /// yielded.
+ ///
+ /// Note that `extract_if` lets you mutate every value in the filter closure, regardless of
+ /// whether you choose to keep or remove it.
+ ///
+ /// The range may be any type that implements [`RangeBounds<usize>`],
+ /// including all of the `std::ops::Range*` types, or even a tuple pair of
+ /// `Bound` start and end values. To check the entire map, use `RangeFull`
+ /// like `map.extract_if(.., predicate)`.
+ ///
+ /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
+ /// or the iteration short-circuits, then the remaining elements will be retained.
+ /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
+ ///
+ /// [`retain`]: IndexMap::retain
+ ///
+ /// ***Panics*** if the starting point is greater than the end point or if
+ /// the end point is greater than the length of the map.
+ ///
+ /// # Examples
+ ///
+ /// Splitting a map into even and odd keys, reusing the original map:
+ ///
+ /// ```
+ /// use indexmap::IndexMap;
+ ///
+ /// let mut map: IndexMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
+ /// let extracted: IndexMap<i32, i32> = map.extract_if(.., |k, _v| k % 2 == 0).collect();
+ ///
+ /// let evens = extracted.keys().copied().collect::<Vec<_>>();
+ /// let odds = map.keys().copied().collect::<Vec<_>>();
+ ///
+ /// assert_eq!(evens, vec![0, 2, 4, 6]);
+ /// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// ```
+ #[track_caller]
+ pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, K, V, F>
+ where
+ F: FnMut(&K, &mut V) -> bool,
+ R: RangeBounds<usize>,
+ {
+ ExtractIf::new(&mut self.core, range, pred)
+ }
+
/// Splits the collection into two at the given index.
///
/// Returns a newly allocated map containing the elements in the range
@@ -447,6 +493,53 @@ where
}
}
+ /// Insert a key-value pair in the map at its ordered position among keys
+ /// sorted by `cmp`.
+ ///
+ /// This is equivalent to finding the position with
+ /// [`binary_search_by`][Self::binary_search_by], then calling
+ /// [`insert_before`][Self::insert_before] with the given key and value.
+ ///
+ /// If the existing keys are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the key-value
+ /// pair is moved to or inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by<F>(&mut self, key: K, value: V, mut cmp: F) -> (usize, Option<V>)
+ where
+ F: FnMut(&K, &V, &K, &V) -> Ordering,
+ {
+ let (Ok(i) | Err(i)) = self.binary_search_by(|k, v| cmp(k, v, &key, &value));
+ self.insert_before(i, key, value)
+ }
+
+ /// Insert a key-value pair in the map at its ordered position
+ /// using a sort-key extraction function.
+ ///
+ /// This is equivalent to finding the position with
+ /// [`binary_search_by_key`][Self::binary_search_by_key] with `sort_key(key)`, then
+ /// calling [`insert_before`][Self::insert_before] with the given key and value.
+ ///
+ /// If the existing keys are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the key-value
+ /// pair is moved to or inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by_key<B, F>(
+ &mut self,
+ key: K,
+ value: V,
+ mut sort_key: F,
+ ) -> (usize, Option<V>)
+ where
+ B: Ord,
+ F: FnMut(&K, &V) -> B,
+ {
+ let search_key = sort_key(&key, &value);
+ let (Ok(i) | Err(i)) = self.binary_search_by_key(&search_key, sort_key);
+ self.insert_before(i, key, value)
+ }
+
/// Insert a key-value pair in the map before the entry at the given index, or at the end.
///
/// If an equivalent key already exists in the map: the key remains and
@@ -606,7 +699,38 @@ where
}
}
- /// Get the given key’s corresponding entry in the map for insertion and/or
+ /// Replaces the key at the given index. The new key does not need to be
+ /// equivalent to the one it is replacing, but it must be unique to the rest
+ /// of the map.
+ ///
+ /// Returns `Ok(old_key)` if successful, or `Err((other_index, key))` if an
+ /// equivalent key already exists at a different index. The map will be
+ /// unchanged in the error case.
+ ///
+ /// Direct indexing can be used to change the corresponding value: simply
+ /// `map[index] = value`, or `mem::replace(&mut map[index], value)` to
+ /// retrieve the old value as well.
+ ///
+ /// ***Panics*** if `index` is out of bounds.
+ ///
+ /// Computes in **O(1)** time (average).
+ #[track_caller]
+ pub fn replace_index(&mut self, index: usize, key: K) -> Result<K, (usize, K)> {
+ // If there's a direct match, we don't even need to hash it.
+ let entry = &mut self.as_entries_mut()[index];
+ if key == entry.key {
+ return Ok(mem::replace(&mut entry.key, key));
+ }
+
+ let hash = self.hash(&key);
+ if let Some(i) = self.core.get_index_of(hash, &key) {
+ debug_assert_ne!(i, index);
+ return Err((i, key));
+ }
+ Ok(self.core.replace_index_unique(index, hash, key))
+ }
+
+ /// Get the given key's corresponding entry in the map for insertion and/or
/// in-place manipulation.
///
/// Computes in **O(1)** time (amortized average).
@@ -704,7 +828,7 @@ where
self.get_index_of(key).is_some()
}
- /// Return a reference to the value stored for `key`, if it is present,
+ /// Return a reference to the stored value for `key`, if it is present,
/// else `None`.
///
/// Computes in **O(1)** time (average).
@@ -720,7 +844,7 @@ where
}
}
- /// Return references to the key-value pair stored for `key`,
+ /// Return references to the stored key-value pair for the lookup `key`,
/// if it is present, else `None`.
///
/// Computes in **O(1)** time (average).
@@ -736,7 +860,10 @@ where
}
}
- /// Return item index, key and value
+ /// Return the index with references to the stored key-value pair for the
+ /// lookup `key`, if it is present, else `None`.
+ ///
+ /// Computes in **O(1)** time (average).
pub fn get_full<Q>(&self, key: &Q) -> Option<(usize, &K, &V)>
where
Q: ?Sized + Hash + Equivalent<K>,
@@ -749,7 +876,7 @@ where
}
}
- /// Return item index, if it exists in the map
+ /// Return the item index for `key`, if it is present, else `None`.
///
/// Computes in **O(1)** time (average).
pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>
@@ -766,6 +893,10 @@ where
}
}
+ /// Return a mutable reference to the stored value for `key`,
+ /// if it is present, else `None`.
+ ///
+ /// Computes in **O(1)** time (average).
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
Q: ?Sized + Hash + Equivalent<K>,
@@ -778,6 +909,26 @@ where
}
}
+ /// Return a reference and mutable references to the stored key-value pair
+ /// for the lookup `key`, if it is present, else `None`.
+ ///
+ /// Computes in **O(1)** time (average).
+ pub fn get_key_value_mut<Q>(&mut self, key: &Q) -> Option<(&K, &mut V)>
+ where
+ Q: ?Sized + Hash + Equivalent<K>,
+ {
+ if let Some(i) = self.get_index_of(key) {
+ let entry = &mut self.as_entries_mut()[i];
+ Some((&entry.key, &mut entry.value))
+ } else {
+ None
+ }
+ }
+
+ /// Return the index with a reference and mutable reference to the stored
+ /// key-value pair for the lookup `key`, if it is present, else `None`.
+ ///
+ /// Computes in **O(1)** time (average).
pub fn get_full_mut<Q>(&mut self, key: &Q) -> Option<(usize, &K, &mut V)>
where
Q: ?Sized + Hash + Equivalent<K>,
@@ -790,6 +941,32 @@ where
}
}
+ /// Return the values for `N` keys. If any key is duplicated, this function will panic.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// let mut map = indexmap::IndexMap::from([(1, 'a'), (3, 'b'), (2, 'c')]);
+ /// assert_eq!(map.get_disjoint_mut([&2, &1]), [Some(&mut 'c'), Some(&mut 'a')]);
+ /// ```
+ pub fn get_disjoint_mut<Q, const N: usize>(&mut self, keys: [&Q; N]) -> [Option<&mut V>; N]
+ where
+ Q: ?Sized + Hash + Equivalent<K>,
+ {
+ let indices = keys.map(|key| self.get_index_of(key));
+ match self.as_mut_slice().get_disjoint_opt_mut(indices) {
+ Err(GetDisjointMutError::IndexOutOfBounds) => {
+ unreachable!(
+ "Internal error: indices should never be OOB as we got them from get_index_of"
+ );
+ }
+ Err(GetDisjointMutError::OverlappingIndices) => {
+ panic!("duplicate keys found");
+ }
+ Ok(key_values) => key_values.map(|kv_opt| kv_opt.map(|kv| kv.1)),
+ }
+ }
+
/// Remove the key-value pair equivalent to `key` and return
/// its value.
///
@@ -973,7 +1150,7 @@ impl<K, V, S> IndexMap<K, V, S> {
self.core.retain_in_order(move |k, v| keep(k, v));
}
- /// Sort the map’s key-value pairs by the default ordering of the keys.
+ /// Sort the map's key-value pairs by the default ordering of the keys.
///
/// This is a stable sort -- but equivalent keys should not normally coexist in
/// a map at all, so [`sort_unstable_keys`][Self::sort_unstable_keys] is preferred
@@ -989,7 +1166,7 @@ impl<K, V, S> IndexMap<K, V, S> {
});
}
- /// Sort the map’s key-value pairs in place using the comparison
+ /// Sort the map's key-value pairs in place using the comparison
/// function `cmp`.
///
/// The comparison function receives two key and value pairs to compare (you
@@ -1019,6 +1196,20 @@ impl<K, V, S> IndexMap<K, V, S> {
IntoIter::new(entries)
}
+ /// Sort the map's key-value pairs in place using a sort-key extraction function.
+ ///
+ /// Computes in **O(n log n + c)** time and **O(n)** space where *n* is
+ /// the length of the map and *c* the capacity. The sort is stable.
+ pub fn sort_by_key<T, F>(&mut self, mut sort_key: F)
+ where
+ T: Ord,
+ F: FnMut(&K, &V) -> T,
+ {
+ self.with_entries(move |entries| {
+ entries.sort_by_key(move |a| sort_key(&a.key, &a.value));
+ });
+ }
+
/// Sort the map's key-value pairs by the default ordering of the keys, but
/// may not preserve the order of equal elements.
///
@@ -1063,7 +1254,21 @@ impl<K, V, S> IndexMap<K, V, S> {
IntoIter::new(entries)
}
- /// Sort the map’s key-value pairs in place using a sort-key extraction function.
+ /// Sort the map's key-value pairs in place using a sort-key extraction function.
+ ///
+ /// Computes in **O(n log n + c)** time where *n* is
+ /// the length of the map and *c* is the capacity. The sort is unstable.
+ pub fn sort_unstable_by_key<T, F>(&mut self, mut sort_key: F)
+ where
+ T: Ord,
+ F: FnMut(&K, &V) -> T,
+ {
+ self.with_entries(move |entries| {
+ entries.sort_unstable_by_key(move |a| sort_key(&a.key, &a.value));
+ });
+ }
+
+ /// Sort the map's key-value pairs in place using a sort-key extraction function.
///
/// During sorting, the function is called at most once per entry, by using temporary storage
/// to remember the results of its evaluation. The order of calls to the function is
@@ -1124,6 +1329,34 @@ impl<K, V, S> IndexMap<K, V, S> {
self.as_slice().binary_search_by_key(b, f)
}
+ /// Checks if the keys of this map are sorted.
+ #[inline]
+ pub fn is_sorted(&self) -> bool
+ where
+ K: PartialOrd,
+ {
+ self.as_slice().is_sorted()
+ }
+
+ /// Checks if this map is sorted using the given comparator function.
+ #[inline]
+ pub fn is_sorted_by<'a, F>(&'a self, cmp: F) -> bool
+ where
+ F: FnMut(&'a K, &'a V, &'a K, &'a V) -> bool,
+ {
+ self.as_slice().is_sorted_by(cmp)
+ }
+
+ /// Checks if this map is sorted using the given sort-key function.
+ #[inline]
+ pub fn is_sorted_by_key<'a, F, T>(&'a self, sort_key: F) -> bool
+ where
+ F: FnMut(&'a K, &'a V) -> T,
+ T: PartialOrd,
+ {
+ self.as_slice().is_sorted_by_key(sort_key)
+ }
+
/// Returns the index of the partition point of a sorted map according to the given predicate
/// (the index of the first element of the second partition).
///
@@ -1138,7 +1371,7 @@ impl<K, V, S> IndexMap<K, V, S> {
self.as_slice().partition_point(pred)
}
- /// Reverses the order of the map’s key-value pairs in place.
+ /// Reverses the order of the map's key-value pairs in place.
///
/// Computes in **O(n)** time and **O(1)** space.
pub fn reverse(&mut self) {
@@ -1196,6 +1429,23 @@ impl<K, V, S> IndexMap<K, V, S> {
Some(IndexedEntry::new(&mut self.core, index))
}
+ /// Get an array of `N` key-value pairs by `N` indices
+ ///
+ /// Valid indices are *0 <= index < self.len()* and each index needs to be unique.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// let mut map = indexmap::IndexMap::from([(1, 'a'), (3, 'b'), (2, 'c')]);
+ /// assert_eq!(map.get_disjoint_indices_mut([2, 0]), Ok([(&2, &mut 'c'), (&1, &mut 'a')]));
+ /// ```
+ pub fn get_disjoint_indices_mut<const N: usize>(
+ &mut self,
+ indices: [usize; N],
+ ) -> Result<[(&K, &mut V); N], GetDisjointMutError> {
+ self.as_mut_slice().get_disjoint_mut(indices)
+ }
+
/// Returns a slice of key-value pairs in the given range of indices.
///
/// Valid indices are `0 <= index < self.len()`.
@@ -1431,14 +1681,14 @@ impl<K, V, S> Index<usize> for IndexMap<K, V, S> {
///
/// ***Panics*** if `index` is out of bounds.
fn index(&self, index: usize) -> &V {
- self.get_index(index)
- .unwrap_or_else(|| {
- panic!(
- "index out of bounds: the len is {len} but the index is {index}",
- len = self.len()
- );
- })
- .1
+ if let Some((_, value)) = self.get_index(index) {
+ value
+ } else {
+ panic!(
+ "index out of bounds: the len is {len} but the index is {index}",
+ len = self.len()
+ );
+ }
}
}
@@ -1478,11 +1728,11 @@ impl<K, V, S> IndexMut<usize> for IndexMap<K, V, S> {
fn index_mut(&mut self, index: usize) -> &mut V {
let len: usize = self.len();
- self.get_index_mut(index)
- .unwrap_or_else(|| {
- panic!("index out of bounds: the len is {len} but the index is {index}");
- })
- .1
+ if let Some((_, value)) = self.get_index_mut(index) {
+ value
+ } else {
+ panic!("index out of bounds: the len is {len} but the index is {index}");
+ }
}
}
diff --git a/third_party/rust/indexmap/src/map/core.rs b/third_party/rust/indexmap/src/map/core.rs
@@ -8,23 +8,23 @@
//! However, we should probably not let this show in the public API or docs.
mod entry;
+mod extract;
pub mod raw_entry_v1;
-use hashbrown::hash_table;
-
-use crate::vec::{self, Vec};
-use crate::TryReserveError;
+use alloc::vec::{self, Vec};
use core::mem;
use core::ops::RangeBounds;
+use hashbrown::hash_table;
use crate::util::simplify_range;
-use crate::{Bucket, Equivalent, HashValue};
+use crate::{Bucket, Equivalent, HashValue, TryReserveError};
type Indices = hash_table::HashTable<usize>;
type Entries<K, V> = Vec<Bucket<K, V>>;
pub use entry::{Entry, IndexedEntry, OccupiedEntry, VacantEntry};
+pub(crate) use extract::ExtractCore;
/// Core of the map that does not depend on S
#[derive(Debug)]
@@ -109,33 +109,6 @@ where
}
}
-impl<K, V> crate::Entries for IndexMapCore<K, V> {
- type Entry = Bucket<K, V>;
-
- #[inline]
- fn into_entries(self) -> Vec<Self::Entry> {
- self.entries
- }
-
- #[inline]
- fn as_entries(&self) -> &[Self::Entry] {
- &self.entries
- }
-
- #[inline]
- fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
- &mut self.entries
- }
-
- fn with_entries<F>(&mut self, f: F)
- where
- F: FnOnce(&mut [Self::Entry]),
- {
- f(&mut self.entries);
- self.rebuild_hash_table();
- }
-}
-
impl<K, V> IndexMapCore<K, V> {
/// The maximum capacity before the `entries` allocation would exceed `isize::MAX`.
const MAX_ENTRIES_CAPACITY: usize = (isize::MAX as usize) / mem::size_of::<Bucket<K, V>>();
@@ -162,7 +135,31 @@ impl<K, V> IndexMapCore<K, V> {
}
#[inline]
+ pub(crate) fn into_entries(self) -> Entries<K, V> {
+ self.entries
+ }
+
+ #[inline]
+ pub(crate) fn as_entries(&self) -> &[Bucket<K, V>] {
+ &self.entries
+ }
+
+ #[inline]
+ pub(crate) fn as_entries_mut(&mut self) -> &mut [Bucket<K, V>] {
+ &mut self.entries
+ }
+
+ pub(crate) fn with_entries<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Bucket<K, V>]),
+ {
+ f(&mut self.entries);
+ self.rebuild_hash_table();
+ }
+
+ #[inline]
pub(crate) fn len(&self) -> usize {
+ debug_assert_eq!(self.entries.len(), self.indices.len());
self.indices.len()
}
@@ -388,6 +385,13 @@ impl<K, V> IndexMapCore<K, V> {
}
}
+ /// Replaces the key at the given index,
+ /// *without* checking whether it already exists.
+ #[track_caller]
+ pub(crate) fn replace_index_unique(&mut self, index: usize, hash: HashValue, key: K) -> K {
+ self.borrow_mut().replace_index_unique(index, hash, key).0
+ }
+
/// Remove an entry by shifting all entries that follow it
pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
where
@@ -564,6 +568,28 @@ impl<'a, K, V> RefMut<'a, K, V> {
OccupiedEntry::new(self.entries, entry)
}
+ /// Replaces the key at the given index,
+ /// *without* checking whether it already exists.
+ #[track_caller]
+ fn replace_index_unique(
+ self,
+ index: usize,
+ hash: HashValue,
+ key: K,
+ ) -> (K, OccupiedEntry<'a, K, V>) {
+ // NB: This removal and insertion isn't "no grow" (with unreachable hasher)
+ // because hashbrown's tombstones might force a resize anyway.
+ erase_index(self.indices, self.entries[index].hash, index);
+ let table_entry = self
+ .indices
+ .insert_unique(hash.get(), index, get_hash(&self.entries));
+
+ let entry = &mut self.entries[index];
+ entry.hash = hash;
+ let old_key = mem::replace(&mut entry.key, key);
+ (old_key, OccupiedEntry::new(self.entries, table_entry))
+ }
+
/// Insert a key-value pair in `entries` at a particular index,
/// *without* checking whether it already exists.
fn shift_insert_unique(&mut self, index: usize, hash: HashValue, key: K, value: V) {
diff --git a/third_party/rust/indexmap/src/map/core/entry.rs b/third_party/rust/indexmap/src/map/core/entry.rs
@@ -1,5 +1,6 @@
use super::{equivalent, Entries, IndexMapCore, RefMut};
use crate::HashValue;
+use core::cmp::Ordering;
use core::{fmt, mem};
use hashbrown::hash_table;
@@ -226,8 +227,8 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -237,7 +238,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -260,8 +261,8 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -272,7 +273,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -308,6 +309,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
/// ***Panics*** if the `other` index is out of bounds.
///
/// Computes in **O(1)** time (average).
+ #[track_caller]
pub fn swap_indices(self, other: usize) {
let index = self.index();
self.into_ref_mut().swap_indices(index, other);
@@ -401,17 +403,67 @@ impl<'a, K, V> VacantEntry<'a, K, V> {
(i, self.shift_insert(i, value))
}
+ /// Inserts the entry's key and the given value into the map at its ordered
+ /// position among keys sorted by `cmp`, and returns the new index and a
+ /// mutable reference to the value.
+ ///
+ /// If the existing keys are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the key-value
+ /// pair is inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by<F>(self, value: V, mut cmp: F) -> (usize, &'a mut V)
+ where
+ F: FnMut(&K, &V, &K, &V) -> Ordering,
+ {
+ let slice = crate::map::Slice::from_slice(self.map.entries);
+ let (Ok(i) | Err(i)) = slice.binary_search_by(|k, v| cmp(k, v, &self.key, &value));
+ (i, self.shift_insert(i, value))
+ }
+
+ /// Inserts the entry's key and the given value into the map at its ordered
+ /// position using a sort-key extraction function, and returns the new index
+ /// and a mutable reference to the value.
+ ///
+ /// If the existing keys are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the key-value
+ /// pair is inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by_key<B, F>(self, value: V, mut sort_key: F) -> (usize, &'a mut V)
+ where
+ B: Ord,
+ F: FnMut(&K, &V) -> B,
+ {
+ let search_key = sort_key(&self.key, &value);
+ let slice = crate::map::Slice::from_slice(self.map.entries);
+ let (Ok(i) | Err(i)) = slice.binary_search_by_key(&search_key, sort_key);
+ (i, self.shift_insert(i, value))
+ }
+
/// Inserts the entry's key and the given value into the map at the given index,
/// shifting others to the right, and returns a mutable reference to the value.
///
/// ***Panics*** if `index` is out of bounds.
///
/// Computes in **O(n)** time (average).
+ #[track_caller]
pub fn shift_insert(mut self, index: usize, value: V) -> &'a mut V {
self.map
.shift_insert_unique(index, self.hash, self.key, value);
&mut self.map.entries[index].value
}
+
+ /// Replaces the key at the given index with this entry's key, returning the
+ /// old key and an `OccupiedEntry` for that index.
+ ///
+ /// ***Panics*** if `index` is out of bounds.
+ ///
+ /// Computes in **O(1)** time (average).
+ #[track_caller]
+ pub fn replace_index(self, index: usize) -> (K, OccupiedEntry<'a, K, V>) {
+ self.map.replace_index_unique(index, self.hash, self.key)
+ }
}
impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
@@ -479,8 +531,8 @@ impl<'a, K, V> IndexedEntry<'a, K, V> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -490,7 +542,7 @@ impl<'a, K, V> IndexedEntry<'a, K, V> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -501,8 +553,8 @@ impl<'a, K, V> IndexedEntry<'a, K, V> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -512,7 +564,7 @@ impl<'a, K, V> IndexedEntry<'a, K, V> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -546,6 +598,7 @@ impl<'a, K, V> IndexedEntry<'a, K, V> {
/// ***Panics*** if the `other` index is out of bounds.
///
/// Computes in **O(1)** time (average).
+ #[track_caller]
pub fn swap_indices(mut self, other: usize) {
self.map.swap_indices(self.index, other);
}
diff --git a/third_party/rust/indexmap/src/map/core/extract.rs b/third_party/rust/indexmap/src/map/core/extract.rs
@@ -0,0 +1,108 @@
+#![allow(unsafe_code)]
+
+use super::{Bucket, IndexMapCore};
+use crate::util::simplify_range;
+
+use core::ops::RangeBounds;
+
+impl<K, V> IndexMapCore<K, V> {
+ #[track_caller]
+ pub(crate) fn extract<R>(&mut self, range: R) -> ExtractCore<'_, K, V>
+ where
+ R: RangeBounds<usize>,
+ {
+ let range = simplify_range(range, self.entries.len());
+
+ // SAFETY: We must have consistent lengths to start, so that's a hard assertion.
+ // Then the worst `set_len` can do is leak items if `ExtractCore` doesn't drop.
+ assert_eq!(self.entries.len(), self.indices.len());
+ unsafe {
+ self.entries.set_len(range.start);
+ }
+ ExtractCore {
+ map: self,
+ new_len: range.start,
+ current: range.start,
+ end: range.end,
+ }
+ }
+}
+
+pub(crate) struct ExtractCore<'a, K, V> {
+ map: &'a mut IndexMapCore<K, V>,
+ new_len: usize,
+ current: usize,
+ end: usize,
+}
+
+impl<K, V> Drop for ExtractCore<'_, K, V> {
+ fn drop(&mut self) {
+ let old_len = self.map.indices.len();
+ let mut new_len = self.new_len;
+
+ debug_assert!(new_len <= self.current);
+ debug_assert!(self.current <= self.end);
+ debug_assert!(self.current <= old_len);
+ debug_assert!(old_len <= self.map.entries.capacity());
+
+ // SAFETY: We assume `new_len` and `current` were correctly maintained by the iterator.
+ // So `entries[new_len..current]` were extracted, but the rest before and after are valid.
+ unsafe {
+ if new_len == self.current {
+ // Nothing was extracted, so any remaining items can be left in place.
+ new_len = old_len;
+ } else if self.current < old_len {
+ // Need to shift the remaining items down.
+ let tail_len = old_len - self.current;
+ let base = self.map.entries.as_mut_ptr();
+ let src = base.add(self.current);
+ let dest = base.add(new_len);
+ src.copy_to(dest, tail_len);
+ new_len += tail_len;
+ }
+ self.map.entries.set_len(new_len);
+ }
+
+ if new_len != old_len {
+ // We don't keep track of *which* items were extracted, so reindex everything.
+ self.map.rebuild_hash_table();
+ }
+ }
+}
+
+impl<K, V> ExtractCore<'_, K, V> {
+ pub(crate) fn extract_if<F>(&mut self, mut pred: F) -> Option<Bucket<K, V>>
+ where
+ F: FnMut(&mut Bucket<K, V>) -> bool,
+ {
+ debug_assert!(self.end <= self.map.entries.capacity());
+
+ let base = self.map.entries.as_mut_ptr();
+ while self.current < self.end {
+ // SAFETY: We're maintaining both indices within bounds of the original entries, so
+ // 0..new_len and current..indices.len() are always valid items for our Drop to keep.
+ unsafe {
+ let item = base.add(self.current);
+ if pred(&mut *item) {
+ // Extract it!
+ self.current += 1;
+ return Some(item.read());
+ } else {
+ // Keep it, shifting it down if needed.
+ if self.new_len != self.current {
+ debug_assert!(self.new_len < self.current);
+ let dest = base.add(self.new_len);
+ item.copy_to_nonoverlapping(dest, 1);
+ }
+ self.current += 1;
+ self.new_len += 1;
+ }
+ }
+ }
+ None
+ }
+
+ pub(crate) fn remaining(&self) -> usize {
+ self.end - self.current
+ }
+}
diff --git a/third_party/rust/indexmap/src/map/core/raw_entry_v1.rs b/third_party/rust/indexmap/src/map/core/raw_entry_v1.rs
@@ -498,8 +498,8 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -509,7 +509,7 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// Remove the key, value pair stored in the map for this entry, and return the value.
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -532,8 +532,8 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
- /// the last element of the map and popping it off.
+ /// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
+ /// with the last element of the map and popping it off.
/// **This perturbs the position of what used to be the last element!**
///
/// Computes in **O(1)** time (average).
@@ -544,7 +544,7 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// Remove and return the key, value pair stored in the map for this entry
///
- /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
+ /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
/// elements that follow it, preserving their relative order.
/// **This perturbs the index of all of those elements!**
///
@@ -566,6 +566,7 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// ***Panics*** if `to` is out of bounds.
///
/// Computes in **O(n)** time (average).
+ #[track_caller]
pub fn move_index(self, to: usize) {
let index = self.index();
self.into_ref_mut().move_index(index, to);
@@ -579,6 +580,7 @@ impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
/// ***Panics*** if the `other` index is out of bounds.
///
/// Computes in **O(1)** time (average).
+ #[track_caller]
pub fn swap_indices(self, other: usize) {
let index = self.index();
self.into_ref_mut().swap_indices(index, other);
@@ -629,6 +631,7 @@ impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
/// ***Panics*** if `index` is out of bounds.
///
/// Computes in **O(n)** time (average).
+ #[track_caller]
pub fn shift_insert(self, index: usize, key: K, value: V) -> (&'a mut K, &'a mut V)
where
K: Hash,
@@ -645,6 +648,7 @@ impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
/// ***Panics*** if `index` is out of bounds.
///
/// Computes in **O(n)** time (average).
+ #[track_caller]
pub fn shift_insert_hashed_nocheck(
mut self,
index: usize,
diff --git a/third_party/rust/indexmap/src/map/iter.rs b/third_party/rust/indexmap/src/map/iter.rs
@@ -1,5 +1,4 @@
-use super::core::IndexMapCore;
-use super::{Bucket, Entries, IndexMap, Slice};
+use super::{Bucket, ExtractCore, IndexMap, IndexMapCore, Slice};
use alloc::vec::{self, Vec};
use core::fmt;
@@ -774,3 +773,58 @@ where
.finish()
}
}
+
+/// An extracting iterator for `IndexMap`.
+///
+/// This `struct` is created by [`IndexMap::extract_if()`].
+/// See its documentation for more.
+pub struct ExtractIf<'a, K, V, F> {
+ inner: ExtractCore<'a, K, V>,
+ pred: F,
+}
+
+impl<K, V, F> ExtractIf<'_, K, V, F> {
+ #[track_caller]
+ pub(super) fn new<R>(core: &mut IndexMapCore<K, V>, range: R, pred: F) -> ExtractIf<'_, K, V, F>
+ where
+ R: RangeBounds<usize>,
+ F: FnMut(&K, &mut V) -> bool,
+ {
+ ExtractIf {
+ inner: core.extract(range),
+ pred,
+ }
+ }
+}
+
+impl<K, V, F> Iterator for ExtractIf<'_, K, V, F>
+where
+ F: FnMut(&K, &mut V) -> bool,
+{
+ type Item = (K, V);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.inner
+ .extract_if(|bucket| {
+ let (key, value) = bucket.ref_mut();
+ (self.pred)(key, value)
+ })
+ .map(Bucket::key_value)
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.inner.remaining()))
+ }
+}
+
+impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
+
+impl<K, V, F> fmt::Debug for ExtractIf<'_, K, V, F>
+where
+ K: fmt::Debug,
+ V: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("ExtractIf").finish_non_exhaustive()
+ }
+}
diff --git a/third_party/rust/indexmap/src/map/mutable.rs b/third_party/rust/indexmap/src/map/mutable.rs
@@ -1,8 +1,7 @@
use core::hash::{BuildHasher, Hash};
use super::{
- Bucket, Entries, Entry, Equivalent, IndexMap, IndexedEntry, IterMut2, OccupiedEntry,
- VacantEntry,
+ Bucket, Entry, Equivalent, IndexMap, IndexedEntry, IterMut2, OccupiedEntry, VacantEntry,
};
/// Opt-in mutable access to [`IndexMap`] keys.
@@ -10,7 +9,7 @@ use super::{
/// These methods expose `&mut K`, mutable references to the key as it is stored
/// in the map.
/// You are allowed to modify the keys in the map **if the modification
-/// does not change the key’s hash and equality**.
+/// does not change the key's hash and equality**.
///
/// If keys are modified erroneously, you can no longer look them up.
/// This is sound (memory safe) but a logical error hazard (just like
@@ -95,7 +94,7 @@ where
/// These methods expose `&mut K`, mutable references to the key as it is stored
/// in the map.
/// You are allowed to modify the keys in the map **if the modification
-/// does not change the key’s hash and equality**.
+/// does not change the key's hash and equality**.
///
/// If keys are modified erroneously, you can no longer look them up.
/// This is sound (memory safe) but a logical error hazard (just like
diff --git a/third_party/rust/indexmap/src/map/serde_seq.rs b/third_party/rust/indexmap/src/map/serde_seq.rs
@@ -9,7 +9,7 @@
//!
//! ```
//! # use indexmap::IndexMap;
-//! # use serde_derive::{Deserialize, Serialize};
+//! # use serde::{Deserialize, Serialize};
//! #[derive(Deserialize, Serialize)]
//! struct Data {
//! #[serde(with = "indexmap::map::serde_seq")]
@@ -18,8 +18,8 @@
//! }
//! ```
-use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
-use serde::ser::{Serialize, Serializer};
+use serde_core::de::{Deserialize, Deserializer, SeqAccess, Visitor};
+use serde_core::ser::{Serialize, Serializer};
use core::fmt::{self, Formatter};
use core::hash::{BuildHasher, Hash};
@@ -66,7 +66,7 @@ where
///
/// ```
/// # use indexmap::IndexMap;
-/// # use serde_derive::Serialize;
+/// # use serde::Serialize;
/// #[derive(Serialize)]
/// struct Data {
/// #[serde(serialize_with = "indexmap::map::serde_seq::serialize")]
@@ -119,7 +119,7 @@ where
///
/// ```
/// # use indexmap::IndexMap;
-/// # use serde_derive::Deserialize;
+/// # use serde::Deserialize;
/// #[derive(Deserialize)]
/// struct Data {
/// #[serde(deserialize_with = "indexmap::map::serde_seq::deserialize")]
diff --git a/third_party/rust/indexmap/src/map/slice.rs b/third_party/rust/indexmap/src/map/slice.rs
@@ -1,8 +1,8 @@
use super::{
- Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values,
- ValuesMut,
+ Bucket, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, ValuesMut,
};
use crate::util::{slice_eq, try_simplify_range};
+use crate::GetDisjointMutError;
use alloc::boxed::Box;
use alloc::vec::Vec;
@@ -124,6 +124,7 @@ impl<K, V> Slice<K, V> {
/// Divides one slice into two at an index.
///
/// ***Panics*** if `index > len`.
+ #[track_caller]
pub fn split_at(&self, index: usize) -> (&Self, &Self) {
let (first, second) = self.entries.split_at(index);
(Self::from_slice(first), Self::from_slice(second))
@@ -132,6 +133,7 @@ impl<K, V> Slice<K, V> {
/// Divides one mutable slice into two at an index.
///
/// ***Panics*** if `index > len`.
+ #[track_caller]
pub fn split_at_mut(&mut self, index: usize) -> (&mut Self, &mut Self) {
let (first, second) = self.entries.split_at_mut(index);
(Self::from_mut_slice(first), Self::from_mut_slice(second))
@@ -256,6 +258,55 @@ impl<K, V> Slice<K, V> {
self.binary_search_by(|k, v| f(k, v).cmp(b))
}
+ /// Checks if the keys of this slice are sorted.
+ #[inline]
+ pub fn is_sorted(&self) -> bool
+ where
+ K: PartialOrd,
+ {
+ // TODO(MSRV 1.82): self.entries.is_sorted_by(|a, b| a.key <= b.key)
+ self.is_sorted_by_key(|k, _| k)
+ }
+
+ /// Checks if this slice is sorted using the given comparator function.
+ #[inline]
+ pub fn is_sorted_by<'a, F>(&'a self, mut cmp: F) -> bool
+ where
+ F: FnMut(&'a K, &'a V, &'a K, &'a V) -> bool,
+ {
+ // TODO(MSRV 1.82): self.entries
+ // .is_sorted_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value))
+ let mut iter = self.entries.iter();
+ match iter.next() {
+ Some(mut prev) => iter.all(move |next| {
+ let sorted = cmp(&prev.key, &prev.value, &next.key, &next.value);
+ prev = next;
+ sorted
+ }),
+ None => true,
+ }
+ }
+
+ /// Checks if this slice is sorted using the given sort-key function.
+ #[inline]
+ pub fn is_sorted_by_key<'a, F, T>(&'a self, mut sort_key: F) -> bool
+ where
+ F: FnMut(&'a K, &'a V) -> T,
+ T: PartialOrd,
+ {
+ // TODO(MSRV 1.82): self.entries
+ // .is_sorted_by_key(move |a| sort_key(&a.key, &a.value))
+ let mut iter = self.entries.iter().map(move |a| sort_key(&a.key, &a.value));
+ match iter.next() {
+ Some(mut prev) => iter.all(move |next| {
+ let sorted = prev <= next;
+ prev = next;
+ sorted
+ }),
+ None => true,
+ }
+ }
+
/// Returns the index of the partition point of a sorted map according to the given predicate
/// (the index of the first element of the second partition).
///
@@ -270,6 +321,51 @@ impl<K, V> Slice<K, V> {
self.entries
.partition_point(move |a| pred(&a.key, &a.value))
}
+
+ /// Get an array of `N` key-value pairs by `N` indices
+ ///
+ /// Valid indices are *0 <= index < self.len()* and each index needs to be unique.
+ pub fn get_disjoint_mut<const N: usize>(
+ &mut self,
+ indices: [usize; N],
+ ) -> Result<[(&K, &mut V); N], GetDisjointMutError> {
+ let indices = indices.map(Some);
+ let key_values = self.get_disjoint_opt_mut(indices)?;
+ Ok(key_values.map(Option::unwrap))
+ }
+
+ #[allow(unsafe_code)]
+ pub(crate) fn get_disjoint_opt_mut<const N: usize>(
+ &mut self,
+ indices: [Option<usize>; N],
+ ) -> Result<[Option<(&K, &mut V)>; N], GetDisjointMutError> {
+ // SAFETY: Can't allow duplicate indices as we would return several mutable refs to the same data.
+ let len = self.len();
+ for i in 0..N {
+ if let Some(idx) = indices[i] {
+ if idx >= len {
+ return Err(GetDisjointMutError::IndexOutOfBounds);
+ } else if indices[..i].contains(&Some(idx)) {
+ return Err(GetDisjointMutError::OverlappingIndices);
+ }
+ }
+ }
+
+ let entries_ptr = self.entries.as_mut_ptr();
+ let out = indices.map(|idx_opt| {
+ match idx_opt {
+ Some(idx) => {
+ // SAFETY: The base pointer is valid as it comes from a slice and the reference is always
+ // in-bounds & unique as we've already checked the indices above.
+ let kv = unsafe { (*(entries_ptr.add(idx))).ref_mut() };
+ Some(kv)
+ }
+ None => None,
+ }
+ });
+
+ Ok(out)
+ }
}
impl<'a, K, V> IntoIterator for &'a Slice<K, V> {
@@ -582,4 +678,123 @@ mod tests {
}
}
}
+
+ #[test]
+ fn slice_new() {
+ let slice: &Slice<i32, i32> = Slice::new();
+ assert!(slice.is_empty());
+ assert_eq!(slice.len(), 0);
+ }
+
+ #[test]
+ fn slice_new_mut() {
+ let slice: &mut Slice<i32, i32> = Slice::new_mut();
+ assert!(slice.is_empty());
+ assert_eq!(slice.len(), 0);
+ }
+
+ #[test]
+ fn slice_get_index_mut() {
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+
+ {
+ let (key, value) = slice.get_index_mut(0).unwrap();
+ assert_eq!(*key, 0);
+ assert_eq!(*value, 0);
+
+ *value = 11;
+ }
+
+ assert_eq!(slice[0], 11);
+
+ {
+ let result = slice.get_index_mut(11);
+ assert!(result.is_none());
+ }
+ }
+
+ #[test]
+ fn slice_split_first() {
+ let slice: &mut Slice<i32, i32> = Slice::new_mut();
+ let result = slice.split_first();
+ assert!(result.is_none());
+
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+
+ {
+ let (first, rest) = slice.split_first().unwrap();
+ assert_eq!(first, (&0, &0));
+ assert_eq!(rest.len(), 9);
+ }
+ assert_eq!(slice.len(), 10);
+ }
+
+ #[test]
+ fn slice_split_first_mut() {
+ let slice: &mut Slice<i32, i32> = Slice::new_mut();
+ let result = slice.split_first_mut();
+ assert!(result.is_none());
+
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+
+ {
+ let (first, rest) = slice.split_first_mut().unwrap();
+ assert_eq!(first, (&0, &mut 0));
+ assert_eq!(rest.len(), 9);
+
+ *first.1 = 11;
+ }
+ assert_eq!(slice.len(), 10);
+ assert_eq!(slice[0], 11);
+ }
+
+ #[test]
+ fn slice_split_last() {
+ let slice: &mut Slice<i32, i32> = Slice::new_mut();
+ let result = slice.split_last();
+ assert!(result.is_none());
+
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+
+ {
+ let (last, rest) = slice.split_last().unwrap();
+ assert_eq!(last, (&9, &81));
+ assert_eq!(rest.len(), 9);
+ }
+ assert_eq!(slice.len(), 10);
+ }
+
+ #[test]
+ fn slice_split_last_mut() {
+ let slice: &mut Slice<i32, i32> = Slice::new_mut();
+ let result = slice.split_last_mut();
+ assert!(result.is_none());
+
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+
+ {
+ let (last, rest) = slice.split_last_mut().unwrap();
+ assert_eq!(last, (&9, &mut 81));
+ assert_eq!(rest.len(), 9);
+
+ *last.1 = 100;
+ }
+
+ assert_eq!(slice.len(), 10);
+ assert_eq!(slice[slice.len() - 1], 100);
+ }
+
+ #[test]
+ fn slice_get_range() {
+ let mut map: IndexMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
+ let slice: &mut Slice<i32, i32> = map.as_mut_slice();
+ let subslice = slice.get_range(3..6).unwrap();
+ assert_eq!(subslice.len(), 3);
+ assert_eq!(subslice, &[(3, 9), (4, 16), (5, 25)]);
+ }
}
diff --git a/third_party/rust/indexmap/src/map/tests.rs b/third_party/rust/indexmap/src/map/tests.rs
@@ -594,6 +594,226 @@ fn iter_default() {
}
#[test]
+fn get_index_mut2() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.insert(1, 2);
+ map.insert(3, 4);
+ map.insert(5, 6);
+
+ {
+ let (key, value) = map.get_index_mut2(0).unwrap();
+ assert_eq!(*key, 1);
+ assert_eq!(*value, 2);
+
+ *value = 7;
+ }
+ assert_eq!(map[0], 7);
+
+ {
+ let (key, _) = map.get_index_mut2(0).unwrap();
+ *key = 8;
+ }
+ assert_eq!(map.get_index(0).unwrap().0, &8);
+}
+
+#[test]
+fn shift_shift_remove_index() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.insert(1, 2);
+ map.insert(3, 4);
+ map.insert(5, 6);
+ map.insert(7, 8);
+ map.insert(9, 10);
+
+ let result = map.shift_remove_index(1);
+ assert_eq!(result, Some((3, 4)));
+ assert_eq!(map.len(), 4);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8), (9, 10)]);
+
+ let result = map.shift_remove_index(1);
+ assert_eq!(result, Some((5, 6)));
+ assert_eq!(map.len(), 3);
+ assert_eq!(map.as_slice(), &[(1, 2), (7, 8), (9, 10)]);
+
+ let result = map.shift_remove_index(2);
+ assert_eq!(result, Some((9, 10)));
+ assert_eq!(map.len(), 2);
+ assert_eq!(map.as_slice(), &[(1, 2), (7, 8)]);
+
+ let result = map.shift_remove_index(2);
+ assert_eq!(result, None);
+ assert_eq!(map.len(), 2);
+ assert_eq!(map.as_slice(), &[(1, 2), (7, 8)]);
+}
+
+#[test]
+fn shift_remove_entry() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.insert(1, 2);
+ map.insert(3, 4);
+ map.insert(5, 6);
+ map.insert(7, 8);
+ map.insert(9, 10);
+
+ let result = map.shift_remove_entry(&3);
+ assert_eq!(result, Some((3, 4)));
+ assert_eq!(map.len(), 4);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8), (9, 10)]);
+
+ let result = map.shift_remove_entry(&9);
+ assert_eq!(result, Some((9, 10)));
+ assert_eq!(map.len(), 3);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8)]);
+
+ let result = map.shift_remove_entry(&9);
+ assert_eq!(result, None);
+ assert_eq!(map.len(), 3);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8)]);
+}
+
+#[test]
+fn shift_remove_full() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.insert(1, 2);
+ map.insert(3, 4);
+ map.insert(5, 6);
+ map.insert(7, 8);
+ map.insert(9, 10);
+
+ let result = map.shift_remove_full(&3);
+ assert_eq!(result, Some((1, 3, 4)));
+ assert_eq!(map.len(), 4);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8), (9, 10)]);
+
+ let result = map.shift_remove_full(&9);
+ assert_eq!(result, Some((3, 9, 10)));
+ assert_eq!(map.len(), 3);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8)]);
+
+ let result = map.shift_remove_full(&9);
+ assert_eq!(result, None);
+ assert_eq!(map.len(), 3);
+ assert_eq!(map.as_slice(), &[(1, 2), (5, 6), (7, 8)]);
+}
+
+#[test]
+fn sorted_unstable_by() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.extend(vec![(1, 10), (2, 20), (3, 30), (4, 40), (5, 50)]);
+ let sorted = map.sorted_unstable_by(|_a, b, _c, d| d.cmp(&b));
+
+ assert_eq!(
+ sorted.as_slice(),
+ &[(5, 50), (4, 40), (3, 30), (2, 20), (1, 10)]
+ );
+}
+
+#[test]
+fn into_boxed_slice() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ for i in 0..5 {
+ map.insert(i, i * 10);
+ }
+ let boxed_slice: Box<Slice<i32, i32>> = map.into_boxed_slice();
+ assert_eq!(boxed_slice.len(), 5);
+ assert_eq!(
+ boxed_slice.as_ref(),
+ &[(0, 0), (1, 10), (2, 20), (3, 30), (4, 40)]
+ );
+}
+
+#[test]
+fn last_mut() {
+ let mut map: IndexMap<&str, i32> = IndexMap::new();
+
+ let last_entry = map.last_mut();
+ assert_eq!(last_entry, None);
+
+ map.insert("key1", 1);
+ map.insert("key2", 2);
+ map.insert("key3", 3);
+ let last_entry = map.last_mut();
+ assert_eq!(last_entry, Some((&"key3", &mut 3)));
+
+ *last_entry.unwrap().1 = 4;
+ assert_eq!(map.get("key3"), Some(&4));
+}
+
+#[test]
+#[should_panic = "index out of bounds"]
+fn insert_before_oob() {
+ let mut map: IndexMap<char, ()> = IndexMap::new();
+ let _ = map.insert_before(0, 'a', ());
+ let _ = map.insert_before(1, 'b', ());
+ map.insert_before(3, 'd', ());
+}
+
+#[test]
+fn clear() {
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ map.extend(vec![(1, 10), (2, 20), (3, 30), (4, 40), (5, 50)]);
+ map.clear();
+ assert_eq!(map.len(), 0);
+}
+
+#[test]
+fn get_range() {
+ let mut index_map: IndexMap<i32, i32> = IndexMap::new();
+ index_map.insert(1, 10);
+ index_map.insert(2, 20);
+ index_map.insert(3, 30);
+ index_map.insert(4, 40);
+ index_map.insert(5, 50);
+
+ let result = index_map.get_range(2..2);
+ assert!(result.unwrap().is_empty());
+
+ let result = index_map.get_range(4..2);
+ assert!(result.is_none());
+
+ let result = index_map.get_range(2..4);
+ let slice: &Slice<i32, i32> = result.unwrap();
+ assert_eq!(slice.len(), 2);
+ assert_eq!(slice, &[(3, 30), (4, 40)]);
+}
+
+#[test]
+fn get_range_mut() {
+ let mut index_map: IndexMap<i32, i32> = IndexMap::new();
+ index_map.insert(1, 10);
+ index_map.insert(2, 20);
+ index_map.insert(3, 30);
+ index_map.insert(4, 40);
+ index_map.insert(5, 50);
+
+ let result = index_map.get_range_mut(2..2);
+ assert!(result.unwrap().is_empty());
+
+ let result = index_map.get_range_mut(4..2);
+ assert!(result.is_none());
+
+ let result = index_map.get_range_mut(2..4);
+ let slice: &mut Slice<i32, i32> = result.unwrap();
+ assert_eq!(slice.len(), 2);
+ assert_eq!(slice, &mut [(3, 30), (4, 40)]);
+
+ for i in 0..slice.len() {
+ slice[i] += 1;
+ }
+ assert_eq!(slice, &mut [(3, 31), (4, 41)]);
+}
+
+#[test]
+#[should_panic = "index out of bounds"]
+fn shift_insert_oob() {
+ let mut map: IndexMap<u32, u32> = IndexMap::new();
+ map.shift_insert(0, 1, 10);
+ map.shift_insert(1, 2, 20);
+ map.shift_insert(2, 3, 30);
+ map.shift_insert(5, 4, 40);
+}
+
+#[test]
fn test_binary_search_by() {
// adapted from std's test for binary_search
let b: IndexMap<_, i32> = []
@@ -828,3 +1048,265 @@ move_index_oob!(test_move_index_out_of_bounds_0_10, 0, 10);
move_index_oob!(test_move_index_out_of_bounds_0_max, 0, usize::MAX);
move_index_oob!(test_move_index_out_of_bounds_10_0, 10, 0);
move_index_oob!(test_move_index_out_of_bounds_max_0, usize::MAX, 0);
+
+#[test]
+fn disjoint_mut_empty_map() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ assert_eq!(
+ map.get_disjoint_mut([&0, &1, &2, &3]),
+ [None, None, None, None]
+ );
+}
+
+#[test]
+fn disjoint_mut_empty_param() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ assert_eq!(map.get_disjoint_mut([] as [&u32; 0]), []);
+}
+
+#[test]
+fn disjoint_mut_single_fail() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ assert_eq!(map.get_disjoint_mut([&0]), [None]);
+}
+
+#[test]
+fn disjoint_mut_single_success() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ assert_eq!(map.get_disjoint_mut([&1]), [Some(&mut 10)]);
+}
+
+#[test]
+fn disjoint_mut_multi_success() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 100);
+ map.insert(2, 200);
+ map.insert(3, 300);
+ map.insert(4, 400);
+ assert_eq!(
+ map.get_disjoint_mut([&1, &2]),
+ [Some(&mut 100), Some(&mut 200)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut([&1, &3]),
+ [Some(&mut 100), Some(&mut 300)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut([&3, &1, &4, &2]),
+ [
+ Some(&mut 300),
+ Some(&mut 100),
+ Some(&mut 400),
+ Some(&mut 200)
+ ]
+ );
+}
+
+#[test]
+fn disjoint_mut_multi_success_unsized_key() {
+ let mut map: IndexMap<&'static str, u32> = IndexMap::default();
+ map.insert("1", 100);
+ map.insert("2", 200);
+ map.insert("3", 300);
+ map.insert("4", 400);
+
+ assert_eq!(
+ map.get_disjoint_mut(["1", "2"]),
+ [Some(&mut 100), Some(&mut 200)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut(["1", "3"]),
+ [Some(&mut 100), Some(&mut 300)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut(["3", "1", "4", "2"]),
+ [
+ Some(&mut 300),
+ Some(&mut 100),
+ Some(&mut 400),
+ Some(&mut 200)
+ ]
+ );
+}
+
+#[test]
+fn disjoint_mut_multi_success_borrow_key() {
+ let mut map: IndexMap<String, u32> = IndexMap::default();
+ map.insert("1".into(), 100);
+ map.insert("2".into(), 200);
+ map.insert("3".into(), 300);
+ map.insert("4".into(), 400);
+
+ assert_eq!(
+ map.get_disjoint_mut(["1", "2"]),
+ [Some(&mut 100), Some(&mut 200)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut(["1", "3"]),
+ [Some(&mut 100), Some(&mut 300)]
+ );
+ assert_eq!(
+ map.get_disjoint_mut(["3", "1", "4", "2"]),
+ [
+ Some(&mut 300),
+ Some(&mut 100),
+ Some(&mut 400),
+ Some(&mut 200)
+ ]
+ );
+}
+
+#[test]
+fn disjoint_mut_multi_fail_missing() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 100);
+ map.insert(2, 200);
+ map.insert(3, 300);
+ map.insert(4, 400);
+
+ assert_eq!(map.get_disjoint_mut([&1, &5]), [Some(&mut 100), None]);
+ assert_eq!(map.get_disjoint_mut([&5, &6]), [None, None]);
+ assert_eq!(
+ map.get_disjoint_mut([&1, &5, &4]),
+ [Some(&mut 100), None, Some(&mut 400)]
+ );
+}
+
+#[test]
+#[should_panic]
+fn disjoint_mut_multi_fail_duplicate_panic() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 100);
+ map.get_disjoint_mut([&1, &2, &1]);
+}
+
+#[test]
+fn disjoint_indices_mut_fail_oob() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ map.insert(321, 20);
+ assert_eq!(
+ map.get_disjoint_indices_mut([1, 3]),
+ Err(crate::GetDisjointMutError::IndexOutOfBounds)
+ );
+}
+
+#[test]
+fn disjoint_indices_mut_empty() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ map.insert(321, 20);
+ assert_eq!(map.get_disjoint_indices_mut([]), Ok([]));
+}
+
+#[test]
+fn disjoint_indices_mut_success() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ map.insert(321, 20);
+ assert_eq!(map.get_disjoint_indices_mut([0]), Ok([(&1, &mut 10)]));
+
+ assert_eq!(map.get_disjoint_indices_mut([1]), Ok([(&321, &mut 20)]));
+ assert_eq!(
+ map.get_disjoint_indices_mut([0, 1]),
+ Ok([(&1, &mut 10), (&321, &mut 20)])
+ );
+}
+
+#[test]
+fn disjoint_indices_mut_fail_duplicate() {
+ let mut map: IndexMap<u32, u32> = IndexMap::default();
+ map.insert(1, 10);
+ map.insert(321, 20);
+ assert_eq!(
+ map.get_disjoint_indices_mut([1, 0, 1]),
+ Err(crate::GetDisjointMutError::OverlappingIndices)
+ );
+}
+
+#[test]
+fn insert_sorted_by_key() {
+ let mut values = [(-1, 8), (3, 18), (-27, 2), (-2, 5)];
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ for (key, value) in values {
+ let (_, old) = map.insert_sorted_by_key(key, value, |k, _| k.abs());
+ assert_eq!(old, None);
+ }
+ values.sort_by_key(|(key, _)| key.abs());
+ assert_eq!(values, *map.as_slice());
+
+ for (key, value) in &mut values {
+ let (_, old) = map.insert_sorted_by_key(*key, -*value, |k, _| k.abs());
+ assert_eq!(old, Some(*value));
+ *value = -*value;
+ }
+ assert_eq!(values, *map.as_slice());
+}
+
+#[test]
+fn insert_sorted_by() {
+ let mut values = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)];
+ let mut map: IndexMap<i32, i32> = IndexMap::new();
+ for (key, value) in values {
+ let (_, old) = map.insert_sorted_by(key, value, |key1, _, key2, _| key2.cmp(key1));
+ assert_eq!(old, None);
+ }
+ values.reverse();
+ assert_eq!(values, *map.as_slice());
+
+ for (key, value) in &mut values {
+ let (_, old) = map.insert_sorted_by(*key, -*value, |key1, _, key2, _| key2.cmp(key1));
+ assert_eq!(old, Some(*value));
+ *value = -*value;
+ }
+ assert_eq!(values, *map.as_slice());
+}
+
+#[test]
+fn is_sorted() {
+ fn expect(map: &IndexMap<i32, i32>, e: [bool; 7]) {
+ assert_eq!(e[0], map.is_sorted());
+ assert_eq!(e[1], map.is_sorted_by(|k1, _, k2, _| k1 < k2));
+ assert_eq!(e[2], map.is_sorted_by(|k1, _, k2, _| k1 > k2));
+ assert_eq!(e[3], map.is_sorted_by(|_, v1, _, v2| v1 < v2));
+ assert_eq!(e[4], map.is_sorted_by(|_, v1, _, v2| v1 > v2));
+ assert_eq!(e[5], map.is_sorted_by_key(|k, _| k));
+ assert_eq!(e[6], map.is_sorted_by_key(|_, v| v));
+ }
+
+ let mut map = IndexMap::from_iter((0..10).map(|i| (i, i * i)));
+ expect(&map, [true, true, false, true, false, true, true]);
+
+ map[5] = -1;
+ expect(&map, [true, true, false, false, false, true, false]);
+
+ map[5] = 25;
+ map.replace_index(5, -1).unwrap();
+ expect(&map, [false, false, false, true, false, false, true]);
+}
+
+#[test]
+fn is_sorted_trivial() {
+ fn expect(map: &IndexMap<i32, i32>, e: [bool; 5]) {
+ assert_eq!(e[0], map.is_sorted());
+ assert_eq!(e[1], map.is_sorted_by(|_, _, _, _| true));
+ assert_eq!(e[2], map.is_sorted_by(|_, _, _, _| false));
+ assert_eq!(e[3], map.is_sorted_by_key(|_, _| 0f64));
+ assert_eq!(e[4], map.is_sorted_by_key(|_, _| f64::NAN));
+ }
+
+ let mut map = IndexMap::new();
+ expect(&map, [true, true, true, true, true]);
+
+ map.insert(0, 0);
+ expect(&map, [true, true, true, true, true]);
+
+ map.insert(1, 1);
+ expect(&map, [true, true, false, true, false]);
+
+ map.reverse();
+ expect(&map, [false, true, false, true, false]);
+}
diff --git a/third_party/rust/indexmap/src/rayon/map.rs b/third_party/rust/indexmap/src/rayon/map.rs
@@ -7,8 +7,8 @@ use super::collect;
use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer};
use rayon::prelude::*;
-use crate::vec::Vec;
use alloc::boxed::Box;
+use alloc::vec::Vec;
use core::cmp::Ordering;
use core::fmt;
use core::hash::{BuildHasher, Hash};
@@ -16,7 +16,6 @@ use core::ops::RangeBounds;
use crate::map::Slice;
use crate::Bucket;
-use crate::Entries;
use crate::IndexMap;
impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S>
@@ -411,7 +410,7 @@ where
K: Send,
V: Send,
{
- /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys.
+ /// Sort the map's key-value pairs in parallel, by the default ordering of the keys.
pub fn par_sort_keys(&mut self)
where
K: Ord,
@@ -421,7 +420,7 @@ where
});
}
- /// Sort the map’s key-value pairs in place and in parallel, using the comparison
+ /// Sort the map's key-value pairs in place and in parallel, using the comparison
/// function `cmp`.
///
/// The comparison function receives two key and value pairs to compare (you
@@ -446,6 +445,18 @@ where
IntoParIter { entries }
}
+ /// Sort the map's key-value pairs in place and in parallel, using a sort-key extraction
+ /// function.
+ pub fn par_sort_by_key<T, F>(&mut self, sort_key: F)
+ where
+ T: Ord,
+ F: Fn(&K, &V) -> T + Sync,
+ {
+ self.with_entries(move |entries| {
+ entries.par_sort_by_key(move |a| sort_key(&a.key, &a.value));
+ });
+ }
+
/// Sort the map's key-value pairs in parallel, by the default ordering of the keys.
pub fn par_sort_unstable_keys(&mut self)
where
@@ -481,7 +492,19 @@ where
IntoParIter { entries }
}
- /// Sort the map’s key-value pairs in place and in parallel, using a sort-key extraction
+ /// Sort the map's key-value pairs in place and in parallel, using a sort-key extraction
+ /// function.
+ pub fn par_sort_unstable_by_key<T, F>(&mut self, sort_key: F)
+ where
+ T: Ord,
+ F: Fn(&K, &V) -> T + Sync,
+ {
+ self.with_entries(move |entries| {
+ entries.par_sort_unstable_by_key(move |a| sort_key(&a.key, &a.value));
+ });
+ }
+
+ /// Sort the map's key-value pairs in place and in parallel, using a sort-key extraction
/// function.
pub fn par_sort_by_cached_key<T, F>(&mut self, sort_key: F)
where
diff --git a/third_party/rust/indexmap/src/rayon/mod.rs b/third_party/rust/indexmap/src/rayon/mod.rs
@@ -3,8 +3,7 @@
use rayon::prelude::*;
use alloc::collections::LinkedList;
-
-use crate::vec::Vec;
+use alloc::vec::Vec;
pub mod map;
pub mod set;
diff --git a/third_party/rust/indexmap/src/rayon/set.rs b/third_party/rust/indexmap/src/rayon/set.rs
@@ -7,15 +7,14 @@ use super::collect;
use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer};
use rayon::prelude::*;
-use crate::vec::Vec;
use alloc::boxed::Box;
+use alloc::vec::Vec;
use core::cmp::Ordering;
use core::fmt;
use core::hash::{BuildHasher, Hash};
use core::ops::RangeBounds;
use crate::set::Slice;
-use crate::Entries;
use crate::IndexSet;
type Bucket<T> = crate::Bucket<T, ()>;
@@ -486,7 +485,7 @@ impl<T, S> IndexSet<T, S>
where
T: Send,
{
- /// Sort the set’s values in parallel by their default ordering.
+ /// Sort the set's values in parallel by their default ordering.
pub fn par_sort(&mut self)
where
T: Ord,
@@ -496,7 +495,7 @@ where
});
}
- /// Sort the set’s values in place and in parallel, using the comparison function `cmp`.
+ /// Sort the set's values in place and in parallel, using the comparison function `cmp`.
pub fn par_sort_by<F>(&mut self, cmp: F)
where
F: Fn(&T, &T) -> Ordering + Sync,
@@ -517,6 +516,17 @@ where
IntoParIter { entries }
}
+ /// Sort the set's values in place and in parallel, using a key extraction function.
+ pub fn par_sort_by_key<K, F>(&mut self, sort_key: F)
+ where
+ K: Ord,
+ F: Fn(&T) -> K + Sync,
+ {
+ self.with_entries(move |entries| {
+ entries.par_sort_by_key(move |a| sort_key(&a.key));
+ });
+ }
+
/// Sort the set's values in parallel by their default ordering.
pub fn par_sort_unstable(&mut self)
where
@@ -527,7 +537,7 @@ where
});
}
- /// Sort the set’s values in place and in parallel, using the comparison function `cmp`.
+ /// Sort the set's values in place and in parallel, using the comparison function `cmp`.
pub fn par_sort_unstable_by<F>(&mut self, cmp: F)
where
F: Fn(&T, &T) -> Ordering + Sync,
@@ -548,7 +558,18 @@ where
IntoParIter { entries }
}
- /// Sort the set’s values in place and in parallel, using a key extraction function.
+ /// Sort the set's values in place and in parallel, using a key extraction function.
+ pub fn par_sort_unstable_by_key<K, F>(&mut self, sort_key: F)
+ where
+ K: Ord,
+ F: Fn(&T) -> K + Sync,
+ {
+ self.with_entries(move |entries| {
+ entries.par_sort_unstable_by_key(move |a| sort_key(&a.key));
+ });
+ }
+
+ /// Sort the set's values in place and in parallel, using a key extraction function.
pub fn par_sort_by_cached_key<K, F>(&mut self, sort_key: F)
where
K: Ord + Send,
diff --git a/third_party/rust/indexmap/src/serde.rs b/third_party/rust/indexmap/src/serde.rs
@@ -1,10 +1,10 @@
#![cfg_attr(docsrs, doc(cfg(feature = "serde")))]
-use serde::de::value::{MapDeserializer, SeqDeserializer};
-use serde::de::{
+use serde_core::de::value::{MapDeserializer, SeqDeserializer};
+use serde_core::de::{
Deserialize, Deserializer, Error, IntoDeserializer, MapAccess, SeqAccess, Visitor,
};
-use serde::ser::{Serialize, Serializer};
+use serde_core::ser::{Serialize, Serializer};
use core::fmt::{self, Formatter};
use core::hash::{BuildHasher, Hash};
diff --git a/third_party/rust/indexmap/src/set.rs b/third_party/rust/indexmap/src/set.rs
@@ -8,7 +8,7 @@ mod slice;
mod tests;
pub use self::iter::{
- Difference, Drain, Intersection, IntoIter, Iter, Splice, SymmetricDifference, Union,
+ Difference, Drain, ExtractIf, Intersection, IntoIter, Iter, Splice, SymmetricDifference, Union,
};
pub use self::mutable::MutableValues;
pub use self::slice::Slice;
@@ -28,7 +28,7 @@ use core::fmt;
use core::hash::{BuildHasher, Hash};
use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub};
-use super::{Entries, Equivalent, IndexMap};
+use super::{Equivalent, IndexMap};
type Bucket<T> = super::Bucket<T, ()>;
@@ -105,32 +105,6 @@ where
}
}
-impl<T, S> Entries for IndexSet<T, S> {
- type Entry = Bucket<T>;
-
- #[inline]
- fn into_entries(self) -> Vec<Self::Entry> {
- self.map.into_entries()
- }
-
- #[inline]
- fn as_entries(&self) -> &[Self::Entry] {
- self.map.as_entries()
- }
-
- #[inline]
- fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
- self.map.as_entries_mut()
- }
-
- fn with_entries<F>(&mut self, f: F)
- where
- F: FnOnce(&mut [Self::Entry]),
- {
- self.map.with_entries(f);
- }
-}
-
impl<T, S> fmt::Debug for IndexSet<T, S>
where
T: fmt::Debug,
@@ -189,6 +163,23 @@ impl<T, S> IndexSet<T, S> {
}
}
+ #[inline]
+ pub(crate) fn into_entries(self) -> Vec<Bucket<T>> {
+ self.map.into_entries()
+ }
+
+ #[inline]
+ pub(crate) fn as_entries(&self) -> &[Bucket<T>] {
+ self.map.as_entries()
+ }
+
+ pub(crate) fn with_entries<F>(&mut self, f: F)
+ where
+ F: FnOnce(&mut [Bucket<T>]),
+ {
+ self.map.with_entries(f);
+ }
+
/// Return the number of elements the set can hold without reallocating.
///
/// This number is a lower bound; the set might be able to hold more,
@@ -258,6 +249,52 @@ impl<T, S> IndexSet<T, S> {
Drain::new(self.map.core.drain(range))
}
+ /// Creates an iterator which uses a closure to determine if a value should be removed,
+ /// for all values in the given range.
+ ///
+ /// If the closure returns true, then the value is removed and yielded.
+ /// If the closure returns false, the value will remain in the list and will not be yielded
+ /// by the iterator.
+ ///
+ /// The range may be any type that implements [`RangeBounds<usize>`],
+ /// including all of the `std::ops::Range*` types, or even a tuple pair of
+ /// `Bound` start and end values. To check the entire set, use `RangeFull`
+ /// like `set.extract_if(.., predicate)`.
+ ///
+ /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
+ /// or the iteration short-circuits, then the remaining elements will be retained.
+ /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
+ ///
+ /// [`retain`]: IndexSet::retain
+ ///
+ /// ***Panics*** if the starting point is greater than the end point or if
+ /// the end point is greater than the length of the set.
+ ///
+ /// # Examples
+ ///
+ /// Splitting a set into even and odd values, reusing the original set:
+ ///
+ /// ```
+ /// use indexmap::IndexSet;
+ ///
+ /// let mut set: IndexSet<i32> = (0..8).collect();
+ /// let extracted: IndexSet<i32> = set.extract_if(.., |v| v % 2 == 0).collect();
+ ///
+ /// let evens = extracted.into_iter().collect::<Vec<_>>();
+ /// let odds = set.into_iter().collect::<Vec<_>>();
+ ///
+ /// assert_eq!(evens, vec![0, 2, 4, 6]);
+ /// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// ```
+ #[track_caller]
+ pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, T, F>
+ where
+ F: FnMut(&T) -> bool,
+ R: RangeBounds<usize>,
+ {
+ ExtractIf::new(&mut self.map.core, range, pred)
+ }
+
/// Splits the collection into two at the given index.
///
/// Returns a newly allocated set containing the elements in the range
@@ -385,6 +422,49 @@ where
(index, existing.is_none())
}
+ /// Insert the value into the set at its ordered position among values
+ /// sorted by `cmp`.
+ ///
+ /// This is equivalent to finding the position with
+ /// [`binary_search_by`][Self::binary_search_by], then calling
+ /// [`insert_before`][Self::insert_before].
+ ///
+ /// If the existing items are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the value
+ /// is moved to or inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by<F>(&mut self, value: T, mut cmp: F) -> (usize, bool)
+ where
+ F: FnMut(&T, &T) -> Ordering,
+ {
+ let (index, existing) = self
+ .map
+ .insert_sorted_by(value, (), |a, (), b, ()| cmp(a, b));
+ (index, existing.is_none())
+ }
+
+ /// Insert the value into the set at its ordered position among values
+ /// using a sort-key extraction function.
+ ///
+ /// This is equivalent to finding the position with
+ /// [`binary_search_by_key`][Self::binary_search_by_key] with `sort_key(key)`,
+ /// then calling [`insert_before`][Self::insert_before].
+ ///
+ /// If the existing items are **not** already sorted, then the insertion
+ /// index is unspecified (like [`slice::binary_search`]), but the value
+ /// is moved to or inserted at that position regardless.
+ ///
+ /// Computes in **O(n)** time (average).
+ pub fn insert_sorted_by_key<B, F>(&mut self, value: T, mut sort_key: F) -> (usize, bool)
+ where
+ B: Ord,
+ F: FnMut(&T) -> B,
+ {
+ let (index, existing) = self.map.insert_sorted_by_key(value, (), |k, _| sort_key(k));
+ (index, existing.is_none())
+ }
+
/// Insert the value into the set before the value at the given index, or at the end.
///
/// If an equivalent item already exists in the set, it returns `false` leaving the
@@ -513,6 +593,22 @@ where
}
}
+ /// Replaces the value at the given index. The new value does not need to be
+ /// equivalent to the one it is replacing, but it must be unique to the rest
+ /// of the set.
+ ///
+ /// Returns `Ok(old_value)` if successful, or `Err((other_index, value))` if
+ /// an equivalent value already exists at a different index. The set will be
+ /// unchanged in the error case.
+ ///
+ /// ***Panics*** if `index` is out of bounds.
+ ///
+ /// Computes in **O(1)** time (average).
+ #[track_caller]
+ pub fn replace_index(&mut self, index: usize, value: T) -> Result<T, (usize, T)> {
+ self.map.replace_index(index, value)
+ }
+
/// Return an iterator over the values that are in `self` but not `other`.
///
/// Values are produced in the same order that they appear in `self`.
@@ -822,7 +918,7 @@ impl<T, S> IndexSet<T, S> {
self.map.retain(move |x, &mut ()| keep(x))
}
- /// Sort the set’s values by their default ordering.
+ /// Sort the set's values by their default ordering.
///
/// This is a stable sort -- but equivalent values should not normally coexist in
/// a set at all, so [`sort_unstable`][Self::sort_unstable] is preferred
@@ -836,14 +932,14 @@ impl<T, S> IndexSet<T, S> {
self.map.sort_keys()
}
- /// Sort the set’s values in place using the comparison function `cmp`.
+ /// Sort the set's values in place using the comparison function `cmp`.
///
/// Computes in **O(n log n)** time and **O(n)** space. The sort is stable.
pub fn sort_by<F>(&mut self, mut cmp: F)
where
F: FnMut(&T, &T) -> Ordering,
{
- self.map.sort_by(move |a, _, b, _| cmp(a, b));
+ self.map.sort_by(move |a, (), b, ()| cmp(a, b));
}
/// Sort the values of the set and return a by-value iterator of
@@ -859,6 +955,19 @@ impl<T, S> IndexSet<T, S> {
IntoIter::new(entries)
}
+ /// Sort the set's values in place using a key extraction function.
+ ///
+ /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable.
+ pub fn sort_by_key<K, F>(&mut self, mut sort_key: F)
+ where
+ K: Ord,
+ F: FnMut(&T) -> K,
+ {
+ self.with_entries(move |entries| {
+ entries.sort_by_key(move |a| sort_key(&a.key));
+ });
+ }
+
/// Sort the set's values by their default ordering.
///
/// See [`sort_unstable_by`](Self::sort_unstable_by) for details.
@@ -890,7 +999,20 @@ impl<T, S> IndexSet<T, S> {
IntoIter::new(entries)
}
- /// Sort the set’s values in place using a key extraction function.
+ /// Sort the set's values in place using a key extraction function.
+ ///
+ /// Computes in **O(n log n)** time. The sort is unstable.
+ pub fn sort_unstable_by_key<K, F>(&mut self, mut sort_key: F)
+ where
+ K: Ord,
+ F: FnMut(&T) -> K,
+ {
+ self.with_entries(move |entries| {
+ entries.sort_unstable_by_key(move |a| sort_key(&a.key));
+ });
+ }
+
+ /// Sort the set's values in place using a key extraction function.
///
/// During sorting, the function is called at most once per entry, by using temporary storage
/// to remember the results of its evaluation. The order of calls to the function is
@@ -951,6 +1073,34 @@ impl<T, S> IndexSet<T, S> {
self.as_slice().binary_search_by_key(b, f)
}
+ /// Checks if the values of this set are sorted.
+ #[inline]
+ pub fn is_sorted(&self) -> bool
+ where
+ T: PartialOrd,
+ {
+ self.as_slice().is_sorted()
+ }
+
+ /// Checks if this set is sorted using the given comparator function.
+ #[inline]
+ pub fn is_sorted_by<'a, F>(&'a self, cmp: F) -> bool
+ where
+ F: FnMut(&'a T, &'a T) -> bool,
+ {
+ self.as_slice().is_sorted_by(cmp)
+ }
+
+ /// Checks if this set is sorted using the given sort-key function.
+ #[inline]
+ pub fn is_sorted_by_key<'a, F, K>(&'a self, sort_key: F) -> bool
+ where
+ F: FnMut(&'a T) -> K,
+ K: PartialOrd,
+ {
+ self.as_slice().is_sorted_by_key(sort_key)
+ }
+
/// Returns the index of the partition point of a sorted set according to the given predicate
/// (the index of the first element of the second partition).
///
@@ -965,7 +1115,7 @@ impl<T, S> IndexSet<T, S> {
self.as_slice().partition_point(pred)
}
- /// Reverses the order of the set’s values in place.
+ /// Reverses the order of the set's values in place.
///
/// Computes in **O(n)** time and **O(1)** space.
pub fn reverse(&mut self) {
@@ -1106,12 +1256,14 @@ impl<T, S> Index<usize> for IndexSet<T, S> {
///
/// ***Panics*** if `index` is out of bounds.
fn index(&self, index: usize) -> &T {
- self.get_index(index).unwrap_or_else(|| {
+ if let Some(value) = self.get_index(index) {
+ value
+ } else {
panic!(
"index out of bounds: the len is {len} but the index is {index}",
len = self.len()
);
- })
+ }
}
}
diff --git a/third_party/rust/indexmap/src/set/iter.rs b/third_party/rust/indexmap/src/set/iter.rs
@@ -1,4 +1,6 @@
-use super::{Bucket, Entries, IndexSet, Slice};
+use crate::map::{ExtractCore, IndexMapCore};
+
+use super::{Bucket, IndexSet, Slice};
use alloc::vec::{self, Vec};
use core::fmt;
@@ -626,3 +628,54 @@ impl<I: fmt::Debug> fmt::Debug for UnitValue<I> {
fmt::Debug::fmt(&self.0, f)
}
}
+
+/// An extracting iterator for `IndexSet`.
+///
+/// This `struct` is created by [`IndexSet::extract_if()`].
+/// See its documentation for more.
+pub struct ExtractIf<'a, T, F> {
+ inner: ExtractCore<'a, T, ()>,
+ pred: F,
+}
+
+impl<T, F> ExtractIf<'_, T, F> {
+ #[track_caller]
+ pub(super) fn new<R>(core: &mut IndexMapCore<T, ()>, range: R, pred: F) -> ExtractIf<'_, T, F>
+ where
+ R: RangeBounds<usize>,
+ F: FnMut(&T) -> bool,
+ {
+ ExtractIf {
+ inner: core.extract(range),
+ pred,
+ }
+ }
+}
+
+impl<T, F> Iterator for ExtractIf<'_, T, F>
+where
+ F: FnMut(&T) -> bool,
+{
+ type Item = T;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.inner
+ .extract_if(|bucket| (self.pred)(bucket.key_ref()))
+ .map(Bucket::key)
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.inner.remaining()))
+ }
+}
+
+impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&T) -> bool {}
+
+impl<T, F> fmt::Debug for ExtractIf<'_, T, F>
+where
+ T: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("ExtractIf").finish_non_exhaustive()
+ }
+}
diff --git a/third_party/rust/indexmap/src/set/mutable.rs b/third_party/rust/indexmap/src/set/mutable.rs
@@ -8,7 +8,7 @@ use crate::map::MutableKeys;
/// These methods expose `&mut T`, mutable references to the value as it is stored
/// in the set.
/// You are allowed to modify the values in the set **if the modification
-/// does not change the value’s hash and equality**.
+/// does not change the value's hash and equality**.
///
/// If values are modified erroneously, you can no longer look them up.
/// This is sound (memory safe) but a logical error hazard (just like
diff --git a/third_party/rust/indexmap/src/set/slice.rs b/third_party/rust/indexmap/src/set/slice.rs
@@ -1,4 +1,4 @@
-use super::{Bucket, Entries, IndexSet, IntoIter, Iter};
+use super::{Bucket, IndexSet, IntoIter, Iter};
use crate::util::{slice_eq, try_simplify_range};
use alloc::boxed::Box;
@@ -85,6 +85,7 @@ impl<T> Slice<T> {
/// Divides one slice into two at an index.
///
/// ***Panics*** if `index > len`.
+ #[track_caller]
pub fn split_at(&self, index: usize) -> (&Self, &Self) {
let (first, second) = self.entries.split_at(index);
(Self::from_slice(first), Self::from_slice(second))
@@ -159,6 +160,53 @@ impl<T> Slice<T> {
self.binary_search_by(|k| f(k).cmp(b))
}
+ /// Checks if the values of this slice are sorted.
+ #[inline]
+ pub fn is_sorted(&self) -> bool
+ where
+ T: PartialOrd,
+ {
+ // TODO(MSRV 1.82): self.entries.is_sorted_by(|a, b| a.key <= b.key)
+ self.is_sorted_by(T::le)
+ }
+
+ /// Checks if this slice is sorted using the given comparator function.
+ #[inline]
+ pub fn is_sorted_by<'a, F>(&'a self, mut cmp: F) -> bool
+ where
+ F: FnMut(&'a T, &'a T) -> bool,
+ {
+ // TODO(MSRV 1.82): self.entries.is_sorted_by(move |a, b| cmp(&a.key, &b.key))
+ let mut iter = self.entries.iter();
+ match iter.next() {
+ Some(mut prev) => iter.all(move |next| {
+ let sorted = cmp(&prev.key, &next.key);
+ prev = next;
+ sorted
+ }),
+ None => true,
+ }
+ }
+
+ /// Checks if this slice is sorted using the given sort-key function.
+ #[inline]
+ pub fn is_sorted_by_key<'a, F, K>(&'a self, mut sort_key: F) -> bool
+ where
+ F: FnMut(&'a T) -> K,
+ K: PartialOrd,
+ {
+ // TODO(MSRV 1.82): self.entries.is_sorted_by_key(move |a| sort_key(&a.key))
+ let mut iter = self.entries.iter().map(move |a| sort_key(&a.key));
+ match iter.next() {
+ Some(mut prev) => iter.all(move |next| {
+ let sorted = prev <= next;
+ prev = next;
+ sorted
+ }),
+ None => true,
+ }
+ }
+
/// Returns the index of the partition point of a sorted set according to the given predicate
/// (the index of the first element of the second partition).
///
diff --git a/third_party/rust/indexmap/src/set/tests.rs b/third_party/rust/indexmap/src/set/tests.rs
@@ -584,6 +584,304 @@ fn iter_default() {
}
#[test]
+#[allow(deprecated)]
+fn take() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(10);
+ assert_eq!(index_set.len(), 1);
+
+ let result = index_set.take(&10);
+ assert_eq!(result, Some(10));
+ assert_eq!(index_set.len(), 0);
+
+ let result = index_set.take(&20);
+ assert_eq!(result, None);
+}
+
+#[test]
+fn swap_take() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(10);
+ index_set.insert(20);
+ index_set.insert(30);
+ index_set.insert(40);
+ assert_eq!(index_set.len(), 4);
+
+ let result = index_set.swap_take(&20);
+ assert_eq!(result, Some(20));
+ assert_eq!(index_set.len(), 3);
+ assert_eq!(index_set.as_slice(), &[10, 40, 30]);
+
+ let result = index_set.swap_take(&50);
+ assert_eq!(result, None);
+}
+
+#[test]
+fn sort_unstable() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(30);
+ index_set.insert(20);
+ index_set.insert(10);
+
+ index_set.sort_unstable();
+ assert_eq!(index_set.as_slice(), &[10, 20, 30]);
+}
+
+#[test]
+fn try_reserve_exact() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(10);
+ index_set.insert(20);
+ index_set.insert(30);
+ index_set.shrink_to_fit();
+ assert_eq!(index_set.capacity(), 3);
+
+ index_set.try_reserve_exact(2).unwrap();
+ assert_eq!(index_set.capacity(), 5);
+}
+
+#[test]
+fn shift_remove_full() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(10);
+ set.insert(20);
+ set.insert(30);
+ set.insert(40);
+ set.insert(50);
+
+ let result = set.shift_remove_full(&20);
+ assert_eq!(result, Some((1, 20)));
+ assert_eq!(set.len(), 4);
+ assert_eq!(set.as_slice(), &[10, 30, 40, 50]);
+
+ let result = set.shift_remove_full(&50);
+ assert_eq!(result, Some((3, 50)));
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[10, 30, 40]);
+
+ let result = set.shift_remove_full(&60);
+ assert_eq!(result, None);
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[10, 30, 40]);
+}
+
+#[test]
+fn shift_remove_index() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(10);
+ set.insert(20);
+ set.insert(30);
+ set.insert(40);
+ set.insert(50);
+
+ let result = set.shift_remove_index(1);
+ assert_eq!(result, Some(20));
+ assert_eq!(set.len(), 4);
+ assert_eq!(set.as_slice(), &[10, 30, 40, 50]);
+
+ let result = set.shift_remove_index(1);
+ assert_eq!(result, Some(30));
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[10, 40, 50]);
+
+ let result = set.shift_remove_index(3);
+ assert_eq!(result, None);
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[10, 40, 50]);
+}
+
+#[test]
+fn sort_unstable_by() {
+ let mut set: IndexSet<i32> = IndexSet::from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+ set.sort_unstable_by(|a, b| b.cmp(a));
+ assert_eq!(set.as_slice(), &[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);
+}
+
+#[test]
+fn sort_by() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(3);
+ set.insert(1);
+ set.insert(2);
+ set.sort_by(|a, b| a.cmp(b));
+ assert_eq!(set.as_slice(), &[1, 2, 3]);
+}
+
+#[test]
+fn drain() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(1);
+ set.insert(2);
+ set.insert(3);
+
+ {
+ let drain = set.drain(0..2);
+ assert_eq!(drain.as_slice(), &[1, 2]);
+ }
+
+ assert_eq!(set.len(), 1);
+ assert_eq!(set.as_slice(), &[3]);
+}
+
+#[test]
+fn split_off() {
+ let mut set: IndexSet<i32> = IndexSet::from([1, 2, 3, 4, 5]);
+ let split_set: IndexSet<i32> = set.split_off(3);
+
+ assert_eq!(split_set.len(), 2);
+ assert_eq!(split_set.as_slice(), &[4, 5]);
+
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[1, 2, 3]);
+}
+
+#[test]
+fn retain() {
+ let mut set: IndexSet<i32> = IndexSet::from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+ set.retain(|&x| x > 4);
+ assert_eq!(set.len(), 6);
+ assert_eq!(set.as_slice(), &[5, 6, 7, 8, 9, 10]);
+
+ set.retain(|_| false);
+ assert_eq!(set.len(), 0);
+}
+
+#[test]
+fn first() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(10);
+ index_set.insert(20);
+ index_set.insert(30);
+
+ let result = index_set.first();
+ assert_eq!(*result.unwrap(), 10);
+
+ index_set.clear();
+ let result = index_set.first();
+ assert!(result.is_none());
+}
+
+#[test]
+fn sort_by_key() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(3);
+ index_set.insert(1);
+ index_set.insert(2);
+ index_set.insert(0);
+ index_set.sort_by_key(|&x| -x);
+ assert_eq!(index_set.as_slice(), &[3, 2, 1, 0]);
+}
+
+#[test]
+fn sort_unstable_by_key() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(3);
+ index_set.insert(1);
+ index_set.insert(2);
+ index_set.insert(0);
+ index_set.sort_unstable_by_key(|&x| -x);
+ assert_eq!(index_set.as_slice(), &[3, 2, 1, 0]);
+}
+
+#[test]
+fn sort_by_cached_key() {
+ let mut index_set: IndexSet<i32> = IndexSet::new();
+ index_set.insert(3);
+ index_set.insert(1);
+ index_set.insert(2);
+ index_set.insert(0);
+ index_set.sort_by_cached_key(|&x| -x);
+ assert_eq!(index_set.as_slice(), &[3, 2, 1, 0]);
+}
+
+#[test]
+fn insert_sorted() {
+ let mut set: IndexSet<i32> = IndexSet::<i32>::new();
+ set.insert_sorted(1);
+ set.insert_sorted(3);
+ assert_eq!(set.insert_sorted(2), (1, true));
+}
+
+#[test]
+fn binary_search() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(100);
+ set.insert(300);
+ set.insert(200);
+ set.insert(400);
+ let result = set.binary_search(&200);
+ assert_eq!(result, Ok(2));
+
+ let result = set.binary_search(&500);
+ assert_eq!(result, Err(4));
+}
+
+#[test]
+fn sorted_unstable_by() {
+ let mut set: IndexSet<i32> = IndexSet::from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+ set.sort_unstable_by(|a, b| b.cmp(a));
+ assert_eq!(set.as_slice(), &[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);
+}
+
+#[test]
+fn last() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(1);
+ set.insert(2);
+ set.insert(3);
+ set.insert(4);
+ set.insert(5);
+ set.insert(6);
+
+ assert_eq!(set.last(), Some(&6));
+
+ set.pop();
+ assert_eq!(set.last(), Some(&5));
+
+ set.clear();
+ assert_eq!(set.last(), None);
+}
+
+#[test]
+fn get_range() {
+ let set: IndexSet<i32> = IndexSet::from([1, 2, 3, 4, 5]);
+ let result = set.get_range(0..3);
+ let slice: &Slice<i32> = result.unwrap();
+ assert_eq!(slice, &[1, 2, 3]);
+
+ let result = set.get_range(0..0);
+ assert_eq!(result.unwrap().len(), 0);
+
+ let result = set.get_range(2..1);
+ assert!(result.is_none());
+}
+
+#[test]
+fn shift_take() {
+ let mut set: IndexSet<i32> = IndexSet::new();
+ set.insert(1);
+ set.insert(2);
+ set.insert(3);
+ set.insert(4);
+ set.insert(5);
+
+ let result = set.shift_take(&2);
+ assert_eq!(result, Some(2));
+ assert_eq!(set.len(), 4);
+ assert_eq!(set.as_slice(), &[1, 3, 4, 5]);
+
+ let result = set.shift_take(&5);
+ assert_eq!(result, Some(5));
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[1, 3, 4]);
+
+ let result = set.shift_take(&5);
+ assert_eq!(result, None);
+ assert_eq!(set.len(), 3);
+ assert_eq!(set.as_slice(), &[1, 3, 4]);
+}
+
+#[test]
fn test_binary_search_by() {
// adapted from std's test for binary_search
let b: IndexSet<i32> = [].into();
@@ -721,3 +1019,42 @@ fn test_partition_point() {
assert_eq!(b.partition_point(|&x| x < 7), 2);
assert_eq!(b.partition_point(|&x| x < 8), 3);
}
+
+#[test]
+fn is_sorted() {
+ fn expect(set: &IndexSet<i32>, e: [bool; 4]) {
+ assert_eq!(e[0], set.is_sorted());
+ assert_eq!(e[1], set.is_sorted_by(|v1, v2| v1 < v2));
+ assert_eq!(e[2], set.is_sorted_by(|v1, v2| v1 > v2));
+ assert_eq!(e[3], set.is_sorted_by_key(|v| v));
+ }
+
+ let mut set = IndexSet::<i32>::from_iter(0..10);
+ expect(&set, [true, true, false, true]);
+
+ set.replace_index(5, -1).unwrap();
+ expect(&set, [false, false, false, false]);
+}
+
+#[test]
+fn is_sorted_trivial() {
+ fn expect(set: &IndexSet<i32>, e: [bool; 5]) {
+ assert_eq!(e[0], set.is_sorted());
+ assert_eq!(e[1], set.is_sorted_by(|_, _| true));
+ assert_eq!(e[2], set.is_sorted_by(|_, _| false));
+ assert_eq!(e[3], set.is_sorted_by_key(|_| 0f64));
+ assert_eq!(e[4], set.is_sorted_by_key(|_| f64::NAN));
+ }
+
+ let mut set = IndexSet::<i32>::default();
+ expect(&set, [true, true, true, true, true]);
+
+ set.insert(0);
+ expect(&set, [true, true, true, true, true]);
+
+ set.insert(1);
+ expect(&set, [true, true, false, true, false]);
+
+ set.reverse();
+ expect(&set, [false, true, false, true, false]);
+}
diff --git a/third_party/rust/indexmap/src/sval.rs b/third_party/rust/indexmap/src/sval.rs
@@ -0,0 +1,36 @@
+#![cfg_attr(docsrs, doc(cfg(feature = "sval")))]
+
+use crate::{IndexMap, IndexSet};
+use sval::{Stream, Value};
+
+impl<K: Value, V: Value, S> Value for IndexMap<K, V, S> {
+ fn stream<'sval, ST: Stream<'sval> + ?Sized>(&'sval self, stream: &mut ST) -> sval::Result {
+ stream.map_begin(Some(self.len()))?;
+
+ for (k, v) in self {
+ stream.map_key_begin()?;
+ stream.value(k)?;
+ stream.map_key_end()?;
+
+ stream.map_value_begin()?;
+ stream.value(v)?;
+ stream.map_value_end()?;
+ }
+
+ stream.map_end()
+ }
+}
+
+impl<K: Value, S> Value for IndexSet<K, S> {
+ fn stream<'sval, ST: Stream<'sval> + ?Sized>(&'sval self, stream: &mut ST) -> sval::Result {
+ stream.seq_begin(Some(self.len()))?;
+
+ for value in self {
+ stream.seq_value_begin()?;
+ stream.value(value)?;
+ stream.seq_value_end()?;
+ }
+
+ stream.seq_end()
+ }
+}
diff --git a/third_party/rust/indexmap/tests/quick.rs b/third_party/rust/indexmap/tests/quick.rs
@@ -130,6 +130,100 @@ quickcheck_limit! {
true
}
+ fn insert_sorted_by(insert: Vec<(u32, u32)>) -> bool {
+ let mut hmap = HashMap::new();
+ let mut map = IndexMap::new();
+ let mut map2 = IndexMap::new();
+ for &(key, value) in &insert {
+ hmap.insert(key, value);
+ map.insert_sorted_by(key, value, |key1, _, key2, _| key2.cmp(key1));
+ match map2.entry(key) {
+ Entry::Occupied(e) => *e.into_mut() = value,
+ Entry::Vacant(e) => {
+ e.insert_sorted_by(value, |key1, _, key2, _| key2.cmp(key1));
+ }
+ }
+ }
+ let hsorted = hmap.iter().sorted_by(|(key1, _), (key2, _)| key2.cmp(key1));
+ itertools::assert_equal(hsorted, &map);
+ itertools::assert_equal(&map, &map2);
+ true
+ }
+
+ fn insert_sorted_by_key(insert: Vec<(i32, u32)>) -> bool {
+ let mut hmap = HashMap::new();
+ let mut map = IndexMap::new();
+ let mut map2 = IndexMap::new();
+ for &(key, value) in &insert {
+ hmap.insert(key, value);
+ map.insert_sorted_by_key(key, value, |&k, _| (k.unsigned_abs(), k));
+ match map2.entry(key) {
+ Entry::Occupied(e) => *e.into_mut() = value,
+ Entry::Vacant(e) => {
+ e.insert_sorted_by_key(value, |&k, _| (k.unsigned_abs(), k));
+ }
+ }
+ }
+ let hsorted = hmap.iter().sorted_by_key(|(&k, _)| (k.unsigned_abs(), k));
+ itertools::assert_equal(hsorted, &map);
+ itertools::assert_equal(&map, &map2);
+ true
+ }
+
+ fn replace_index(insert: Vec<u8>, index: u8, new_key: u8) -> TestResult {
+ if insert.is_empty() {
+ return TestResult::discard();
+ }
+ let mut map = IndexMap::new();
+ for &key in &insert {
+ map.insert(key, ());
+ }
+ let mut index = usize::from(index);
+ if index < map.len() {
+ match map.replace_index(index, new_key) {
+ Ok(old_key) => {
+ assert!(old_key == new_key || !map.contains_key(&old_key));
+ }
+ Err((i, key)) => {
+ assert_eq!(key, new_key);
+ index = i;
+ }
+ }
+ assert_eq!(map.get_index_of(&new_key), Some(index));
+ assert_eq!(map.get_index(index), Some((&new_key, &())));
+ TestResult::passed()
+ } else {
+ TestResult::must_fail(move || map.replace_index(index, new_key))
+ }
+ }
+
+ fn vacant_replace_index(insert: Vec<u8>, index: u8, new_key: u8) -> TestResult {
+ if insert.is_empty() {
+ return TestResult::discard();
+ }
+ let mut map = IndexMap::new();
+ for &key in &insert {
+ map.insert(key, ());
+ }
+ let index = usize::from(index);
+ if let Some((&old_key, &())) = map.get_index(index) {
+ match map.entry(new_key) {
+ Entry::Occupied(_) => return TestResult::discard(),
+ Entry::Vacant(entry) => {
+ let (replaced_key, entry) = entry.replace_index(index);
+ assert_eq!(old_key, replaced_key);
+ assert_eq!(*entry.key(), new_key);
+ }
+ };
+ assert!(!map.contains_key(&old_key));
+ assert_eq!(map.get_index_of(&new_key), Some(index));
+ assert_eq!(map.get_index(index), Some((&new_key, &())));
+ TestResult::passed()
+ } else {
+ TestResult::must_fail(move || map.replace_index(index, new_key))
+ }
+ }
+
fn pop(insert: Vec<u8>) -> bool {
let mut map = IndexMap::new();
for &key in &insert {
@@ -191,6 +285,47 @@ quickcheck_limit! {
}
}
+ fn extract_if_odd(insert: Vec<u8>) -> bool {
+ let mut map = IndexMap::new();
+ for &x in &insert {
+ map.insert(x, x.to_string());
+ }
+
+ let (odd, even): (Vec<_>, Vec<_>) = map.keys().copied().partition(|k| k % 2 == 1);
+
+ let extracted: Vec<_> = map
+ .extract_if(.., |k, _| k % 2 == 1)
+ .map(|(k, _)| k)
+ .collect();
+
+ even.iter().all(|k| map.contains_key(k))
+ && map.keys().eq(&even)
+ && extracted == odd
+ }
+
+ fn extract_if_odd_limit(insert: Vec<u8>, limit: usize) -> bool {
+ let mut map = IndexMap::new();
+ for &x in &insert {
+ map.insert(x, x.to_string());
+ }
+ let limit = limit % (map.len() + 1);
+
+ let mut i = 0;
+ let (odd, other): (Vec<_>, Vec<_>) = map.keys().copied().partition(|k| {
+ k % 2 == 1 && i < limit && { i += 1; true }
+ });
+
+ let extracted: Vec<_> = map
+ .extract_if(.., |k, _| k % 2 == 1)
+ .map(|(k, _)| k)
+ .take(limit)
+ .collect();
+
+ other.iter().all(|k| map.contains_key(k))
+ && map.keys().eq(&other)
+ && extracted == odd
+ }
+
fn shift_remove(insert: Vec<u8>, remove: Vec<u8>) -> bool {
let mut map = IndexMap::new();
for &key in &insert {
