flux_syntax/parser/
lookahead.rs

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