<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>docs/dev/syntax.md - fork/rust-analyzer @ master</title>
<meta name="description" content="docs/dev/syntax.md in fork/rust-analyzer at master.">
<meta property="og:title" content="docs/dev/syntax.md - fork/rust-analyzer @ master">
<meta property="og:description" content="docs/dev/syntax.md in fork/rust-analyzer at master.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="master" data-tip="57d03478a01048a759cf04fb8b255dfce5157d0f">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>fork/rust-analyzer</h1>
</div>
<pre class="clone">git clone https://git.julia.blue/fork/rust-analyzer</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">bors</span><span class="commit-message" data-commit="df4ed94f2fb7c16daefa1722657216609f0e8d31">Auto merge of #12722 - jonas-schievink:update-urls, r=jonas-schievink</span><span class="snapshot-sha sha" data-commit="df4ed94f2fb7c16daefa1722657216609f0e8d31">df4ed94f2f</span><time datetime="2022-07-08T13:50:20+00:00" title="2022-07-08 13:50:20 +0000">2022-07-08</time></p>
<header class="topbar"><details class="switcher"><summary>master</summary><div class="menu"><strong>branches</strong><a class="current" href="/fork/rust-analyzer/ref/master/">master</a><strong>tags</strong><a href="/fork/rust-analyzer/ref/2022-06-13/">2022-06-13</a><a href="/fork/rust-analyzer/ref/2022-06-20/">2022-06-20</a><a href="/fork/rust-analyzer/ref/2022-06-27/">2022-06-27</a><a href="/fork/rust-analyzer/ref/2022-07-04/">2022-07-04</a><a href="/fork/rust-analyzer/ref/2022-07-11/">2022-07-11</a><a href="/fork/rust-analyzer/ref/2022-07-18/">2022-07-18</a><a href="/fork/rust-analyzer/ref/2022-07-25/">2022-07-25</a><a href="/fork/rust-analyzer/ref/nightly/">nightly</a><a class="all" href="/fork/rust-analyzer/refs">all refs →</a></div></details><nav class="crumbs"><a href="/fork/rust-analyzer/">rust-analyzer</a> / <a href="/fork/rust-analyzer/ref/master/tree/docs/">docs</a> / <a href="/fork/rust-analyzer/ref/master/tree/docs/dev/">dev</a> / <span class="cur">syntax.md</span></nav>
<span class="view-stats"><span>20.6 KiB</span><span>534 lines</span></span><span class="actions"><a class="raw" href="/fork/rust-analyzer/raw/30e13701383a9a3f091daa20f35ee9bacaad8e56/docs/dev/syntax.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h1>Syntax in rust-analyzer</h1>
<h2>About the guide</h2>
<p>This guide describes the current state of syntax trees and parsing in rust-analyzer as of 2020-01-09 (<a href="https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6">link to commit</a>).</p>
<h2>Source Code</h2>
<p>The things described are implemented in three places</p>
<ul>
<li><a href="https://github.com/rust-analyzer/rowan/tree/v0.9.0">rowan</a> -- a generic library for rowan syntax trees.</li>
<li><a href="https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/ra_syntax">ra_syntax</a> crate inside rust-analyzer which wraps <code>rowan</code> into rust-analyzer specific API.
Nothing in rust-analyzer except this crate knows about <code>rowan</code>.</li>
<li><a href="https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/parser">parser</a> crate parses input tokens into an <code>ra_syntax</code> tree</li>
</ul>
<h2>Design Goals</h2>
<ul>
<li>Syntax trees are lossless, or full fidelity. All comments and whitespace get preserved.</li>
<li>Syntax trees are semantic-less. They describe <em>strictly</em> the structure of a sequence of characters, they don't have hygiene, name resolution or type information attached.</li>
<li>Syntax trees are simple value types. It is possible to create trees for a syntax without any external context.</li>
<li>Syntax trees have intuitive traversal API (parent, children, siblings, etc).</li>
<li>Parsing is lossless (even if the input is invalid, the tree produced by the parser represents it exactly).</li>
<li>Parsing is resilient (even if the input is invalid, parser tries to see as much syntax tree fragments in the input as it can).</li>
<li>Performance is important, it's OK to use <code>unsafe</code> if it means better memory/cpu usage.</li>
<li>Keep the parser and the syntax tree isolated from each other, such that they can vary independently.</li>
</ul>
<h2>Trees</h2>
<h3>Overview</h3>
<p>The syntax tree consists of three layers:</p>
<ul>
<li>GreenNodes</li>
<li>SyntaxNodes (aka RedNode)</li>
<li>AST</li>
</ul>
<p>Of these, only GreenNodes store the actual data, the other two layers are (non-trivial) views into green tree.
Red-green terminology comes from Roslyn (<a href="https://ericlippert.com/2012/06/08/red-green-trees/">link</a>) and gives the name to the <code>rowan</code> library. Green and syntax nodes are defined in rowan, ast is defined in rust-analyzer.</p>
<p>Syntax trees are a semi-transient data structure.
In general, frontend does not keep syntax trees for all files in memory.
Instead, it <em>lowers</em> syntax trees to more compact and rigid representation, which is not full-fidelity, but which can be mapped back to a syntax tree if so desired.</p>
<h3>GreenNode</h3>
<p>GreenNode is a purely-functional tree with arbitrary arity. Conceptually, it is equivalent to the following run of the mill struct:</p>
<pre class="language-rust"><a-at>#</a-at><a-p>[</a-p><a-at>derive</a-at><a-p>(</a-p><a-cr>PartialEq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Eq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Clone</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Copy</a-cr><a-p>)]</a-p>
<a-k>struct</a-k> <a-t>SyntaxKind</a-t><a-p>(</a-p><a-t>u16</a-t><a-p>);</a-p>

<a-at>#</a-at><a-p>[</a-p><a-at>derive</a-at><a-p>(</a-p><a-cr>PartialEq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Eq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Clone</a-cr><a-p>)]</a-p>
<a-k>struct</a-k> <a-t>Node</a-t> <a-p>{</a-p>
    <a-pr>kind</a-pr><a-p>:</a-p> <a-t>SyntaxKind</a-t><a-p>,</a-p>
    <a-pr>text_len</a-pr><a-p>:</a-p> <a-t>usize</a-t><a-p>,</a-p>
    <a-pr>children</a-pr><a-p>:</a-p> <a-t>Vec</a-t><a-p>&lt;</a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>Either</a-t><a-p>&lt;</a-p><a-t>Node</a-t><a-p>,</a-p> <a-t>Token</a-t><a-p>&gt;&gt;&gt;,</a-p>
<a-p>}</a-p>

<a-at>#</a-at><a-p>[</a-p><a-at>derive</a-at><a-p>(</a-p><a-cr>PartialEq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Eq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Clone</a-cr><a-p>)]</a-p>
<a-k>struct</a-k> <a-t>Token</a-t> <a-p>{</a-p>
    <a-pr>kind</a-pr><a-p>:</a-p> <a-t>SyntaxKind</a-t><a-p>,</a-p>
    <a-pr>text</a-pr><a-p>:</a-p> <a-t>String</a-t><a-p>,</a-p>
<a-p>}</a-p></pre>
<p>All the difference between the above sketch and the real implementation are strictly due to optimizations.</p>
<p>Points of note:</p>
<ul>
<li>The tree is untyped. Each node has a "type tag", <code>SyntaxKind</code>.</li>
<li>Interior and leaf nodes are distinguished on the type level.</li>
<li>Trivia and non-trivia tokens are not distinguished on the type level.</li>
<li>Each token carries its full text.</li>
<li>The original text can be recovered by concatenating the texts of all tokens in order.</li>
<li>Accessing a child of particular type (for example, parameter list of a function) generally involves linearly traversing the children, looking for a specific <code>kind</code>.</li>
<li>Modifying the tree is roughly <code>O(depth)</code>.
We don't make special efforts to guarantee that the depth is not linear, but, in practice, syntax trees are branchy and shallow.</li>
<li>If mandatory (grammar wise) node is missing from the input, it's just missing from the tree.</li>
<li>If an extra erroneous input is present, it is wrapped into a node with <code>ERROR</code> kind, and treated just like any other node.</li>
<li>Parser errors are not a part of syntax tree.</li>
</ul>
<p>An input like <code>fn f() { 90 + 2 }</code> might be parsed as</p>
<pre>FN@0..17
  FN_KW@0..2 &quot;fn&quot;
  WHITESPACE@2..3 &quot; &quot;
  NAME@3..4
    IDENT@3..4 &quot;f&quot;
  PARAM_LIST@4..6
    L_PAREN@4..5 &quot;(&quot;
    R_PAREN@5..6 &quot;)&quot;
  WHITESPACE@6..7 &quot; &quot;
  BLOCK_EXPR@7..17
    L_CURLY@7..8 &quot;{&quot;
    WHITESPACE@8..9 &quot; &quot;
    BIN_EXPR@9..15
      LITERAL@9..11
        INT_NUMBER@9..11 &quot;90&quot;
      WHITESPACE@11..12 &quot; &quot;
      PLUS@12..13 &quot;+&quot;
      WHITESPACE@13..14 &quot; &quot;
      LITERAL@14..15
        INT_NUMBER@14..15 &quot;2&quot;
    WHITESPACE@15..16 &quot; &quot;
    R_CURLY@16..17 &quot;}&quot;
