crates/ra_parser/src/parser.rs

   1 //! FIXME: write short doc here
   2
   3 use std::cell::Cell;
   4
   5 use drop_bomb::DropBomb;
   6
   7 use crate::{
   8     event::Event,
   9     ParseError,
  10     SyntaxKind::{self, EOF, ERROR, TOMBSTONE},
  11     TokenSet, TokenSource, T,
  12 };
  13
  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.
  18 ///
  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,
  25     events: Vec<Event>,
  26     steps: Cell<u32>,
  27 }
  28
  29 impl<'t> Parser<'t> {
  30     pub(super) fn new(token_source: &'t mut dyn TokenSource) -> Parser<'t> {
  31         Parser { token_source, events: Vec::new(), steps: Cell::new(0) }
  32     }
  33
  34     pub(crate) fn finish(self) -> Vec<Event> {
  35         self.events
  36     }
  37
  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 {
  42         self.nth(0)
  43     }
  44
  45     /// Lookahead operation: returns the kind of the next nth
  46     /// token.
  47     pub(crate) fn nth(&self, n: usize) -> SyntaxKind {
  48         assert!(n <= 3);
  49
  50         let steps = self.steps.get();
  51         assert!(steps <= 10_000_000, "the parser seems stuck");
  52         self.steps.set(steps + 1);
  53
  54         self.token_source.lookahead_nth(n).kind
  55     }
  56
  57     /// Checks if the current token is `kind`.
  58     pub(crate) fn at(&self, kind: SyntaxKind) -> bool {
  59         self.nth_at(0, kind)
  60     }
  61
  62     pub(crate) fn nth_at(&self, n: usize, kind: SyntaxKind) -> bool {
  63         match kind {
  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![|]),
  84
  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![=]),
  89
  90             _ => self.token_source.lookahead_nth(n).kind == kind,
  91         }
  92     }
  93
  94     /// Consume the next token if `kind` matches.
  95     pub(crate) fn eat(&mut self, kind: SyntaxKind) -> bool {
  96         if !self.at(kind) {
  97             return false;
  98         }
  99         let n_raw_tokens = match kind {
 100             T![-=]
 101             | T![->]
 102             | T![::]
 103             | T![!=]
 104             | T![..]
 105             | T![*=]
 106             | T![/=]
 107             | T![&&]
 108             | T![&=]
 109             | T![%=]
 110             | T![^=]
 111             | T![+=]
 112             | T![<<]
 113             | T![<=]
 114             | T![==]
 115             | T![=>]
 116             | T![>=]
 117             | T![>>]
 118             | T![|=]
 119             | T![||] => 2,
 120
 121             T![...] | T![..=] | T![<<=] | T![>>=] => 3,
 122             _ => 1,
 123         };
 124         self.do_bump(kind, n_raw_tokens);
 125         true
 126     }
 127
 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
 132     }
 133
 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)
 140             && t3.kind == k3
 141     }
 142
 143     /// Checks if the current token is in `kinds`.
 144     pub(crate) fn at_ts(&self, kinds: TokenSet) -> bool {
 145         kinds.contains(self.current())
 146     }
 147
 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)
 151     }
 152
 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());
 159         Marker::new(pos)
 160     }
 161
 162     /// Consume the next token if `kind` matches.
 163     pub(crate) fn bump(&mut self, kind: SyntaxKind) {
 164         assert!(self.eat(kind));
 165     }
 166
 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);
 170         if kind == EOF {
 171             return;
 172         }
 173         self.do_bump(kind, 1)
 174     }
 175
 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
 181     /// final tree.
 182     pub(crate) fn bump_remap(&mut self, kind: SyntaxKind) {
 183         if self.nth(0) == EOF {
 184             // FIXME: panic!?
 185             return;
 186         }
 187         self.do_bump(kind, 1);
 188     }
 189
 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
 193     /// does.
 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 })
 197     }
 198
 199     /// Consume the next token if it is `kind` or emit an error
 200     /// otherwise.
 201     pub(crate) fn expect(&mut self, kind: SyntaxKind) -> bool {
 202         if self.eat(kind) {
 203             return true;
 204         }
 205         self.error(format!("expected {:?}", kind));
 206         false
 207     }
 208
 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());
 212     }
 213
 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!['}'] => {
 218                 self.error(message);
 219                 return;
 220             }
 221             _ => (),
 222         }
 223
 224         if self.at_ts(recovery) {
 225             self.error(message);
 226             return;
 227         }
 228
 229         let m = self.start();
 230         self.error(message);
 231         self.bump_any();
 232         m.complete(self, ERROR);
 233     }
 234
 235     fn do_bump(&mut self, kind: SyntaxKind, n_raw_tokens: u8) {
 236         for _ in 0..n_raw_tokens {
 237             self.token_source.bump();
 238         }
 239
 240         self.push_event(Event::Token { kind, n_raw_tokens });
 241     }
 242
 243     fn push_event(&mut self, event: Event) {
 244         self.events.push(event)
 245     }
 246 }
 247
 248 /// See `Parser::start`.
 249 pub(crate) struct Marker {
 250     pos: u32,
 251     bomb: DropBomb,
 252 }
 253
 254 impl Marker {
 255     fn new(pos: u32) -> Marker {
 256         Marker { pos, bomb: DropBomb::new("Marker must be either completed or abandoned") }
 257     }
 258
 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 {
 263         self.bomb.defuse();
 264         let idx = self.pos as usize;
 265         match p.events[idx] {
 266             Event::Start { kind: ref mut slot, .. } => {
 267                 *slot = kind;
 268             }
 269             _ => unreachable!(),
 270         }
 271         let finish_pos = p.events.len() as u32;
 272         p.push_event(Event::Finish);
 273         CompletedMarker::new(self.pos, finish_pos, kind)
 274     }
 275
 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) {
 279         self.bomb.defuse();
 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 }) => (),
 284                 _ => unreachable!(),
 285             }
 286         }
 287     }
 288 }
 289
 290 pub(crate) struct CompletedMarker {
 291     start_pos: u32,
 292     finish_pos: u32,
 293     kind: SyntaxKind,
 294 }
 295
 296 impl CompletedMarker {
 297     fn new(start_pos: u32, finish_pos: u32, kind: SyntaxKind) -> Self {
 298         CompletedMarker { start_pos, finish_pos, kind }
 299     }
 300
 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`.
 307     ///
 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);
 319             }
 320             _ => unreachable!(),
 321         }
 322         new_pos
 323     }
 324
 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,
 331             _ => unreachable!(),
 332         }
 333         match p.events[finish_idx] {
 334             ref mut slot @ Event::Finish => *slot = Event::tombstone(),
 335             _ => unreachable!(),
 336         }
 337         Marker::new(self.start_pos)
 338     }
 339
 340     pub(crate) fn kind(&self) -> SyntaxKind {
 341         self.kind
 342     }
 343 }