1 //! FIXME: write short doc here
5 use drop_bomb::DropBomb;
10 SyntaxKind::{self, EOF, ERROR, TOMBSTONE},
11 TokenSet, TokenSource, T,
14 /// `Parser` struct provides the low-level API for
15 /// navigating through the stream of tokens and
16 /// constructing the parse tree. The actual parsing
17 /// happens in the `grammar` module.
19 /// However, the result of this `Parser` is not a real
20 /// tree, but rather a flat stream of events of the form
21 /// "start expression, consume number literal,
22 /// finish expression". See `Event` docs for more.
23 pub(crate) struct Parser<'t> {
24 token_source: &'t mut dyn TokenSource,
30 pub(super) fn new(token_source: &'t mut dyn TokenSource) -> Parser<'t> {
31 Parser { token_source, events: Vec::new(), steps: Cell::new(0) }
34 pub(crate) fn finish(self) -> Vec<Event> {
38 /// Returns the kind of the current token.
39 /// If parser has already reached the end of input,
40 /// the special `EOF` kind is returned.
41 pub(crate) fn current(&self) -> SyntaxKind {
45 /// Lookahead operation: returns the kind of the next nth
47 pub(crate) fn nth(&self, n: usize) -> SyntaxKind {
50 let steps = self.steps.get();
51 assert!(steps <= 10_000_000, "the parser seems stuck");
52 self.steps.set(steps + 1);
54 self.token_source.lookahead_nth(n).kind
57 /// Checks if the current token is `kind`.
58 pub(crate) fn at(&self, kind: SyntaxKind) -> bool {
62 pub(crate) fn nth_at(&self, n: usize, kind: SyntaxKind) -> bool {
64 T![-=] => self.at_composite2(n, T![-], T![=]),
65 T![->] => self.at_composite2(n, T![-], T![>]),
66 T![::] => self.at_composite2(n, T![:], T![:]),
67 T![!=] => self.at_composite2(n, T![!], T![=]),
68 T![..] => self.at_composite2(n, T![.], T![.]),
69 T![*=] => self.at_composite2(n, T![*], T![=]),
70 T![/=] => self.at_composite2(n, T![/], T![=]),
71 T![&&] => self.at_composite2(n, T![&], T![&]),
72 T![&=] => self.at_composite2(n, T![&], T![=]),
73 T![%=] => self.at_composite2(n, T![%], T![=]),
74 T![^=] => self.at_composite2(n, T![^], T![=]),
75 T![+=] => self.at_composite2(n, T![+], T![=]),
76 T![<<] => self.at_composite2(n, T![<], T![<]),
77 T![<=] => self.at_composite2(n, T![<], T![=]),
78 T![==] => self.at_composite2(n, T![=], T![=]),
79 T![=>] => self.at_composite2(n, T![=], T![>]),
80 T![>=] => self.at_composite2(n, T![>], T![=]),
81 T![>>] => self.at_composite2(n, T![>], T![>]),
82 T![|=] => self.at_composite2(n, T![|], T![=]),
83 T![||] => self.at_composite2(n, T![|], T![|]),
85 T![...] => self.at_composite3(n, T![.], T![.], T![.]),
86 T![..=] => self.at_composite3(n, T![.], T![.], T![=]),
87 T![<<=] => self.at_composite3(n, T![<], T![<], T![=]),
88 T![>>=] => self.at_composite3(n, T![>], T![>], T![=]),
90 _ => self.token_source.lookahead_nth(n).kind == kind,
94 /// Consume the next token if `kind` matches.
95 pub(crate) fn eat(&mut self, kind: SyntaxKind) -> bool {
99 let n_raw_tokens = match kind {
121 T![...] | T![..=] | T![<<=] | T![>>=] => 3,
124 self.do_bump(kind, n_raw_tokens);
128 fn at_composite2(&self, n: usize, k1: SyntaxKind, k2: SyntaxKind) -> bool {
129 let t1 = self.token_source.lookahead_nth(n + 0);
130 let t2 = self.token_source.lookahead_nth(n + 1);
131 t1.kind == k1 && t1.is_jointed_to_next && t2.kind == k2
134 fn at_composite3(&self, n: usize, k1: SyntaxKind, k2: SyntaxKind, k3: SyntaxKind) -> bool {
135 let t1 = self.token_source.lookahead_nth(n + 0);
136 let t2 = self.token_source.lookahead_nth(n + 1);
137 let t3 = self.token_source.lookahead_nth(n + 2);
138 (t1.kind == k1 && t1.is_jointed_to_next)
139 && (t2.kind == k2 && t2.is_jointed_to_next)
143 /// Checks if the current token is in `kinds`.
144 pub(crate) fn at_ts(&self, kinds: TokenSet) -> bool {
145 kinds.contains(self.current())
148 /// Checks if the current token is contextual keyword with text `t`.
149 pub(crate) fn at_contextual_kw(&self, kw: &str) -> bool {
150 self.token_source.is_keyword(kw)
153 /// Starts a new node in the syntax tree. All nodes and tokens
154 /// consumed between the `start` and the corresponding `Marker::complete`
155 /// belong to the same node.
156 pub(crate) fn start(&mut self) -> Marker {
157 let pos = self.events.len() as u32;
158 self.push_event(Event::tombstone());
162 /// Consume the next token if `kind` matches.
163 pub(crate) fn bump(&mut self, kind: SyntaxKind) {
164 assert!(self.eat(kind));
167 /// Advances the parser by one token with composite puncts handled
168 pub(crate) fn bump_any(&mut self) {
169 let kind = self.nth(0);
173 self.do_bump(kind, 1)
176 /// Advances the parser by one token, remapping its kind.
177 /// This is useful to create contextual keywords from
178 /// identifiers. For example, the lexer creates an `union`
179 /// *identifier* token, but the parser remaps it to the
180 /// `union` keyword, and keyword is what ends up in the
182 pub(crate) fn bump_remap(&mut self, kind: SyntaxKind) {
183 if self.nth(0) == EOF {
187 self.do_bump(kind, 1);
190 /// Emit error with the `message`
191 /// FIXME: this should be much more fancy and support
192 /// structured errors with spans and notes, like rustc
194 pub(crate) fn error<T: Into<String>>(&mut self, message: T) {
195 let msg = ParseError(message.into());
196 self.push_event(Event::Error { msg })
199 /// Consume the next token if it is `kind` or emit an error
201 pub(crate) fn expect(&mut self, kind: SyntaxKind) -> bool {
205 self.error(format!("expected {:?}", kind));
209 /// Create an error node and consume the next token.
210 pub(crate) fn err_and_bump(&mut self, message: &str) {
211 self.err_recover(message, TokenSet::EMPTY);
214 /// Create an error node and consume the next token.
215 pub(crate) fn err_recover(&mut self, message: &str, recovery: TokenSet) {
216 match self.current() {
217 T!['{'] | T!['}'] => {
224 if self.at_ts(recovery) {
229 let m = self.start();
232 m.complete(self, ERROR);
235 fn do_bump(&mut self, kind: SyntaxKind, n_raw_tokens: u8) {
236 for _ in 0..n_raw_tokens {
237 self.token_source.bump();
240 self.push_event(Event::Token { kind, n_raw_tokens });
243 fn push_event(&mut self, event: Event) {
244 self.events.push(event)
248 /// See `Parser::start`.
249 pub(crate) struct Marker {
255 fn new(pos: u32) -> Marker {
256 Marker { pos, bomb: DropBomb::new("Marker must be either completed or abandoned") }
259 /// Finishes the syntax tree node and assigns `kind` to it,
260 /// and mark the create a `CompletedMarker` for possible future
261 /// operation like `.precede()` to deal with forward_parent.
262 pub(crate) fn complete(mut self, p: &mut Parser, kind: SyntaxKind) -> CompletedMarker {
264 let idx = self.pos as usize;
265 match p.events[idx] {
266 Event::Start { kind: ref mut slot, .. } => {
271 let finish_pos = p.events.len() as u32;
272 p.push_event(Event::Finish);
273 CompletedMarker::new(self.pos, finish_pos, kind)
276 /// Abandons the syntax tree node. All its children
277 /// are attached to its parent instead.
278 pub(crate) fn abandon(mut self, p: &mut Parser) {
280 let idx = self.pos as usize;
281 if idx == p.events.len() - 1 {
282 match p.events.pop() {
283 Some(Event::Start { kind: TOMBSTONE, forward_parent: None }) => (),
290 pub(crate) struct CompletedMarker {
296 impl CompletedMarker {
297 fn new(start_pos: u32, finish_pos: u32, kind: SyntaxKind) -> Self {
298 CompletedMarker { start_pos, finish_pos, kind }
301 /// This method allows to create a new node which starts
302 /// *before* the current one. That is, parser could start
303 /// node `A`, then complete it, and then after parsing the
304 /// whole `A`, decide that it should have started some node
305 /// `B` before starting `A`. `precede` allows to do exactly
306 /// that. See also docs about `forward_parent` in `Event::Start`.
308 /// Given completed events `[START, FINISH]` and its corresponding
309 /// `CompletedMarker(pos: 0, _)`.
310 /// Append a new `START` events as `[START, FINISH, NEWSTART]`,
311 /// then mark `NEWSTART` as `START`'s parent with saving its relative
312 /// distance to `NEWSTART` into forward_parent(=2 in this case);
313 pub(crate) fn precede(self, p: &mut Parser) -> Marker {
314 let new_pos = p.start();
315 let idx = self.start_pos as usize;
316 match p.events[idx] {
317 Event::Start { ref mut forward_parent, .. } => {
318 *forward_parent = Some(new_pos.pos - self.start_pos);
325 /// Undo this completion and turns into a `Marker`
326 pub(crate) fn undo_completion(self, p: &mut Parser) -> Marker {
327 let start_idx = self.start_pos as usize;
328 let finish_idx = self.finish_pos as usize;
329 match p.events[start_idx] {
330 Event::Start { ref mut kind, forward_parent: None } => *kind = TOMBSTONE,
333 match p.events[finish_idx] {
334 ref mut slot @ Event::Finish => *slot = Event::tombstone(),
337 Marker::new(self.start_pos)
340 pub(crate) fn kind(&self) -> SyntaxKind {