</pre>
<h4>Optimizations</h4>
<p>(significant amount of implementation work here was done by <a href="https://github.com/cad97">CAD97</a>).</p>
<p>To reduce the amount of allocations, the GreenNode is a <a href="https://doc.rust-lang.org/reference/dynamically-sized-types.html">DST</a>, which uses a single allocation for header and children. Thus, it is only usable behind a pointer.</p>
<pre>*-----------+------+----------+------------+--------+--------+-----+--------*
| ref_count | kind | text_len | n_children | child1 | child2 | ... | childn |
*-----------+------+----------+------------+--------+--------+-----+--------*
</pre>
<p>To more compactly store the children, we box <em>both</em> interior nodes and tokens, and represent
<code>Either&lt;Arc&lt;Node&gt;, Arc&lt;Token&gt;&gt;</code> as a single pointer with a tag in the last bit.</p>
<p>To avoid allocating EVERY SINGLE TOKEN on the heap, syntax trees use interning.
Because the tree is fully immutable, it's valid to structurally share subtrees.
For example, in <code>1 + 1</code>, there will be a <em>single</em> token for <code>1</code> with ref count 2; the same goes for the <code> </code> whitespace token.
Interior nodes are shared as well (for example in <code>(1 + 1) * (1 + 1)</code>).</p>
<p>Note that, the result of the interning is an <code>Arc&lt;Node&gt;</code>.
That is, it's not an index into interning table, so you don't have to have the table around to do anything with the tree.
Each tree is fully self-contained (although different trees might share parts).
Currently, the interner is created per-file, but it will be easy to use a per-thread or per-some-contex one.</p>
<p>We use a <code>TextSize</code>, a newtyped <code>u32</code>, to store the length of the text.</p>
<p>We currently use <code>SmolStr</code>, a small object optimized string to store text.
This was mostly relevant <em>before</em> we implemented tree interning, to avoid allocating common keywords and identifiers. We should switch to storing text data alongside the interned tokens.</p>
<h4>Alternative designs</h4>
<h5>Dealing with trivia</h5>
<p>In the above model, whitespace is not treated specially.
Another alternative (used by swift and roslyn) is to explicitly divide the set of tokens into trivia and non-trivia tokens, and represent non-trivia tokens as</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>Token</a-t> <a-p>{</a-p>
    <a-pr>kind</a-pr><a-p>:</a-p> <a-t>NonTriviaTokenKind</a-t><a-p>,</a-p>
    <a-pr>text</a-pr><a-p>:</a-p> <a-t>String</a-t><a-p>,</a-p>
    <a-pr>leading_trivia</a-pr><a-p>:</a-p> <a-t>Vec</a-t><a-p>&lt;</a-p><a-t>TriviaToken</a-t><a-p>&gt;,</a-p>
    <a-pr>trailing_trivia</a-pr><a-p>:</a-p> <a-t>Vec</a-t><a-p>&lt;</a-p><a-t>TriviaToken</a-t><a-p>&gt;,</a-p>
<a-p>}</a-p></pre>
<p>The tree then contains only non-trivia tokens.</p>
<p>Another approach (from Dart) is to, in addition to a syntax tree, link all the tokens into a bidirectional link list.
That way, the tree again contains only non-trivia tokens.</p>
<p>Explicit trivia nodes, like in <code>rowan</code>, are used by IntelliJ.</p>
<h5>Accessing Children</h5>
<p>As noted before, accessing a specific child in the node requires a linear traversal of the children (though we can skip tokens, because the tag is encoded in the pointer itself).
It is possible to recover O(1) access with another representation.
We explicitly store optional and missing (required by the grammar, but not present) nodes.
That is, we use <code>Option&lt;Node&gt;</code> for children.
We also remove trivia tokens from the tree.
This way, each child kind generally occupies a fixed position in a parent, and we can use index access to fetch it.
The cost is that we now need to allocate space for all not-present optional nodes.
So, <code>fn foo() {}</code> will have slots for visibility, unsafeness, attributes, abi and return type.</p>
<p>IntelliJ uses linear traversal.
Roslyn and Swift do <code>O(1)</code> access.</p>
<h5>Mutable Trees</h5>
<p>IntelliJ uses mutable trees.
Overall, it creates a lot of additional complexity.
However, the API for <em>editing</em> syntax trees is nice.</p>
<p>For example the assist to move generic bounds to where clause has this code:</p>
<pre class="language-kotlin"> <a-k>for</a-k> <a-v>typeBound</a-v> <a-o>in</a-o> <a-f>typeBounds</a-f> <a-p>{</a-p>
     <a-v>typeBound</a-v><a-p>.</a-p><a-pr>typeParamBounds</a-pr><a-o>?.</a-o><a-f>delete</a-f><a-p>()</a-p>
<a-p>}</a-p></pre>
<p>Modeling this with immutable trees is possible, but annoying.</p>
<h3>Syntax Nodes</h3>
<p>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: <code>fn collect_expressions(file: GreenNode) -&gt; HashSet&lt;GreenNode&gt;</code>.
For the input like</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>main</a-f><a-p>()</a-p> <a-p>{</a-p>
    <a-k>let</a-k> x = <a-co>90i8</a-co><a-p>;</a-p>
    <a-k>let</a-k> x = x + <a-co>2</a-co><a-p>;</a-p>
    <a-k>let</a-k> x = <a-co>90i64</a-co><a-p>;</a-p>
    <a-k>let</a-k> x = x + <a-co>2</a-co><a-p>;</a-p>
<a-p>}</a-p></pre>
<p>both copies of the <code>x + 2</code> expression are representing by equal (and, with interning in mind, actually the same) green nodes.
Green trees just can't differentiate between the two.</p>
<p><code>SyntaxNode</code> adds parent pointers and identify semantics to green nodes.
They can be called cursors or <a href="https://en.wikipedia.org/wiki/Zipper_(data_structure)">zippers</a> (fun fact: zipper is a derivative (as in ′) of a data structure).</p>
<p>Conceptually, a <code>SyntaxNode</code> looks like this:</p>
<pre class="language-rust"><a-k>type</a-k> <a-t>SyntaxNode</a-t> = <a-t>Arc</a-t><a-p>&lt;</a-p><a-t>SyntaxData</a-t><a-p>&gt;;</a-p>

<a-k>struct</a-k> <a-t>SyntaxData</a-t> <a-p>{</a-p>
    <a-pr>offset</a-pr><a-p>:</a-p> <a-t>usize</a-t><a-p>,</a-p>
    <a-pr>parent</a-pr><a-p>:</a-p> <a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;,</a-p>
    <a-pr>green</a-pr><a-p>:</a-p> <a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;,</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>SyntaxNode</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>new_root</a-f><a-p>(</a-p><a-v>root</a-v><a-p>:</a-p> <a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;)</a-p> -&gt; <a-t>SyntaxNode</a-t> <a-p>{</a-p>
        <a-t>Arc</a-t><a-p>::</a-p><a-f>new</a-f><a-p>(</a-p><a-t>SyntaxData</a-t> <a-p>{</a-p>
            <a-pr>offset</a-pr><a-p>:</a-p> <a-co>0</a-co><a-p>,</a-p>
            <a-pr>parent</a-pr><a-p>:</a-p> <a-cr>None</a-cr><a-p>,</a-p>
            <a-pr>green</a-pr><a-p>:</a-p> root<a-p>,</a-p>
        <a-p>})</a-p>
    <a-p>}</a-p>
    <a-k>fn</a-k> <a-f>parent</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>parent</a-pr><a-p>.</a-p><a-f>clone</a-f><a-p>()</a-p>
    <a-p>}</a-p>
    <a-k>fn</a-k> <a-f>children</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-k>impl</a-k> <a-t>Iterator</a-t><a-p>&lt;</a-p><a-t>Item</a-t> = <a-t>SyntaxNode</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-k>let</a-k> <a-k>mut</a-k> offset = <a-v>self</a-v><a-p>.</a-p><a-pr>offset</a-pr><a-p>;</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>green</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>map</a-f><a-p>(</a-p>|green_child| <a-p>{</a-p>
            <a-k>let</a-k> child_offset = offset<a-p>;</a-p>
            offset += green_child<a-p>.</a-p><a-pr>text_len</a-pr><a-p>;</a-p>
            <a-t>Arc</a-t><a-p>::</a-p><a-f>new</a-f><a-p>(</a-p><a-t>SyntaxData</a-t> <a-p>{</a-p>
                <a-pr>offset</a-pr><a-p>:</a-p> child_offset<a-p>,</a-p>
                <a-pr>parent</a-pr><a-p>:</a-p> <a-f>Some</a-f><a-p>(</a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>clone</a-f><a-p>(</a-p><a-v>self</a-v><a-p>)),</a-p>
                <a-pr>green</a-pr><a-p>:</a-p> <a-t>Arc</a-t><a-p>::</a-p><a-f>clone</a-f><a-p>(</a-p>green_child<a-p>),</a-p>
            <a-p>})</a-p>
        <a-p>})</a-p>
    <a-p>}</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>PartialEq</a-t> <a-k>for</a-k> <a-t>SyntaxNode</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>eq</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>,</a-p> <a-v>other</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-t>SyntaxNode</a-t><a-p>)</a-p> -&gt; <a-t>bool</a-t> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>offset</a-pr> == other<a-p>.</a-p><a-pr>offset</a-pr>
            &amp;&amp; <a-t>Arc</a-t><a-p>::</a-p><a-f>ptr_eq</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>.</a-p><a-pr>green</a-pr><a-p>,</a-p> <a-o>&amp;</a-o>other<a-p>.</a-p><a-pr>green</a-pr><a-p>)</a-p>
    <a-p>}</a-p>
<a-p>}</a-p></pre>
<p>Points of note:</p>
<ul>
<li>SyntaxNode remembers its parent node (and, transitively, the path to the root of the tree)</li>
<li>SyntaxNode knows its <em>absolute</em> text offset in the whole file</li>
<li>Equality is based on identity. Comparing nodes from different trees does not make sense.</li>
</ul>
<h4>Optimization</h4>
<p>The reality is different though :-)
Traversal of trees is a common operation, and it makes sense to optimize it.
In particular, the above code allocates and does atomic operations during a traversal.</p>
<p>To get rid of atomics, <code>rowan</code> uses non thread-safe <code>Rc</code>.
This is OK because trees traversals mostly (always, in case of rust-analyzer) run on a single thread. If you need to send a <code>SyntaxNode</code> to another thread, you can send a pair of <strong>root</strong><code>GreenNode</code> (which is thread safe) and a <code>Range&lt;usize&gt;</code>.
The other thread can restore the <code>SyntaxNode</code> 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 <code>SyntaxNode</code>.
That is, a data structure that holds a <code>(GreenNode, Range&lt;usize&gt;)</code> will be <code>Sync</code>.
However, rust-analyzer goes even further.
It treats trees as semi-transient and instead of storing a <code>GreenNode</code>, it generally stores just the id of the file from which the tree originated: <code>(FileId, Range&lt;usize&gt;)</code>.
The <code>SyntaxNode</code> 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.</p>
<p>Additionally, only the root <code>SyntaxNode</code> owns an <code>Arc</code> to the (root) <code>GreenNode</code>.
All other <code>SyntaxNode</code>s point to corresponding <code>GreenNode</code>s with a raw pointer.
They also point to the parent (and, consequently, to the root) with an owning <code>Rc</code>, so this is sound.
In other words, one needs <em>one</em> arc bump when initiating a traversal.</p>
<p>To get rid of allocations, <code>rowan</code> takes advantage of <code>SyntaxNode: !Sync</code> and uses a thread-local free list of <code>SyntaxNode</code>s.
In a typical traversal, you only directly hold a few <code>SyntaxNode</code>s at a time (and their ancestors indirectly), so a free list proportional to the depth of the tree removes all allocations in a typical case.</p>
<p>So, while traversal is not exactly incrementing a pointer, it's still pretty cheap: TLS + rc bump!</p>
<p>Traversal also yields (cheap) owned nodes, which improves ergonomics quite a bit.</p>
<h4>Alternative Designs</h4>
<h5>Memoized RedNodes</h5>
<p>C# and Swift follow the design where the red nodes are memoized, which would look roughly like this in Rust:</p>
<pre class="language-rust"><a-k>type</a-k> <a-t>SyntaxNode</a-t> = <a-t>Arc</a-t><a-p>&lt;</a-p><a-t>SyntaxData</a-t><a-p>&gt;;</a-p>

