flux_syntax/parser/
lookahead.rs

1//! Support for "peeking" into the token stream to decide how to parse.
2
3use std::fmt;
4
5use rustc_span::{Symbol, edition::Edition};
6
7use crate::{
8    ParseCtxt, ParseError, ParseResult,
9    lexer::{Token, TokenKind},
10    surface::BinOp,
11    symbols,
12};
13
14/// See [`PeekExpected`]
15#[derive(Debug)]
16pub enum Expected {
17    Str(&'static str),
18    Sym(Symbol),
19}
20
21impl fmt::Display for Expected {
22    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23        match self {
24            Expected::Str(descr) => write!(f, "{descr}"),
25            Expected::Sym(sym) => write!(f, "{sym}"),
26        }
27    }
28}
29
30/// A trait for testing whether a token matches a rule.
31pub(crate) trait Peek: Copy {
32    /// Returns true if a token matches this rule
33    ///
34    /// The rule is edition dependent because keywords can vary.
35    fn matches(self, tok: TokenKind, edition: Edition) -> bool;
36}
37
38/// A subtrait of [`Peek`] for rules that have an *expected description*.
39///
40/// This is used to automatically build error messages of the form:
41/// ```text
42/// expected one of `expected1`, `expected2`, ...
43/// ```
44/// where each `expected` is the description of a peek rule.
45pub(crate) trait PeekExpected: Peek {
46    fn expected(self) -> Expected;
47}
48
49/// Use a [`TokenKind`] to match by exact equality
50impl Peek for TokenKind {
51    fn matches(self, tok: TokenKind, _: Edition) -> bool {
52        self == tok
53    }
54}
55impl PeekExpected for TokenKind {
56    fn expected(self) -> Expected {
57        Expected::Str(TokenKind::descr(&self))
58    }
59}
60
61/// A struct that can be used to match a non-reserved identifier
62#[derive(Clone, Copy)]
63pub(crate) struct NonReserved;
64impl Peek for NonReserved {
65    fn matches(self, tok: TokenKind, edition: Edition) -> bool {
66        match tok {
67            TokenKind::Ident(sym) => !symbols::is_reserved(sym, edition),
68            _ => false,
69        }
70    }
71}
72impl PeekExpected for NonReserved {
73    fn expected(self) -> Expected {
74        Expected::Str("identifier")
75    }
76}
77
78/// A struct that can be used to match any literal
79#[derive(Clone, Copy)]
80pub(crate) struct AnyLit;
81impl Peek for AnyLit {
82    fn matches(self, tok: TokenKind, _: Edition) -> bool {
83        matches!(tok, TokenKind::Literal(_))
84    }
85}
86impl PeekExpected for AnyLit {
87    fn expected(self) -> Expected {
88        Expected::Str("literal")
89    }
90}
91
92/// There are some lexing ambiguities with `>>` because it can represet both a right shift or two
93/// closing angle brackets (e.g., `Vec<Option<i32>>`). We solve the ambiguity by giving `>` a
94/// special token if it's immediately followed by another `>`,  i.e., `>>` is tokenized as
95/// [`TokenKind::GtFollowedByGt`] followed by [`TokenKind::Gt`].
96///
97/// Use this struct to match on a right angle bracket for the purpose of parsing generics.
98#[derive(Clone, Copy)]
99pub(crate) struct RAngle;
100impl Peek for RAngle {
101    fn matches(self, tok: TokenKind, _: Edition) -> bool {
102        matches!(tok, TokenKind::GtFollowedByGt | TokenKind::Gt)
103    }
104}
105impl PeekExpected for RAngle {
106    fn expected(self) -> Expected {
107        Expected::Str(">")
108    }
109}
110
111/// This is the same as [`RAngle`] but for opening angle brackets.
112///
113/// It is less common to have two opening angle brackets, but it appears in stuff like
114/// `<<Self as Trait1>::Assoc1 as Trait2>::Assoc2`
115#[derive(Clone, Copy)]
116pub(crate) struct LAngle;
117impl Peek for LAngle {
118    fn matches(self, tok: TokenKind, _: Edition) -> bool {
119        matches!(tok, TokenKind::LtFollowedByLt | TokenKind::Lt)
120    }
121}
122impl PeekExpected for LAngle {
123    fn expected(self) -> Expected {
124        Expected::Str("<")
125    }
126}
127
128/// Use a [`Symbol`] to match a [`TokenKind::Ident`] equal to it.
129impl Peek for Symbol {
130    fn matches(self, tok: TokenKind, _: Edition) -> bool {
131        matches!(tok, TokenKind::Ident(sym) if sym == self)
132    }
133}
134impl PeekExpected for Symbol {
135    fn expected(self) -> Expected {
136        Expected::Sym(self)
137    }
138}
139
140/// A rule that matches if any of the rules in a list matches
141#[derive(Clone, Copy)]
142pub(crate) struct AnyOf<T, const N: usize>(pub [T; N]);
143impl<T: Peek, const N: usize> Peek for AnyOf<T, N> {
144    fn matches(self, tok: TokenKind, edition: Edition) -> bool {
145        self.0.into_iter().any(|t| t.matches(tok, edition))
146    }
147}
148
149/// An arbitrary peek rule defined by a predicate on [`TokenKind`]
150impl<F: FnOnce(TokenKind) -> bool + Copy> Peek for F {
151    fn matches(self, tok: TokenKind, _: Edition) -> bool {
152        (self)(tok)
153    }
154}
155
156/// Support for checking the next token in a stream to decide how to parse.
157///
158/// An important advantage of using this struct over [`ParseCtxt::peek`] is that here we
159/// automatically construct an appropriate error message based on the token alternatives
160/// that get peeked.
161///
162/// Use [`ParseCtxt::lookahead1`] to construct this object.
163pub(crate) struct Lookahead1<'a, 'cx> {
164    /// List of "expected" tokens that have been peeked by this struct
165    expected: Vec<Expected>,
166    cx: &'a mut ParseCtxt<'cx>,
167}
168
169impl<'a, 'cx> Lookahead1<'a, 'cx> {
170    fn new(cx: &'a mut ParseCtxt<'cx>) -> Self {
171        Lookahead1 { expected: Vec::new(), cx }
172    }
173
174    /// Like [`ParseCtxt::lookahead1`] but it records the expected token to construct an error in
175    /// case parsing can't proceed. If this method returns true, this [`Lookahead1`] object should be
176    /// discarded.
177    pub(crate) fn peek<T: PeekExpected>(&mut self, t: T) -> bool {
178        self.expected.push(t.expected());
179        self.cx.peek(t)
180    }
181
182    /// Like [`ParseCtxt::advance_if`] but it records the expected token to construct an error in
183    /// case parsing can't proceed. If this method returns true, this [`Lookahead1`] object should be
184    /// discarded.
185    pub(crate) fn advance_if<T: PeekExpected>(&mut self, t: T) -> bool {
186        self.expected.push(t.expected());
187        self.cx.advance_if(t)
188    }
189
190    /// Create an `unexpected token` error based on the expected tokens that have been peeked
191    /// with this [`Lookahead1`] object.
192    pub(crate) fn into_error(self) -> ParseError {
193        self.cx.unexpected_token(self.expected)
194    }
195}
196
197impl<'cx> ParseCtxt<'cx> {
198    /// Returns the token at the requested position.
199    pub(crate) fn at(&mut self, n: usize) -> Token {
200        self.tokens.at(n)
201    }
202
203    /// Looks at the next token in the underlying cursor to determine whether it matches the
204    /// requested type of token. Does not advance the position of the cursor.
205    pub(crate) fn peek<T: Peek>(&mut self, t: T) -> bool {
206        self.peek_at(0, t)
207    }
208
209    /// Looks at the next two tokens
210    pub(crate) fn peek2<T1: Peek, T2: Peek>(&mut self, t1: T1, t2: T2) -> bool {
211        self.peek_at(0, t1) && self.peek_at(1, t2)
212    }
213
214    /// Looks at the next three tokens
215    pub(crate) fn peek3<T1: Peek, T2: Peek, T3: Peek>(&mut self, t1: T1, t2: T2, t3: T3) -> bool {
216        self.peek_at(0, t1) && self.peek_at(1, t2) && self.peek_at(2, t3)
217    }
218
219    fn peek_at<T: Peek>(&mut self, n: usize, t: T) -> bool {
220        let tok = self.at(n);
221        t.matches(tok.kind, self.edition)
222    }
223
224    /// Looks whether the next token matches a binary operation. In case of a match, returns
225    /// the corresponding binary operation and its size in number of tokens. This function
226    /// doesn't advance the position of the underlying cursor.
227    pub(crate) fn peek_binop(&mut self) -> Option<(BinOp, usize)> {
228        let op = match self.at(0).kind {
229            TokenKind::Iff => (BinOp::Iff, 1),
230            TokenKind::FatArrow => (BinOp::Imp, 1),
231            TokenKind::OrOr => (BinOp::Or, 1),
232            TokenKind::AndAnd => (BinOp::And, 1),
233            TokenKind::EqEq => (BinOp::Eq, 1),
234            TokenKind::Ne => (BinOp::Ne, 1),
235            TokenKind::Lt => (BinOp::Lt, 1),
236            TokenKind::Gt => (BinOp::Gt, 1),
237            TokenKind::Le => (BinOp::Le, 1),
238            TokenKind::Ge => (BinOp::Ge, 1),
239            TokenKind::Caret => (BinOp::BitOr, 1),
240            TokenKind::And => (BinOp::BitAnd, 1),
241            TokenKind::LtFollowedByLt => (BinOp::BitShl, 2),
242            TokenKind::GtFollowedByGt => (BinOp::BitShr, 2),
243            TokenKind::Plus => (BinOp::Add, 1),
244            TokenKind::Minus => (BinOp::Sub, 1),
245            TokenKind::Star => (BinOp::Mul, 1),
246            TokenKind::Slash => (BinOp::Div, 1),
247            TokenKind::Percent => (BinOp::Mod, 1),
248            _ => return None,
249        };
250        Some(op)
251    }
252
253    /// Advances the underlying cursor to the next token
254    pub(crate) fn advance(&mut self) {
255        self.tokens.advance();
256    }
257
258    /// Advances the underlying cursor by the requested number of tokens
259    pub(crate) fn advance_by(&mut self, n: usize) {
260        self.tokens.advance_by(n);
261    }
262
263    /// Looks at the next token and advances the cursor if it matches the requested
264    /// rule. Returns `true` if there was a match (i.e., the cursor was advanced).
265    pub(crate) fn advance_if<T: Peek>(&mut self, t: T) -> bool {
266        if self.peek(t) {
267            self.advance();
268            true
269        } else {
270            false
271        }
272    }
273
274    /// Looks at the next two tokens advacing the cursor if there's a match on both of them
275    pub(crate) fn advance_if2<T1: Peek, T2: Peek>(&mut self, t1: T1, t2: T2) -> bool {
276        if self.peek2(t1, t2) {
277            self.advance_by(2);
278            true
279        } else {
280            false
281        }
282    }
283
284    /// If the next token matches the requested rule advances the cursor, otherwise returns an
285    /// `unexpected token` error.
286    pub(crate) fn expect<T: PeekExpected>(&mut self, t: T) -> ParseResult {
287        if self.advance_if(t) { Ok(()) } else { Err(self.unexpected_token(vec![t.expected()])) }
288    }
289
290    /// See documentation for [`Lookahead1`]
291    pub(crate) fn lookahead1(&mut self) -> Lookahead1<'_, 'cx> {
292        Lookahead1::new(self)
293    }
294}