diff options
Diffstat (limited to 'vendor/rowan')
25 files changed, 5142 insertions, 0 deletions
diff --git a/vendor/rowan/.cargo-checksum.json b/vendor/rowan/.cargo-checksum.json new file mode 100644 index 000000000..f2cbdfc1d --- /dev/null +++ b/vendor/rowan/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.lock":"d89194369a60b64062043f52664726c5f114542c20c2fbfaafac9fad682c139b","Cargo.toml":"fbd2ff15249776d6bbc4d3646ed0a7681172aad7c7f7a42b512308b7672b43b4","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"23f18e03dc49df91622fe2a76176497404e46ced8a715d9d2b67a7446571cca3","README.md":"69657dd291f7b245820ee01fa7bdbfdc5dc2b47284767641ffb8f94e9f9bc522","examples/math.rs":"e7557914686973cc16c6b2736a9934708465ef996b4f0a54fdb454b524641dc9","examples/s_expressions.rs":"6d963a8c030978e2648a059f2dcd5314d9fef47f0dda45e4134caedae1429eee","src/api.rs":"b5d48c0d401014c09ef9d8ee54c849735b1235e5faa798f7291be3d6a8a335c9","src/arc.rs":"fef1aa58a57d167bf4ba99b186b7e9a9c0df8c6096c2f604fbff86430dbaa6e3","src/ast.rs":"6eeedc3fcfb7b1d3d53aa54fc68a8f3bc6381ba2433e12d82b13f51fb5a82446","src/cow_mut.rs":"c90f47a013ae8cfb00bee089b75bbc2e493424e344fb4aaeff78cb2db8558ec2","src/cursor.rs":"b150f5d016aee8b196f5c02af6e7473b32e62f39fc62242dd7adbfddb21f8b69","src/green.rs":"34d58d497d2af2bbd1533aea6b4aa91496d65275b3b6def8dd6f5b1210ec0ce0","src/green/builder.rs":"517e4f6393f8fe6deaabd288f5e5b6a670dc7deec99e5bd92df34cdb4f02db49","src/green/element.rs":"df199a8b6adefef54398f209e7316525eaf84133e952325d46641b66cb89ada9","src/green/node.rs":"02701fc84ad6fdf44bd2c9b63923b0c919ca77acdb09c40d1d2b949830eab185","src/green/node_cache.rs":"f85ca104edb7d2261fd111a6fa4165f076e802aa9414457bdb028788db8dde9d","src/green/token.rs":"a1440de773044e82686dc9173ca7732a6a415a7ba6272c8bc68b3dd896f0cd7b","src/lib.rs":"e0eb1ba73978636b577094ebb726e2e222f347587928ba3930b196b809f17f86","src/serde_impls.rs":"603a459c1e3ad6edd2915e6ef3d103bae36364e01d781a8521486d618ba7b678","src/sll.rs":"f476ecf40629de8f45f5d952a88ebd91f91c71ac635ddc7cd2eebf5a90ce07bf","src/syntax_text.rs":"e387fa481a53aa9dd220a350acabd150daa8440c07ade49ea8a2f69275c6b366","src/utility_types.rs":"ce0874ae3e2b1eccb77025322c4453ceafef983f5d41b442448fb848259edf06","tests/tidy.rs":"15f655d7022a23cea887c6ac52727811f72c7d6a0fd54cdbb0476521ab4fea7f"},"package":"e88acf7b001007e9e8c989fe7449f6601d909e5dd2c56399fc158977ad6c56e8"}
\ No newline at end of file diff --git a/vendor/rowan/Cargo.lock b/vendor/rowan/Cargo.lock new file mode 100644 index 000000000..a53655c96 --- /dev/null +++ b/vendor/rowan/Cargo.lock @@ -0,0 +1,105 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "0.7.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e37cfd5e7657ada45f742d6e99ca5788580b5c529dc78faf11ece6dc702656f" +dependencies = [ + "memchr", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "countme" +version = "3.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7704b5fdd17b18ae31c4c1da5a2e0305a2bf17b5249300a9ee9ed7b72114c636" + +[[package]] +name = "hashbrown" +version = "0.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888" + +[[package]] +name = "m_lexer" +version = "0.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7e51ebf91162d585a5bae05e4779efc4a276171cb880d61dd6fab11c98467a7" +dependencies = [ + "regex", +] + +[[package]] +name = "memchr" +version = "2.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2dffe52ecf27772e601905b7522cb4ef790d2cc203488bbd0e2fe85fcb74566d" + +[[package]] +name = "memoffset" +version = "0.6.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5aa361d4faea93603064a027415f07bd8e1d5c88c9fbf68bf56a285428fd79ce" +dependencies = [ + "autocfg", +] + +[[package]] +name = "regex" +version = "1.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4c4eb3267174b8c6c2f654116623910a0fef09c4753f8dd83db29c48a0df988b" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.6.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a3f87b73ce11b1619a3c6332f45341e0047173771e8b8b73f87bfeefb7b56244" + +[[package]] +name = "rowan" +version = "0.15.8" +dependencies = [ + "countme", + "hashbrown", + "m_lexer", + "memoffset", + "rustc-hash", + "serde", + "text-size", +] + +[[package]] +name = "rustc-hash" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "08d43f7aa6b08d49f382cde6a7982047c3426db949b1424bc4b7ec9ae12c6ce2" + +[[package]] +name = "serde" +version = "1.0.140" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fc855a42c7967b7c369eb5860f7164ef1f6f81c20c7cc1141f2a604e18723b03" + +[[package]] +name = "text-size" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "288cb548dbe72b652243ea797201f3d481a0609a967980fcc5b2315ea811560a" +dependencies = [ + "serde", +] diff --git a/vendor/rowan/Cargo.toml b/vendor/rowan/Cargo.toml new file mode 100644 index 000000000..c717f55d0 --- /dev/null +++ b/vendor/rowan/Cargo.toml @@ -0,0 +1,57 @@ +# 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 = "2021" +name = "rowan" +version = "0.15.8" +authors = ["Aleksey Kladov <aleksey.kladov@gmail.com>"] +exclude = [ + ".github/", + "bors.toml", + "rustfmt.toml", +] +description = "Library for generic lossless syntax trees" +readme = "README.md" +license = "MIT OR Apache-2.0" +repository = "https://github.com/rust-analyzer/rowan" +resolver = "2" + +[dependencies.countme] +version = "3.0.0" + +[dependencies.hashbrown] +version = "0.12" +features = ["inline-more"] +default-features = false + +[dependencies.memoffset] +version = "0.6" + +[dependencies.rustc-hash] +version = "1.0.1" + +[dependencies.serde] +version = "1.0.89" +optional = true +default-features = false + +[dependencies.text-size] +version = "1.1.0" + +[dev-dependencies.m_lexer] +version = "0.0.4" + +[features] +serde1 = [ + "serde", + "text-size/serde", +] diff --git a/vendor/rowan/LICENSE-APACHE b/vendor/rowan/LICENSE-APACHE new file mode 100644 index 000000000..16fe87b06 --- /dev/null +++ b/vendor/rowan/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/vendor/rowan/LICENSE-MIT b/vendor/rowan/LICENSE-MIT new file mode 100644 index 000000000..31aa79387 --- /dev/null +++ b/vendor/rowan/LICENSE-MIT @@ -0,0 +1,23 @@ +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/vendor/rowan/README.md b/vendor/rowan/README.md new file mode 100644 index 000000000..f0d5b133e --- /dev/null +++ b/vendor/rowan/README.md @@ -0,0 +1,22 @@ +# Rowan + +[](https://crates.io/crates/rowan) +[](https://crates.io/crates/rowan) + +Rowan is a library for lossless syntax trees, inspired in part by +Swift's [libsyntax](https://github.com/apple/swift/tree/5e2c815edfd758f9b1309ce07bfc01c4bc20ec23/lib/Syntax). + +A conceptual overview is available in the [rust-analyzer repo](https://github.com/rust-analyzer/rust-analyzer/blob/master/docs/dev/syntax.md). + +See `examples/s_expressions` for a tutorial, and [rust-analyzer](https://github.com/rust-analyzer/rust-analyzer/) for real-world usage. + +## Testing + +This crate is primarily tested by various integration tests in rust-analyzer. + +## License + +Rowan is primarily distributed under the terms of both the MIT +license and the Apache License (Version 2.0). + +See LICENSE-APACHE and LICENSE-MIT for details. diff --git a/vendor/rowan/examples/math.rs b/vendor/rowan/examples/math.rs new file mode 100644 index 000000000..930c591b0 --- /dev/null +++ b/vendor/rowan/examples/math.rs @@ -0,0 +1,152 @@ +//! Example that takes the input +//! 1 + 2 * 3 + 4 +//! and builds the tree +//! - Marker(Root) +//! - Marker(Operation) +//! - Marker(Operation) +//! - "1" Token(Number) +//! - "+" Token(Add) +//! - Marker(Operation) +//! - "2" Token(Number) +//! - "*" Token(Mul) +//! - "3" Token(Number) +//! - "+" Token(Add) +//! - "4" Token(Number) + +use rowan::{GreenNodeBuilder, NodeOrToken}; +use std::iter::Peekable; + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +#[allow(non_camel_case_types)] +#[repr(u16)] +enum SyntaxKind { + WHITESPACE = 0, + + ADD, + SUB, + MUL, + DIV, + + NUMBER, + ERROR, + OPERATION, + ROOT, +} +use SyntaxKind::*; + +impl From<SyntaxKind> for rowan::SyntaxKind { + fn from(kind: SyntaxKind) -> Self { + Self(kind as u16) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +enum Lang {} +impl rowan::Language for Lang { + type Kind = SyntaxKind; + fn kind_from_raw(raw: rowan::SyntaxKind) -> Self::Kind { + assert!(raw.0 <= ROOT as u16); + unsafe { std::mem::transmute::<u16, SyntaxKind>(raw.0) } + } + fn kind_to_raw(kind: Self::Kind) -> rowan::SyntaxKind { + kind.into() + } +} + +type SyntaxNode = rowan::SyntaxNode<Lang>; +#[allow(unused)] +type SyntaxToken = rowan::SyntaxToken<Lang>; +#[allow(unused)] +type SyntaxElement = rowan::NodeOrToken<SyntaxNode, SyntaxToken>; + +struct Parser<I: Iterator<Item = (SyntaxKind, String)>> { + builder: GreenNodeBuilder<'static>, + iter: Peekable<I>, +} +impl<I: Iterator<Item = (SyntaxKind, String)>> Parser<I> { + fn peek(&mut self) -> Option<SyntaxKind> { + while self.iter.peek().map(|&(t, _)| t == WHITESPACE).unwrap_or(false) { + self.bump(); + } + self.iter.peek().map(|&(t, _)| t) + } + fn bump(&mut self) { + if let Some((token, string)) = self.iter.next() { + self.builder.token(token.into(), string.as_str()); + } + } + fn parse_val(&mut self) { + match self.peek() { + Some(NUMBER) => self.bump(), + _ => { + self.builder.start_node(ERROR.into()); + self.bump(); + self.builder.finish_node(); + } + } + } + fn handle_operation(&mut self, tokens: &[SyntaxKind], next: fn(&mut Self)) { + let checkpoint = self.builder.checkpoint(); + next(self); + while self.peek().map(|t| tokens.contains(&t)).unwrap_or(false) { + self.builder.start_node_at(checkpoint, OPERATION.into()); + self.bump(); + next(self); + self.builder.finish_node(); + } + } + fn parse_mul(&mut self) { + self.handle_operation(&[MUL, DIV], Self::parse_val) + } + fn parse_add(&mut self) { + self.handle_operation(&[ADD, SUB], Self::parse_mul) + } + fn parse(mut self) -> SyntaxNode { + self.builder.start_node(ROOT.into()); + self.parse_add(); + self.builder.finish_node(); + + SyntaxNode::new_root(self.builder.finish()) + } +} + +fn print(indent: usize, element: SyntaxElement) { + let kind: SyntaxKind = element.kind().into(); + print!("{:indent$}", "", indent = indent); + match element { + NodeOrToken::Node(node) => { + println!("- {:?}", kind); + for child in node.children_with_tokens() { + print(indent + 2, child); + } + } + + NodeOrToken::Token(token) => println!("- {:?} {:?}", token.text(), kind), + } +} + +fn main() { + let ast = Parser { + builder: GreenNodeBuilder::new(), + iter: vec![ + // 1 + 2 * 3 + 4 + (NUMBER, "1".into()), + (WHITESPACE, " ".into()), + (ADD, "+".into()), + (WHITESPACE, " ".into()), + (NUMBER, "2".into()), + (WHITESPACE, " ".into()), + (MUL, "*".into()), + (WHITESPACE, " ".into()), + (NUMBER, "3".into()), + (WHITESPACE, " ".into()), + (ADD, "+".into()), + (WHITESPACE, " ".into()), + (NUMBER, "4".into()), + ] + .into_iter() + .peekable(), + } + .parse(); + print(0, ast.into()); +} diff --git a/vendor/rowan/examples/s_expressions.rs b/vendor/rowan/examples/s_expressions.rs new file mode 100644 index 000000000..e7df4c644 --- /dev/null +++ b/vendor/rowan/examples/s_expressions.rs @@ -0,0 +1,425 @@ +//! In this tutorial, we will write parser +//! and evaluator of arithmetic S-expressions, +//! which look like this: +//! ``` +//! (+ (* 15 2) 62) +//! ``` +//! +//! It's suggested to read the conceptual overview of the design +//! alongside this tutorial: +//! https://github.com/rust-analyzer/rust-analyzer/blob/master/docs/dev/syntax.md + +/// Let's start with defining all kinds of tokens and +/// composite nodes. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +#[allow(non_camel_case_types)] +#[repr(u16)] +enum SyntaxKind { + L_PAREN = 0, // '(' + R_PAREN, // ')' + WORD, // '+', '15' + WHITESPACE, // whitespaces is explicit + ERROR, // as well as errors + + // composite nodes + LIST, // `(+ 2 3)` + ATOM, // `+`, `15`, wraps a WORD token + ROOT, // top-level node: a list of s-expressions +} +use SyntaxKind::*; + +/// Some boilerplate is needed, as rowan settled on using its own +/// `struct SyntaxKind(u16)` internally, instead of accepting the +/// user's `enum SyntaxKind` as a type parameter. +/// +/// First, to easily pass the enum variants into rowan via `.into()`: +impl From<SyntaxKind> for rowan::SyntaxKind { + fn from(kind: SyntaxKind) -> Self { + Self(kind as u16) + } +} + +/// Second, implementing the `Language` trait teaches rowan to convert between +/// these two SyntaxKind types, allowing for a nicer SyntaxNode API where +/// "kinds" are values from our `enum SyntaxKind`, instead of plain u16 values. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +enum Lang {} +impl rowan::Language for Lang { + type Kind = SyntaxKind; + fn kind_from_raw(raw: rowan::SyntaxKind) -> Self::Kind { + assert!(raw.0 <= ROOT as u16); + unsafe { std::mem::transmute::<u16, SyntaxKind>(raw.0) } + } + fn kind_to_raw(kind: Self::Kind) -> rowan::SyntaxKind { + kind.into() + } +} + +/// GreenNode is an immutable tree, which is cheap to change, +/// but doesn't contain offsets and parent pointers. +use rowan::GreenNode; + +/// You can construct GreenNodes by hand, but a builder +/// is helpful for top-down parsers: it maintains a stack +/// of currently in-progress nodes +use rowan::GreenNodeBuilder; + +/// The parse results are stored as a "green tree". +/// We'll discuss working with the results later +struct Parse { + green_node: GreenNode, + #[allow(unused)] + errors: Vec<String>, +} + +/// Now, let's write a parser. +/// Note that `parse` does not return a `Result`: +/// by design, syntax tree can be built even for +/// completely invalid source code. +fn parse(text: &str) -> Parse { + struct Parser { + /// input tokens, including whitespace, + /// in *reverse* order. + tokens: Vec<(SyntaxKind, String)>, + /// the in-progress tree. + builder: GreenNodeBuilder<'static>, + /// the list of syntax errors we've accumulated + /// so far. + errors: Vec<String>, + } + + /// The outcome of parsing a single S-expression + enum SexpRes { + /// An S-expression (i.e. an atom, or a list) was successfully parsed + Ok, + /// Nothing was parsed, as no significant tokens remained + Eof, + /// An unexpected ')' was found + RParen, + } + + impl Parser { + fn parse(mut self) -> Parse { + // Make sure that the root node covers all source + self.builder.start_node(ROOT.into()); + // Parse zero or more S-expressions + loop { + match self.sexp() { + SexpRes::Eof => break, + SexpRes::RParen => { + self.builder.start_node(ERROR.into()); + self.errors.push("unmatched `)`".to_string()); + self.bump(); // be sure to chug along in case of error + self.builder.finish_node(); + } + SexpRes::Ok => (), + } + } + // Don't forget to eat *trailing* whitespace + self.skip_ws(); + // Close the root node. + self.builder.finish_node(); + + // Turn the builder into a GreenNode + Parse { green_node: self.builder.finish(), errors: self.errors } + } + fn list(&mut self) { + assert_eq!(self.current(), Some(L_PAREN)); + // Start the list node + self.builder.start_node(LIST.into()); + self.bump(); // '(' + loop { + match self.sexp() { + SexpRes::Eof => { + self.errors.push("expected `)`".to_string()); + break; + } + SexpRes::RParen => { + self.bump(); + break; + } + SexpRes::Ok => (), + } + } + // close the list node + self.builder.finish_node(); + } + fn sexp(&mut self) -> SexpRes { + // Eat leading whitespace + self.skip_ws(); + // Either a list, an atom, a closing paren, + // or an eof. + let t = match self.current() { + None => return SexpRes::Eof, + Some(R_PAREN) => return SexpRes::RParen, + Some(t) => t, + }; + match t { + L_PAREN => self.list(), + WORD => { + self.builder.start_node(ATOM.into()); + self.bump(); + self.builder.finish_node(); + } + ERROR => self.bump(), + _ => unreachable!(), + } + SexpRes::Ok + } + /// Advance one token, adding it to the current branch of the tree builder. + fn bump(&mut self) { + let (kind, text) = self.tokens.pop().unwrap(); + self.builder.token(kind.into(), text.as_str()); + } + /// Peek at the first unprocessed token + fn current(&self) -> Option<SyntaxKind> { + self.tokens.last().map(|(kind, _)| *kind) + } + fn skip_ws(&mut self) { + while self.current() == Some(WHITESPACE) { + self.bump() + } + } + } + + let mut tokens = lex(text); + tokens.reverse(); + Parser { tokens, builder: GreenNodeBuilder::new(), errors: Vec::new() }.parse() +} + +/// To work with the parse results we need a view into the +/// green tree - the Syntax tree. +/// It is also immutable, like a GreenNode, +/// but it contains parent pointers, offsets, and +/// has identity semantics. + +type SyntaxNode = rowan::SyntaxNode<Lang>; +#[allow(unused)] +type SyntaxToken = rowan::SyntaxToken<Lang>; +#[allow(unused)] +type SyntaxElement = rowan::NodeOrToken<SyntaxNode, SyntaxToken>; + +impl Parse { + fn syntax(&self) -> SyntaxNode { + SyntaxNode::new_root(self.green_node.clone()) + } +} + +/// Let's check that the parser works as expected +#[test] +fn test_parser() { + let text = "(+ (* 15 2) 62)"; + let node = parse(text).syntax(); + assert_eq!( + format!("{:?}", node), + "ROOT@0..15", // root node, spanning 15 bytes + ); + assert_eq!(node.children().count(), 1); + let list = node.children().next().unwrap(); + let children = list + .children_with_tokens() + .map(|child| format!("{:?}@{:?}", child.kind(), child.text_range())) + .collect::<Vec<_>>(); + + assert_eq!( + children, + vec![ + "L_PAREN@0..1".to_string(), + "ATOM@1..2".to_string(), + "WHITESPACE@2..3".to_string(), // note, explicit whitespace! + "LIST@3..11".to_string(), + "WHITESPACE@11..12".to_string(), + "ATOM@12..14".to_string(), + "R_PAREN@14..15".to_string(), + ] + ); +} + +/// So far, we've been working with a homogeneous untyped tree. +/// It's nice to provide generic tree operations, like traversals, +/// but it's a bad fit for semantic analysis. +/// This crate itself does not provide AST facilities directly, +/// but it is possible to layer AST on top of `SyntaxNode` API. +/// Let's write a function to evaluate S-expression. +/// +/// For that, let's define AST nodes. +/// It'll be quite a bunch of repetitive code, so we'll use a macro. +/// +/// For a real language, you'd want to generate an AST. I find a +/// combination of `serde`, `ron` and `tera` crates invaluable for that! +macro_rules! ast_node { + ($ast:ident, $kind:ident) => { + #[derive(PartialEq, Eq, Hash)] + #[repr(transparent)] + struct $ast(SyntaxNode); + impl $ast { + #[allow(unused)] + fn cast(node: SyntaxNode) -> Option<Self> { + if node.kind() == $kind { + Some(Self(node)) + } else { + None + } + } + } + }; +} + +ast_node!(Root, ROOT); +ast_node!(Atom, ATOM); +ast_node!(List, LIST); + +// Sexp is slightly different, so let's do it by hand. +#[derive(PartialEq, Eq, Hash)] +#[repr(transparent)] +struct Sexp(SyntaxNode); + +enum SexpKind { + Atom(Atom), + List(List), +} + +impl Sexp { + fn cast(node: SyntaxNode) -> Option<Self> { + if Atom::cast(node.clone()).is_some() || List::cast(node.clone()).is_some() { + Some(Sexp(node)) + } else { + None + } + } + + fn kind(&self) -> SexpKind { + Atom::cast(self.0.clone()) + .map(SexpKind::Atom) + .or_else(|| List::cast(self.0.clone()).map(SexpKind::List)) + .unwrap() + } +} + +// Let's enhance AST nodes with ancillary functions and +// eval. +impl Root { + fn sexps(&self) -> impl Iterator<Item = Sexp> + '_ { + self.0.children().filter_map(Sexp::cast) + } +} + +enum Op { + Add, + Sub, + Div, + Mul, +} + +impl Atom { + fn eval(&self) -> Option<i64> { + self.text().parse().ok() + } + fn as_op(&self) -> Option<Op> { + let op = match self.text().as_str() { + "+" => Op::Add, + "-" => Op::Sub, + "*" => Op::Mul, + "/" => Op::Div, + _ => return None, + }; + Some(op) + } + fn text(&self) -> String { + match self.0.green().children().next() { + Some(rowan::NodeOrToken::Token(token)) => token.text().to_string(), + _ => unreachable!(), + } + } +} + +impl List { + fn sexps(&self) -> impl Iterator<Item = Sexp> + '_ { + self.0.children().filter_map(Sexp::cast) + } + fn eval(&self) -> Option<i64> { + let op = match self.sexps().nth(0)?.kind() { + SexpKind::Atom(atom) => atom.as_op()?, + _ => return None, + }; + let arg1 = self.sexps().nth(1)?.eval()?; + let arg2 = self.sexps().nth(2)?.eval()?; + let res = match op { + Op::Add => arg1 + arg2, + Op::Sub => arg1 - arg2, + Op::Mul => arg1 * arg2, + Op::Div if arg2 == 0 => return None, + Op::Div => arg1 / arg2, + }; + Some(res) + } +} + +impl Sexp { + fn eval(&self) -> Option<i64> { + match self.kind() { + SexpKind::Atom(atom) => atom.eval(), + SexpKind::List(list) => list.eval(), + } + } +} + +impl Parse { + fn root(&self) -> Root { + Root::cast(self.syntax()).unwrap() + } +} + +/// Let's test the eval! +fn main() { + let sexps = " +92 +(+ 62 30) +(/ 92 0) +nan +(+ (* 15 2) 62) +"; + let root = parse(sexps).root(); + let res = root.sexps().map(|it| it.eval()).collect::<Vec<_>>(); + eprintln!("{:?}", res); + assert_eq!(res, vec![Some(92), Some(92), None, None, Some(92),]) +} + +/// Split the input string into a flat list of tokens +/// (such as L_PAREN, WORD, and WHITESPACE) +fn lex(text: &str) -> Vec<(SyntaxKind, String)> { + fn tok(t: SyntaxKind) -> m_lexer::TokenKind { + m_lexer::TokenKind(rowan::SyntaxKind::from(t).0) + } + fn kind(t: m_lexer::TokenKind) -> SyntaxKind { + match t.0 { + 0 => L_PAREN, + 1 => R_PAREN, + 2 => WORD, + 3 => WHITESPACE, + 4 => ERROR, + _ => unreachable!(), + } + } + + let lexer = m_lexer::LexerBuilder::new() + .error_token(tok(ERROR)) + .tokens(&[ + (tok(L_PAREN), r"\("), + (tok(R_PAREN), r"\)"), + (tok(WORD), r"[^\s()]+"), + (tok(WHITESPACE), r"\s+"), + ]) + .build(); + + lexer + .tokenize(text) + .into_iter() + .map(|t| (t.len, kind(t.kind))) + .scan(0usize, |start_offset, (len, kind)| { + let s: String = text[*start_offset..*start_offset + len].into(); + *start_offset += len; + Some((kind, s)) + }) + .collect() +} diff --git a/vendor/rowan/src/api.rs b/vendor/rowan/src/api.rs new file mode 100644 index 000000000..605fcc50c --- /dev/null +++ b/vendor/rowan/src/api.rs @@ -0,0 +1,487 @@ +use std::{borrow::Cow, fmt, iter, marker::PhantomData, ops::Range}; + +use crate::{ + cursor, green::GreenTokenData, Direction, GreenNode, GreenNodeData, GreenToken, NodeOrToken, + SyntaxKind, SyntaxText, TextRange, TextSize, TokenAtOffset, WalkEvent, +}; + +pub trait Language: Sized + Copy + fmt::Debug + Eq + Ord + std::hash::Hash { + type Kind: Sized + Copy + fmt::Debug + Eq + Ord + std::hash::Hash; + + fn kind_from_raw(raw: SyntaxKind) -> Self::Kind; + fn kind_to_raw(kind: Self::Kind) -> SyntaxKind; +} + +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct SyntaxNode<L: Language> { + raw: cursor::SyntaxNode, + _p: PhantomData<L>, +} + +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct SyntaxToken<L: Language> { + raw: cursor::SyntaxToken, + _p: PhantomData<L>, +} + +pub type SyntaxElement<L> = NodeOrToken<SyntaxNode<L>, SyntaxToken<L>>; + +impl<L: Language> fmt::Debug for SyntaxNode<L> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if f.alternate() { + let mut level = 0; + for event in self.preorder_with_tokens() { + match event { + WalkEvent::Enter(element) => { + for _ in 0..level { + write!(f, " ")?; + } + match element { + NodeOrToken::Node(node) => writeln!(f, "{:?}", node)?, + NodeOrToken::Token(token) => writeln!(f, "{:?}", token)?, + } + level += 1; + } + WalkEvent::Leave(_) => level -= 1, + } + } + assert_eq!(level, 0); + Ok(()) + } else { + write!(f, "{:?}@{:?}", self.kind(), self.text_range()) + } + } +} + +impl<L: Language> fmt::Display for SyntaxNode<L> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.raw, f) + } +} + +impl<L: Language> fmt::Debug for SyntaxToken<L> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{:?}@{:?}", self.kind(), self.text_range())?; + if self.text().len() < 25 { + return write!(f, " {:?}", self.text()); + } + let text = self.text(); + for idx in 21..25 { + if text.is_char_boundary(idx) { + let text = format!("{} ...", &text[..idx]); + return write!(f, " {:?}", text); + } + } + unreachable!() + } +} + +impl<L: Language> fmt::Display for SyntaxToken<L> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.raw, f) + } +} + +impl<L: Language> From<SyntaxNode<L>> for SyntaxElement<L> { + fn from(node: SyntaxNode<L>) -> SyntaxElement<L> { + NodeOrToken::Node(node) + } +} + +impl<L: Language> From<SyntaxToken<L>> for SyntaxElement<L> { + fn from(token: SyntaxToken<L>) -> SyntaxElement<L> { + NodeOrToken::Token(token) + } +} + +impl<L: Language> SyntaxNode<L> { + pub fn new_root(green: GreenNode) -> SyntaxNode<L> { + SyntaxNode::from(cursor::SyntaxNode::new_root(green)) + } + /// Returns a green tree, equal to the green tree this node + /// belongs two, except with this node substitute. The complexity + /// of operation is proportional to the depth of the tree + pub fn replace_with(&self, replacement: GreenNode) -> GreenNode { + self.raw.replace_with(replacement) + } + + pub fn kind(&self) -> L::Kind { + L::kind_from_raw(self.raw.kind()) + } + + pub fn text_range(&self) -> TextRange { + self.raw.text_range() + } + + pub fn index(&self) -> usize { + self.raw.index() + } + + pub fn text(&self) -> SyntaxText { + self.raw.text() + } + + pub fn green(&self) -> Cow<'_, GreenNodeData> { + self.raw.green() + } + + pub fn parent(&self) -> Option<SyntaxNode<L>> { + self.raw.parent().map(Self::from) + } + + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode<L>> { + self.raw.ancestors().map(SyntaxNode::from) + } + + pub fn children(&self) -> SyntaxNodeChildren<L> { + SyntaxNodeChildren { raw: self.raw.children(), _p: PhantomData } + } + + pub fn children_with_tokens(&self) -> SyntaxElementChildren<L> { + SyntaxElementChildren { raw: self.raw.children_with_tokens(), _p: PhantomData } + } + + pub fn first_child(&self) -> Option<SyntaxNode<L>> { + self.raw.first_child().map(Self::from) + } + pub fn last_child(&self) -> Option<SyntaxNode<L>> { + self.raw.last_child().map(Self::from) + } + + pub fn first_child_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.first_child_or_token().map(NodeOrToken::from) + } + pub fn last_child_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.last_child_or_token().map(NodeOrToken::from) + } + + pub fn next_sibling(&self) -> Option<SyntaxNode<L>> { + self.raw.next_sibling().map(Self::from) + } + pub fn prev_sibling(&self) -> Option<SyntaxNode<L>> { + self.raw.prev_sibling().map(Self::from) + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.next_sibling_or_token().map(NodeOrToken::from) + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.prev_sibling_or_token().map(NodeOrToken::from) + } + + /// Return the leftmost token in the subtree of this node. + pub fn first_token(&self) -> Option<SyntaxToken<L>> { + self.raw.first_token().map(SyntaxToken::from) + } + /// Return the rightmost token in the subtree of this node. + pub fn last_token(&self) -> Option<SyntaxToken<L>> { + self.raw.last_token().map(SyntaxToken::from) + } + + pub fn siblings(&self, direction: Direction) -> impl Iterator<Item = SyntaxNode<L>> { + self.raw.siblings(direction).map(SyntaxNode::from) + } + + pub fn siblings_with_tokens( + &self, + direction: Direction, + ) -> impl Iterator<Item = SyntaxElement<L>> { + self.raw.siblings_with_tokens(direction).map(SyntaxElement::from) + } + + pub fn descendants(&self) -> impl Iterator<Item = SyntaxNode<L>> { + self.raw.descendants().map(SyntaxNode::from) + } + + pub fn descendants_with_tokens(&self) -> impl Iterator<Item = SyntaxElement<L>> { + self.raw.descendants_with_tokens().map(NodeOrToken::from) + } + + /// Traverse the subtree rooted at the current node (including the current + /// node) in preorder, excluding tokens. + pub fn preorder(&self) -> Preorder<L> { + Preorder { raw: self.raw.preorder(), _p: PhantomData } + } + + /// Traverse the subtree rooted at the current node (including the current + /// node) in preorder, including tokens. + pub fn preorder_with_tokens(&self) -> PreorderWithTokens<L> { + PreorderWithTokens { raw: self.raw.preorder_with_tokens(), _p: PhantomData } + } + + /// Find a token in the subtree corresponding to this node, which covers the offset. + /// Precondition: offset must be withing node's range. + pub fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken<L>> { + self.raw.token_at_offset(offset).map(SyntaxToken::from) + } + + /// Return the deepest node or token in the current subtree that fully + /// contains the range. If the range is empty and is contained in two leaf + /// nodes, either one can be returned. Precondition: range must be contained + /// withing the current node + pub fn covering_element(&self, range: TextRange) -> SyntaxElement<L> { + NodeOrToken::from(self.raw.covering_element(range)) + } + + /// Finds a [`SyntaxElement`] which intersects with a given `range`. If + /// there are several intersecting elements, any one can be returned. + /// + /// The method uses binary search internally, so it's complexity is + /// `O(log(N))` where `N = self.children_with_tokens().count()`. + pub fn child_or_token_at_range(&self, range: TextRange) -> Option<SyntaxElement<L>> { + self.raw.child_or_token_at_range(range).map(SyntaxElement::from) + } + + /// Returns an independent copy of the subtree rooted at this node. + /// + /// The parent of the returned node will be `None`, the start offset will be + /// zero, but, otherwise, it'll be equivalent to the source node. + pub fn clone_subtree(&self) -> SyntaxNode<L> { + SyntaxNode::from(self.raw.clone_subtree()) + } + + pub fn clone_for_update(&self) -> SyntaxNode<L> { + SyntaxNode::from(self.raw.clone_for_update()) + } + + pub fn detach(&self) { + self.raw.detach() + } + + pub fn splice_children(&self, to_delete: Range<usize>, to_insert: Vec<SyntaxElement<L>>) { + let to_insert = to_insert.into_iter().map(cursor::SyntaxElement::from).collect::<Vec<_>>(); + self.raw.splice_children(to_delete, to_insert) + } +} + +impl<L: Language> SyntaxToken<L> { + /// Returns a green tree, equal to the green tree this token + /// belongs two, except with this token substitute. The complexity + /// of operation is proportional to the depth of the tree + pub fn replace_with(&self, new_token: GreenToken) -> GreenNode { + self.raw.replace_with(new_token) + } + + pub fn kind(&self) -> L::Kind { + L::kind_from_raw(self.raw.kind()) + } + + pub fn text_range(&self) -> TextRange { + self.raw.text_range() + } + + pub fn index(&self) -> usize { + self.raw.index() + } + + pub fn text(&self) -> &str { + self.raw.text() + } + + pub fn green(&self) -> &GreenTokenData { + self.raw.green() + } + + pub fn parent(&self) -> Option<SyntaxNode<L>> { + self.raw.parent().map(SyntaxNode::from) + } + + /// Iterator over all the ancestors of this token excluding itself. + #[deprecated = "use `SyntaxToken::parent_ancestors` instead"] + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode<L>> { + self.parent_ancestors() + } + + /// Iterator over all the ancestors of this token excluding itself. + pub fn parent_ancestors(&self) -> impl Iterator<Item = SyntaxNode<L>> { + self.raw.ancestors().map(SyntaxNode::from) + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.next_sibling_or_token().map(NodeOrToken::from) + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + self.raw.prev_sibling_or_token().map(NodeOrToken::from) + } + + pub fn siblings_with_tokens( + &self, + direction: Direction, + ) -> impl Iterator<Item = SyntaxElement<L>> { + self.raw.siblings_with_tokens(direction).map(SyntaxElement::from) + } + + /// Next token in the tree (i.e, not necessary a sibling). + pub fn next_token(&self) -> Option<SyntaxToken<L>> { + self.raw.next_token().map(SyntaxToken::from) + } + /// Previous token in the tree (i.e, not necessary a sibling). + pub fn prev_token(&self) -> Option<SyntaxToken<L>> { + self.raw.prev_token().map(SyntaxToken::from) + } + + pub fn detach(&self) { + self.raw.detach() + } +} + +impl<L: Language> SyntaxElement<L> { + pub fn text_range(&self) -> TextRange { + match self { + NodeOrToken::Node(it) => it.text_range(), + NodeOrToken::Token(it) => it.text_range(), + } + } + + pub fn index(&self) -> usize { + match self { + NodeOrToken::Node(it) => it.index(), + NodeOrToken::Token(it) => it.index(), + } + } + + pub fn kind(&self) -> L::Kind { + match self { + NodeOrToken::Node(it) => it.kind(), + NodeOrToken::Token(it) => it.kind(), + } + } + + pub fn parent(&self) -> Option<SyntaxNode<L>> { + match self { + NodeOrToken::Node(it) => it.parent(), + NodeOrToken::Token(it) => it.parent(), + } + } + + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode<L>> { + let first = match self { + NodeOrToken::Node(it) => Some(it.clone()), + NodeOrToken::Token(it) => it.parent(), + }; + iter::successors(first, SyntaxNode::parent) + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + match self { + NodeOrToken::Node(it) => it.next_sibling_or_token(), + NodeOrToken::Token(it) => it.next_sibling_or_token(), + } + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement<L>> { + match self { + NodeOrToken::Node(it) => it.prev_sibling_or_token(), + NodeOrToken::Token(it) => it.prev_sibling_or_token(), + } + } + pub fn detach(&self) { + match self { + NodeOrToken::Node(it) => it.detach(), + NodeOrToken::Token(it) => it.detach(), + } + } +} + +#[derive(Debug, Clone)] +pub struct SyntaxNodeChildren<L: Language> { + raw: cursor::SyntaxNodeChildren, + _p: PhantomData<L>, +} + +impl<L: Language> Iterator for SyntaxNodeChildren<L> { + type Item = SyntaxNode<L>; + fn next(&mut self) -> Option<Self::Item> { + self.raw.next().map(SyntaxNode::from) + } +} + +#[derive(Debug, Clone)] +pub struct SyntaxElementChildren<L: Language> { + raw: cursor::SyntaxElementChildren, + _p: PhantomData<L>, +} + +impl<L: Language> Iterator for SyntaxElementChildren<L> { + type Item = SyntaxElement<L>; + fn next(&mut self) -> Option<Self::Item> { + self.raw.next().map(NodeOrToken::from) + } +} + +pub struct Preorder<L: Language> { + raw: cursor::Preorder, + _p: PhantomData<L>, +} + +impl<L: Language> Preorder<L> { + pub fn skip_subtree(&mut self) { + self.raw.skip_subtree() + } +} + +impl<L: Language> Iterator for Preorder<L> { + type Item = WalkEvent<SyntaxNode<L>>; + fn next(&mut self) -> Option<Self::Item> { + self.raw.next().map(|it| it.map(SyntaxNode::from)) + } +} + +pub struct PreorderWithTokens<L: Language> { + raw: cursor::PreorderWithTokens, + _p: PhantomData<L>, +} + +impl<L: Language> PreorderWithTokens<L> { + pub fn skip_subtree(&mut self) { + self.raw.skip_subtree() + } +} + +impl<L: Language> Iterator for PreorderWithTokens<L> { + type Item = WalkEvent<SyntaxElement<L>>; + fn next(&mut self) -> Option<Self::Item> { + self.raw.next().map(|it| it.map(SyntaxElement::from)) + } +} + +impl<L: Language> From<cursor::SyntaxNode> for SyntaxNode<L> { + fn from(raw: cursor::SyntaxNode) -> SyntaxNode<L> { + SyntaxNode { raw, _p: PhantomData } + } +} + +impl<L: Language> From<SyntaxNode<L>> for cursor::SyntaxNode { + fn from(node: SyntaxNode<L>) -> cursor::SyntaxNode { + node.raw + } +} + +impl<L: Language> From<cursor::SyntaxToken> for SyntaxToken<L> { + fn from(raw: cursor::SyntaxToken) -> SyntaxToken<L> { + SyntaxToken { raw, _p: PhantomData } + } +} + +impl<L: Language> From<SyntaxToken<L>> for cursor::SyntaxToken { + fn from(token: SyntaxToken<L>) -> cursor::SyntaxToken { + token.raw + } +} + +impl<L: Language> From<cursor::SyntaxElement> for SyntaxElement<L> { + fn from(raw: cursor::SyntaxElement) -> SyntaxElement<L> { + match raw { + NodeOrToken::Node(it) => NodeOrToken::Node(it.into()), + NodeOrToken::Token(it) => NodeOrToken::Token(it.into()), + } + } +} + +impl<L: Language> From<SyntaxElement<L>> for cursor::SyntaxElement { + fn from(element: SyntaxElement<L>) -> cursor::SyntaxElement { + match element { + NodeOrToken::Node(it) => NodeOrToken::Node(it.into()), + NodeOrToken::Token(it) => NodeOrToken::Token(it.into()), + } + } +} diff --git a/vendor/rowan/src/arc.rs b/vendor/rowan/src/arc.rs new file mode 100644 index 000000000..348831290 --- /dev/null +++ b/vendor/rowan/src/arc.rs @@ -0,0 +1,463 @@ +//! Vendored and stripped down version of triomphe +use std::{ + alloc::{self, Layout}, + cmp::Ordering, + hash::{Hash, Hasher}, + marker::PhantomData, + mem::{self, ManuallyDrop}, + ops::Deref, + ptr, + sync::atomic::{ + self, + Ordering::{Acquire, Relaxed, Release}, + }, +}; + +use memoffset::offset_of; + +/// A soft limit on the amount of references that may be made to an `Arc`. +/// +/// Going above this limit will abort your program (although not +/// necessarily) at _exactly_ `MAX_REFCOUNT + 1` references. +const MAX_REFCOUNT: usize = (isize::MAX) as usize; + +/// The object allocated by an Arc<T> +#[repr(C)] +pub(crate) struct ArcInner<T: ?Sized> { + pub(crate) count: atomic::AtomicUsize, + pub(crate) data: T, +} + +unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {} +unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {} + +/// An atomically reference counted shared pointer +/// +/// See the documentation for [`Arc`] in the standard library. Unlike the +/// standard library `Arc`, this `Arc` does not support weak reference counting. +/// +/// [`Arc`]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html +#[repr(transparent)] +pub(crate) struct Arc<T: ?Sized> { + pub(crate) p: ptr::NonNull<ArcInner<T>>, + pub(crate) phantom: PhantomData<T>, +} + +unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {} +unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {} + +impl<T> Arc<T> { + /// Reconstruct the Arc<T> from a raw pointer obtained from into_raw() + /// + /// Note: This raw pointer will be offset in the allocation and must be preceded + /// by the atomic count. + /// + /// It is recommended to use OffsetArc for this + #[inline] + pub(crate) unsafe fn from_raw(ptr: *const T) -> Self { + // To find the corresponding pointer to the `ArcInner` we need + // to subtract the offset of the `data` field from the pointer. + let ptr = (ptr as *const u8).sub(offset_of!(ArcInner<T>, data)); + Arc { p: ptr::NonNull::new_unchecked(ptr as *mut ArcInner<T>), phantom: PhantomData } + } +} + +impl<T: ?Sized> Arc<T> { + #[inline] + fn inner(&self) -> &ArcInner<T> { + // This unsafety is ok because while this arc is alive we're guaranteed + // that the inner pointer is valid. Furthermore, we know that the + // `ArcInner` structure itself is `Sync` because the inner data is + // `Sync` as well, so we're ok loaning out an immutable pointer to these + // contents. + unsafe { &*self.ptr() } + } + + // Non-inlined part of `drop`. Just invokes the destructor. + #[inline(never)] + unsafe fn drop_slow(&mut self) { + let _ = Box::from_raw(self.ptr()); + } + + /// Test pointer equality between the two Arcs, i.e. they must be the _same_ + /// allocation + #[inline] + pub(crate) fn ptr_eq(this: &Self, other: &Self) -> bool { + this.ptr() == other.ptr() + } + + pub(crate) fn ptr(&self) -> *mut ArcInner<T> { + self.p.as_ptr() + } +} + +impl<T: ?Sized> Clone for Arc<T> { + #[inline] + fn clone(&self) -> Self { + // Using a relaxed ordering is alright here, as knowledge of the + // original reference prevents other threads from erroneously deleting + // the object. + // + // As explained in the [Boost documentation][1], Increasing the + // reference counter can always be done with memory_order_relaxed: New + // references to an object can only be formed from an existing + // reference, and passing an existing reference from one thread to + // another must already provide any required synchronization. + // + // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html) + let old_size = self.inner().count.fetch_add(1, Relaxed); + + // However we need to guard against massive refcounts in case someone + // is `mem::forget`ing Arcs. If we don't do this the count can overflow + // and users will use-after free. We racily saturate to `isize::MAX` on + // the assumption that there aren't ~2 billion threads incrementing + // the reference count at once. This branch will never be taken in + // any realistic program. + // + // We abort because such a program is incredibly degenerate, and we + // don't care to support it. + if old_size > MAX_REFCOUNT { + std::process::abort(); + } + + unsafe { Arc { p: ptr::NonNull::new_unchecked(self.ptr()), phantom: PhantomData } } + } +} + +impl<T: ?Sized> Deref for Arc<T> { + type Target = T; + + #[inline] + fn deref(&self) -> &T { + &self.inner().data + } +} + +impl<T: ?Sized> Arc<T> { + /// Provides mutable access to the contents _if_ the `Arc` is uniquely owned. + #[inline] + pub(crate) fn get_mut(this: &mut Self) -> Option<&mut T> { + if this.is_unique() { + unsafe { + // See make_mut() for documentation of the threadsafety here. + Some(&mut (*this.ptr()).data) + } + } else { + None + } + } + + /// Whether or not the `Arc` is uniquely owned (is the refcount 1?). + pub(crate) fn is_unique(&self) -> bool { + // See the extensive discussion in [1] for why this needs to be Acquire. + // + // [1] https://github.com/servo/servo/issues/21186 + self.inner().count.load(Acquire) == 1 + } +} + +impl<T: ?Sized> Drop for Arc<T> { + #[inline] + fn drop(&mut self) { + // Because `fetch_sub` is already atomic, we do not need to synchronize + // with other threads unless we are going to delete the object. + if self.inner().count.fetch_sub(1, Release) != 1 { + return; + } + + // FIXME(bholley): Use the updated comment when [2] is merged. + // + // This load is needed to prevent reordering of use of the data and + // deletion of the data. Because it is marked `Release`, the decreasing + // of the reference count synchronizes with this `Acquire` load. This + // means that use of the data happens before decreasing the reference + // count, which happens before this load, which happens before the + // deletion of the data. + // + // As explained in the [Boost documentation][1], + // + // > It is important to enforce any possible access to the object in one + // > thread (through an existing reference) to *happen before* deleting + // > the object in a different thread. This is achieved by a "release" + // > operation after dropping a reference (any access to the object + // > through this reference must obviously happened before), and an + // > "acquire" operation before deleting the object. + // + // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html) + // [2]: https://github.com/rust-lang/rust/pull/41714 + self.inner().count.load(Acquire); + + unsafe { + self.drop_slow(); + } + } +} + +impl<T: ?Sized + PartialEq> PartialEq for Arc<T> { + fn eq(&self, other: &Arc<T>) -> bool { + Self::ptr_eq(self, other) || *(*self) == *(*other) + } + + fn ne(&self, other: &Arc<T>) -> bool { + !Self::ptr_eq(self, other) && *(*self) != *(*other) + } +} + +impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> { + fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> { + (**self).partial_cmp(&**other) + } + + fn lt(&self, other: &Arc<T>) -> bool { + *(*self) < *(*other) + } + + fn le(&self, other: &Arc<T>) -> bool { + *(*self) <= *(*other) + } + + fn gt(&self, other: &Arc<T>) -> bool { + *(*self) > *(*other) + } + + fn ge(&self, other: &Arc<T>) -> bool { + *(*self) >= *(*other) + } +} + +impl<T: ?Sized + Ord> Ord for Arc<T> { + fn cmp(&self, other: &Arc<T>) -> Ordering { + (**self).cmp(&**other) + } +} + +impl<T: ?Sized + Eq> Eq for Arc<T> {} + +impl<T: ?Sized + Hash> Hash for Arc<T> { + fn hash<H: Hasher>(&self, state: &mut H) { + (**self).hash(state) + } +} + +#[derive(Debug, Eq, PartialEq, Hash, PartialOrd)] +#[repr(C)] +pub(crate) struct HeaderSlice<H, T: ?Sized> { + pub(crate) header: H, + length: usize, + slice: T, +} + +impl<H, T> HeaderSlice<H, [T]> { + pub(crate) fn slice(&self) -> &[T] { + &self.slice + } +} + +impl<H, T> Deref for HeaderSlice<H, [T; 0]> { + type Target = HeaderSlice<H, [T]>; + + fn deref(&self) -> &Self::Target { + unsafe { + let len = self.length; + let fake_slice: *const [T] = + ptr::slice_from_raw_parts(self as *const _ as *const T, len); + &*(fake_slice as *const HeaderSlice<H, [T]>) + } + } +} + +/// A "thin" `Arc` containing dynamically sized data +/// +/// This is functionally equivalent to `Arc<(H, [T])>` +/// +/// When you create an `Arc` containing a dynamically sized type +/// like `HeaderSlice<H, [T]>`, the `Arc` is represented on the stack +/// as a "fat pointer", where the length of the slice is stored +/// alongside the `Arc`'s pointer. In some situations you may wish to +/// have a thin pointer instead, perhaps for FFI compatibility +/// or space efficiency. +/// +/// Note that we use `[T; 0]` in order to have the right alignment for `T`. +/// +/// `ThinArc` solves this by storing the length in the allocation itself, +/// via `HeaderSlice`. +#[repr(transparent)] +pub(crate) struct ThinArc<H, T> { + ptr: ptr::NonNull<ArcInner<HeaderSlice<H, [T; 0]>>>, + phantom: PhantomData<(H, T)>, +} + +unsafe impl<H: Sync + Send, T: Sync + Send> Send for ThinArc<H, T> {} +unsafe impl<H: Sync + Send, T: Sync + Send> Sync for ThinArc<H, T> {} + +// Synthesize a fat pointer from a thin pointer. +fn thin_to_thick<H, T>( + thin: *mut ArcInner<HeaderSlice<H, [T; 0]>>, +) -> *mut ArcInner<HeaderSlice<H, [T]>> { + let len = unsafe { (*thin).data.length }; + let fake_slice: *mut [T] = ptr::slice_from_raw_parts_mut(thin as *mut T, len); + // Transplants metadata. + fake_slice as *mut ArcInner<HeaderSlice<H, [T]>> +} + +impl<H, T> ThinArc<H, T> { + /// Temporarily converts |self| into a bonafide Arc and exposes it to the + /// provided callback. The refcount is not modified. + #[inline] + pub(crate) fn with_arc<F, U>(&self, f: F) -> U + where + F: FnOnce(&Arc<HeaderSlice<H, [T]>>) -> U, + { + // Synthesize transient Arc, which never touches the refcount of the ArcInner. + let transient = unsafe { + ManuallyDrop::new(Arc { + p: ptr::NonNull::new_unchecked(thin_to_thick(self.ptr.as_ptr())), + phantom: PhantomData, + }) + }; + + // Expose the transient Arc to the callback, which may clone it if it wants. + let result = f(&transient); + + // Forward the result. + result + } + + /// Creates a `ThinArc` for a HeaderSlice using the given header struct and + /// iterator to generate the slice. + pub(crate) fn from_header_and_iter<I>(header: H, mut items: I) -> Self + where + I: Iterator<Item = T> + ExactSizeIterator, + { + assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST"); + + let num_items = items.len(); + + // Offset of the start of the slice in the allocation. + let inner_to_data_offset = offset_of!(ArcInner<HeaderSlice<H, [T; 0]>>, data); + let data_to_slice_offset = offset_of!(HeaderSlice<H, [T; 0]>, slice); + let slice_offset = inner_to_data_offset + data_to_slice_offset; + + // Compute the size of the real payload. + let slice_size = mem::size_of::<T>().checked_mul(num_items).expect("size overflows"); + let usable_size = slice_offset.checked_add(slice_size).expect("size overflows"); + + // Round up size to alignment. + let align = mem::align_of::<ArcInner<HeaderSlice<H, [T; 0]>>>(); + let size = usable_size.wrapping_add(align - 1) & !(align - 1); + assert!(size >= usable_size, "size overflows"); + let layout = Layout::from_size_align(size, align).expect("invalid layout"); + + let ptr: *mut ArcInner<HeaderSlice<H, [T; 0]>>; + unsafe { + let buffer = alloc::alloc(layout); + + if buffer.is_null() { + alloc::handle_alloc_error(layout); + } + + // // Synthesize the fat pointer. We do this by claiming we have a direct + // // pointer to a [T], and then changing the type of the borrow. The key + // // point here is that the length portion of the fat pointer applies + // // only to the number of elements in the dynamically-sized portion of + // // the type, so the value will be the same whether it points to a [T] + // // or something else with a [T] as its last member. + // let fake_slice: &mut [T] = slice::from_raw_parts_mut(buffer as *mut T, num_items); + // ptr = fake_slice as *mut [T] as *mut ArcInner<HeaderSlice<H, [T]>>; + ptr = buffer as *mut _; + + let count = atomic::AtomicUsize::new(1); + + // Write the data. + // + // Note that any panics here (i.e. from the iterator) are safe, since + // we'll just leak the uninitialized memory. + ptr::write(ptr::addr_of_mut!((*ptr).count), count); + ptr::write(ptr::addr_of_mut!((*ptr).data.header), header); + ptr::write(ptr::addr_of_mut!((*ptr).data.length), num_items); + if num_items != 0 { + let mut current = ptr::addr_of_mut!((*ptr).data.slice) as *mut T; + debug_assert_eq!(current as usize - buffer as usize, slice_offset); + for _ in 0..num_items { + ptr::write( + current, + items.next().expect("ExactSizeIterator over-reported length"), + ); + current = current.offset(1); + } + assert!(items.next().is_none(), "ExactSizeIterator under-reported length"); + + // We should have consumed the buffer exactly. + debug_assert_eq!(current as *mut u8, buffer.add(usable_size)); + } + assert!(items.next().is_none(), "ExactSizeIterator under-reported length"); + } + + ThinArc { ptr: unsafe { ptr::NonNull::new_unchecked(ptr) }, phantom: PhantomData } + } +} + +impl<H, T> Deref for ThinArc<H, T> { + type Target = HeaderSlice<H, [T]>; + + #[inline] + fn deref(&self) -> &Self::Target { + unsafe { &(*thin_to_thick(self.ptr.as_ptr())).data } + } +} + +impl<H, T> Clone for ThinArc<H, T> { + #[inline] + fn clone(&self) -> Self { + ThinArc::with_arc(self, |a| Arc::into_thin(a.clone())) + } +} + +impl<H, T> Drop for ThinArc<H, T> { + #[inline] + fn drop(&mut self) { + let _ = Arc::from_thin(ThinArc { ptr: self.ptr, phantom: PhantomData }); + } +} + +impl<H, T> Arc<HeaderSlice<H, [T]>> { + /// Converts an `Arc` into a `ThinArc`. This consumes the `Arc`, so the refcount + /// is not modified. + #[inline] + pub(crate) fn into_thin(a: Self) -> ThinArc<H, T> { + assert_eq!(a.length, a.slice.len(), "Length needs to be correct for ThinArc to work"); + let fat_ptr: *mut ArcInner<HeaderSlice<H, [T]>> = a.ptr(); + mem::forget(a); + let thin_ptr = fat_ptr as *mut [usize] as *mut usize; + ThinArc { + ptr: unsafe { + ptr::NonNull::new_unchecked(thin_ptr as *mut ArcInner<HeaderSlice<H, [T; 0]>>) + }, + phantom: PhantomData, + } + } + + /// Converts a `ThinArc` into an `Arc`. This consumes the `ThinArc`, so the refcount + /// is not modified. + #[inline] + pub(crate) fn from_thin(a: ThinArc<H, T>) -> Self { + let ptr = thin_to_thick(a.ptr.as_ptr()); + mem::forget(a); + unsafe { Arc { p: ptr::NonNull::new_unchecked(ptr), phantom: PhantomData } } + } +} + +impl<H: PartialEq, T: PartialEq> PartialEq for ThinArc<H, T> { + #[inline] + fn eq(&self, other: &ThinArc<H, T>) -> bool { + **self == **other + } +} + +impl<H: Eq, T: Eq> Eq for ThinArc<H, T> {} + +impl<H: Hash, T: Hash> Hash for ThinArc<H, T> { + fn hash<HSR: Hasher>(&self, state: &mut HSR) { + (**self).hash(state) + } +} diff --git a/vendor/rowan/src/ast.rs b/vendor/rowan/src/ast.rs new file mode 100644 index 000000000..ea848e08a --- /dev/null +++ b/vendor/rowan/src/ast.rs @@ -0,0 +1,206 @@ +//! Working with abstract syntax trees. +//! +//! In rowan, syntax trees are transient objects. That means that we create +//! trees when we need them, and tear them down to save memory. In this +//! architecture, hanging on to a particular syntax node for a long time is +//! ill-advisable, as that keeps the whole tree resident. +//! +//! Instead, we provide a [`SyntaxNodePtr`] type, which stores information about +//! the _location_ of a particular syntax node in a tree. It's a small type +//! which can be cheaply stored, and which can be resolved to a real +//! [`SyntaxNode`] when necessary. +//! +//! We also provide an [`AstNode`] trait for typed AST wrapper APIs over rowan +//! nodes. + +use std::{ + fmt, + hash::{Hash, Hasher}, + iter::successors, + marker::PhantomData, +}; + +use crate::{Language, SyntaxNode, SyntaxNodeChildren, TextRange}; + +/// The main trait to go from untyped [`SyntaxNode`] to a typed AST. The +/// conversion itself has zero runtime cost: AST and syntax nodes have exactly +/// the same representation: a pointer to the tree root and a pointer to the +/// node itself. +pub trait AstNode { + type Language: Language; + + fn can_cast(kind: <Self::Language as Language>::Kind) -> bool + where + Self: Sized; + + fn cast(node: SyntaxNode<Self::Language>) -> Option<Self> + where + Self: Sized; + + fn syntax(&self) -> &SyntaxNode<Self::Language>; + + fn clone_for_update(&self) -> Self + where + Self: Sized, + { + Self::cast(self.syntax().clone_for_update()).unwrap() + } + + fn clone_subtree(&self) -> Self + where + Self: Sized, + { + Self::cast(self.syntax().clone_subtree()).unwrap() + } +} + +/// A "pointer" to a [`SyntaxNode`], via location in the source code. +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct SyntaxNodePtr<L: Language> { + kind: L::Kind, + range: TextRange, +} + +impl<L: Language> SyntaxNodePtr<L> { + /// Returns a [`SyntaxNodePtr`] for the node. + pub fn new(node: &SyntaxNode<L>) -> Self { + Self { kind: node.kind(), range: node.text_range() } + } + + /// "Dereferences" the pointer to get the [`SyntaxNode`] it points to. + /// + /// Panics if node is not found, so make sure that `root` syntax tree is + /// equivalent (is build from the same text) to the tree which was + /// originally used to get this [`SyntaxNodePtr`]. + /// + /// Also panics if `root` is not actually a root (i.e. it has a parent). + /// + /// The complexity is linear in the depth of the tree and logarithmic in + /// tree width. As most trees are shallow, thinking about this as + /// `O(log(N))` in the size of the tree is not too wrong! + pub fn to_node(&self, root: &SyntaxNode<L>) -> SyntaxNode<L> { + assert!(root.parent().is_none()); + successors(Some(root.clone()), |node| { + node.child_or_token_at_range(self.range).and_then(|it| it.into_node()) + }) + .find(|it| it.text_range() == self.range && it.kind() == self.kind) + .unwrap_or_else(|| panic!("can't resolve local ptr to SyntaxNode: {:?}", self)) + } + + /// Casts this to an [`AstPtr`] to the given node type if possible. + pub fn cast<N: AstNode<Language = L>>(self) -> Option<AstPtr<N>> { + if !N::can_cast(self.kind) { + return None; + } + Some(AstPtr { raw: self }) + } + + /// Returns the kind of the syntax node this points to. + pub fn kind(&self) -> L::Kind { + self.kind + } + + /// Returns the range of the syntax node this points to. + pub fn text_range(&self) -> TextRange { + self.range + } +} + +/// Like [`SyntaxNodePtr`], but remembers the type of node. +pub struct AstPtr<N: AstNode> { + raw: SyntaxNodePtr<N::Language>, +} + +impl<N: AstNode> AstPtr<N> { + /// Returns an [`AstPtr`] for the node. + pub fn new(node: &N) -> Self { + Self { raw: SyntaxNodePtr::new(node.syntax()) } + } + + /// Given the root node containing the node `n` that `self` is a pointer to, + /// returns `n`. See [`SyntaxNodePtr::to_node`]. + pub fn to_node(&self, root: &SyntaxNode<N::Language>) -> N { + N::cast(self.raw.to_node(root)).unwrap() + } + + /// Returns the underlying [`SyntaxNodePtr`]. + pub fn syntax_node_ptr(&self) -> SyntaxNodePtr<N::Language> { + self.raw.clone() + } + + /// Casts this to an [`AstPtr`] to the given node type if possible. + pub fn cast<U: AstNode<Language = N::Language>>(self) -> Option<AstPtr<U>> { + if !U::can_cast(self.raw.kind) { + return None; + } + Some(AstPtr { raw: self.raw }) + } +} + +impl<N: AstNode> fmt::Debug for AstPtr<N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("AstPtr").field("raw", &self.raw).finish() + } +} + +impl<N: AstNode> Clone for AstPtr<N> { + fn clone(&self) -> Self { + Self { raw: self.raw.clone() } + } +} + +impl<N: AstNode> PartialEq for AstPtr<N> { + fn eq(&self, other: &AstPtr<N>) -> bool { + self.raw == other.raw + } +} + +impl<N: AstNode> Eq for AstPtr<N> {} + +impl<N: AstNode> Hash for AstPtr<N> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.raw.hash(state) + } +} + +impl<N: AstNode> From<AstPtr<N>> for SyntaxNodePtr<N::Language> { + fn from(ptr: AstPtr<N>) -> SyntaxNodePtr<N::Language> { + ptr.raw + } +} + +#[derive(Debug, Clone)] +pub struct AstChildren<N: AstNode> { + inner: SyntaxNodeChildren<N::Language>, + ph: PhantomData<N>, +} + +impl<N: AstNode> AstChildren<N> { + fn new(parent: &SyntaxNode<N::Language>) -> Self { + AstChildren { inner: parent.children(), ph: PhantomData } + } +} + +impl<N: AstNode> Iterator for AstChildren<N> { + type Item = N; + fn next(&mut self) -> Option<N> { + self.inner.find_map(N::cast) + } +} + +pub mod support { + use super::{AstChildren, AstNode}; + use crate::{Language, SyntaxNode, SyntaxToken}; + + pub fn child<N: AstNode>(parent: &SyntaxNode<N::Language>) -> Option<N> { + parent.children().find_map(N::cast) + } + + pub fn children<N: AstNode>(parent: &SyntaxNode<N::Language>) -> AstChildren<N> { + AstChildren::new(parent) + } + + pub fn token<L: Language>(parent: &SyntaxNode<L>, kind: L::Kind) -> Option<SyntaxToken<L>> { + parent.children_with_tokens().filter_map(|it| it.into_token()).find(|it| it.kind() == kind) + } +} diff --git a/vendor/rowan/src/cow_mut.rs b/vendor/rowan/src/cow_mut.rs new file mode 100644 index 000000000..c50e25b70 --- /dev/null +++ b/vendor/rowan/src/cow_mut.rs @@ -0,0 +1,30 @@ +#[derive(Debug)] +pub(crate) enum CowMut<'a, T> { + Owned(T), + Borrowed(&'a mut T), +} + +impl<T> std::ops::Deref for CowMut<'_, T> { + type Target = T; + fn deref(&self) -> &T { + match self { + CowMut::Owned(it) => it, + CowMut::Borrowed(it) => *it, + } + } +} + +impl<T> std::ops::DerefMut for CowMut<'_, T> { + fn deref_mut(&mut self) -> &mut T { + match self { + CowMut::Owned(it) => it, + CowMut::Borrowed(it) => *it, + } + } +} + +impl<T: Default> Default for CowMut<'_, T> { + fn default() -> Self { + CowMut::Owned(T::default()) + } +} diff --git a/vendor/rowan/src/cursor.rs b/vendor/rowan/src/cursor.rs new file mode 100644 index 000000000..39b0c9624 --- /dev/null +++ b/vendor/rowan/src/cursor.rs @@ -0,0 +1,1284 @@ +//! Implementation of the cursors -- API for convenient access to syntax trees. +//! +//! Functional programmers will recognize that this module implements a zipper +//! for a purely functional (green) tree. +//! +//! A cursor node (`SyntaxNode`) points to a `GreenNode` and a parent +//! `SyntaxNode`. This allows cursor to provide iteration over both ancestors +//! and descendants, as well as a cheep access to absolute offset of the node in +//! file. +//! +//! By default `SyntaxNode`s are immutable, but you can get a mutable copy of +//! the tree by calling `clone_for_update`. Mutation is based on interior +//! mutability and doesn't need `&mut`. You can have two `SyntaxNode`s pointing +//! at different parts of the same tree; mutations via the first node will be +//! reflected in the other. + +// Implementation notes: +// +// The implementation is utterly and horribly unsafe. This whole module is an +// unsafety boundary. It is believed that the API here is, in principle, sound, +// but the implementation might have bugs. +// +// The core type is `NodeData` -- a heap-allocated reference counted object, +// which points to a green node or a green token, and to the parent `NodeData`. +// Publicly-exposed `SyntaxNode` and `SyntaxToken` own a reference to +// `NodeData`. +// +// `NodeData`s are transient, and are created and destroyed during tree +// traversals. In general, only currently referenced nodes and their ancestors +// are alive at any given moment. +// +// More specifically, `NodeData`'s ref count is equal to the number of +// outstanding `SyntaxNode` and `SyntaxToken` plus the number of children with +// non-zero ref counts. For example, if the user has only a single `SyntaxNode` +// pointing somewhere in the middle of the tree, then all `NodeData` on the path +// from that point towards the root have ref count equal to one. +// +// `NodeData` which doesn't have a parent (is a root) owns the corresponding +// green node or token, and is responsible for freeing it. +// +// That's mostly it for the immutable subset of the API. Mutation is fun though, +// you'll like it! +// +// Mutability is a run-time property of a tree of `NodeData`. The whole tree is +// either mutable or immutable. `clone_for_update` clones the whole tree of +// `NodeData`s, making it mutable (note that the green tree is re-used). +// +// If the tree is mutable, then all live `NodeData` are additionally liked to +// each other via intrusive liked lists. Specifically, there are two pointers to +// siblings, as well as a pointer to the first child. Note that only live nodes +// are considered. If the user only has `SyntaxNode`s for the first and last +// children of some particular node, then their `NodeData` will point at each +// other. +// +// The links are used to propagate mutations across the tree. Specifically, each +// `NodeData` remembers it's index in parent. When the node is detached from or +// attached to the tree, we need to adjust the indices of all subsequent +// siblings. That's what makes the `for c in node.children() { c.detach() }` +// pattern work despite the apparent iterator invalidation. +// +// This code is encapsulated into the sorted linked list (`sll`) module. +// +// The actual mutation consist of functionally "mutating" (creating a +// structurally shared copy) the green node, and then re-spinning the tree. This +// is a delicate process: `NodeData` point directly to the green nodes, so we +// must make sure that those nodes don't move. Additionally, during mutation a +// node might become or might stop being a root, so we must take care to not +// double free / leak its green node. +// +// Because we can change green nodes using only shared references, handing out +// references into green nodes in the public API would be unsound. We don't do +// that, but we do use such references internally a lot. Additionally, for +// tokens the underlying green token actually is immutable, so we can, and do +// return `&str`. +// +// Invariants [must not leak outside of the module]: +// - Mutability is the property of the whole tree. Intermixing elements that +// differ in mutability is not allowed. +// - Mutability property is persistent. +// - References to the green elements' data are not exposed into public API +// when the tree is mutable. +// - TBD + +use std::{ + borrow::Cow, + cell::Cell, + fmt, + hash::{Hash, Hasher}, + iter, + mem::{self, ManuallyDrop}, + ops::Range, + ptr, slice, +}; + +use countme::Count; + +use crate::{ + green::{GreenChild, GreenElementRef, GreenNodeData, GreenTokenData, SyntaxKind}, + sll, + utility_types::Delta, + Direction, GreenNode, GreenToken, NodeOrToken, SyntaxText, TextRange, TextSize, TokenAtOffset, + WalkEvent, +}; + +enum Green { + Node { ptr: Cell<ptr::NonNull<GreenNodeData>> }, + Token { ptr: ptr::NonNull<GreenTokenData> }, +} + +struct _SyntaxElement; + +struct NodeData { + _c: Count<_SyntaxElement>, + + rc: Cell<u32>, + parent: Cell<Option<ptr::NonNull<NodeData>>>, + index: Cell<u32>, + green: Green, + + /// Invariant: never changes after NodeData is created. + mutable: bool, + /// Absolute offset for immutable nodes, unused for mutable nodes. + offset: TextSize, + // The following links only have meaning when `mutable` is true. + first: Cell<*const NodeData>, + /// Invariant: never null if mutable. + next: Cell<*const NodeData>, + /// Invariant: never null if mutable. + prev: Cell<*const NodeData>, +} + +unsafe impl sll::Elem for NodeData { + fn prev(&self) -> &Cell<*const Self> { + &self.prev + } + fn next(&self) -> &Cell<*const Self> { + &self.next + } + fn key(&self) -> &Cell<u32> { + &self.index + } +} + +pub type SyntaxElement = NodeOrToken<SyntaxNode, SyntaxToken>; + +pub struct SyntaxNode { + ptr: ptr::NonNull<NodeData>, +} + +impl Clone for SyntaxNode { + #[inline] + fn clone(&self) -> Self { + self.data().inc_rc(); + SyntaxNode { ptr: self.ptr } + } +} + +impl Drop for SyntaxNode { + #[inline] + fn drop(&mut self) { + if self.data().dec_rc() { + unsafe { free(self.ptr) } + } + } +} + +#[derive(Debug)] +pub struct SyntaxToken { + ptr: ptr::NonNull<NodeData>, +} + +impl Clone for SyntaxToken { + #[inline] + fn clone(&self) -> Self { + self.data().inc_rc(); + SyntaxToken { ptr: self.ptr } + } +} + +impl Drop for SyntaxToken { + #[inline] + fn drop(&mut self) { + if self.data().dec_rc() { + unsafe { free(self.ptr) } + } + } +} + +#[inline(never)] +unsafe fn free(mut data: ptr::NonNull<NodeData>) { + loop { + debug_assert_eq!(data.as_ref().rc.get(), 0); + debug_assert!(data.as_ref().first.get().is_null()); + let node = Box::from_raw(data.as_ptr()); + match node.parent.take() { + Some(parent) => { + debug_assert!(parent.as_ref().rc.get() > 0); + if node.mutable { + sll::unlink(&parent.as_ref().first, &*node) + } + if parent.as_ref().dec_rc() { + data = parent; + } else { + break; + } + } + None => { + match &node.green { + Green::Node { ptr } => { + let _ = GreenNode::from_raw(ptr.get()); + } + Green::Token { ptr } => { + let _ = GreenToken::from_raw(*ptr); + } + } + break; + } + } + } +} + +impl NodeData { + #[inline] + fn new( + parent: Option<SyntaxNode>, + index: u32, + offset: TextSize, + green: Green, + mutable: bool, + ) -> ptr::NonNull<NodeData> { + let parent = ManuallyDrop::new(parent); + let res = NodeData { + _c: Count::new(), + rc: Cell::new(1), + parent: Cell::new(parent.as_ref().map(|it| it.ptr)), + index: Cell::new(index), + green, + + mutable, + offset, + first: Cell::new(ptr::null()), + next: Cell::new(ptr::null()), + prev: Cell::new(ptr::null()), + }; + unsafe { + if mutable { + let res_ptr: *const NodeData = &res; + match sll::init((*res_ptr).parent().map(|it| &it.first), res_ptr.as_ref().unwrap()) + { + sll::AddToSllResult::AlreadyInSll(node) => { + if cfg!(debug_assertions) { + assert_eq!((*node).index(), (*res_ptr).index()); + match ((*node).green(), (*res_ptr).green()) { + (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => { + assert!(ptr::eq(lhs, rhs)) + } + (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => { + assert!(ptr::eq(lhs, rhs)) + } + it => { + panic!("node/token confusion: {:?}", it) + } + } + } + + ManuallyDrop::into_inner(parent); + let res = node as *mut NodeData; + (*res).inc_rc(); + return ptr::NonNull::new_unchecked(res); + } + it => { + let res = Box::into_raw(Box::new(res)); + it.add_to_sll(res); + return ptr::NonNull::new_unchecked(res); + } + } + } + ptr::NonNull::new_unchecked(Box::into_raw(Box::new(res))) + } + } + + #[inline] + fn inc_rc(&self) { + let rc = match self.rc.get().checked_add(1) { + Some(it) => it, + None => std::process::abort(), + }; + self.rc.set(rc) + } + + #[inline] + fn dec_rc(&self) -> bool { + let rc = self.rc.get() - 1; + self.rc.set(rc); + rc == 0 + } + + #[inline] + fn key(&self) -> (ptr::NonNull<()>, TextSize) { + let ptr = match &self.green { + Green::Node { ptr } => ptr.get().cast(), + Green::Token { ptr } => ptr.cast(), + }; + (ptr, self.offset()) + } + + #[inline] + fn parent_node(&self) -> Option<SyntaxNode> { + let parent = self.parent()?; + debug_assert!(matches!(parent.green, Green::Node { .. })); + parent.inc_rc(); + Some(SyntaxNode { ptr: ptr::NonNull::from(parent) }) + } + + #[inline] + fn parent(&self) -> Option<&NodeData> { + self.parent.get().map(|it| unsafe { &*it.as_ptr() }) + } + + #[inline] + fn green(&self) -> GreenElementRef<'_> { + match &self.green { + Green::Node { ptr } => GreenElementRef::Node(unsafe { &*ptr.get().as_ptr() }), + Green::Token { ptr } => GreenElementRef::Token(unsafe { &*ptr.as_ref() }), + } + } + #[inline] + fn green_siblings(&self) -> slice::Iter<GreenChild> { + match &self.parent().map(|it| &it.green) { + Some(Green::Node { ptr }) => unsafe { &*ptr.get().as_ptr() }.children().raw, + Some(Green::Token { .. }) => { + debug_assert!(false); + [].iter() + } + None => [].iter(), + } + } + #[inline] + fn index(&self) -> u32 { + self.index.get() + } + + #[inline] + fn offset(&self) -> TextSize { + if self.mutable { + self.offset_mut() + } else { + self.offset + } + } + + #[cold] + fn offset_mut(&self) -> TextSize { + let mut res = TextSize::from(0); + + let mut node = self; + while let Some(parent) = node.parent() { + let green = parent.green().into_node().unwrap(); + res += green.children().raw.nth(node.index() as usize).unwrap().rel_offset(); + node = parent; + } + + res + } + + #[inline] + fn text_range(&self) -> TextRange { + let offset = self.offset(); + let len = self.green().text_len(); + TextRange::at(offset, len) + } + + #[inline] + fn kind(&self) -> SyntaxKind { + self.green().kind() + } + + fn next_sibling(&self) -> Option<SyntaxNode> { + let mut siblings = self.green_siblings().enumerate(); + let index = self.index() as usize; + + siblings.nth(index); + siblings.find_map(|(index, child)| { + child.as_ref().into_node().and_then(|green| { + let parent = self.parent_node()?; + let offset = parent.offset() + child.rel_offset(); + Some(SyntaxNode::new_child(green, parent, index as u32, offset)) + }) + }) + } + fn prev_sibling(&self) -> Option<SyntaxNode> { + let mut rev_siblings = self.green_siblings().enumerate().rev(); + let index = rev_siblings.len() - (self.index() as usize); + + rev_siblings.nth(index); + rev_siblings.find_map(|(index, child)| { + child.as_ref().into_node().and_then(|green| { + let parent = self.parent_node()?; + let offset = parent.offset() + child.rel_offset(); + Some(SyntaxNode::new_child(green, parent, index as u32, offset)) + }) + }) + } + + fn next_sibling_or_token(&self) -> Option<SyntaxElement> { + let mut siblings = self.green_siblings().enumerate(); + let index = self.index() as usize + 1; + + siblings.nth(index).and_then(|(index, child)| { + let parent = self.parent_node()?; + let offset = parent.offset() + child.rel_offset(); + Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset)) + }) + } + fn prev_sibling_or_token(&self) -> Option<SyntaxElement> { + let mut siblings = self.green_siblings().enumerate(); + let index = self.index().checked_sub(1)? as usize; + + siblings.nth(index).and_then(|(index, child)| { + let parent = self.parent_node()?; + let offset = parent.offset() + child.rel_offset(); + Some(SyntaxElement::new(child.as_ref(), parent, index as u32, offset)) + }) + } + + fn detach(&self) { + assert!(self.mutable); + assert!(self.rc.get() > 0); + let parent_ptr = match self.parent.take() { + Some(parent) => parent, + None => return, + }; + + unsafe { + sll::adjust(self, self.index() + 1, Delta::Sub(1)); + let parent = parent_ptr.as_ref(); + sll::unlink(&parent.first, self); + + // Add strong ref to green + match self.green().to_owned() { + NodeOrToken::Node(it) => { + GreenNode::into_raw(it); + } + NodeOrToken::Token(it) => { + GreenToken::into_raw(it); + } + } + + match parent.green() { + NodeOrToken::Node(green) => { + let green = green.remove_child(self.index() as usize); + parent.respine(green) + } + NodeOrToken::Token(_) => unreachable!(), + } + + if parent.dec_rc() { + free(parent_ptr) + } + } + } + fn attach_child(&self, index: usize, child: &NodeData) { + assert!(self.mutable && child.mutable && child.parent().is_none()); + assert!(self.rc.get() > 0 && child.rc.get() > 0); + + unsafe { + child.index.set(index as u32); + child.parent.set(Some(self.into())); + self.inc_rc(); + + if !self.first.get().is_null() { + sll::adjust(&*self.first.get(), index as u32, Delta::Add(1)); + } + + match sll::link(&self.first, child) { + sll::AddToSllResult::AlreadyInSll(_) => { + panic!("Child already in sorted linked list") + } + it => it.add_to_sll(child), + } + + match self.green() { + NodeOrToken::Node(green) => { + // Child is root, so it ownes the green node. Steal it! + let child_green = match &child.green { + Green::Node { ptr } => GreenNode::from_raw(ptr.get()).into(), + Green::Token { ptr } => GreenToken::from_raw(*ptr).into(), + }; + + let green = green.insert_child(index, child_green); + self.respine(green); + } + NodeOrToken::Token(_) => unreachable!(), + } + } + } + unsafe fn respine(&self, mut new_green: GreenNode) { + let mut node = self; + loop { + let old_green = match &node.green { + Green::Node { ptr } => ptr.replace(ptr::NonNull::from(&*new_green)), + Green::Token { .. } => unreachable!(), + }; + match node.parent() { + Some(parent) => match parent.green() { + NodeOrToken::Node(parent_green) => { + new_green = + parent_green.replace_child(node.index() as usize, new_green.into()); + node = parent; + } + _ => unreachable!(), + }, + None => { + mem::forget(new_green); + let _ = GreenNode::from_raw(old_green); + break; + } + } + } + } +} + +impl SyntaxNode { + pub fn new_root(green: GreenNode) -> SyntaxNode { + let green = GreenNode::into_raw(green); + let green = Green::Node { ptr: Cell::new(green) }; + SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, false) } + } + + pub fn new_root_mut(green: GreenNode) -> SyntaxNode { + let green = GreenNode::into_raw(green); + let green = Green::Node { ptr: Cell::new(green) }; + SyntaxNode { ptr: NodeData::new(None, 0, 0.into(), green, true) } + } + + fn new_child( + green: &GreenNodeData, + parent: SyntaxNode, + index: u32, + offset: TextSize, + ) -> SyntaxNode { + let mutable = parent.data().mutable; + let green = Green::Node { ptr: Cell::new(green.into()) }; + SyntaxNode { ptr: NodeData::new(Some(parent), index, offset, green, mutable) } + } + + pub fn clone_for_update(&self) -> SyntaxNode { + assert!(!self.data().mutable); + match self.parent() { + Some(parent) => { + let parent = parent.clone_for_update(); + SyntaxNode::new_child(self.green_ref(), parent, self.data().index(), self.offset()) + } + None => SyntaxNode::new_root_mut(self.green_ref().to_owned()), + } + } + + pub fn clone_subtree(&self) -> SyntaxNode { + SyntaxNode::new_root(self.green().into()) + } + + #[inline] + fn data(&self) -> &NodeData { + unsafe { self.ptr.as_ref() } + } + + pub fn replace_with(&self, replacement: GreenNode) -> GreenNode { + assert_eq!(self.kind(), replacement.kind()); + match &self.parent() { + None => replacement, + Some(parent) => { + let new_parent = parent + .green_ref() + .replace_child(self.data().index() as usize, replacement.into()); + parent.replace_with(new_parent) + } + } + } + + #[inline] + pub fn kind(&self) -> SyntaxKind { + self.data().kind() + } + + #[inline] + fn offset(&self) -> TextSize { + self.data().offset() + } + + #[inline] + pub fn text_range(&self) -> TextRange { + self.data().text_range() + } + + #[inline] + pub fn index(&self) -> usize { + self.data().index() as usize + } + + #[inline] + pub fn text(&self) -> SyntaxText { + SyntaxText::new(self.clone()) + } + + #[inline] + pub fn green(&self) -> Cow<'_, GreenNodeData> { + let green_ref = self.green_ref(); + match self.data().mutable { + false => Cow::Borrowed(green_ref), + true => Cow::Owned(green_ref.to_owned()), + } + } + #[inline] + fn green_ref(&self) -> &GreenNodeData { + self.data().green().into_node().unwrap() + } + + #[inline] + pub fn parent(&self) -> Option<SyntaxNode> { + self.data().parent_node() + } + + #[inline] + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> { + iter::successors(Some(self.clone()), SyntaxNode::parent) + } + + #[inline] + pub fn children(&self) -> SyntaxNodeChildren { + SyntaxNodeChildren::new(self.clone()) + } + + #[inline] + pub fn children_with_tokens(&self) -> SyntaxElementChildren { + SyntaxElementChildren::new(self.clone()) + } + + pub fn first_child(&self) -> Option<SyntaxNode> { + self.green_ref().children().raw.enumerate().find_map(|(index, child)| { + child.as_ref().into_node().map(|green| { + SyntaxNode::new_child( + green, + self.clone(), + index as u32, + self.offset() + child.rel_offset(), + ) + }) + }) + } + pub fn last_child(&self) -> Option<SyntaxNode> { + self.green_ref().children().raw.enumerate().rev().find_map(|(index, child)| { + child.as_ref().into_node().map(|green| { + SyntaxNode::new_child( + green, + self.clone(), + index as u32, + self.offset() + child.rel_offset(), + ) + }) + }) + } + + pub fn first_child_or_token(&self) -> Option<SyntaxElement> { + self.green_ref().children().raw.next().map(|child| { + SyntaxElement::new(child.as_ref(), self.clone(), 0, self.offset() + child.rel_offset()) + }) + } + pub fn last_child_or_token(&self) -> Option<SyntaxElement> { + self.green_ref().children().raw.enumerate().next_back().map(|(index, child)| { + SyntaxElement::new( + child.as_ref(), + self.clone(), + index as u32, + self.offset() + child.rel_offset(), + ) + }) + } + + pub fn next_sibling(&self) -> Option<SyntaxNode> { + self.data().next_sibling() + } + pub fn prev_sibling(&self) -> Option<SyntaxNode> { + self.data().prev_sibling() + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> { + self.data().next_sibling_or_token() + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> { + self.data().prev_sibling_or_token() + } + + pub fn first_token(&self) -> Option<SyntaxToken> { + self.first_child_or_token()?.first_token() + } + pub fn last_token(&self) -> Option<SyntaxToken> { + self.last_child_or_token()?.last_token() + } + + #[inline] + pub fn siblings(&self, direction: Direction) -> impl Iterator<Item = SyntaxNode> { + iter::successors(Some(self.clone()), move |node| match direction { + Direction::Next => node.next_sibling(), + Direction::Prev => node.prev_sibling(), + }) + } + + #[inline] + pub fn siblings_with_tokens( + &self, + direction: Direction, + ) -> impl Iterator<Item = SyntaxElement> { + let me: SyntaxElement = self.clone().into(); + iter::successors(Some(me), move |el| match direction { + Direction::Next => el.next_sibling_or_token(), + Direction::Prev => el.prev_sibling_or_token(), + }) + } + + #[inline] + pub fn descendants(&self) -> impl Iterator<Item = SyntaxNode> { + self.preorder().filter_map(|event| match event { + WalkEvent::Enter(node) => Some(node), + WalkEvent::Leave(_) => None, + }) + } + + #[inline] + pub fn descendants_with_tokens(&self) -> impl Iterator<Item = SyntaxElement> { + self.preorder_with_tokens().filter_map(|event| match event { + WalkEvent::Enter(it) => Some(it), + WalkEvent::Leave(_) => None, + }) + } + + #[inline] + pub fn preorder(&self) -> Preorder { + Preorder::new(self.clone()) + } + + #[inline] + pub fn preorder_with_tokens(&self) -> PreorderWithTokens { + PreorderWithTokens::new(self.clone()) + } + + pub fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> { + // TODO: this could be faster if we first drill-down to node, and only + // then switch to token search. We should also replace explicit + // recursion with a loop. + let range = self.text_range(); + assert!( + range.start() <= offset && offset <= range.end(), + "Bad offset: range {:?} offset {:?}", + range, + offset + ); + if range.is_empty() { + return TokenAtOffset::None; + } + + let mut children = self.children_with_tokens().filter(|child| { + let child_range = child.text_range(); + !child_range.is_empty() + && (child_range.start() <= offset && offset <= child_range.end()) + }); + + let left = children.next().unwrap(); + let right = children.next(); + assert!(children.next().is_none()); + + if let Some(right) = right { + match (left.token_at_offset(offset), right.token_at_offset(offset)) { + (TokenAtOffset::Single(left), TokenAtOffset::Single(right)) => { + TokenAtOffset::Between(left, right) + } + _ => unreachable!(), + } + } else { + left.token_at_offset(offset) + } + } + + pub fn covering_element(&self, range: TextRange) -> SyntaxElement { + let mut res: SyntaxElement = self.clone().into(); + loop { + assert!( + res.text_range().contains_range(range), + "Bad range: node range {:?}, range {:?}", + res.text_range(), + range, + ); + res = match &res { + NodeOrToken::Token(_) => return res, + NodeOrToken::Node(node) => match node.child_or_token_at_range(range) { + Some(it) => it, + None => return res, + }, + }; + } + } + + pub fn child_or_token_at_range(&self, range: TextRange) -> Option<SyntaxElement> { + let rel_range = range - self.offset(); + self.green_ref().child_at_range(rel_range).map(|(index, rel_offset, green)| { + SyntaxElement::new(green, self.clone(), index as u32, self.offset() + rel_offset) + }) + } + + pub fn splice_children(&self, to_delete: Range<usize>, to_insert: Vec<SyntaxElement>) { + assert!(self.data().mutable, "immutable tree: {}", self); + for (i, child) in self.children_with_tokens().enumerate() { + if to_delete.contains(&i) { + child.detach(); + } + } + let mut index = to_delete.start; + for child in to_insert { + self.attach_child(index, child); + index += 1; + } + } + + pub fn detach(&self) { + assert!(self.data().mutable, "immutable tree: {}", self); + self.data().detach() + } + + fn attach_child(&self, index: usize, child: SyntaxElement) { + assert!(self.data().mutable, "immutable tree: {}", self); + child.detach(); + let data = match &child { + NodeOrToken::Node(it) => it.data(), + NodeOrToken::Token(it) => it.data(), + }; + self.data().attach_child(index, data) + } +} + +impl SyntaxToken { + fn new( + green: &GreenTokenData, + parent: SyntaxNode, + index: u32, + offset: TextSize, + ) -> SyntaxToken { + let mutable = parent.data().mutable; + let green = Green::Token { ptr: green.into() }; + SyntaxToken { ptr: NodeData::new(Some(parent), index, offset, green, mutable) } + } + + #[inline] + fn data(&self) -> &NodeData { + unsafe { self.ptr.as_ref() } + } + + pub fn replace_with(&self, replacement: GreenToken) -> GreenNode { + assert_eq!(self.kind(), replacement.kind()); + let parent = self.parent().unwrap(); + let me: u32 = self.data().index(); + + let new_parent = parent.green_ref().replace_child(me as usize, replacement.into()); + parent.replace_with(new_parent) + } + + #[inline] + pub fn kind(&self) -> SyntaxKind { + self.data().kind() + } + + #[inline] + pub fn text_range(&self) -> TextRange { + self.data().text_range() + } + + #[inline] + pub fn index(&self) -> usize { + self.data().index() as usize + } + + #[inline] + pub fn text(&self) -> &str { + match self.data().green().as_token() { + Some(it) => it.text(), + None => { + debug_assert!( + false, + "corrupted tree: a node thinks it is a token: {:?}", + self.data().green().as_node().unwrap().to_string() + ); + "" + } + } + } + + #[inline] + pub fn green(&self) -> &GreenTokenData { + self.data().green().into_token().unwrap() + } + + #[inline] + pub fn parent(&self) -> Option<SyntaxNode> { + self.data().parent_node() + } + + #[inline] + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> { + std::iter::successors(self.parent(), SyntaxNode::parent) + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> { + self.data().next_sibling_or_token() + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> { + self.data().prev_sibling_or_token() + } + + #[inline] + pub fn siblings_with_tokens( + &self, + direction: Direction, + ) -> impl Iterator<Item = SyntaxElement> { + let me: SyntaxElement = self.clone().into(); + iter::successors(Some(me), move |el| match direction { + Direction::Next => el.next_sibling_or_token(), + Direction::Prev => el.prev_sibling_or_token(), + }) + } + + pub fn next_token(&self) -> Option<SyntaxToken> { + match self.next_sibling_or_token() { + Some(element) => element.first_token(), + None => self + .ancestors() + .find_map(|it| it.next_sibling_or_token()) + .and_then(|element| element.first_token()), + } + } + pub fn prev_token(&self) -> Option<SyntaxToken> { + match self.prev_sibling_or_token() { + Some(element) => element.last_token(), + None => self + .ancestors() + .find_map(|it| it.prev_sibling_or_token()) + .and_then(|element| element.last_token()), + } + } + + pub fn detach(&self) { + assert!(self.data().mutable, "immutable tree: {}", self); + self.data().detach() + } +} + +impl SyntaxElement { + fn new( + element: GreenElementRef<'_>, + parent: SyntaxNode, + index: u32, + offset: TextSize, + ) -> SyntaxElement { + match element { + NodeOrToken::Node(node) => { + SyntaxNode::new_child(node, parent, index as u32, offset).into() + } + NodeOrToken::Token(token) => { + SyntaxToken::new(token, parent, index as u32, offset).into() + } + } + } + + #[inline] + pub fn text_range(&self) -> TextRange { + match self { + NodeOrToken::Node(it) => it.text_range(), + NodeOrToken::Token(it) => it.text_range(), + } + } + + #[inline] + pub fn index(&self) -> usize { + match self { + NodeOrToken::Node(it) => it.index(), + NodeOrToken::Token(it) => it.index(), + } + } + + #[inline] + pub fn kind(&self) -> SyntaxKind { + match self { + NodeOrToken::Node(it) => it.kind(), + NodeOrToken::Token(it) => it.kind(), + } + } + + #[inline] + pub fn parent(&self) -> Option<SyntaxNode> { + match self { + NodeOrToken::Node(it) => it.parent(), + NodeOrToken::Token(it) => it.parent(), + } + } + + #[inline] + pub fn ancestors(&self) -> impl Iterator<Item = SyntaxNode> { + let first = match self { + NodeOrToken::Node(it) => Some(it.clone()), + NodeOrToken::Token(it) => it.parent(), + }; + iter::successors(first, SyntaxNode::parent) + } + + pub fn first_token(&self) -> Option<SyntaxToken> { + match self { + NodeOrToken::Node(it) => it.first_token(), + NodeOrToken::Token(it) => Some(it.clone()), + } + } + pub fn last_token(&self) -> Option<SyntaxToken> { + match self { + NodeOrToken::Node(it) => it.last_token(), + NodeOrToken::Token(it) => Some(it.clone()), + } + } + + pub fn next_sibling_or_token(&self) -> Option<SyntaxElement> { + match self { + NodeOrToken::Node(it) => it.next_sibling_or_token(), + NodeOrToken::Token(it) => it.next_sibling_or_token(), + } + } + pub fn prev_sibling_or_token(&self) -> Option<SyntaxElement> { + match self { + NodeOrToken::Node(it) => it.prev_sibling_or_token(), + NodeOrToken::Token(it) => it.prev_sibling_or_token(), + } + } + + fn token_at_offset(&self, offset: TextSize) -> TokenAtOffset<SyntaxToken> { + assert!(self.text_range().start() <= offset && offset <= self.text_range().end()); + match self { + NodeOrToken::Token(token) => TokenAtOffset::Single(token.clone()), + NodeOrToken::Node(node) => node.token_at_offset(offset), + } + } + + pub fn detach(&self) { + match self { + NodeOrToken::Node(it) => it.detach(), + NodeOrToken::Token(it) => it.detach(), + } + } +} + +// region: impls + +// Identity semantics for hash & eq +impl PartialEq for SyntaxNode { + #[inline] + fn eq(&self, other: &SyntaxNode) -> bool { + self.data().key() == other.data().key() + } +} + +impl Eq for SyntaxNode {} + +impl Hash for SyntaxNode { + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + self.data().key().hash(state); + } +} + +impl fmt::Debug for SyntaxNode { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("SyntaxNode") + .field("kind", &self.kind()) + .field("text_range", &self.text_range()) + .finish() + } +} + +impl fmt::Display for SyntaxNode { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.preorder_with_tokens() + .filter_map(|event| match event { + WalkEvent::Enter(NodeOrToken::Token(token)) => Some(token), + _ => None, + }) + .try_for_each(|it| fmt::Display::fmt(&it, f)) + } +} + +// Identity semantics for hash & eq +impl PartialEq for SyntaxToken { + #[inline] + fn eq(&self, other: &SyntaxToken) -> bool { + self.data().key() == other.data().key() + } +} + +impl Eq for SyntaxToken {} + +impl Hash for SyntaxToken { + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + self.data().key().hash(state); + } +} + +impl fmt::Display for SyntaxToken { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(self.text(), f) + } +} + +impl From<SyntaxNode> for SyntaxElement { + #[inline] + fn from(node: SyntaxNode) -> SyntaxElement { + NodeOrToken::Node(node) + } +} + +impl From<SyntaxToken> for SyntaxElement { + #[inline] + fn from(token: SyntaxToken) -> SyntaxElement { + NodeOrToken::Token(token) + } +} + +// endregion + +// region: iterators + +#[derive(Clone, Debug)] +pub struct SyntaxNodeChildren { + next: Option<SyntaxNode>, +} + +impl SyntaxNodeChildren { + fn new(parent: SyntaxNode) -> SyntaxNodeChildren { + SyntaxNodeChildren { next: parent.first_child() } + } +} + +impl Iterator for SyntaxNodeChildren { + type Item = SyntaxNode; + fn next(&mut self) -> Option<SyntaxNode> { + self.next.take().map(|next| { + self.next = next.next_sibling(); + next + }) + } +} + +#[derive(Clone, Debug)] +pub struct SyntaxElementChildren { + next: Option<SyntaxElement>, +} + +impl SyntaxElementChildren { + fn new(parent: SyntaxNode) -> SyntaxElementChildren { + SyntaxElementChildren { next: parent.first_child_or_token() } + } +} + +impl Iterator for SyntaxElementChildren { + type Item = SyntaxElement; + fn next(&mut self) -> Option<SyntaxElement> { + self.next.take().map(|next| { + self.next = next.next_sibling_or_token(); + next + }) + } +} + +pub struct Preorder { + start: SyntaxNode, + next: Option<WalkEvent<SyntaxNode>>, + skip_subtree: bool, +} + +impl Preorder { + fn new(start: SyntaxNode) -> Preorder { + let next = Some(WalkEvent::Enter(start.clone())); + Preorder { start, next, skip_subtree: false } + } + + pub fn skip_subtree(&mut self) { + self.skip_subtree = true; + } + + #[cold] + fn do_skip(&mut self) { + self.next = self.next.take().map(|next| match next { + WalkEvent::Enter(first_child) => WalkEvent::Leave(first_child.parent().unwrap()), + WalkEvent::Leave(parent) => WalkEvent::Leave(parent), + }) + } +} + +impl Iterator for Preorder { + type Item = WalkEvent<SyntaxNode>; + + fn next(&mut self) -> Option<WalkEvent<SyntaxNode>> { + if self.skip_subtree { + self.do_skip(); + self.skip_subtree = false; + } + let next = self.next.take(); + self.next = next.as_ref().and_then(|next| { + Some(match next { + WalkEvent::Enter(node) => match node.first_child() { + Some(child) => WalkEvent::Enter(child), + None => WalkEvent::Leave(node.clone()), + }, + WalkEvent::Leave(node) => { + if node == &self.start { + return None; + } + match node.next_sibling() { + Some(sibling) => WalkEvent::Enter(sibling), + None => WalkEvent::Leave(node.parent()?), + } + } + }) + }); + next + } +} + +pub struct PreorderWithTokens { + start: SyntaxElement, + next: Option<WalkEvent<SyntaxElement>>, + skip_subtree: bool, +} + +impl PreorderWithTokens { + fn new(start: SyntaxNode) -> PreorderWithTokens { + let next = Some(WalkEvent::Enter(start.clone().into())); + PreorderWithTokens { start: start.into(), next, skip_subtree: false } + } + + pub fn skip_subtree(&mut self) { + self.skip_subtree = true; + } + + #[cold] + fn do_skip(&mut self) { + self.next = self.next.take().map(|next| match next { + WalkEvent::Enter(first_child) => WalkEvent::Leave(first_child.parent().unwrap().into()), + WalkEvent::Leave(parent) => WalkEvent::Leave(parent), + }) + } +} + +impl Iterator for PreorderWithTokens { + type Item = WalkEvent<SyntaxElement>; + + fn next(&mut self) -> Option<WalkEvent<SyntaxElement>> { + if self.skip_subtree { + self.do_skip(); + self.skip_subtree = false; + } + let next = self.next.take(); + self.next = next.as_ref().and_then(|next| { + Some(match next { + WalkEvent::Enter(el) => match el { + NodeOrToken::Node(node) => match node.first_child_or_token() { + Some(child) => WalkEvent::Enter(child), + None => WalkEvent::Leave(node.clone().into()), + }, + NodeOrToken::Token(token) => WalkEvent::Leave(token.clone().into()), + }, + WalkEvent::Leave(el) if el == &self.start => return None, + WalkEvent::Leave(el) => match el.next_sibling_or_token() { + Some(sibling) => WalkEvent::Enter(sibling), + None => WalkEvent::Leave(el.parent()?.into()), + }, + }) + }); + next + } +} +// endregion diff --git a/vendor/rowan/src/green.rs b/vendor/rowan/src/green.rs new file mode 100644 index 000000000..e2b5b4a4e --- /dev/null +++ b/vendor/rowan/src/green.rs @@ -0,0 +1,42 @@ +mod node; +mod token; +mod element; +mod builder; +mod node_cache; + +use self::element::GreenElement; + +pub(crate) use self::{element::GreenElementRef, node::GreenChild}; + +pub use self::{ + builder::{Checkpoint, GreenNodeBuilder}, + node::{Children, GreenNode, GreenNodeData}, + node_cache::NodeCache, + token::{GreenToken, GreenTokenData}, +}; + +/// SyntaxKind is a type tag for each token or node. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct SyntaxKind(pub u16); + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn assert_send_sync() { + fn f<T: Send + Sync>() {} + f::<GreenNode>(); + f::<GreenToken>(); + f::<GreenElement>(); + } + + #[test] + fn test_size_of() { + use std::mem::size_of; + + eprintln!("GreenNode {}", size_of::<GreenNode>()); + eprintln!("GreenToken {}", size_of::<GreenToken>()); + eprintln!("GreenElement {}", size_of::<GreenElement>()); + } +} diff --git a/vendor/rowan/src/green/builder.rs b/vendor/rowan/src/green/builder.rs new file mode 100644 index 000000000..1dbc8bb08 --- /dev/null +++ b/vendor/rowan/src/green/builder.rs @@ -0,0 +1,119 @@ +use crate::{ + cow_mut::CowMut, + green::{node_cache::NodeCache, GreenElement, GreenNode, SyntaxKind}, + NodeOrToken, +}; + +/// A checkpoint for maybe wrapping a node. See `GreenNodeBuilder::checkpoint` for details. +#[derive(Clone, Copy, Debug)] +pub struct Checkpoint(usize); + +/// A builder for a green tree. +#[derive(Default, Debug)] +pub struct GreenNodeBuilder<'cache> { + cache: CowMut<'cache, NodeCache>, + parents: Vec<(SyntaxKind, usize)>, + children: Vec<(u64, GreenElement)>, +} + +impl GreenNodeBuilder<'_> { + /// Creates new builder. + pub fn new() -> GreenNodeBuilder<'static> { + GreenNodeBuilder::default() + } + + /// Reusing `NodeCache` between different `GreenNodeBuilder`s saves memory. + /// It allows to structurally share underlying trees. + pub fn with_cache(cache: &mut NodeCache) -> GreenNodeBuilder<'_> { + GreenNodeBuilder { + cache: CowMut::Borrowed(cache), + parents: Vec::new(), + children: Vec::new(), + } + } + + /// Adds new token to the current branch. + #[inline] + pub fn token(&mut self, kind: SyntaxKind, text: &str) { + let (hash, token) = self.cache.token(kind, text); + self.children.push((hash, token.into())); + } + + /// Start new node and make it current. + #[inline] + pub fn start_node(&mut self, kind: SyntaxKind) { + let len = self.children.len(); + self.parents.push((kind, len)); + } + + /// Finish current branch and restore previous + /// branch as current. + #[inline] + pub fn finish_node(&mut self) { + let (kind, first_child) = self.parents.pop().unwrap(); + let (hash, node) = self.cache.node(kind, &mut self.children, first_child); + self.children.push((hash, node.into())); + } + + /// Prepare for maybe wrapping the next node. + /// The way wrapping works is that you first of all get a checkpoint, + /// then you place all tokens you want to wrap, and then *maybe* call + /// `start_node_at`. + /// Example: + /// ```rust + /// # use rowan::{GreenNodeBuilder, SyntaxKind}; + /// # const PLUS: SyntaxKind = SyntaxKind(0); + /// # const OPERATION: SyntaxKind = SyntaxKind(1); + /// # struct Parser; + /// # impl Parser { + /// # fn peek(&self) -> Option<SyntaxKind> { None } + /// # fn parse_expr(&mut self) {} + /// # } + /// # let mut builder = GreenNodeBuilder::new(); + /// # let mut parser = Parser; + /// let checkpoint = builder.checkpoint(); + /// parser.parse_expr(); + /// if parser.peek() == Some(PLUS) { + /// // 1 + 2 = Add(1, 2) + /// builder.start_node_at(checkpoint, OPERATION); + /// parser.parse_expr(); + /// builder.finish_node(); + /// } + /// ``` + #[inline] + pub fn checkpoint(&self) -> Checkpoint { + Checkpoint(self.children.len()) + } + + /// Wrap the previous branch marked by `checkpoint` in a new branch and + /// make it current. + #[inline] + pub fn start_node_at(&mut self, checkpoint: Checkpoint, kind: SyntaxKind) { + let Checkpoint(checkpoint) = checkpoint; + assert!( + checkpoint <= self.children.len(), + "checkpoint no longer valid, was finish_node called early?" + ); + + if let Some(&(_, first_child)) = self.parents.last() { + assert!( + checkpoint >= first_child, + "checkpoint no longer valid, was an unmatched start_node_at called?" + ); + } + + self.parents.push((kind, checkpoint)); + } + + /// Complete tree building. Make sure that + /// `start_node_at` and `finish_node` calls + /// are paired! + #[inline] + pub fn finish(mut self) -> GreenNode { + assert_eq!(self.children.len(), 1); + match self.children.pop().unwrap().1 { + NodeOrToken::Node(node) => node, + NodeOrToken::Token(_) => panic!(), + } + } +} diff --git a/vendor/rowan/src/green/element.rs b/vendor/rowan/src/green/element.rs new file mode 100644 index 000000000..2d1ce1f61 --- /dev/null +++ b/vendor/rowan/src/green/element.rs @@ -0,0 +1,89 @@ +use std::borrow::Cow; + +use crate::{ + green::{GreenNode, GreenToken, SyntaxKind}, + GreenNodeData, NodeOrToken, TextSize, +}; + +use super::GreenTokenData; + +pub(super) type GreenElement = NodeOrToken<GreenNode, GreenToken>; +pub(crate) type GreenElementRef<'a> = NodeOrToken<&'a GreenNodeData, &'a GreenTokenData>; + +impl From<GreenNode> for GreenElement { + #[inline] + fn from(node: GreenNode) -> GreenElement { + NodeOrToken::Node(node) + } +} + +impl<'a> From<&'a GreenNode> for GreenElementRef<'a> { + #[inline] + fn from(node: &'a GreenNode) -> GreenElementRef<'a> { + NodeOrToken::Node(node) + } +} + +impl From<GreenToken> for GreenElement { + #[inline] + fn from(token: GreenToken) -> GreenElement { + NodeOrToken::Token(token) + } +} + +impl From<Cow<'_, GreenNodeData>> for GreenElement { + #[inline] + fn from(cow: Cow<'_, GreenNodeData>) -> Self { + NodeOrToken::Node(cow.into_owned()) + } +} + +impl<'a> From<&'a GreenToken> for GreenElementRef<'a> { + #[inline] + fn from(token: &'a GreenToken) -> GreenElementRef<'a> { + NodeOrToken::Token(token) + } +} + +impl GreenElementRef<'_> { + pub fn to_owned(self) -> GreenElement { + match self { + NodeOrToken::Node(it) => NodeOrToken::Node(it.to_owned()), + NodeOrToken::Token(it) => NodeOrToken::Token(it.to_owned()), + } + } +} + +impl GreenElement { + /// Returns kind of this element. + #[inline] + pub fn kind(&self) -> SyntaxKind { + self.as_deref().kind() + } + + /// Returns the length of the text covered by this element. + #[inline] + pub fn text_len(&self) -> TextSize { + self.as_deref().text_len() + } +} + +impl GreenElementRef<'_> { + /// Returns kind of this element. + #[inline] + pub fn kind(&self) -> SyntaxKind { + match self { + NodeOrToken::Node(it) => it.kind(), + NodeOrToken::Token(it) => it.kind(), + } + } + + /// Returns the length of the text covered by this element. + #[inline] + pub fn text_len(self) -> TextSize { + match self { + NodeOrToken::Node(it) => it.text_len(), + NodeOrToken::Token(it) => it.text_len(), + } + } +} diff --git a/vendor/rowan/src/green/node.rs b/vendor/rowan/src/green/node.rs new file mode 100644 index 000000000..e94dc01cf --- /dev/null +++ b/vendor/rowan/src/green/node.rs @@ -0,0 +1,361 @@ +use std::{ + borrow::{Borrow, Cow}, + fmt, + iter::{self, FusedIterator}, + mem::{self, ManuallyDrop}, + ops, ptr, slice, +}; + +use countme::Count; + +use crate::{ + arc::{Arc, HeaderSlice, ThinArc}, + green::{GreenElement, GreenElementRef, SyntaxKind}, + utility_types::static_assert, + GreenToken, NodeOrToken, TextRange, TextSize, +}; + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub(super) struct GreenNodeHead { + kind: SyntaxKind, + text_len: TextSize, + _c: Count<GreenNode>, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub(crate) enum GreenChild { + Node { rel_offset: TextSize, node: GreenNode }, + Token { rel_offset: TextSize, token: GreenToken }, +} +#[cfg(target_pointer_width = "64")] +static_assert!(mem::size_of::<GreenChild>() == mem::size_of::<usize>() * 2); + +type Repr = HeaderSlice<GreenNodeHead, [GreenChild]>; +type ReprThin = HeaderSlice<GreenNodeHead, [GreenChild; 0]>; +#[repr(transparent)] +pub struct GreenNodeData { + data: ReprThin, +} + +impl PartialEq for GreenNodeData { + fn eq(&self, other: &Self) -> bool { + self.header() == other.header() && self.slice() == other.slice() + } +} + +/// Internal node in the immutable tree. +/// It has other nodes and tokens as children. +#[derive(Clone, PartialEq, Eq, Hash)] +#[repr(transparent)] +pub struct GreenNode { + ptr: ThinArc<GreenNodeHead, GreenChild>, +} + +impl ToOwned for GreenNodeData { + type Owned = GreenNode; + + #[inline] + fn to_owned(&self) -> GreenNode { + unsafe { + let green = GreenNode::from_raw(ptr::NonNull::from(self)); + let green = ManuallyDrop::new(green); + GreenNode::clone(&green) + } + } +} + +impl Borrow<GreenNodeData> for GreenNode { + #[inline] + fn borrow(&self) -> &GreenNodeData { + &*self + } +} + +impl From<Cow<'_, GreenNodeData>> for GreenNode { + #[inline] + fn from(cow: Cow<'_, GreenNodeData>) -> Self { + cow.into_owned() + } +} + +impl fmt::Debug for GreenNodeData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("GreenNode") + .field("kind", &self.kind()) + .field("text_len", &self.text_len()) + .field("n_children", &self.children().len()) + .finish() + } +} + +impl fmt::Debug for GreenNode { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let data: &GreenNodeData = &*self; + fmt::Debug::fmt(data, f) + } +} + +impl fmt::Display for GreenNode { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let data: &GreenNodeData = &*self; + fmt::Display::fmt(data, f) + } +} + +impl fmt::Display for GreenNodeData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + for child in self.children() { + write!(f, "{}", child)?; + } + Ok(()) + } +} + +impl GreenNodeData { + #[inline] + fn header(&self) -> &GreenNodeHead { + &self.data.header + } + + #[inline] + fn slice(&self) -> &[GreenChild] { + self.data.slice() + } + + /// Kind of this node. + #[inline] + pub fn kind(&self) -> SyntaxKind { + self.header().kind + } + + /// Returns the length of the text covered by this node. + #[inline] + pub fn text_len(&self) -> TextSize { + self.header().text_len + } + + /// Children of this node. + #[inline] + pub fn children(&self) -> Children<'_> { + Children { raw: self.slice().iter() } + } + + pub(crate) fn child_at_range( + &self, + rel_range: TextRange, + ) -> Option<(usize, TextSize, GreenElementRef<'_>)> { + let idx = self + .slice() + .binary_search_by(|it| { + let child_range = it.rel_range(); + TextRange::ordering(child_range, rel_range) + }) + // XXX: this handles empty ranges + .unwrap_or_else(|it| it.saturating_sub(1)); + let child = &self.slice().get(idx).filter(|it| it.rel_range().contains_range(rel_range))?; + Some((idx, child.rel_offset(), child.as_ref())) + } + + #[must_use] + pub fn replace_child(&self, index: usize, new_child: GreenElement) -> GreenNode { + let mut replacement = Some(new_child); + let children = self.children().enumerate().map(|(i, child)| { + if i == index { + replacement.take().unwrap() + } else { + child.to_owned() + } + }); + GreenNode::new(self.kind(), children) + } + #[must_use] + pub fn insert_child(&self, index: usize, new_child: GreenElement) -> GreenNode { + // https://github.com/rust-lang/rust/issues/34433 + self.splice_children(index..index, iter::once(new_child)) + } + #[must_use] + pub fn remove_child(&self, index: usize) -> GreenNode { + self.splice_children(index..=index, iter::empty()) + } + #[must_use] + pub fn splice_children<R, I>(&self, range: R, replace_with: I) -> GreenNode + where + R: ops::RangeBounds<usize>, + I: IntoIterator<Item = GreenElement>, + { + let mut children: Vec<_> = self.children().map(|it| it.to_owned()).collect(); + children.splice(range, replace_with); + GreenNode::new(self.kind(), children) + } +} + +impl ops::Deref for GreenNode { + type Target = GreenNodeData; + + #[inline] + fn deref(&self) -> &GreenNodeData { + unsafe { + let repr: &Repr = &self.ptr; + let repr: &ReprThin = &*(repr as *const Repr as *const ReprThin); + mem::transmute::<&ReprThin, &GreenNodeData>(repr) + } + } +} + +impl GreenNode { + /// Creates new Node. + #[inline] + pub fn new<I>(kind: SyntaxKind, children: I) -> GreenNode + where + I: IntoIterator<Item = GreenElement>, + I::IntoIter: ExactSizeIterator, + { + let mut text_len: TextSize = 0.into(); + let children = children.into_iter().map(|el| { + let rel_offset = text_len; + text_len += el.text_len(); + match el { + NodeOrToken::Node(node) => GreenChild::Node { rel_offset, node }, + NodeOrToken::Token(token) => GreenChild::Token { rel_offset, token }, + } + }); + + let data = ThinArc::from_header_and_iter( + GreenNodeHead { kind, text_len: 0.into(), _c: Count::new() }, + children, + ); + + // XXX: fixup `text_len` after construction, because we can't iterate + // `children` twice. + let data = { + let mut data = Arc::from_thin(data); + Arc::get_mut(&mut data).unwrap().header.text_len = text_len; + Arc::into_thin(data) + }; + + GreenNode { ptr: data } + } + + #[inline] + pub(crate) fn into_raw(this: GreenNode) -> ptr::NonNull<GreenNodeData> { + let green = ManuallyDrop::new(this); + let green: &GreenNodeData = &*green; + ptr::NonNull::from(&*green) + } + + #[inline] + pub(crate) unsafe fn from_raw(ptr: ptr::NonNull<GreenNodeData>) -> GreenNode { + let arc = Arc::from_raw(&ptr.as_ref().data as *const ReprThin); + let arc = mem::transmute::<Arc<ReprThin>, ThinArc<GreenNodeHead, GreenChild>>(arc); + GreenNode { ptr: arc } + } +} + +impl GreenChild { + #[inline] + pub(crate) fn as_ref(&self) -> GreenElementRef { + match self { + GreenChild::Node { node, .. } => NodeOrToken::Node(node), + GreenChild::Token { token, .. } => NodeOrToken::Token(token), + } + } + #[inline] + pub(crate) fn rel_offset(&self) -> TextSize { + match self { + GreenChild::Node { rel_offset, .. } | GreenChild::Token { rel_offset, .. } => { + *rel_offset + } + } + } + #[inline] + fn rel_range(&self) -> TextRange { + let len = self.as_ref().text_len(); + TextRange::at(self.rel_offset(), len) + } +} + +#[derive(Debug, Clone)] +pub struct Children<'a> { + pub(crate) raw: slice::Iter<'a, GreenChild>, +} + +// NB: forward everything stable that iter::Slice specializes as of Rust 1.39.0 +impl ExactSizeIterator for Children<'_> { + #[inline(always)] + fn len(&self) -> usize { + self.raw.len() + } +} + +impl<'a> Iterator for Children<'a> { + type Item = GreenElementRef<'a>; + + #[inline] + fn next(&mut self) -> Option<GreenElementRef<'a>> { + self.raw.next().map(GreenChild::as_ref) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.raw.size_hint() + } + + #[inline] + fn count(self) -> usize + where + Self: Sized, + { + self.raw.count() + } + + #[inline] + fn nth(&mut self, n: usize) -> Option<Self::Item> { + self.raw.nth(n).map(GreenChild::as_ref) + } + + #[inline] + fn last(mut self) -> Option<Self::Item> + where + Self: Sized, + { + self.next_back() + } + + #[inline] + fn fold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut accum = init; + while let Some(x) = self.next() { + accum = f(accum, x); + } + accum + } +} + +impl<'a> DoubleEndedIterator for Children<'a> { + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + self.raw.next_back().map(GreenChild::as_ref) + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option<Self::Item> { + self.raw.nth_back(n).map(GreenChild::as_ref) + } + + #[inline] + fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + let mut accum = init; + while let Some(x) = self.next_back() { + accum = f(accum, x); + } + accum + } +} + +impl FusedIterator for Children<'_> {} diff --git a/vendor/rowan/src/green/node_cache.rs b/vendor/rowan/src/green/node_cache.rs new file mode 100644 index 000000000..c73f3e696 --- /dev/null +++ b/vendor/rowan/src/green/node_cache.rs @@ -0,0 +1,157 @@ +use hashbrown::hash_map::RawEntryMut; +use rustc_hash::FxHasher; +use std::hash::{BuildHasherDefault, Hash, Hasher}; + +use crate::{ + green::GreenElementRef, GreenNode, GreenNodeData, GreenToken, GreenTokenData, NodeOrToken, + SyntaxKind, +}; + +use super::element::GreenElement; + +type HashMap<K, V> = hashbrown::HashMap<K, V, BuildHasherDefault<FxHasher>>; + +#[derive(Debug)] +struct NoHash<T>(T); + +/// Interner for GreenTokens and GreenNodes +// XXX: the impl is a bit tricky. As usual when writing interners, we want to +// store all values in one HashSet. +// +// However, hashing trees is fun: hash of the tree is recursively defined. We +// maintain an invariant -- if the tree is interned, then all of its children +// are interned as well. +// +// That means that computing the hash naively is wasteful -- we just *know* +// hashes of children, and we can re-use those. +// +// So here we use *raw* API of hashbrown and provide the hashes manually, +// instead of going via a `Hash` impl. Our manual `Hash` and the +// `#[derive(Hash)]` are actually different! At some point we had a fun bug, +// where we accidentally mixed the two hashes, which made the cache much less +// efficient. +// +// To fix that, we additionally wrap the data in `NoHash` wrapper, to make sure +// we don't accidentally use the wrong hash! +#[derive(Default, Debug)] +pub struct NodeCache { + nodes: HashMap<NoHash<GreenNode>, ()>, + tokens: HashMap<NoHash<GreenToken>, ()>, +} + +fn token_hash(token: &GreenTokenData) -> u64 { + let mut h = FxHasher::default(); + token.kind().hash(&mut h); + token.text().hash(&mut h); + h.finish() +} + +fn node_hash(node: &GreenNodeData) -> u64 { + let mut h = FxHasher::default(); + node.kind().hash(&mut h); + for child in node.children() { + match child { + NodeOrToken::Node(it) => node_hash(it), + NodeOrToken::Token(it) => token_hash(it), + } + .hash(&mut h) + } + h.finish() +} + +fn element_id(elem: GreenElementRef<'_>) -> *const () { + match elem { + NodeOrToken::Node(it) => it as *const GreenNodeData as *const (), + NodeOrToken::Token(it) => it as *const GreenTokenData as *const (), + } +} + +impl NodeCache { + pub(crate) fn node( + &mut self, + kind: SyntaxKind, + children: &mut Vec<(u64, GreenElement)>, + first_child: usize, + ) -> (u64, GreenNode) { + let build_node = move |children: &mut Vec<(u64, GreenElement)>| { + GreenNode::new(kind, children.drain(first_child..).map(|(_, it)| it)) + }; + + let children_ref = &children[first_child..]; + if children_ref.len() > 3 { + let node = build_node(children); + return (0, node); + } + + let hash = { + let mut h = FxHasher::default(); + kind.hash(&mut h); + for &(hash, _) in children_ref { + if hash == 0 { + let node = build_node(children); + return (0, node); + } + hash.hash(&mut h); + } + h.finish() + }; + + // Green nodes are fully immutable, so it's ok to deduplicate them. + // This is the same optimization that Roslyn does + // https://github.com/KirillOsenkov/Bliki/wiki/Roslyn-Immutable-Trees + // + // For example, all `#[inline]` in this file share the same green node! + // For `libsyntax/parse/parser.rs`, measurements show that deduping saves + // 17% of the memory for green nodes! + let entry = self.nodes.raw_entry_mut().from_hash(hash, |node| { + node.0.kind() == kind && node.0.children().len() == children_ref.len() && { + let lhs = node.0.children(); + let rhs = children_ref.iter().map(|(_, it)| it.as_deref()); + + let lhs = lhs.map(element_id); + let rhs = rhs.map(element_id); + + lhs.eq(rhs) + } + }); + + let node = match entry { + RawEntryMut::Occupied(entry) => { + drop(children.drain(first_child..)); + entry.key().0.clone() + } + RawEntryMut::Vacant(entry) => { + let node = build_node(children); + entry.insert_with_hasher(hash, NoHash(node.clone()), (), |n| node_hash(&n.0)); + node + } + }; + + (hash, node) + } + + pub(crate) fn token(&mut self, kind: SyntaxKind, text: &str) -> (u64, GreenToken) { + let hash = { + let mut h = FxHasher::default(); + kind.hash(&mut h); + text.hash(&mut h); + h.finish() + }; + + let entry = self + .tokens + .raw_entry_mut() + .from_hash(hash, |token| token.0.kind() == kind && token.0.text() == text); + + let token = match entry { + RawEntryMut::Occupied(entry) => entry.key().0.clone(), + RawEntryMut::Vacant(entry) => { + let token = GreenToken::new(kind, text); + entry.insert_with_hasher(hash, NoHash(token.clone()), (), |t| token_hash(&t.0)); + token + } + }; + + (hash, token) + } +} diff --git a/vendor/rowan/src/green/token.rs b/vendor/rowan/src/green/token.rs new file mode 100644 index 000000000..1a4548a43 --- /dev/null +++ b/vendor/rowan/src/green/token.rs @@ -0,0 +1,145 @@ +use std::{ + borrow::Borrow, + fmt, + mem::{self, ManuallyDrop}, + ops, ptr, +}; + +use countme::Count; + +use crate::{ + arc::{Arc, HeaderSlice, ThinArc}, + green::SyntaxKind, + TextSize, +}; + +#[derive(PartialEq, Eq, Hash)] +struct GreenTokenHead { + kind: SyntaxKind, + _c: Count<GreenToken>, +} + +type Repr = HeaderSlice<GreenTokenHead, [u8]>; +type ReprThin = HeaderSlice<GreenTokenHead, [u8; 0]>; +#[repr(transparent)] +pub struct GreenTokenData { + data: ReprThin, +} + +impl PartialEq for GreenTokenData { + fn eq(&self, other: &Self) -> bool { + self.kind() == other.kind() && self.text() == other.text() + } +} + +/// Leaf node in the immutable tree. +#[derive(PartialEq, Eq, Hash, Clone)] +#[repr(transparent)] +pub struct GreenToken { + ptr: ThinArc<GreenTokenHead, u8>, +} + +impl ToOwned for GreenTokenData { + type Owned = GreenToken; + + #[inline] + fn to_owned(&self) -> GreenToken { + unsafe { + let green = GreenToken::from_raw(ptr::NonNull::from(self)); + let green = ManuallyDrop::new(green); + GreenToken::clone(&green) + } + } +} + +impl Borrow<GreenTokenData> for GreenToken { + #[inline] + fn borrow(&self) -> &GreenTokenData { + &*self + } +} + +impl fmt::Debug for GreenTokenData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("GreenToken") + .field("kind", &self.kind()) + .field("text", &self.text()) + .finish() + } +} + +impl fmt::Debug for GreenToken { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let data: &GreenTokenData = &*self; + fmt::Debug::fmt(data, f) + } +} + +impl fmt::Display for GreenToken { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let data: &GreenTokenData = &*self; + fmt::Display::fmt(data, f) + } +} + +impl fmt::Display for GreenTokenData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{}", self.text()) + } +} + +impl GreenTokenData { + /// Kind of this Token. + #[inline] + pub fn kind(&self) -> SyntaxKind { + self.data.header.kind + } + + /// Text of this Token. + #[inline] + pub fn text(&self) -> &str { + unsafe { std::str::from_utf8_unchecked(self.data.slice()) } + } + + /// Returns the length of the text covered by this token. + #[inline] + pub fn text_len(&self) -> TextSize { + TextSize::of(self.text()) + } +} + +impl GreenToken { + /// Creates new Token. + #[inline] + pub fn new(kind: SyntaxKind, text: &str) -> GreenToken { + let head = GreenTokenHead { kind, _c: Count::new() }; + let ptr = ThinArc::from_header_and_iter(head, text.bytes()); + GreenToken { ptr } + } + #[inline] + pub(crate) fn into_raw(this: GreenToken) -> ptr::NonNull<GreenTokenData> { + let green = ManuallyDrop::new(this); + let green: &GreenTokenData = &*green; + ptr::NonNull::from(&*green) + } + + #[inline] + pub(crate) unsafe fn from_raw(ptr: ptr::NonNull<GreenTokenData>) -> GreenToken { + let arc = Arc::from_raw(&ptr.as_ref().data as *const ReprThin); + let arc = mem::transmute::<Arc<ReprThin>, ThinArc<GreenTokenHead, u8>>(arc); + GreenToken { ptr: arc } + } +} + +impl ops::Deref for GreenToken { + type Target = GreenTokenData; + + #[inline] + fn deref(&self) -> &GreenTokenData { + unsafe { + let repr: &Repr = &self.ptr; + let repr: &ReprThin = &*(repr as *const Repr as *const ReprThin); + mem::transmute::<&ReprThin, &GreenTokenData>(repr) + } + } +} diff --git a/vendor/rowan/src/lib.rs b/vendor/rowan/src/lib.rs new file mode 100644 index 000000000..bb8f30d02 --- /dev/null +++ b/vendor/rowan/src/lib.rs @@ -0,0 +1,41 @@ +//! A generic library for lossless syntax trees. +//! See `examples/s_expressions.rs` for a tutorial. +#![forbid( + // missing_debug_implementations, + unconditional_recursion, + future_incompatible, + // missing_docs, +)] +#![deny(unsafe_code)] + +#[allow(unsafe_code)] +mod green; +#[allow(unsafe_code)] +pub mod cursor; + +pub mod api; +mod syntax_text; +mod utility_types; + +mod cow_mut; +#[allow(unsafe_code)] +mod sll; +#[allow(unsafe_code)] +mod arc; +#[cfg(feature = "serde1")] +mod serde_impls; +pub mod ast; + +pub use text_size::{TextLen, TextRange, TextSize}; + +pub use crate::{ + api::{ + Language, SyntaxElement, SyntaxElementChildren, SyntaxNode, SyntaxNodeChildren, SyntaxToken, + }, + green::{ + Checkpoint, Children, GreenNode, GreenNodeBuilder, GreenNodeData, GreenToken, + GreenTokenData, NodeCache, SyntaxKind, + }, + syntax_text::SyntaxText, + utility_types::{Direction, NodeOrToken, TokenAtOffset, WalkEvent}, +}; diff --git a/vendor/rowan/src/serde_impls.rs b/vendor/rowan/src/serde_impls.rs new file mode 100644 index 000000000..aea5d88b7 --- /dev/null +++ b/vendor/rowan/src/serde_impls.rs @@ -0,0 +1,66 @@ +use serde::ser::{Serialize, SerializeMap, SerializeSeq, Serializer}; +use std::fmt; + +use crate::{ + api::{Language, SyntaxNode, SyntaxToken}, + NodeOrToken, +}; + +struct SerDisplay<T>(T); +impl<T: fmt::Display> Serialize for SerDisplay<T> { + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + serializer.collect_str(&self.0) + } +} + +struct DisplayDebug<T>(T); +impl<T: fmt::Debug> fmt::Display for DisplayDebug<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.0, f) + } +} + +impl<L: Language> Serialize for SyntaxNode<L> { + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut state = serializer.serialize_map(Some(3))?; + state.serialize_entry("kind", &SerDisplay(DisplayDebug(self.kind())))?; + state.serialize_entry("text_range", &self.text_range())?; + state.serialize_entry("children", &Children(self))?; + state.end() + } +} + +impl<L: Language> Serialize for SyntaxToken<L> { + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut state = serializer.serialize_map(Some(3))?; + state.serialize_entry("kind", &SerDisplay(DisplayDebug(self.kind())))?; + state.serialize_entry("text_range", &self.text_range())?; + state.serialize_entry("text", &self.text())?; + state.end() + } +} + +struct Children<T>(T); + +impl<L: Language> Serialize for Children<&'_ SyntaxNode<L>> { + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut state = serializer.serialize_seq(None)?; + self.0.children_with_tokens().try_for_each(|element| match element { + NodeOrToken::Node(it) => state.serialize_element(&it), + NodeOrToken::Token(it) => state.serialize_element(&it), + })?; + state.end() + } +} diff --git a/vendor/rowan/src/sll.rs b/vendor/rowan/src/sll.rs new file mode 100644 index 000000000..87d2f1f31 --- /dev/null +++ b/vendor/rowan/src/sll.rs @@ -0,0 +1,129 @@ +//! Sorted Linked List + +use std::{cell::Cell, cmp::Ordering, ptr}; + +use crate::utility_types::Delta; +pub(crate) unsafe trait Elem { + fn prev(&self) -> &Cell<*const Self>; + fn next(&self) -> &Cell<*const Self>; + fn key(&self) -> &Cell<u32>; +} + +pub(crate) enum AddToSllResult<'a, E: Elem> { + NoHead, + EmptyHead(&'a Cell<*const E>), + SmallerThanHead(&'a Cell<*const E>), + SmallerThanNotHead(*const E), + AlreadyInSll(*const E), +} + +impl<'a, E: Elem> AddToSllResult<'a, E> { + pub(crate) fn add_to_sll(&self, elem_ptr: *const E) { + unsafe { + (*elem_ptr).prev().set(elem_ptr); + (*elem_ptr).next().set(elem_ptr); + + match self { + // Case 1: empty head, replace it. + AddToSllResult::EmptyHead(head) => head.set(elem_ptr), + + // Case 2: we are smaller than the head, replace it. + AddToSllResult::SmallerThanHead(head) => { + let old_head = head.get(); + let prev = (*old_head).prev().replace(elem_ptr); + (*prev).next().set(elem_ptr); + (*elem_ptr).next().set(old_head); + (*elem_ptr).prev().set(prev); + head.set(elem_ptr); + } + + // Case 3: insert in place found by looping + AddToSllResult::SmallerThanNotHead(curr) => { + let next = (**curr).next().replace(elem_ptr); + (*next).prev().set(elem_ptr); + (*elem_ptr).prev().set(*curr); + (*elem_ptr).next().set(next); + } + AddToSllResult::NoHead | AddToSllResult::AlreadyInSll(_) => (), + } + } + } +} + +#[cold] +pub(crate) fn init<'a, E: Elem>( + head: Option<&'a Cell<*const E>>, + elem: &E, +) -> AddToSllResult<'a, E> { + if let Some(head) = head { + link(head, elem) + } else { + AddToSllResult::NoHead + } +} + +#[cold] +pub(crate) fn unlink<E: Elem>(head: &Cell<*const E>, elem: &E) { + debug_assert!(!head.get().is_null(), "invalid linked list head"); + + let elem_ptr: *const E = elem; + + let prev = elem.prev().replace(elem_ptr); + let next = elem.next().replace(elem_ptr); + unsafe { + debug_assert_eq!((*prev).next().get(), elem_ptr, "invalid linked list links"); + debug_assert_eq!((*next).prev().get(), elem_ptr, "invalid linked list links"); + (*prev).next().set(next); + (*next).prev().set(prev); + } + + if head.get() == elem_ptr { + head.set(if next == elem_ptr { ptr::null() } else { next }) + } +} + +#[cold] +pub(crate) fn link<'a, E: Elem>(head: &'a Cell<*const E>, elem: &E) -> AddToSllResult<'a, E> { + unsafe { + let old_head = head.get(); + // Case 1: empty head, replace it. + if old_head.is_null() { + return AddToSllResult::EmptyHead(head); + } + + // Case 2: we are smaller than the head, replace it. + if elem.key() < (*old_head).key() { + return AddToSllResult::SmallerThanHead(head); + } + + // Case 3: loop *backward* until we find insertion place. Because of + // Case 2, we can't loop beyond the head. + let mut curr = (*old_head).prev().get(); + loop { + match (*curr).key().cmp(elem.key()) { + Ordering::Less => return AddToSllResult::SmallerThanNotHead(curr), + Ordering::Equal => return AddToSllResult::AlreadyInSll(curr), + Ordering::Greater => curr = (*curr).prev().get(), + } + } + } +} + +pub(crate) fn adjust<E: Elem>(elem: &E, from: u32, by: Delta<u32>) { + let elem_ptr: *const E = elem; + + unsafe { + let mut curr = elem_ptr; + loop { + let mut key = (*curr).key().get(); + if key >= from { + key += by; + (*curr).key().set(key); + } + curr = (*curr).next().get(); + if curr == elem_ptr { + break; + } + } + } +} diff --git a/vendor/rowan/src/syntax_text.rs b/vendor/rowan/src/syntax_text.rs new file mode 100644 index 000000000..3ab3f6cb0 --- /dev/null +++ b/vendor/rowan/src/syntax_text.rs @@ -0,0 +1,311 @@ +use std::fmt; + +use crate::{ + cursor::{SyntaxNode, SyntaxToken}, + TextRange, TextSize, +}; + +#[derive(Clone)] +pub struct SyntaxText { + node: SyntaxNode, + range: TextRange, +} + +impl SyntaxText { + pub(crate) fn new(node: SyntaxNode) -> SyntaxText { + let range = node.text_range(); + SyntaxText { node, range } + } + + pub fn len(&self) -> TextSize { + self.range.len() + } + + pub fn is_empty(&self) -> bool { + self.range.is_empty() + } + + pub fn contains_char(&self, c: char) -> bool { + self.try_for_each_chunk(|chunk| if chunk.contains(c) { Err(()) } else { Ok(()) }).is_err() + } + + pub fn find_char(&self, c: char) -> Option<TextSize> { + let mut acc: TextSize = 0.into(); + let res = self.try_for_each_chunk(|chunk| { + if let Some(pos) = chunk.find(c) { + let pos: TextSize = (pos as u32).into(); + return Err(acc + pos); + } + acc += TextSize::of(chunk); + Ok(()) + }); + found(res) + } + + pub fn char_at(&self, offset: TextSize) -> Option<char> { + let offset = offset.into(); + let mut start: TextSize = 0.into(); + let res = self.try_for_each_chunk(|chunk| { + let end = start + TextSize::of(chunk); + if start <= offset && offset < end { + let off: usize = u32::from(offset - start) as usize; + return Err(chunk[off..].chars().next().unwrap()); + } + start = end; + Ok(()) + }); + found(res) + } + + pub fn slice<R: private::SyntaxTextRange>(&self, range: R) -> SyntaxText { + let start = range.start().unwrap_or_default(); + let end = range.end().unwrap_or(self.len()); + assert!(start <= end); + let len = end - start; + let start = self.range.start() + start; + let end = start + len; + assert!( + start <= end, + "invalid slice, range: {:?}, slice: {:?}", + self.range, + (range.start(), range.end()), + ); + let range = TextRange::new(start, end); + assert!( + self.range.contains_range(range), + "invalid slice, range: {:?}, slice: {:?}", + self.range, + range, + ); + SyntaxText { node: self.node.clone(), range } + } + + pub fn try_fold_chunks<T, F, E>(&self, init: T, mut f: F) -> Result<T, E> + where + F: FnMut(T, &str) -> Result<T, E>, + { + self.tokens_with_ranges() + .try_fold(init, move |acc, (token, range)| f(acc, &token.text()[range])) + } + + pub fn try_for_each_chunk<F: FnMut(&str) -> Result<(), E>, E>( + &self, + mut f: F, + ) -> Result<(), E> { + self.try_fold_chunks((), move |(), chunk| f(chunk)) + } + + pub fn for_each_chunk<F: FnMut(&str)>(&self, mut f: F) { + enum Void {} + match self.try_for_each_chunk(|chunk| Ok::<(), Void>(f(chunk))) { + Ok(()) => (), + Err(void) => match void {}, + } + } + + fn tokens_with_ranges(&self) -> impl Iterator<Item = (SyntaxToken, TextRange)> { + let text_range = self.range; + self.node.descendants_with_tokens().filter_map(|element| element.into_token()).filter_map( + move |token| { + let token_range = token.text_range(); + let range = text_range.intersect(token_range)?; + Some((token, range - token_range.start())) + }, + ) + } +} + +fn found<T>(res: Result<(), T>) -> Option<T> { + match res { + Ok(()) => None, + Err(it) => Some(it), + } +} + +impl fmt::Debug for SyntaxText { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + fmt::Debug::fmt(&self.to_string(), f) + } +} + +impl fmt::Display for SyntaxText { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.try_for_each_chunk(|chunk| fmt::Display::fmt(chunk, f)) + } +} + +impl From<SyntaxText> for String { + fn from(text: SyntaxText) -> String { + text.to_string() + } +} + +impl PartialEq<str> for SyntaxText { + fn eq(&self, mut rhs: &str) -> bool { + self.try_for_each_chunk(|chunk| { + if !rhs.starts_with(chunk) { + return Err(()); + } + rhs = &rhs[chunk.len()..]; + Ok(()) + }) + .is_ok() + && rhs.is_empty() + } +} + +impl PartialEq<SyntaxText> for str { + fn eq(&self, rhs: &SyntaxText) -> bool { + rhs == self + } +} + +impl PartialEq<&'_ str> for SyntaxText { + fn eq(&self, rhs: &&str) -> bool { + self == *rhs + } +} + +impl PartialEq<SyntaxText> for &'_ str { + fn eq(&self, rhs: &SyntaxText) -> bool { + rhs == self + } +} + +impl PartialEq for SyntaxText { + fn eq(&self, other: &SyntaxText) -> bool { + if self.range.len() != other.range.len() { + return false; + } + let mut lhs = self.tokens_with_ranges(); + let mut rhs = other.tokens_with_ranges(); + zip_texts(&mut lhs, &mut rhs).is_none() + && lhs.all(|it| it.1.is_empty()) + && rhs.all(|it| it.1.is_empty()) + } +} + +fn zip_texts<I: Iterator<Item = (SyntaxToken, TextRange)>>(xs: &mut I, ys: &mut I) -> Option<()> { + let mut x = xs.next()?; + let mut y = ys.next()?; + loop { + while x.1.is_empty() { + x = xs.next()?; + } + while y.1.is_empty() { + y = ys.next()?; + } + let x_text = &x.0.text()[x.1]; + let y_text = &y.0.text()[y.1]; + if !(x_text.starts_with(y_text) || y_text.starts_with(x_text)) { + return Some(()); + } + let advance = std::cmp::min(x.1.len(), y.1.len()); + x.1 = TextRange::new(x.1.start() + advance, x.1.end()); + y.1 = TextRange::new(y.1.start() + advance, y.1.end()); + } +} + +impl Eq for SyntaxText {} + +mod private { + use std::ops; + + use crate::{TextRange, TextSize}; + + pub trait SyntaxTextRange { + fn start(&self) -> Option<TextSize>; + fn end(&self) -> Option<TextSize>; + } + + impl SyntaxTextRange for TextRange { + fn start(&self) -> Option<TextSize> { + Some(TextRange::start(*self)) + } + fn end(&self) -> Option<TextSize> { + Some(TextRange::end(*self)) + } + } + + impl SyntaxTextRange for ops::Range<TextSize> { + fn start(&self) -> Option<TextSize> { + Some(self.start) + } + fn end(&self) -> Option<TextSize> { + Some(self.end) + } + } + + impl SyntaxTextRange for ops::RangeFrom<TextSize> { + fn start(&self) -> Option<TextSize> { + Some(self.start) + } + fn end(&self) -> Option<TextSize> { + None + } + } + + impl SyntaxTextRange for ops::RangeTo<TextSize> { + fn start(&self) -> Option<TextSize> { + None + } + fn end(&self) -> Option<TextSize> { + Some(self.end) + } + } + + impl SyntaxTextRange for ops::RangeFull { + fn start(&self) -> Option<TextSize> { + None + } + fn end(&self) -> Option<TextSize> { + None + } + } +} + +#[cfg(test)] +mod tests { + use crate::{green::SyntaxKind, GreenNodeBuilder}; + + use super::*; + + fn build_tree(chunks: &[&str]) -> SyntaxNode { + let mut builder = GreenNodeBuilder::new(); + builder.start_node(SyntaxKind(62)); + for &chunk in chunks.iter() { + builder.token(SyntaxKind(92), chunk.into()) + } + builder.finish_node(); + SyntaxNode::new_root(builder.finish()) + } + + #[test] + fn test_text_equality() { + fn do_check(t1: &[&str], t2: &[&str]) { + let t1 = build_tree(t1).text(); + let t2 = build_tree(t2).text(); + let expected = t1.to_string() == t2.to_string(); + let actual = t1 == t2; + assert_eq!(expected, actual, "`{}` (SyntaxText) `{}` (SyntaxText)", t1, t2); + let actual = t1 == &*t2.to_string(); + assert_eq!(expected, actual, "`{}` (SyntaxText) `{}` (&str)", t1, t2); + } + fn check(t1: &[&str], t2: &[&str]) { + do_check(t1, t2); + do_check(t2, t1) + } + + check(&[""], &[""]); + check(&["a"], &[""]); + check(&["a"], &["a"]); + check(&["abc"], &["def"]); + check(&["hello", "world"], &["hello", "world"]); + check(&["hellowo", "rld"], &["hell", "oworld"]); + check(&["hel", "lowo", "rld"], &["helloworld"]); + check(&["{", "abc", "}"], &["{", "123", "}"]); + check(&["{", "abc", "}", "{"], &["{", "123", "}"]); + check(&["{", "abc", "}"], &["{", "123", "}", "{"]); + check(&["{", "abc", "}ab"], &["{", "abc", "}", "ab"]); + } +} diff --git a/vendor/rowan/src/utility_types.rs b/vendor/rowan/src/utility_types.rs new file mode 100644 index 000000000..817add72e --- /dev/null +++ b/vendor/rowan/src/utility_types.rs @@ -0,0 +1,180 @@ +use std::{ + fmt, + ops::{AddAssign, Deref}, +}; +use text_size::TextSize; + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub enum NodeOrToken<N, T> { + Node(N), + Token(T), +} + +impl<N, T> NodeOrToken<N, T> { + pub fn into_node(self) -> Option<N> { + match self { + NodeOrToken::Node(node) => Some(node), + NodeOrToken::Token(_) => None, + } + } + + pub fn into_token(self) -> Option<T> { + match self { + NodeOrToken::Node(_) => None, + NodeOrToken::Token(token) => Some(token), + } + } + + pub fn as_node(&self) -> Option<&N> { + match self { + NodeOrToken::Node(node) => Some(node), + NodeOrToken::Token(_) => None, + } + } + + pub fn as_token(&self) -> Option<&T> { + match self { + NodeOrToken::Node(_) => None, + NodeOrToken::Token(token) => Some(token), + } + } +} + +impl<N: Deref, T: Deref> NodeOrToken<N, T> { + pub(crate) fn as_deref(&self) -> NodeOrToken<&N::Target, &T::Target> { + match self { + NodeOrToken::Node(node) => NodeOrToken::Node(&*node), + NodeOrToken::Token(token) => NodeOrToken::Token(&*token), + } + } +} + +impl<N: fmt::Display, T: fmt::Display> fmt::Display for NodeOrToken<N, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + NodeOrToken::Node(node) => fmt::Display::fmt(node, f), + NodeOrToken::Token(token) => fmt::Display::fmt(token, f), + } + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub enum Direction { + Next, + Prev, +} + +/// `WalkEvent` describes tree walking process. +#[derive(Debug, Copy, Clone)] +pub enum WalkEvent<T> { + /// Fired before traversing the node. + Enter(T), + /// Fired after the node is traversed. + Leave(T), +} + +impl<T> WalkEvent<T> { + pub fn map<F: FnOnce(T) -> U, U>(self, f: F) -> WalkEvent<U> { + match self { + WalkEvent::Enter(it) => WalkEvent::Enter(f(it)), + WalkEvent::Leave(it) => WalkEvent::Leave(f(it)), + } + } +} + +/// There might be zero, one or two leaves at a given offset. +#[derive(Clone, Debug)] +pub enum TokenAtOffset<T> { + /// No leaves at offset -- possible for the empty file. + None, + /// Only a single leaf at offset. + Single(T), + /// Offset is exactly between two leaves. + Between(T, T), +} + +impl<T> TokenAtOffset<T> { + pub fn map<F: Fn(T) -> U, U>(self, f: F) -> TokenAtOffset<U> { + match self { + TokenAtOffset::None => TokenAtOffset::None, + TokenAtOffset::Single(it) => TokenAtOffset::Single(f(it)), + TokenAtOffset::Between(l, r) => TokenAtOffset::Between(f(l), f(r)), + } + } + + /// Convert to option, preferring the right leaf in case of a tie. + pub fn right_biased(self) -> Option<T> { + match self { + TokenAtOffset::None => None, + TokenAtOffset::Single(node) => Some(node), + TokenAtOffset::Between(_, right) => Some(right), + } + } + + /// Convert to option, preferring the left leaf in case of a tie. + pub fn left_biased(self) -> Option<T> { + match self { + TokenAtOffset::None => None, + TokenAtOffset::Single(node) => Some(node), + TokenAtOffset::Between(left, _) => Some(left), + } + } +} + +impl<T> Iterator for TokenAtOffset<T> { + type Item = T; + + fn next(&mut self) -> Option<T> { + match std::mem::replace(self, TokenAtOffset::None) { + TokenAtOffset::None => None, + TokenAtOffset::Single(node) => { + *self = TokenAtOffset::None; + Some(node) + } + TokenAtOffset::Between(left, right) => { + *self = TokenAtOffset::Single(right); + Some(left) + } + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + match self { + TokenAtOffset::None => (0, Some(0)), + TokenAtOffset::Single(_) => (1, Some(1)), + TokenAtOffset::Between(_, _) => (2, Some(2)), + } + } +} + +impl<T> ExactSizeIterator for TokenAtOffset<T> {} + +macro_rules! _static_assert { + ($expr:expr) => { + const _: i32 = 0 / $expr as i32; + }; +} + +pub(crate) use _static_assert as static_assert; + +#[derive(Copy, Clone, Debug)] +pub(crate) enum Delta<T> { + Add(T), + Sub(T), +} + +// This won't be coherent :-( +// impl<T: AddAssign + SubAssign> AddAssign<Delta<T>> for T +macro_rules! impls { + ($($ty:ident)*) => {$( + impl AddAssign<Delta<$ty>> for $ty { + fn add_assign(&mut self, rhs: Delta<$ty>) { + match rhs { + Delta::Add(amt) => *self += amt, + Delta::Sub(amt) => *self -= amt, + } + } + } + )*}; +} +impls!(u32 TextSize); diff --git a/vendor/rowan/tests/tidy.rs b/vendor/rowan/tests/tidy.rs new file mode 100644 index 000000000..a716e35b2 --- /dev/null +++ b/vendor/rowan/tests/tidy.rs @@ -0,0 +1,46 @@ +use std::{ + env, + path::{Path, PathBuf}, + process::{Command, Stdio}, +}; + +fn project_root() -> PathBuf { + PathBuf::from( + env::var("CARGO_MANIFEST_DIR").unwrap_or_else(|_| env!("CARGO_MANIFEST_DIR").to_owned()), + ) +} + +fn run(cmd: &str, dir: impl AsRef<Path>) -> Result<(), ()> { + let mut args: Vec<_> = cmd.split_whitespace().collect(); + let bin = args.remove(0); + println!("> {}", cmd); + let output = Command::new(bin) + .args(args) + .current_dir(dir) + .stdin(Stdio::null()) + .stdout(Stdio::piped()) + .stderr(Stdio::inherit()) + .output() + .map_err(drop)?; + if output.status.success() { + Ok(()) + } else { + let stdout = String::from_utf8(output.stdout).map_err(drop)?; + print!("{}", stdout); + Err(()) + } +} + +#[test] +fn check_code_formatting() { + let dir = project_root(); + if run("rustfmt +stable --version", &dir).is_err() { + panic!( + "failed to run rustfmt from toolchain 'stable'; \ + please run `rustup component add rustfmt --toolchain stable` to install it.", + ); + } + if run("cargo +stable fmt -- --check", &dir).is_err() { + panic!("code is not properly formatted; please format the code by running `cargo fmt`") + } +} |