<a-k>struct</a-k> <a-t>SyntaxData</a-t> <a-p>{</a-p>
    <a-pr>offset</a-pr><a-p>:</a-p> <a-t>usize</a-t><a-p>,</a-p>
    <a-pr>parent</a-pr><a-p>:</a-p> <a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;,</a-p>
    <a-pr>green</a-pr><a-p>:</a-p> <a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;,</a-p>
    <a-pr>children</a-pr><a-p>:</a-p> <a-t>Vec</a-t><a-p>&lt;</a-p><a-t>OnceCell</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;&gt;,</a-p>
<a-p>}</a-p></pre>
<p>This allows using true pointer equality for comparison of identities of <code>SyntaxNodes</code>.
rust-analyzer used to have this design as well, but we've since switched to cursors.
The main problem with memoizing the red nodes is that it more than doubles the memory requirements for fully realized syntax trees.
In contrast, cursors generally retain only a path to the root.
C# combats increased memory usage by using weak references.</p>
<h3>AST</h3>
<p><code>GreenTree</code>s are untyped and homogeneous, because it makes accommodating error nodes, arbitrary whitespace and comments natural, and because it makes possible to write generic tree traversals.
However, when working with a specific node, like a function definition, one would want a strongly typed API.</p>
<p>This is what is provided by the AST layer. AST nodes are transparent wrappers over untyped syntax nodes:</p>
<pre class="language-rust"><a-k>pub</a-k> <a-k>trait</a-k> <a-t>AstNode</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>cast</a-f><a-p>(</a-p><a-v>syntax</a-v><a-p>:</a-p> <a-t>SyntaxNode</a-t><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>Self</a-t><a-p>&gt;</a-p>
    <a-k>where</a-k>
        <a-t>Self</a-t><a-p>:</a-p> <a-t>Sized</a-t><a-p>;</a-p>

    <a-k>fn</a-k> <a-f>syntax</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-o>&amp;</a-o><a-t>SyntaxNode</a-t><a-p>;</a-p>
<a-p>}</a-p></pre>
<p>Concrete nodes are generated (there are 117 of them), and look roughly like this:</p>
<pre class="language-rust"><a-at>#</a-at><a-p>[</a-p><a-at>derive</a-at><a-p>(</a-p><a-cr>Debug</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Clone</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>PartialEq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Eq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Hash</a-cr><a-p>)]</a-p>
<a-k>pub</a-k> <a-k>struct</a-k> <a-t>FnDef</a-t> <a-p>{</a-p>
    <a-pr>syntax</a-pr><a-p>:</a-p> <a-t>SyntaxNode</a-t><a-p>,</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>AstNode</a-t> <a-k>for</a-k> <a-t>FnDef</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>cast</a-f><a-p>(</a-p><a-v>syntax</a-v><a-p>:</a-p> <a-t>SyntaxNode</a-t><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>Self</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-k>match</a-k> kind <a-p>{</a-p>
            <a-cr>FN</a-cr> =&gt; <a-f>Some</a-f><a-p>(</a-p><a-t>FnDef</a-t> <a-p>{</a-p> syntax <a-p>}),</a-p>
            _ =&gt; <a-cr>None</a-cr><a-p>,</a-p>
        <a-p>}</a-p>
    <a-p>}</a-p>
    <a-k>fn</a-k> <a-f>syntax</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-o>&amp;</a-o><a-t>SyntaxNode</a-t> <a-p>{</a-p>
        <a-o>&amp;</a-o><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr>
    <a-p>}</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>FnDef</a-t> <a-p>{</a-p>
    <a-k>pub</a-k> <a-k>fn</a-k> <a-f>param_list</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>ParamList</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>ParamList</a-t><a-p>::</a-p>cast<a-p>)</a-p>
    <a-p>}</a-p>
    <a-k>pub</a-k> <a-k>fn</a-k> <a-f>ret_type</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>RetType</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>RetType</a-t><a-p>::</a-p>cast<a-p>)</a-p>
    <a-p>}</a-p>
    <a-k>pub</a-k> <a-k>fn</a-k> <a-f>body</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>BlockExpr</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>BlockExpr</a-t><a-p>::</a-p>cast<a-p>)</a-p>
    <a-p>}</a-p>
    <a-c>// ...</a-c>
<a-p>}</a-p></pre>
<p>Variants like expressions, patterns or items are modeled with <code>enum</code>s, which also implement <code>AstNode</code>:</p>
<pre class="language-rust"><a-at>#</a-at><a-p>[</a-p><a-at>derive</a-at><a-p>(</a-p><a-cr>Debug</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Clone</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>PartialEq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Eq</a-cr><a-p>,</a-p><a-at> </a-at><a-cr>Hash</a-cr><a-p>)]</a-p>
<a-k>pub</a-k> <a-k>enum</a-k> <a-t>AssocItem</a-t> <a-p>{</a-p>
    <a-cr>FnDef</a-cr><a-p>(</a-p><a-t>FnDef</a-t><a-p>),</a-p>
    <a-cr>TypeAliasDef</a-cr><a-p>(</a-p><a-t>TypeAliasDef</a-t><a-p>),</a-p>
    <a-cr>ConstDef</a-cr><a-p>(</a-p><a-t>ConstDef</a-t><a-p>),</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>AstNode</a-t> <a-k>for</a-k> <a-t>AssocItem</a-t> <a-p>{</a-p>
    ...
<a-p>}</a-p></pre>
<p>Shared AST substructures are modeled via (object safe) traits:</p>
<pre class="language-rust"><a-k>trait</a-k> <a-t>HasVisibility</a-t><a-p>:</a-p> <a-t>AstNode</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>visibility</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>Visibility</a-t><a-p>&gt;;</a-p>
<a-p>}</a-p>

<a-k>impl</a-k> <a-t>HasVisibility</a-t> <a-k>for</a-k> <a-t>FnDef</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>visibility</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Option</a-t><a-p>&lt;</a-p><a-t>Visibility</a-t><a-p>&gt;</a-p> <a-p>{</a-p>
        <a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>Visibility</a-t><a-p>::</a-p>cast<a-p>)</a-p>
    <a-p>}</a-p>
<a-p>}</a-p></pre>
<p>Points of note:</p>
<ul>
<li>Like <code>SyntaxNode</code>s, AST nodes are cheap to clone pointer-sized owned values.</li>
<li>All "fields" are optional, to accommodate incomplete and/or erroneous source code.</li>
<li>It's always possible to go from an ast node to an untyped <code>SyntaxNode</code>.</li>
<li>It's possible to go in the opposite direction with a checked cast.</li>
<li><code>enum</code>s allow modeling of arbitrary intersecting subsets of AST types.</li>
<li>Most of rust-analyzer works with the ast layer, with notable exceptions of:
<ul>
<li>macro expansion, which needs access to raw tokens and works with <code>SyntaxNode</code>s</li>
<li>some IDE-specific features like syntax highlighting are more conveniently implemented over a homogeneous <code>SyntaxNode</code> tree</li>
</ul>
</li>
</ul>
<h4>Alternative Designs</h4>
<h5>Semantic Full AST</h5>
<p>In IntelliJ the AST layer (dubbed <strong>P</strong>rogram <strong>S</strong>tructure <strong>I</strong>nterface) can have semantics attached, and is usually backed by either syntax tree, indices, or metadata from compiled libraries.
The backend for PSI can change dynamically.</p>
<h3>Syntax Tree Recap</h3>
<p>At its core, the syntax tree is a purely functional n-ary tree, which stores text at the leaf nodes and node "kinds" at all nodes.
A cursor layer is added on top, which gives owned, cheap to clone nodes with identity semantics, parent links and absolute offsets.
An AST layer is added on top, which reifies each node <code>Kind</code> as a separate Rust type with the corresponding API.</p>
<h2>Parsing</h2>
<p>The (green) tree is constructed by a DFS "traversal" of the desired tree structure:</p>
<pre class="language-rust"><a-k>pub</a-k> <a-k>struct</a-k> <a-t>GreenNodeBuilder</a-t> <a-p>{</a-p> ... <a-p>}</a-p>

<a-k>impl</a-k> <a-t>GreenNodeBuilder</a-t> <a-p>{</a-p>
    <a-k>pub</a-k> <a-k>fn</a-k> <a-f>new</a-f><a-p>()</a-p> -&gt; <a-t>GreenNodeBuilder</a-t> <a-p>{</a-p> ..<a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>

    </a-pr><a-k>pub</a-k><a-pr> </a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>token</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-pr> </a-pr><a-v>self</a-v><a-p>,</a-p><a-pr> </a-pr><a-v>kind</a-v><a-p>:</a-p><a-pr> </a-pr><a-t>SyntaxKind</a-t><a-p>,</a-p><a-pr> </a-pr><a-v>text</a-v><a-p>:</a-p><a-pr> </a-pr><a-o>&amp;</a-o><a-t>str</a-t><a-p>)</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr> ..</a-pr><a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>

    </a-pr><a-k>pub</a-k><a-pr> </a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>start_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-pr> </a-pr><a-v>self</a-v><a-p>,</a-p><a-pr> </a-pr><a-v>kind</a-v><a-p>:</a-p><a-pr> </a-pr><a-t>SyntaxKind</a-t><a-p>)</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr> ..</a-pr><a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>
    </a-pr><a-k>pub</a-k><a-pr> </a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>finish_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-pr> </a-pr><a-v>self</a-v><a-p>)</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr> ..</a-pr><a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>

    </a-pr><a-k>pub</a-k><a-pr> </a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>finish</a-f><a-p>(</a-p><a-v>self</a-v><a-p>)</a-p><a-pr> -&gt; </a-pr><a-t>GreenNode</a-t><a-pr> </a-pr><a-p>{</a-p><a-pr> ..</a-pr><a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>
</a-pr><a-p>}</a-p></pre>
<p>The parser, ultimately, needs to invoke the <code>GreenNodeBuilder</code>.
There are two principal sources of inputs for the parser:</p>
<ul>
<li>source text, which contains trivia tokens (whitespace and comments)</li>
<li>token trees from macros, which lack trivia</li>
</ul>
<p>Additionally, input tokens do not correspond 1-to-1 with output tokens.
For example, two consecutive <code>&gt;</code> tokens might be glued, by the parser, into a single <code>&gt;&gt;</code>.</p>
<p>For these reasons, the parser crate defines a callback interfaces for both input tokens and output trees.
The explicit glue layer then bridges various gaps.</p>
<p>The parser interface looks like this:</p>
<pre class="language-rust"><a-k>pub</a-k> <a-k>struct</a-k> <a-t>Token</a-t> <a-p>{</a-p>
    <a-k>pub</a-k> <a-pr>kind</a-pr><a-p>:</a-p> <a-t>SyntaxKind</a-t><a-p>,</a-p>
    <a-k>pub</a-k> <a-pr>is_joined_to_next</a-pr><a-p>:</a-p> <a-t>bool</a-t><a-p>,</a-p>
<a-p>}</a-p>

<a-k>pub</a-k> <a-k>trait</a-k> <a-t>TokenSource</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>current</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>)</a-p> -&gt; <a-t>Token</a-t><a-p>;</a-p>
    <a-k>fn</a-k> <a-f>lookahead_nth</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>,</a-p> <a-v>n</a-v><a-p>:</a-p> <a-t>usize</a-t><a-p>)</a-p> -&gt; <a-t>Token</a-t><a-p>;</a-p>
    <a-k>fn</a-k> <a-f>is_keyword</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>,</a-p> <a-v>kw</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-t>str</a-t><a-p>)</a-p> -&gt; <a-t>bool</a-t><a-p>;</a-p>

    <a-k>fn</a-k> <a-f>bump</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-v>self</a-v><a-p>);</a-p>
<a-p>}</a-p>

