Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/syntax/parser.rs

46.4 KiB, 1 run

created by r1870400018:63570, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// SPDX-License-Identifier: Apache-2.0
2// Portions Copyright (c) The Typst Project Developers, from typst-syntax 0.15.1's `src/parser.rs`; see
3// fe2o3_austenite/licences/typst-LICENSE.txt for the full Apache-2.0 text.
4// Modified for Austenite.
5//! Ported from typst-syntax 0.15.1 (`src/parser.rs`, Apache-2.0, (c) the Typst authors): the same
6//! recursive descent over the three modes, the same newline modes, backtracking memo and depth limit,
7//! so the tree has typst-syntax's kinds, child order and error nodes. The tree is built with detached
8//! spans and numbered once at the end, which keeps every node's span its exact byte range.
9
10use crate::syntax::{
11 FileId,
12 SyntaxKind,
13 SyntaxNode,
14};
15use crate::syntax::ast;
16use crate::syntax::kind::{
17 self,
18 SyntaxSet,
19 syntax_set,
20};
21use crate::syntax::lexer::{
22 self,
23 LexMode,
24 Lexer,
25};
26
27use std::collections::{
28 HashMap,
29 HashSet,
30};
31use std::ops::Range;
32
33const MAX_DEPTH: u32 = 256; // Typst's nesting limit
34
35/// Parses a file in markup mode into a `Markup` root.
36pub fn parse(text: &str, file: FileId) -> SyntaxNode {
37 let mut p = Parser::new(text, LexMode::Markup);
38 markup_exprs(&mut p, true, syntax_set!(End));
39 p.finish_into(SyntaxKind::Markup, file)
40}
41
42/// Parses code, as `eval(mode: "code")` and a `typst eval` probe need, into a `Code` root.
43pub fn parse_code(text: &str, file: FileId) -> SyntaxNode {
44 let mut p = Parser::new(text, LexMode::Code);
45 code_exprs(&mut p, syntax_set!(End));
46 p.finish_into(SyntaxKind::Code, file)
47}
48
49/// Parses maths, as `eval(mode: "math")` needs, into a `Math` root.
50pub fn parse_math(text: &str, file: FileId) -> SyntaxNode {
51 let mut p = Parser::new(text, LexMode::Math);
52 math_exprs(&mut p, syntax_set!(End));
53 p.finish_into(SyntaxKind::Math, file)
54}
55
56// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
57// │ Markup │
58// └───────────────────────────────────────────────────────────────────────────────────────────┘
59
60fn markup(p: &mut Parser, at_start: bool, wrap_trivia: bool, stop: SyntaxSet) {
61 let m = if wrap_trivia { p.before_trivia() } else { p.marker() };
62 markup_exprs(p, at_start, stop);
63 if wrap_trivia {
64 p.flush_trivia();
65 }
66 p.wrap(m, SyntaxKind::Markup);
67}
68
69fn markup_exprs(p: &mut Parser, mut at_start: bool, stop: SyntaxSet) {
70 if !p.check_depth_until(stop) {
71 return;
72 }
73 at_start |= p.had_newline();
74 let mut nesting: usize = 0;
75 // A nested right bracket is text, whatever the stop set says.
76 while !p.at_set(stop) || (nesting > 0 && p.at(SyntaxKind::RightBracket)) {
77 markup_expr(p, at_start, &mut nesting);
78 at_start = p.had_newline();
79 }
80}
81
82fn markup_expr(p: &mut Parser, at_start: bool, nesting: &mut usize) {
83 if !p.enter() {
84 return;
85 }
86 match p.current() {
87 SyntaxKind::LeftBracket => {
88 *nesting += 1;
89 p.convert_and_eat(SyntaxKind::Text);
90 },
91 SyntaxKind::RightBracket if *nesting > 0 => {
92 *nesting -= 1;
93 p.convert_and_eat(SyntaxKind::Text);
94 },
95 SyntaxKind::RightBracket => {
96 p.unexpected();
97 p.hint("try using a backslash escape: \\]");
98 },
99
100 SyntaxKind::Shebang
101 | SyntaxKind::Text
102 | SyntaxKind::Linebreak
103 | SyntaxKind::Escape
104 | SyntaxKind::Shorthand
105 | SyntaxKind::SmartQuote
106 | SyntaxKind::Link
107 | SyntaxKind::Label
108 | SyntaxKind::Raw => p.eat(),
109
110 SyntaxKind::Hash => embedded_code_expr(p),
111 SyntaxKind::Star => strong(p),
112 SyntaxKind::Underscore => emph(p),
113 SyntaxKind::HeadingMarker if at_start => heading(p),
114 SyntaxKind::ListMarker if at_start => list_item(p),
115 SyntaxKind::EnumMarker if at_start => enum_item(p),
116 SyntaxKind::TermMarker if at_start => term_item(p),
117 SyntaxKind::RefMarker => reference(p),
118 SyntaxKind::Dollar => equation(p),
119
120 SyntaxKind::HeadingMarker
121 | SyntaxKind::ListMarker
122 | SyntaxKind::EnumMarker
123 | SyntaxKind::TermMarker
124 | SyntaxKind::Colon => p.convert_and_eat(SyntaxKind::Text),
125
126 _ => p.unexpected(),
127 }
128 p.leave();
129}
130
131fn strong(p: &mut Parser) {
132 delimited_markup(p, SyntaxKind::Star, SyntaxKind::Strong, "no text within stars",
133 "using multiple consecutive stars (e.g. **) has no additional effect");
134}
135
136fn emph(p: &mut Parser) {
137 delimited_markup(p, SyntaxKind::Underscore, SyntaxKind::Emph, "no text within underscores",
138 "using multiple consecutive underscores (e.g. __) has no additional effect");
139}
140
141// `*strong*` and `_emph_`: stop at a paragraph break, warn when empty.
142fn delimited_markup(p: &mut Parser, delim: SyntaxKind, wrapper: SyntaxKind, warning: &str, hint: &str) {
143 p.with_nl_mode(AtNewline::StopParBreak, |p| {
144 let m = p.marker();
145 p.assert(delim);
146 markup(p, false, true, syntax_set!(RightBracket, End).add(delim));
147 let closed = p.expect_closing_delimiter(m, delim);
148 p.wrap(m, wrapper);
149 if closed {
150 if let Some(n) = p.node_mut(m) {
151 if n.len() == 2 {
152 n.warn(warning);
153 n.hint(hint);
154 }
155 }
156 }
157 });
158}
159
160fn heading(p: &mut Parser) {
161 p.with_nl_mode(AtNewline::Stop, |p| {
162 let m = p.marker();
163 p.assert(SyntaxKind::HeadingMarker);
164 markup(p, false, false, syntax_set!(Label, RightBracket, End));
165 p.wrap(m, SyntaxKind::Heading);
166 });
167}
168
169fn list_item(p: &mut Parser) {
170 let col = p.current_column();
171 p.with_nl_mode(AtNewline::RequireColumn(col), |p| {
172 let m = p.marker();
173 p.assert(SyntaxKind::ListMarker);
174 markup(p, true, false, syntax_set!(RightBracket, End));
175 p.wrap(m, SyntaxKind::ListItem);
176 });
177}
178
179fn enum_item(p: &mut Parser) {
180 let col = p.current_column();
181 p.with_nl_mode(AtNewline::RequireColumn(col), |p| {
182 let m = p.marker();
183 p.assert(SyntaxKind::EnumMarker);
184 markup(p, true, false, syntax_set!(RightBracket, End));
185 p.wrap(m, SyntaxKind::EnumItem);
186 });
187}
188
189fn term_item(p: &mut Parser) {
190 let col = p.current_column();
191 p.with_nl_mode(AtNewline::RequireColumn(col), |p| {
192 let m = p.marker();
193 p.with_nl_mode(AtNewline::Stop, |p| {
194 p.assert(SyntaxKind::TermMarker);
195 markup(p, false, false, syntax_set!(Colon, RightBracket, End));
196 });
197 p.expect(SyntaxKind::Colon);
198 markup(p, true, false, syntax_set!(RightBracket, End));
199 p.wrap(m, SyntaxKind::TermItem);
200 });
201}
202
203fn reference(p: &mut Parser) {
204 let m = p.marker();
205 p.assert(SyntaxKind::RefMarker);
206 if p.directly_at(SyntaxKind::LeftBracket) {
207 content_block(p);
208 }
209 p.wrap(m, SyntaxKind::Ref);
210}
211
212fn equation(p: &mut Parser) {
213 let m = p.marker();
214 p.enter_modes(LexMode::Math, AtNewline::Continue, |p| {
215 p.assert(SyntaxKind::Dollar);
216 math(p, syntax_set!(Dollar, End));
217 p.expect_closing_delimiter(m, SyntaxKind::Dollar);
218 });
219 p.wrap(m, SyntaxKind::Equation);
220}
221
222// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
223// │ Maths │
224// └───────────────────────────────────────────────────────────────────────────────────────────┘
225
226fn math(p: &mut Parser, stop: SyntaxSet) {
227 let m = p.marker();
228 math_exprs(p, stop);
229 p.wrap(m, SyntaxKind::Math);
230}
231
232// Returns the number of expressions parsed, errors included.
233fn math_exprs(p: &mut Parser, stop: SyntaxSet) -> usize {
234 if !p.check_depth_until(stop) {
235 return 1;
236 }
237 let mut count = 0;
238 while !p.at_set(stop) {
239 if p.at_set(kind::MATH_EXPR) {
240 math_expr(p);
241 } else {
242 p.unexpected();
243 }
244 count += 1;
245 }
246 count
247}
248
249fn math_expr(p: &mut Parser) {
250 math_expr_prec(p, 0, syntax_set!());
251}
252
253const MATH_FUNC_PREC: u8 = 2;
254const MATH_ROOT_PREC: u8 = 2;
255
256fn math_expr_prec(p: &mut Parser, min_prec: u8, stop: SyntaxSet) {
257 if !p.enter() {
258 return;
259 }
260 math_expr_prec_inner(p, min_prec, stop);
261 p.leave();
262}
263
264fn math_expr_prec_inner(p: &mut Parser, min_prec: u8, stop: SyntaxSet) {
265 let m = p.marker();
266 let mut continuable = false;
267 match p.current() {
268 SyntaxKind::Hash => embedded_code_expr(p),
269
270 // The lexer builds whole `MathFieldAccess` chains.
271 SyntaxKind::MathIdent | SyntaxKind::MathFieldAccess => {
272 continuable = true;
273 p.eat();
274 if MATH_FUNC_PREC >= min_prec && p.directly_at(SyntaxKind::LeftParen) {
275 math_args(p);
276 p.wrap(m, SyntaxKind::MathCall);
277 continuable = false;
278 }
279 },
280
281 SyntaxKind::LeftBrace | SyntaxKind::LeftParen => math_delimited(p),
282 SyntaxKind::RightBrace if p.current_text() == "|]" =>
283 p.convert_and_eat(SyntaxKind::MathShorthand),
284 SyntaxKind::Dot
285 | SyntaxKind::Bang
286 | SyntaxKind::Comma
287 | SyntaxKind::Semicolon
288 | SyntaxKind::RightBrace
289 | SyntaxKind::RightParen => p.convert_and_eat(SyntaxKind::MathText),
290
291 SyntaxKind::MathText => {
292 continuable = is_math_alphabetic(p.current_text());
293 p.eat();
294 },
295
296 SyntaxKind::Linebreak
297 | SyntaxKind::MathAlignPoint
298 | SyntaxKind::MathShorthand => p.eat(),
299
300 SyntaxKind::MathPrimes | SyntaxKind::Escape | SyntaxKind::Str => {
301 continuable = true;
302 p.eat();
303 },
304
305 SyntaxKind::Root => {
306 p.eat();
307 let m2 = p.marker();
308 math_expr_prec(p, MATH_ROOT_PREC, syntax_set!());
309 math_unparen(p, m2);
310 p.wrap(m, SyntaxKind::MathRoot);
311 },
312
313 _ => p.expected("expression"),
314 }
315
316 // An implicit call: a continuable atom directly followed by delimiters groups with them, so `a(b)/c`
317 // is `(a(b))/c`.
318 if continuable
319 && MATH_FUNC_PREC >= min_prec
320 && !p.had_trivia()
321 && p.at_set(syntax_set!(LeftBrace, LeftParen))
322 {
323 math_delimited(p);
324 p.wrap(m, SyntaxKind::Math);
325 }
326
327 // Infix and postfix operators, `MathAttach[ MathText("x"), Hat("^"), MathText("2") ]`.
328 loop {
329 if p.at_set(stop) {
330 break;
331 }
332 let op_kind = p.current();
333 let (wrapper, assoc, prec) = match math_op(op_kind, p.had_trivia()) {
334 Some(op) if op.2 >= min_prec => op,
335 _ => break,
336 };
337
338 // `^` chains with `_` and back; a prime chains with either.
339 let mut chain = if wrapper == SyntaxKind::MathAttach {
340 syntax_set!(Hat, Underscore).remove(op_kind)
341 } else {
342 syntax_set!()
343 };
344
345 if op_kind == SyntaxKind::Bang {
346 p.convert_and_eat(SyntaxKind::MathText);
347 } else {
348 p.eat();
349 }
350
351 // Only the slash strips its left operand's parentheses.
352 if wrapper == SyntaxKind::MathFrac {
353 math_unparen(p, m);
354 }
355
356 if let Some(assoc) = assoc {
357 let prec = match assoc {
358 ast::Assoc::Left => prec + 1,
359 ast::Assoc::Right => prec,
360 };
361 let m_rhs = p.marker();
362 math_expr_prec(p, prec, chain);
363 math_unparen(p, m_rhs);
364 }
365
366 // A prime at the end of a chain does not interrupt it: `a^b'_c^d` is `(a^(b')_c)^d`.
367 if !(op_kind == SyntaxKind::MathPrimes && p.at_set(stop)) {
368 while p.at_set(chain) {
369 chain = chain.remove(p.current());
370 p.eat();
371 let m_rhs = p.marker();
372 math_expr_prec(p, prec, chain);
373 math_unparen(p, m_rhs);
374 }
375 }
376
377 p.wrap(m, wrapper);
378 }
379}
380
381fn math_op(kind: SyntaxKind, had_trivia: bool) -> Option<(SyntaxKind, Option<ast::Assoc>, u8)> {
382 match kind {
383 SyntaxKind::Slash => Some((SyntaxKind::MathFrac, Some(ast::Assoc::Left), 1)),
384 SyntaxKind::Underscore => Some((SyntaxKind::MathAttach, Some(ast::Assoc::Right), 2)),
385 SyntaxKind::Hat => Some((SyntaxKind::MathAttach, Some(ast::Assoc::Right), 2)),
386 SyntaxKind::MathPrimes if !had_trivia => Some((SyntaxKind::MathAttach, None, 2)),
387 SyntaxKind::Bang if !had_trivia => Some((SyntaxKind::Math, None, 3)),
388 _ => None,
389 }
390}
391
392/// Does the text count as alphabetic in maths, grouping with a following parenthesis as an implicit call?
393fn is_math_alphabetic(text: &str) -> bool {
394 let mut chars = text.chars();
395 match (chars.next(), chars.next()) {
396 (Some(c), None) => c.is_alphabetic() || lexer::is_math_alphabetic_class(c),
397 _ => text.chars().all(char::is_alphabetic),
398 }
399}
400
401// Matched delimiters, `[x + y]`. The lexer's brace and paren kinds turn back into text here.
402fn math_delimited(p: &mut Parser) {
403 let m = p.marker();
404 if p.current_text() == "[|" {
405 p.convert_and_eat(SyntaxKind::MathShorthand);
406 } else {
407 p.convert_and_eat(SyntaxKind::MathText);
408 }
409 let m_body = p.marker();
410 math_exprs(p, syntax_set!(Dollar, End, RightBrace, RightParen));
411 if p.at_set(syntax_set!(RightBrace, RightParen)) {
412 p.wrap(m_body, SyntaxKind::Math);
413 if p.current_text() == "|]" {
414 p.convert_and_eat(SyntaxKind::MathShorthand);
415 } else {
416 p.convert_and_eat(SyntaxKind::MathText);
417 }
418 p.wrap(m, SyntaxKind::MathDelimited);
419 } else {
420 // Unclosed: a plain sequence.
421 p.wrap(m, SyntaxKind::Math);
422 }
423}
424
425// Strips one pair of round parentheses from the expression at `m`, by re-kinding them.
426fn math_unparen(p: &mut Parser, m: Marker) {
427 let node = match p.nodes.get_mut(m.0) {
428 Some(n) => n,
429 None => return,
430 };
431 if node.kind() != SyntaxKind::MathDelimited {
432 return;
433 }
434 let parens = {
435 let c = node.children();
436 match (c.first(), c.last()) {
437 (Some(f), Some(l)) => c.len() >= 2 && f.text() == "(" && l.text() == ")",
438 _ => false,
439 }
440 };
441 if parens {
442 let children = node.children_mut();
443 let n = children.len();
444 if let Some(f) = children.first_mut() {
445 f.convert_to_kind(SyntaxKind::LeftParen);
446 }
447 if let Some(l) = children.get_mut(n - 1) {
448 l.convert_to_kind(SyntaxKind::RightParen);
449 }
450 node.convert_to_kind(SyntaxKind::Math);
451 }
452}
453
454// A maths argument list, `(a, b; c, d; size: #50%)`.
455fn math_args(p: &mut Parser) {
456 let m = p.marker();
457 p.assert(SyntaxKind::LeftParen);
458 let mut seen = HashSet::new();
459 while !p.at_set(syntax_set!(End, Dollar, RightParen)) {
460 math_arg(p, &mut seen);
461 match p.current() {
462 SyntaxKind::End | SyntaxKind::Dollar | SyntaxKind::RightParen => (),
463 SyntaxKind::Semicolon | SyntaxKind::Comma => p.eat(),
464 _ => p.expected("comma or semicolon"),
465 }
466 }
467 p.expect_closing_delimiter(m, SyntaxKind::RightParen);
468 p.wrap(m, SyntaxKind::MathArgs);
469}
470
471fn math_arg<'s>(p: &mut Parser<'s>, seen: &mut HashSet<&'s str>) {
472 let m = p.marker();
473 let start = p.current_start();
474 let mut arg_kind = None;
475
476 if let Some(spread) = p.lexer.maybe_math_spread_arg(start) {
477 arg_kind = Some(SyntaxKind::Spread);
478 p.token.node = spread;
479 p.eat();
480 } else if let Some(named) = p.lexer.maybe_math_named_arg(start) {
481 arg_kind = Some(SyntaxKind::Named);
482 p.token.node = named;
483 let text = p.current_text();
484 p.eat();
485 p.convert_and_eat(SyntaxKind::Colon);
486 if !seen.insert(text) {
487 if let Some(n) = p.node_mut(m) {
488 n.convert_to_error(&format!("duplicate argument: {}", text));
489 }
490 }
491 }
492
493 let m_arg = p.marker();
494 let count = math_exprs(p, syntax_set!(End, Dollar, Comma, Semicolon, RightParen));
495 if count == 0 && arg_kind == Some(SyntaxKind::Named) {
496 p.expected("expression");
497 }
498 // One expression stays as it is (`func(#12pt)` keeps a length); none or several become maths.
499 if count != 1 {
500 p.wrap(m_arg, SyntaxKind::Math);
501 }
502 if let Some(k) = arg_kind {
503 p.wrap(m, k);
504 }
505}
506
507// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
508// │ Code │
509// └───────────────────────────────────────────────────────────────────────────────────────────┘
510
511fn code(p: &mut Parser, stop: SyntaxSet) {
512 let m = p.marker();
513 code_exprs(p, stop);
514 p.wrap(m, SyntaxKind::Code);
515}
516
517fn code_exprs(p: &mut Parser, stop: SyntaxSet) {
518 if !p.check_depth_until(stop) {
519 return;
520 }
521 while !p.at_set(stop) {
522 p.with_nl_mode(AtNewline::ContextualContinue, |p| {
523 if !p.at_set(kind::CODE_EXPR) {
524 p.unexpected();
525 return;
526 }
527 code_expr(p);
528 if !p.at_set(stop) && !p.eat_if(SyntaxKind::Semicolon) {
529 p.expected("semicolon or line break");
530 if p.at(SyntaxKind::Label) {
531 p.hint("labels can only be applied in markup mode");
532 p.hint("try wrapping your code in a markup block (`[ ]`)");
533 }
534 }
535 });
536 }
537}
538
539// An atomic code expression after a `#` in markup or maths.
540fn embedded_code_expr(p: &mut Parser) {
541 p.enter_modes(LexMode::Code, AtNewline::Stop, |p| {
542 p.assert(SyntaxKind::Hash);
543 if p.had_trivia() || p.end() {
544 p.expected("expression");
545 return;
546 }
547 let stmt = p.at_set(kind::STMT);
548 code_expr_prec(p, true, 0);
549 // Two-dimensional maths arguments rely on the `directly_at` here.
550 let semi = (stmt || p.directly_at(SyntaxKind::Semicolon)) && p.eat_if(SyntaxKind::Semicolon);
551 if stmt && !semi && !p.end() && !p.at(SyntaxKind::RightBracket) {
552 p.expected("semicolon or line break");
553 }
554 });
555}
556
557fn code_expr(p: &mut Parser) {
558 code_expr_prec(p, false, 0);
559}
560
561fn code_expr_prec(p: &mut Parser, atomic: bool, min_prec: u8) {
562 if !p.enter() {
563 return;
564 }
565 code_expr_prec_inner(p, atomic, min_prec);
566 p.leave();
567}
568
569fn code_expr_prec_inner(p: &mut Parser, atomic: bool, min_prec: u8) {
570 let m = p.marker();
571 if p.at_set(kind::UNARY_OP) {
572 if !atomic {
573 let op = match ast::UnOp::from_kind(p.current()) {
574 Some(op) => op,
575 None => ast::UnOp::Pos,
576 };
577 p.eat();
578 code_expr_prec(p, atomic, op.precedence());
579 p.wrap(m, SyntaxKind::Unary);
580 } else {
581 p.unexpected();
582 p.hint("to use a unary operator here, wrap the entire expression in parentheses");
583 }
584 } else {
585 code_primary(p, atomic);
586 }
587
588 loop {
589 if p.directly_at(SyntaxKind::LeftParen) || p.directly_at(SyntaxKind::LeftBracket) {
590 args(p);
591 p.wrap(m, SyntaxKind::FuncCall);
592 continue;
593 }
594
595 let at_field_or_method = p.directly_at(SyntaxKind::Dot)
596 && p.lexer.clone().next().0 == SyntaxKind::Ident;
597 if atomic && !at_field_or_method {
598 break;
599 }
600
601 if p.eat_if(SyntaxKind::Dot) {
602 p.expect(SyntaxKind::Ident);
603 p.wrap(m, SyntaxKind::FieldAccess);
604 continue;
605 }
606
607 let binop = if p.at_set(kind::BINARY_OP) {
608 ast::BinOp::from_kind(p.current())
609 } else if min_prec <= ast::BinOp::NotIn.precedence() && p.eat_if(SyntaxKind::Not) {
610 if p.at(SyntaxKind::In) {
611 Some(ast::BinOp::NotIn)
612 } else {
613 p.expected("keyword `in`");
614 break;
615 }
616 } else {
617 None
618 };
619
620 if let Some(op) = binop {
621 let mut prec = op.precedence();
622 if prec < min_prec {
623 break;
624 }
625 if op.assoc() == ast::Assoc::Left {
626 prec += 1;
627 }
628 p.eat();
629 code_expr_prec(p, false, prec);
630 p.wrap(m, SyntaxKind::Binary);
631 continue;
632 }
633
634 break;
635 }
636}
637
638// The atoms unary and binary operations, calls and field accesses are built from.
639fn code_primary(p: &mut Parser, atomic: bool) {
640 let m = p.marker();
641 match p.current() {
642 SyntaxKind::Ident => {
643 p.eat();
644 if !atomic && p.at(SyntaxKind::Arrow) {
645 p.wrap(m, SyntaxKind::Params);
646 p.assert(SyntaxKind::Arrow);
647 code_expr(p);
648 p.wrap(m, SyntaxKind::Closure);
649 }
650 },
651 SyntaxKind::Underscore if !atomic => {
652 p.eat();
653 if p.at(SyntaxKind::Arrow) {
654 p.wrap(m, SyntaxKind::Params);
655 p.eat();
656 code_expr(p);
657 p.wrap(m, SyntaxKind::Closure);
658 } else if p.eat_if(SyntaxKind::Eq) {
659 code_expr(p);
660 p.wrap(m, SyntaxKind::DestructAssignment);
661 } else if let Some(n) = p.node_mut(m) {
662 n.expected("expression");
663 }
664 },
665
666 SyntaxKind::LeftBrace => code_block(p),
667 SyntaxKind::LeftBracket => content_block(p),
668 SyntaxKind::LeftParen => expr_with_paren(p, atomic),
669 SyntaxKind::Dollar => equation(p),
670 SyntaxKind::Let => let_binding(p),
671 SyntaxKind::Set => set_rule(p),
672 SyntaxKind::Show => show_rule(p),
673 SyntaxKind::Context => contextual(p, atomic),
674 SyntaxKind::If => conditional(p),
675 SyntaxKind::While => while_loop(p),
676 SyntaxKind::For => for_loop(p),
677 SyntaxKind::Import => module_import(p),
678 SyntaxKind::Include => module_include(p),
679 SyntaxKind::Break => break_stmt(p),
680 SyntaxKind::Continue => continue_stmt(p),
681 SyntaxKind::Return => return_stmt(p),
682
683 SyntaxKind::Raw
684 | SyntaxKind::None
685 | SyntaxKind::Auto
686 | SyntaxKind::Int
687 | SyntaxKind::Float
688 | SyntaxKind::Bool
689 | SyntaxKind::Numeric
690 | SyntaxKind::Str
691 | SyntaxKind::Label => p.eat(),
692
693 // `#12p`, `#]`, `#"abc\"`: consume the bad token.
694 _ if atomic => p.unexpected(),
695
696 _ => p.expected("expression"),
697 }
698}
699
700fn block(p: &mut Parser) {
701 match p.current() {
702 SyntaxKind::LeftBracket => content_block(p),
703 SyntaxKind::LeftBrace => code_block(p),
704 _ => p.expected("block"),
705 }
706}
707
708fn code_block(p: &mut Parser) {
709 let m = p.marker();
710 p.enter_modes(LexMode::Code, AtNewline::Continue, |p| {
711 p.assert(SyntaxKind::LeftBrace);
712 code(p, syntax_set!(RightBrace, RightBracket, RightParen, End));
713 p.expect_closing_delimiter(m, SyntaxKind::RightBrace);
714 });
715 p.wrap(m, SyntaxKind::CodeBlock);
716}
717
718fn content_block(p: &mut Parser) {
719 let m = p.marker();
720 p.enter_modes(LexMode::Markup, AtNewline::Continue, |p| {
721 p.assert(SyntaxKind::LeftBracket);
722 markup(p, true, true, syntax_set!(RightBracket, End));
723 p.expect_closing_delimiter(m, SyntaxKind::RightBracket);
724 });
725 p.wrap(m, SyntaxKind::ContentBlock);
726}
727
728fn let_binding(p: &mut Parser) {
729 let m = p.marker();
730 p.assert(SyntaxKind::Let);
731
732 let m2 = p.marker();
733 let mut closure = false;
734 let mut other = false;
735 if p.eat_if(SyntaxKind::Ident) {
736 if p.directly_at(SyntaxKind::LeftParen) {
737 params(p);
738 closure = true;
739 }
740 } else {
741 pattern(p, false, &mut HashSet::new(), None);
742 other = true;
743 }
744
745 let has_init = if closure || other { p.expect(SyntaxKind::Eq) } else { p.eat_if(SyntaxKind::Eq) };
746 if has_init {
747 code_expr(p);
748 }
749 if closure {
750 p.wrap(m2, SyntaxKind::Closure);
751 }
752 p.wrap(m, SyntaxKind::LetBinding);
753}
754
755fn set_rule(p: &mut Parser) {
756 let m = p.marker();
757 p.assert(SyntaxKind::Set);
758 let m2 = p.marker();
759 p.expect(SyntaxKind::Ident);
760 while p.eat_if(SyntaxKind::Dot) {
761 p.expect(SyntaxKind::Ident);
762 p.wrap(m2, SyntaxKind::FieldAccess);
763 }
764 args(p);
765 if p.eat_if(SyntaxKind::If) {
766 code_expr(p);
767 }
768 p.wrap(m, SyntaxKind::SetRule);
769}
770
771fn show_rule(p: &mut Parser) {
772 let m = p.marker();
773 p.assert(SyntaxKind::Show);
774 let m2 = p.before_trivia();
775 if !p.at(SyntaxKind::Colon) {
776 code_expr(p);
777 }
778 if p.eat_if(SyntaxKind::Colon) {
779 code_expr(p);
780 } else {
781 p.expected_at(m2, "colon");
782 }
783 p.wrap(m, SyntaxKind::ShowRule);
784}
785
786fn contextual(p: &mut Parser, atomic: bool) {
787 let m = p.marker();
788 p.assert(SyntaxKind::Context);
789 code_expr_prec(p, atomic, 0);
790 p.wrap(m, SyntaxKind::Contextual);
791}
792
793fn conditional(p: &mut Parser) {
794 let m = p.marker();
795 p.assert(SyntaxKind::If);
796 code_expr(p);
797 block(p);
798 if p.eat_if(SyntaxKind::Else) {
799 if p.at(SyntaxKind::If) {
800 conditional(p);
801 } else {
802 block(p);
803 }
804 }
805 p.wrap(m, SyntaxKind::Conditional);
806}
807
808fn while_loop(p: &mut Parser) {
809 let m = p.marker();
810 p.assert(SyntaxKind::While);
811 code_expr(p);
812 block(p);
813 p.wrap(m, SyntaxKind::WhileLoop);
814}
815
816fn for_loop(p: &mut Parser) {
817 let m = p.marker();
818 p.assert(SyntaxKind::For);
819 let mut seen = HashSet::new();
820 pattern(p, false, &mut seen, None);
821 if p.at(SyntaxKind::Comma) {
822 let n = p.eat_and_get();
823 n.unexpected();
824 n.hint("destructuring patterns must be wrapped in parentheses");
825 if p.at_set(kind::PATTERN) {
826 pattern(p, false, &mut seen, None);
827 }
828 }
829 p.expect(SyntaxKind::In);
830 code_expr(p);
831 block(p);
832 p.wrap(m, SyntaxKind::ForLoop);
833}
834
835fn module_import(p: &mut Parser) {
836 let m = p.marker();
837 p.assert(SyntaxKind::Import);
838 code_expr(p);
839 // Renames the whole module; with items, both are imported.
840 if p.eat_if(SyntaxKind::As) {
841 p.expect(SyntaxKind::Ident);
842 }
843 if p.eat_if(SyntaxKind::Colon) {
844 if p.at(SyntaxKind::LeftParen) {
845 p.with_nl_mode(AtNewline::Continue, |p| {
846 let m2 = p.marker();
847 p.assert(SyntaxKind::LeftParen);
848 import_items(p);
849 p.expect_closing_delimiter(m2, SyntaxKind::RightParen);
850 });
851 } else if !p.eat_if(SyntaxKind::Star) {
852 import_items(p);
853 }
854 }
855 p.wrap(m, SyntaxKind::ModuleImport);
856}
857
858fn import_items(p: &mut Parser) {
859 let m = p.marker();
860 while !p.current().is_terminator() {
861 let item = p.marker();
862 if !p.eat_if(SyntaxKind::Ident) {
863 p.unexpected();
864 }
865 // A nested path, `a.b.c`.
866 while p.eat_if(SyntaxKind::Dot) {
867 p.expect(SyntaxKind::Ident);
868 }
869 p.wrap(item, SyntaxKind::ImportItemPath);
870 if p.eat_if(SyntaxKind::As) {
871 p.expect(SyntaxKind::Ident);
872 p.wrap(item, SyntaxKind::RenamedImportItem);
873 }
874 if !p.current().is_terminator() {
875 p.expect(SyntaxKind::Comma);
876 }
877 }
878 p.wrap(m, SyntaxKind::ImportItems);
879}
880
881fn module_include(p: &mut Parser) {
882 let m = p.marker();
883 p.assert(SyntaxKind::Include);
884 code_expr(p);
885 p.wrap(m, SyntaxKind::ModuleInclude);
886}
887
888fn break_stmt(p: &mut Parser) {
889 let m = p.marker();
890 p.assert(SyntaxKind::Break);
891 p.wrap(m, SyntaxKind::LoopBreak);
892}
893
894fn continue_stmt(p: &mut Parser) {
895 let m = p.marker();
896 p.assert(SyntaxKind::Continue);
897 p.wrap(m, SyntaxKind::LoopContinue);
898}
899
900fn return_stmt(p: &mut Parser) {
901 let m = p.marker();
902 p.assert(SyntaxKind::Return);
903 if p.at_set(kind::CODE_EXPR) {
904 code_expr(p);
905 }
906 p.wrap(m, SyntaxKind::FuncReturn);
907}
908
909// A `(` may open a group, an array, a dictionary, closure parameters or a destructuring. The first
910// three are tried in one pass; when `=>` or `=` follows, the parser backtracks and reparses, memoising the
911// correct parse so that no parenthesised expression is parsed more than twice (`(x: (x: (x) => y) => y)
912// => y` would otherwise take time exponential in its depth).
913fn expr_with_paren(p: &mut Parser, atomic: bool) {
914 if atomic {
915 parenthesized_or_array_or_dict(p);
916 return;
917 }
918
919 let (key, checkpoint) = match p.restore_memo_or_checkpoint() {
920 Some(kc) => kc,
921 None => return,
922 };
923 let prev_len = checkpoint.node_len;
924
925 let kind = parenthesized_or_array_or_dict(p);
926
927 if p.at(SyntaxKind::Arrow) {
928 p.restore(checkpoint);
929 let m = p.marker();
930 params(p);
931 if !p.expect(SyntaxKind::Arrow) {
932 return;
933 }
934 code_expr(p);
935 p.wrap(m, SyntaxKind::Closure);
936 } else if p.at(SyntaxKind::Eq) && kind != SyntaxKind::Parenthesized {
937 p.restore(checkpoint);
938 let m = p.marker();
939 destructuring_or_parenthesized(p, true, &mut HashSet::new());
940 if !p.expect(SyntaxKind::Eq) {
941 return;
942 }
943 code_expr(p);
944 p.wrap(m, SyntaxKind::DestructAssignment);
945 } else {
946 return;
947 }
948
949 p.memoize_parsed_nodes(key, prev_len);
950}
951
952struct GroupState {
953 count: usize,
954 maybe_just_parens: bool, // `(a)`, until a comma or a pair says otherwise
955 kind: Option<SyntaxKind>, // `Array` or `Dict`, once known
956 seen: HashSet<String>, // keys, for duplicate detection
957}
958
959// `(1 + 2)`, `(1, "hi", 12cm)` or `(thickness: 3pt)`. A leading colon forces a dictionary, so
960// `(: ..a, ..b)` joins two dictionaries where `(..a, ..b)` joins arrays.
961fn parenthesized_or_array_or_dict(p: &mut Parser) -> SyntaxKind {
962 let mut state = GroupState { count: 0, maybe_just_parens: true, kind: None, seen: HashSet::new() };
963 let m = p.marker();
964 p.with_nl_mode(AtNewline::Continue, |p| {
965 p.assert(SyntaxKind::LeftParen);
966 if p.eat_if(SyntaxKind::Colon) {
967 state.kind = Some(SyntaxKind::Dict);
968 }
969 while !p.current().is_terminator() {
970 if !p.at_set(kind::ARRAY_OR_DICT_ITEM) {
971 p.unexpected();
972 continue;
973 }
974 array_or_dict_item(p, &mut state);
975 state.count += 1;
976 if !p.current().is_terminator() && p.expect(SyntaxKind::Comma) {
977 state.maybe_just_parens = false;
978 }
979 }
980 p.expect_closing_delimiter(m, SyntaxKind::RightParen);
981 });
982
983 let kind = if state.maybe_just_parens && state.count == 1 {
984 SyntaxKind::Parenthesized
985 } else {
986 match state.kind {
987 Some(k) => k,
988 None => SyntaxKind::Array,
989 }
990 };
991 p.wrap(m, kind);
992 kind
993}
994
995fn array_or_dict_item(p: &mut Parser, state: &mut GroupState) {
996 let m = p.marker();
997
998 if p.eat_if(SyntaxKind::Dots) {
999 code_expr(p);
1000 p.wrap(m, SyntaxKind::Spread);
1001 state.maybe_just_parens = false;
1002 return;
1003 }
1004
1005 code_expr(p);
1006
1007 if p.eat_if(SyntaxKind::Colon) {
1008 code_expr(p);
1009 if let Some(node) = p.node_mut(m) {
1010 let key = match node.kind() {
1011 SyntaxKind::Ident => Some(node.text().to_string()),
1012 SyntaxKind::Str => Some(ast::unescape_str(node.text())),
1013 _ => None,
1014 };
1015 if let Some(key) = key {
1016 if !state.seen.insert(key.clone()) {
1017 node.convert_to_error(&format!("duplicate key: {}", key));
1018 }
1019 }
1020 }
1021 let pair_kind = match p.node_mut(m) {
1022 Some(n) if n.kind() == SyntaxKind::Ident => SyntaxKind::Named,
1023 _ => SyntaxKind::Keyed,
1024 };
1025 p.wrap(m, pair_kind);
1026 state.maybe_just_parens = false;
1027 if state.kind == Some(SyntaxKind::Array) {
1028 if let Some(n) = p.node_mut(m) {
1029 n.expected("expression");
1030 }
1031 } else {
1032 state.kind = Some(SyntaxKind::Dict);
1033 }
1034 } else if state.kind == Some(SyntaxKind::Dict) {
1035 if let Some(n) = p.node_mut(m) {
1036 n.expected("named or keyed pair");
1037 }
1038 } else {
1039 state.kind = Some(SyntaxKind::Array);
1040 }
1041}
1042
1043// A call's argument list, `(12pt, y)`, with any trailing content blocks.
1044fn args(p: &mut Parser) {
1045 if !p.directly_at(SyntaxKind::LeftParen) && !p.directly_at(SyntaxKind::LeftBracket) {
1046 p.expected("argument list");
1047 if p.at(SyntaxKind::LeftParen) || p.at(SyntaxKind::LeftBracket) {
1048 p.hint("there may not be any spaces before the argument list");
1049 }
1050 }
1051
1052 let m = p.marker();
1053 if p.at(SyntaxKind::LeftParen) {
1054 let m2 = p.marker();
1055 p.with_nl_mode(AtNewline::Continue, |p| {
1056 p.assert(SyntaxKind::LeftParen);
1057 let mut seen = HashSet::new();
1058 while !p.current().is_terminator() {
1059 if !p.at_set(kind::ARG) {
1060 p.unexpected();
1061 continue;
1062 }
1063 arg(p, &mut seen);
1064 if !p.current().is_terminator() {
1065 p.expect(SyntaxKind::Comma);
1066 }
1067 }
1068 p.expect_closing_delimiter(m2, SyntaxKind::RightParen);
1069 });
1070 }
1071 while p.directly_at(SyntaxKind::LeftBracket) {
1072 content_block(p);
1073 }
1074 p.wrap(m, SyntaxKind::Args);
1075}
1076
1077fn arg<'s>(p: &mut Parser<'s>, seen: &mut HashSet<&'s str>) {
1078 let m = p.marker();
1079 if p.eat_if(SyntaxKind::Dots) {
1080 code_expr(p);
1081 p.wrap(m, SyntaxKind::Spread);
1082 return;
1083 }
1084
1085 let was_at_expr = p.at_set(kind::CODE_EXPR);
1086 let text = p.current_text();
1087 code_expr(p);
1088
1089 if p.eat_if(SyntaxKind::Colon) {
1090 if was_at_expr {
1091 if let Some(n) = p.node_mut(m) {
1092 if n.kind() != SyntaxKind::Ident {
1093 n.expected("identifier");
1094 } else if !seen.insert(text) {
1095 n.convert_to_error(&format!("duplicate argument: {}", text));
1096 }
1097 }
1098 }
1099 code_expr(p);
1100 p.wrap(m, SyntaxKind::Named);
1101 }
1102}
1103
1104fn params(p: &mut Parser) {
1105 let m = p.marker();
1106 p.with_nl_mode(AtNewline::Continue, |p| {
1107 p.assert(SyntaxKind::LeftParen);
1108 let mut seen = HashSet::new();
1109 let mut sink = false;
1110 while !p.current().is_terminator() {
1111 if !p.at_set(kind::PARAM) {
1112 p.unexpected();
1113 continue;
1114 }
1115 param(p, &mut seen, &mut sink);
1116 if !p.current().is_terminator() {
1117 p.expect(SyntaxKind::Comma);
1118 }
1119 }
1120 p.expect_closing_delimiter(m, SyntaxKind::RightParen);
1121 });
1122 p.wrap(m, SyntaxKind::Params);
1123}
1124
1125fn param<'s>(p: &mut Parser<'s>, seen: &mut HashSet<&'s str>, sink: &mut bool) {
1126 let m = p.marker();
1127 if p.eat_if(SyntaxKind::Dots) {
1128 if p.at_set(kind::PATTERN_LEAF) {
1129 pattern_leaf(p, false, seen, Some("parameter"));
1130 }
1131 p.wrap(m, SyntaxKind::Spread);
1132 let had = std::mem::replace(sink, true);
1133 if had {
1134 if let Some(n) = p.node_mut(m) {
1135 n.convert_to_error("only one argument sink is allowed");
1136 }
1137 }
1138 return;
1139 }
1140
1141 let was_at_pat = p.at_set(kind::PATTERN);
1142 pattern(p, false, seen, Some("parameter"));
1143
1144 if p.eat_if(SyntaxKind::Colon) {
1145 if was_at_pat {
1146 if let Some(n) = p.node_mut(m) {
1147 if n.kind() != SyntaxKind::Ident {
1148 n.expected("identifier");
1149 }
1150 }
1151 }
1152 code_expr(p);
1153 p.wrap(m, SyntaxKind::Named);
1154 }
1155}
1156
1157fn pattern<'s>(p: &mut Parser<'s>, reassignment: bool, seen: &mut HashSet<&'s str>, dupe: Option<&'s str>) {
1158 if !p.enter() {
1159 return;
1160 }
1161 match p.current() {
1162 SyntaxKind::Underscore => p.eat(),
1163 SyntaxKind::LeftParen => destructuring_or_parenthesized(p, reassignment, seen),
1164 _ => pattern_leaf(p, reassignment, seen, dupe),
1165 }
1166 p.leave();
1167}
1168
1169fn destructuring_or_parenthesized<'s>(p: &mut Parser<'s>, reassignment: bool, seen: &mut HashSet<&'s str>) {
1170 let mut sink = false;
1171 let mut count = 0;
1172 let mut maybe_just_parens = true;
1173
1174 let m = p.marker();
1175 p.with_nl_mode(AtNewline::Continue, |p| {
1176 p.assert(SyntaxKind::LeftParen);
1177 while !p.current().is_terminator() {
1178 if !p.at_set(kind::DESTRUCTURING_ITEM) {
1179 p.unexpected();
1180 continue;
1181 }
1182 destructuring_item(p, reassignment, seen, &mut maybe_just_parens, &mut sink);
1183 count += 1;
1184 if !p.current().is_terminator() && p.expect(SyntaxKind::Comma) {
1185 maybe_just_parens = false;
1186 }
1187 }
1188 p.expect_closing_delimiter(m, SyntaxKind::RightParen);
1189 });
1190
1191 if maybe_just_parens && count == 1 && !sink {
1192 p.wrap(m, SyntaxKind::Parenthesized);
1193 } else {
1194 p.wrap(m, SyntaxKind::Destructuring);
1195 }
1196}
1197
1198fn destructuring_item<'s>(
1199 p: &mut Parser<'s>,
1200 reassignment: bool,
1201 seen: &mut HashSet<&'s str>,
1202 maybe_just_parens: &mut bool,
1203 sink: &mut bool,
1204) {
1205 let m = p.marker();
1206
1207 if p.eat_if(SyntaxKind::Dots) {
1208 if p.at_set(kind::PATTERN_LEAF) {
1209 pattern_leaf(p, reassignment, seen, None);
1210 }
1211 p.wrap(m, SyntaxKind::Spread);
1212 let had = std::mem::replace(sink, true);
1213 if had {
1214 if let Some(n) = p.node_mut(m) {
1215 n.convert_to_error("only one destructuring sink is allowed");
1216 }
1217 }
1218 return;
1219 }
1220
1221 let was_at_pat = p.at_set(kind::PATTERN);
1222
1223 // A full checkpoint, since trivia may sit between the identifier and the colon.
1224 let checkpoint = p.checkpoint();
1225 if !(p.eat_if(SyntaxKind::Ident) && p.at(SyntaxKind::Colon)) {
1226 p.restore(checkpoint);
1227 pattern(p, reassignment, seen, None);
1228 }
1229
1230 if p.eat_if(SyntaxKind::Colon) {
1231 if was_at_pat {
1232 if let Some(n) = p.node_mut(m) {
1233 if n.kind() != SyntaxKind::Ident {
1234 n.expected("identifier");
1235 }
1236 }
1237 }
1238 pattern(p, reassignment, seen, None);
1239 p.wrap(m, SyntaxKind::Named);
1240 *maybe_just_parens = false;
1241 }
1242}
1243
1244// An identifier when binding, any atomic expression when reassigning; the whole expression is parsed
1245// either way so that a bad one is a single error.
1246fn pattern_leaf<'s>(p: &mut Parser<'s>, reassignment: bool, seen: &mut HashSet<&'s str>, dupe: Option<&'s str>) {
1247 if p.current().is_keyword() {
1248 p.eat_and_get().expected("pattern");
1249 return;
1250 } else if !p.at_set(kind::PATTERN_LEAF) {
1251 p.expected("pattern");
1252 return;
1253 }
1254
1255 let m = p.marker();
1256 let text = p.current_text();
1257 code_expr_prec(p, true, 0);
1258
1259 if !reassignment {
1260 if let Some(n) = p.node_mut(m) {
1261 if n.kind() == SyntaxKind::Ident {
1262 if !seen.insert(text) {
1263 let what = match dupe {
1264 Some(d) => d,
1265 None => "binding",
1266 };
1267 n.convert_to_error(&format!("duplicate {}: {}", what, text));
1268 }
1269 } else {
1270 n.expected("pattern");
1271 }
1272 }
1273 }
1274}
1275
1276// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
1277// │ Parser │
1278// └───────────────────────────────────────────────────────────────────────────────────────────┘
1279
1280// The parser holds one token of lookahead. Trivia before it are already in `nodes`; `wrap` leaves them
1281// outside the node it builds. A newline may turn the token into a fake `End` according to the newline
1282// mode, which is how a heading stops at the end of its line and a code expression at a line break.
1283struct Parser<'s> {
1284 text: &'s str,
1285 lexer: Lexer<'s>,
1286 nl_mode: AtNewline,
1287 token: Token,
1288 nodes: Vec<SyntaxNode>,
1289 memo: MemoArena,
1290 depth: u32,
1291}
1292
1293#[derive(Clone, Debug)]
1294struct Token {
1295 kind: SyntaxKind, // possibly a fake `End`
1296 node: SyntaxNode,
1297 n_trivia: usize,
1298 newline: Option<Newline>,
1299 start: usize,
1300 prev_end: usize,
1301}
1302
1303#[derive(Clone, Copy, Debug)]
1304struct Newline {
1305 column: Option<usize>, // in markup only
1306 parbreak: bool,
1307}
1308
1309#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1310enum AtNewline {
1311 Continue,
1312 Stop,
1313 ContextualContinue, // continue only before `else` or `.`
1314 StopParBreak,
1315 RequireColumn(usize), // stop unless the next line is indented past the column
1316}
1317
1318impl AtNewline {
1319 fn stop_at(self, nl: Newline, kind: SyntaxKind) -> bool {
1320 match self {
1321 AtNewline::Continue => false,
1322 AtNewline::Stop => true,
1323 AtNewline::ContextualContinue => !matches!(kind, SyntaxKind::Else | SyntaxKind::Dot),
1324 AtNewline::StopParBreak => nl.parbreak,
1325 AtNewline::RequireColumn(min) => match nl.column {
1326 Some(c) => c <= min,
1327 None => false,
1328 },
1329 }
1330 }
1331}
1332
1333#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1334struct Marker(usize);
1335
1336#[derive(Default)]
1337struct MemoArena {
1338 arena: Vec<SyntaxNode>,
1339 memo_map: HashMap<usize, (Range<usize>, PartialState)>,
1340}
1341
1342struct Checkpoint {
1343 node_len: usize,
1344 state: PartialState,
1345}
1346
1347#[derive(Clone)]
1348struct PartialState {
1349 cursor: usize,
1350 lex_mode: LexMode,
1351 token: Token,
1352}
1353
1354impl<'s> Parser<'s> {
1355 fn new(text: &'s str, mode: LexMode) -> Self {
1356 let mut lexer = Lexer::new(text, mode);
1357 let nl_mode = AtNewline::Continue;
1358 let mut nodes = Vec::new();
1359 let token = Self::lex(&mut nodes, &mut lexer, nl_mode);
1360 Self { text, lexer, nl_mode, token, nodes, memo: MemoArena::default(), depth: 0 }
1361 }
1362
1363 fn finish_into(mut self, kind: SyntaxKind, file: FileId) -> SyntaxNode {
1364 // A top-level parse always runs to the true end; anything left is swallowed as an error.
1365 while !self.lexer_done() {
1366 self.unexpected();
1367 }
1368 let mut root = SyntaxNode::inner(kind, self.nodes);
1369 root.numberise(file, 0);
1370 root
1371 }
1372
1373 fn lexer_done(&self) -> bool {
1374 self.token.node.kind() == SyntaxKind::End && self.token.start >= self.text.len()
1375 }
1376
1377 fn current(&self) -> SyntaxKind { self.token.kind }
1378 fn at(&self, kind: SyntaxKind) -> bool { self.token.kind == kind }
1379 fn at_set(&self, set: SyntaxSet) -> bool { set.contains(self.token.kind) }
1380 fn end(&self) -> bool { self.at(SyntaxKind::End) }
1381 fn directly_at(&self, kind: SyntaxKind) -> bool { self.token.kind == kind && !self.had_trivia() }
1382 fn had_trivia(&self) -> bool { self.token.n_trivia > 0 }
1383 fn had_newline(&self) -> bool { self.token.newline.is_some() }
1384
1385 fn current_column(&self) -> usize {
1386 match self.token.newline.and_then(|nl| nl.column) {
1387 Some(c) => c,
1388 None => self.lexer.column(self.token.start),
1389 }
1390 }
1391
1392 fn current_text(&self) -> &'s str {
1393 match self.text.get(self.token.start..self.current_end()) {
1394 Some(t) => t,
1395 None => "",
1396 }
1397 }
1398
1399 fn current_start(&self) -> usize { self.token.start }
1400 fn current_end(&self) -> usize { self.lexer.cursor() }
1401
1402 fn marker(&self) -> Marker { Marker(self.nodes.len()) }
1403
1404 fn before_trivia(&self) -> Marker { Marker(self.nodes.len() - self.token.n_trivia) }
1405
1406 fn node_mut(&mut self, m: Marker) -> Option<&mut SyntaxNode> { self.nodes.get_mut(m.0) }
1407
1408 fn eat_and_get(&mut self) -> &mut SyntaxNode {
1409 let at = self.nodes.len();
1410 self.eat();
1411 &mut self.nodes[at]
1412 }
1413
1414 fn eat_if(&mut self, kind: SyntaxKind) -> bool {
1415 let at = self.at(kind);
1416 if at {
1417 self.eat();
1418 }
1419 at
1420 }
1421
1422 // The callers guarantee the token; eating whatever is there keeps the parse moving regardless.
1423 fn assert(&mut self, _kind: SyntaxKind) {
1424 self.eat();
1425 }
1426
1427 fn convert_and_eat(&mut self, kind: SyntaxKind) {
1428 self.token.node.convert_to_kind(kind);
1429 self.eat();
1430 }
1431
1432 fn eat(&mut self) {
1433 let node = std::mem::replace(&mut self.token.node, SyntaxNode::placeholder(SyntaxKind::End));
1434 self.nodes.push(node);
1435 self.token = Self::lex(&mut self.nodes, &mut self.lexer, self.nl_mode);
1436 }
1437
1438 // Detaches the trivia before the token so that the next wrap includes them.
1439 fn flush_trivia(&mut self) {
1440 self.token.n_trivia = 0;
1441 self.token.prev_end = self.token.start;
1442 }
1443
1444 fn wrap(&mut self, from: Marker, kind: SyntaxKind) {
1445 let to = self.before_trivia().0;
1446 let from = from.0.min(to);
1447 let children: Vec<SyntaxNode> = self.nodes.drain(from..to).collect();
1448 self.nodes.insert(from, SyntaxNode::inner(kind, children));
1449 }
1450
1451 fn wrap_error(&mut self, from: Marker, message: &str) {
1452 let to = self.before_trivia().0;
1453 let from = from.0.min(to);
1454 let len: usize = self.nodes.drain(from..to).map(|n| n.len()).sum();
1455 let end = self.token.prev_end;
1456 let text = match self.text.get(end.saturating_sub(len)..end) {
1457 Some(t) => t,
1458 None => "",
1459 };
1460 self.nodes.insert(from, SyntaxNode::error(text, message, crate::syntax::Span::detached()));
1461 }
1462
1463 // Parses `f` in another lexical mode; the token after it is re-lexed in the outer mode.
1464 fn enter_modes<F: FnOnce(&mut Parser<'s>)>(&mut self, mode: LexMode, stop: AtNewline, f: F) {
1465 let previous = self.lexer.mode();
1466 self.lexer.set_mode(mode);
1467 self.with_nl_mode(stop, f);
1468 if mode != previous {
1469 self.lexer.set_mode(previous);
1470 self.lexer.jump(self.token.prev_end);
1471 let keep = self.nodes.len() - self.token.n_trivia;
1472 self.nodes.truncate(keep);
1473 self.token = Self::lex(&mut self.nodes, &mut self.lexer, self.nl_mode);
1474 }
1475 }
1476
1477 fn with_nl_mode<F: FnOnce(&mut Parser<'s>)>(&mut self, mode: AtNewline, f: F) {
1478 let previous = self.nl_mode;
1479 self.nl_mode = mode;
1480 f(self);
1481 self.nl_mode = previous;
1482 if let Some(nl) = self.token.newline {
1483 if mode != previous {
1484 // Restore the real kind, or put a fake end back.
1485 let actual = self.token.node.kind();
1486 self.token.kind = if self.nl_mode.stop_at(nl, actual) { SyntaxKind::End } else { actual };
1487 }
1488 }
1489 }
1490
1491 fn lex(nodes: &mut Vec<SyntaxNode>, lexer: &mut Lexer, nl_mode: AtNewline) -> Token {
1492 let prev_end = lexer.cursor();
1493 let mut start = prev_end;
1494 let (mut kind, mut node) = lexer.next();
1495 let mut n_trivia = 0;
1496 let mut had_newline = false;
1497 let mut parbreak = false;
1498
1499 while kind.is_trivia() {
1500 had_newline |= lexer.newline();
1501 parbreak |= kind == SyntaxKind::Parbreak;
1502 n_trivia += 1;
1503 nodes.push(node);
1504 start = lexer.cursor();
1505 let (k, n) = lexer.next();
1506 kind = k;
1507 node = n;
1508 }
1509
1510 let newline = if had_newline {
1511 let column = if lexer.mode() == LexMode::Markup { Some(lexer.column(start)) } else { None };
1512 let nl = Newline { column, parbreak };
1513 if nl_mode.stop_at(nl, kind) {
1514 kind = SyntaxKind::End;
1515 }
1516 Some(nl)
1517 } else {
1518 None
1519 };
1520
1521 Token { kind, node, n_trivia, newline, start, prev_end }
1522 }
1523
1524 // Depth.
1525
1526 fn enter(&mut self) -> bool {
1527 if self.depth < MAX_DEPTH {
1528 self.depth += 1;
1529 true
1530 } else {
1531 self.depth_check_error(None);
1532 false
1533 }
1534 }
1535
1536 fn leave(&mut self) {
1537 self.depth = self.depth.saturating_sub(1);
1538 }
1539
1540 fn check_depth_until(&mut self, stop: SyntaxSet) -> bool {
1541 if self.depth < MAX_DEPTH {
1542 true
1543 } else {
1544 self.depth_check_error(Some(stop));
1545 false
1546 }
1547 }
1548
1549 // Eats at least one token, balancing brackets, and wraps what it ate as one error.
1550 fn depth_check_error(&mut self, stop: Option<SyntaxSet>) {
1551 let m = self.marker();
1552 let mut balance: usize = 0;
1553 self.with_nl_mode(AtNewline::Continue, |p| {
1554 loop {
1555 if p.at_set(syntax_set!(LeftBracket, LeftBrace, LeftParen)) {
1556 balance = balance.saturating_add(1);
1557 } else if p.at_set(syntax_set!(RightBracket, RightBrace, RightParen)) {
1558 balance = balance.saturating_sub(1);
1559 }
1560 p.eat();
1561 let at_stop = match stop {
1562 Some(s) => p.at_set(s),
1563 None => true,
1564 };
1565 if (balance == 0 && at_stop) || p.end() {
1566 break;
1567 }
1568 }
1569 });
1570 self.wrap_error(m, "maximum parsing depth exceeded");
1571 }
1572
1573 // Memo.
1574
1575 fn memoize_parsed_nodes(&mut self, key: usize, prev_len: usize) {
1576 let Checkpoint { state, node_len } = self.checkpoint();
1577 let start = self.memo.arena.len();
1578 if let Some(parsed) = self.nodes.get(prev_len..node_len) {
1579 self.memo.arena.extend_from_slice(parsed);
1580 }
1581 let range = start..self.memo.arena.len();
1582 self.memo.memo_map.insert(key, (range, state));
1583 }
1584
1585 fn restore_memo_or_checkpoint(&mut self) -> Option<(usize, Checkpoint)> {
1586 let key = self.current_start();
1587 match self.memo.memo_map.get(&key).cloned() {
1588 Some((range, state)) => {
1589 if let Some(parsed) = self.memo.arena.get(range) {
1590 self.nodes.extend_from_slice(parsed);
1591 }
1592 self.restore_partial(state);
1593 None
1594 },
1595 None => Some((key, self.checkpoint())),
1596 }
1597 }
1598
1599 fn restore(&mut self, checkpoint: Checkpoint) {
1600 self.nodes.truncate(checkpoint.node_len);
1601 self.restore_partial(checkpoint.state);
1602 }
1603
1604 fn restore_partial(&mut self, state: PartialState) {
1605 self.lexer.jump(state.cursor);
1606 self.lexer.set_mode(state.lex_mode);
1607 self.token = state.token;
1608 }
1609
1610 fn checkpoint(&self) -> Checkpoint {
1611 Checkpoint {
1612 node_len: self.nodes.len(),
1613 state: PartialState {
1614 cursor: self.lexer.cursor(),
1615 lex_mode: self.lexer.mode(),
1616 token: self.token.clone(),
1617 },
1618 }
1619 }
1620
1621 // Errors.
1622
1623 fn expect(&mut self, kind: SyntaxKind) -> bool {
1624 let at = self.at(kind);
1625 if at {
1626 self.eat();
1627 } else if kind == SyntaxKind::Ident && self.token.kind.is_keyword() {
1628 self.trim_errors();
1629 self.eat_and_get().expected(kind.name());
1630 } else {
1631 self.expected(kind.name());
1632 }
1633 at
1634 }
1635
1636 // Turns the opening delimiter at `open` into an error when the closing one is missing.
1637 fn expect_closing_delimiter(&mut self, open: Marker, kind: SyntaxKind) -> bool {
1638 let at = self.eat_if(kind);
1639 if !at {
1640 if let Some(n) = self.nodes.get_mut(open.0) {
1641 n.convert_to_error("unclosed delimiter");
1642 }
1643 }
1644 at
1645 }
1646
1647 fn expected(&mut self, thing: &str) {
1648 if self.token.kind.is_error() {
1649 // Consume an erroneous token so that it keeps the mode it was lexed in.
1650 self.trim_errors();
1651 self.eat();
1652 } else if !self.after_error() {
1653 let m = self.before_trivia();
1654 self.expected_at(m, thing);
1655 }
1656 }
1657
1658 fn after_error(&self) -> bool {
1659 let m = self.before_trivia().0;
1660 match m.checked_sub(1).and_then(|i| self.nodes.get(i)) {
1661 Some(n) => n.kind().is_error(),
1662 None => false,
1663 }
1664 }
1665
1666 fn expected_at(&mut self, m: Marker, thing: &str) {
1667 let error = SyntaxNode::error("", &format!("expected {}", thing), crate::syntax::Span::detached());
1668 let at = m.0.min(self.nodes.len());
1669 self.nodes.insert(at, error);
1670 }
1671
1672 fn hint(&mut self, hint: &str) {
1673 let m = self.before_trivia().0;
1674 if let Some(n) = m.checked_sub(1).and_then(|i| self.nodes.get_mut(i)) {
1675 n.hint(hint);
1676 }
1677 }
1678
1679 fn unexpected(&mut self) {
1680 self.trim_errors();
1681 self.eat_and_get().unexpected();
1682 }
1683
1684 // Drops trailing zero-length errors before the token.
1685 fn trim_errors(&mut self) {
1686 let end = self.before_trivia().0;
1687 let mut start = end;
1688 while start > 0 {
1689 match self.nodes.get(start - 1) {
1690 Some(n) if n.kind().is_error() && n.is_empty() => start -= 1,
1691 _ => break,
1692 }
1693 }
1694 self.nodes.drain(start..end);
1695 }
1696}