1 //! This module provides a way to construct a `File`.
2 //! It is intended to be completely decoupled from the
3 //! parser, so as to allow to evolve the tree representation
4 //! and the parser algorithm independently.
5 //!
6 //! The `TreeSink` trait is the bridge between the parser and the
7 //! tree builder: the parser produces a stream of events like
8 //! `start node`, `finish node`, and `FileBuilder` converts
9 //! this stream to a real tree.
10 use std::mem;
11
12 use crate::{
13 ParseError,
14 SyntaxKind::{self, *},
15 TreeSink,
16 };
17
18 /// `Parser` produces a flat list of `Event`s.
19 /// They are converted to a tree-structure in
20 /// a separate pass, via `TreeBuilder`.
21 #[derive(Debug)]
22 pub(crate) enum Event {
23 /// This event signifies the start of the node.
24 /// It should be either abandoned (in which case the
25 /// `kind` is `TOMBSTONE`, and the event is ignored),
26 /// or completed via a `Finish` event.
27 ///
28 /// All tokens between a `Start` and a `Finish` would
29 /// become the children of the respective node.
30 ///
31 /// For left-recursive syntactic constructs, the parser produces
32 /// a child node before it sees a parent. `forward_parent`
33 /// saves the position of current event's parent.
34 ///
35 /// Consider this path
36 ///
37 /// foo::bar
38 ///
39 /// The events for it would look like this:
40 ///
41 /// ```text
42 /// START(PATH) IDENT('foo') FINISH START(PATH) T![::] IDENT('bar') FINISH
43 /// | /\
44 /// | |
45 /// +------forward-parent------+
46 /// ```
47 ///
48 /// And the tree would look like this
49 ///
50 /// ```text
51 /// +--PATH---------+
52 /// | | |
53 /// | | |
54 /// | '::' 'bar'
55 /// |
56 /// PATH
57 /// |
58 /// 'foo'
59 /// ```
60 ///
61 /// See also `CompletedMarker::precede`.
62 Start {
63 kind: SyntaxKind,
64 forward_parent: Option<u32>,
65 },
66
67 /// Complete the previous `Start` event
68 Finish,
69
70 /// Produce a single leaf-element.
71 /// `n_raw_tokens` is used to glue complex contextual tokens.
72 /// For example, lexer tokenizes `>>` as `>`, `>`, and
73 /// `n_raw_tokens = 2` is used to produced a single `>>`.
74 Token {
75 kind: SyntaxKind,
76 n_raw_tokens: u8,
77 },
78
79 Error {
80 msg: ParseError,
81 },
82 }
83
84 impl Event {
tombstone() -> Self85 pub(crate) fn tombstone() -> Self {
86 Event::Start { kind: TOMBSTONE, forward_parent: None }
87 }
88 }
89
90 /// Generate the syntax tree with the control of events.
process(sink: &mut dyn TreeSink, mut events: Vec<Event>)91 pub(super) fn process(sink: &mut dyn TreeSink, mut events: Vec<Event>) {
92 let mut forward_parents = Vec::new();
93
94 for i in 0..events.len() {
95 match mem::replace(&mut events[i], Event::tombstone()) {
96 Event::Start { kind, forward_parent } => {
97 // For events[A, B, C], B is A's forward_parent, C is B's forward_parent,
98 // in the normal control flow, the parent-child relation: `A -> B -> C`,
99 // while with the magic forward_parent, it writes: `C <- B <- A`.
100
101 // append `A` into parents.
102 forward_parents.push(kind);
103 let mut idx = i;
104 let mut fp = forward_parent;
105 while let Some(fwd) = fp {
106 idx += fwd as usize;
107 // append `A`'s forward_parent `B`
108 fp = match mem::replace(&mut events[idx], Event::tombstone()) {
109 Event::Start { kind, forward_parent } => {
110 forward_parents.push(kind);
111 forward_parent
112 }
113 _ => unreachable!(),
114 };
115 // append `B`'s forward_parent `C` in the next stage.
116 }
117
118 for kind in forward_parents.drain(..).rev() {
119 if kind != TOMBSTONE {
120 sink.start_node(kind);
121 }
122 }
123 }
124 Event::Finish => sink.finish_node(),
125 Event::Token { kind, n_raw_tokens } => {
126 sink.token(kind, n_raw_tokens);
127 }
128 Event::Error { msg } => sink.error(msg),
129 }
130 }
131 }
132