From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- third_party/rust/self_cell/.cargo-checksum.json | 1 + third_party/rust/self_cell/Cargo.toml | 32 + third_party/rust/self_cell/LICENSE | 201 +++++++ third_party/rust/self_cell/README.md | 186 ++++++ third_party/rust/self_cell/src/lib.rs | 659 +++++++++++++++++++++ third_party/rust/self_cell/src/unsafe_self_cell.rs | 230 +++++++ 6 files changed, 1309 insertions(+) create mode 100644 third_party/rust/self_cell/.cargo-checksum.json create mode 100644 third_party/rust/self_cell/Cargo.toml create mode 100644 third_party/rust/self_cell/LICENSE create mode 100644 third_party/rust/self_cell/README.md create mode 100644 third_party/rust/self_cell/src/lib.rs create mode 100644 third_party/rust/self_cell/src/unsafe_self_cell.rs (limited to 'third_party/rust/self_cell') diff --git a/third_party/rust/self_cell/.cargo-checksum.json b/third_party/rust/self_cell/.cargo-checksum.json new file mode 100644 index 0000000000..303f1e05f5 --- /dev/null +++ b/third_party/rust/self_cell/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"ab60ad0024cea3e0c60fc4d116adc7fae35d5f85b042d285bba65f22c42407d5","LICENSE":"c71d239df91726fc519c6eb72d318ec65820627232b2f796219e87dcf35d0ab4","README.md":"51dac2de0fd70602457b5f94f96c765385adfb2b14266c4c83946c89968e0886","src/lib.rs":"1127bdfd2390f17eac015e9379ad72a8d9bfbb057bc82ed2e386f1b074c83b06","src/unsafe_self_cell.rs":"fb2b71ea2057085dcc8ff1430f8684f67aa08e1519cd51704d264593819bf3fb"},"package":"1ef965a420fe14fdac7dd018862966a4c14094f900e1650bbc71ddd7d580c8af"} \ No newline at end of file diff --git a/third_party/rust/self_cell/Cargo.toml b/third_party/rust/self_cell/Cargo.toml new file mode 100644 index 0000000000..f8ba952e5f --- /dev/null +++ b/third_party/rust/self_cell/Cargo.toml @@ -0,0 +1,32 @@ +# 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 = "self_cell" +version = "0.10.2" +authors = ["Lukas Bergdoll "] +include = ["src/*.rs", "Cargo.toml", "README.md", "LICENSE"] +description = "Safe-to-use proc-macro-free self-referential structs in stable Rust." +documentation = "https://docs.rs/self_cell" +readme = "README.md" +keywords = ["lifetime", "borrowing", "self", "reference", "intrusive"] +categories = ["rust-patterns", "memory-management"] +license = "Apache-2.0" +repository = "https://github.com/Voultapher/self_cell" +[dependencies.rustversion] +version = ">=1" +optional = true +[dev-dependencies.once_cell] +version = ">=1" + +[features] +old_rust = ["rustversion"] diff --git a/third_party/rust/self_cell/LICENSE b/third_party/rust/self_cell/LICENSE new file mode 100644 index 0000000000..261eeb9e9f --- /dev/null +++ b/third_party/rust/self_cell/LICENSE @@ -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/self_cell/README.md b/third_party/rust/self_cell/README.md new file mode 100644 index 0000000000..819bdc87ca --- /dev/null +++ b/third_party/rust/self_cell/README.md @@ -0,0 +1,186 @@ +[github](https://github.com/Voultapher/self_cell) +[crates.io](https://crates.io/crates/self_cell) +[docs.rs](https://docs.rs/self_cell) + +# `self_cell!` + +Use the macro-rules macro: `self_cell!` to create safe-to-use self-referential +structs in stable Rust, without leaking the struct internal lifetime. + +In a nutshell, the API looks *roughly* like this: + +```rust +// User code: + +self_cell!( + struct NewStructName { + owner: Owner, + + #[covariant] + dependent: Dependent, + } + + impl {Debug} +); + +// Generated by macro: + +struct NewStructName(...); + +impl NewStructName { + fn new( + owner: Owner, + dependent_builder: impl for<'a> FnOnce(&'a Owner) -> Dependent<'a> + ) -> NewStructName { ... } + fn borrow_owner<'a>(&'a self) -> &'a Owner { ... } + fn borrow_dependent<'a>(&'a self) -> &'a Dependent<'a> { ... } +} + +impl Debug for NewStructName { ... } +``` + +Self-referential structs are currently not supported with safe vanilla Rust. The +only reasonable safe alternative is to expect the user to juggle 2 separate data +structures which is a mess. The library solution ouroboros is really expensive +to compile due to its use of procedural macros. + +This alternative is `no_std`, uses no proc-macros, some self contained unsafe +and works on stable Rust, and is miri tested. With a total of less than 300 +lines of implementation code, which consists mostly of type and trait +implementations, this crate aims to be a good minimal solution to the problem of +self-referential structs. + +It has undergone [community code review](https://users.rust-lang.org/t/experimental-safe-to-use-proc-macro-free-self-referential-structs-in-stable-rust/52775) +from experienced Rust users. + +### Fast compile times + +``` +$ rm -rf target && cargo +nightly build -Z timings + +Compiling self_cell v0.9.0 +Completed self_cell v0.9.0 in 0.2s +``` + +Because it does **not** use proc-macros, and has 0 dependencies compile-times +are fast. + +Measurements done on a slow laptop. + +### A motivating use case + +```rust +use self_cell::self_cell; + +#[derive(Debug, Eq, PartialEq)] +struct Ast<'a>(pub Vec<&'a str>); + +self_cell!( + struct AstCell { + owner: String, + + #[covariant] + dependent: Ast, + } + + impl {Debug, Eq, PartialEq} +); + +fn build_ast_cell(code: &str) -> AstCell { + // Create owning String on stack. + let pre_processed_code = code.trim().to_string(); + + // Move String into AstCell, then build Ast inplace. + AstCell::new( + pre_processed_code, + |code| Ast(code.split(' ').filter(|word| word.len() > 1).collect()) + ) +} + +fn main() { + let ast_cell = build_ast_cell("fox = cat + dog"); + + println!("ast_cell -> {:?}", &ast_cell); + println!("ast_cell.borrow_owner() -> {:?}", ast_cell.borrow_owner()); + println!("ast_cell.borrow_dependent().0[1] -> {:?}", ast_cell.borrow_dependent().0[1]); +} +``` + +``` +$ cargo run + +ast_cell -> AstCell { owner: "fox = cat + dog", dependent: Ast(["fox", "cat", "dog"]) } +ast_cell.borrow_owner() -> "fox = cat + dog" +ast_cell.borrow_dependent().0[1] -> "cat" +``` + +There is no way in safe Rust to have an API like `build_ast_cell`, as soon as +`Ast` depends on stack variables like `pre_processed_code` you can't return the +value out of the function anymore. You could move the pre-processing into the +caller but that gets ugly quickly because you can't encapsulate things anymore. +Note this is a somewhat niche use case, self-referential structs should only be +used when there is no good alternative. + +Under the hood, it heap allocates a struct which it initializes first by moving +the owner value to it and then using the reference to this now Pin/Immovable +owner to construct the dependent inplace next to it. This makes it safe to move +the generated SelfCell but you have to pay for the heap allocation. + +See the documentation for a more in-depth API overview and advanced examples: +https://docs.rs/self_cell + +### Installing + +[See cargo docs](https://doc.rust-lang.org/cargo/guide/). + +## Running the tests + +``` +cargo test + +cargo miri test +``` + +### Related projects + +[ouroboros](https://github.com/joshua-maros/ouroboros) + +[rental](https://github.com/jpernst/rental) + +[Schroedinger](https://github.com/dureuill/sc) + +[owning_ref](https://github.com/Kimundi/owning-ref-rs) + +[ghost-cell](https://github.com/matthieu-m/ghost-cell) + +## Min required rustc version + +By default the minimum required rustc version is 1.51. + +There is an optional feature you can enable called "old_rust" that enables +support down to rustc version 1.36. However this requires polyfilling std +library functionality for older rustc with technically UB versions. Testing does +not show older rustc versions (ab)using this. Use at your own risk. + +The minimum versions are a best effor and may change with any new major release. + +## Contributing + +Please respect the [CODE_OF_CONDUCT.md](CODE_OF_CONDUCT.md) when contributing. + +## Versioning + +We use [SemVer](http://semver.org/) for versioning. For the versions available, +see the [tags on this repository](https://github.com/Voultapher/self_cell/tags). + +## Authors + +* **Lukas Bergdoll** - *Initial work* - [Voultapher](https://github.com/Voultapher) + +See also the list of [contributors](https://github.com/Voultapher/self_cell/contributors) +who participated in this project. + +## License + +This project is licensed under the Apache License, Version 2.0 - +see the [LICENSE.md](LICENSE.md) file for details. diff --git a/third_party/rust/self_cell/src/lib.rs b/third_party/rust/self_cell/src/lib.rs new file mode 100644 index 0000000000..e2d8f2ee62 --- /dev/null +++ b/third_party/rust/self_cell/src/lib.rs @@ -0,0 +1,659 @@ +//! # Overview +//! +//! `self_cell` provides one macro-rules macro: [`self_cell`]. With this macro +//! you can create self-referential structs that are safe-to-use in stable Rust, +//! without leaking the struct internal lifetime. +//! +//! In a nutshell, the API looks *roughly* like this: +//! +//! ```ignore +//! // User code: +//! +//! self_cell!( +//! struct NewStructName { +//! owner: Owner, +//! +//! #[covariant] +//! dependent: Dependent, +//! } +//! +//! impl {Debug} +//! ); +//! +//! // Generated by macro: +//! +//! struct NewStructName(...); +//! +//! impl NewStructName { +//! fn new( +//! owner: Owner, +//! dependent_builder: impl for<'a> FnOnce(&'a Owner) -> Dependent<'a> +//! ) -> NewStructName { ... } +//! fn borrow_owner<'a>(&'a self) -> &'a Owner { ... } +//! fn borrow_dependent<'a>(&'a self) -> &'a Dependent<'a> { ... } +//! } +//! +//! impl Debug for NewStructName { ... } +//! ``` +//! +//! Self-referential structs are currently not supported with safe vanilla Rust. +//! The only reasonable safe alternative is to have the user juggle 2 separate +//! data structures which is a mess. The library solution ouroboros is really +//! expensive to compile due to its use of procedural macros. +//! +//! This alternative is `no_std`, uses no proc-macros, some self contained +//! unsafe and works on stable Rust, and is miri tested. With a total of less +//! than 300 lines of implementation code, which consists mostly of type and +//! trait implementations, this crate aims to be a good minimal solution to the +//! problem of self-referential structs. +//! +//! It has undergone [community code +//! review](https://users.rust-lang.org/t/experimental-safe-to-use-proc-macro-free-self-referential-structs-in-stable-rust/52775) +//! from experienced Rust users. +//! +//! ### Fast compile times +//! +//! ```txt +//! $ rm -rf target && cargo +nightly build -Z timings +//! +//! Compiling self_cell v0.7.0 +//! Completed self_cell v0.7.0 in 0.2s +//! ``` +//! +//! Because it does **not** use proc-macros, and has 0 dependencies +//! compile-times are fast. +//! +//! Measurements done on a slow laptop. +//! +//! ### A motivating use case +//! +//! ```rust +//! use self_cell::self_cell; +//! +//! #[derive(Debug, Eq, PartialEq)] +//! struct Ast<'a>(pub Vec<&'a str>); +//! +//! self_cell!( +//! struct AstCell { +//! owner: String, +//! +//! #[covariant] +//! dependent: Ast, +//! } +//! +//! impl {Debug, Eq, PartialEq} +//! ); +//! +//! fn build_ast_cell(code: &str) -> AstCell { +//! // Create owning String on stack. +//! let pre_processed_code = code.trim().to_string(); +//! +//! // Move String into AstCell, then build Ast inplace. +//! AstCell::new( +//! pre_processed_code, +//! |code| Ast(code.split(' ').filter(|word| word.len() > 1).collect()) +//! ) +//! } +//! +//! fn main() { +//! let ast_cell = build_ast_cell("fox = cat + dog"); +//! +//! println!("ast_cell -> {:?}", &ast_cell); +//! println!("ast_cell.borrow_owner() -> {:?}", ast_cell.borrow_owner()); +//! println!("ast_cell.borrow_dependent().0[1] -> {:?}", ast_cell.borrow_dependent().0[1]); +//! } +//! ``` +//! +//! ```txt +//! $ cargo run +//! +//! ast_cell -> AstCell { owner: "fox = cat + dog", dependent: Ast(["fox", "cat", "dog"]) } +//! ast_cell.borrow_owner() -> "fox = cat + dog" +//! ast_cell.borrow_dependent().0[1] -> "cat" +//! ``` +//! +//! There is no way in safe Rust to have an API like `build_ast_cell`, as soon +//! as `Ast` depends on stack variables like `pre_processed_code` you can't +//! return the value out of the function anymore. You could move the +//! pre-processing into the caller but that gets ugly quickly because you can't +//! encapsulate things anymore. Note this is a somewhat niche use case, +//! self-referential structs should only be used when there is no good +//! alternative. +//! +//! Under the hood, it heap allocates a struct which it initializes first by +//! moving the owner value to it and then using the reference to this now +//! Pin/Immovable owner to construct the dependent inplace next to it. This +//! makes it safe to move the generated SelfCell but you have to pay for the +//! heap allocation. +//! +//! See the documentation for [`self_cell`] to dive further into the details. +//! +//! Or take a look at the advanced examples: +//! - [Example how to handle dependent construction that can +//! fail](https://github.com/Voultapher/self_cell/tree/main/examples/fallible_dependent_construction) +//! +//! - [How to build a lazy AST with +//! self_cell](https://github.com/Voultapher/self_cell/tree/main/examples/lazy_ast) +//! +//! - [How to use an owner type with +//! lifetime](https://github.com/Voultapher/self_cell/tree/main/examples/owner_with_lifetime) +//! +//! ### Min required rustc version +//! +//! By default the minimum required rustc version is 1.51. +//! +//! There is an optional feature you can enable called "old_rust" that enables +//! support down to rustc version 1.36. However this requires polyfilling std +//! library functionality for older rustc with technically UB versions. Testing +//! does not show older rustc versions (ab)using this. Use at your own risk. +//! +//! The minimum versions are a best effor and may change with any new major +//! release. + +#![no_std] + +#[doc(hidden)] +pub extern crate alloc; + +#[doc(hidden)] +pub mod unsafe_self_cell; + +/// This macro declares a new struct of `$StructName` and implements traits +/// based on `$AutomaticDerive`. +/// +/// ### Example: +/// +/// ```rust +/// use self_cell::self_cell; +/// +/// #[derive(Debug, Eq, PartialEq)] +/// struct Ast<'a>(Vec<&'a str>); +/// +/// self_cell!( +/// #[doc(hidden)] +/// struct PackedAstCell { +/// owner: String, +/// +/// #[covariant] +/// dependent: Ast, +/// } +/// +/// impl {Debug, PartialEq, Eq, Hash} +/// ); +/// ``` +/// +/// See the crate overview to get a get an overview and a motivating example. +/// +/// ### Generated API: +/// +/// The macro implements these constructors: +/// +/// ```ignore +/// fn new( +/// owner: $Owner, +/// dependent_builder: impl for<'a> FnOnce(&'a $Owner) -> $Dependent<'a> +/// ) -> Self +/// ``` +/// +/// ```ignore +/// fn try_new( +/// owner: $Owner, +/// dependent_builder: impl for<'a> FnOnce(&'a $Owner) -> Result<$Dependent<'a>, Err> +/// ) -> Result +/// ``` +/// +/// ```ignore +/// fn try_new_or_recover( +/// owner: $Owner, +/// dependent_builder: impl for<'a> FnOnce(&'a $Owner) -> Result<$Dependent<'a>, Err> +/// ) -> Result +/// ``` +/// +/// The macro implements these methods: +/// +/// ```ignore +/// fn borrow_owner<'a>(&'a self) -> &'a $Owner +/// ``` +/// +/// ```ignore +/// // Only available if dependent is covariant. +/// fn borrow_dependent<'a>(&'a self) -> &'a $Dependent<'a> +/// ``` +/// +/// ```ignore +/// fn with_dependent<'outer_fn, Ret>( +/// &'outer_fn self, +/// func: impl for<'a> FnOnce(&'a $Owner, &'outer_fn $Dependent<'a> +/// ) -> Ret) -> Ret +/// ``` +/// +/// ```ignore +/// fn with_dependent_mut<'outer_fn, Ret>( +/// &'outer_fn mut self, +/// func: impl for<'a> FnOnce(&'a $Owner, &'outer_fn mut $Dependent<'a>) -> Ret +/// ) -> Ret +/// ``` +/// +/// ```ignore +/// fn into_owner(self) -> $Owner +/// ``` +/// +/// +/// ### Parameters: +/// +/// - `$Vis:vis struct $StructName:ident` Name of the struct that will be +/// declared, this needs to be unique for the relevant scope. Example: `struct +/// AstCell` or `pub struct AstCell`. `$Vis` can be used to mark the struct +/// and all functions implemented by the macro as public. +/// +/// `$(#[$StructMeta:meta])*` allows you specify further meta items for this +/// struct, eg. `#[doc(hidden)] struct AstCell`. +/// +/// - `$Owner:ty` Type of owner. This has to have a `'static` lifetime. Example: +/// `String`. +/// +/// - `$Dependent:ident` Name of the dependent type without specified lifetime. +/// This can't be a nested type name. As workaround either create a type alias +/// `type Dep<'a> = Option>;` or create a new-type `struct +/// Dep<'a>(Option>);`. Example: `Ast`. +/// +/// `$Covariance:ident` Marker declaring if `$Dependent` is +/// [covariant](https://doc.rust-lang.org/nightly/nomicon/subtyping.html). +/// Possible Values: +/// +/// * **covariant**: This generates the direct reference accessor function +/// `borrow_dependent`. This is only safe to do if this compiles `fn +/// _assert_covariance<'x: 'y, 'y>(x: $Dependent<'x>) -> $Dependent<'y> +/// {x}`. Otherwise you could choose a lifetime that is too short for types +/// with interior mutability like `Cell`, which can lead to UB in safe code. +/// Which would violate the promise of this library that it is safe-to-use. +/// If you accidentally mark a type that is not covariant as covariant, you +/// will get a compile time error. +/// +/// * **not_covariant**: This generates no additional code but you can use the +/// `with_dependent` function. See [How to build a lazy AST with +/// self_cell](https://github.com/Voultapher/self_cell/tree/main/examples/lazy_ast) +/// for a usage example. +/// +/// In both cases you can use the `with_dependent_mut` function to mutate the +/// dependent value. This is safe to do because notionally you are replacing +/// pointers to a value not the other way around. +/// +/// - `impl {$($AutomaticDerive:ident),*},` Optional comma separated list of +/// optional automatic trait implementations. Possible Values: +/// +/// * **Debug**: Prints the debug representation of owner and dependent. +/// Example: `AstCell { owner: "fox = cat + dog", dependent: Ast(["fox", +/// "cat", "dog"]) }` +/// +/// * **PartialEq**: Logic `*self.borrow_owner() == *other.borrow_owner()`, +/// this assumes that `Dependent<'a>::From<&'a Owner>` is deterministic, so +/// that only comparing owner is enough. +/// +/// * **Eq**: Will implement the trait marker `Eq` for `$StructName`. Beware +/// if you select this `Eq` will be implemented regardless if `$Owner` +/// implements `Eq`, that's an unfortunate technical limitation. +/// +/// * **Hash**: Logic `self.borrow_owner().hash(state);`, this assumes that +/// `Dependent<'a>::From<&'a Owner>` is deterministic, so that only hashing +/// owner is enough. +/// +/// All `AutomaticDerive` are optional and you can implement you own version +/// of these traits. The declared struct is part of your module and you are +/// free to implement any trait in any way you want. Access to the unsafe +/// internals is only possible via unsafe functions, so you can't accidentally +/// use them in safe code. +/// +/// There is limited nested cell support. Eg, having an owner with non static +/// references. Eg `struct ChildCell<'a> { owner: &'a String, ...`. You can +/// use any lifetime name you want, except `_q` and only a single lifetime is +/// supported, and can only be used in the owner. Due to macro_rules +/// limitations, no `AutomaticDerive` are supported if an owner lifetime is +/// provided. +/// +#[macro_export] +macro_rules! self_cell { +( + $(#[$StructMeta:meta])* + $Vis:vis struct $StructName:ident $(<$OwnerLifetime:lifetime>)? { + owner: $Owner:ty, + + #[$Covariance:ident] + dependent: $Dependent:ident, + } + + $(impl {$($AutomaticDerive:ident),*})? +) => { + #[repr(transparent)] + $(#[$StructMeta])* + $Vis struct $StructName $(<$OwnerLifetime>)? { + unsafe_self_cell: $crate::unsafe_self_cell::UnsafeSelfCell< + $StructName$(<$OwnerLifetime>)?, + $Owner, + $Dependent<'static> + >, + + $(owner_marker: $crate::_covariant_owner_marker!($Covariance, $OwnerLifetime) ,)? + } + + impl $(<$OwnerLifetime>)? $StructName $(<$OwnerLifetime>)? { + $Vis fn new( + owner: $Owner, + dependent_builder: impl for<'_q> FnOnce(&'_q $Owner) -> $Dependent<'_q> + ) -> Self { + use core::ptr::NonNull; + + unsafe { + // All this has to happen here, because there is not good way + // of passing the appropriate logic into UnsafeSelfCell::new + // short of assuming Dependent<'static> is the same as + // Dependent<'_q>, which I'm not confident is safe. + + // For this API to be safe there has to be no safe way to + // capture additional references in `dependent_builder` and then + // return them as part of Dependent. Eg. it should be impossible + // to express: '_q should outlive 'x here `fn + // bad<'_q>(outside_ref: &'_q String) -> impl for<'x> FnOnce(&'x + // Owner) -> Dependent<'x>`. + + type JoinedCell<'_q $(, $OwnerLifetime)?> = + $crate::unsafe_self_cell::JoinedCell<$Owner, $Dependent<'_q>>; + + let layout = $crate::alloc::alloc::Layout::new::(); + assert!(layout.size() != 0); + + let joined_void_ptr = NonNull::new($crate::alloc::alloc::alloc(layout)).unwrap(); + + let mut joined_ptr = core::mem::transmute::, NonNull>( + joined_void_ptr + ); + + let (owner_ptr, dependent_ptr) = JoinedCell::_field_pointers(joined_ptr.as_ptr()); + + // Move owner into newly allocated space. + owner_ptr.write(owner); + + // Drop guard that cleans up should building the dependent panic. + let drop_guard = + $crate::unsafe_self_cell::OwnerAndCellDropGuard::new(joined_ptr); + + // Initialize dependent with owner reference in final place. + dependent_ptr.write(dependent_builder(&*owner_ptr)); + core::mem::forget(drop_guard); + + Self { + unsafe_self_cell: $crate::unsafe_self_cell::UnsafeSelfCell::new( + joined_void_ptr, + ), + $(owner_marker: $crate::_covariant_owner_marker_ctor!($OwnerLifetime) ,)? + } + } + } + + $Vis fn try_new( + owner: $Owner, + dependent_builder: + impl for<'_q> FnOnce(&'_q $Owner) -> core::result::Result<$Dependent<'_q>, Err> + ) -> core::result::Result { + use core::ptr::NonNull; + + unsafe { + // See fn new for more explanation. + + type JoinedCell<'_q $(, $OwnerLifetime)?> = + $crate::unsafe_self_cell::JoinedCell<$Owner, $Dependent<'_q>>; + + let layout = $crate::alloc::alloc::Layout::new::(); + assert!(layout.size() != 0); + + let joined_void_ptr = NonNull::new($crate::alloc::alloc::alloc(layout)).unwrap(); + + let mut joined_ptr = core::mem::transmute::, NonNull>( + joined_void_ptr + ); + + let (owner_ptr, dependent_ptr) = JoinedCell::_field_pointers(joined_ptr.as_ptr()); + + // Move owner into newly allocated space. + owner_ptr.write(owner); + + // Drop guard that cleans up should building the dependent panic. + let mut drop_guard = + $crate::unsafe_self_cell::OwnerAndCellDropGuard::new(joined_ptr); + + match dependent_builder(&*owner_ptr) { + Ok(dependent) => { + dependent_ptr.write(dependent); + core::mem::forget(drop_guard); + + Ok(Self { + unsafe_self_cell: $crate::unsafe_self_cell::UnsafeSelfCell::new( + joined_void_ptr, + ), + $(owner_marker: $crate::_covariant_owner_marker_ctor!($OwnerLifetime) ,)? + }) + } + Err(err) => Err(err) + } + } + } + + $Vis fn try_new_or_recover( + owner: $Owner, + dependent_builder: + impl for<'_q> FnOnce(&'_q $Owner) -> core::result::Result<$Dependent<'_q>, Err> + ) -> core::result::Result { + use core::ptr::NonNull; + + unsafe { + // See fn new for more explanation. + + type JoinedCell<'_q $(, $OwnerLifetime)?> = + $crate::unsafe_self_cell::JoinedCell<$Owner, $Dependent<'_q>>; + + let layout = $crate::alloc::alloc::Layout::new::(); + assert!(layout.size() != 0); + + let joined_void_ptr = NonNull::new($crate::alloc::alloc::alloc(layout)).unwrap(); + + let mut joined_ptr = core::mem::transmute::, NonNull>( + joined_void_ptr + ); + + let (owner_ptr, dependent_ptr) = JoinedCell::_field_pointers(joined_ptr.as_ptr()); + + // Move owner into newly allocated space. + owner_ptr.write(owner); + + // Drop guard that cleans up should building the dependent panic. + let mut drop_guard = + $crate::unsafe_self_cell::OwnerAndCellDropGuard::new(joined_ptr); + + match dependent_builder(&*owner_ptr) { + Ok(dependent) => { + dependent_ptr.write(dependent); + core::mem::forget(drop_guard); + + Ok(Self { + unsafe_self_cell: $crate::unsafe_self_cell::UnsafeSelfCell::new( + joined_void_ptr, + ), + $(owner_marker: $crate::_covariant_owner_marker_ctor!($OwnerLifetime) ,)? + }) + } + Err(err) => { + // In contrast to into_owner ptr::read, here no dependent + // ever existed in this function and so we are sure its + // drop impl can't access owner after the read. + // And err can't return a reference to owner. + let owner_on_err = core::ptr::read(owner_ptr); + + // Allowing drop_guard to finish would let it double free owner. + // So we dealloc the JoinedCell here manually. + core::mem::forget(drop_guard); + $crate::alloc::alloc::dealloc(joined_void_ptr.as_ptr(), layout); + + Err((owner_on_err, err)) + } + } + } + } + + $Vis fn borrow_owner<'_q>(&'_q self) -> &'_q $Owner { + unsafe { self.unsafe_self_cell.borrow_owner::<$Dependent<'_q>>() } + } + + $Vis fn with_dependent<'outer_fn, Ret>( + &'outer_fn self, + func: impl for<'_q> FnOnce(&'_q $Owner, &'outer_fn $Dependent<'_q> + ) -> Ret) -> Ret { + unsafe { + func( + self.unsafe_self_cell.borrow_owner::<$Dependent>(), + self.unsafe_self_cell.borrow_dependent() + ) + } + } + + $Vis fn with_dependent_mut<'outer_fn, Ret>( + &'outer_fn mut self, + func: impl for<'_q> FnOnce(&'_q $Owner, &'outer_fn mut $Dependent<'_q>) -> Ret + ) -> Ret { + let (owner, dependent) = unsafe { + self.unsafe_self_cell.borrow_mut() + }; + + func(owner, dependent) + } + + $crate::_covariant_access!($Covariance, $Vis, $Dependent); + + $Vis fn into_owner(self) -> $Owner { + // This is only safe to do with repr(transparent). + let unsafe_self_cell = unsafe { core::mem::transmute::< + Self, + $crate::unsafe_self_cell::UnsafeSelfCell< + $StructName$(<$OwnerLifetime>)?, + $Owner, + $Dependent<'static> + > + >(self) }; + + let owner = unsafe { unsafe_self_cell.into_owner::<$Dependent>() }; + + owner + } + } + + impl $(<$OwnerLifetime>)? Drop for $StructName $(<$OwnerLifetime>)? { + fn drop(&mut self) { + unsafe { + self.unsafe_self_cell.drop_joined::<$Dependent>(); + } + } + } + + // The user has to choose which traits can and should be automatically + // implemented for the cell. + $($( + $crate::_impl_automatic_derive!($AutomaticDerive, $StructName); + )*)* +}; +} + +#[doc(hidden)] +#[macro_export] +macro_rules! _covariant_access { + (covariant, $Vis:vis, $Dependent:ident) => { + $Vis fn borrow_dependent<'_q>(&'_q self) -> &'_q $Dependent<'_q> { + fn _assert_covariance<'x: 'y, 'y>(x: $Dependent<'x>) -> $Dependent<'y> { + // This function only compiles for covariant types. + x // Change the macro invocation to not_covariant. + } + + unsafe { self.unsafe_self_cell.borrow_dependent() } + } + }; + (not_covariant, $Vis:vis, $Dependent:ident) => { + // For types that are not covariant it's unsafe to allow + // returning direct references. + // For example a lifetime that is too short could be chosen: + // See https://github.com/Voultapher/self_cell/issues/5 + }; + ($x:ident, $Vis:vis, $Dependent:ident) => { + compile_error!("This macro only accepts `covariant` or `not_covariant`"); + }; +} + +#[doc(hidden)] +#[macro_export] +macro_rules! _covariant_owner_marker { + (covariant, $OwnerLifetime:lifetime) => { + // Ensure that contravariant owners don't imply covariance + // over the dependent. See issue https://github.com/Voultapher/self_cell/issues/18 + core::marker::PhantomData<&$OwnerLifetime ()> + }; + (not_covariant, $OwnerLifetime:lifetime) => { + // See the discussion in https://github.com/Voultapher/self_cell/pull/29 + // + // If the dependent is non_covariant, mark the owner as invariant over its + // lifetime. Otherwise unsound use is possible. + core::marker::PhantomData &$OwnerLifetime ()> + }; + ($x:ident, $OwnerLifetime:lifetime) => { + compile_error!("This macro only accepts `covariant` or `not_covariant`"); + }; +} + +#[doc(hidden)] +#[macro_export] +macro_rules! _covariant_owner_marker_ctor { + ($OwnerLifetime:lifetime) => { + // Helper to optionally expand into PhantomData for construction. + core::marker::PhantomData + }; +} + +#[doc(hidden)] +#[macro_export] +macro_rules! _impl_automatic_derive { + (Debug, $StructName:ident) => { + impl core::fmt::Debug for $StructName { + fn fmt( + &self, + fmt: &mut core::fmt::Formatter, + ) -> core::result::Result<(), core::fmt::Error> { + self.with_dependent(|owner, dependent| { + fmt.debug_struct(stringify!($StructName)) + .field("owner", owner) + .field("dependent", dependent) + .finish() + }) + } + } + }; + (PartialEq, $StructName:ident) => { + impl core::cmp::PartialEq for $StructName { + fn eq(&self, other: &Self) -> bool { + *self.borrow_owner() == *other.borrow_owner() + } + } + }; + (Eq, $StructName:ident) => { + // TODO this should only be allowed if owner is Eq. + impl core::cmp::Eq for $StructName {} + }; + (Hash, $StructName:ident) => { + impl core::hash::Hash for $StructName { + fn hash(&self, state: &mut H) { + self.borrow_owner().hash(state); + } + } + }; + ($x:ident, $StructName:ident) => { + compile_error!(concat!( + "No automatic trait impl for trait: ", + stringify!($x) + )); + }; +} diff --git a/third_party/rust/self_cell/src/unsafe_self_cell.rs b/third_party/rust/self_cell/src/unsafe_self_cell.rs new file mode 100644 index 0000000000..b0b934d6f7 --- /dev/null +++ b/third_party/rust/self_cell/src/unsafe_self_cell.rs @@ -0,0 +1,230 @@ +use core::marker::PhantomData; +use core::mem::{self, transmute}; +use core::ptr::{drop_in_place, read, NonNull}; + +extern crate alloc; + +use alloc::alloc::{dealloc, Layout}; + +// Self referential structs are currently not supported with safe vanilla Rust. +// The only reasonable safe alternative is to expect the user to juggle 2 separate +// data structures which is a mess. The library solution rental is both no longer +// maintained and really heavy to compile. So begrudgingly I rolled my own version. +// These are some of the core invariants we require for this to be safe to use. +// +// 1. owner is initialized when UnsafeSelfCell is constructed. +// 2. owner is NEVER changed again. +// 3. The pointer to owner and dependent never changes, even when moved. +// 4. The only access to owner and dependent is as immutable reference. +// 5. owner lives longer than dependent. + +#[doc(hidden)] +pub struct JoinedCell { + pub owner: Owner, + pub dependent: Dependent, +} + +// Library controlled struct that marks all accesses as unsafe. +// Because the macro generated struct impl can be extended, could be unsafe. +#[doc(hidden)] +pub struct UnsafeSelfCell { + joined_void_ptr: NonNull, + + // ContainedIn is necessary for type safety since we don't fully + // prohibit access to the UnsafeSelfCell; swapping between different + // structs can be unsafe otherwise, see Issue #17. + contained_in_marker: PhantomData, + + owner_marker: PhantomData, + // DependentStatic is only used to correctly derive Send and Sync. + dependent_marker: PhantomData, +} + +impl UnsafeSelfCell { + pub unsafe fn new(joined_void_ptr: NonNull) -> Self { + Self { + joined_void_ptr, + contained_in_marker: PhantomData, + owner_marker: PhantomData, + dependent_marker: PhantomData, + } + } + + // Calling any of these *unsafe* functions with the wrong Dependent type is UB. + + pub unsafe fn borrow_owner<'a, Dependent>(&'a self) -> &'a Owner { + let joined_ptr = + transmute::, NonNull>>(self.joined_void_ptr); + + &(*joined_ptr.as_ptr()).owner + } + + pub unsafe fn borrow_dependent<'a, Dependent>(&'a self) -> &'a Dependent { + let joined_ptr = + transmute::, NonNull>>(self.joined_void_ptr); + + &(*joined_ptr.as_ptr()).dependent + } + + pub unsafe fn borrow_mut<'a, Dependent>(&'a mut self) -> (&'a Owner, &'a mut Dependent) { + let joined_ptr = + transmute::, NonNull>>(self.joined_void_ptr); + + // This function used to return `&'a mut JoinedCell`. + // It now creates two references to the fields instead to avoid claiming mutable access + // to the whole `JoinedCell` (including the owner!) here. + ( + &(*joined_ptr.as_ptr()).owner, + &mut (*joined_ptr.as_ptr()).dependent, + ) + } + + // Any subsequent use of this struct other than dropping it is UB. + pub unsafe fn drop_joined(&mut self) { + let joined_ptr = + transmute::, NonNull>>(self.joined_void_ptr); + + // Also used in case drop_in_place(...dependent) fails + let _guard = OwnerAndCellDropGuard { joined_ptr }; + + // IMPORTANT dependent must be dropped before owner. + // We don't want to rely on an implicit order of struct fields. + // So we drop the struct, field by field manually. + drop_in_place(&mut (*joined_ptr.as_ptr()).dependent); + + // Dropping owner + // and deallocating + // due to _guard at end of scope. + } + + pub unsafe fn into_owner(self) -> Owner { + let joined_ptr = + transmute::, NonNull>>(self.joined_void_ptr); + + // In case drop_in_place(...dependent) fails + let drop_guard = OwnerAndCellDropGuard::new(joined_ptr); + + // Drop dependent + drop_in_place(&mut (*joined_ptr.as_ptr()).dependent); + + mem::forget(drop_guard); + + let owner_ptr: *const Owner = &(*joined_ptr.as_ptr()).owner; + + // Move owner out so it can be returned. + // Must not read before dropping dependent!! (Which happened above.) + let owner = read(owner_ptr); + + // Deallocate JoinedCell + let layout = Layout::new::>(); + dealloc(self.joined_void_ptr.as_ptr(), layout); + + owner + } +} + +unsafe impl Send + for UnsafeSelfCell +where + // Only derive Send if Owner and DependentStatic is also Send + Owner: Send, + DependentStatic: Send, +{ +} + +unsafe impl Sync + for UnsafeSelfCell +where + // Only derive Sync if Owner and DependentStatic is also Sync + Owner: Sync, + DependentStatic: Sync, +{ +} + +// This struct is used to safely deallocate only the owner if dependent +// construction fails. +// +// mem::forget it once it's no longer needed or dtor will be UB. +#[doc(hidden)] +pub struct OwnerAndCellDropGuard { + joined_ptr: NonNull>, +} + +impl OwnerAndCellDropGuard { + pub unsafe fn new(joined_ptr: NonNull>) -> Self { + Self { joined_ptr } + } +} + +impl Drop for OwnerAndCellDropGuard { + fn drop(&mut self) { + struct DeallocGuard { + ptr: *mut u8, + layout: Layout, + } + impl Drop for DeallocGuard { + fn drop(&mut self) { + unsafe { dealloc(self.ptr, self.layout) } + } + } + + // Deallocate even when the drop_in_place(...owner) panics + let _guard = DeallocGuard { + ptr: unsafe { + transmute::<*mut JoinedCell, *mut u8>(self.joined_ptr.as_ptr()) + }, + layout: Layout::new::>(), + }; + + unsafe { + // We must only drop owner and the struct itself, + // The whole point of this drop guard is to clean up the partially + // initialized struct should building the dependent fail. + drop_in_place(&mut (*self.joined_ptr.as_ptr()).owner); + } + + // Deallocation happens at end of scope + } +} + +// Older versions of rust do not support addr_of_mut!. What we want to do here +// is to emulate the behavior of that macro by going (incorrectly) via a +// reference cast. Technically this is UB, but testing does not show the older +// compiler versions (ab)using this. For discussions about this behavior see +// https://github.com/Voultapher/self_cell/pull/31 and +// https://github.com/Voultapher/self_cell/issues/30 and +// https://github.com/Voultapher/self_cell/pull/33 +// +// Because of 'procedural macros cannot expand to macro definitions' +// we have wrap this in functions. +impl JoinedCell { + #[doc(hidden)] + #[cfg(not(feature = "old_rust"))] + pub unsafe fn _field_pointers(this: *mut Self) -> (*mut Owner, *mut Dependent) { + let owner_ptr = core::ptr::addr_of_mut!((*this).owner); + let dependent_ptr = core::ptr::addr_of_mut!((*this).dependent); + + (owner_ptr, dependent_ptr) + } + + #[doc(hidden)] + #[cfg(feature = "old_rust")] + #[rustversion::since(1.51)] + pub unsafe fn _field_pointers(this: *mut Self) -> (*mut Owner, *mut Dependent) { + let owner_ptr = core::ptr::addr_of_mut!((*this).owner); + let dependent_ptr = core::ptr::addr_of_mut!((*this).dependent); + + (owner_ptr, dependent_ptr) + } + + #[doc(hidden)] + #[cfg(feature = "old_rust")] + #[rustversion::before(1.51)] + pub unsafe fn _field_pointers(this: *mut Self) -> (*mut Owner, *mut Dependent) { + // See comment above, technically this is UB. + let owner_ptr = &mut (*this).owner as *mut Owner; + let dependent_ptr = &mut (*this).dependent as *mut Dependent; + + (owner_ptr, dependent_ptr) + } +} -- cgit v1.2.3