1#![allow(
17 missing_docs,
18 missing_debug_implementations,
19 missing_copy_implementations,
20 clippy::all,
21 unused_qualifications
22)]
23
24use crate::lexer::token::TokenTy as Token;
25use crate::source_tracking::{SourceRef, fragment::Fragment};
26use crate::terminal_interface::reporting::{Diagnostic, Highlight};
27use std::fmt;
28
29include!(concat!(env!("OUT_DIR"), "/generated.rs"));
30
31#[derive(Debug)]
33pub struct ParseContext {
34 source: SourceRef,
36
37 split_count: usize,
39
40 record_literals_allowed: Vec<bool>,
44}
45
46impl ParseContext {
47 fn new(source: SourceRef) -> Self {
49 ParseContext {
50 source,
51 split_count: 0,
52 record_literals_allowed: Vec::new(),
53 }
54 }
55
56 fn record_literals_allowed(&self) -> bool {
58 self.record_literals_allowed.last().copied().unwrap_or(true)
59 }
60}
61
62fn describe_token(token: Token, text: &str) -> String {
64 match token {
65 Token::EOF | Token::EOFExpr | Token::EOFTy => "end of input".to_owned(),
66 Token::Identifier => format!("identifier `{text}`"),
67 Token::IntegerLiteral => format!("integer literal `{text}`"),
68 Token::FloatLiteral => format!("float literal `{text}`"),
69 Token::StringLiteral | Token::FormatStringLiteral => "string literal".to_owned(),
70 Token::CharLiteral => format!("character literal {text}"),
71 _ if text.starts_with(|c: char| c.is_ascii_alphabetic()) => format!("keyword `{text}`"),
72 _ => format!("`{text}`"),
73 }
74}
75
76const EXPECTED_GROUPS: &[(&str, &[&str])] = &[
80 (
81 "a statement",
82 &[
83 "'let'",
84 "'var'",
85 "'return'",
86 "'break'",
87 "'continue'",
88 "'@'",
89 "'!'",
90 "<character literal>",
91 "<float literal>",
92 "<format string literal>",
93 "<identifier>",
94 "<integer literal>",
95 "'false'",
96 "'for'",
97 "'if'",
98 "'loop'",
99 "'true'",
100 "'while'",
101 "'['",
102 "'{'",
103 "'('",
104 "'-'",
105 "'*'",
106 "<string literal>",
107 "'~'",
108 ],
109 ),
110 (
111 "an expression",
112 &[
113 "'@'",
114 "'!'",
115 "<character literal>",
116 "<float literal>",
117 "<format string literal>",
118 "<identifier>",
119 "<integer literal>",
120 "'false'",
121 "'for'",
122 "'if'",
123 "'loop'",
124 "'true'",
125 "'while'",
126 "'['",
127 "'{'",
128 "'('",
129 "'-'",
130 "'*'",
131 "<string literal>",
132 "'~'",
133 ],
134 ),
135 (
136 "a type",
137 &[
138 "'@'",
139 "<identifier>",
140 "'['",
141 "'func'",
142 "'bool'",
143 "'char'",
144 "'u8'",
145 "'i8'",
146 "'u16'",
147 "'i16'",
148 "'u32'",
149 "'i32'",
150 "'u64'",
151 "'i64'",
152 "'f32'",
153 "'f64'",
154 ],
155 ),
156 (
157 "an item",
158 &[
159 "'const'", "'enum'", "'func'", "'impl'", "'mod'", "'naked'", "'pub'", "'pure'",
160 "'record'", "'type'", "'union'", "'unsafe'", "'use'",
161 ],
162 ),
163 (
164 "an operator",
165 &[
166 "'*'", "'/'", "'%'", "'+'", "'-'", "'<<'", "'>>'", "'&'", "'^'", "'|'", "'=='", "'!='",
167 "'<'", "'<='", "'>'", "'>='", "'&&'", "'||'", "'..'", "'..='", "'as'",
168 ],
169 ),
170 (
171 "an assignment",
172 &[
173 "'='", "'+='", "'-='", "'*='", "'/='", "'%='", "'^='", "'&='", "'|='", "'<<='", "'>>='",
174 ],
175 ),
176];
177
178fn describe_expected(message: &str) -> String {
182 let list = message.strip_prefix("invalid syntax, ").unwrap_or(message);
183 let list = list
184 .strip_prefix("expected one of: ")
185 .or_else(|| list.strip_prefix("expected: "))
186 .unwrap_or(list);
187
188 let all_items: Vec<&str> = list.split(", ").collect();
189 let mut items: Vec<&str> = all_items.clone();
190 let mut descriptions: Vec<String> = Vec::new();
191
192 for (description, group) in EXPECTED_GROUPS {
196 if group.iter().all(|item| all_items.contains(item))
197 && group.iter().any(|item| items.contains(item))
198 {
199 items.retain(|item| !group.contains(item));
200 descriptions.push((*description).to_owned());
201 }
202 }
203
204 descriptions.extend(items.into_iter().map(|item| {
205 match item {
206 "<end of file>" => "end of input".to_owned(),
207 quoted if quoted.len() > 2 && quoted.starts_with('\'') && quoted.ends_with('\'') => {
209 format!("`{}`", "ed[1..quoted.len() - 1])
210 }
211 class => class
213 .trim_start_matches('<')
214 .trim_end_matches('>')
215 .to_owned(),
216 }
217 }));
218
219 match descriptions.as_slice() {
220 [] => "something else".to_owned(),
221 [one] => one.clone(),
222 [first, second] => format!("{first} or {second}"),
223 [init @ .., last] => format!("{}, or {last}", init.join(", ")),
224 }
225}
226
227impl<'a> Parser<'a> {
228 fn split_leading_gt(&mut self) {
231 let rest = match self.current {
232 Token::GtGt => Token::Gt,
233 Token::GtEq => Token::Eq,
234 Token::GtGtEq => Token::GtEq,
235 _ => return,
236 };
237
238 let span = self.cst.data.spans[self.pos].clone();
239 let split = span.start + 1;
240
241 self.tokens[self.pos] = Token::Gt;
242 self.tokens.insert(self.pos + 1, rest);
243 self.cst.data.spans[self.pos] = span.start..split;
244 self.cst.data.spans.insert(self.pos + 1, split..span.end);
245 self.current = Token::Gt;
246 self.context.split_count += 1;
247 }
248
249 fn finish_entry(&mut self, diags: &mut Vec<Diagnostic>) {
255 if self.context.split_count == 0 {
256 return;
257 }
258
259 if self.pos < self.tokens.len() {
260 self.close_error_node(diags);
261 self.error(diags, err![self, "invalid syntax, expected: <end of file>"]);
262 let error_tree = self.open(diags);
263
264 while self.pos < self.tokens.len() {
265 let token = self.tokens[self.pos];
266 self.cst.data.advance(token, Self::is_skipped(token));
267 self.pos += 1;
268 }
269
270 self.cst.data.close(error_tree, Rule::Error);
271 }
272
273 self.pos -= self.context.split_count;
274 }
275
276 fn next_closes_generics(&self) -> bool {
278 matches!(self.peek(1), Token::Gt | Token::GtGt | Token::GtEq | Token::GtGtEq)
279 }
280
281 fn push_record_literals_allowed(&mut self, allowed: bool) {
282 self.context.record_literals_allowed.push(allowed);
283 }
284
285 fn pop_record_literals_allowed(&mut self) {
286 self.context.record_literals_allowed.pop();
287 }
288}
289
290impl<'a> ParserCallbacks<'a> for Parser<'a> {
291 type Diagnostic = Diagnostic;
292 type Context = ParseContext;
293
294 fn create_tokens(
295 context: &mut Self::Context,
296 _source: &'a str,
297 diags: &mut Vec<Self::Diagnostic>,
298 ) -> (Vec<Token>, Vec<Span>) {
299 super::lexer::tokenize(&context.source, diags)
300 }
301
302 fn create_diagnostic(&self, span: Span, message: String) -> Self::Diagnostic {
303 let fragment = Fragment {
304 source: self.context.source.clone(),
305 range: span.clone(),
306 };
307
308 let expected = describe_expected(&message);
309 let found = describe_token(self.current, &self.cst.source[span]);
310
311 Diagnostic::error()
312 .with_message(format!("syntax error: expected {expected}, found {found}"))
313 .with_highlights([Highlight::primary(fragment, format!("unexpected {found}"))])
314 }
315
316 fn predicate_param_list_1(&self) -> bool {
317 self.peek(1) != Token::RightParen
318 }
319
320 fn predicate_record_body_1(&self) -> bool {
321 self.peek(1) != Token::RightCurly
322 }
323
324 fn predicate_enum_body_1(&self) -> bool {
325 self.peek(1) != Token::RightCurly
326 }
327
328 fn predicate_generic_params_1(&self) -> bool {
329 !self.next_closes_generics()
330 }
331
332 fn predicate_named_ty_1(&self) -> bool {
333 true
334 }
335
336 fn predicate_generic_args_1(&self) -> bool {
337 !self.next_closes_generics()
338 }
339
340 fn predicate_func_ty_1(&self) -> bool {
341 self.peek(1) != Token::RightParen
342 }
343
344 fn predicate_path_expr_1(&self) -> bool {
345 self.context.record_literals_allowed()
346 }
347
348 fn predicate_record_lit_fields_1(&self) -> bool {
349 self.peek(1) != Token::RightCurly
350 }
351
352 fn predicate_arg_list_1(&self) -> bool {
353 self.peek(1) != Token::RightParen
354 }
355
356 fn predicate_array_expr_1(&self) -> bool {
357 self.peek(1) != Token::RightBracket
358 }
359
360 fn action_generic_close_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
361 self.split_leading_gt();
362 }
363
364 fn action_block_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
367 self.push_record_literals_allowed(true);
368 }
369
370 fn action_block_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
371 self.pop_record_literals_allowed();
372 }
373
374 fn action_record_lit_fields_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
375 self.push_record_literals_allowed(true);
376 }
377
378 fn action_record_lit_fields_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
379 self.pop_record_literals_allowed();
380 }
381
382 fn action_arg_list_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
383 self.push_record_literals_allowed(true);
384 }
385
386 fn action_arg_list_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
387 self.pop_record_literals_allowed();
388 }
389
390 fn action_index_inner_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
391 self.push_record_literals_allowed(true);
392 }
393
394 fn action_index_inner_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
395 self.pop_record_literals_allowed();
396 }
397
398 fn action_paren_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
399 self.push_record_literals_allowed(true);
400 }
401
402 fn action_paren_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
403 self.pop_record_literals_allowed();
404 }
405
406 fn action_array_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
407 self.push_record_literals_allowed(true);
408 }
409
410 fn action_array_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
411 self.pop_record_literals_allowed();
412 }
413
414 fn action_if_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
417 self.push_record_literals_allowed(false);
418 }
419
420 fn action_if_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
421 self.pop_record_literals_allowed();
422 }
423
424 fn action_while_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
425 self.push_record_literals_allowed(false);
426 }
427
428 fn action_while_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
429 self.pop_record_literals_allowed();
430 }
431
432 fn action_for_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
433 self.push_record_literals_allowed(false);
434 }
435
436 fn action_for_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
437 self.pop_record_literals_allowed();
438 }
439}
440
441#[derive(Clone, Copy, Debug, PartialEq, Eq)]
443pub(crate) enum EntryPoint {
444 SourceFile,
446 Expr,
448 Ty,
450}
451
452pub(crate) fn parse(
454 source: &SourceRef,
455 entry: EntryPoint,
456 diags: &mut Vec<Diagnostic>,
457) -> SyntaxTree {
458 let text: &str = source.source().as_str();
459 let parser = Parser::new_with_context(text, diags, ParseContext::new(source.clone()));
460
461 let cst: Cst<'_> = match entry {
462 EntryPoint::SourceFile => parser.parse_rule(
463 |p, d| {
464 p.rule_source_file(d);
465 p.finish_entry(d);
466 },
467 diags,
468 Rule::SourceFile,
469 ),
470
471 EntryPoint::Expr => {
474 let mut parser = parser;
475 parser.end_of_input = Token::EOFExpr;
476
477 parser.parse_rule(
478 |p, d| {
479 p.rule_expr(d);
480 p.finish_entry(d);
481 },
482 diags,
483 Rule::Part,
484 )
485 }
486
487 EntryPoint::Ty => {
488 let mut parser = parser;
489 parser.end_of_input = Token::EOFTy;
490
491 parser.parse_rule(
492 |p, d| {
493 p.rule_ty(d);
494 p.finish_entry(d);
495 },
496 diags,
497 Rule::Part,
498 )
499 }
500 };
501
502 SyntaxTree {
503 source: source.clone(),
504 data: cst.into_data(),
505 }
506}
507
508#[derive(Debug)]
514pub struct SyntaxTree {
515 source: SourceRef,
516 data: CstData,
517}
518
519impl SyntaxTree {
520 pub const ROOT: NodeRef = NodeRef::ROOT;
522
523 pub fn source(&self) -> &SourceRef {
525 &self.source
526 }
527
528 pub fn get(&self, node: NodeRef) -> Node {
530 self.data.get(node)
531 }
532
533 pub fn rule(&self, node: NodeRef) -> Option<Rule> {
535 match self.data.get(node) {
536 Node::Rule(rule, _) => Some(rule),
537 Node::Token(..) => None,
538 }
539 }
540
541 pub fn token(&self, node: NodeRef) -> Option<Token> {
543 match self.data.get(node) {
544 Node::Token(token, _) => Some(token),
545 Node::Rule(..) => None,
546 }
547 }
548
549 pub fn children(&self, node: NodeRef) -> CstChildren<'_> {
551 self.data.children(node)
552 }
553
554 pub fn span(&self, node: NodeRef) -> std::ops::Range<usize> {
559 self.data.span(node)
560 }
561
562 pub fn fragment(&self, node: NodeRef) -> Fragment {
564 Fragment {
565 source: self.source.clone(),
566 range: self.span(node),
567 }
568 }
569
570 pub fn text(&self, node: NodeRef) -> &str {
572 &self.source.source().as_str()[self.span(node)]
573 }
574}
575
576impl fmt::Display for SyntaxTree {
577 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
580 let mut stack: Vec<(NodeRef, usize)> = vec![(Self::ROOT, 0)];
582
583 while let Some((node, depth)) = stack.pop() {
584 let indent = " ".repeat(depth);
585 let span = self.span(node);
586
587 match self.get(node) {
588 Node::Rule(rule, _) => {
589 writeln!(f, "{indent}{rule:?} [{span:?}]")?;
590 let children: Vec<NodeRef> = self.children(node).collect();
591 stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
592 }
593
594 Node::Token(token, _) => {
595 writeln!(f, "{indent}{token:?} {:?} [{span:?}]", self.text(node))?;
596 }
597 }
598 }
599
600 Ok(())
601 }
602}
603
604#[cfg(test)]
605mod tests {
606 use super::describe_expected;
607
608 #[test]
609 fn expected_single_token() {
610 assert_eq!(describe_expected("invalid syntax, expected: ';'"), "`;`");
611 assert_eq!(describe_expected("invalid syntax, expected: <identifier>"), "identifier");
612 assert_eq!(describe_expected("invalid syntax, expected: <end of file>"), "end of input");
613 }
614
615 #[test]
616 fn expected_lists() {
617 assert_eq!(describe_expected("invalid syntax, expected one of: ',', '}'"), "`,` or `}`");
618 assert_eq!(
619 describe_expected("invalid syntax, expected one of: ',', '}', <identifier>"),
620 "`,`, `}`, or identifier"
621 );
622 }
623
624 #[test]
625 fn expected_groups_collapse() {
626 let expression_starts = "'@', '!', <character literal>, <float literal>, <format string literal>, \
627 <identifier>, <integer literal>, 'false', 'for', 'if', 'loop', 'true', 'while', '[', '{', '(', '-', '*', \
628 <string literal>, '~'";
629
630 assert_eq!(
631 describe_expected(&format!("invalid syntax, expected one of: {expression_starts}")),
632 "an expression"
633 );
634
635 assert_eq!(
636 describe_expected(&format!(
637 "invalid syntax, expected one of: {expression_starts}, ';'"
638 )),
639 "an expression or `;`"
640 );
641
642 assert_eq!(
644 describe_expected(&format!(
645 "invalid syntax, expected one of: 'let', 'var', 'return', 'break', 'continue', {expression_starts}"
646 )),
647 "a statement"
648 );
649 }
650}