parser_lang/parser.rs
1//! The token cursor a recursive-descent grammar threads.
2
3use alloc::boxed::Box;
4use alloc::format;
5use alloc::vec::Vec;
6
7use diag_lang::{Diagnostic, Label, Severity};
8use token_lang::{Span, Token, TokenKind};
9
10/// A saved cursor position, taken by [`Parser::checkpoint`] and restored by
11/// [`Parser::rewind`].
12///
13/// A checkpoint captures both the cursor and the number of diagnostics recorded so
14/// far, so rewinding to it un-does a speculative parse completely — the cursor
15/// moves back and any errors recorded since are dropped. It is `Copy`, so taking
16/// one is free and it can be kept in a local.
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub struct Checkpoint {
19 pos: usize,
20 errors: usize,
21}
22
23/// A cursor over a slice of [`Token`]s, with error recovery, that a hand-written
24/// recursive-descent grammar drives.
25///
26/// `Parser` holds the borrowed token stream, the current position, and the
27/// diagnostics recorded so far. A grammar is a set of functions that take
28/// `&mut Parser` and return `Option<T>` — `Some(node)` on success, `None` after a
29/// recoverable error has been recorded. The cursor skips trivia automatically
30/// (anything [`TokenKind::is_trivia`] holds for), so the grammar only ever sees
31/// significant tokens, and it stops cleanly at the end of input.
32///
33/// Kinds are matched with predicates rather than equality — `at(|k| matches!(k,
34/// Kind::Plus))` — so a kind that carries data (an interned identifier, a literal)
35/// works without a `PartialEq` bound, and matching a *category* never accidentally
36/// compares the payload.
37///
38/// # Examples
39///
40/// ```
41/// use parser_lang::{Parser, Span, Token, TokenKind};
42///
43/// #[derive(Clone, Copy, PartialEq)]
44/// enum Kind { Num, Plus, Eof }
45/// impl TokenKind for Kind {
46/// fn is_eof(&self) -> bool { matches!(self, Kind::Eof) }
47/// }
48///
49/// // `1 + 2`, terminated.
50/// let tokens = [
51/// Token::new(Kind::Num, Span::new(0, 1)),
52/// Token::new(Kind::Plus, Span::new(2, 3)),
53/// Token::new(Kind::Num, Span::new(4, 5)),
54/// Token::new(Kind::Eof, Span::empty(5)),
55/// ];
56///
57/// let mut p = Parser::new(&tokens);
58/// assert!(p.at(|k| matches!(k, Kind::Num)));
59/// p.bump();
60/// assert!(p.eat(|k| matches!(k, Kind::Plus)).is_some());
61/// assert!(p.at(|k| matches!(k, Kind::Num)));
62/// p.bump();
63/// assert!(p.at_end());
64/// ```
65pub struct Parser<'t, K> {
66 tokens: &'t [Token<K>],
67 /// Index of the current significant token, or `tokens.len()` past the end. The
68 /// type's methods keep it parked on a non-trivia token.
69 pos: usize,
70 /// Where to attribute an error reported at end of input.
71 eof_span: Span,
72 errors: Vec<Diagnostic>,
73}
74
75impl<'t, K: TokenKind> Parser<'t, K> {
76 /// Creates a cursor over `tokens`, positioned at the first significant token.
77 ///
78 /// Leading trivia is skipped immediately. The stream need not end with an
79 /// end-of-input token, but if it does the cursor stops on it rather than
80 /// running past.
81 ///
82 /// # Examples
83 ///
84 /// ```
85 /// use parser_lang::{Parser, Span, Token, TokenKind};
86 ///
87 /// #[derive(Clone, Copy)]
88 /// enum Kind { Word, Space }
89 /// impl TokenKind for Kind {
90 /// fn is_trivia(&self) -> bool { matches!(self, Kind::Space) }
91 /// }
92 ///
93 /// // Leading whitespace is skipped on construction.
94 /// let tokens = [
95 /// Token::new(Kind::Space, Span::new(0, 1)),
96 /// Token::new(Kind::Word, Span::new(1, 5)),
97 /// ];
98 /// let p = Parser::new(&tokens);
99 /// assert!(p.at(|k| matches!(k, Kind::Word)));
100 /// ```
101 #[must_use]
102 pub fn new(tokens: &'t [Token<K>]) -> Self {
103 let eof_span = tokens
104 .last()
105 .map_or(Span::empty(0), |t| Span::empty(t.span().end().to_u32()));
106 let mut parser = Self {
107 tokens,
108 pos: 0,
109 eof_span,
110 errors: Vec::new(),
111 };
112 parser.skip_trivia();
113 parser
114 }
115
116 /// Advances the cursor past any trivia tokens, parking it on the next
117 /// significant token or at the end.
118 fn skip_trivia(&mut self) {
119 while self.tokens.get(self.pos).is_some_and(Token::is_trivia) {
120 self.pos += 1;
121 }
122 }
123
124 /// Returns the current significant token without consuming it, or `None` at the
125 /// end of input.
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use parser_lang::{Parser, Span, Token, TokenKind};
131 /// # #[derive(Clone, Copy)] enum K { A }
132 /// # impl TokenKind for K {}
133 /// let tokens = [Token::new(K::A, Span::new(0, 1))];
134 /// let p = Parser::new(&tokens);
135 /// assert_eq!(p.peek().map(|t| t.span()), Some(Span::new(0, 1)));
136 /// ```
137 #[must_use]
138 pub fn peek(&self) -> Option<&'t Token<K>> {
139 self.tokens.get(self.pos)
140 }
141
142 /// Returns the kind of the current significant token, or `None` at the end.
143 #[must_use]
144 pub fn peek_kind(&self) -> Option<&'t K> {
145 self.peek().map(Token::kind)
146 }
147
148 /// Returns the span of the current token, or an empty span at the end of input
149 /// (positioned just past the last token), so an error reported at the end still
150 /// points somewhere sensible.
151 #[must_use]
152 pub fn span(&self) -> Span {
153 self.peek().map_or(self.eof_span, Token::span)
154 }
155
156 /// Returns `true` at the end of input: when there is no current token, or the
157 /// current token is the end-of-input marker.
158 #[must_use]
159 pub fn at_end(&self) -> bool {
160 self.peek().is_none_or(Token::is_eof)
161 }
162
163 /// Returns `true` if the current token's kind satisfies `pred`. Always `false`
164 /// at the end of input.
165 ///
166 /// # Examples
167 ///
168 /// ```
169 /// use parser_lang::{Parser, Span, Token, TokenKind};
170 /// # #[derive(Clone, Copy)] enum K { Plus, Minus }
171 /// # impl TokenKind for K {}
172 /// let tokens = [Token::new(K::Plus, Span::new(0, 1))];
173 /// let p = Parser::new(&tokens);
174 /// assert!(p.at(|k| matches!(k, K::Plus)));
175 /// assert!(!p.at(|k| matches!(k, K::Minus)));
176 /// ```
177 #[must_use]
178 pub fn at(&self, pred: impl FnOnce(&K) -> bool) -> bool {
179 self.peek_kind().is_some_and(pred)
180 }
181
182 /// Consumes and returns the current significant token, advancing to the next
183 /// one. Returns `None` (and does not move) at the end of input.
184 pub fn bump(&mut self) -> Option<&'t Token<K>> {
185 let token = self.tokens.get(self.pos)?;
186 self.pos += 1;
187 self.skip_trivia();
188 Some(token)
189 }
190
191 /// Consumes the current token if its kind satisfies `pred`, returning it;
192 /// otherwise leaves the cursor untouched and returns `None`.
193 ///
194 /// # Examples
195 ///
196 /// ```
197 /// use parser_lang::{Parser, Span, Token, TokenKind};
198 /// # #[derive(Clone, Copy)] enum K { Comma, Num }
199 /// # impl TokenKind for K {}
200 /// let tokens = [Token::new(K::Num, Span::new(0, 1))];
201 /// let mut p = Parser::new(&tokens);
202 /// assert!(p.eat(|k| matches!(k, K::Comma)).is_none()); // not a comma
203 /// assert!(p.eat(|k| matches!(k, K::Num)).is_some()); // consumed
204 /// ```
205 pub fn eat(&mut self, pred: impl FnOnce(&K) -> bool) -> Option<&'t Token<K>> {
206 if self.at(pred) { self.bump() } else { None }
207 }
208
209 /// Consumes the current token if its kind satisfies `pred`; otherwise records an
210 /// "expected `{description}`" diagnostic at the current position and returns
211 /// `None`.
212 ///
213 /// This is the workhorse for required tokens: the grammar names what it wanted
214 /// (`description`), and on a mismatch the error is recorded for later rendering
215 /// while parsing continues — the caller decides whether to recover.
216 ///
217 /// # Examples
218 ///
219 /// ```
220 /// use parser_lang::{Parser, Span, Token, TokenKind};
221 /// # #[derive(Clone, Copy)] enum K { RParen, Num }
222 /// # impl TokenKind for K {}
223 /// let tokens = [Token::new(K::Num, Span::new(0, 1))];
224 /// let mut p = Parser::new(&tokens);
225 /// assert!(p.expect(|k| matches!(k, K::RParen), "`)`").is_none());
226 /// assert!(p.has_errors());
227 /// ```
228 pub fn expect(
229 &mut self,
230 pred: impl FnOnce(&K) -> bool,
231 description: &str,
232 ) -> Option<&'t Token<K>> {
233 match self.eat(pred) {
234 Some(token) => Some(token),
235 None => {
236 self.error(format!("expected {description}"));
237 None
238 }
239 }
240 }
241
242 /// Records an error diagnostic at the current position.
243 ///
244 /// # Examples
245 ///
246 /// ```
247 /// use parser_lang::{Parser, Span, Token, TokenKind};
248 /// # #[derive(Clone, Copy)] enum K { Bad }
249 /// # impl TokenKind for K {}
250 /// let tokens = [Token::new(K::Bad, Span::new(0, 3))];
251 /// let mut p = Parser::new(&tokens);
252 /// p.error("unexpected token");
253 /// assert_eq!(p.errors().len(), 1);
254 /// ```
255 pub fn error(&mut self, message: impl Into<Box<str>>) {
256 let span = self.span();
257 self.error_at(span, message);
258 }
259
260 /// Records an error diagnostic at a specific span — for instance pointing back
261 /// at an unclosed opening delimiter rather than at the current token.
262 pub fn error_at(&mut self, span: Span, message: impl Into<Box<str>>) {
263 self.errors.push(Diagnostic::new(
264 Severity::Error,
265 message,
266 Label::unlabelled(span),
267 ));
268 }
269
270 /// Skips tokens until the current one satisfies `sync`, or the end of input is
271 /// reached, leaving the cursor *on* the synchronizing token.
272 ///
273 /// This is the recovery primitive: after recording an error, advance to a known
274 /// landmark (a statement terminator, a closing brace) and resume parsing there,
275 /// so one malformed construct does not derail the rest of the input. It always
276 /// makes progress and always stops at the end marker, so it cannot run away.
277 ///
278 /// # Examples
279 ///
280 /// ```
281 /// use parser_lang::{Parser, Span, Token, TokenKind};
282 /// # #[derive(Clone, Copy)] enum K { Junk, Semi, Eof }
283 /// # impl TokenKind for K { fn is_eof(&self) -> bool { matches!(self, K::Eof) } }
284 /// let tokens = [
285 /// Token::new(K::Junk, Span::new(0, 1)),
286 /// Token::new(K::Junk, Span::new(1, 2)),
287 /// Token::new(K::Semi, Span::new(2, 3)),
288 /// Token::new(K::Eof, Span::empty(3)),
289 /// ];
290 /// let mut p = Parser::new(&tokens);
291 /// p.recover(|k| matches!(k, K::Semi));
292 /// assert!(p.at(|k| matches!(k, K::Semi)));
293 /// ```
294 pub fn recover(&mut self, sync: impl Fn(&K) -> bool) {
295 while let Some(token) = self.tokens.get(self.pos) {
296 if token.is_eof() || sync(token.kind()) {
297 return;
298 }
299 self.pos += 1;
300 self.skip_trivia();
301 }
302 }
303
304 /// Parses zero or more items, calling `parse` until it returns `None`, and
305 /// collects the results.
306 ///
307 /// A `parse` that returns `Some` without advancing the cursor would loop
308 /// forever; this guards against that by stopping if no progress was made.
309 ///
310 /// # Examples
311 ///
312 /// ```
313 /// use parser_lang::{Parser, Span, Token, TokenKind};
314 /// # #[derive(Clone, Copy)] enum K { Num, Eof }
315 /// # impl TokenKind for K { fn is_eof(&self) -> bool { matches!(self, K::Eof) } }
316 /// let tokens = [
317 /// Token::new(K::Num, Span::new(0, 1)),
318 /// Token::new(K::Num, Span::new(1, 2)),
319 /// Token::new(K::Eof, Span::empty(2)),
320 /// ];
321 /// let mut p = Parser::new(&tokens);
322 /// let nums = p.repeated(|p| p.eat(|k| matches!(k, K::Num)).map(|t| t.span()));
323 /// assert_eq!(nums.len(), 2);
324 /// ```
325 pub fn repeated<T>(&mut self, mut parse: impl FnMut(&mut Self) -> Option<T>) -> Vec<T> {
326 let mut items = Vec::new();
327 loop {
328 let before = self.pos;
329 match parse(self) {
330 Some(item) => {
331 items.push(item);
332 if self.pos == before {
333 break; // no progress: stop rather than spin
334 }
335 }
336 None => break,
337 }
338 }
339 items
340 }
341
342 /// Parses a possibly-empty list of items produced by `parse`, separated by
343 /// tokens matching `sep` (such as a comma), and collects the results.
344 ///
345 /// Parsing stops after a separator that is not followed by another item (a
346 /// trailing separator), or when `parse` first returns `None` (an empty list).
347 ///
348 /// # Examples
349 ///
350 /// ```
351 /// use parser_lang::{Parser, Span, Token, TokenKind};
352 /// # #[derive(Clone, Copy)] enum K { Num, Comma, Eof }
353 /// # impl TokenKind for K { fn is_eof(&self) -> bool { matches!(self, K::Eof) } }
354 /// // `1, 2, 3`
355 /// let tokens = [
356 /// Token::new(K::Num, Span::new(0, 1)),
357 /// Token::new(K::Comma, Span::new(1, 2)),
358 /// Token::new(K::Num, Span::new(3, 4)),
359 /// Token::new(K::Comma, Span::new(4, 5)),
360 /// Token::new(K::Num, Span::new(6, 7)),
361 /// Token::new(K::Eof, Span::empty(7)),
362 /// ];
363 /// let mut p = Parser::new(&tokens);
364 /// let items = p.separated(
365 /// |k| matches!(k, K::Comma),
366 /// |p| p.eat(|k| matches!(k, K::Num)).map(|t| t.span()),
367 /// );
368 /// assert_eq!(items.len(), 3);
369 /// ```
370 pub fn separated<T>(
371 &mut self,
372 mut sep: impl FnMut(&K) -> bool,
373 mut parse: impl FnMut(&mut Self) -> Option<T>,
374 ) -> Vec<T> {
375 let mut items = Vec::new();
376 match parse(self) {
377 Some(first) => items.push(first),
378 None => return items,
379 }
380 while self.eat(&mut sep).is_some() {
381 let before = self.pos;
382 match parse(self) {
383 Some(item) => {
384 items.push(item);
385 if self.pos == before {
386 break;
387 }
388 }
389 None => break,
390 }
391 }
392 items
393 }
394
395 /// Takes a snapshot of the cursor and the error count, for speculative parsing.
396 ///
397 /// Pair it with [`rewind`](Parser::rewind) to try a parse and back out of it
398 /// cleanly if it does not work — the cursor returns to where it was and any
399 /// diagnostics recorded in the meantime are dropped.
400 #[must_use]
401 pub fn checkpoint(&self) -> Checkpoint {
402 Checkpoint {
403 pos: self.pos,
404 errors: self.errors.len(),
405 }
406 }
407
408 /// Restores the cursor and error log to a [`Checkpoint`], undoing everything
409 /// done since it was taken.
410 ///
411 /// # Examples
412 ///
413 /// ```
414 /// use parser_lang::{Parser, Span, Token, TokenKind};
415 /// # #[derive(Clone, Copy)] enum K { Num }
416 /// # impl TokenKind for K {}
417 /// let tokens = [Token::new(K::Num, Span::new(0, 1))];
418 /// let mut p = Parser::new(&tokens);
419 /// let cp = p.checkpoint();
420 /// p.bump();
421 /// p.error("speculative");
422 /// p.rewind(cp); // cursor and the recorded error are both rolled back
423 /// assert!(!p.has_errors());
424 /// assert!(p.at(|k| matches!(k, K::Num)));
425 /// ```
426 pub fn rewind(&mut self, checkpoint: Checkpoint) {
427 self.pos = checkpoint.pos;
428 self.errors.truncate(checkpoint.errors);
429 }
430
431 /// Returns the diagnostics recorded so far, in the order they occurred.
432 #[must_use]
433 pub fn errors(&self) -> &[Diagnostic] {
434 &self.errors
435 }
436
437 /// Returns `true` if any diagnostic has been recorded.
438 #[must_use]
439 pub fn has_errors(&self) -> bool {
440 !self.errors.is_empty()
441 }
442
443 /// Consumes the parser, returning all recorded diagnostics in source order.
444 #[must_use]
445 pub fn into_errors(self) -> Vec<Diagnostic> {
446 self.errors
447 }
448}
449
450#[cfg(test)]
451mod tests {
452 use super::*;
453
454 #[derive(Clone, Copy, Debug, PartialEq)]
455 enum K {
456 Num,
457 Plus,
458 Space,
459 Eof,
460 }
461 impl TokenKind for K {
462 fn is_trivia(&self) -> bool {
463 matches!(self, K::Space)
464 }
465 fn is_eof(&self) -> bool {
466 matches!(self, K::Eof)
467 }
468 }
469
470 fn toks(kinds: &[K]) -> Vec<Token<K>> {
471 kinds
472 .iter()
473 .enumerate()
474 .map(|(i, k)| Token::new(*k, Span::new(i as u32, i as u32 + 1)))
475 .collect()
476 }
477
478 #[test]
479 fn test_new_skips_leading_trivia() {
480 let t = toks(&[K::Space, K::Space, K::Num]);
481 let p = Parser::new(&t);
482 assert!(p.at(|k| matches!(k, K::Num)));
483 }
484
485 #[test]
486 fn test_bump_skips_trailing_trivia() {
487 let t = toks(&[K::Num, K::Space, K::Plus]);
488 let mut p = Parser::new(&t);
489 p.bump();
490 assert!(p.at(|k| matches!(k, K::Plus)));
491 }
492
493 #[test]
494 fn test_navigation_is_total_on_empty_stream() {
495 let t: Vec<Token<K>> = Vec::new();
496 let mut p = Parser::new(&t);
497 assert!(p.peek().is_none());
498 assert!(p.at_end());
499 assert!(p.bump().is_none());
500 assert_eq!(p.span(), Span::empty(0));
501 }
502
503 #[test]
504 fn test_at_end_true_on_eof_marker() {
505 let t = toks(&[K::Num, K::Eof]);
506 let mut p = Parser::new(&t);
507 assert!(!p.at_end());
508 p.bump();
509 assert!(p.at_end());
510 }
511
512 #[test]
513 fn test_expect_records_error_and_returns_none() {
514 let t = toks(&[K::Num]);
515 let mut p = Parser::new(&t);
516 assert!(p.expect(|k| matches!(k, K::Plus), "`+`").is_none());
517 assert_eq!(p.errors().len(), 1);
518 }
519
520 #[test]
521 fn test_recover_stops_at_sync_and_at_eof() {
522 let t = toks(&[K::Num, K::Num, K::Plus, K::Eof]);
523 let mut p = Parser::new(&t);
524 p.recover(|k| matches!(k, K::Plus));
525 assert!(p.at(|k| matches!(k, K::Plus)));
526
527 // No sync present -> stop at the eof marker, not past it.
528 let t2 = toks(&[K::Num, K::Num, K::Eof]);
529 let mut p2 = Parser::new(&t2);
530 p2.recover(|k| matches!(k, K::Plus));
531 assert!(p2.at_end());
532 }
533
534 #[test]
535 fn test_checkpoint_rewinds_cursor_and_errors() {
536 let t = toks(&[K::Num, K::Plus]);
537 let mut p = Parser::new(&t);
538 let cp = p.checkpoint();
539 p.bump();
540 p.error("nope");
541 p.rewind(cp);
542 assert!(!p.has_errors());
543 assert!(p.at(|k| matches!(k, K::Num)));
544 }
545
546 #[test]
547 fn test_repeated_stops_without_progress() {
548 let t = toks(&[K::Num]);
549 let mut p = Parser::new(&t);
550 // A parse that never consumes returns Some once then would spin; the guard
551 // breaks after the first no-progress iteration.
552 let collected = p.repeated(|_p| Some(1u8));
553 assert_eq!(collected, [1]);
554 }
555}