cairo_lang_parser/
lexer.rs

1#[cfg(test)]
2#[path = "lexer_test.rs"]
3mod test;
4
5use cairo_lang_filesystem::ids::SmolStrId;
6use cairo_lang_filesystem::span::{TextOffset, TextSpan, TextWidth};
7use cairo_lang_syntax::node::Token;
8use cairo_lang_syntax::node::ast::{
9    TokenNewline, TokenSingleLineComment, TokenSingleLineDocComment, TokenSingleLineInnerComment,
10    TokenWhitespace, TriviumGreen,
11};
12use cairo_lang_syntax::node::kind::SyntaxKind;
13use salsa::Database;
14
15#[derive(Clone, PartialEq, Eq, Hash)]
16pub struct Lexer<'a> {
17    text: &'a str,
18    previous_position: TextOffset,
19    current_position: TextOffset,
20}
21
22impl<'a> Lexer<'a> {
23    /// Creates a new lexer with the given text.
24    pub fn new(text: &'a str) -> Self {
25        Self { text, previous_position: TextOffset::START, current_position: TextOffset::START }
26    }
27
28    // Helpers.
29    fn peek(&self) -> Option<char> {
30        self.current_position.take_from(self.text).chars().next()
31    }
32
33    fn peek_nth(&self, n: usize) -> Option<char> {
34        self.current_position.take_from(self.text).chars().nth(n)
35    }
36
37    fn take(&mut self) -> Option<char> {
38        let res = self.peek()?;
39        self.current_position = self.current_position.add_width(TextWidth::from_char(res));
40        Some(res)
41    }
42
43    /// Takes a character while the given function returns true.
44    fn take_while<F>(&mut self, f: F)
45    where
46        F: Fn(char) -> bool,
47    {
48        while self.peek().map(&f).unwrap_or(false) {
49            self.take();
50        }
51    }
52
53    fn peek_text_span(&self) -> TextSpan {
54        TextSpan::new(self.previous_position, self.current_position)
55    }
56
57    fn consume_text_span(&mut self) -> TextSpan {
58        let val = self.peek_text_span();
59        self.previous_position = self.current_position;
60        val
61    }
62
63    // Trivia matchers.
64    fn match_trivia(&mut self, db: &'a dyn Database, leading: bool) -> Vec<TriviumGreen<'a>> {
65        let mut res: Vec<TriviumGreen<'a>> = Vec::new();
66        while let Some(current) = self.peek() {
67            let trivium = match current {
68                ' ' | '\r' | '\t' => self.match_trivium_whitespace(db),
69                '\n' => self.match_trivium_newline(db),
70                '/' if self.peek_nth(1) == Some('/') => self.match_trivium_single_line_comment(db),
71                _ => break,
72            };
73            res.push(trivium);
74            if current == '\n' && !leading {
75                break;
76            }
77        }
78        res
79    }
80
81    /// Assumes the next character is one of [' ', '\r', '\t'].
82    fn match_trivium_whitespace(&mut self, db: &'a dyn Database) -> TriviumGreen<'a> {
83        self.take_while(|s| matches!(s, ' ' | '\r' | '\t'));
84        let span = self.consume_text_span();
85        let text = span.take(self.text);
86        TokenWhitespace::new_green(db, SmolStrId::from(db, text)).into()
87    }
88
89    /// Assumes the next character is '\n'.
90    fn match_trivium_newline(&mut self, db: &'a dyn Database) -> TriviumGreen<'a> {
91        self.take();
92        let span = self.consume_text_span();
93        let text = span.take(self.text);
94        TokenNewline::new_green(db, SmolStrId::from(db, text)).into()
95    }
96
97    /// Assumes the next 2 characters are "//".
98    fn match_trivium_single_line_comment(&mut self, db: &'a dyn Database) -> TriviumGreen<'a> {
99        match self.peek_nth(2) {
100            // `///` is a doc comment, but `////` (4+ slashes) is a regular comment. This matches
101            // `cairo-lang-doc`, which discards a doc comment whose content starts with `/`.
102            Some('/') if self.peek_nth(3) != Some('/') => {
103                self.take_while(|c| c != '\n');
104                let span = self.consume_text_span();
105                let text = span.take(self.text);
106                TokenSingleLineDocComment::new_green(db, SmolStrId::from(db, text)).into()
107            }
108            Some('!') => {
109                self.take_while(|c| c != '\n');
110                let span = self.consume_text_span();
111                let text = span.take(self.text);
112                TokenSingleLineInnerComment::new_green(db, SmolStrId::from(db, text)).into()
113            }
114            _ => {
115                self.take_while(|c| c != '\n');
116                let span = self.consume_text_span();
117                let text = span.take(self.text);
118                TokenSingleLineComment::new_green(db, SmolStrId::from(db, text)).into()
119            }
120        }
121    }
122
123    // Token matchers.
124    // =================================================================================
125
126    /// Takes a number. May be decimal, hex, oct or bin.
127    fn take_token_literal_number(&mut self) -> TokenKind {
128        let special = if self.peek() == Some('0') {
129            self.take();
130            match self.peek() {
131                Some('x' | 'o' | 'b') => {
132                    match self.take() {
133                        Some('x') => self.take_while(|c| c.is_ascii_hexdigit()),
134                        Some('o') => self.take_while(|c| matches!(c, '0'..='7')),
135                        Some('b') => self.take_while(|c| matches!(c, '0'..='1')),
136                        _ => unreachable!(),
137                    }
138                    true
139                }
140                _ => false,
141            }
142        } else {
143            false
144        };
145        // Not a special case - so just reading the rest of the digits.
146        if !special {
147            self.take_while(|c| c.is_ascii_digit());
148        }
149
150        // Parse _type suffix.
151        if self.peek() == Some('_') {
152            self.take_while(|c| c.is_ascii_alphanumeric() || c == '_');
153        }
154        TokenKind::LiteralNumber
155    }
156
157    /// Takes a short string.
158    fn take_token_short_string(&mut self) -> TokenKind {
159        self.take_token_string_helper('\'');
160
161        // Parse _type suffix.
162        if self.peek() == Some('_') {
163            self.take_while(|c| c.is_ascii_alphanumeric() || c == '_');
164        }
165        TokenKind::ShortString
166    }
167
168    /// Takes a string.
169    fn take_token_string(&mut self) -> TokenKind {
170        self.take_token_string_helper('"');
171        TokenKind::String
172    }
173
174    fn take_token_string_helper(&mut self, delimiter: char) {
175        self.take();
176        let mut escaped = false;
177        while let Some(token) = self.peek() {
178            self.take();
179            match token {
180                _ if escaped => escaped = false,
181                '\\' => escaped = true,
182                _ if token == delimiter => {
183                    break;
184                }
185                _ => {}
186            };
187        }
188    }
189
190    /// Assumes the next character is [a-zA-Z_].
191    fn take_token_identifier(&mut self) -> TokenKind {
192        // TODO(spapini): Support or explicitly report general unicode characters.
193        self.take_while(|c| c.is_ascii_alphanumeric() || c == '_');
194
195        let span = self.peek_text_span();
196        match span.take(self.text) {
197            "as" => TokenKind::As,
198            "const" => TokenKind::Const,
199            "false" => TokenKind::False,
200            "true" => TokenKind::True,
201            "extern" => TokenKind::Extern,
202            "type" => TokenKind::Type,
203            "fn" => TokenKind::Function,
204            "trait" => TokenKind::Trait,
205            "impl" => TokenKind::Impl,
206            "of" => TokenKind::Of,
207            "mod" => TokenKind::Module,
208            "struct" => TokenKind::Struct,
209            "enum" => TokenKind::Enum,
210            "let" => TokenKind::Let,
211            "return" => TokenKind::Return,
212            "match" => TokenKind::Match,
213            "macro" => TokenKind::Macro,
214            "if" => TokenKind::If,
215            "loop" => TokenKind::Loop,
216            "continue" => TokenKind::Continue,
217            "break" => TokenKind::Break,
218            "else" => TokenKind::Else,
219            "while" => TokenKind::While,
220            "use" => TokenKind::Use,
221            "implicits" => TokenKind::Implicits,
222            "ref" => TokenKind::Ref,
223            "mut" => TokenKind::Mut,
224            "for" => TokenKind::For,
225            "nopanic" => TokenKind::NoPanic,
226            "pub" => TokenKind::Pub,
227            "_" => TokenKind::Underscore,
228            _ => TokenKind::Identifier,
229        }
230    }
231
232    /// Takes a single character and returns the given kind.
233    fn take_token_of_kind(&mut self, kind: TokenKind) -> TokenKind {
234        self.take();
235        kind
236    }
237
238    /// If the next character is `second_char`, returns `long_kind`, otherwise returns `short_kind`.
239    fn pick_kind(
240        &mut self,
241        second_char: char,
242        long_kind: TokenKind,
243        short_kind: TokenKind,
244    ) -> TokenKind {
245        self.take();
246        if self.peek() == Some(second_char) {
247            self.take();
248            long_kind
249        } else {
250            short_kind
251        }
252    }
253
254    pub fn match_terminal(&mut self, db: &'a dyn Database) -> LexerTerminal<'a> {
255        let leading_trivia = self.match_trivia(db, true);
256
257        let kind = if let Some(current) = self.peek() {
258            match current {
259                '0'..='9' => self.take_token_literal_number(),
260                '\'' => self.take_token_short_string(),
261                '"' => self.take_token_string(),
262                ',' => self.take_token_of_kind(TokenKind::Comma),
263                ';' => self.take_token_of_kind(TokenKind::Semicolon),
264                '?' => self.take_token_of_kind(TokenKind::QuestionMark),
265                '{' => self.take_token_of_kind(TokenKind::LBrace),
266                '}' => self.take_token_of_kind(TokenKind::RBrace),
267                '[' => self.take_token_of_kind(TokenKind::LBrack),
268                ']' => self.take_token_of_kind(TokenKind::RBrack),
269                '(' => self.take_token_of_kind(TokenKind::LParen),
270                ')' => self.take_token_of_kind(TokenKind::RParen),
271                '.' => {
272                    self.take();
273                    match self.peek() {
274                        Some('.') => self.pick_kind('=', TokenKind::DotDotEq, TokenKind::DotDot),
275                        _ => TokenKind::Dot,
276                    }
277                }
278                '*' => self.pick_kind('=', TokenKind::MulEq, TokenKind::Mul),
279                '/' => self.pick_kind('=', TokenKind::DivEq, TokenKind::Div),
280                '%' => self.pick_kind('=', TokenKind::ModEq, TokenKind::Mod),
281                '+' => self.pick_kind('=', TokenKind::PlusEq, TokenKind::Plus),
282                '#' => self.take_token_of_kind(TokenKind::Hash),
283                '$' => self.take_token_of_kind(TokenKind::Dollar),
284                '-' => {
285                    self.take();
286                    match self.peek() {
287                        Some('>') => self.take_token_of_kind(TokenKind::Arrow),
288                        Some('=') => self.take_token_of_kind(TokenKind::MinusEq),
289                        _ => TokenKind::Minus,
290                    }
291                }
292                '<' => self.pick_kind('=', TokenKind::LE, TokenKind::LT),
293                '>' => self.pick_kind('=', TokenKind::GE, TokenKind::GT),
294                'a'..='z' | 'A'..='Z' | '_' => self.take_token_identifier(),
295                ':' => self.pick_kind(':', TokenKind::ColonColon, TokenKind::Colon),
296                '!' => self.pick_kind('=', TokenKind::Neq, TokenKind::Not),
297                '~' => self.take_token_of_kind(TokenKind::BitNot),
298                '=' => {
299                    self.take();
300                    match self.peek() {
301                        Some('=') => self.take_token_of_kind(TokenKind::EqEq),
302                        Some('>') => self.take_token_of_kind(TokenKind::MatchArrow),
303                        _ => TokenKind::Eq,
304                    }
305                }
306                '&' => self.pick_kind('&', TokenKind::AndAnd, TokenKind::And),
307                '|' => self.pick_kind('|', TokenKind::OrOr, TokenKind::Or),
308                '^' => self.take_token_of_kind(TokenKind::Xor),
309                '@' => self.take_token_of_kind(TokenKind::At),
310                _ => self.take_token_of_kind(TokenKind::BadCharacters),
311            }
312        } else {
313            TokenKind::EndOfFile
314        };
315
316        let span = self.consume_text_span();
317        let text = SmolStrId::from(db, span.take(self.text));
318        let trailing_trivia = self.match_trivia(db, false);
319        let terminal_kind = token_kind_to_terminal_syntax_kind(kind);
320
321        // TODO(yuval): log(verbose) "consumed text: ..."
322        LexerTerminal { text, kind: terminal_kind, leading_trivia, trailing_trivia }
323    }
324}
325
326/// Output terminal emitted by the lexer.
327#[derive(Clone, PartialEq, Eq, Debug, salsa::SalsaValue)]
328pub struct LexerTerminal<'a> {
329    pub text: SmolStrId<'a>,
330    /// The kind of the inner token of this terminal.
331    pub kind: SyntaxKind,
332    pub leading_trivia: Vec<TriviumGreen<'a>>,
333    pub trailing_trivia: Vec<TriviumGreen<'a>>,
334}
335impl<'a> LexerTerminal<'a> {
336    pub fn width(&self, db: &dyn Database) -> TextWidth {
337        self.leading_trivia.iter().map(|t| t.0.width(db)).sum::<TextWidth>()
338            + TextWidth::from_str(self.text.long(db))
339            + self.trailing_trivia.iter().map(|t| t.0.width(db)).sum::<TextWidth>()
340    }
341
342    pub fn text(&self, db: &'a dyn Database) -> &'a str {
343        self.text.long(db)
344    }
345}
346
347#[derive(Clone, Copy, PartialEq, Debug, Eq, Hash)]
348enum TokenKind {
349    Identifier,
350
351    // Literals.
352    LiteralNumber,
353    ShortString,
354    String,
355
356    // Keywords.
357    As,
358    Const,
359    False,
360    True,
361    Extern,
362    Type,
363    Function,
364    Trait,
365    Impl,
366    Of,
367    Module,
368    Struct,
369    Enum,
370    Let,
371    Return,
372    Match,
373    Macro,
374    If,
375    While,
376    For,
377    Loop,
378    Continue,
379    Break,
380    Else,
381    Use,
382    Implicits,
383    NoPanic,
384    Pub,
385
386    // Modifiers.
387    Ref,
388    Mut,
389
390    // Punctuation.
391    And,
392    AndAnd,
393    At,
394    Or,
395    OrOr,
396    Xor,
397    EqEq,
398    Neq,
399    GE,
400    GT,
401    LE,
402    LT,
403    Not,
404    BitNot,
405    Plus,
406    PlusEq,
407    Minus,
408    MinusEq,
409    Mul,
410    MulEq,
411    Div,
412    DivEq,
413    Mod,
414    ModEq,
415
416    Colon,
417    ColonColon,
418    Comma,
419    Dollar,
420    Dot,
421    DotDot,
422    DotDotEq,
423    Eq,
424    Hash,
425    Semicolon,
426    QuestionMark,
427    Underscore,
428    LBrace,
429    RBrace,
430    LBrack,
431    RBrack,
432    LParen,
433    RParen,
434    Arrow,
435    MatchArrow,
436
437    // Meta.
438    EndOfFile,
439    BadCharacters,
440}
441
442fn token_kind_to_terminal_syntax_kind(kind: TokenKind) -> SyntaxKind {
443    match kind {
444        TokenKind::As => SyntaxKind::TerminalAs,
445        TokenKind::Const => SyntaxKind::TerminalConst,
446        TokenKind::Identifier => SyntaxKind::TerminalIdentifier,
447        TokenKind::LiteralNumber => SyntaxKind::TerminalLiteralNumber,
448        TokenKind::ShortString => SyntaxKind::TerminalShortString,
449        TokenKind::String => SyntaxKind::TerminalString,
450        TokenKind::False => SyntaxKind::TerminalFalse,
451        TokenKind::True => SyntaxKind::TerminalTrue,
452        TokenKind::Extern => SyntaxKind::TerminalExtern,
453        TokenKind::Type => SyntaxKind::TerminalType,
454        TokenKind::Function => SyntaxKind::TerminalFunction,
455        TokenKind::Trait => SyntaxKind::TerminalTrait,
456        TokenKind::Impl => SyntaxKind::TerminalImpl,
457        TokenKind::Of => SyntaxKind::TerminalOf,
458        TokenKind::Module => SyntaxKind::TerminalModule,
459        TokenKind::Struct => SyntaxKind::TerminalStruct,
460        TokenKind::Enum => SyntaxKind::TerminalEnum,
461        TokenKind::Let => SyntaxKind::TerminalLet,
462        TokenKind::Return => SyntaxKind::TerminalReturn,
463        TokenKind::Match => SyntaxKind::TerminalMatch,
464        TokenKind::If => SyntaxKind::TerminalIf,
465        TokenKind::While => SyntaxKind::TerminalWhile,
466        TokenKind::For => SyntaxKind::TerminalFor,
467        TokenKind::Loop => SyntaxKind::TerminalLoop,
468        TokenKind::Continue => SyntaxKind::TerminalContinue,
469        TokenKind::Break => SyntaxKind::TerminalBreak,
470        TokenKind::Else => SyntaxKind::TerminalElse,
471        TokenKind::Use => SyntaxKind::TerminalUse,
472        TokenKind::Implicits => SyntaxKind::TerminalImplicits,
473        TokenKind::NoPanic => SyntaxKind::TerminalNoPanic,
474        TokenKind::Pub => SyntaxKind::TerminalPub,
475        TokenKind::Macro => SyntaxKind::TerminalMacro,
476        TokenKind::And => SyntaxKind::TerminalAnd,
477        TokenKind::AndAnd => SyntaxKind::TerminalAndAnd,
478        TokenKind::At => SyntaxKind::TerminalAt,
479        TokenKind::Or => SyntaxKind::TerminalOr,
480        TokenKind::OrOr => SyntaxKind::TerminalOrOr,
481        TokenKind::Xor => SyntaxKind::TerminalXor,
482        TokenKind::EqEq => SyntaxKind::TerminalEqEq,
483        TokenKind::Neq => SyntaxKind::TerminalNeq,
484        TokenKind::GE => SyntaxKind::TerminalGE,
485        TokenKind::GT => SyntaxKind::TerminalGT,
486        TokenKind::LE => SyntaxKind::TerminalLE,
487        TokenKind::LT => SyntaxKind::TerminalLT,
488        TokenKind::Not => SyntaxKind::TerminalNot,
489        TokenKind::BitNot => SyntaxKind::TerminalBitNot,
490        TokenKind::Plus => SyntaxKind::TerminalPlus,
491        TokenKind::PlusEq => SyntaxKind::TerminalPlusEq,
492        TokenKind::Minus => SyntaxKind::TerminalMinus,
493        TokenKind::MinusEq => SyntaxKind::TerminalMinusEq,
494        TokenKind::Mul => SyntaxKind::TerminalMul,
495        TokenKind::MulEq => SyntaxKind::TerminalMulEq,
496        TokenKind::Div => SyntaxKind::TerminalDiv,
497        TokenKind::DivEq => SyntaxKind::TerminalDivEq,
498        TokenKind::Mod => SyntaxKind::TerminalMod,
499        TokenKind::ModEq => SyntaxKind::TerminalModEq,
500        TokenKind::Colon => SyntaxKind::TerminalColon,
501        TokenKind::ColonColon => SyntaxKind::TerminalColonColon,
502        TokenKind::Comma => SyntaxKind::TerminalComma,
503        TokenKind::Dollar => SyntaxKind::TerminalDollar,
504        TokenKind::Dot => SyntaxKind::TerminalDot,
505        TokenKind::DotDot => SyntaxKind::TerminalDotDot,
506        TokenKind::DotDotEq => SyntaxKind::TerminalDotDotEq,
507        TokenKind::Eq => SyntaxKind::TerminalEq,
508        TokenKind::Hash => SyntaxKind::TerminalHash,
509        TokenKind::Semicolon => SyntaxKind::TerminalSemicolon,
510        TokenKind::QuestionMark => SyntaxKind::TerminalQuestionMark,
511        TokenKind::Underscore => SyntaxKind::TerminalUnderscore,
512        TokenKind::LBrace => SyntaxKind::TerminalLBrace,
513        TokenKind::RBrace => SyntaxKind::TerminalRBrace,
514        TokenKind::LBrack => SyntaxKind::TerminalLBrack,
515        TokenKind::RBrack => SyntaxKind::TerminalRBrack,
516        TokenKind::LParen => SyntaxKind::TerminalLParen,
517        TokenKind::RParen => SyntaxKind::TerminalRParen,
518        TokenKind::Ref => SyntaxKind::TerminalRef,
519        TokenKind::Mut => SyntaxKind::TerminalMut,
520        TokenKind::Arrow => SyntaxKind::TerminalArrow,
521        TokenKind::MatchArrow => SyntaxKind::TerminalMatchArrow,
522        TokenKind::BadCharacters => SyntaxKind::TerminalBadCharacters,
523        TokenKind::EndOfFile => SyntaxKind::TerminalEndOfFile,
524    }
525}
cairo_lang_parser/lexer.rs

cairo_lang_parser/
lexer.rs
