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 output::Output,
14 SyntaxKind::{self, *},
15 };
16
17 /// `Parser` produces a flat list of `Event`s.
18 /// They are converted to a tree-structure in
19 /// a separate pass, via `TreeBuilder`.
20 #[derive(Debug)]
21 pub(crate) enum Event {
22 /// This event signifies the start of the node.
23 /// It should be either abandoned (in which case the
24 /// `kind` is `TOMBSTONE`, and the event is ignored),
25 /// or completed via a `Finish` event.
26 ///
27 /// All tokens between a `Start` and a `Finish` would
28 /// become the children of the respective node.
29 ///
30 /// For left-recursive syntactic constructs, the parser produces
31 /// a child node before it sees a parent. `forward_parent`
32 /// saves the position of current event's parent.
33 ///
34 /// Consider this path
35 ///
36 /// foo::bar
37 ///
38 /// The events for it would look like this:
39 ///
40 /// ```text
41 /// START(PATH) IDENT('foo') FINISH START(PATH) T![::] IDENT('bar') FINISH
42 /// | /\
43 /// | |
44 /// +------forward-parent------+
45 /// ```
46 ///
47 /// And the tree would look like this
48 ///
49 /// ```text
50 /// +--PATH---------+
51 /// | | |
52 /// | | |
53 /// | '::' 'bar'
54 /// |
55 /// PATH
56 /// |
57 /// 'foo'
58 /// ```
59 ///
60 /// See also `CompletedMarker::precede`.
61 Start {
62 kind: SyntaxKind,
63 forward_parent: Option<u32>,
64 },
65
66 /// Complete the previous `Start` event
67 Finish,
68
69 /// Produce a single leaf-element.
70 /// `n_raw_tokens` is used to glue complex contextual tokens.
71 /// For example, lexer tokenizes `>>` as `>`, `>`, and
72 /// `n_raw_tokens = 2` is used to produced a single `>>`.
73 Token {
74 kind: SyntaxKind,
75 n_raw_tokens: u8,
76 },
77 /// When we parse `foo.0.0` or `foo. 0. 0` the lexer will hand us a float literal
78 /// instead of an integer literal followed by a dot as the lexer has no contextual knowledge.
79 /// This event instructs whatever consumes the events to split the float literal into
80 /// the corresponding parts.
81 FloatSplitHack {
82 ends_in_dot: bool,
83 },
84 Error {
85 msg: String,
86 },
87 }
88
89 impl Event {
tombstone() -> Self90 pub(crate) fn tombstone() -> Self {
91 Event::Start { kind: TOMBSTONE, forward_parent: None }
92 }
93 }
94
95 /// Generate the syntax tree with the control of events.
process(mut events: Vec<Event>) -> Output96 pub(super) fn process(mut events: Vec<Event>) -> Output {
97 let mut res = Output::default();
98 let mut forward_parents = Vec::new();
99
100 for i in 0..events.len() {
101 match mem::replace(&mut events[i], Event::tombstone()) {
102 Event::Start { kind, forward_parent } => {
103 // For events[A, B, C], B is A's forward_parent, C is B's forward_parent,
104 // in the normal control flow, the parent-child relation: `A -> B -> C`,
105 // while with the magic forward_parent, it writes: `C <- B <- A`.
106
107 // append `A` into parents.
108 forward_parents.push(kind);
109 let mut idx = i;
110 let mut fp = forward_parent;
111 while let Some(fwd) = fp {
112 idx += fwd as usize;
113 // append `A`'s forward_parent `B`
114 fp = match mem::replace(&mut events[idx], Event::tombstone()) {
115 Event::Start { kind, forward_parent } => {
116 forward_parents.push(kind);
117 forward_parent
118 }
119 _ => unreachable!(),
120 };
121 // append `B`'s forward_parent `C` in the next stage.
122 }
123
124 for kind in forward_parents.drain(..).rev() {
125 if kind != TOMBSTONE {
126 res.enter_node(kind);
127 }
128 }
129 }
130 Event::Finish => res.leave_node(),
131 Event::Token { kind, n_raw_tokens } => {
132 res.token(kind, n_raw_tokens);
133 }
134 Event::FloatSplitHack { ends_in_dot } => {
135 res.float_split_hack(ends_in_dot);
136 let ev = mem::replace(&mut events[i + 1], Event::tombstone());
137 assert!(matches!(ev, Event::Finish), "{ev:?}");
138 }
139 Event::Error { msg } => res.error(msg),
140 }
141 }
142
143 res
144 }
145