Sitelet https://github.com/starkware-libs/cairo/commit/dcae7ca61fe329f676bbe9cf3a8861fdf66c308a
Skip to content

Commit dcae7ca

Browse files
oriziorizi
committed
performance(parser): Stream the lexer with a lookahead window instead of cloning all tokens.
 `Parser::new` called the salsa-cached `tokenize_all` and deep-cloned the whole resulting `Deque<LexerTerminal>` into the parser on every parse (each terminal owns two trivia vectors). That full per-file token buffer is unnecessary: the parse is already memoized by `file_syntax_data`. Have the parser drive the `Lexer` directly, pulling terminals lazily into a small lookahead `VecDeque` (refilled on demand via `ensure_next_k_exists`), rather than consuming a clone of the cached token list. `tokenize_all` is left as-is (now used only by the lexer tests). -7.35% of cairo-to-diagnostics heap allocations on corelib; parser/lexer golden tests and corelib diagnostics unchanged.
1 parent 186de1b commit dcae7ca

3 files changed

Lines changed: 63 additions & 47 deletions

File tree

‎crates/cairo-lang-parser/src/lexer.rs‎

Lines changed: 5 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,14 @@ mod test;
44

55
use std::sync::Arc;
66

7-
use cairo_lang_filesystem::ids::{SmolStrId, Tracked};
7+
use cairo_lang_filesystem::ids::SmolStrId;
88
use cairo_lang_filesystem::span::{TextOffset, TextSpan, TextWidth};
99
use cairo_lang_syntax::node::Token;
1010
use cairo_lang_syntax::node::ast::{
1111
TokenNewline, TokenSingleLineComment, TokenSingleLineDocComment, TokenSingleLineInnerComment,
1212
TokenWhitespace, TriviumGreen,
1313
};
1414
use cairo_lang_syntax::node::kind::SyntaxKind;
15-
use cairo_lang_utils::deque::Deque;
1615
use salsa::Database;
1716

1817
#[derive(Clone, PartialEq, Eq, Hash)]
@@ -23,8 +22,9 @@ pub struct Lexer {
2322
}
2423

2524
impl Lexer {
26-
pub fn position(&self) -> TextOffset {
27-
self.current_position
25+
/// Creates a new lexer with the given text.
26+
pub fn new(text: Arc<str>) -> Self {
27+
Self { text, previous_position: TextOffset::START, current_position: TextOffset::START }
2828
}
2929

3030
// Helpers.
@@ -253,7 +253,7 @@ impl Lexer {
253253
}
254254
}
255255

256-
fn match_terminal<'a>(&mut self, db: &'a dyn Database) -> LexerTerminal<'a> {
256+
pub fn match_terminal<'a>(&mut self, db: &'a dyn Database) -> LexerTerminal<'a> {
257257
let leading_trivia = self.match_trivia(db, true);
258258

259259
let kind = if let Some(current) = self.peek() {
@@ -325,27 +325,6 @@ impl Lexer {
325325
}
326326
}
327327

328-
/// Tokenizes the entire text and returns a deque of terminals.
329-
#[salsa::tracked]
330-
pub fn tokenize_all<'a>(
331-
db: &'a dyn Database,
332-
_tracked: Tracked,
333-
text: Arc<str>,
334-
) -> cairo_lang_utils::deque::Deque<LexerTerminal<'a>> {
335-
let mut lexer =
336-
Lexer { text, previous_position: TextOffset::START, current_position: TextOffset::START };
337-
let mut result: Deque<LexerTerminal<'a>> = Default::default();
338-
loop {
339-
let terminal = lexer.match_terminal(db);
340-
let is_eof = terminal.kind == SyntaxKind::TerminalEndOfFile;
341-
result.push_back(terminal);
342-
if is_eof {
343-
break;
344-
}
345-
}
346-
result
347-
}
348-
349328
/// Output terminal emitted by the lexer.
350329
#[derive(Clone, PartialEq, Eq, Debug, salsa::Update)]
351330
pub struct LexerTerminal<'a> {

‎crates/cairo-lang-parser/src/lexer_test.rs‎

Lines changed: 23 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,9 @@ use cairo_lang_syntax::node::ast::{TokenSingleLineComment, TokenWhitespace};
66
use cairo_lang_syntax::node::kind::SyntaxKind;
77
use cairo_lang_test_utils::test;
88
use itertools::Itertools;
9+
use salsa::Database;
910

10-
use crate::lexer::{LexerTerminal, tokenize_all};
11+
use crate::lexer::{Lexer, LexerTerminal};
1112
use crate::utils::SimpleParserDatabase;
1213

