## Source Code
-The things described are implemented in two places
+The things described are implemented in three places
* [rowan](https://github.com/rust-analyzer/rowan/tree/v0.9.0) -- a generic library for rowan syntax trees.
* [ra_syntax](https://github.com/rust-analyzer/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/ra_syntax) crate inside rust-analyzer which wraps `rowan` into rust-analyzer specific API.
Nothing in rust-analyzer except this crate knows about `rowan`.
-* [ra_parser](https://github.com/rust-analyzer/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/ra_parser) crate parses input tokens into an `ra_syntax` tree
+* [parser](https://github.com/rust-analyzer/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/parser) crate parses input tokens into an `ra_syntax` tree
## Design Goals
-* Syntax trees are lossless, or full fidelity. All comments and whitespace are preserved.
+* Syntax trees are lossless, or full fidelity. All comments and whitespace get preserved.
* Syntax trees are semantic-less. They describe *strictly* the structure of a sequence of characters, they don't have hygiene, name resolution or type information attached.
-* Syntax trees are simple value type. It is possible to create trees for a syntax without any external context.
+* Syntax trees are simple value types. It is possible to create trees for a syntax without any external context.
* Syntax trees have intuitive traversal API (parent, children, siblings, etc).
* Parsing is lossless (even if the input is invalid, the tree produced by the parser represents it exactly).
* Parsing is resilient (even if the input is invalid, parser tries to see as much syntax tree fragments in the input as it can).
* Trivia and non-trivia tokens are not distinguished on the type level.
* Each token carries its full text.
* The original text can be recovered by concatenating the texts of all tokens in order.
-* Accessing a child of particular type (for example, parameter list of a function) generally involves linerary traversing the children, looking for a specific `kind`.
+* Accessing a child of particular type (for example, parameter list of a function) generally involves linearly traversing the children, looking for a specific `kind`.
* Modifying the tree is roughly `O(depth)`.
We don't make special efforts to guarantee that the depth is not linear, but, in practice, syntax trees are branchy and shallow.
* If mandatory (grammar wise) node is missing from the input, it's just missing from the tree.
R_PAREN@5..6 ")"
WHITESPACE@6..7 " "
BLOCK_EXPR@7..17
- BLOCK@7..17
- L_CURLY@7..8 "{"
- WHITESPACE@8..9 " "
- BIN_EXPR@9..15
- LITERAL@9..11
- INT_NUMBER@9..11 "90"
- WHITESPACE@11..12 " "
- PLUS@12..13 "+"
- WHITESPACE@13..14 " "
- LITERAL@14..15
- INT_NUMBER@14..15 "2"
- WHITESPACE@15..16 " "
- R_CURLY@16..17 "}"
+ L_CURLY@7..8 "{"
+ WHITESPACE@8..9 " "
+ BIN_EXPR@9..15
+ LITERAL@9..11
+ INT_NUMBER@9..11 "90"
+ WHITESPACE@11..12 " "
+ PLUS@12..13 "+"
+ WHITESPACE@13..14 " "
+ LITERAL@14..15
+ INT_NUMBER@14..15 "2"
+ WHITESPACE@15..16 " "
+ R_CURLY@16..17 "}"
```
#### Optimizations
(significant amount of implementation work here was done by [CAD97](https://github.com/cad97)).
-To reduce the amount of allocations, the GreenNode is a DST, which uses a single allocation for header and children. Thus, it is only usable behind a pointer
+To reduce the amount of allocations, the GreenNode is a [DST](https://doc.rust-lang.org/reference/dynamically-sized-types.html), which uses a single allocation for header and children. Thus, it is only usable behind a pointer.
```
*-----------+------+----------+------------+--------+--------+-----+--------*
```rust
struct Token {
- kind: NonTriviaTokenKind
+ kind: NonTriviaTokenKind,
text: String,
leading_trivia: Vec<TriviaToken>,
trailing_trivia: Vec<TriviaToken>,
A function green tree is not super-convenient to use.
The biggest problem is accessing parents (there are no parent pointers!).
But there are also "identify" issues.
-Let's say you want to write a code which builds a list of expressions in a file: `fn collect_exrepssions(file: GreenNode) -> HashSet<GreenNode>`.
+Let's say you want to write a code which builds a list of expressions in a file: `fn collect_expressions(file: GreenNode) -> HashSet<GreenNode>`.
For the input like
```rust
self.parent.clone()
}
fn children(&self) -> impl Iterator<Item = SyntaxNode> {
- let mut offset = self.offset
+ let mut offset = self.offset;
self.green.children().map(|green_child| {
let child_offset = offset;
offset += green_child.text_len;
Arc::new(SyntaxData {
- offset: child_offset;
+ offset: child_offset,
parent: Some(Arc::clone(self)),
green: Arc::clone(green_child),
})
}
impl PartialEq for SyntaxNode {
- fn eq(&self, other: &SyntaxNode) {
+ fn eq(&self, other: &SyntaxNode) -> bool {
self.offset == other.offset
&& Arc::ptr_eq(&self.green, &other.green)
}
The other thread can restore the `SyntaxNode` by traversing from the root green node and looking for a node with specified range.
You can also use the similar trick to store a `SyntaxNode`.
That is, a data structure that holds a `(GreenNode, Range<usize>)` will be `Sync`.
-However rust-analyzer goes even further.
+However, rust-analyzer goes even further.
It treats trees as semi-transient and instead of storing a `GreenNode`, it generally stores just the id of the file from which the tree originated: `(FileId, Range<usize>)`.
The `SyntaxNode` is the restored by reparsing the file and traversing it from root.
With this trick, rust-analyzer holds only a small amount of trees in memory at the same time, which reduces memory usage.
fn visibility(&self) -> Option<Visibility>;
}
-impl HasVisbility for FnDef {
+impl HasVisibility for FnDef {
fn visibility(&self) -> Option<Visibility> {
self.syntax.children().find_map(Visibility::cast)
}
### Parsing Algorithm
-We use a boring hand-crafted recursive descent + pratt combination, with a special effort of continuting the parsing if an error is detected.
+We use a boring hand-crafted recursive descent + pratt combination, with a special effort of continuing the parsing if an error is detected.
### Parser Recap
projects / rust.git / blobdiff