<a-k>pub</a-k> <a-k>trait</a-k> <a-t>TreeSink</a-t> <a-p>{</a-p>
    <a-k>fn</a-k> <a-f>token</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-v>self</a-v><a-p>,</a-p> <a-v>kind</a-v><a-p>:</a-p> <a-t>SyntaxKind</a-t><a-p>,</a-p> <a-v>n_tokens</a-v><a-p>:</a-p> <a-t>u8</a-t><a-p>);</a-p>

    <a-k>fn</a-k> <a-f>start_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-v>self</a-v><a-p>,</a-p> <a-v>kind</a-v><a-p>:</a-p> <a-t>SyntaxKind</a-t><a-p>);</a-p>
    <a-k>fn</a-k> <a-f>finish_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-v>self</a-v><a-p>);</a-p>

    <a-k>fn</a-k> <a-f>error</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-v>self</a-v><a-p>,</a-p> <a-v>error</a-v><a-p>:</a-p> <a-t>ParseError</a-t><a-p>);</a-p>
<a-p>}</a-p>

<a-k>pub</a-k> <a-k>fn</a-k> <a-f>parse</a-f><a-p>(</a-p>
    <a-v>token_source</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-k>dyn</a-k> <a-t>TokenSource</a-t><a-p>,</a-p>
    <a-v>tree_sink</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-k>dyn</a-k> <a-t>TreeSink</a-t><a-p>,</a-p>
<a-p>)</a-p> <a-p>{</a-p> ..<a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p></pre>
<p>Points of note:</p>
<ul>
<li>The parser and the syntax tree are independent, they live in different crates neither of which depends on the other.</li>
<li>The parser doesn't know anything about textual contents of the tokens, with an isolated hack for checking contextual keywords.</li>
<li>For gluing tokens, the <code>TreeSink::token</code> might advance further than one atomic token ahead.</li>
</ul>
<h3>Reporting Syntax Errors</h3>
<p>Syntax errors are not stored directly in the tree.
The primary motivation for this is that syntax tree is not necessary produced by the parser, it may also be assembled manually from pieces (which happens all the time in refactorings).
Instead, parser reports errors to an error sink, which stores them in a <code>Vec</code>.
If possible, errors are not reported during parsing and are postponed for a separate validation step.
For example, parser accepts visibility modifiers on trait methods, but then a separate tree traversal flags all such visibilities as erroneous.</p>
<h3>Macros</h3>
<p>The primary difficulty with macros is that individual tokens have identities, which need to be preserved in the syntax tree for hygiene purposes.
This is handled by the <code>TreeSink</code> layer.
Specifically, <code>TreeSink</code> constructs the tree in lockstep with draining the original token stream.
In the process, it records which tokens of the tree correspond to which tokens of the input, by using text ranges to identify syntax tokens.
The end result is that parsing an expanded code yields a syntax tree and a mapping of text-ranges of the tree to original tokens.</p>
<p>To deal with precedence in cases like <code>$expr * 1</code>, we use special invisible parenthesis, which are explicitly handled by the parser</p>
<h3>Whitespace &amp; Comments</h3>
<p>Parser does not see whitespace nodes.
Instead, they are attached to the tree in the <code>TreeSink</code> layer.</p>
<p>For example, in</p>
<pre class="language-rust"><a-c>// non doc comment</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>()</a-p> <a-p>{}</a-p></pre>
<p>the comment will be (heuristically) made a child of function node.</p>
<h3>Incremental Reparse</h3>
<p>Green trees are cheap to modify, so incremental reparse works by patching a previous tree, without maintaining any additional state.
The reparse is based on heuristic: we try to contain a change to a single <code>{}</code> block, and reparse only this block.
To do this, we maintain the invariant that, even for invalid code, curly braces are always paired correctly.</p>
<p>In practice, incremental reparsing doesn't actually matter much for IDE use-cases, parsing from scratch seems to be fast enough.</p>
<h3>Parsing Algorithm</h3>
<p>We use a boring hand-crafted recursive descent + pratt combination, with a special effort of continuing the parsing if an error is detected.</p>
<h3>Parser Recap</h3>
<p>Parser itself defines traits for token sequence input and syntax tree output.
It doesn't care about where the tokens come from, and how the resulting syntax tree looks like.</p>
</section><div class="code-panel"><pre class="code src language-markdown"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"><a-p>#</a-p> <a-tt>Syntax in rust-analyzer</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text"><a-p>##</a-p> <a-tt>About the guide</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text">This guide describes the current state of syntax trees and parsing in rust-analyzer as of 2020-01-09 ([link to commit](https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6)).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text"><a-p>##</a-p> <a-tt>Source Code</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text">The things described are implemented in three places</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text"><a-p>* </a-p>[rowan](https://github.com/rust-analyzer/rowan/tree/v0.9.0) -- a generic library for rowan syntax trees.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text"><a-p>* </a-p>[ra_syntax](https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/ra_syntax) crate inside rust-analyzer which wraps `rowan` into rust-analyzer specific API.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text"><a-p>  </a-p>Nothing in rust-analyzer except this crate knows about `rowan`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text"><a-p>* </a-p>[parser](https://github.com/rust-lang/rust-analyzer/tree/cf5bdf464cad7ceb9a67e07985a3f4d3799ec0b6/crates/parser) crate parses input tokens into an `ra_syntax` tree</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text"><a-p>## </a-p><a-tt>Design Goals</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text"><a-p>* Syntax trees are lossless, or full fidelity. All comments and whitespace get preserved.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text"><a-p>* Syntax trees are semantic-less. They describe *strictly* the structure of a sequence of characters, they don&#39;t have hygiene, name resolution or type information attached.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text"><a-p>* Syntax trees are simple value types. It is possible to create trees for a syntax without any external context.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text"><a-p>* Syntax trees have intuitive traversal API (parent, children, siblings, etc).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text"><a-p>* Parsing is lossless (even if the input is invalid, the tree produced by the parser represents it exactly).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text"><a-p>* Parsing is resilient (even if the input is invalid, parser tries to see as much syntax tree fragments in the input as it can).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text"><a-p>* Performance is important, it&#39;s OK to use `unsafe` if it means better memory/cpu usage.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text"><a-p>* Keep the parser and the syntax tree isolated from each other, such that they can vary independently.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text"><a-p>## </a-p><a-tt>Trees</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"><a-p>### </a-p><a-tt>Overview</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text"><a-p>The syntax tree consists of three layers:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text"><a-p>* GreenNodes</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text"><a-p>* SyntaxNodes (aka RedNode)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text"><a-p>* AST</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L37" href="#L37">37</a><span class="code-text"><a-p>Of these, only GreenNodes store the actual data, the other two layers are (non-trivial) views into green tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L38" href="#L38">38</a><span class="code-text"><a-p>Red-green terminology comes from Roslyn ([link](https://ericlippert.com/2012/06/08/red-green-trees/)) and gives the name to the `rowan` library. Green and syntax nodes are defined in rowan, ast is defined in rust-analyzer.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text"><a-p>Syntax trees are a semi-transient data structure.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text"><a-p>In general, frontend does not keep syntax trees for all files in memory.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text"><a-p>Instead, it *lowers* syntax trees to more compact and rigid representation, which is not full-fidelity, but which can be mapped back to a syntax tree if so desired.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text"><a-p>### </a-p><a-tt>GreenNode</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text"><a-p>GreenNode is a purely-functional tree with arbitrary arity. Conceptually, it is equivalent to the following run of the mill struct:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text"><a-p>#[derive(</a-p><a-cr>PartialEq</a-cr><a-p>, </a-p><a-cr>Eq</a-cr><a-p>, </a-p><a-cr>Clone</a-cr><a-p>, </a-p><a-cr>Copy</a-cr><a-p>)]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text"><a-p>struct </a-p><a-t>SyntaxKind</a-t><a-p>(</a-p><a-t>u16</a-t><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text"><a-p>#[derive(</a-p><a-cr>PartialEq</a-cr><a-p>, </a-p><a-cr>Eq</a-cr><a-p>, </a-p><a-cr>Clone</a-cr><a-p>)]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text"><a-p>struct </a-p><a-t>Node</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text"><a-p>    </a-p><a-pr>kind</a-pr><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L56" href="#L56">56</a><span class="code-text"><a-p>    </a-p><a-pr>text_len</a-pr><a-p>: </a-p><a-t>usize</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L57" href="#L57">57</a><span class="code-text"><a-p>    </a-p><a-pr>children</a-pr><a-p>: </a-p><a-t>Vec</a-t><a-p>&lt;</a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>Either</a-t><a-p>&lt;</a-p><a-t>Node</a-t><a-p>, </a-p><a-t>Token</a-t><a-p>&gt;&gt;&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text"><a-p>#[derive(</a-p><a-cr>PartialEq</a-cr><a-p>, </a-p><a-cr>Eq</a-cr><a-p>, </a-p><a-cr>Clone</a-cr><a-p>)]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text"><a-p>struct </a-p><a-t>Token</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text"><a-p>    </a-p><a-pr>kind</a-pr><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L63" href="#L63">63</a><span class="code-text"><a-p>    </a-p><a-pr>text</a-pr><a-p>: </a-p><a-t>String</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L64" href="#L64">64</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L65" href="#L65">65</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L66" href="#L66">66</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L67" href="#L67">67</a><span class="code-text"><a-p>All the difference between the above sketch and the real implementation are strictly due to optimizations.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L68" href="#L68">68</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L69" href="#L69">69</a><span class="code-text"><a-p>Points of note:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L70" href="#L70">70</a><span class="code-text"><a-p>* The tree is untyped. Each node has a &quot;type tag&quot;, `SyntaxKind`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L71" href="#L71">71</a><span class="code-text"><a-p>* Interior and leaf nodes are distinguished on the type level.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L72" href="#L72">72</a><span class="code-text"><a-p>* Trivia and non-trivia tokens are not distinguished on the type level.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L73" href="#L73">73</a><span class="code-text"><a-p>* Each token carries its full text.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L74" href="#L74">74</a><span class="code-text"><a-p>* The original text can be recovered by concatenating the texts of all tokens in order.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L75" href="#L75">75</a><span class="code-text"><a-p>* Accessing a child of particular type (for example, parameter list of a function) generally involves linearly traversing the children, looking for a specific `kind`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L76" href="#L76">76</a><span class="code-text"><a-p>* Modifying the tree is roughly `O(depth)`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L77" href="#L77">77</a><span class="code-text"><a-p>  We don&#39;t make special efforts to guarantee that the depth is not linear, but, in practice, syntax trees are branchy and shallow.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L78" href="#L78">78</a><span class="code-text"><a-p>* If mandatory (grammar wise) node is missing from the input, it&#39;s just missing from the tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L79" href="#L79">79</a><span class="code-text"><a-p>* If an extra erroneous input is present, it is wrapped into a node with `ERROR` kind, and treated just like any other node.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L80" href="#L80">80</a><span class="code-text"><a-p>* Parser errors are not a part of syntax tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L81" href="#L81">81</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L82" href="#L82">82</a><span class="code-text"><a-p>An input like `fn f() { 90 + 2 }` might be parsed as</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L83" href="#L83">83</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L84" href="#L84">84</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L85" href="#L85">85</a><span class="code-text"><a-p>FN@0..17</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L86" href="#L86">86</a><span class="code-text"><a-p>  FN_KW@0..2 &quot;fn&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L87" href="#L87">87</a><span class="code-text"><a-p>  WHITESPACE@2..3 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L88" href="#L88">88</a><span class="code-text"><a-p>  NAME@3..4</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L89" href="#L89">89</a><span class="code-text"><a-p>    IDENT@3..4 &quot;f&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L90" href="#L90">90</a><span class="code-text"><a-p>  PARAM_LIST@4..6</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L91" href="#L91">91</a><span class="code-text"><a-p>    L_PAREN@4..5 &quot;(&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L92" href="#L92">92</a><span class="code-text"><a-p>    R_PAREN@5..6 &quot;)&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L93" href="#L93">93</a><span class="code-text"><a-p>  WHITESPACE@6..7 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L94" href="#L94">94</a><span class="code-text"><a-p>  BLOCK_EXPR@7..17</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L95" href="#L95">95</a><span class="code-text"><a-p>    L_CURLY@7..8 &quot;{&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L96" href="#L96">96</a><span class="code-text"><a-p>    WHITESPACE@8..9 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L97" href="#L97">97</a><span class="code-text"><a-p>    BIN_EXPR@9..15</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L98" href="#L98">98</a><span class="code-text"><a-p>      LITERAL@9..11</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L99" href="#L99">99</a><span class="code-text"><a-p>        INT_NUMBER@9..11 &quot;90&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L100" href="#L100">100</a><span class="code-text"><a-p>      WHITESPACE@11..12 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L101" href="#L101">101</a><span class="code-text"><a-p>      PLUS@12..13 &quot;+&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L102" href="#L102">102</a><span class="code-text"><a-p>      WHITESPACE@13..14 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L103" href="#L103">103</a><span class="code-text"><a-p>      LITERAL@14..15</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L104" href="#L104">104</a><span class="code-text"><a-p>        INT_NUMBER@14..15 &quot;2&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L105" href="#L105">105</a><span class="code-text"><a-p>    WHITESPACE@15..16 &quot; &quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L106" href="#L106">106</a><span class="code-text"><a-p>    R_CURLY@16..17 &quot;}&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L107" href="#L107">107</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L108" href="#L108">108</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L109" href="#L109">109</a><span class="code-text"><a-p>#### </a-p><a-tt>Optimizations</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L110" href="#L110">110</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L111" href="#L111">111</a><span class="code-text"><a-p>(significant amount of implementation work here was done by [CAD97](https://github.com/cad97)).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L112" href="#L112">112</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L113" href="#L113">113</a><span class="code-text"><a-p>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.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L114" href="#L114">114</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L115" href="#L115">115</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L116" href="#L116">116</a><span class="code-text"><a-p>*-----------+------+----------+------------+--------+--------+-----+--------*</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L117" href="#L117">117</a><span class="code-text"><a-p>| ref_count | kind | text_len | n_children | child1 | child2 | ... | childn |</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L118" href="#L118">118</a><span class="code-text"><a-p>*-----------+------+----------+------------+--------+--------+-----+--------*</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L119" href="#L119">119</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L120" href="#L120">120</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L121" href="#L121">121</a><span class="code-text"><a-p>To more compactly store the children, we box *both* interior nodes and tokens, and represent</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L122" href="#L122">122</a><span class="code-text"><a-p>`Either&lt;Arc&lt;Node&gt;, Arc&lt;Token&gt;&gt;` as a single pointer with a tag in the last bit.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L123" href="#L123">123</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L124" href="#L124">124</a><span class="code-text"><a-p>To avoid allocating EVERY SINGLE TOKEN on the heap, syntax trees use interning.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L125" href="#L125">125</a><span class="code-text"><a-p>Because the tree is fully immutable, it&#39;s valid to structurally share subtrees.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L126" href="#L126">126</a><span class="code-text"><a-p>For example, in `1 + 1`, there will be a *single* token for `1` with ref count 2; the same goes for the ` ` whitespace token.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L127" href="#L127">127</a><span class="code-text"><a-p>Interior nodes are shared as well (for example in `(1 + 1) * (1 + 1)`).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L128" href="#L128">128</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L129" href="#L129">129</a><span class="code-text"><a-p>Note that, the result of the interning is an `Arc&lt;Node&gt;`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L130" href="#L130">130</a><span class="code-text"><a-p>That is, it&#39;s not an index into interning table, so you don&#39;t have to have the table around to do anything with the tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L131" href="#L131">131</a><span class="code-text"><a-p>Each tree is fully self-contained (although different trees might share parts).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L132" href="#L132">132</a><span class="code-text"><a-p>Currently, the interner is created per-file, but it will be easy to use a per-thread or per-some-contex one.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L133" href="#L133">133</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L134" href="#L134">134</a><span class="code-text"><a-p>We use a `TextSize`, a newtyped `u32`, to store the length of the text.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L135" href="#L135">135</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L136" href="#L136">136</a><span class="code-text"><a-p>We currently use `SmolStr`, a small object optimized string to store text.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L137" href="#L137">137</a><span class="code-text"><a-p>This was mostly relevant *before* we implemented tree interning, to avoid allocating common keywords and identifiers. We should switch to storing text data alongside the interned tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L138" href="#L138">138</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L139" href="#L139">139</a><span class="code-text"><a-p>#### </a-p><a-tt>Alternative designs</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L140" href="#L140">140</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L141" href="#L141">141</a><span class="code-text"><a-p>##### </a-p><a-tt>Dealing with trivia</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L142" href="#L142">142</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L143" href="#L143">143</a><span class="code-text"><a-p>In the above model, whitespace is not treated specially.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L144" href="#L144">144</a><span class="code-text"><a-p>Another alternative (used by swift and roslyn) is to explicitly divide the set of tokens into trivia and non-trivia tokens, and represent non-trivia tokens as</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L145" href="#L145">145</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L146" href="#L146">146</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L147" href="#L147">147</a><span class="code-text"><a-p>struct </a-p><a-t>Token</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L148" href="#L148">148</a><span class="code-text"><a-p>    </a-p><a-pr>kind</a-pr><a-p>: </a-p><a-t>NonTriviaTokenKind</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L149" href="#L149">149</a><span class="code-text"><a-p>    </a-p><a-pr>text</a-pr><a-p>: </a-p><a-t>String</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L150" href="#L150">150</a><span class="code-text"><a-p>    </a-p><a-pr>leading_trivia</a-pr><a-p>: </a-p><a-t>Vec</a-t><a-p>&lt;</a-p><a-t>TriviaToken</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L151" href="#L151">151</a><span class="code-text"><a-p>    </a-p><a-pr>trailing_trivia</a-pr><a-p>: </a-p><a-t>Vec</a-t><a-p>&lt;</a-p><a-t>TriviaToken</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L152" href="#L152">152</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L153" href="#L153">153</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L154" href="#L154">154</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L155" href="#L155">155</a><span class="code-text"><a-p>The tree then contains only non-trivia tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L156" href="#L156">156</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L157" href="#L157">157</a><span class="code-text"><a-p>Another approach (from Dart) is to, in addition to a syntax tree, link all the tokens into a bidirectional link list.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L158" href="#L158">158</a><span class="code-text"><a-p>That way, the tree again contains only non-trivia tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L159" href="#L159">159</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L160" href="#L160">160</a><span class="code-text"><a-p>Explicit trivia nodes, like in `rowan`, are used by IntelliJ.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L161" href="#L161">161</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L162" href="#L162">162</a><span class="code-text"><a-p>##### </a-p><a-tt>Accessing Children</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L163" href="#L163">163</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L164" href="#L164">164</a><span class="code-text"><a-p>As noted before, accessing a specific child in the node requires a linear traversal of the children (though we can skip tokens, because the tag is encoded in the pointer itself).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L165" href="#L165">165</a><span class="code-text"><a-p>It is possible to recover O(1) access with another representation.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L166" href="#L166">166</a><span class="code-text"><a-p>We explicitly store optional and missing (required by the grammar, but not present) nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L167" href="#L167">167</a><span class="code-text"><a-p>That is, we use `Option&lt;Node&gt;` for children.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L168" href="#L168">168</a><span class="code-text"><a-p>We also remove trivia tokens from the tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L169" href="#L169">169</a><span class="code-text"><a-p>This way, each child kind generally occupies a fixed position in a parent, and we can use index access to fetch it.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L170" href="#L170">170</a><span class="code-text"><a-p>The cost is that we now need to allocate space for all not-present optional nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L171" href="#L171">171</a><span class="code-text"><a-p>So, `fn foo() {}` will have slots for visibility, unsafeness, attributes, abi and return type.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L172" href="#L172">172</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L173" href="#L173">173</a><span class="code-text"><a-p>IntelliJ uses linear traversal.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L174" href="#L174">174</a><span class="code-text"><a-p>Roslyn and Swift do `O(1)` access.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L175" href="#L175">175</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L176" href="#L176">176</a><span class="code-text"><a-p>##### </a-p><a-tt>Mutable Trees</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L177" href="#L177">177</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L178" href="#L178">178</a><span class="code-text"><a-p>IntelliJ uses mutable trees.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L179" href="#L179">179</a><span class="code-text"><a-p>Overall, it creates a lot of additional complexity.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L180" href="#L180">180</a><span class="code-text"><a-p>However, the API for *editing* syntax trees is nice.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L181" href="#L181">181</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L182" href="#L182">182</a><span class="code-text"><a-p>For example the assist to move generic bounds to where clause has this code:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L183" href="#L183">183</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L184" href="#L184">184</a><span class="code-text"><a-p>```</a-p><a-tl>kotlin</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L185" href="#L185">185</a><span class="code-text"><a-p> </a-p><a-k>for</a-k><a-p> </a-p><a-v>typeBound</a-v><a-p> </a-p><a-o>in</a-o><a-p> </a-p><a-f>typeBounds</a-f><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L186" href="#L186">186</a><span class="code-text"><a-p>     </a-p><a-v>typeBound</a-v><a-p>.</a-p><a-pr>typeParamBounds</a-pr><a-o>?.</a-o><a-f>delete</a-f><a-p>()</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L187" href="#L187">187</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L188" href="#L188">188</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L189" href="#L189">189</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L190" href="#L190">190</a><span class="code-text"><a-p>Modeling this with immutable trees is possible, but annoying.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L191" href="#L191">191</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L192" href="#L192">192</a><span class="code-text"><a-p>### </a-p><a-tt>Syntax Nodes</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L193" href="#L193">193</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L194" href="#L194">194</a><span class="code-text"><a-p>A function green tree is not super-convenient to use.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L195" href="#L195">195</a><span class="code-text"><a-p>The biggest problem is accessing parents (there are no parent pointers!).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L196" href="#L196">196</a><span class="code-text"><a-p>But there are also &quot;identify&quot; issues.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L197" href="#L197">197</a><span class="code-text"><a-p>Let&#39;s say you want to write a code which builds a list of expressions in a file: `fn collect_expressions(file: GreenNode) -&gt; HashSet&lt;GreenNode&gt;`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L198" href="#L198">198</a><span class="code-text"><a-p>For the input like</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L199" href="#L199">199</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L200" href="#L200">200</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L201" href="#L201">201</a><span class="code-text"><a-p>fn </a-p><a-f>main</a-f><a-p>() {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L202" href="#L202">202</a><span class="code-text"><a-p>    </a-p><a-k>let</a-k><a-p> x = </a-p><a-co>90i8</a-co><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L203" href="#L203">203</a><span class="code-text"><a-p>    </a-p><a-k>let</a-k><a-p> x = x + </a-p><a-co>2</a-co><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L204" href="#L204">204</a><span class="code-text"><a-p>    </a-p><a-k>let</a-k><a-p> x = </a-p><a-co>90i64</a-co><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L205" href="#L205">205</a><span class="code-text"><a-p>    </a-p><a-k>let</a-k><a-p> x = x + </a-p><a-co>2</a-co><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L206" href="#L206">206</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L207" href="#L207">207</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L208" href="#L208">208</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L209" href="#L209">209</a><span class="code-text"><a-p>both copies of the `x + 2` expression are representing by equal (and, with interning in mind, actually the same) green nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L210" href="#L210">210</a><span class="code-text"><a-p>Green trees just can&#39;t differentiate between the two.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L211" href="#L211">211</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L212" href="#L212">212</a><span class="code-text"><a-p>`SyntaxNode` adds parent pointers and identify semantics to green nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L213" href="#L213">213</a><span class="code-text"><a-p>They can be called cursors or [zippers](https://en.wikipedia.org/wiki/Zipper_(data_structure)) (fun fact: zipper is a derivative (as in ′) of a data structure).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L214" href="#L214">214</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L215" href="#L215">215</a><span class="code-text"><a-p>Conceptually, a `SyntaxNode` looks like this:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L216" href="#L216">216</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L217" href="#L217">217</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L218" href="#L218">218</a><span class="code-text"><a-p>type </a-p><a-t>SyntaxNode</a-t><a-p> = </a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>SyntaxData</a-t><a-p>&gt;;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L219" href="#L219">219</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L220" href="#L220">220</a><span class="code-text"><a-p>struct </a-p><a-t>SyntaxData</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L221" href="#L221">221</a><span class="code-text"><a-p>    </a-p><a-pr>offset</a-pr><a-p>: </a-p><a-t>usize</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L222" href="#L222">222</a><span class="code-text"><a-p>    </a-p><a-pr>parent</a-pr><a-p>: </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L223" href="#L223">223</a><span class="code-text"><a-p>    </a-p><a-pr>green</a-pr><a-p>: </a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L224" href="#L224">224</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L225" href="#L225">225</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L226" href="#L226">226</a><span class="code-text"><a-p>impl </a-p><a-t>SyntaxNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L227" href="#L227">227</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>new_root</a-f><a-p>(</a-p><a-v>root</a-v><a-p>: </a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;) -&gt; </a-p><a-t>SyntaxNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L228" href="#L228">228</a><span class="code-text"><a-p>        </a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>new</a-f><a-p>(</a-p><a-t>SyntaxData</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L229" href="#L229">229</a><span class="code-text"><a-p>            </a-p><a-pr>offset</a-pr><a-p>: </a-p><a-co>0</a-co><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L230" href="#L230">230</a><span class="code-text"><a-p>            </a-p><a-pr>parent</a-pr><a-p>: </a-p><a-cr>None</a-cr><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L231" href="#L231">231</a><span class="code-text"><a-p>            </a-p><a-pr>green</a-pr><a-p>: root,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L232" href="#L232">232</a><span class="code-text"><a-p>        })</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L233" href="#L233">233</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L234" href="#L234">234</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>parent</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L235" href="#L235">235</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>parent</a-pr><a-p>.</a-p><a-f>clone</a-f><a-p>()</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L236" href="#L236">236</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L237" href="#L237">237</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>children</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-k>impl</a-k><a-p> </a-p><a-t>Iterator</a-t><a-p>&lt;</a-p><a-t>Item</a-t><a-p> = </a-p><a-t>SyntaxNode</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L238" href="#L238">238</a><span class="code-text"><a-p>        </a-p><a-k>let</a-k><a-p> </a-p><a-k>mut</a-k><a-p> offset = </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>offset</a-pr><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L239" href="#L239">239</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>green</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>map</a-f><a-p>(|green_child| {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L240" href="#L240">240</a><span class="code-text"><a-p>            </a-p><a-k>let</a-k><a-p> child_offset = offset;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L241" href="#L241">241</a><span class="code-text"><a-p>            offset += green_child.</a-p><a-pr>text_len</a-pr><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L242" href="#L242">242</a><span class="code-text"><a-p>            </a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>new</a-f><a-p>(</a-p><a-t>SyntaxData</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L243" href="#L243">243</a><span class="code-text"><a-p>                </a-p><a-pr>offset</a-pr><a-p>: child_offset,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L244" href="#L244">244</a><span class="code-text"><a-p>                </a-p><a-pr>parent</a-pr><a-p>: </a-p><a-f>Some</a-f><a-p>(</a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>clone</a-f><a-p>(</a-p><a-v>self</a-v><a-p>)),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L245" href="#L245">245</a><span class="code-text"><a-p>                </a-p><a-pr>green</a-pr><a-p>: </a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>clone</a-f><a-p>(green_child),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L246" href="#L246">246</a><span class="code-text"><a-p>            })</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L247" href="#L247">247</a><span class="code-text"><a-p>        })</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L248" href="#L248">248</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L249" href="#L249">249</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L250" href="#L250">250</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L251" href="#L251">251</a><span class="code-text"><a-p>impl </a-p><a-t>PartialEq</a-t><a-p> </a-p><a-k>for</a-k><a-p> </a-p><a-t>SyntaxNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L252" href="#L252">252</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>eq</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>, </a-p><a-v>other</a-v><a-p>: </a-p><a-o>&amp;</a-o><a-t>SyntaxNode</a-t><a-p>) -&gt; </a-p><a-t>bool</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L253" href="#L253">253</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>offset</a-pr><a-p> == other.</a-p><a-pr>offset</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L254" href="#L254">254</a><span class="code-text"><a-p>            &amp;&amp; </a-p><a-t>Arc</a-t><a-p>::</a-p><a-f>ptr_eq</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>.</a-p><a-pr>green</a-pr><a-p>, </a-p><a-o>&amp;</a-o><a-p>other.</a-p><a-pr>green</a-pr><a-p>)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L255" href="#L255">255</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L256" href="#L256">256</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L257" href="#L257">257</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L258" href="#L258">258</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L259" href="#L259">259</a><span class="code-text"><a-p>Points of note:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L260" href="#L260">260</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L261" href="#L261">261</a><span class="code-text"><a-p>* SyntaxNode remembers its parent node (and, transitively, the path to the root of the tree)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L262" href="#L262">262</a><span class="code-text"><a-p>* SyntaxNode knows its *absolute* text offset in the whole file</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L263" href="#L263">263</a><span class="code-text"><a-p>* Equality is based on identity. Comparing nodes from different trees does not make sense.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L264" href="#L264">264</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L265" href="#L265">265</a><span class="code-text"><a-p>#### </a-p><a-tt>Optimization</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L266" href="#L266">266</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L267" href="#L267">267</a><span class="code-text"><a-p>The reality is different though :-)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L268" href="#L268">268</a><span class="code-text"><a-p>Traversal of trees is a common operation, and it makes sense to optimize it.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L269" href="#L269">269</a><span class="code-text"><a-p>In particular, the above code allocates and does atomic operations during a traversal.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L270" href="#L270">270</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L271" href="#L271">271</a><span class="code-text"><a-p>To get rid of atomics, `rowan` uses non thread-safe `Rc`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L272" href="#L272">272</a><span class="code-text"><a-p>This is OK because trees traversals mostly (always, in case of rust-analyzer) run on a single thread. If you need to send a `SyntaxNode` to another thread, you can send a pair of **root**`GreenNode` (which is thread safe) and a `Range&lt;usize&gt;`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L273" href="#L273">273</a><span class="code-text"><a-p>The other thread can restore the `SyntaxNode` by traversing from the root green node and looking for a node with specified range.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L274" href="#L274">274</a><span class="code-text"><a-p>You can also use the similar trick to store a `SyntaxNode`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L275" href="#L275">275</a><span class="code-text"><a-p>That is, a data structure that holds a `(GreenNode, Range&lt;usize&gt;)` will be `Sync`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L276" href="#L276">276</a><span class="code-text"><a-p>However, rust-analyzer goes even further.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L277" href="#L277">277</a><span class="code-text"><a-p>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&lt;usize&gt;)`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L278" href="#L278">278</a><span class="code-text"><a-p>The `SyntaxNode` is the restored by reparsing the file and traversing it from root.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L279" href="#L279">279</a><span class="code-text"><a-p>With this trick, rust-analyzer holds only a small amount of trees in memory at the same time, which reduces memory usage.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L280" href="#L280">280</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L281" href="#L281">281</a><span class="code-text"><a-p>Additionally, only the root `SyntaxNode` owns an `Arc` to the (root) `GreenNode`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L282" href="#L282">282</a><span class="code-text"><a-p>All other `SyntaxNode`s point to corresponding `GreenNode`s with a raw pointer.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L283" href="#L283">283</a><span class="code-text"><a-p>They also point to the parent (and, consequently, to the root) with an owning `Rc`, so this is sound.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L284" href="#L284">284</a><span class="code-text"><a-p>In other words, one needs *one* arc bump when initiating a traversal.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L285" href="#L285">285</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L286" href="#L286">286</a><span class="code-text"><a-p>To get rid of allocations, `rowan` takes advantage of `SyntaxNode: !Sync` and uses a thread-local free list of `SyntaxNode`s.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L287" href="#L287">287</a><span class="code-text"><a-p>In a typical traversal, you only directly hold a few `SyntaxNode`s at a time (and their ancestors indirectly), so a free list proportional to the depth of the tree removes all allocations in a typical case.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L288" href="#L288">288</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L289" href="#L289">289</a><span class="code-text"><a-p>So, while traversal is not exactly incrementing a pointer, it&#39;s still pretty cheap: TLS + rc bump!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L290" href="#L290">290</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L291" href="#L291">291</a><span class="code-text"><a-p>Traversal also yields (cheap) owned nodes, which improves ergonomics quite a bit.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L292" href="#L292">292</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L293" href="#L293">293</a><span class="code-text"><a-p>#### </a-p><a-tt>Alternative Designs</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L294" href="#L294">294</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L295" href="#L295">295</a><span class="code-text"><a-p>##### </a-p><a-tt>Memoized RedNodes</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L296" href="#L296">296</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L297" href="#L297">297</a><span class="code-text"><a-p>C# and Swift follow the design where the red nodes are memoized, which would look roughly like this in Rust:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L298" href="#L298">298</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L299" href="#L299">299</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L300" href="#L300">300</a><span class="code-text"><a-p>type </a-p><a-t>SyntaxNode</a-t><a-p> = </a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>SyntaxData</a-t><a-p>&gt;;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L301" href="#L301">301</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L302" href="#L302">302</a><span class="code-text"><a-p>struct </a-p><a-t>SyntaxData</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L303" href="#L303">303</a><span class="code-text"><a-p>    </a-p><a-pr>offset</a-pr><a-p>: </a-p><a-t>usize</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L304" href="#L304">304</a><span class="code-text"><a-p>    </a-p><a-pr>parent</a-pr><a-p>: </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L305" href="#L305">305</a><span class="code-text"><a-p>    </a-p><a-pr>green</a-pr><a-p>: </a-p><a-t>Arc</a-t><a-p>&lt;</a-p><a-t>GreenNode</a-t><a-p>&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L306" href="#L306">306</a><span class="code-text"><a-p>    </a-p><a-pr>children</a-pr><a-p>: </a-p><a-t>Vec</a-t><a-p>&lt;</a-p><a-t>OnceCell</a-t><a-p>&lt;</a-p><a-t>SyntaxNode</a-t><a-p>&gt;&gt;,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L307" href="#L307">307</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L308" href="#L308">308</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L309" href="#L309">309</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L310" href="#L310">310</a><span class="code-text"><a-p>This allows using true pointer equality for comparison of identities of `SyntaxNodes`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L311" href="#L311">311</a><span class="code-text"><a-p>rust-analyzer used to have this design as well, but we&#39;ve since switched to cursors.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L312" href="#L312">312</a><span class="code-text"><a-p>The main problem with memoizing the red nodes is that it more than doubles the memory requirements for fully realized syntax trees.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L313" href="#L313">313</a><span class="code-text"><a-p>In contrast, cursors generally retain only a path to the root.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L314" href="#L314">314</a><span class="code-text"><a-p>C# combats increased memory usage by using weak references.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L315" href="#L315">315</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L316" href="#L316">316</a><span class="code-text"><a-p>### </a-p><a-tt>AST</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L317" href="#L317">317</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L318" href="#L318">318</a><span class="code-text"><a-p>`GreenTree`s are untyped and homogeneous, because it makes accommodating error nodes, arbitrary whitespace and comments natural, and because it makes possible to write generic tree traversals.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L319" href="#L319">319</a><span class="code-text"><a-p>However, when working with a specific node, like a function definition, one would want a strongly typed API.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L320" href="#L320">320</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L321" href="#L321">321</a><span class="code-text"><a-p>This is what is provided by the AST layer. AST nodes are transparent wrappers over untyped syntax nodes:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L322" href="#L322">322</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L323" href="#L323">323</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L324" href="#L324">324</a><span class="code-text"><a-p>pub </a-p><a-k>trait</a-k><a-p> </a-p><a-t>AstNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L325" href="#L325">325</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>cast</a-f><a-p>(</a-p><a-v>syntax</a-v><a-p>: </a-p><a-t>SyntaxNode</a-t><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>Self</a-t><a-p>&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L326" href="#L326">326</a><span class="code-text"><a-p>    </a-p><a-k>where</a-k></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L327" href="#L327">327</a><span class="code-text"><a-p>        </a-p><a-t>Self</a-t><a-p>: </a-p><a-t>Sized</a-t><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L328" href="#L328">328</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L329" href="#L329">329</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>syntax</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-o>&amp;</a-o><a-t>SyntaxNode</a-t><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L330" href="#L330">330</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L331" href="#L331">331</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L332" href="#L332">332</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L333" href="#L333">333</a><span class="code-text"><a-p>Concrete nodes are generated (there are 117 of them), and look roughly like this:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L334" href="#L334">334</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L335" href="#L335">335</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L336" href="#L336">336</a><span class="code-text"><a-p>#[derive(</a-p><a-cr>Debug</a-cr><a-p>, </a-p><a-cr>Clone</a-cr><a-p>, </a-p><a-cr>PartialEq</a-cr><a-p>, </a-p><a-cr>Eq</a-cr><a-p>, </a-p><a-cr>Hash</a-cr><a-p>)]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L337" href="#L337">337</a><span class="code-text"><a-p>pub </a-p><a-k>struct</a-k><a-p> </a-p><a-t>FnDef</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L338" href="#L338">338</a><span class="code-text"><a-p>    </a-p><a-pr>syntax</a-pr><a-p>: </a-p><a-t>SyntaxNode</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L339" href="#L339">339</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L340" href="#L340">340</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L341" href="#L341">341</a><span class="code-text"><a-p>impl </a-p><a-t>AstNode</a-t><a-p> </a-p><a-k>for</a-k><a-p> </a-p><a-t>FnDef</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L342" href="#L342">342</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>cast</a-f><a-p>(</a-p><a-v>syntax</a-v><a-p>: </a-p><a-t>SyntaxNode</a-t><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>Self</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L343" href="#L343">343</a><span class="code-text"><a-p>        </a-p><a-k>match</a-k><a-p> kind {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L344" href="#L344">344</a><span class="code-text"><a-p>            </a-p><a-cr>FN</a-cr><a-p> =&gt; </a-p><a-f>Some</a-f><a-p>(</a-p><a-t>FnDef</a-t><a-p> { syntax }),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L345" href="#L345">345</a><span class="code-text"><a-p>            _ =&gt; </a-p><a-cr>None</a-cr><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L346" href="#L346">346</a><span class="code-text"><a-p>        }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L347" href="#L347">347</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L348" href="#L348">348</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>syntax</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-o>&amp;</a-o><a-t>SyntaxNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L349" href="#L349">349</a><span class="code-text"><a-p>        </a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L350" href="#L350">350</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L351" href="#L351">351</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L352" href="#L352">352</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L353" href="#L353">353</a><span class="code-text"><a-p>impl </a-p><a-t>FnDef</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L354" href="#L354">354</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>param_list</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>ParamList</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L355" href="#L355">355</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>ParamList</a-t><a-p>::cast)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L356" href="#L356">356</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L357" href="#L357">357</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>ret_type</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>RetType</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L358" href="#L358">358</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>RetType</a-t><a-p>::cast)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L359" href="#L359">359</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L360" href="#L360">360</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>body</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>BlockExpr</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L361" href="#L361">361</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>BlockExpr</a-t><a-p>::cast)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L362" href="#L362">362</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L363" href="#L363">363</a><span class="code-text"><a-p>    </a-p><a-c>// ...</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L364" href="#L364">364</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L365" href="#L365">365</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L366" href="#L366">366</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L367" href="#L367">367</a><span class="code-text"><a-p>Variants like expressions, patterns or items are modeled with `enum`s, which also implement `AstNode`:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L368" href="#L368">368</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L369" href="#L369">369</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L370" href="#L370">370</a><span class="code-text"><a-p>#[derive(</a-p><a-cr>Debug</a-cr><a-p>, </a-p><a-cr>Clone</a-cr><a-p>, </a-p><a-cr>PartialEq</a-cr><a-p>, </a-p><a-cr>Eq</a-cr><a-p>, </a-p><a-cr>Hash</a-cr><a-p>)]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L371" href="#L371">371</a><span class="code-text"><a-p>pub </a-p><a-k>enum</a-k><a-p> </a-p><a-t>AssocItem</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L372" href="#L372">372</a><span class="code-text"><a-p>    </a-p><a-cr>FnDef</a-cr><a-p>(</a-p><a-t>FnDef</a-t><a-p>),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L373" href="#L373">373</a><span class="code-text"><a-p>    </a-p><a-cr>TypeAliasDef</a-cr><a-p>(</a-p><a-t>TypeAliasDef</a-t><a-p>),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L374" href="#L374">374</a><span class="code-text"><a-p>    </a-p><a-cr>ConstDef</a-cr><a-p>(</a-p><a-t>ConstDef</a-t><a-p>),</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L375" href="#L375">375</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L376" href="#L376">376</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L377" href="#L377">377</a><span class="code-text"><a-p>impl </a-p><a-t>AstNode</a-t><a-p> </a-p><a-k>for</a-k><a-p> </a-p><a-t>AssocItem</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L378" href="#L378">378</a><span class="code-text"><a-p>    ...</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L379" href="#L379">379</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L380" href="#L380">380</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L381" href="#L381">381</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L382" href="#L382">382</a><span class="code-text"><a-p>Shared AST substructures are modeled via (object safe) traits:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L383" href="#L383">383</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L384" href="#L384">384</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L385" href="#L385">385</a><span class="code-text"><a-p>trait </a-p><a-t>HasVisibility</a-t><a-p>: </a-p><a-t>AstNode</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L386" href="#L386">386</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>visibility</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>Visibility</a-t><a-p>&gt;;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L387" href="#L387">387</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L388" href="#L388">388</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L389" href="#L389">389</a><span class="code-text"><a-p>impl </a-p><a-t>HasVisibility</a-t><a-p> </a-p><a-k>for</a-k><a-p> </a-p><a-t>FnDef</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L390" href="#L390">390</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>visibility</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Option</a-t><a-p>&lt;</a-p><a-t>Visibility</a-t><a-p>&gt; {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L391" href="#L391">391</a><span class="code-text"><a-p>        </a-p><a-v>self</a-v><a-p>.</a-p><a-pr>syntax</a-pr><a-p>.</a-p><a-f>children</a-f><a-p>().</a-p><a-f>find_map</a-f><a-p>(</a-p><a-t>Visibility</a-t><a-p>::cast)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L392" href="#L392">392</a><span class="code-text"><a-p>    }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L393" href="#L393">393</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L394" href="#L394">394</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L395" href="#L395">395</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L396" href="#L396">396</a><span class="code-text"><a-p>Points of note:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L397" href="#L397">397</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L398" href="#L398">398</a><span class="code-text"><a-p>* Like `SyntaxNode`s, AST nodes are cheap to clone pointer-sized owned values.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L399" href="#L399">399</a><span class="code-text"><a-p>* All &quot;fields&quot; are optional, to accommodate incomplete and/or erroneous source code.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L400" href="#L400">400</a><span class="code-text"><a-p>* It&#39;s always possible to go from an ast node to an untyped `SyntaxNode`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L401" href="#L401">401</a><span class="code-text"><a-p>* It&#39;s possible to go in the opposite direction with a checked cast.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L402" href="#L402">402</a><span class="code-text"><a-p>* `enum`s allow modeling of arbitrary intersecting subsets of AST types.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L403" href="#L403">403</a><span class="code-text"><a-p>* Most of rust-analyzer works with the ast layer, with notable exceptions of:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L404" href="#L404">404</a><span class="code-text"><a-p>  * macro expansion, which needs access to raw tokens and works with `SyntaxNode`s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L405" href="#L405">405</a><span class="code-text"><a-p>  * some IDE-specific features like syntax highlighting are more conveniently implemented over a homogeneous `SyntaxNode` tree</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L406" href="#L406">406</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L407" href="#L407">407</a><span class="code-text"><a-p>#### </a-p><a-tt>Alternative Designs</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L408" href="#L408">408</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L409" href="#L409">409</a><span class="code-text"><a-p>##### </a-p><a-tt>Semantic Full AST</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L410" href="#L410">410</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L411" href="#L411">411</a><span class="code-text"><a-p>In IntelliJ the AST layer (dubbed **P**rogram **S**tructure **I**nterface) can have semantics attached, and is usually backed by either syntax tree, indices, or metadata from compiled libraries.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L412" href="#L412">412</a><span class="code-text"><a-p>The backend for PSI can change dynamically.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L413" href="#L413">413</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L414" href="#L414">414</a><span class="code-text"><a-p>### </a-p><a-tt>Syntax Tree Recap</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L415" href="#L415">415</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L416" href="#L416">416</a><span class="code-text"><a-p>At its core, the syntax tree is a purely functional n-ary tree, which stores text at the leaf nodes and node &quot;kinds&quot; at all nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L417" href="#L417">417</a><span class="code-text"><a-p>A cursor layer is added on top, which gives owned, cheap to clone nodes with identity semantics, parent links and absolute offsets.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L418" href="#L418">418</a><span class="code-text"><a-p>An AST layer is added on top, which reifies each node `Kind` as a separate Rust type with the corresponding API.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L419" href="#L419">419</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L420" href="#L420">420</a><span class="code-text"><a-p>## </a-p><a-tt>Parsing</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L421" href="#L421">421</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L422" href="#L422">422</a><span class="code-text"><a-p>The (green) tree is constructed by a DFS &quot;traversal&quot; of the desired tree structure:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L423" href="#L423">423</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L424" href="#L424">424</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L425" href="#L425">425</a><span class="code-text"><a-p>pub </a-p><a-k>struct</a-k><a-p> </a-p><a-t>GreenNodeBuilder</a-t><a-p> { ... }</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L426" href="#L426">426</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L427" href="#L427">427</a><span class="code-text"><a-p>impl </a-p><a-t>GreenNodeBuilder</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L428" href="#L428">428</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>new</a-f><a-p>() -&gt; </a-p><a-t>GreenNodeBuilder</a-t><a-p> { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L429" href="#L429">429</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L430" href="#L430">430</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>token</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>, </a-p><a-v>kind</a-v><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>, </a-p><a-v>text</a-v><a-p>: </a-p><a-o>&amp;</a-o><a-t>str</a-t><a-p>) { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L431" href="#L431">431</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L432" href="#L432">432</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>start_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>, </a-p><a-v>kind</a-v><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>) { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L433" href="#L433">433</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>finish_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>) { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L434" href="#L434">434</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L435" href="#L435">435</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-k>fn</a-k><a-p> </a-p><a-f>finish</a-f><a-p>(</a-p><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>GreenNode</a-t><a-p> { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L436" href="#L436">436</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L437" href="#L437">437</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L438" href="#L438">438</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L439" href="#L439">439</a><span class="code-text"><a-pr>The parser, ultimately, needs to invoke the `GreenNodeBuilder`.</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L440" href="#L440">440</a><span class="code-text"><a-pr>There are two principal sources of inputs for the parser:</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L441" href="#L441">441</a><span class="code-text"><a-p>  * </a-p><a-pr>source text, which contains trivia tokens (whitespace and comments)</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L442" href="#L442">442</a><span class="code-text"><a-pr>  </a-pr><a-p>* </a-p><a-pr>token trees from macros, which lack trivia</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L443" href="#L443">443</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L444" href="#L444">444</a><span class="code-text"><a-p>Additionally, input tokens do not correspond 1-to-1 with output tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L445" href="#L445">445</a><span class="code-text"><a-p>For example, two consecutive `&gt;` tokens might be glued, by the parser, into a single `&gt;&gt;`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L446" href="#L446">446</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L447" href="#L447">447</a><span class="code-text"><a-p>For these reasons, the parser crate defines a callback interfaces for both input tokens and output trees.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L448" href="#L448">448</a><span class="code-text"><a-p>The explicit glue layer then bridges various gaps.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L449" href="#L449">449</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L450" href="#L450">450</a><span class="code-text"><a-p>The parser interface looks like this:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L451" href="#L451">451</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L452" href="#L452">452</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L453" href="#L453">453</a><span class="code-text"><a-p>pub </a-p><a-k>struct</a-k><a-p> </a-p><a-t>Token</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L454" href="#L454">454</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-pr>kind</a-pr><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L455" href="#L455">455</a><span class="code-text"><a-p>    </a-p><a-k>pub</a-k><a-p> </a-p><a-pr>is_joined_to_next</a-pr><a-p>: </a-p><a-t>bool</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L456" href="#L456">456</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L457" href="#L457">457</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L458" href="#L458">458</a><span class="code-text"><a-p>pub </a-p><a-k>trait</a-k><a-p> </a-p><a-t>TokenSource</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L459" href="#L459">459</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>current</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>) -&gt; </a-p><a-t>Token</a-t><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L460" href="#L460">460</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>lookahead_nth</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>, </a-p><a-v>n</a-v><a-p>: </a-p><a-t>usize</a-t><a-p>) -&gt; </a-p><a-t>Token</a-t><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L461" href="#L461">461</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>is_keyword</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-v>self</a-v><a-p>, </a-p><a-v>kw</a-v><a-p>: </a-p><a-o>&amp;</a-o><a-t>str</a-t><a-p>) -&gt; </a-p><a-t>bool</a-t><a-p>;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L462" href="#L462">462</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L463" href="#L463">463</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>bump</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L464" href="#L464">464</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L465" href="#L465">465</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L466" href="#L466">466</a><span class="code-text"><a-p>pub </a-p><a-k>trait</a-k><a-p> </a-p><a-t>TreeSink</a-t><a-p> {</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L467" href="#L467">467</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>token</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>, </a-p><a-v>kind</a-v><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>, </a-p><a-v>n_tokens</a-v><a-p>: </a-p><a-t>u8</a-t><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L468" href="#L468">468</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L469" href="#L469">469</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>start_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>, </a-p><a-v>kind</a-v><a-p>: </a-p><a-t>SyntaxKind</a-t><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L470" href="#L470">470</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>finish_node</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L471" href="#L471">471</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L472" href="#L472">472</a><span class="code-text"><a-p>    </a-p><a-k>fn</a-k><a-p> </a-p><a-f>error</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-v>self</a-v><a-p>, </a-p><a-v>error</a-v><a-p>: </a-p><a-t>ParseError</a-t><a-p>);</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L473" href="#L473">473</a><span class="code-text"><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L474" href="#L474">474</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L475" href="#L475">475</a><span class="code-text"><a-p>pub </a-p><a-k>fn</a-k><a-p> </a-p><a-f>parse</a-f><a-p>(</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L476" href="#L476">476</a><span class="code-text"><a-p>    </a-p><a-v>token_source</a-v><a-p>: </a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-k>dyn</a-k><a-p> </a-p><a-t>TokenSource</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L477" href="#L477">477</a><span class="code-text"><a-p>    </a-p><a-v>tree_sink</a-v><a-p>: </a-p><a-o>&amp;</a-o><a-k>mut</a-k><a-p> </a-p><a-k>dyn</a-k><a-p> </a-p><a-t>TreeSink</a-t><a-p>,</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L478" href="#L478">478</a><span class="code-text"><a-p>) { ...</a-p><a-pr> </a-pr><a-p>}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L479" href="#L479">479</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L480" href="#L480">480</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L481" href="#L481">481</a><span class="code-text"><a-pr>Points of note:</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L482" href="#L482">482</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L483" href="#L483">483</a><span class="code-text"><a-p>* </a-p><a-pr>The parser and the syntax tree are independent, they live in different crates neither of which depends on the other.</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L484" href="#L484">484</a><span class="code-text"><a-p>* </a-p><a-pr>The parser doesn&#39;t know anything about textual contents of the tokens, with an isolated hack for checking contextual keywords.</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L485" href="#L485">485</a><span class="code-text"><a-p>* </a-p><a-pr>For gluing tokens, the `TreeSink::token` might advance further than one atomic token ahead.</a-pr></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L486" href="#L486">486</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L487" href="#L487">487</a><span class="code-text"><a-p>### </a-p><a-tt>Reporting Syntax Errors</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L488" href="#L488">488</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L489" href="#L489">489</a><span class="code-text"><a-p>Syntax errors are not stored directly in the tree.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L490" href="#L490">490</a><span class="code-text"><a-p>The primary motivation for this is that syntax tree is not necessary produced by the parser, it may also be assembled manually from pieces (which happens all the time in refactorings).</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L491" href="#L491">491</a><span class="code-text"><a-p>Instead, parser reports errors to an error sink, which stores them in a `Vec`.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L492" href="#L492">492</a><span class="code-text"><a-p>If possible, errors are not reported during parsing and are postponed for a separate validation step.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L493" href="#L493">493</a><span class="code-text"><a-p>For example, parser accepts visibility modifiers on trait methods, but then a separate tree traversal flags all such visibilities as erroneous.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L494" href="#L494">494</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L495" href="#L495">495</a><span class="code-text"><a-p>### </a-p><a-tt>Macros</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L496" href="#L496">496</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L497" href="#L497">497</a><span class="code-text"><a-p>The primary difficulty with macros is that individual tokens have identities, which need to be preserved in the syntax tree for hygiene purposes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L498" href="#L498">498</a><span class="code-text"><a-p>This is handled by the `TreeSink` layer.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L499" href="#L499">499</a><span class="code-text"><a-p>Specifically, `TreeSink` constructs the tree in lockstep with draining the original token stream.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L500" href="#L500">500</a><span class="code-text"><a-p>In the process, it records which tokens of the tree correspond to which tokens of the input, by using text ranges to identify syntax tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L501" href="#L501">501</a><span class="code-text"><a-p>The end result is that parsing an expanded code yields a syntax tree and a mapping of text-ranges of the tree to original tokens.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L502" href="#L502">502</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L503" href="#L503">503</a><span class="code-text"><a-p>To deal with precedence in cases like `$expr * 1`, we use special invisible parenthesis, which are explicitly handled by the parser</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L504" href="#L504">504</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L505" href="#L505">505</a><span class="code-text"><a-p>### </a-p><a-tt>Whitespace &amp; Comments</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L506" href="#L506">506</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L507" href="#L507">507</a><span class="code-text"><a-p>Parser does not see whitespace nodes.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L508" href="#L508">508</a><span class="code-text"><a-p>Instead, they are attached to the tree in the `TreeSink` layer.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L509" href="#L509">509</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L510" href="#L510">510</a><span class="code-text"><a-p>For example, in</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L511" href="#L511">511</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L512" href="#L512">512</a><span class="code-text"><a-p>```</a-p><a-tl>rust</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L513" href="#L513">513</a><span class="code-text"><a-p>// non doc comment</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L514" href="#L514">514</a><span class="code-text"><a-p>fn </a-p><a-f>foo</a-f><a-p>() {}</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L515" href="#L515">515</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L516" href="#L516">516</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L517" href="#L517">517</a><span class="code-text"><a-p>the comment will be (heuristically) made a child of function node.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L518" href="#L518">518</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L519" href="#L519">519</a><span class="code-text"><a-p>### </a-p><a-tt>Incremental Reparse</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L520" href="#L520">520</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L521" href="#L521">521</a><span class="code-text"><a-p>Green trees are cheap to modify, so incremental reparse works by patching a previous tree, without maintaining any additional state.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L522" href="#L522">522</a><span class="code-text"><a-p>The reparse is based on heuristic: we try to contain a change to a single `{}` block, and reparse only this block.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L523" href="#L523">523</a><span class="code-text"><a-p>To do this, we maintain the invariant that, even for invalid code, curly braces are always paired correctly.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L524" href="#L524">524</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L525" href="#L525">525</a><span class="code-text"><a-p>In practice, incremental reparsing doesn&#39;t actually matter much for IDE use-cases, parsing from scratch seems to be fast enough.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L526" href="#L526">526</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L527" href="#L527">527</a><span class="code-text"><a-p>### </a-p><a-tt>Parsing Algorithm</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L528" href="#L528">528</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L529" href="#L529">529</a><span class="code-text"><a-p>We use a boring hand-crafted recursive descent + pratt combination, with a special effort of continuing the parsing if an error is detected.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L530" href="#L530">530</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L531" href="#L531">531</a><span class="code-text"><a-p>### </a-p><a-tt>Parser Recap</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L532" href="#L532">532</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L533" href="#L533">533</a><span class="code-text">Parser itself defines traits for token sequence input and syntax tree output.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L534" href="#L534">534</a><span class="code-text">It doesn&#39;t care about where the tokens come from, and how the resulting syntax tree looks like.</span></span></pre></div></div>
</main>
</body>
</html>