1314
// TODO(spapini): Use snapshot/regression tests.
@@ -267,7 +268,7 @@ fn test_lex_single_token() {
267268
let db_val = SimpleParserDatabase::default();
268269
let db = &db_val;
269270
for (kind, text) in terminal_kind_and_text() {
270-
let terminals = tokenize_all(db, (), Arc::from(text));
271+
let terminals = tokenize_all(db, Arc::from(text));
271272
let terminal = &terminals[0];
272273
// TODO(spapini): Remove calling new_root on non root elements.
273274
assert_eq!(terminal.kind, kind, "Wrong token kind, with text: \"{text}\".");
@@ -294,7 +295,7 @@ fn test_lex_double_token() {
294295
}
295296
for separator in separators {
296297
let text = format!("{text0}{separator}{text1}");
297-
let terminals = tokenize_all(db, (), Arc::from(text.as_str()));
298+
let terminals = tokenize_all(db, Arc::from(text.as_str()));
298299
let terminal = &terminals[0];
299300
let token_text = terminal.text(db);
300301
assert_eq!(
@@ -343,7 +344,7 @@ fn test_lex_token_with_trivia() {
343344
for leading_trivia in trivia_texts() {
344345
for trailing_trivia in trivia_texts() {
345346
let text = format!("{leading_trivia}{expected_token_text} {trailing_trivia}");
346-
let terminals = tokenize_all(db, (), Arc::from(text.as_str()));
347+
let terminals = tokenize_all(db, Arc::from(text.as_str()));
347348
let terminal = &terminals[0];
348349
let token_text = terminal.text(db);
349350
assert_eq!(terminal.kind, kind, "Wrong token kind, with text: \"{text}\".");
@@ -365,7 +366,7 @@ fn test_lex_token_with_trivia() {
365366
fn test_cases() {
366367
let db_val = SimpleParserDatabase::default();
367368
let db = &db_val;
368-
let res = tokenize_all(db, (), Arc::from("let x: &T = ` 6; // 5+ 3;"));
369+
let res = tokenize_all(db, Arc::from("let x: &T = ` 6; // 5+ 3;"));
369370
assert_eq!(
370371
res.into_iter().collect::<Vec<_>>(),
371372
vec![
@@ -453,7 +454,7 @@ fn test_doc_comment_classification() {
453454
let db_val = SimpleParserDatabase::default();
454455
let db = &db_val;
455456
let text = "// regular\n/// doc\n//! inner\n//// regular\n///// regular\n";
456-
let terminal = tokenize_all(db, (), Arc::from(text)).into_iter().exactly_one().unwrap();
457+
let terminal = tokenize_all(db, Arc::from(text)).into_iter().exactly_one().unwrap();
457458
assert_eq!(
458459
terminal.leading_trivia.into_iter().map(|t| t.0.long(db).kind).collect_vec(),
459460
[
@@ -477,7 +478,7 @@ fn test_bad_character() {
477478
let db = &db_val;
478479

479480
let text = "`";
480-
let terminals = tokenize_all(db, (), Arc::from(text));
481+
let terminals = tokenize_all(db, Arc::from(text));
481482
let terminal = &terminals[0];
482483
let token_text = terminal.text(db);
483484
assert_eq!(
@@ -494,3 +495,18 @@ fn test_bad_character() {
494495
);
495496
assert_eq!(terminals.len(), 2, "Expected exactly 2 terminals (bad char + EOF).");
496497
}
498+
499+
/// Tokenizes the entire text and returns a vector of terminals.
500+
pub fn tokenize_all<'db>(db: &'db dyn Database, text: Arc<str>) -> Vec<LexerTerminal<'db>> {
501+
let mut lexer = Lexer::new(text);
502+
let mut result = vec![];
503+
loop {
504+
let terminal = lexer.match_terminal(db);
505+
let is_eof = terminal.kind == SyntaxKind::TerminalEndOfFile;
506+
result.push(terminal);
507+
if is_eof {
508+
break;
509+
}
510+
}
511+
result
512+
}

‎crates/cairo-lang-parser/src/parser.rs‎

Lines changed: 35 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
use std::collections::VecDeque;
12
use std::mem;
23
use std::sync::Arc;
34

@@ -11,15 +12,14 @@ use cairo_lang_syntax::node::ast::*;
1112
use cairo_lang_syntax::node::helpers::GetIdentifier;
1213
use cairo_lang_syntax::node::kind::SyntaxKind;
1314
use cairo_lang_syntax::node::{SyntaxNode, Token, TypedSyntaxNode};
14-
use cairo_lang_utils::deque::Deque;
1515
use cairo_lang_utils::{extract_matches, require};
1616
use salsa::Database;
1717
use syntax::node::green::{GreenNode, GreenNodeDetails};
1818
use syntax::node::ids::GreenId;
1919

2020
use crate::ParserDiagnostic;
2121
use crate::diagnostic::ParserDiagnosticKind;
22-
use crate::lexer::{LexerTerminal, tokenize_all};
22+
use crate::lexer::{Lexer, LexerTerminal};
2323
use crate::operators::{get_post_operator_precedence, get_unary_operator_precedence};
2424
use crate::recovery::is_of_kind;
2525
use crate::utils::primitive_token_stream_content_and_offset;
@@ -47,8 +47,13 @@ enum MacroParsingContext {
4747
pub struct Parser<'a, 'mt> {
4848
db: &'a dyn Database,
4949
file_id: FileId<'a>,
50-
/// A queue of lexed tokens to be parsed.
51-
terminals: Deque<LexerTerminal<'a>>,
50+
/// The lexer producing the tokens, pulled lazily into `current_terminals` as parsing advances.
51+
lexer: Lexer,
52+
/// A small lookahead window of already-lexed, not-yet-consumed terminals, kept filled by
53+
/// `ensure_next_k_exists`. The front is the next terminal to parse.
54+
current_terminals: VecDeque<LexerTerminal<'a>>,
55+
/// Whether the lexer has produced the end-of-file terminal (no more tokens to pull).
56+
eof: bool,
5257
/// A vector of pending trivia to be added as leading trivia to the next valid terminal.
5358
pending_trivia: Vec<TriviumGreen<'a>>,
5459
/// The current offset, excluding the current terminal.
@@ -67,19 +72,32 @@ pub struct Parser<'a, 'mt> {
6772

6873
impl<'a> Parser<'a, '_> {
6974
fn next_terminal(&self) -> &LexerTerminal<'a> {
70-
&self.terminals[0]
75+
&self.current_terminals[0]
7176
}
7277

7378
fn next_next_terminal(&self) -> &LexerTerminal<'a> {
74-
&self.terminals[1]
79+
&self.current_terminals[1]
7580
}
7681

7782
fn advance(&mut self) -> LexerTerminal<'a> {
78-
self.terminals.pop_front().unwrap()
83+
// Keep the two-terminal lookahead (`next_terminal`/`next_next_terminal`) valid after the
84+
// pop by refilling to 3 (the popped terminal plus the two peeked ones) before popping.
85+
self.ensure_next_k_exists(3);
86+
self.current_terminals.pop_front().unwrap()
87+
}
88+
89+
/// Pulls terminals from the lexer until the lookahead window holds at least `k` of them (or the
90+
/// lexer reaches end-of-file).
91+
fn ensure_next_k_exists(&mut self, k: usize) {
92+
while !self.eof && self.current_terminals.len() < k {
93+
let terminal = self.lexer.match_terminal(self.db);
94+
self.eof = terminal.kind == SyntaxKind::TerminalEndOfFile;
95+
self.current_terminals.push_back(terminal);
96+
}
7997
}
8098

8199
fn next_terminal_mut(&mut self) -> &mut LexerTerminal<'a> {
82-
&mut self.terminals[0]
100+
&mut self.current_terminals[0]
83101
}
84102
}
85103

@@ -147,19 +165,22 @@ impl<'a, 'mt> Parser<'a, 'mt> {
147165
text: &'a str,
148166
diagnostics: &'mt mut DiagnosticsBuilder<'a, ParserDiagnostic<'a>>,
149167
) -> Self {
150-
let tokens: Deque<LexerTerminal<'a>> = tokenize_all(db, (), Arc::from(text));
151-
Parser {
168+
let mut parser = Parser {
152169
db,
153170
file_id,
154-
terminals: tokens,
171+
lexer: Lexer::new(Arc::from(text)),
172+
current_terminals: VecDeque::with_capacity(8),
173+
eof: false,
155174
pending_trivia: Vec::new(),
156175
offset: Default::default(),
157176
current_width: Default::default(),
158177
last_trivia_length: Default::default(),
159178
diagnostics,
160179
pending_skipped_token_diagnostics: Vec::new(),
161180
macro_parsing_context: MacroParsingContext::None,
162-
}
181+
};
182+
parser.ensure_next_k_exists(2);
183+
parser
163184
}
164185

165186
/// Adds a diagnostic to the parser diagnostics collection.
@@ -3530,14 +3551,14 @@ impl<'a, 'mt> Parser<'a, 'mt> {
35303551
// Consume the original token and grab its trivia.
35313552
let orig = self.advance();
35323553
// Pushing the second first, with the trailing trivia.
3533-
self.terminals.push_front(LexerTerminal {
3554+
self.current_terminals.push_front(LexerTerminal {
35343555
text: SmolStrId::from(self.db, second),
35353556
kind: Second::KIND,
35363557
leading_trivia: vec![],
35373558
trailing_trivia: orig.trailing_trivia,
35383559
});
35393560
// Pushing the first second, with the leading trivia.
3540-
self.terminals.push_front(LexerTerminal {
3561+
self.current_terminals.push_front(LexerTerminal {
35413562
text: SmolStrId::from(self.db, first),
35423563
kind: First::KIND,
35433564
leading_trivia: orig.leading_trivia,

0 commit comments

Comments
 (0)