diff options
Diffstat (limited to 'vendor/elsa')
| -rw-r--r-- | vendor/elsa/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/elsa/Cargo.lock | 39 | ||||
| -rw-r--r-- | vendor/elsa/Cargo.toml | 47 | ||||
| -rw-r--r-- | vendor/elsa/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | vendor/elsa/LICENSE-MIT | 27 | ||||
| -rw-r--r-- | vendor/elsa/README.md | 19 | ||||
| -rw-r--r-- | vendor/elsa/examples/arena.rs | 56 | ||||
| -rw-r--r-- | vendor/elsa/examples/fluentresource.rs | 50 | ||||
| -rw-r--r-- | vendor/elsa/examples/mutable_arena.rs | 79 | ||||
| -rw-r--r-- | vendor/elsa/examples/string_interner.rs | 61 | ||||
| -rw-r--r-- | vendor/elsa/examples/sync.rs | 26 | ||||
| -rw-r--r-- | vendor/elsa/src/index_map.rs | 215 | ||||
| -rw-r--r-- | vendor/elsa/src/index_set.rs | 180 | ||||
| -rw-r--r-- | vendor/elsa/src/lib.rs | 29 | ||||
| -rw-r--r-- | vendor/elsa/src/map.rs | 451 | ||||
| -rw-r--r-- | vendor/elsa/src/sync.rs | 624 | ||||
| -rw-r--r-- | vendor/elsa/src/vec.rs | 347 |
17 files changed, 2452 insertions, 0 deletions
diff --git a/vendor/elsa/.cargo-checksum.json b/vendor/elsa/.cargo-checksum.json new file mode 100644 index 000000000..a43c1ffd2 --- /dev/null +++ b/vendor/elsa/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.lock":"436a38effb1bc439febdcf0235758d480258326fb87c19c5cd482194e37d19f3","Cargo.toml":"3f3f154070e2d096c40b6080e233e0f081cd8c67b033fb5150badf7cb3f97a7f","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"15656cc11a8331f28c0986b8ab97220d3e76f98e60ed388b5ffad37dfac4710c","README.md":"72ec631a7cc4907ab80d87776b8eb1929d7cbd76b260f2fdb913714787f30dac","examples/arena.rs":"dd44f11e4b4e8b1eedca5ce5205aef3efface3c8888daa16b735dd476362b335","examples/fluentresource.rs":"d2bc2a1b02e6c92819bc608d91214591d8dc7d52f7f524c24e39ba5fe28ee6fe","examples/mutable_arena.rs":"553541b20ac97339cf89e2ef60810490f8362520911f3279f4129a30c2af6eb6","examples/string_interner.rs":"d8b427b71e6c340bf8ee01bc1245c82839fa6efb3dde6b91aab8791f0dfebbf9","examples/sync.rs":"bf9f395c029129fac6247068874b9514e0a174d342174dc4c65716acdbce3741","src/index_map.rs":"c265730dc36a49c8e7966226ebab0aa74f6c828fa6a5b3779a8df4bd34981c19","src/index_set.rs":"2173479eb3cd1009ed4e6b54ebc8aab8e0869d076b7e270dc937657e49838e01","src/lib.rs":"d26839bf88764445d2ec453b269b4359761186afda947101ee42c344cb0ad940","src/map.rs":"8f663631d817081dc8eac50d5235cac28f11dac0f8ebef6f57676d495b1aaab3","src/sync.rs":"8bc2e17981f58c9773e90d5ef40f66ebb1a13ee0f794294133486e6b4f5b50a0","src/vec.rs":"c9f053f0e22dc40ff1137d60b87650bf521f09a41111c4b8329b37af59893697"},"package":"f74077c3c3aedb99a2683919698285596662518ea13e5eedcf8bdd43b0d0453b"}
\ No newline at end of file diff --git a/vendor/elsa/Cargo.lock b/vendor/elsa/Cargo.lock new file mode 100644 index 000000000..a03e9a806 --- /dev/null +++ b/vendor/elsa/Cargo.lock @@ -0,0 +1,39 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "elsa" +version = "1.8.0" +dependencies = [ + "indexmap", + "stable_deref_trait", +] + +[[package]] +name = "hashbrown" +version = "0.11.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ab5ef0d4909ef3724cc8cce6ccc8572c5c817592e9285f5464f8e86f8bd3726e" + +[[package]] +name = "indexmap" +version = "1.8.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0f647032dfaa1f8b6dc29bd3edb7bbef4861b8b8007ebb118d6db284fd59f6ee" +dependencies = [ + "autocfg", + "hashbrown", +] + +[[package]] +name = "stable_deref_trait" +version = "1.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a8f112729512f8e442d81f95a8a7ddf2b7c6b8a1a6f509a95864142b30cab2d3" diff --git a/vendor/elsa/Cargo.toml b/vendor/elsa/Cargo.toml new file mode 100644 index 000000000..b9c473a20 --- /dev/null +++ b/vendor/elsa/Cargo.toml @@ -0,0 +1,47 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2018" +name = "elsa" +version = "1.8.0" +authors = ["Manish Goregaokar <manishsmail@gmail.com>"] +description = "Append-only collections for Rust where borrows to entries can outlive insertions" +documentation = "https://docs.rs/elsa/" +readme = "README.md" +keywords = [ + "data-structure", + "map", + "frozen", + "cache", + "arena", +] +categories = [ + "data-structures", + "caching", +] +license = "MIT/Apache-2.0" +repository = "https://github.com/manishearth/elsa" + +[package.metadata.docs.rs] +features = ["indexmap"] + +[[example]] +name = "string_interner" +path = "examples/string_interner.rs" +required-features = ["indexmap"] + +[dependencies.indexmap] +version = "1.6" +optional = true + +[dependencies.stable_deref_trait] +version = "1.1.1" diff --git a/vendor/elsa/LICENSE-APACHE b/vendor/elsa/LICENSE-APACHE new file mode 100644 index 000000000..16fe87b06 --- /dev/null +++ b/vendor/elsa/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/vendor/elsa/LICENSE-MIT b/vendor/elsa/LICENSE-MIT new file mode 100644 index 000000000..d74f9e93d --- /dev/null +++ b/vendor/elsa/LICENSE-MIT @@ -0,0 +1,27 @@ +MIT License + +Copyright (c) 2019 Manish Goregaokar + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/vendor/elsa/README.md b/vendor/elsa/README.md new file mode 100644 index 000000000..cd4a5b94a --- /dev/null +++ b/vendor/elsa/README.md @@ -0,0 +1,19 @@ +## elsa + +[](https://travis-ci.org/Manishearth/elsa) +[](https://crates.io/crates/elsa) +[](#license) + +_🎵 Immutability never bothered me anyway 🎶_ + +This crate provides various "frozen" collections. + +These are append-only collections where references to entries can be held on to even across insertions. This is safe because these collections only support storing data that's present behind some indirection -- i.e. `String`, `Vec<T>`, `Box<T>`, etc, and they only yield references to the data behind the allocation (`&str`, `&[T]`, and `&T` respectively) + +The typical use case is having a global cache of strings or other data which the rest of the program borrows from. + +### Running all examples + +```bash +cargo test --examples --features indexmap +``` diff --git a/vendor/elsa/examples/arena.rs b/vendor/elsa/examples/arena.rs new file mode 100644 index 000000000..79913c2e7 --- /dev/null +++ b/vendor/elsa/examples/arena.rs @@ -0,0 +1,56 @@ +use elsa::FrozenVec; + +fn main() { + let arena = Arena::new(); + let lonely = arena.add_thing("lonely", vec![]); + let best_friend = arena.add_thing("best friend", vec![lonely]); + let threes_a_crowd = arena.add_thing("threes a crowd", vec![lonely, best_friend]); + let rando = arena.add_thing("rando", vec![]); + let _facebook = arena.add_thing("facebook", vec![rando, threes_a_crowd, lonely, best_friend]); + + assert!(cmp_ref(lonely, best_friend.friends[0])); + assert!(cmp_ref(best_friend, threes_a_crowd.friends[1])); + arena.dump(); +} + +struct Arena<'arena> { + things: FrozenVec<Box<Thing<'arena>>>, +} + +struct Thing<'arena> { + pub friends: Vec<ThingRef<'arena>>, + pub name: &'static str, +} + +type ThingRef<'arena> = &'arena Thing<'arena>; + +impl<'arena> Arena<'arena> { + fn new() -> Arena<'arena> { + Arena { + things: FrozenVec::new(), + } + } + + fn add_thing( + &'arena self, + name: &'static str, + friends: Vec<ThingRef<'arena>>, + ) -> ThingRef<'arena> { + let idx = self.things.len(); + self.things.push(Box::new(Thing { name, friends })); + &self.things[idx] + } + + fn dump(&'arena self) { + for thing in &self.things { + println!("friends of {}:", thing.name); + for friend in &thing.friends { + println!("\t{}", friend.name); + } + } + } +} + +fn cmp_ref<T>(x: &T, y: &T) -> bool { + x as *const T as usize == y as *const T as usize +} diff --git a/vendor/elsa/examples/fluentresource.rs b/vendor/elsa/examples/fluentresource.rs new file mode 100644 index 000000000..dba4aaed8 --- /dev/null +++ b/vendor/elsa/examples/fluentresource.rs @@ -0,0 +1,50 @@ +use elsa::FrozenMap; + +/// Stores some parsed AST representation of the file +#[derive(Debug)] +pub struct FluentResource<'mgr>(&'mgr str); + +impl<'mgr> FluentResource<'mgr> { + pub fn new(s: &'mgr str) -> Self { + // very simple parse step + FluentResource(&s[0..1]) + } +} + +/// Stores loaded files and parsed ASTs +/// +/// Parsed ASTs are zero-copy and +/// contain references to the files +pub struct ResourceManager<'mgr> { + strings: FrozenMap<String, String>, + resources: FrozenMap<String, Box<FluentResource<'mgr>>>, +} + +impl<'mgr> ResourceManager<'mgr> { + pub fn new() -> Self { + ResourceManager { + strings: FrozenMap::new(), + resources: FrozenMap::new(), + } + } + + pub fn get_resource(&'mgr self, path: &str) -> &'mgr FluentResource<'mgr> { + let strings = &self.strings; + + if strings.get(path).is_some() { + return self.resources.get(path).unwrap(); + } else { + // pretend to load a file + let string = format!("file for {}", path); + let val = self.strings.insert(path.to_string(), string); + let res = FluentResource::new(val); + self.resources.insert(path.to_string(), Box::new(res)) + } + } +} + +fn main() { + let manager = ResourceManager::new(); + let resource = manager.get_resource("somefile.ftl"); + println!("{:?}", resource); +} diff --git a/vendor/elsa/examples/mutable_arena.rs b/vendor/elsa/examples/mutable_arena.rs new file mode 100644 index 000000000..d5db2d331 --- /dev/null +++ b/vendor/elsa/examples/mutable_arena.rs @@ -0,0 +1,79 @@ +use elsa::FrozenVec; + +fn main() { + let arena = Arena::new(); + let lonely = arena.add_person("lonely", vec![]); + let best_friend = arena.add_person("best friend", vec![lonely]); + let threes_a_crowd = arena.add_person("threes a crowd", vec![lonely, best_friend]); + let rando = arena.add_person("rando", vec![]); + let _everyone = arena.add_person( + "follows everyone", + vec![rando, threes_a_crowd, lonely, best_friend], + ); + arena.dump(); +} + +struct Arena<'arena> { + people: FrozenVec<Box<Person<'arena>>>, +} + +struct Person<'arena> { + pub follows: FrozenVec<PersonRef<'arena>>, + pub reverse_follows: FrozenVec<PersonRef<'arena>>, + pub name: &'static str, +} + +type PersonRef<'arena> = &'arena Person<'arena>; + +impl<'arena> Arena<'arena> { + fn new() -> Arena<'arena> { + Arena { + people: FrozenVec::new(), + } + } + + fn add_person( + &'arena self, + name: &'static str, + follows: Vec<PersonRef<'arena>>, + ) -> PersonRef<'arena> { + let idx = self.people.len(); + self.people.push(Box::new(Person { + name, + follows: follows.into(), + reverse_follows: Default::default(), + })); + let me = &self.people[idx]; + for friend in &me.follows { + friend.reverse_follows.push(me) + } + me + } + + fn dump(&'arena self) { + for thing in &self.people { + println!("{} network:", thing.name); + println!("\tfollowing:"); + for friend in &thing.follows { + println!("\t\t{}", friend.name); + } + println!("\tfollowers:"); + for friend in &thing.reverse_follows { + println!("\t\t{}", friend.name); + } + } + } +} + +// Note that the following will cause the above code to stop compiling +// since non-eyepatched custom destructors can potentially +// read deallocated data. +// +// impl<'arena> Drop for Person<'arena> { +// fn drop(&mut self) { +// println!("goodbye {:?}", self.name); +// for friend in &self.follows { +// println!("\t\t{}", friend.name); +// } +// } +// } diff --git a/vendor/elsa/examples/string_interner.rs b/vendor/elsa/examples/string_interner.rs new file mode 100644 index 000000000..fd039f7ba --- /dev/null +++ b/vendor/elsa/examples/string_interner.rs @@ -0,0 +1,61 @@ +use std::collections::BTreeSet; +use std::convert::AsRef; + +use elsa::FrozenIndexSet; + +struct StringInterner { + set: FrozenIndexSet<String>, +} + +impl StringInterner { + fn new() -> Self { + StringInterner { + set: FrozenIndexSet::new(), + } + } + + fn get_or_intern<T>(&self, value: T) -> usize + where + T: AsRef<str>, + { + // TODO use Entry in case the standard Entry API gets improved + // (here to avoid premature allocation or double lookup) + self.set.insert_full(value.as_ref().to_string()).0 + } + + fn get<T>(&self, value: T) -> Option<usize> + where + T: AsRef<str>, + { + self.set.get_full(value.as_ref()).map(|(i, _r)| i) + } + + fn resolve(&self, index: usize) -> Option<&str> { + self.set.get_index(index) + } +} + +fn main() { + let interner = StringInterner::new(); + let lonely = interner.get_or_intern("lonely"); + let best_friend = interner.get_or_intern("best friend"); + let threes_a_crowd = interner.get_or_intern("threes a crowd"); + let rando = interner.get_or_intern("rando"); + let _facebook = interner.get_or_intern("facebook"); + + let best_friend_2 = interner.get_or_intern("best friend"); + let best_friend_3 = interner.get("best friend").unwrap(); + + let best_friend_ref = interner.resolve(best_friend).unwrap(); + + let mut set = BTreeSet::new(); + set.insert(lonely); + set.insert(best_friend); + set.insert(threes_a_crowd); + set.insert(rando); + set.insert(best_friend_2); + assert_eq!(set.len(), 4); + assert_eq!(best_friend, best_friend_2); + assert_eq!(best_friend_2, best_friend_3); + assert_eq!(best_friend_ref, "best friend"); +} diff --git a/vendor/elsa/examples/sync.rs b/vendor/elsa/examples/sync.rs new file mode 100644 index 000000000..c6d9eb3cc --- /dev/null +++ b/vendor/elsa/examples/sync.rs @@ -0,0 +1,26 @@ +use elsa::sync::*; + +use std::sync::Arc; +use std::thread; +use std::time::Duration; + +fn main() { + let a = Arc::new(FrozenMap::new()); + for i in 1..10 { + let b = a.clone(); + thread::spawn(move || { + b.insert(i, i.to_string()); + thread::sleep(Duration::from_millis(300)); + loop { + if let Some(opposite) = b.get(&(10 - i)) { + assert!(opposite.parse::<i32>().unwrap() == 10 - i); + break; + } else { + thread::sleep(Duration::from_millis(200)); + } + } + }); + } + + thread::sleep(Duration::from_millis(1000)); +} diff --git a/vendor/elsa/src/index_map.rs b/vendor/elsa/src/index_map.rs new file mode 100644 index 000000000..3c97dfbaa --- /dev/null +++ b/vendor/elsa/src/index_map.rs @@ -0,0 +1,215 @@ +use std::borrow::Borrow; +use std::cell::{Cell, UnsafeCell}; +use std::collections::hash_map::RandomState; +use std::hash::{BuildHasher, Hash}; +use std::iter::FromIterator; +use std::ops::Index; + +use indexmap::IndexMap; +use stable_deref_trait::StableDeref; + +/// Append-only version of `indexmap::IndexMap` where +/// insertion does not require mutable access +pub struct FrozenIndexMap<K, V, S = RandomState> { + map: UnsafeCell<IndexMap<K, V, S>>, + /// Eq/Hash implementations can have side-effects, and using Rc it is possible + /// for FrozenIndexMap::insert to be called on a key that itself contains the same + /// `FrozenIndexMap`, whose `eq` implementation also calls FrozenIndexMap::insert + /// + /// We use this `in_use` flag to guard against any reentrancy. + in_use: Cell<bool>, +} + +// safety: UnsafeCell implies !Sync + +impl<K: Eq + Hash, V> FrozenIndexMap<K, V> { + pub fn new() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} + +impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenIndexMap<K, V, S> { + // these should never return &K or &V + // these should never delete any entries + pub fn insert(&self, k: K, v: V) -> &V::Target { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + &*(*map).entry(k).or_insert(v) + }; + self.in_use.set(false); + ret + } + + // these should never return &K or &V + // these should never delete any entries + pub fn insert_full(&self, k: K, v: V) -> (usize, &V::Target) { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + let entry = (*map).entry(k); + let index = entry.index(); + (index, &**entry.or_insert(v)) + }; + self.in_use.set(false); + ret + } + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenIndexMap; + /// + /// let map = FrozenIndexMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(|x| &**x) + }; + self.in_use.set(false); + ret + } + + pub fn get_index(&self, index: usize) -> Option<(&K::Target, &V::Target)> + where + K: StableDeref, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get_index(index).map(|(k, v)| (&**k, &**v)) + }; + self.in_use.set(false); + ret + } + + /// Applies a function to the owner of the value corresponding to the key (if any). + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenIndexMap; + /// + /// let map = FrozenIndexMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a"))); + /// assert_eq!(map.map_get(&2, Clone::clone), None); + /// ``` + pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T> + where + K: Borrow<Q>, + Q: Hash + Eq, + F: FnOnce(&V) -> T, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(f) + }; + self.in_use.set(false); + ret + } + + pub fn into_map(self) -> IndexMap<K, V, S> { + self.map.into_inner() + } + + /// Get mutable access to the underlying [`IndexMap`]. + /// + /// This is safe, as it requires a `&mut self`, ensuring nothing is using + /// the 'frozen' contents. + pub fn as_mut(&mut self) -> &mut IndexMap<K, V, S> { + unsafe { &mut *self.map.get() } + } + + /// Returns true if the map contains no elements. + pub fn is_empty(&self) -> bool { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).is_empty() + }; + self.in_use.set(false); + ret + } +} + +impl<K, V, S> From<IndexMap<K, V, S>> for FrozenIndexMap<K, V, S> { + fn from(map: IndexMap<K, V, S>) -> Self { + Self { + map: UnsafeCell::new(map), + in_use: Cell::new(false), + } + } +} + +impl<Q: ?Sized, K: Eq + Hash, V: StableDeref, S: BuildHasher> Index<&Q> for FrozenIndexMap<K, V, S> + where + Q: Eq + Hash, + K: Eq + Hash + Borrow<Q>, + V: StableDeref, + S: BuildHasher +{ + type Output = V::Target; + + /// # Examples + /// + /// ``` + /// use elsa::FrozenIndexMap; + /// + /// let map = FrozenIndexMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map[&1], "a"); + /// ``` + fn index(&self, idx: &Q) -> &V::Target { + self.get(&idx) + .expect("attempted to index FrozenIndexMap with unknown key") + } +} + +impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenIndexMap<K, V, S> { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = (K, V)>, + { + let map: IndexMap<_, _, _> = iter.into_iter().collect(); + map.into() + } +} + +impl<K: Eq + Hash, V, S: Default> Default for FrozenIndexMap<K, V, S> { + fn default() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} diff --git a/vendor/elsa/src/index_set.rs b/vendor/elsa/src/index_set.rs new file mode 100644 index 000000000..1222cde05 --- /dev/null +++ b/vendor/elsa/src/index_set.rs @@ -0,0 +1,180 @@ +use std::borrow::Borrow; +use std::cell::{Cell, UnsafeCell}; +use std::collections::hash_map::RandomState; +use std::hash::{BuildHasher, Hash}; +use std::iter::FromIterator; +use std::ops::Index; + +use indexmap::IndexSet; +use stable_deref_trait::StableDeref; + +/// Append-only version of `indexmap::IndexSet` where +/// insertion does not require mutable access +pub struct FrozenIndexSet<T, S = RandomState> { + set: UnsafeCell<IndexSet<T, S>>, + /// Eq/Hash implementations can have side-effects, and using Rc it is possible + /// for FrozenIndexSet::insert to be called on a key that itself contains the same + /// `FrozenIndexSet`, whose `eq` implementation also calls FrozenIndexSet::insert + /// + /// We use this `in_use` flag to guard against any reentrancy. + in_use: Cell<bool>, +} + +// safety: UnsafeCell implies !Sync + +impl<T: Eq + Hash> FrozenIndexSet<T> { + pub fn new() -> Self { + Self::from(IndexSet::new()) + } +} + +impl<T: Eq + Hash + StableDeref, S: BuildHasher> FrozenIndexSet<T, S> { + // these should never return &T + // these should never delete any entries + pub fn insert(&self, value: T) -> &T::Target { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + let (index, _was_vacant) = (*set).insert_full(value); + &*(*set)[index] + }; + self.in_use.set(false); + ret + } + + // these should never return &T + // these should never delete any entries + pub fn insert_full(&self, value: T) -> (usize, &T::Target) { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + let (index, _was_vacant) = (*set).insert_full(value); + (index, &*(*set)[index]) + }; + self.in_use.set(false); + ret + } + + // TODO implement in case the standard Entry API gets improved + // // TODO avoid double lookup + // pub fn entry<Q: ?Sized>(&self, value: &Q) -> Entry<T, Q> + // where Q: Hash + Equivalent<T> + ToOwned<Owned = T> + // { + // assert!(!self.in_use.get()); + // self.in_use.set(true); + // unsafe { + // let set = self.set.get(); + // match (*set).get_full(value) { + // Some((index, reference)) => { + // Entry::Occupied(OccupiedEntry { + // index, + // reference, + // set: &*set, + // }) + // } + // None => { + // Entry::Vacant(VacantEntry { + // value: Cow::Borrowed(value), + // set: &*set, + // }) + // } + // } + // } + // } + + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&T::Target> + where + T: Borrow<Q>, + Q: Hash + Eq, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + (*set).get(k).map(|x| &**x) + }; + self.in_use.set(false); + ret + } + + pub fn get_full<Q: ?Sized>(&self, k: &Q) -> Option<(usize, &T::Target)> + where + T: Borrow<Q>, + Q: Hash + Eq, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + (*set).get_full(k).map(|(i, x)| (i, &**x)) + }; + self.in_use.set(false); + ret + } + + pub fn get_index(&self, index: usize) -> Option<&T::Target> { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + (*set).get_index(index).map(|r| &**r) + }; + self.in_use.set(false); + ret + } + + pub fn into_set(self) -> IndexSet<T, S> { + self.set.into_inner() + } + + /// Get mutable access to the underlying [`IndexSet`]. + /// + /// This is safe, as it requires a `&mut self`, ensuring nothing is using + /// the 'frozen' contents. + pub fn as_mut(&mut self) -> &mut IndexSet<T, S> { + unsafe { &mut *self.set.get() } + } + + // TODO add more +} + +impl<T, S> From<IndexSet<T, S>> for FrozenIndexSet<T, S> { + fn from(set: IndexSet<T, S>) -> Self { + Self { + set: UnsafeCell::new(set), + in_use: Cell::new(false), + } + } +} + +impl<T: Eq + Hash + StableDeref, S> Index<usize> for FrozenIndexSet<T, S> { + type Output = T::Target; + fn index(&self, idx: usize) -> &T::Target { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let set = self.set.get(); + &*(*set)[idx] + }; + self.in_use.set(false); + ret + } +} + +impl<T: Eq + Hash, S: Default + BuildHasher> FromIterator<T> for FrozenIndexSet<T, S> { + fn from_iter<U>(iter: U) -> Self + where + U: IntoIterator<Item = T>, + { + let set: IndexSet<_, _> = iter.into_iter().collect(); + set.into() + } +} + +impl<T: Eq + Hash, S: Default> Default for FrozenIndexSet<T, S> { + fn default() -> Self { + Self::from(IndexSet::default()) + } +} diff --git a/vendor/elsa/src/lib.rs b/vendor/elsa/src/lib.rs new file mode 100644 index 000000000..848dceb34 --- /dev/null +++ b/vendor/elsa/src/lib.rs @@ -0,0 +1,29 @@ +//! _🎵 Immutability never bothered me anyway 🎶_ +//! +//! This crate provides various "Frozen" collections. +//! +//! These are append-only collections where references to entries can be held +//! on to even across insertions. This is safe because these collections only +//! support storing data that's present behind some indirection -- i.e. `String`, +//! `Vec<T>`, `Box<T>`, etc, and they only yield references to the data behind the +//! allocation (`&str`, `&[T]`, and `&T` respectively) +//! +//! The typical use case is having a global cache of strings or other data which the rest of the program borrows from. + +pub mod map; +pub mod vec; + +#[cfg(feature = "indexmap")] +pub mod index_map; +#[cfg(feature = "indexmap")] +pub mod index_set; + +pub mod sync; + +pub use map::{FrozenBTreeMap, FrozenMap}; +pub use vec::FrozenVec; + +#[cfg(feature = "indexmap")] +pub use index_map::FrozenIndexMap; +#[cfg(feature = "indexmap")] +pub use index_set::FrozenIndexSet; diff --git a/vendor/elsa/src/map.rs b/vendor/elsa/src/map.rs new file mode 100644 index 000000000..2faa19ce2 --- /dev/null +++ b/vendor/elsa/src/map.rs @@ -0,0 +1,451 @@ +use std::borrow::Borrow; +use std::cell::{Cell, UnsafeCell}; +use std::collections::hash_map::RandomState; +use std::collections::BTreeMap; +use std::collections::HashMap; +use std::hash::{BuildHasher, Hash}; +use std::iter::FromIterator; +use std::ops::Index; + +use stable_deref_trait::StableDeref; + +/// Append-only version of `std::collections::HashMap` where +/// insertion does not require mutable access +pub struct FrozenMap<K, V, S = RandomState> { + map: UnsafeCell<HashMap<K, V, S>>, + /// Eq/Hash implementations can have side-effects, and using Rc it is possible + /// for FrozenMap::insert to be called on a key that itself contains the same + /// `FrozenMap`, whose `eq` implementation also calls FrozenMap::insert + /// + /// We use this `in_use` flag to guard against any reentrancy. + in_use: Cell<bool>, +} + +// safety: UnsafeCell implies !Sync + +impl<K: Eq + Hash, V> FrozenMap<K, V> { + pub fn new() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } + + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.len(), 0); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.len(), 1); + /// ``` + pub fn len(&self) -> usize { + assert!(!self.in_use.get()); + self.in_use.set(true); + let len = unsafe { + let map = self.map.get(); + (*map).len() + }; + self.in_use.set(false); + len + } + + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.is_empty(), true); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.is_empty(), false); + /// ``` + pub fn is_empty(&self) -> bool { + self.len() == 0 + } +} + +impl<K: Eq + Hash, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> { + // these should never return &K or &V + // these should never delete any entries + pub fn insert(&self, k: K, v: V) -> &V::Target { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + &*(*map).entry(k).or_insert(v) + }; + self.in_use.set(false); + ret + } + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(|x| &**x) + }; + self.in_use.set(false); + ret + } + + /// Applies a function to the owner of the value corresponding to the key (if any). + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a"))); + /// assert_eq!(map.map_get(&2, Clone::clone), None); + /// ``` + pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T> + where + K: Borrow<Q>, + Q: Hash + Eq, + F: FnOnce(&V) -> T, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(f) + }; + self.in_use.set(false); + ret + } + + pub fn into_map(self) -> HashMap<K, V, S> { + self.map.into_inner() + } + + // TODO add more +} + +impl<K: Eq + Hash + StableDeref, V: StableDeref, S: BuildHasher> FrozenMap<K, V, S> { + /// Returns a reference to the key and value matching a borrowed + /// key. + /// + /// The key argument may be any borrowed form of the map's key type, + /// but [`Hash`] and [`Eq`] on the borrowed form *must* match those + /// for the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(Box::new("1"), Box::new("a")); + /// assert_eq!(map.get_key_value(&"1"), Some((&"1", &"a"))); + /// assert_eq!(map.get_key_value(&"2"), None); + /// ``` + pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K::Target, &V::Target)> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get_key_value(k).map(|(k, v)| (&**k, &**v)) + }; + self.in_use.set(false); + ret + } +} + +impl<K, V, S> std::convert::AsMut<HashMap<K, V, S>> for FrozenMap<K, V, S> { + /// Get mutable access to the underlying [`HashMap`]. + /// + /// This is safe, as it requires a `&mut self`, ensuring nothing is using + /// the 'frozen' contents. + fn as_mut(&mut self) -> &mut HashMap<K, V, S> { + unsafe { &mut *self.map.get() } + } +} + +impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V, S> { + fn from(map: HashMap<K, V, S>) -> Self { + Self { + map: UnsafeCell::new(map), + in_use: Cell::new(false), + } + } +} + +impl<Q: ?Sized, K, V, S> Index<&Q> for FrozenMap<K, V, S> +where + Q: Eq + Hash, + K: Eq + Hash + Borrow<Q>, + V: StableDeref, + S: BuildHasher, +{ + type Output = V::Target; + + /// # Examples + /// + /// ``` + /// use elsa::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map[&1], "a"); + /// ``` + fn index(&self, idx: &Q) -> &V::Target { + self.get(idx) + .expect("attempted to index FrozenMap with unknown key") + } +} + +impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for FrozenMap<K, V, S> { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = (K, V)>, + { + let map: HashMap<_, _, _> = iter.into_iter().collect(); + map.into() + } +} + +impl<K: Eq + Hash, V, S: Default> Default for FrozenMap<K, V, S> { + fn default() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} + +/// Append-only version of `std::collections::BTreeMap` where +/// insertion does not require mutable access +pub struct FrozenBTreeMap<K, V> { + map: UnsafeCell<BTreeMap<K, V>>, + /// Eq/Hash implementations can have side-effects, and using Rc it is possible + /// for FrozenBTreeMap::insert to be called on a key that itself contains the same + /// `FrozenBTreeMap`, whose `eq` implementation also calls FrozenBTreeMap::insert + /// + /// We use this `in_use` flag to guard against any reentrancy. + in_use: Cell<bool>, +} + +// safety: UnsafeCell implies !Sync + +impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> { + pub fn new() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } + + /// # Examples + /// + /// ``` + /// use elsa::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// assert_eq!(map.len(), 0); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.len(), 1); + /// ``` + pub fn len(&self) -> usize { + assert!(!self.in_use.get()); + self.in_use.set(true); + let len = unsafe { + let map = self.map.get(); + (*map).len() + }; + self.in_use.set(false); + len + } + + /// # Examples + /// + /// ``` + /// use elsa::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// assert_eq!(map.is_empty(), true); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.is_empty(), false); + /// ``` + pub fn is_empty(&self) -> bool { + self.len() == 0 + } +} + +impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> { + // these should never return &K or &V + // these should never delete any entries + pub fn insert(&self, k: K, v: V) -> &V::Target { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + &*(*map).entry(k).or_insert(v) + }; + self.in_use.set(false); + ret + } + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow<Q>, + Q: Ord, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(|x| &**x) + }; + self.in_use.set(false); + ret + } + + /// Applies a function to the owner of the value corresponding to the key (if any). + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a"))); + /// assert_eq!(map.map_get(&2, Clone::clone), None); + /// ``` + pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T> + where + K: Borrow<Q>, + Q: Ord, + F: FnOnce(&V) -> T, + { + assert!(!self.in_use.get()); + self.in_use.set(true); + let ret = unsafe { + let map = self.map.get(); + (*map).get(k).map(f) + }; + self.in_use.set(false); + ret + } + + pub fn into_map(self) -> BTreeMap<K, V> { + self.map.into_inner() + } + + // TODO add more +} + +impl<K, V> std::convert::AsMut<BTreeMap<K, V>> for FrozenBTreeMap<K, V> { + /// Get mutable access to the underlying [`HashMap`]. + /// + /// This is safe, as it requires a `&mut self`, ensuring nothing is using + /// the 'frozen' contents. + fn as_mut(&mut self) -> &mut BTreeMap<K, V> { + unsafe { &mut *self.map.get() } + } +} + +impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> { + fn from(map: BTreeMap<K, V>) -> Self { + Self { + map: UnsafeCell::new(map), + in_use: Cell::new(false), + } + } +} + +impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V> +where + Q: Ord, + K: Clone + Ord + Borrow<Q>, + V: StableDeref, +{ + type Output = V::Target; + + /// # Examples + /// + /// ``` + /// use elsa::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map[&1], "a"); + /// ``` + fn index(&self, idx: &Q) -> &V::Target { + self.get(idx) + .expect("attempted to index FrozenBTreeMap with unknown key") + } +} + +impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = (K, V)>, + { + let map: BTreeMap<_, _> = iter.into_iter().collect(); + map.into() + } +} + +impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> { + fn default() -> Self { + Self { + map: UnsafeCell::new(Default::default()), + in_use: Cell::new(false), + } + } +} diff --git a/vendor/elsa/src/sync.rs b/vendor/elsa/src/sync.rs new file mode 100644 index 000000000..afa4bb7c7 --- /dev/null +++ b/vendor/elsa/src/sync.rs @@ -0,0 +1,624 @@ +//! **This module is experimental** +//! +//! This module provides threadsafe versions of FrozenMap and FrozenVec, +//! ideal for use as a cache. +//! +//! These lock internally, however locks only last as long as the method calls +//! + +use stable_deref_trait::StableDeref; +use std::alloc::Layout; +use std::borrow::Borrow; +use std::collections::BTreeMap; +use std::collections::HashMap; +use std::hash::Hash; +use std::iter::{FromIterator, IntoIterator}; +use std::mem::MaybeUninit; +use std::ops::Index; + +use std::sync::atomic::AtomicPtr; +use std::sync::atomic::AtomicUsize; +use std::sync::atomic::Ordering; +use std::sync::RwLock; + +/// Append-only threadsafe version of `std::collections::HashMap` where +/// insertion does not require mutable access +pub struct FrozenMap<K, V> { + map: RwLock<HashMap<K, V>>, +} + +impl<K, V> Default for FrozenMap<K, V> { + fn default() -> Self { + Self { + map: Default::default(), + } + } +} + +impl<K: Eq + Hash, V: StableDeref> FrozenMap<K, V> { + // these should never return &K or &V + // these should never delete any entries + + pub fn new() -> Self { + Self::default() + } + + /// If the key exists in the map, returns a reference + /// to the corresponding value, otherwise inserts a + /// new entry in the map for that key and returns a + /// reference to the given value. + /// + /// Existing values are never overwritten. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.insert(1, Box::new("a")), &"a"); + /// assert_eq!(map.insert(1, Box::new("b")), &"a"); + /// ``` + pub fn insert(&self, k: K, v: V) -> &V::Target { + let mut map = self.map.write().unwrap(); + let ret = unsafe { + let inserted = &**map.entry(k).or_insert(v); + &*(inserted as *const _) + }; + ret + } + + /// If the key exists in the map, returns a reference to the corresponding + /// value, otherwise inserts a new entry in the map for that key and the + /// value returned by the creation function, and returns a reference to the + /// generated value. + /// + /// Existing values are never overwritten. + /// + /// The key may be any borrowed form of the map's key type, but [`Hash`] and + /// [`Eq`] on the borrowed form *must* match those for the key type. + /// + /// **Note** that the write lock is held for the duration of this function’s + /// execution, even while the value creation function is executing (if + /// needed). This will block any concurrent `get` or `insert` calls. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.insert_with(1, || Box::new("a")), &"a"); + /// assert_eq!(map.insert_with(1, || unreachable!()), &"a"); + /// ``` + pub fn insert_with(&self, k: K, f: impl FnOnce() -> V) -> &V::Target { + let mut map = self.map.write().unwrap(); + let ret = unsafe { + let inserted = &**map.entry(k).or_insert_with(f); + &*(inserted as *const _) + }; + ret + } + + /// If the key exists in the map, returns a reference to the corresponding + /// value, otherwise inserts a new entry in the map for that key and the + /// value returned by the creation function, and returns a reference to the + /// generated value. + /// + /// Existing values are never overwritten. + /// + /// The key may be any borrowed form of the map's key type, but [`Hash`] and + /// [`Eq`] on the borrowed form *must* match those for the key type. + /// + /// **Note** that the write lock is held for the duration of this function’s + /// execution, even while the value creation function is executing (if + /// needed). This will block any concurrent `get` or `insert` calls. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.insert_with_key(1, |_| Box::new("a")), &"a"); + /// assert_eq!(map.insert_with_key(1, |_| unreachable!()), &"a"); + /// ``` + pub fn insert_with_key(&self, k: K, f: impl FnOnce(&K) -> V) -> &V::Target { + let mut map = self.map.write().unwrap(); + let ret = unsafe { + let inserted = &**map.entry(k).or_insert_with_key(f); + &*(inserted as *const _) + }; + ret + } + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + let map = self.map.read().unwrap(); + let ret = unsafe { map.get(k).map(|x| &*(&**x as *const V::Target)) }; + ret + } + + /// Applies a function to the owner of the value corresponding to the key (if any). + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a"))); + /// assert_eq!(map.map_get(&2, Clone::clone), None); + /// ``` + pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T> + where + K: Borrow<Q>, + Q: Hash + Eq, + F: FnOnce(&V) -> T, + { + let map = self.map.read().unwrap(); + let ret = map.get(k).map(f); + ret + } + + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.len(), 0); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.len(), 1); + /// ``` + pub fn len(&self) -> usize { + let map = self.map.read().unwrap(); + map.len() + } + + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenMap; + /// + /// let map = FrozenMap::new(); + /// assert_eq!(map.is_empty(), true); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.is_empty(), false); + /// ``` + pub fn is_empty(&self) -> bool { + let map = self.map.read().unwrap(); + map.is_empty() + } + + // TODO add more +} + +/// Append-only threadsafe version of `std::vec::Vec` where +/// insertion does not require mutable access +pub struct FrozenVec<T> { + vec: RwLock<Vec<T>>, +} + +impl<T> Default for FrozenVec<T> { + fn default() -> Self { + Self { + vec: Default::default(), + } + } +} + +impl<T: StableDeref> FrozenVec<T> { + pub fn new() -> Self { + Default::default() + } + + // these should never return &T + // these should never delete any entries + + pub fn push(&self, val: T) { + let mut vec = self.vec.write().unwrap(); + vec.push(val); + } + + /// Push, immediately getting a reference to the element + pub fn push_get(&self, val: T) -> &T::Target { + let mut vec = self.vec.write().unwrap(); + vec.push(val); + unsafe { &*(&**vec.get_unchecked(vec.len() - 1) as *const T::Target) } + } + + /// Push, immediately getting a an index of the element + /// + /// Index can then be used with the `get` method + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenVec; + /// + /// let map = FrozenVec::new(); + /// let idx = map.push_get_index(String::from("a")); + /// assert_eq!(map.get(idx), Some("a")); + /// assert_eq!(idx, 0); + /// assert_eq!(map.push_get_index(String::from("b")), 1); + /// ``` + pub fn push_get_index(&self, val: T) -> usize { + let mut vec = self.vec.write().unwrap(); + let index = vec.len(); + vec.push(val); + return index; + } + + pub fn get(&self, index: usize) -> Option<&T::Target> { + let vec = self.vec.read().unwrap(); + unsafe { vec.get(index).map(|x| &*(&**x as *const T::Target)) } + } + + // TODO add more +} + +/// Append-only threadsafe version of `std::vec::Vec` where +/// insertion does not require mutable access. +/// Does not have locks, only allows `Copy` types and will +/// spinlock on contention. The spinlocks are really rare as +/// they only happen on reallocation due to a push going over +/// the capacity. +pub struct LockFreeFrozenVec<T: Copy> { + data: AtomicPtr<T>, + len: AtomicUsize, + cap: AtomicUsize, +} + +impl<T: Copy> Drop for LockFreeFrozenVec<T> { + fn drop(&mut self) { + let cap = *self.cap.get_mut(); + let layout = self.layout(cap); + unsafe { + std::alloc::dealloc((*self.data.get_mut()).cast(), layout); + } + } +} + +impl<T: Copy> Default for LockFreeFrozenVec<T> { + fn default() -> Self { + Self { + // FIXME: use `std::ptr::invalid_mut()` once that is stable. + data: AtomicPtr::new(std::mem::align_of::<T>() as *mut T), + len: AtomicUsize::new(0), + cap: AtomicUsize::new(0), + } + } +} + +impl<T: Copy> LockFreeFrozenVec<T> { + pub fn new() -> Self { + Default::default() + } + + pub fn with_capacity(cap: usize) -> Self { + Self { + data: AtomicPtr::new( + Box::into_raw(vec![MaybeUninit::<T>::uninit(); cap].into_boxed_slice()).cast(), + ), + len: AtomicUsize::new(0), + cap: AtomicUsize::new(cap), + } + } + + fn lock<U>(&self, f: impl FnOnce(&mut *mut T) -> U) -> U { + let mut ptr; + loop { + ptr = self.data.swap(std::ptr::null_mut(), Ordering::Acquire); + if !ptr.is_null() { + // Wheeeee spinlock + break; + } + } + + let ret = f(&mut ptr); + self.data.store(ptr, Ordering::Release); + ret + } + + fn layout(&self, cap: usize) -> Layout { + let num_bytes = std::mem::size_of::<T>() * cap; + let align = std::mem::align_of::<T>(); + Layout::from_size_align(num_bytes, align).unwrap() + } + + // these should never return &T + // these should never delete any entries + + const NOT_ZST: () = if std::mem::size_of::<T>() == 0 { + panic!("`LockFreeFrozenVec` cannot be used with ZSTs"); + }; + + pub fn push(&self, val: T) -> usize { + // This statement actually does something: it evaluates a constant. + #[allow(path_statements)] + { + Self::NOT_ZST + } + self.lock(|ptr| { + // These values must be consistent with the pointer we got. + let len = self.len.load(Ordering::Acquire); + let cap = self.cap.load(Ordering::Acquire); + if len >= cap { + if cap == 0 { + // No memory allocated yet + let layout = self.layout(128); + // SAFETY: `LockFreeFrozenVec` statically rejects zsts + unsafe { + *ptr = std::alloc::alloc(layout).cast::<T>(); + } + // This is written before the end of the `lock` closure, so no one will observe this + // until the data pointer has been updated anyway. + self.cap.store(128, Ordering::Release); + } else { + // Out of memory, realloc with double the capacity + let layout = self.layout(cap); + let new_size = layout.size() * 2; + // SAFETY: `LockFreeFrozenVec` statically rejects zsts and the input `ptr` has always been + // allocated at the size stated in `cap`. + unsafe { + *ptr = std::alloc::realloc((*ptr).cast(), layout, new_size).cast::<T>(); + } + // This is written before the end of the `lock` closure, so no one will observe this + // until the data pointer has been updated anyway. + self.cap.store(cap * 2, Ordering::Release); + } + assert!(!ptr.is_null()); + } + unsafe { + ptr.add(len).write(val); + } + // This is written before updating the data pointer. Other `push` calls cannot observe this, + // because they are blocked on aquiring the data pointer before they ever read the `len`. + // `get` may read the length before actually aquiring the data pointer lock, but that is fine, + // as once it is able to aquire the lock, there will be actually the right number of elements + // stored. + self.len.store(len + 1, Ordering::Release); + len + }) + } + + pub fn get(&self, index: usize) -> Option<T> { + // The length can only grow, so just doing the length check + // independently of the `lock` and read is fine. Worst case we + // read an old length value and end up returning `None` even if + // another thread already inserted the value. + let len = self.len.load(Ordering::Relaxed); + if index >= len { + return None; + } + self.lock(|ptr| Some(unsafe { ptr.add(index).read() })) + } +} + +#[test] +fn test_non_lockfree() { + #[derive(Copy, Clone, Debug, PartialEq, Eq)] + struct Moo(i32); + + for vec in [ + LockFreeFrozenVec::new(), + LockFreeFrozenVec::with_capacity(1), + LockFreeFrozenVec::with_capacity(2), + LockFreeFrozenVec::with_capacity(1000), + ] { + assert_eq!(vec.get(1), None); + + vec.push(Moo(1)); + let i = vec.push(Moo(2)); + vec.push(Moo(3)); + + assert_eq!(vec.get(i), Some(Moo(2))); + + std::thread::scope(|s| { + s.spawn(|| { + for i in 0..1000 { + vec.push(Moo(i)); + } + }); + s.spawn(|| { + for i in 0..1000 { + vec.push(Moo(i)); + } + }); + for i in 0..2000 { + while vec.get(i).is_none() {} + } + }); + } +} + +/// Append-only threadsafe version of `std::collections::BTreeMap` where +/// insertion does not require mutable access +#[derive(Debug)] +pub struct FrozenBTreeMap<K, V>(RwLock<BTreeMap<K, V>>); + +impl<K: Clone + Ord, V: StableDeref> FrozenBTreeMap<K, V> { + pub fn new() -> Self { + Self(RwLock::new(BTreeMap::new())) + } + + // these should never return &K or &V + // these should never delete any entries + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Ord`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V::Target> + where + K: Borrow<Q>, + Q: Ord, + { + let map = self.0.read().unwrap(); + let ret = unsafe { map.get(k).map(|x| &*(&**x as *const V::Target)) }; + ret + } + + /// Insert a new value into the map. Does nothing if the key is already occupied. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.get(&1), Some(&"a")); + /// ``` + pub fn insert(&self, k: K, v: V) -> &V::Target { + let mut map = self.0.write().unwrap(); + let ret = unsafe { + let inserted = &**map.entry(k).or_insert(v); + &*(inserted as *const _) + }; + ret + } + + /// Applies a function to the owner of the value corresponding to the key (if any). + /// + /// The key may be any borrowed form of the map's key type, but + /// [`Ord`] on the borrowed form *must* match those for + /// the key type. + /// + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.map_get(&1, Clone::clone), Some(Box::new("a"))); + /// assert_eq!(map.map_get(&2, Clone::clone), None); + /// ``` + pub fn map_get<Q: ?Sized, T, F>(&self, k: &Q, f: F) -> Option<T> + where + K: Borrow<Q>, + Q: Ord, + F: FnOnce(&V) -> T, + { + let map = self.0.read().unwrap(); + let ret = map.get(k).map(f); + ret + } + + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// assert_eq!(map.len(), 0); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.len(), 1); + /// ``` + pub fn len(&self) -> usize { + let map = self.0.read().unwrap(); + map.len() + } + + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// assert_eq!(map.is_empty(), true); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map.is_empty(), false); + /// ``` + pub fn is_empty(&self) -> bool { + let map = self.0.read().unwrap(); + map.is_empty() + } +} + +impl<K: Clone + Ord, V: StableDeref> From<BTreeMap<K, V>> for FrozenBTreeMap<K, V> { + fn from(map: BTreeMap<K, V>) -> Self { + Self(RwLock::new(map)) + } +} + +impl<Q: ?Sized, K, V> Index<&Q> for FrozenBTreeMap<K, V> +where + Q: Ord, + K: Clone + Ord + Borrow<Q>, + V: StableDeref, +{ + type Output = V::Target; + + /// # Examples + /// + /// ``` + /// use elsa::sync::FrozenBTreeMap; + /// + /// let map = FrozenBTreeMap::new(); + /// map.insert(1, Box::new("a")); + /// assert_eq!(map[&1], "a"); + /// ``` + fn index(&self, idx: &Q) -> &V::Target { + self.get(idx) + .expect("attempted to index FrozenBTreeMap with unknown key") + } +} + +impl<K: Clone + Ord, V: StableDeref> FromIterator<(K, V)> for FrozenBTreeMap<K, V> { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = (K, V)>, + { + let map: BTreeMap<_, _> = iter.into_iter().collect(); + map.into() + } +} + +impl<K: Clone + Ord, V: StableDeref> Default for FrozenBTreeMap<K, V> { + fn default() -> Self { + Self::new() + } +} diff --git a/vendor/elsa/src/vec.rs b/vendor/elsa/src/vec.rs new file mode 100644 index 000000000..33b6e6a50 --- /dev/null +++ b/vendor/elsa/src/vec.rs @@ -0,0 +1,347 @@ +use std::cell::UnsafeCell; +use std::cmp::Ordering; +use std::iter::FromIterator; +use std::ops::Index; + +use stable_deref_trait::StableDeref; + +/// Append-only version of `std::vec::Vec` where +/// insertion does not require mutable access +pub struct FrozenVec<T> { + vec: UnsafeCell<Vec<T>>, + // XXXManishearth do we need a reentrancy guard here as well? + // StableDeref may not guarantee that there are no side effects +} + +// safety: UnsafeCell implies !Sync + +impl<T> FrozenVec<T> { + /// Constructs a new, empty vector. + pub fn new() -> Self { + Self { + vec: UnsafeCell::new(Default::default()), + } + } +} + +impl<T> FrozenVec<T> { + // these should never return &T + // these should never delete any entries + + /// Appends an element to the back of the vector. + pub fn push(&self, val: T) { + unsafe { + let vec = self.vec.get(); + (*vec).push(val) + } + } +} + +impl<T: StableDeref> FrozenVec<T> { + /// Push, immediately getting a reference to the element + pub fn push_get(&self, val: T) -> &T::Target { + unsafe { + let vec = self.vec.get(); + (*vec).push(val); + &*(&**(*vec).get_unchecked((*vec).len() - 1) as *const T::Target) + } + } + + /// Returns a reference to an element. + pub fn get(&self, index: usize) -> Option<&T::Target> { + unsafe { + let vec = self.vec.get(); + (*vec).get(index).map(|x| &**x) + } + } + + /// Returns a reference to an element, without doing bounds checking. + /// + /// ## Safety + /// + /// `index` must be in bounds, i.e. it must be less than `self.len()` + pub unsafe fn get_unchecked(&self, index: usize) -> &T::Target { + let vec = self.vec.get(); + &**(*vec).get_unchecked(index) + } +} + +impl<T: Copy> FrozenVec<T> { + /// Returns a copy of an element. + pub fn get_copy(&self, index: usize) -> Option<T> { + unsafe { + let vec = self.vec.get(); + (*vec).get(index).copied() + } + } +} + +impl<T> FrozenVec<T> { + /// Returns the number of elements in the vector. + pub fn len(&self) -> usize { + unsafe { + let vec = self.vec.get(); + (*vec).len() + } + } + + /// Returns `true` if the vector contains no elements. + pub fn is_empty(&self) -> bool { + self.len() == 0 + } +} + +impl<T: StableDeref> FrozenVec<T> { + /// Returns the first element of the vector, or `None` if empty. + pub fn first(&self) -> Option<&T::Target> { + unsafe { + let vec = self.vec.get(); + (*vec).first().map(|x| &**x) + } + } + + /// Returns the last element of the vector, or `None` if empty. + pub fn last(&self) -> Option<&T::Target> { + unsafe { + let vec = self.vec.get(); + (*vec).last().map(|x| &**x) + } + } + /// Returns an iterator over the vector. + pub fn iter(&self) -> Iter<T> { + self.into_iter() + } +} + +impl<T: StableDeref> FrozenVec<T> { + /// Converts the frozen vector into a plain vector. + pub fn into_vec(self) -> Vec<T> { + self.vec.into_inner() + } +} + +impl<T: StableDeref> FrozenVec<T> { + // binary search functions: they need to be reimplemented here to be safe (instead of calling + // their equivalents directly on the underlying Vec), as they run user callbacks that could + // reentrantly call other functions on this vector + + /// Binary searches this sorted vector for a given element, analogous to [slice::binary_search]. + pub fn binary_search(&self, x: &T::Target) -> Result<usize, usize> + where + T::Target: Ord, + { + self.binary_search_by(|p| p.cmp(x)) + } + + /// Binary searches this sorted vector with a comparator function, analogous to + /// [slice::binary_search_by]. + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a T::Target) -> Ordering, + { + let mut size = self.len(); + let mut left = 0; + let mut right = size; + while left < right { + let mid = left + size / 2; + + // safety: like the core algorithm, mid is always within original vector len; in + // pathlogical cases, user could push to the vector in the meantime, but this can only + // increase the length, keeping this safe + let cmp = f(unsafe { self.get_unchecked(mid) }); + + if cmp == Ordering::Less { + left = mid + 1; + } else if cmp == Ordering::Greater { + right = mid; + } else { + return Ok(mid); + } + + size = right - left; + } + Err(left) + } + + /// Binary searches this sorted vector with a key extraction function, analogous to + /// [slice::binary_search_by_key]. + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a T::Target) -> B, + B: Ord, + { + self.binary_search_by(|k| f(k).cmp(b)) + } + + /// Returns the index of the partition point according to the given predicate + /// (the index of the first element of the second partition), analogous to + /// [slice::partition_point]. + pub fn partition_point<P>(&self, mut pred: P) -> usize + where + P: FnMut(&T::Target) -> bool, + { + let mut left = 0; + let mut right = self.len(); + + while left != right { + let mid = left + (right - left) / 2; + // safety: like in binary_search_by + let value = unsafe { self.get_unchecked(mid) }; + if pred(value) { + left = mid + 1; + } else { + right = mid; + } + } + + left + } + + // TODO add more +} + +impl<T> std::convert::AsMut<Vec<T>> for FrozenVec<T> { + /// Get mutable access to the underlying vector. + /// + /// This is safe, as it requires a `&mut self`, ensuring nothing is using + /// the 'frozen' contents. + fn as_mut(&mut self) -> &mut Vec<T> { + unsafe { &mut *self.vec.get() } + } +} + +impl<T> Default for FrozenVec<T> { + fn default() -> Self { + FrozenVec::new() + } +} + +impl<T> From<Vec<T>> for FrozenVec<T> { + fn from(vec: Vec<T>) -> Self { + Self { + vec: UnsafeCell::new(vec), + } + } +} + +impl<T: StableDeref> Index<usize> for FrozenVec<T> { + type Output = T::Target; + fn index(&self, idx: usize) -> &T::Target { + self.get(idx).unwrap_or_else(|| { + panic!( + "index out of bounds: the len is {} but the index is {}", + self.len(), + idx + ) + }) + } +} + +impl<A> FromIterator<A> for FrozenVec<A> { + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = A>, + { + let vec: Vec<_> = iter.into_iter().collect(); + vec.into() + } +} + +/// Iterator over FrozenVec, obtained via `.iter()` +/// +/// It is safe to push to the vector during iteration +pub struct Iter<'a, T> { + vec: &'a FrozenVec<T>, + idx: usize, +} + +impl<'a, T: StableDeref> Iterator for Iter<'a, T> { + type Item = &'a T::Target; + fn next(&mut self) -> Option<&'a T::Target> { + if let Some(ret) = self.vec.get(self.idx) { + self.idx += 1; + Some(ret) + } else { + None + } + } +} + +impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> { + type Item = &'a T::Target; + type IntoIter = Iter<'a, T>; + fn into_iter(self) -> Iter<'a, T> { + Iter { vec: self, idx: 0 } + } +} + +#[test] +fn test_iteration() { + let vec = vec!["a", "b", "c", "d"]; + let frozen: FrozenVec<_> = vec.clone().into(); + + assert_eq!(vec, frozen.iter().collect::<Vec<_>>()); + for (e1, e2) in vec.iter().zip(frozen.iter()) { + assert_eq!(*e1, e2); + } + + assert_eq!(vec.len(), frozen.iter().count()) +} + +#[test] +fn test_accessors() { + let vec: FrozenVec<String> = FrozenVec::new(); + + assert_eq!(vec.is_empty(), true); + assert_eq!(vec.len(), 0); + assert_eq!(vec.first(), None); + assert_eq!(vec.last(), None); + assert_eq!(vec.get(1), None); + + vec.push("a".to_string()); + vec.push("b".to_string()); + vec.push("c".to_string()); + + assert_eq!(vec.is_empty(), false); + assert_eq!(vec.len(), 3); + assert_eq!(vec.first(), Some("a")); + assert_eq!(vec.last(), Some("c")); + assert_eq!(vec.get(1), Some("b")); +} + +#[test] +fn test_non_stable_deref() { + #[derive(Copy, Clone, Debug, PartialEq, Eq)] + struct Moo(i32); + let vec: FrozenVec<Moo> = FrozenVec::new(); + + assert_eq!(vec.is_empty(), true); + assert_eq!(vec.len(), 0); + assert_eq!(vec.get_copy(1), None); + + vec.push(Moo(1)); + vec.push(Moo(2)); + vec.push(Moo(3)); + + assert_eq!(vec.is_empty(), false); + assert_eq!(vec.len(), 3); + assert_eq!(vec.get_copy(1), Some(Moo(2))); +} + +#[test] +fn test_binary_search() { + let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into(); + + assert_eq!(vec.binary_search("cde"), Ok(1)); + assert_eq!(vec.binary_search("cdf"), Err(2)); + assert_eq!(vec.binary_search("a"), Err(0)); + assert_eq!(vec.binary_search("g"), Err(3)); + + assert_eq!(vec.binary_search_by_key(&1, |x| x.len()), Err(0)); + assert_eq!(vec.binary_search_by_key(&3, |x| x.len()), Ok(1)); + assert_eq!(vec.binary_search_by_key(&4, |x| x.len()), Err(2)); + + assert_eq!(vec.partition_point(|x| x.len() < 4), 2); + assert_eq!(vec.partition_point(|_| false), 0); + assert_eq!(vec.partition_point(|_| true), 3); +} |