diff options
Diffstat (limited to 'third_party/rust/id-arena')
| -rw-r--r-- | third_party/rust/id-arena/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/id-arena/CHANGELOG.md | 65 | ||||
| -rw-r--r-- | third_party/rust/id-arena/Cargo.toml | 31 | ||||
| -rw-r--r-- | third_party/rust/id-arena/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | third_party/rust/id-arena/LICENSE-MIT | 25 | ||||
| -rw-r--r-- | third_party/rust/id-arena/README.md | 100 | ||||
| -rw-r--r-- | third_party/rust/id-arena/README.tpl | 3 | ||||
| -rw-r--r-- | third_party/rust/id-arena/src/lib.rs | 726 | ||||
| -rw-r--r-- | third_party/rust/id-arena/src/rayon.rs | 282 | ||||
| -rw-r--r-- | third_party/rust/id-arena/tests/readme_up_to_date.rs | 22 |
10 files changed, 1456 insertions, 0 deletions
diff --git a/third_party/rust/id-arena/.cargo-checksum.json b/third_party/rust/id-arena/.cargo-checksum.json new file mode 100644 index 0000000000..f28430a787 --- /dev/null +++ b/third_party/rust/id-arena/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"44d2bc9ae9829b9d80bbd64cf758a29c5b7a136e8049bde601f25b504ff5daf8","Cargo.toml":"68ffe09814502adc81ab77dacc5d76e5f439435a71b48ec9c575289193945cb7","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"378f5840b258e2779c39418f3f2d7b2ba96f1c7917dd6be0713f88305dbda397","README.md":"74619b782c5085d5e12762a2a209555e90770d0e08048d95a31f95febac0b4c6","README.tpl":"ec385000e14590a306855e7893daed0168102f33166bdc1e5cf5fa5599dac03f","src/lib.rs":"ee705a8a93ccfa0f958e421a1e27440e5b92afd422ee6579f66282287cb9abe8","src/rayon.rs":"48807a5563e6c248bab2731b60b00148084db9c071cf3c47cdb12dc7ecfa84e0","tests/readme_up_to_date.rs":"8db3e41d803e2a10307e7e35cb2afa6733e1c39ad34789752a927564bf6795b6"},"package":"25a2bc672d1148e28034f176e01fffebb08b35768468cc954630da77a1449005"}
\ No newline at end of file diff --git a/third_party/rust/id-arena/CHANGELOG.md b/third_party/rust/id-arena/CHANGELOG.md new file mode 100644 index 0000000000..0f3ecde738 --- /dev/null +++ b/third_party/rust/id-arena/CHANGELOG.md @@ -0,0 +1,65 @@ +# 2.2.1 + +Released 2019-02-15. + +* Make sure our rayon parallel iterators are exported. Previously instances of + them were returned by `pub` methods but the types themselves were not + exported. + +# 2.2.0 + +Released 2019-01-30. + +* Add the `Arena::alloc_with_id` method. This is better than using + `Arena::next_id` directly most of the time (but is also not *quite* as + flexible). See [#9](https://github.com/fitzgen/id-arena/issues/9) and + [#10](https://github.com/fitzgen/id-arena/pull/10). + +-------------------------------------------------------------------------------- + +# 2.1.0 + +Released 2019-01-25. + +* Added optional support for `rayon` parallel iteration. Enable the `rayon` + Cargo feature to get access. + +-------------------------------------------------------------------------------- + +# 2.0.1 + +Released 2019-01-09. + +* Implemented `Ord` and `PartialOrd` for `Id<T>`. +* Added an `Arena::with_capacity` constructor. +* Added `Arena::next_id` to get the id that will be used for the next + allocation. + +-------------------------------------------------------------------------------- + +# 2.0.0 + +Released 2018-11-28. + +* Introduces the `ArenaBehavior` trait, which allows one to customize identifier + types and do things like implement space optimizations or use identifiers for + many arenas at once. +* Implements `Clone`, `PartialEq` and `Eq` for arenas. + +-------------------------------------------------------------------------------- + +# 1.0.2 + +Released 2018-11-25. + +* `Id<T>` now implements `Send` and `Sync` +* The `PartialEq` implementation for `Id<T>` now correctly checks that two ids + are for the same arena when checking equality. + +-------------------------------------------------------------------------------- + +# 1.0.1 + +-------------------------------------------------------------------------------- + +# 1.0.0 diff --git a/third_party/rust/id-arena/Cargo.toml b/third_party/rust/id-arena/Cargo.toml new file mode 100644 index 0000000000..c8566221d4 --- /dev/null +++ b/third_party/rust/id-arena/Cargo.toml @@ -0,0 +1,31 @@ +# 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 believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +name = "id-arena" +version = "2.2.1" +authors = ["Nick Fitzgerald <fitzgen@gmail.com>", "Aleksey Kladov <aleksey.kladov@gmail.com>"] +description = "A simple, id-based arena." +documentation = "https://docs.rs/id-arena" +readme = "README.md" +categories = ["memory-management", "rust-patterns", "no-std"] +license = "MIT/Apache-2.0" +repository = "https://github.com/fitzgen/id-arena" +[package.metadata.docs.rs] +features = ["rayon"] +[dependencies.rayon] +version = "1.0.3" +optional = true + +[features] +default = ["std"] +std = [] diff --git a/third_party/rust/id-arena/LICENSE-APACHE b/third_party/rust/id-arena/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/id-arena/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/id-arena/LICENSE-MIT b/third_party/rust/id-arena/LICENSE-MIT new file mode 100644 index 0000000000..39e0ed6602 --- /dev/null +++ b/third_party/rust/id-arena/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2014 Alex Crichton + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/third_party/rust/id-arena/README.md b/third_party/rust/id-arena/README.md new file mode 100644 index 0000000000..a783f1ce0b --- /dev/null +++ b/third_party/rust/id-arena/README.md @@ -0,0 +1,100 @@ +# `id-arena` + +[](https://crates.io/crates/id-arena) +[](https://crates.io/crates/id-arena) +[](https://travis-ci.org/fitzgen/id-arena) + +A simple, id-based arena. + +### Id-based + +Allocate objects and get an identifier for that object back, *not* a +reference to the allocated object. Given an id, you can get a shared or +exclusive reference to the allocated object from the arena. This id-based +approach is useful for constructing mutable graph data structures. + +If you want allocation to return a reference, consider [the `typed-arena` +crate](https://github.com/SimonSapin/rust-typed-arena/) instead. + +### No Deletion + +This arena does not support deletion, which makes its implementation simple +and allocation fast. If you want deletion, you need a way to solve the ABA +problem. Consider using [the `generational-arena` +crate](https://github.com/fitzgen/generational-arena) instead. + +### Homogeneous + +This crate's arenas can only contain objects of a single type `T`. If you +need an arena of objects with heterogeneous types, consider another crate. + +### `#![no_std]` Support + +Requires the `alloc` nightly feature. Disable the on-by-default `"std"` feature: + +```toml +[dependencies.id-arena] +version = "2" +default-features = false +``` + +### `rayon` Support + +If the `rayon` feature of this crate is activated: + +```toml +[dependencies] +id-arena = { version = "2", features = ["rayon"] } +``` + +then you can use [`rayon`](https://crates.io/crates/rayon)'s support for +parallel iteration. The `Arena` type will have a `par_iter` family of +methods where appropriate. + +### Example + +```rust +use id_arena::{Arena, Id}; + +type AstNodeId = Id<AstNode>; + +#[derive(Debug, Eq, PartialEq)] +pub enum AstNode { + Const(i64), + Var(String), + Add { + lhs: AstNodeId, + rhs: AstNodeId, + }, + Sub { + lhs: AstNodeId, + rhs: AstNodeId, + }, + Mul { + lhs: AstNodeId, + rhs: AstNodeId, + }, + Div { + lhs: AstNodeId, + rhs: AstNodeId, + }, +} + +let mut ast_nodes = Arena::<AstNode>::new(); + +// Create the AST for `a * (b + 3)`. +let three = ast_nodes.alloc(AstNode::Const(3)); +let b = ast_nodes.alloc(AstNode::Var("b".into())); +let b_plus_three = ast_nodes.alloc(AstNode::Add { + lhs: b, + rhs: three, +}); +let a = ast_nodes.alloc(AstNode::Var("a".into())); +let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul { + lhs: a, + rhs: b_plus_three, +}); + +// Can use indexing to access allocated nodes. +assert_eq!(ast_nodes[three], AstNode::Const(3)); +``` diff --git a/third_party/rust/id-arena/README.tpl b/third_party/rust/id-arena/README.tpl new file mode 100644 index 0000000000..56c38d5f08 --- /dev/null +++ b/third_party/rust/id-arena/README.tpl @@ -0,0 +1,3 @@ +# `{{crate}}` + +{{readme}} diff --git a/third_party/rust/id-arena/src/lib.rs b/third_party/rust/id-arena/src/lib.rs new file mode 100644 index 0000000000..0c0edd4e60 --- /dev/null +++ b/third_party/rust/id-arena/src/lib.rs @@ -0,0 +1,726 @@ +//! [](https://crates.io/crates/id-arena) +//! [](https://crates.io/crates/id-arena) +//! [](https://travis-ci.org/fitzgen/id-arena) +//! +//! A simple, id-based arena. +//! +//! ## Id-based +//! +//! Allocate objects and get an identifier for that object back, *not* a +//! reference to the allocated object. Given an id, you can get a shared or +//! exclusive reference to the allocated object from the arena. This id-based +//! approach is useful for constructing mutable graph data structures. +//! +//! If you want allocation to return a reference, consider [the `typed-arena` +//! crate](https://github.com/SimonSapin/rust-typed-arena/) instead. +//! +//! ## No Deletion +//! +//! This arena does not support deletion, which makes its implementation simple +//! and allocation fast. If you want deletion, you need a way to solve the ABA +//! problem. Consider using [the `generational-arena` +//! crate](https://github.com/fitzgen/generational-arena) instead. +//! +//! ## Homogeneous +//! +//! This crate's arenas can only contain objects of a single type `T`. If you +//! need an arena of objects with heterogeneous types, consider another crate. +//! +//! ## `#![no_std]` Support +//! +//! Requires the `alloc` nightly feature. Disable the on-by-default `"std"` feature: +//! +//! ```toml +//! [dependencies.id-arena] +//! version = "2" +//! default-features = false +//! ``` +//! +//! ## `rayon` Support +//! +//! If the `rayon` feature of this crate is activated: +//! +//! ```toml +//! [dependencies] +//! id-arena = { version = "2", features = ["rayon"] } +//! ``` +//! +//! then you can use [`rayon`](https://crates.io/crates/rayon)'s support for +//! parallel iteration. The `Arena` type will have a `par_iter` family of +//! methods where appropriate. +//! +//! ## Example +//! +//! ```rust +//! use id_arena::{Arena, Id}; +//! +//! type AstNodeId = Id<AstNode>; +//! +//! #[derive(Debug, Eq, PartialEq)] +//! pub enum AstNode { +//! Const(i64), +//! Var(String), +//! Add { +//! lhs: AstNodeId, +//! rhs: AstNodeId, +//! }, +//! Sub { +//! lhs: AstNodeId, +//! rhs: AstNodeId, +//! }, +//! Mul { +//! lhs: AstNodeId, +//! rhs: AstNodeId, +//! }, +//! Div { +//! lhs: AstNodeId, +//! rhs: AstNodeId, +//! }, +//! } +//! +//! let mut ast_nodes = Arena::<AstNode>::new(); +//! +//! // Create the AST for `a * (b + 3)`. +//! let three = ast_nodes.alloc(AstNode::Const(3)); +//! let b = ast_nodes.alloc(AstNode::Var("b".into())); +//! let b_plus_three = ast_nodes.alloc(AstNode::Add { +//! lhs: b, +//! rhs: three, +//! }); +//! let a = ast_nodes.alloc(AstNode::Var("a".into())); +//! let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul { +//! lhs: a, +//! rhs: b_plus_three, +//! }); +//! +//! // Can use indexing to access allocated nodes. +//! assert_eq!(ast_nodes[three], AstNode::Const(3)); +//! ``` + +#![forbid(unsafe_code)] +#![deny(missing_debug_implementations)] +#![deny(missing_docs)] +// In no-std mode, use the alloc crate to get `Vec`. +#![no_std] +#![cfg_attr(not(feature = "std"), feature(alloc))] + +use core::cmp::Ordering; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::iter; +use core::marker::PhantomData; +use core::ops; +use core::slice; +use core::sync::atomic::{self, AtomicUsize, ATOMIC_USIZE_INIT}; + +#[cfg(not(feature = "std"))] +extern crate alloc; +#[cfg(not(feature = "std"))] +use alloc::vec::{self, Vec}; + +#[cfg(feature = "std")] +extern crate std; +#[cfg(feature = "std")] +use std::vec::{self, Vec}; + +#[cfg(feature = "rayon")] +mod rayon; +#[cfg(feature = "rayon")] +pub use rayon::*; + +/// A trait representing the implementation behavior of an arena and how +/// identifiers are represented. +/// +/// ## When should I implement `ArenaBehavior` myself? +/// +/// Usually, you should just use `DefaultArenaBehavior`, which is simple and +/// correct. However, there are some scenarios where you might want to implement +/// `ArenaBehavior` yourself: +/// +/// * **Space optimizations:** The default identifier is two words in size, +/// which is larger than is usually necessary. For example, if you know that an +/// arena *cannot* contain more than 256 items, you could make your own +/// identifier type that stores the index as a `u8` and then you can save some +/// space. +/// +/// * **Trait Coherence:** If you need to implement an upstream crate's traits +/// for identifiers, then defining your own identifier type allows you to work +/// with trait coherence rules. +/// +/// * **Share identifiers across arenas:** You can coordinate and share +/// identifiers across different arenas to enable a "struct of arrays" style +/// data representation. +pub trait ArenaBehavior { + /// The identifier type. + type Id: Copy; + + /// Construct a new object identifier from the given index and arena + /// identifier. + /// + /// ## Panics + /// + /// Implementations are allowed to panic if the given index is larger than + /// the underlying storage (e.g. the implementation uses a `u8` for storing + /// indices and the given index value is larger than 255). + fn new_id(arena_id: u32, index: usize) -> Self::Id; + + /// Get the given identifier's index. + fn index(Self::Id) -> usize; + + /// Get the given identifier's arena id. + fn arena_id(Self::Id) -> u32; + + /// Construct a new arena identifier. + /// + /// This is used to disambiguate `Id`s across different arenas. To make + /// identifiers with the same index from different arenas compare false for + /// equality, return a unique `u32` on every invocation. This is the + /// default, provided implementation's behavior. + /// + /// To make identifiers with the same index from different arenas compare + /// true for equality, return the same `u32` on every invocation. + fn new_arena_id() -> u32 { + static ARENA_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT; + ARENA_COUNTER.fetch_add(1, atomic::Ordering::SeqCst) as u32 + } +} + +/// An identifier for an object allocated within an arena. +pub struct Id<T> { + idx: usize, + arena_id: u32, + _ty: PhantomData<fn() -> T>, +} + +impl<T> fmt::Debug for Id<T> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("Id").field("idx", &self.idx).finish() + } +} + +impl<T> Copy for Id<T> {} + +impl<T> Clone for Id<T> { + #[inline] + fn clone(&self) -> Id<T> { + *self + } +} + +impl<T> PartialEq for Id<T> { + #[inline] + fn eq(&self, rhs: &Self) -> bool { + self.arena_id == rhs.arena_id && self.idx == rhs.idx + } +} + +impl<T> Eq for Id<T> {} + +impl<T> Hash for Id<T> { + #[inline] + fn hash<H: Hasher>(&self, h: &mut H) { + self.arena_id.hash(h); + self.idx.hash(h); + } +} + +impl<T> PartialOrd for Id<T> { + fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> { + Some(self.cmp(rhs)) + } +} + +impl<T> Ord for Id<T> { + fn cmp(&self, rhs: &Self) -> Ordering { + self.arena_id + .cmp(&rhs.arena_id) + .then(self.idx.cmp(&rhs.idx)) + } +} + +impl<T> Id<T> { + /// Get the index within the arena that this id refers to. + #[inline] + pub fn index(&self) -> usize { + self.idx + } +} + +/// The default `ArenaBehavior` implementation. +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct DefaultArenaBehavior<T> { + _phantom: PhantomData<fn() -> T>, +} + +impl<T> ArenaBehavior for DefaultArenaBehavior<T> { + type Id = Id<T>; + + #[inline] + fn new_id(arena_id: u32, idx: usize) -> Self::Id { + Id { + idx, + arena_id, + _ty: PhantomData, + } + } + + #[inline] + fn index(id: Self::Id) -> usize { + id.idx + } + + #[inline] + fn arena_id(id: Self::Id) -> u32 { + id.arena_id + } +} + +/// An arena of objects of type `T`. +/// +/// ``` +/// use id_arena::Arena; +/// +/// let mut arena = Arena::<&str>::new(); +/// +/// let a = arena.alloc("Albert"); +/// assert_eq!(arena[a], "Albert"); +/// +/// arena[a] = "Alice"; +/// assert_eq!(arena[a], "Alice"); +/// ``` +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct Arena<T, A = DefaultArenaBehavior<T>> { + arena_id: u32, + items: Vec<T>, + _phantom: PhantomData<fn() -> A>, +} + +impl<T, A> Default for Arena<T, A> +where + A: ArenaBehavior, +{ + #[inline] + fn default() -> Arena<T, A> { + Arena { + arena_id: A::new_arena_id(), + items: Vec::new(), + _phantom: PhantomData, + } + } +} + +impl<T, A> Arena<T, A> +where + A: ArenaBehavior, +{ + /// Construct a new, empty `Arena`. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<usize>::new(); + /// arena.alloc(42); + /// ``` + #[inline] + pub fn new() -> Arena<T, A> { + Default::default() + } + + /// Construct a new, empty `Arena` with capacity for the given number of + /// elements. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<usize>::with_capacity(100); + /// for x in 0..100 { + /// arena.alloc(x * x); + /// } + /// ``` + #[inline] + pub fn with_capacity(capacity: usize) -> Arena<T, A> { + Arena { + arena_id: A::new_arena_id(), + items: Vec::with_capacity(capacity), + _phantom: PhantomData, + } + } + + /// Allocate `item` within this arena and return its id. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<usize>::new(); + /// let _id = arena.alloc(42); + /// ``` + /// + /// ## Panics + /// + /// Panics if the number of elements in the arena overflows a `usize` or + /// `Id`'s index storage representation. + #[inline] + pub fn alloc(&mut self, item: T) -> A::Id { + let id = self.next_id(); + self.items.push(item); + id + } + + /// Allocate an item with the id that it will be assigned. + /// + /// This is useful for structures that want to store their id as their own + /// member. + /// + /// ``` + /// use id_arena::{Arena, Id}; + /// + /// struct Cat { + /// id: Id<Cat>, + /// } + /// + /// let mut arena = Arena::<Cat>::new(); + /// + /// let kitty = arena.alloc_with_id(|id| Cat { id }); + /// assert_eq!(arena[kitty].id, kitty); + /// ``` + #[inline] + pub fn alloc_with_id(&mut self, f: impl FnOnce(A::Id) -> T) -> A::Id { + let id = self.next_id(); + let val = f(id); + self.alloc(val) + } + + /// Get the id that will be used for the next item allocated into this + /// arena. + /// + /// If you are allocating a `struct` that wants to have its id as a member + /// of itself, prefer the less error-prone `Arena::alloc_with_id` method. + #[inline] + pub fn next_id(&self) -> A::Id { + let arena_id = self.arena_id; + let idx = self.items.len(); + A::new_id(arena_id, idx) + } + + /// Get a shared reference to the object associated with the given `id` if + /// it exists. + /// + /// If there is no object associated with `id` (for example, it might + /// reference an object allocated within a different arena) then return + /// `None`. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<usize>::new(); + /// let id = arena.alloc(42); + /// assert!(arena.get(id).is_some()); + /// + /// let other_arena = Arena::<usize>::new(); + /// assert!(other_arena.get(id).is_none()); + /// ``` + #[inline] + pub fn get(&self, id: A::Id) -> Option<&T> { + if A::arena_id(id) != self.arena_id { + None + } else { + self.items.get(A::index(id)) + } + } + + /// Get an exclusive reference to the object associated with the given `id` + /// if it exists. + /// + /// If there is no object associated with `id` (for example, it might + /// reference an object allocated within a different arena) then return + /// `None`. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<usize>::new(); + /// let id = arena.alloc(42); + /// assert!(arena.get_mut(id).is_some()); + /// + /// let mut other_arena = Arena::<usize>::new(); + /// assert!(other_arena.get_mut(id).is_none()); + /// ``` + #[inline] + pub fn get_mut(&mut self, id: A::Id) -> Option<&mut T> { + if A::arena_id(id) != self.arena_id { + None + } else { + self.items.get_mut(A::index(id)) + } + } + + /// Iterate over this arena's items and their ids. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<&str>::new(); + /// + /// arena.alloc("hello"); + /// arena.alloc("hi"); + /// arena.alloc("yo"); + /// + /// for (id, s) in arena.iter() { + /// assert_eq!(arena.get(id).unwrap(), s); + /// println!("{:?} -> {}", id, s); + /// } + /// ``` + #[inline] + pub fn iter(&self) -> Iter<T, A> { + IntoIterator::into_iter(self) + } + + /// Iterate over this arena's items and their ids, allowing mutation of each + /// item. + #[inline] + pub fn iter_mut(&mut self) -> IterMut<T, A> { + IntoIterator::into_iter(self) + } + + /// Get the number of objects allocated in this arena. + /// + /// ``` + /// use id_arena::Arena; + /// + /// let mut arena = Arena::<&str>::new(); + /// + /// arena.alloc("hello"); + /// arena.alloc("hi"); + /// + /// assert_eq!(arena.len(), 2); + /// ``` + #[inline] + pub fn len(&self) -> usize { + self.items.len() + } +} + +impl<T, A> ops::Index<A::Id> for Arena<T, A> +where + A: ArenaBehavior, +{ + type Output = T; + + #[inline] + fn index(&self, id: A::Id) -> &T { + assert_eq!(self.arena_id, A::arena_id(id)); + &self.items[A::index(id)] + } +} + +impl<T, A> ops::IndexMut<A::Id> for Arena<T, A> +where + A: ArenaBehavior, +{ + #[inline] + fn index_mut(&mut self, id: A::Id) -> &mut T { + assert_eq!(self.arena_id, A::arena_id(id)); + &mut self.items[A::index(id)] + } +} + +fn add_id<A, T>(item: Option<(usize, T)>, arena_id: u32) -> Option<(A::Id, T)> +where + A: ArenaBehavior, +{ + item.map(|(idx, item)| (A::new_id(arena_id, idx), item)) +} + +/// An iterator over `(Id, &T)` pairs in an arena. +/// +/// See [the `Arena::iter()` method](./struct.Arena.html#method.iter) for details. +#[derive(Debug)] +pub struct Iter<'a, T: 'a, A: 'a> { + arena_id: u32, + iter: iter::Enumerate<slice::Iter<'a, T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<'a, T: 'a, A: 'a> Iterator for Iter<'a, T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, &'a T); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next(), self.arena_id) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T: 'a, A: 'a> DoubleEndedIterator for Iter<'a, T, A> +where + A: ArenaBehavior, +{ + fn next_back(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next_back(), self.arena_id) + } +} + +impl<'a, T: 'a, A: 'a> ExactSizeIterator for Iter<'a, T, A> +where + A: ArenaBehavior, +{ + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<'a, T, A> IntoIterator for &'a Arena<T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, &'a T); + type IntoIter = Iter<'a, T, A>; + + #[inline] + fn into_iter(self) -> Iter<'a, T, A> { + Iter { + arena_id: self.arena_id, + iter: self.items.iter().enumerate(), + _phantom: PhantomData, + } + } +} + +/// An iterator over `(Id, &mut T)` pairs in an arena. +/// +/// See [the `Arena::iter_mut()` method](./struct.Arena.html#method.iter_mut) +/// for details. +#[derive(Debug)] +pub struct IterMut<'a, T: 'a, A: 'a> { + arena_id: u32, + iter: iter::Enumerate<slice::IterMut<'a, T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<'a, T: 'a, A: 'a> Iterator for IterMut<'a, T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, &'a mut T); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next(), self.arena_id) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T: 'a, A: 'a> DoubleEndedIterator for IterMut<'a, T, A> +where + A: ArenaBehavior, +{ + fn next_back(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next_back(), self.arena_id) + } +} + +impl<'a, T: 'a, A: 'a> ExactSizeIterator for IterMut<'a, T, A> +where + A: ArenaBehavior, +{ + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<'a, T, A> IntoIterator for &'a mut Arena<T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, &'a mut T); + type IntoIter = IterMut<'a, T, A>; + + #[inline] + fn into_iter(self) -> IterMut<'a, T, A> { + IterMut { + arena_id: self.arena_id, + iter: self.items.iter_mut().enumerate(), + _phantom: PhantomData, + } + } +} + +/// An iterator over `(Id, T)` pairs in an arena. +#[derive(Debug)] +pub struct IntoIter<T, A> { + arena_id: u32, + iter: iter::Enumerate<vec::IntoIter<T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<T, A> Iterator for IntoIter<T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, T); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next(), self.arena_id) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<T, A> DoubleEndedIterator for IntoIter<T, A> +where + A: ArenaBehavior, +{ + fn next_back(&mut self) -> Option<Self::Item> { + add_id::<A, _>(self.iter.next_back(), self.arena_id) + } +} + +impl<T, A> ExactSizeIterator for IntoIter<T, A> +where + A: ArenaBehavior, +{ + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T, A> IntoIterator for Arena<T, A> +where + A: ArenaBehavior, +{ + type Item = (A::Id, T); + type IntoIter = IntoIter<T, A>; + + #[inline] + fn into_iter(self) -> IntoIter<T, A> { + IntoIter { + arena_id: self.arena_id, + iter: self.items.into_iter().enumerate(), + _phantom: PhantomData, + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn ids_are_send_sync() { + fn assert_send_sync<T: Send + Sync>() {} + struct Foo; + assert_send_sync::<Id<Foo>>(); + } +} diff --git a/third_party/rust/id-arena/src/rayon.rs b/third_party/rust/id-arena/src/rayon.rs new file mode 100644 index 0000000000..7bea702247 --- /dev/null +++ b/third_party/rust/id-arena/src/rayon.rs @@ -0,0 +1,282 @@ +extern crate rayon; + +use self::rayon::iter::plumbing::{Consumer, UnindexedConsumer}; +use self::rayon::iter::plumbing::ProducerCallback; +use self::rayon::prelude::*; +use super::*; + +impl<T, A> Arena<T, A> +where + A: ArenaBehavior, +{ + /// Returns an iterator of shared references which can be used to iterate + /// over this arena in parallel with the `rayon` crate. + /// + /// # Features + /// + /// This API requires the `rayon` feature of this crate to be enabled. + pub fn par_iter(&self) -> ParIter<T, A> + where + T: Sync, + A::Id: Send, + { + ParIter { + arena_id: self.arena_id, + iter: self.items.par_iter().enumerate(), + _phantom: PhantomData, + } + } + + /// Returns an iterator of mutable references which can be used to iterate + /// over this arena in parallel with the `rayon` crate. + /// + /// # Features + /// + /// This API requires the `rayon` feature of this crate to be enabled. + pub fn par_iter_mut(&mut self) -> ParIterMut<T, A> + where + T: Send + Sync, + A::Id: Send, + { + ParIterMut { + arena_id: self.arena_id, + iter: self.items.par_iter_mut().enumerate(), + _phantom: PhantomData, + } + } +} + +/// A parallel iterator over shared references in an arena. +/// +/// See `Arena::par_iter` for more information. +#[derive(Debug)] +pub struct ParIter<'a, T, A> +where + T: Sync, +{ + arena_id: u32, + iter: rayon::iter::Enumerate<rayon::slice::Iter<'a, T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<'a, T, A> ParallelIterator for ParIter<'a, T, A> +where + T: Sync, + A: ArenaBehavior, + A::Id: Send, +{ + type Item = (A::Id, &'a T); + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive_unindexed(consumer) + } + + fn opt_len(&self) -> Option<usize> { + self.iter.opt_len() + } +} + +impl<'a, T, A> IndexedParallelIterator for ParIter<'a, T, A> +where + T: Sync, + A: ArenaBehavior, + A::Id: Send, +{ + fn drive<C>(self, consumer: C) -> C::Result + where + C: Consumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive(consumer) + } + + fn len(&self) -> usize { + self.iter.len() + } + + fn with_producer<CB>(self, callback: CB) -> CB::Output + where + CB: ProducerCallback<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .with_producer(callback) + } +} + +impl<'data, T, A> IntoParallelIterator for &'data Arena<T, A> + where A: ArenaBehavior, + A::Id: Send, + T: Sync, +{ + type Item = (A::Id, &'data T); + type Iter = ParIter<'data, T, A>; + + fn into_par_iter(self) -> Self::Iter { + self.par_iter() + } +} + +/// A parallel iterator over mutable references in an arena. +/// +/// See `Arena::par_iter_mut` for more information. +#[derive(Debug)] +pub struct ParIterMut<'a, T, A> +where + T: Send + Sync, +{ + arena_id: u32, + iter: rayon::iter::Enumerate<rayon::slice::IterMut<'a, T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<'a, T, A> ParallelIterator for ParIterMut<'a, T, A> +where + T: Send + Sync, + A: ArenaBehavior, + A::Id: Send, +{ + type Item = (A::Id, &'a mut T); + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive_unindexed(consumer) + } + + fn opt_len(&self) -> Option<usize> { + self.iter.opt_len() + } +} + +impl<'a, T, A> IndexedParallelIterator for ParIterMut<'a, T, A> +where + T: Send + Sync, + A: ArenaBehavior, + A::Id: Send, +{ + fn drive<C>(self, consumer: C) -> C::Result + where + C: Consumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive(consumer) + } + + fn len(&self) -> usize { + self.iter.len() + } + + fn with_producer<CB>(self, callback: CB) -> CB::Output + where + CB: ProducerCallback<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .with_producer(callback) + } +} + +impl<'data, T, A> IntoParallelIterator for &'data mut Arena<T, A> + where A: ArenaBehavior, + A::Id: Send, + T: Send + Sync, +{ + type Item = (A::Id, &'data mut T); + type Iter = ParIterMut<'data, T, A>; + + fn into_par_iter(self) -> Self::Iter { + self.par_iter_mut() + } +} + +/// A parallel iterator over items in an arena. +/// +/// See `Arena::into_par_iter` for more information. +#[derive(Debug)] +pub struct IntoParIter<T, A> +where + T: Send, +{ + arena_id: u32, + iter: rayon::iter::Enumerate<rayon::vec::IntoIter<T>>, + _phantom: PhantomData<fn() -> A>, +} + +impl<T, A> ParallelIterator for IntoParIter<T, A> +where + T: Send, + A: ArenaBehavior, + A::Id: Send, +{ + type Item = (A::Id, T); + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive_unindexed(consumer) + } + + fn opt_len(&self) -> Option<usize> { + self.iter.opt_len() + } +} + +impl<T, A> IndexedParallelIterator for IntoParIter<T, A> +where + T: Send, + A: ArenaBehavior, + A::Id: Send, +{ + fn drive<C>(self, consumer: C) -> C::Result + where + C: Consumer<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .drive(consumer) + } + + fn len(&self) -> usize { + self.iter.len() + } + + fn with_producer<CB>(self, callback: CB) -> CB::Output + where + CB: ProducerCallback<Self::Item>, + { + let arena_id = self.arena_id; + self.iter.map(|(i, item)| (A::new_id(arena_id, i), item)) + .with_producer(callback) + } +} + +impl<T, A> IntoParallelIterator for Arena<T, A> + where A: ArenaBehavior, + A::Id: Send, + T: Send, +{ + type Item = (A::Id, T); + type Iter = IntoParIter<T, A>; + + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + arena_id: self.arena_id, + iter: self.items.into_par_iter().enumerate(), + _phantom: PhantomData, + } + } +} diff --git a/third_party/rust/id-arena/tests/readme_up_to_date.rs b/third_party/rust/id-arena/tests/readme_up_to_date.rs new file mode 100644 index 0000000000..38af909e31 --- /dev/null +++ b/third_party/rust/id-arena/tests/readme_up_to_date.rs @@ -0,0 +1,22 @@ +use std::fs; +use std::process::Command; + +#[test] +fn cargo_readme_up_to_date() { + println!("Checking that `cargo readme > README.md` is up to date..."); + + let expected = Command::new("cargo") + .arg("readme") + .current_dir(env!("CARGO_MANIFEST_DIR")) + .output() + .expect("should run `cargo readme` OK") + .stdout; + let expected = String::from_utf8_lossy(&expected); + + let actual = fs::read_to_string(concat!(env!("CARGO_MANIFEST_DIR"), "/README.md")) + .expect("should read README.md OK"); + + if actual != expected { + panic!("Run `cargo readme > README.md` to update README.md"); + } +} |