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}4849#[derive(Debug)]50pub struct LocatedSyntaxError {51 pub error: SyntaxError,52 pub range: TextRange,53}5455impl Parser {56 pub fn new(kinds: Vec<SyntaxKind>) -> Self {57 Self {58 kinds,59 offset: 0,60 events: vec![],61 entered: 0,62 last_error_token: 0,63 hints: vec![],64 expected_syntax_tracking_state: Rc::new(Cell::new(ExpectedSyntax::Unnamed(TS![]))),65 steps: Cell::new(0),66 }67 }68 pub fn clear_outdated_hints(&mut self) {69 let amount = self70 .hints71 .iter()72 .rev()73 .take_while(|h| h.0 > self.entered)74 .count();75 self.hints.truncate(self.hints.len() - amount)76 }77 fn clear_expected_syntaxes(&mut self) {78 self.expected_syntax_tracking_state79 .set(ExpectedSyntax::Unnamed(TS![]));80 }81 pub fn start(&mut self) -> Marker {82 let start_event_idx = self.events.len();83 self.events.push(Event::Pending);84 self.entered += 1;85 Marker::new(start_event_idx)86 }87 88 89 90 91 pub fn parse(mut self) -> Vec<Event> {92 let m = self.start();93 expr(&mut self);94 if !self.at(EOF) {95 let m = self.start();96 while !self.at(EOF) {97 self.bump();98 }99 m.complete_error(&mut self, "unexpected tokens after end");100 }101 m.complete(&mut self, SOURCE_FILE);102103 self.events104 }105106 pub(crate) fn expect(&mut self, kind: SyntaxKind) {107 self.expect_with_recovery_set(kind, TS![])108 }109110 pub(crate) fn expect_with_recovery_set(111 &mut self,112 kind: SyntaxKind,113 recovery_set: SyntaxKindSet,114 ) {115 if self.at(kind) {116 if kind != EOF {117 self.bump();118 }119 } else {120 self.error_with_recovery_set(recovery_set);121 }122 }123124 125 126 127 128 129 130 131 pub fn error_with_no_skip(&mut self) -> CompletedMarker {132 self.error_with_recovery_set(SyntaxKindSet::ALL)133 }134135 pub fn error_with_recovery_set(&mut self, recovery_set: SyntaxKindSet) -> CompletedMarker {136 let expected = self.expected_syntax_tracking_state.get();137 self.expected_syntax_tracking_state138 .set(ExpectedSyntax::Unnamed(TS![]));139140 if self.at_end() || self.at_ts(recovery_set) {141 let m = self.start();142 return m.complete_missing(self, expected);143 }144145 let current_token = self.current();146147 self.last_error_token = self.offset;148149 let m = self.start();150 self.bump();151 let m = m.complete_unexpected(self, expected, current_token);152 self.clear_expected_syntaxes();153 m154 }155 fn bump_assert(&mut self, kind: SyntaxKind) {156 assert!(self.at(kind), "expected {:?}", kind);157 self.bump_remap(self.current());158 }159 fn bump(&mut self) {160 self.bump_remap(self.current());161 }162 fn bump_remap(&mut self, kind: SyntaxKind) {163 assert_ne!(self.offset, self.kinds.len(), "already at end");164 self.events.push(Event::Token { kind });165 self.offset += 1;166 self.clear_expected_syntaxes();167 }168 fn step(&self) {169 use std::fmt::Write;170 let steps = self.steps.get();171 if steps >= 15000000 {172 let mut out = "seems like parsing is stuck".to_owned();173 {174 let last = 20;175 write!(out, "\n\nLast {} events:", last).unwrap();176 for (i, event) in self177 .events178 .iter()179 .skip(self.events.len().saturating_sub(last))180 .enumerate()181 {182 write!(out, "\n{i}. {event:?}").unwrap();183 }184 }185 {186 let next = 20;187 write!(out, "\n\nNext {next} tokens:").unwrap();188 for (i, tok) in self.kinds.iter().skip(self.offset).take(next).enumerate() {189 write!(out, "\n{i}. {tok:?}").unwrap();190 }191 }192 panic!("{out}")193 }194 self.steps.set(steps + 1);195 }196 fn nth(&self, i: usize) -> SyntaxKind {197 self.step();198 let mut offset = self.offset;199 for _ in 0..i {200 offset += 1;201 }202 self.kinds.get(offset).copied().unwrap_or(EOF)203 }204 fn current(&self) -> SyntaxKind {205 self.nth(0)206 }207 #[must_use]208 pub(crate) fn expected_syntax_name(&mut self, name: &'static str) -> ExpectedSyntaxGuard {209 self.expected_syntax_tracking_state210 .set(ExpectedSyntax::Named(name));211212 ExpectedSyntaxGuard::new(Rc::clone(&self.expected_syntax_tracking_state))213 }214 pub fn at(&mut self, kind: SyntaxKind) -> bool {215 self.nth_at(0, kind)216 }217 pub fn nth_at(&mut self, n: usize, kind: SyntaxKind) -> bool {218 if n == 0 {219 if let ExpectedSyntax::Unnamed(kinds) = self.expected_syntax_tracking_state.get() {220 let kinds = kinds.with(kind);221 self.expected_syntax_tracking_state222 .set(ExpectedSyntax::Unnamed(kinds))223 }224 }225 self.nth(n) == kind226 }227 pub fn at_ts(&mut self, set: SyntaxKindSet) -> bool {228 if let ExpectedSyntax::Unnamed(kinds) = self.expected_syntax_tracking_state.get() {229 let kinds = kinds.union(set);230 self.expected_syntax_tracking_state231 .set(ExpectedSyntax::Unnamed(kinds))232 }233 set.contains(self.current())234 }235 pub fn at_end(&mut self) -> bool {236 self.at(EOF)237 }238}239pub(crate) struct ExpectedSyntaxGuard {240 expected_syntax_tracking_state: Rc<Cell<ExpectedSyntax>>,241}242243impl ExpectedSyntaxGuard {244 fn new(expected_syntax_tracking_state: Rc<Cell<ExpectedSyntax>>) -> Self {245 Self {246 expected_syntax_tracking_state,247 }248 }249}250251impl Drop for ExpectedSyntaxGuard {252 fn drop(&mut self) {253 self.expected_syntax_tracking_state254 .set(ExpectedSyntax::Unnamed(TS![]));255 }256}257258#[derive(Clone, Debug, Copy)]259pub enum ExpectedSyntax {260 Named(&'static str),261 Unnamed(SyntaxKindSet),262}263impl fmt::Display for ExpectedSyntax {264 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {265 match self {266 ExpectedSyntax::Named(name) => write!(f, "{name}"),267 ExpectedSyntax::Unnamed(set) => write!(f, "{set}"),268 }269 }270}271272fn expr(p: &mut Parser) -> CompletedMarker {273 let m = p.start();274 while p.at(T![local]) || p.at(T![assert]) {275 let m = p.start();276277 if p.at(T![local]) {278 p.bump();279 loop {280 if p.at(T![;]) {281 p.bump();282 break;283 }284 bind(p);285286 if p.at(T![,]) {287 p.bump();288 continue;289 }290 p.expect(T![;]);291 break;292 }293 m.complete(p, STMT_LOCAL);294 } else {295 assertion(p);296 p.expect(T![;]);297 m.complete(p, STMT_ASSERT);298 }299 }300 match expr_binding_power(p, 0) {301 Ok(m) => m,302 Err(m) => m,303 };304 m.complete(p, EXPR)305}306fn expr_binding_power(307 p: &mut Parser,308 minimum_binding_power: u8,309) -> Result<CompletedMarker, CompletedMarker> {310 let mut lhs = lhs(p)?;311312 while let Some(op) = BinaryOperatorKind::cast(p.current())313 .or_else(|| p.at(T!['{']).then_some(BinaryOperatorKind::MetaObjectApply))314 {315 let (left_binding_power, right_binding_power) = op.binding_power();316 if left_binding_power < minimum_binding_power {317 break;318 }319320 321 if op != BinaryOperatorKind::MetaObjectApply {322 p.bump();323 }324325 let m = lhs.wrap(p, EXPR).precede(p);326 let parsed_rhs = expr_binding_power(p, right_binding_power)327 .map(|v| v.precede(p).complete(p, EXPR))328 .is_ok();329 lhs = m.complete(330 p,331 if op == BinaryOperatorKind::MetaObjectApply {332 EXPR_OBJ_EXTEND333 } else {334 EXPR_BINARY335 },336 );337338 if !parsed_rhs {339 break;340 }341 }342 Ok(lhs)343}344345const COMPSPEC: SyntaxKindSet = TS![for if];346fn compspec(p: &mut Parser) -> CompletedMarker {347 assert!(p.at_ts(COMPSPEC));348 if p.at(T![for]) {349 let m = p.start();350 p.bump();351 destruct(p);352 p.expect(T![in]);353 expr(p);354 m.complete(p, FOR_SPEC)355 } else if p.at(T![if]) {356 let m = p.start();357 p.bump();358 expr(p);359 m.complete(p, IF_SPEC)360 } else {361 unreachable!()362 }363}364365fn comma(p: &mut Parser) -> bool {366 comma_with_alternatives(p, TS![])367}368fn comma_with_alternatives(p: &mut Parser, set: SyntaxKindSet) -> bool {369 if p.at(T![,]) {370 p.bump();371 true372 } else if p.at_ts(set) {373 let _ex = p.expected_syntax_name("comma");374 p.expect_with_recovery_set(T![,], TS![]);375 true376 } else {377 false378 }379}380381fn field_name(p: &mut Parser) {382 let _e = p.expected_syntax_name("field name");383 let m = p.start();384 if p.at(T!['[']) {385 p.bump();386 expr(p);387 p.expect(T![']']);388 m.complete(p, FIELD_NAME_DYNAMIC);389 } else if p.at(IDENT) {390 name(p);391 m.complete(p, FIELD_NAME_FIXED);392 } else if Text::can_cast(p.current()) {393 text(p);394 m.complete(p, FIELD_NAME_FIXED);395 } else {396 m.forget(p);397 p.error_with_recovery_set(TS![; : :: ::: '(']);398 }399}400fn visibility(p: &mut Parser) {401 if p.at_ts(TS![: :: :::]) {402 p.bump()403 } else {404 p.error_with_recovery_set(TS![=]);405 }406}407fn assertion(p: &mut Parser) {408 let m = p.start();409 p.bump_assert(T![assert]);410 expr(p);411 if p.at(T![:]) {412 p.bump();413 expr(p);414 }415 m.complete(p, ASSERTION);416}417fn object(p: &mut Parser) -> CompletedMarker {418 let m_t = p.start();419 let m = p.start();420 p.bump_assert(T!['{']);421422 let mut elems = 0;423 let mut compspecs = Vec::new();424 let mut asserts = Vec::new();425 loop {426 if p.at(T!['}']) {427 p.bump();428 break;429 }430 if p.at_ts(TS![for]) {431 if elems == 0 {432 let m = p.start();433 m.complete_missing(p, ExpectedSyntax::Named("field definition"));434 }435 while p.at_ts(COMPSPEC) {436 compspecs.push(compspec(p));437 }438 if comma_with_alternatives(p, TS![;]) {439 continue;440 }441 p.expect(R_BRACE);442 break;443 }444 let m = p.start();445 if p.at(T![local]) {446 obj_local(p);447 m.complete(p, MEMBER_BIND_STMT);448 } else if p.at(T![assert]) {449 assertion(p);450 asserts.push(m.complete(p, MEMBER_ASSERT_STMT));451 } else {452 field_name(p);453 if p.at(T![+]) {454 p.bump();455 }456 let params = if p.at(T!['(']) {457 params_desc(p);458 visibility(p);459 expr(p);460 true461 } else if p.at_ts(TS![: :: :::]) && p.nth_at(1, T![function]) {462 visibility(p);463 p.bump_assert(T![function]);464 params_desc(p);465 expr(p);466 true467 } else {468 visibility(p);469 expr(p);470 false471 };472 elems += 1;473474 if params {475 m.complete(p, MEMBER_FIELD_METHOD)476 } else {477 m.complete(p, MEMBER_FIELD_NORMAL)478 };479 };480 while p.at_ts(COMPSPEC) {481 compspecs.push(compspec(p));482 }483 if comma_with_alternatives(p, TS![;]) {484 continue;485 }486 p.expect(R_BRACE);487 break;488 }489490 if elems > 1 && !compspecs.is_empty() {491 for errored in compspecs {492 errored.wrap_error(493 p,494 "compspec may only be used if there is only one object element",495 );496 }497 m.complete(p, OBJ_BODY_MEMBER_LIST);498 } else if !compspecs.is_empty() {499 for errored in asserts {500 errored.wrap_error(p, "asserts can't be used in object comprehensions");501 }502 m.complete(p, OBJ_BODY_COMP);503 } else {504 m.complete(p, OBJ_BODY_MEMBER_LIST);505 }506 m_t.complete(p, EXPR_OBJECT)507}508fn param(p: &mut Parser) {509 let m = p.start();510 destruct(p);511 if p.at(T![=]) {512 p.bump();513 expr(p);514 }515 m.complete(p, PARAM);516}517fn params_desc(p: &mut Parser) -> CompletedMarker {518 let m = p.start();519 p.bump_assert(T!['(']);520521 loop {522 if p.at(T![')']) {523 p.bump();524 break;525 }526 param(p);527 if comma(p) {528 continue;529 }530 p.expect(T![')']);531 break;532 }533534 m.complete(p, PARAMS_DESC)535}536fn args_desc(p: &mut Parser) {537 let m = p.start();538 p.bump_assert(T!['(']);539540 let started_named = Cell::new(false);541 let mut unnamed_after_named = Vec::new();542543 loop {544 if p.at(T![')']) {545 break;546 }547548 let m = p.start();549 if p.at(IDENT) && p.nth_at(1, T![=]) {550 name(p);551 p.bump();552 expr(p);553 m.complete(p, ARG);554 started_named.set(true);555 } else {556 expr(p);557 let arg = m.complete(p, ARG);558 if started_named.get() {559 unnamed_after_named.push(arg)560 }561 }562 if comma(p) {563 continue;564 }565 break;566 }567 p.expect(T![')']);568 if p.at(T![tailstrict]) {569 p.bump()570 }571572 for errored in unnamed_after_named {573 errored.wrap_error(p, "can't use positional arguments after named");574 }575576 m.complete(p, ARGS_DESC);577}578579fn array(p: &mut Parser) -> CompletedMarker {580 581 let m = p.start();582 p.bump_assert(T!['[']);583584 let mut compspecs = Vec::new();585 let mut elems = 0;586587 loop {588 if p.at(T![']']) {589 p.bump();590 break;591 }592 if elems != 0 && p.at_ts(TS![for]) {593 while p.at_ts(COMPSPEC) {594 compspecs.push(compspec(p));595 }596 if comma(p) {597 continue;598 }599 p.expect(T![']']);600 break;601 }602 expr(p);603 elems += 1;604 while p.at_ts(COMPSPEC) {605 compspecs.push(compspec(p));606 }607 if comma(p) {608 continue;609 }610 p.expect(T![']']);611 break;612 }613614 if elems > 1 && !compspecs.is_empty() {615 for spec in compspecs {616 spec.wrap_error(617 p,618 "compspec may only be used if there is only one array element",619 );620 }621622 m.complete(p, EXPR_ARRAY)623 } else if !compspecs.is_empty() {624 m.complete(p, EXPR_ARRAY_COMP)625 } else {626 m.complete(p, EXPR_ARRAY)627 }628}629630#[must_use]631fn slice_desc_or_index(p: &mut Parser) -> bool {632 let m = p.start();633 p.bump();634 635 636 if !p.at(T![:]) && !p.at(T![::]) {637 expr(p);638 }639 if p.at(T![:]) {640 p.bump();641 642 if !p.at(T![']']) {643 expr(p).wrap(p, SLICE_DESC_END);644 }645 if p.at(T![:]) {646 p.bump();647 648 if !p.at(T![']']) {649 expr(p).wrap(p, SLICE_DESC_STEP);650 }651 }652 } else if p.at(T![::]) {653 p.bump();654 655 if !p.at(T![']']) {656 expr(p).wrap(p, SLICE_DESC_END);657 }658 } else {659 660 p.expect(T![']']);661 m.forget(p);662 return false;663 }664 p.expect(T![']']);665 m.complete(p, SLICE_DESC);666 true667}668669fn suffix(p: &mut Parser) {670 loop {671 let start = p.start();672 let _marker: CompletedMarker = if p.at(T![?]) {673 p.bump();674 p.expect(T![.]);675 if p.at(IDENT) {676 name(p);677 start.complete(p, SUFFIX_INDEX)678 } else if p.at(T!['[']) {679 p.bump();680 expr(p);681 p.expect(T![']']);682 start.complete(p, SUFFIX_INDEX_EXPR)683 } else {684 start.complete_missing(p, ExpectedSyntax::Named("index"))685 }686 } else if p.at(T![.]) {687 p.bump();688 name(p);689 start.complete(p, SUFFIX_INDEX)690 } else if p.at(T!['[']) {691 if slice_desc_or_index(p) {692 start.complete(p, SUFFIX_SLICE)693 } else {694 start.complete(p, SUFFIX_INDEX_EXPR)695 }696 } else if p.at(T!['(']) {697 args_desc(p);698 start.complete(p, SUFFIX_APPLY)699 } else {700 start.forget(p);701 break;702 };703 }704}705706fn lhs(p: &mut Parser) -> Result<CompletedMarker, CompletedMarker> {707 let lhs = lhs_basic(p)?;708709 suffix(p);710711 Ok(lhs)712}713fn name(p: &mut Parser) {714 let m = p.start();715 p.expect(IDENT);716 m.complete(p, NAME);717}718fn destruct_rest(p: &mut Parser) {719 let m = p.start();720 p.bump_assert(T![...]);721 if p.at(IDENT) {722 p.bump()723 }724 m.complete(p, DESTRUCT_REST);725}726fn destruct_object_field(p: &mut Parser) {727 let m = p.start();728 name(p);729 if p.at(T![:]) {730 p.bump();731 destruct(p);732 };733 if p.at(T![=]) {734 p.bump();735 expr(p);736 }737 m.complete(p, DESTRUCT_OBJECT_FIELD);738}739fn obj_local(p: &mut Parser) {740 let m = p.start();741 p.bump_assert(T![local]);742 bind(p);743 m.complete(p, OBJ_LOCAL);744}745fn destruct(p: &mut Parser) -> CompletedMarker {746 let m = p.start();747 let _ex = p.expected_syntax_name("destruction specifier");748 if p.at(T![?]) {749 p.bump();750 m.complete(p, DESTRUCT_SKIP)751 } else if p.at(T!['[']) {752 p.bump();753 754 loop {755 if p.at(T![']']) {756 p.bump();757 break;758 } else if p.at(T![...]) {759 760 destruct_rest(p);761 762 763 764 765 } else {766 destruct(p);767 }768 if p.at(T![,]) {769 p.bump();770 continue;771 }772 p.expect(T![']']);773 break;774 }775 m.complete(p, DESTRUCT_ARRAY)776 } else if p.at(T!['{']) {777 p.bump();778 let mut had_rest = false;779 loop {780 if p.at(T!['}']) {781 p.bump();782 break;783 } else if p.at(T![...]) {784 785 destruct_rest(p);786 787 788 789 had_rest = true;790 } else {791 if had_rest {792 p.error_with_recovery_set(TS![]);793 }794 destruct_object_field(p);795 }796 if p.at(T![,]) {797 p.bump();798 continue;799 }800 p.expect(T!['}']);801 break;802 }803 m.complete(p, DESTRUCT_OBJECT)804 } else if p.at(IDENT) {805 name(p);806 m.complete(p, DESTRUCT_FULL)807 } else {808 m.forget(p);809 p.error_with_recovery_set(TS![; , '}', '(', :])810 }811}812fn bind(p: &mut Parser) {813 let m = p.start();814 if p.at(IDENT) && p.nth_at(1, T!['(']) {815 name(p);816 params_desc(p);817 p.expect(T![=]);818 expr(p);819 m.complete(p, BIND_FUNCTION)820 } else if p.at(IDENT) && p.nth_at(1, T![=]) && p.nth_at(2, T![function]) {821 name(p);822 p.expect(T![=]);823 p.expect(T![function]);824 params_desc(p);825 expr(p);826 m.complete(p, BIND_FUNCTION)827 } else {828 destruct(p);829 p.expect(T![=]);830 expr(p);831 m.complete(p, BIND_DESTRUCT)832 };833}834fn text(p: &mut Parser) {835 assert!(Text::can_cast(p.current()));836 p.bump();837}838fn number(p: &mut Parser) {839 assert!(Number::can_cast(p.current()));840 p.bump();841}842fn literal(p: &mut Parser) {843 assert!(Literal::can_cast(p.current()));844 p.bump();845}846fn lhs_basic(p: &mut Parser) -> Result<CompletedMarker, CompletedMarker> {847 let _e = p.expected_syntax_name("expression");848 Ok(if Literal::can_cast(p.current()) {849 let m = p.start();850 literal(p);851 m.complete(p, EXPR_LITERAL)852 } else if Text::can_cast(p.current()) {853 let m = p.start();854 text(p);855 m.complete(p, EXPR_STRING)856 } else if Number::can_cast(p.current()) {857 let m = p.start();858 number(p);859 m.complete(p, EXPR_NUMBER)860 } else if p.at(IDENT) {861 let m = p.start();862 name(p);863 m.complete(p, EXPR_VAR)864 } else if p.at(T![if]) {865 let m = p.start();866 p.bump();867 expr(p);868 p.expect(T![then]);869 expr(p).wrap(p, TRUE_EXPR);870 if p.at(T![else]) {871 p.bump();872 expr(p).wrap(p, FALSE_EXPR);873 }874 m.complete(p, EXPR_IF_THEN_ELSE)875 } else if p.at(T!['[']) {876 array(p)877 } else if p.at(T!['{']) {878 object(p)879 } else if p.at(T![function]) {880 let m = p.start();881 p.bump();882 params_desc(p);883 expr(p);884 m.complete(p, EXPR_FUNCTION)885 } else if p.at(T![error]) {886 let m = p.start();887 p.bump();888 expr(p);889 m.complete(p, EXPR_ERROR)890 } else if p.at(T![import]) || p.at(T![importstr]) || p.at(T![importbin]) {891 let m = p.start();892 p.bump();893 text(p);894 m.complete(p, EXPR_IMPORT)895 } else if let Some(op) = UnaryOperatorKind::cast(p.current()) {896 let ((), right_binding_power) = op.binding_power();897898 let m = p.start();899 p.bump();900 let _ = expr_binding_power(p, right_binding_power);901 m.complete(p, EXPR_UNARY)902 } else if p.at(T!['(']) {903 let m = p.start();904 p.bump();905 expr(p);906 p.expect(T![')']);907 m.complete(p, EXPR_PARENED)908 } else {909 return Err(p.error_with_no_skip());910 })911}912913impl Parse {914 pub fn syntax(&self) -> SyntaxNode {915 SyntaxNode::new_root(self.green_node.clone())916 }917}