1use std::{cell::Cell, fmt, rc::Rc};23use rowan::{GreenNode, TextRange};45use crate::{6 event::Event,7 marker::{CompletedMarker, Marker},8 nodes::{BinaryOperatorKind, Literal, Number, Text, UnaryOperatorKind},9 token_set::SyntaxKindSet,10 AstToken, SyntaxKind,11 SyntaxKind::*,12 SyntaxNode, T, TS,13};1415pub struct Parse {16 pub green_node: GreenNode,17 pub errors: Vec<LocatedSyntaxError>,18}1920pub struct Parser {21 22 kinds: Vec<SyntaxKind>,23 pub offset: usize,24 pub events: Vec<Event>,25 pub entered: u32,26 pub hints: Vec<(u32, TextRange, String)>,27 pub last_error_token: usize,28 expected_syntax_tracking_state: Rc<Cell<ExpectedSyntax>>,29 steps: Cell<u64>,30}3132#[derive(Clone, Debug)]33pub enum SyntaxError {34 Unexpected {35 expected: ExpectedSyntax,36 found: SyntaxKind,37 },38 Missing {39 expected: ExpectedSyntax,40 },41 Custom {42 error: String,43 },44 Hint {45 error: String,46 },47}48impl fmt::Display for SyntaxError {49 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {50 match self {51 SyntaxError::Unexpected { expected, found } => {52 write!(f, "unexpected {found:?}, expecting {expected}")53 }54 SyntaxError::Missing { expected } => write!(f, "missing {expected}"),55 SyntaxError::Custom { error } => write!(f, "{error}"),56 SyntaxError::Hint { error } => write!(f, "{error}"),57 }58 }59}6061#[derive(Debug)]62pub struct LocatedSyntaxError {63 pub error: SyntaxError,64 pub range: TextRange,65}6667impl Parser {68 pub fn new(kinds: Vec<SyntaxKind>) -> Self {69 Self {70 kinds,71 offset: 0,72 events: vec![],73 entered: 0,74 last_error_token: 0,75 hints: vec![],76 expected_syntax_tracking_state: Rc::new(Cell::new(ExpectedSyntax::Unnamed(TS![]))),77 steps: Cell::new(0),78 }79 }80 pub fn clear_outdated_hints(&mut self) {81 let amount = self82 .hints83 .iter()84 .rev()85 .take_while(|h| h.0 > self.entered)86 .count();87 self.hints.truncate(self.hints.len() - amount);88 }89 fn clear_expected_syntaxes(&self) {90 self.expected_syntax_tracking_state91 .set(ExpectedSyntax::Unnamed(TS![]));92 }93 pub fn start(&mut self) -> Marker {94 let start_event_idx = self.events.len();95 self.events.push(Event::Pending);96 self.entered += 1;97 Marker::new(start_event_idx)98 }99 100 101 102 103 pub fn parse(mut self) -> Vec<Event> {104 let m = self.start();105 expr(&mut self);106 if !self.at(EOF) {107 let m = self.start();108 while !self.at(EOF) {109 self.bump();110 }111 m.complete_error(&mut self, "unexpected tokens after end");112 }113 m.complete(&mut self, SOURCE_FILE);114115 self.events116 }117118 pub(crate) fn expect(&mut self, kind: SyntaxKind) {119 self.expect_with_recovery_set(kind, TS![]);120 }121122 pub(crate) fn expect_with_recovery_set(123 &mut self,124 kind: SyntaxKind,125 recovery_set: SyntaxKindSet,126 ) {127 if self.at(kind) {128 if kind != EOF {129 self.bump();130 }131 } else {132 self.error_with_recovery_set(recovery_set);133 }134 }135136 137 138 139 140 141 142 143 pub fn error_with_no_skip(&mut self) -> CompletedMarker {144 self.error_with_recovery_set(SyntaxKindSet::ALL)145 }146147 pub fn error_with_recovery_set(&mut self, recovery_set: SyntaxKindSet) -> CompletedMarker {148 let expected = self.expected_syntax_tracking_state.get();149 self.expected_syntax_tracking_state150 .set(ExpectedSyntax::Unnamed(TS![]));151152 if self.at_end() || self.at_ts(recovery_set) {153 let m = self.start();154 return m.complete_missing(self, expected);155 }156157 let current_token = self.current();158159 self.last_error_token = self.offset;160161 let m = self.start();162 self.bump();163 let m = m.complete_unexpected(self, expected, current_token);164 self.clear_expected_syntaxes();165 m166 }167 fn bump_assert(&mut self, kind: SyntaxKind) {168 assert!(self.at(kind), "expected {kind:?}");169 self.bump_remap(self.current());170 }171 fn bump(&mut self) {172 self.bump_remap(self.current());173 }174 fn bump_remap(&mut self, kind: SyntaxKind) {175 assert_ne!(self.offset, self.kinds.len(), "already at end");176 self.events.push(Event::Token { kind });177 self.offset += 1;178 self.clear_expected_syntaxes();179 }180 fn step(&self) {181 use std::fmt::Write;182 let steps = self.steps.get();183 if steps >= 15_000_000 {184 let mut out = "seems like parsing is stuck".to_owned();185 {186 let last = 20;187 write!(out, "\n\nLast {last} events:").unwrap();188 for (i, event) in self189 .events190 .iter()191 .skip(self.events.len().saturating_sub(last))192 .enumerate()193 {194 write!(out, "\n{i}. {event:?}").unwrap();195 }196 }197 {198 let next = 20;199 write!(out, "\n\nNext {next} tokens:").unwrap();200 for (i, tok) in self.kinds.iter().skip(self.offset).take(next).enumerate() {201 write!(out, "\n{i}. {tok:?}").unwrap();202 }203 }204 panic!("{out}")205 }206 self.steps.set(steps + 1);207 }208 fn nth(&self, i: usize) -> SyntaxKind {209 self.step();210 let mut offset = self.offset;211 for _ in 0..i {212 offset += 1;213 }214 self.kinds.get(offset).copied().unwrap_or(EOF)215 }216 fn current(&self) -> SyntaxKind {217 self.nth(0)218 }219 #[must_use]220 pub(crate) fn expected_syntax_name(&self, name: &'static str) -> ExpectedSyntaxGuard {221 self.expected_syntax_tracking_state222 .set(ExpectedSyntax::Named(name));223224 ExpectedSyntaxGuard::new(Rc::clone(&self.expected_syntax_tracking_state))225 }226 pub fn at(&self, kind: SyntaxKind) -> bool {227 self.nth_at(0, kind)228 }229 pub fn nth_at(&self, n: usize, kind: SyntaxKind) -> bool {230 if n == 0 {231 if let ExpectedSyntax::Unnamed(kinds) = self.expected_syntax_tracking_state.get() {232 let kinds = kinds.with(kind);233 self.expected_syntax_tracking_state234 .set(ExpectedSyntax::Unnamed(kinds));235 }236 }237 self.nth(n) == kind238 }239 pub fn at_ts(&self, set: SyntaxKindSet) -> bool {240 if let ExpectedSyntax::Unnamed(kinds) = self.expected_syntax_tracking_state.get() {241 let kinds = kinds.union(set);242 self.expected_syntax_tracking_state243 .set(ExpectedSyntax::Unnamed(kinds));244 }245 set.contains(self.current())246 }247 pub fn at_end(&self) -> bool {248 self.at(EOF)249 }250}251pub struct ExpectedSyntaxGuard {252 expected_syntax_tracking_state: Rc<Cell<ExpectedSyntax>>,253}254255impl ExpectedSyntaxGuard {256 fn new(expected_syntax_tracking_state: Rc<Cell<ExpectedSyntax>>) -> Self {257 Self {258 expected_syntax_tracking_state,259 }260 }261}262263impl Drop for ExpectedSyntaxGuard {264 fn drop(&mut self) {265 self.expected_syntax_tracking_state266 .set(ExpectedSyntax::Unnamed(TS![]));267 }268}269270#[derive(Clone, Debug, Copy)]271pub enum ExpectedSyntax {272 Named(&'static str),273 Unnamed(SyntaxKindSet),274}275impl fmt::Display for ExpectedSyntax {276 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {277 match self {278 Self::Named(name) => write!(f, "{name}"),279 Self::Unnamed(set) => write!(f, "{set}"),280 }281 }282}283284fn expr(p: &mut Parser) -> CompletedMarker {285 let m = p.start();286 while p.at(T![local]) || p.at(T![assert]) {287 let m = p.start();288289 if p.at(T![local]) {290 p.bump();291 loop {292 if p.at(T![;]) {293 p.bump();294 break;295 }296 bind(p);297298 if p.at(T![,]) {299 p.bump();300 continue;301 }302 p.expect(T![;]);303 break;304 }305 m.complete(p, STMT_LOCAL);306 } else {307 assertion(p);308 p.expect(T![;]);309 m.complete(p, STMT_ASSERT);310 }311 }312 match expr_binding_power(p, 0) {313 Ok(m) | Err(m) => m,314 };315 m.complete(p, EXPR)316}317fn expr_binding_power(318 p: &mut Parser,319 minimum_binding_power: u8,320) -> Result<CompletedMarker, CompletedMarker> {321 let mut lhs = lhs(p)?;322323 while let Some(op) = BinaryOperatorKind::cast(p.current())324 .or_else(|| p.at(T!['{']).then_some(BinaryOperatorKind::MetaObjectApply))325 {326 let (left_binding_power, right_binding_power) = op.binding_power();327 if left_binding_power < minimum_binding_power {328 break;329 }330331 let m = lhs.wrap(p, EXPR, false);332333 334 if op != BinaryOperatorKind::MetaObjectApply {335 p.bump();336 }337338 let m = m.precede(p);339 let parsed_rhs = expr_binding_power(p, right_binding_power)340 .map(|v| v.precede(p).complete(p, EXPR))341 .is_ok();342 lhs = m.complete(343 p,344 if op == BinaryOperatorKind::MetaObjectApply {345 EXPR_OBJ_EXTEND346 } else {347 EXPR_BINARY348 },349 );350351 if !parsed_rhs {352 break;353 }354 }355 Ok(lhs)356}357358const COMPSPEC: SyntaxKindSet = TS![for if];359fn compspec(p: &mut Parser) -> CompletedMarker {360 assert!(p.at_ts(COMPSPEC));361 if p.at(T![for]) {362 let m = p.start();363 p.bump();364 destruct(p);365 p.expect(T![in]);366 expr(p);367 m.complete(p, FOR_SPEC)368 } else if p.at(T![if]) {369 let m = p.start();370 p.bump();371 expr(p);372 m.complete(p, IF_SPEC)373 } else {374 unreachable!()375 }376}377378fn comma(p: &mut Parser) -> bool {379 comma_with_alternatives(p, TS![])380}381fn comma_with_alternatives(p: &mut Parser, set: SyntaxKindSet) -> bool {382 if p.at(T![,]) {383 p.bump();384 true385 } else if p.at_ts(set) {386 let _ex = p.expected_syntax_name("comma");387 p.expect_with_recovery_set(T![,], TS![]);388 true389 } else {390 false391 }392}393394fn field_name(p: &mut Parser) {395 let _e = p.expected_syntax_name("field name");396 let m = p.start();397 if p.at(T!['[']) {398 p.bump();399 expr(p);400 p.expect(T![']']);401 m.complete(p, FIELD_NAME_DYNAMIC);402 } else if p.at(IDENT) {403 name(p);404 m.complete(p, FIELD_NAME_FIXED);405 } else if Text::can_cast(p.current()) {406 text(p);407 m.complete(p, FIELD_NAME_FIXED);408 } else {409 m.forget(p);410 411 p.error_with_recovery_set(TS![; : :: '('].with(T![:::]));412 }413}414fn visibility(p: &mut Parser) {415 416 if p.at_ts(TS![: ::].with(T![:::])) {417 p.bump();418 } else {419 p.error_with_recovery_set(TS![=]);420 }421}422fn assertion(p: &mut Parser) {423 let m = p.start();424 p.bump_assert(T![assert]);425 expr(p);426 if p.at(T![:]) {427 p.bump();428 expr(p);429 }430 m.complete(p, ASSERTION);431}432fn object(p: &mut Parser) -> CompletedMarker {433 let m_t = p.start();434 let m = p.start();435 p.bump_assert(T!['{']);436437 let mut elems = 0;438 let mut compspecs = Vec::new();439 let mut asserts = Vec::new();440 loop {441 if p.at(T!['}']) {442 p.bump();443 break;444 }445 if p.at_ts(TS![for]) {446 if elems == 0 {447 let m = p.start();448 m.complete_missing(p, ExpectedSyntax::Named("field definition"));449 }450 while p.at_ts(COMPSPEC) {451 compspecs.push(compspec(p));452 }453 if comma_with_alternatives(p, TS![;]) {454 continue;455 }456 p.expect(R_BRACE);457 break;458 }459 let m = p.start();460 if p.at(T![local]) {461 obj_local(p);462 m.complete(p, MEMBER_BIND_STMT);463 } else if p.at(T![assert]) {464 assertion(p);465 asserts.push(m.complete(p, MEMBER_ASSERT_STMT));466 } else {467 field_name(p);468 if p.at(T![+]) {469 p.bump();470 }471 let params = if p.at(T!['(']) {472 params_desc(p);473 visibility(p);474 expr(p);475 true476 477 } else if p.at_ts(TS![: ::].with(T![:::])) && p.nth_at(1, T![function]) {478 visibility(p);479 p.bump_assert(T![function]);480 params_desc(p);481 expr(p);482 true483 } else {484 visibility(p);485 expr(p);486 false487 };488 elems += 1;489490 if params {491 m.complete(p, MEMBER_FIELD_METHOD)492 } else {493 m.complete(p, MEMBER_FIELD_NORMAL)494 };495 };496 while p.at_ts(COMPSPEC) {497 compspecs.push(compspec(p));498 }499 if comma_with_alternatives(p, TS![;]) {500 continue;501 }502 p.expect(R_BRACE);503 break;504 }505506 if elems > 1 && !compspecs.is_empty() {507 for errored in compspecs {508 errored.wrap_error(509 p,510 "compspec may only be used if there is only one object element",511 true,512 );513 }514 m.complete(p, OBJ_BODY_MEMBER_LIST);515 } else if !compspecs.is_empty() {516 for errored in asserts {517 errored.wrap_error(p, "asserts can't be used in object comprehensions", true);518 }519 m.complete(p, OBJ_BODY_COMP);520 } else {521 m.complete(p, OBJ_BODY_MEMBER_LIST);522 }523 m_t.complete(p, EXPR_OBJECT)524}525fn param(p: &mut Parser) {526 let m = p.start();527 destruct(p);528 if p.at(T![=]) {529 p.bump();530 expr(p);531 }532 m.complete(p, PARAM);533}534fn params_desc(p: &mut Parser) -> CompletedMarker {535 let m = p.start();536 p.bump_assert(T!['(']);537538 loop {539 if p.at(T![')']) {540 p.bump();541 break;542 }543 param(p);544 if comma(p) {545 continue;546 }547 p.expect(T![')']);548 break;549 }550551 m.complete(p, PARAMS_DESC)552}553fn args_desc(p: &mut Parser) {554 let m = p.start();555 p.bump_assert(T!['(']);556557 let started_named = Cell::new(false);558 let mut unnamed_after_named = Vec::new();559560 loop {561 if p.at(T![')']) {562 break;563 }564565 let m = p.start();566 if p.at(IDENT) && p.nth_at(1, T![=]) {567 name(p);568 p.bump();569 expr(p);570 m.complete(p, ARG);571 started_named.set(true);572 } else {573 expr(p);574 let arg = m.complete(p, ARG);575 if started_named.get() {576 unnamed_after_named.push(arg);577 }578 }579 if comma(p) {580 continue;581 }582 break;583 }584 p.expect(T![')']);585 if p.at(T![tailstrict]) {586 p.bump();587 }588589 for errored in unnamed_after_named {590 errored.wrap_error(p, "can't use positional arguments after named", true);591 }592593 m.complete(p, ARGS_DESC);594}595596fn array(p: &mut Parser) -> CompletedMarker {597 598 let m = p.start();599 p.bump_assert(T!['[']);600601 let mut compspecs = Vec::new();602 let mut elems = 0;603604 loop {605 if p.at(T![']']) {606 p.bump();607 break;608 }609 if elems != 0 && p.at_ts(TS![for]) {610 while p.at_ts(COMPSPEC) {611 compspecs.push(compspec(p));612 }613 if comma(p) {614 continue;615 }616 p.expect(T![']']);617 break;618 }619 expr(p);620 elems += 1;621 while p.at_ts(COMPSPEC) {622 compspecs.push(compspec(p));623 }624 if comma(p) {625 continue;626 }627 p.expect(T![']']);628 break;629 }630631 if elems > 1 && !compspecs.is_empty() {632 for spec in compspecs {633 spec.wrap_error(634 p,635 "compspec may only be used if there is only one array element",636 true,637 );638 }639640 m.complete(p, EXPR_ARRAY)641 } else if !compspecs.is_empty() {642 m.complete(p, EXPR_ARRAY_COMP)643 } else {644 m.complete(p, EXPR_ARRAY)645 }646}647648#[must_use]649fn slice_desc_or_index(p: &mut Parser) -> bool {650 let m = p.start();651 p.bump();652 653 654 if !p.at(T![:]) && !p.at(T![::]) {655 expr(p);656 }657 if p.at(T![:]) {658 p.bump();659 660 if !p.at(T![']']) {661 expr(p).wrap(p, SLICE_DESC_END, true);662 }663 if p.at(T![:]) {664 p.bump();665 666 if !p.at(T![']']) {667 expr(p).wrap(p, SLICE_DESC_STEP, true);668 }669 }670 } else if p.at(T![::]) {671 p.bump();672 673 if !p.at(T![']']) {674 expr(p).wrap(p, SLICE_DESC_END, true);675 }676 } else {677 678 p.expect(T![']']);679 m.forget(p);680 return false;681 }682 p.expect(T![']']);683 m.complete(p, SLICE_DESC);684 true685}686687fn suffix(p: &mut Parser) {688 loop {689 let start = p.start();690 let _marker: CompletedMarker = if p.at(T![?]) {691 p.bump();692 p.expect(T![.]);693 if p.at(IDENT) {694 name(p);695 start.complete(p, SUFFIX_INDEX)696 } else if p.at(T!['[']) {697 p.bump();698 expr(p);699 p.expect(T![']']);700 start.complete(p, SUFFIX_INDEX_EXPR)701 } else {702 start.complete_missing(p, ExpectedSyntax::Named("index"))703 }704 } else if p.at(T![.]) {705 p.bump();706 name(p);707 start.complete(p, SUFFIX_INDEX)708 } else if p.at(T!['[']) {709 if slice_desc_or_index(p) {710 start.complete(p, SUFFIX_SLICE)711 } else {712 start.complete(p, SUFFIX_INDEX_EXPR)713 }714 } else if p.at(T!['(']) {715 args_desc(p);716 start.complete(p, SUFFIX_APPLY)717 } else {718 start.forget(p);719 break;720 };721 }722}723724fn lhs(p: &mut Parser) -> Result<CompletedMarker, CompletedMarker> {725 let lhs = lhs_basic(p)?;726727 suffix(p);728729 Ok(lhs)730}731fn name(p: &mut Parser) {732 let m = p.start();733 p.expect(IDENT);734 m.complete(p, NAME);735}736fn destruct_rest(p: &mut Parser) {737 let m = p.start();738 p.bump_assert(T![...]);739 if p.at(IDENT) {740 p.bump();741 }742 m.complete(p, DESTRUCT_REST);743}744fn destruct_object_field(p: &mut Parser) {745 let m = p.start();746 name(p);747 if p.at(T![:]) {748 p.bump();749 destruct(p);750 };751 if p.at(T![=]) {752 p.bump();753 expr(p);754 }755 m.complete(p, DESTRUCT_OBJECT_FIELD);756}757fn obj_local(p: &mut Parser) {758 let m = p.start();759 p.bump_assert(T![local]);760 bind(p);761 m.complete(p, OBJ_LOCAL);762}763fn destruct(p: &mut Parser) -> CompletedMarker {764 let m = p.start();765 let _ex = p.expected_syntax_name("destruction specifier");766 if p.at(T![?]) {767 p.bump();768 m.complete(p, DESTRUCT_SKIP)769 } else if p.at(T!['[']) {770 p.bump();771 772 loop {773 if p.at(T![']']) {774 p.bump();775 break;776 } else if p.at(T![...]) {777 778 destruct_rest(p);779 780 781 782 783 } else {784 destruct(p);785 }786 if p.at(T![,]) {787 p.bump();788 continue;789 }790 p.expect(T![']']);791 break;792 }793 m.complete(p, DESTRUCT_ARRAY)794 } else if p.at(T!['{']) {795 p.bump();796 let mut had_rest = false;797 loop {798 if p.at(T!['}']) {799 p.bump();800 break;801 } else if p.at(T![...]) {802 803 destruct_rest(p);804 805 806 807 had_rest = true;808 } else {809 if had_rest {810 p.error_with_recovery_set(TS![]);811 }812 destruct_object_field(p);813 }814 if p.at(T![,]) {815 p.bump();816 continue;817 }818 p.expect(T!['}']);819 break;820 }821 m.complete(p, DESTRUCT_OBJECT)822 } else if p.at(IDENT) {823 name(p);824 m.complete(p, DESTRUCT_FULL)825 } else {826 m.forget(p);827 p.error_with_recovery_set(TS![; , '}', '(', :])828 }829}830fn bind(p: &mut Parser) {831 let m = p.start();832 if p.at(IDENT) && p.nth_at(1, T!['(']) {833 name(p);834 params_desc(p);835 p.expect(T![=]);836 expr(p);837 m.complete(p, BIND_FUNCTION)838 } else if p.at(IDENT) && p.nth_at(1, T![=]) && p.nth_at(2, T![function]) {839 name(p);840 p.expect(T![=]);841 p.expect(T![function]);842 params_desc(p);843 expr(p);844 m.complete(p, BIND_FUNCTION)845 } else {846 destruct(p);847 p.expect(T![=]);848 expr(p);849 m.complete(p, BIND_DESTRUCT)850 };851}852fn text(p: &mut Parser) {853 assert!(Text::can_cast(p.current()));854 p.bump();855}856fn number(p: &mut Parser) {857 assert!(Number::can_cast(p.current()));858 p.bump();859}860fn literal(p: &mut Parser) {861 assert!(Literal::can_cast(p.current()));862 p.bump();863}864fn lhs_basic(p: &mut Parser) -> Result<CompletedMarker, CompletedMarker> {865 let _e = p.expected_syntax_name("expression");866 Ok(if Literal::can_cast(p.current()) {867 let m = p.start();868 literal(p);869 m.complete(p, EXPR_LITERAL)870 } else if Text::can_cast(p.current()) {871 let m = p.start();872 text(p);873 m.complete(p, EXPR_STRING)874 } else if Number::can_cast(p.current()) {875 let m = p.start();876 number(p);877 m.complete(p, EXPR_NUMBER)878 } else if p.at(IDENT) {879 let m = p.start();880 name(p);881 m.complete(p, EXPR_VAR)882 } else if p.at(T![if]) {883 let m = p.start();884 p.bump();885 expr(p);886 p.expect(T![then]);887 expr(p).wrap(p, TRUE_EXPR, true);888 if p.at(T![else]) {889 p.bump();890 expr(p).wrap(p, FALSE_EXPR, true);891 }892 m.complete(p, EXPR_IF_THEN_ELSE)893 } else if p.at(T!['[']) {894 array(p)895 } else if p.at(T!['{']) {896 object(p)897 } else if p.at(T![function]) {898 let m = p.start();899 p.bump();900 params_desc(p);901 expr(p);902 m.complete(p, EXPR_FUNCTION)903 } else if p.at(T![error]) {904 let m = p.start();905 p.bump();906 expr(p);907 m.complete(p, EXPR_ERROR)908 } else if p.at(T![import]) || p.at(T![importstr]) || p.at(T![importbin]) {909 let m = p.start();910 p.bump();911 text(p);912 m.complete(p, EXPR_IMPORT)913 } else if let Some(op) = UnaryOperatorKind::cast(p.current()) {914 let ((), right_binding_power) = op.binding_power();915916 let m = p.start();917 p.bump();918 let _ = expr_binding_power(p, right_binding_power);919 m.complete(p, EXPR_UNARY)920 } else if p.at(T!['(']) {921 let m = p.start();922 p.bump();923 expr(p);924 p.expect(T![')']);925 m.complete(p, EXPR_PARENED)926 } else {927 return Err(p.error_with_no_skip());928 })929}930931impl Parse {932 pub fn syntax(&self) -> SyntaxNode {933 SyntaxNode::new_root(self.green_node.clone())934 }935}