☂️ AST Façade Improvements

[MichaReiser]

Description

RSLint's and Rust-analyzer's child accessors defined on the AST nodes return Option<TNode>. For example, the IfStmt child accessors are defined as follow (implementations omitted for brevity):

impl IfStmt {
	pub fn if_token(&self) -> Option<SyntaxToken>;
	pub fn condition(&self) -> Option<Condition>;
	pub fn cons(&self) -> Option<Stmt>;
	pub fn else_token(&self) -> Option<SyntaxToken>;
	pub fn alt(&self) -> Option<Stmt>;
}

We identified that such an API has two major shortcomings for our use case. Let's explore these using the following example:

if (test)) else {}

RSLint creates the following CST for this script:

[email protected]
  [email protected]
    [email protected] "if"
    [email protected] " "
    [email protected]
      [email protected] "("
      [email protected]
        [email protected] "test"
      [email protected] ")"
    **[email protected]
      [email protected] ")"**
    [email protected] " "
    [email protected] "else"
    [email protected] " "
    [email protected]
      [email protected] "{"
      [email protected] "}"
  [email protected] "\n"

1. The condition of the IfStmt has one right parenthesis too many. RSLint excellently recovers from this error by inserting an Error in the place of the if's consequence. The problem with the API is that accessing if_stmt.cons() returns None because Error isn't a Stmt. This has the advantage that a linter will not bother and try to dive into the body but a formatter needs the Error node to format its content (even if that just means printing it as it was in the original source).
2. It's not clear from the API what are the mandatory and optional children. Correctly handling the case where a mandatory child is missing is important where, on the other hand, it's safe to skip missing optional children. That's why the API should guide users to handle missing mandatory children.

Because of this, we plan to make the following two changes to the facade:

• Change the return type for mandatory children to Result<TNode, MissinElementError> (the name and shape of the error are still up for discussion). Changing the return type to Result encodes that this is a mandatory child and guides the user to handle a missing child appropriately.
• Change our grammar to be explicit about where the parser inserts Error elements to recover from syntax errors. For example, the parser may create an Error element for an unknown statement. That's why the Stmt union should be extended to include a Stmt::Unknown case. Adding the Unknown case allows the facade to return an Error element in places of Stmts because it's now part of the Stmt union.
  Designing the grammar requires finding the right balance between recover-granularity and API ergonomics. For instance, the parser must generate an Error statement for --; if the grammar only allows errors on the Stmt level but it can parse expression_statement(error) if errors are also allowed in places of expressions. However, allowing errors in too many places increases the complexity of writing CST passes because they must be handled by the authors.
  The places where a parser wants to insert errors to recover from syntax errors are language-specific.
• We may want to split the Error syntax kind into different Error kinds, for example, UnkownStmt, UnknownExpr, and so on. Splitting the Errors into different kinds allows to query for a specific Unknown kind and implement custom behaviour per kind using methods or implementing the same trait differently for each kind.

The definition of the IfStmt and Stmt changes as follows:

impl IfStmt {
	pub fn if_token(&self) -> **MandatoryElementResult<SyntaxToken>**;
	pub fn condition(&self) -> **MandatoryElementResult<Condition>**;
	pub fn cons(&self) -> **MandatoryElementResult<Stmt>**; // union includes the `UnknownStmt`. 
	pub fn else_clause(&self) -> Option<ElseClause>;
}

enum Stmt {
	If(IfStmt),
	Empty(EmptyStmt),
	...,
	**Unknown(UnknownStmt)**,
}

// other cases...
// 
// import { %%%% } from "./foo"
// Import { namedImports: [ImportSpecifier { binding: Err }] }
//
// let { %%% } = init
// ObjectBinding { properties: [BindingPropertyIdentifier { binding: Err }] }
//
// class { %%% } 
//
// let id = %%%
// VariableDeclaration { declarators: [VariableDeclarator { id: Id, init: Some(Expr::UnknownExpression) }

Part of #1718

AST Facade for lists

Introduce the AstList<N> and AstSeparatedList<N> and change the codegen to reduce an AstList for T*and an AstSeparatedList for (T (',' T)* ','?) where ',' could be any token. See this discussion for more details.

• AstList: View over a homogenous list of child nodes. For example, a list of the statements in a block statement. Wrap many-child inside of a list node #1728
• AstSeparatedList: View over a list that contains nodes separated by a token. For example, the array element nodes that are separated by comma tokens. See this prototype for inspiration. AST Separated List #1746
• Remove workaround for missing/errors

Replace Error with Unknown* nodes

A possible way of defining the Unknown* nodes in Ungrammar could look as follow:

SyntaxNode = SyntaxNode
SyntaxToken = SyntaxToken
SyntaxElement = SyntaxNode | SyntaxToken

JsUnknownStatement = SyntaxElement*
JsUnknownExpression = SyntaxElement*
JsUnknownPattern = SyntaxElement*
JsUnknownMember = SyntaxElement*
JsUnknownBinding = SyntaxElement*
JsUnknownAssignmentTarget = SyntaxElement*

• Change the codegen to skip the SyntaxNode, SyntaxToken, and SyntaxElement nodes and instead, resolve them to the types from the parser crate. #1751
• Define the new error node types and add them to their corresponding union types (Stmt, Expr, ClassElement)
• Revisit the parse rules and replace the generic Error handler #1759
• Parse and Error Recovery API #1815
• Remove the Error kind

Change return type of mandatory nodes

The ungrammar encodes the optionality of the children and the codegen should take that into consideration when generating the field accessors.

Mandatory children should now return Results instead of Option because it's an error if they're missing. Following a draft of the API

type SyntaxResult<T> = Result<T, SyntaxError>;

// Do we need the enum?
enum SyntaxError {
  MissingElement; // Should we store the kind? 
}

impl IfStmt {
  pub fn cons(&self) -> SyntaxResult<Stmt> {
    match self.get_child(5) {
      None => Err(SyntaxError::MissingElement),
      Some(element) => Ok(Stmt::cast(element).expect("Expected a 'Stmt' in the 'cons' slot of an if stmt'")) // Create helper on AstNode that creates a nice error message?
    }
  }
}

• Introduce SyntaxResult #1731
• Change the codegen to respect a child's optionality and generate the appropriate code, fix consuming code #1732

Codegen extensions

• Add support for labels so that we can influence how the child accessors are named. For example, we want to name the left and right expressions of BinaryExpression left and right and not expression and expression. Ungrammar supports the label: Type` syntax. All we need to do is to respect the naming when generating the fields.

• Implode alternatives of tokens #1741
  Support inline token-union types. For example, the binary expression operator can be any of ==, +, -, .... That's why it's defined as operator: ( '==' | '+' | '-' ...). The source gen should only generate a single field for the operator that returns a SyntaxToken

• Flatten unions of unions during the code generation #1743
  It's convenient to define unions in respect of other unions. For example, JsClassMemberName = JsObjectMemberName | JsPrivateClassMemberName where JsObjectMemberName is an union type as well. This is convenient to maintain the grammar but makes the Facade more awkward to use because it requires two matches: first on the outer union and then on the inner union. We can avoid this if we flatten unions inside of the source gen and automatically generate From<InnerUnion> implementations.

New AST Structure and naming

Requirements to AST

• It's possible to visit every element using the AST facade (including separator tokens)

• Visiting a node with a missing mandatory child yields a SyntaxError::MissingElement (for example, a try statement missing both the catch and finally clause

• Children, where their optionality depends on the presence/absence of other siblings, are grouped in a node to guarantee that visiting any yields a SyntaxError::MissingElement if any of the other siblings are missing.

• Prefix nodes with 'Js'

  • Strip Js from codegen and enforce usage of labels in codegen #1733
  • Prefix all nodes (and JS specific tokens) #1734

• Align the AST structure with Rome-classic's AST. This is not a complete list of the work to be done. The end goal is to implement the grammar defined in RFC: JS Grammar #1719

  • Rename Stmt and Expr to AnyJsStatement and AnyJsExpression refactor (rslint_parser): Rename Script & Module, Stmt, and Expr #1767
  • Change JsScript and JsModule refactor (rslint_parser): Rename Script & Module, Stmt, and Expr #1767
  • "Simple" Stmts: Block, Debugger, Empty, Expression, Return, Labeled, With refactor(rslint_parser): Restructure simple statements #1769
  • While-Loops: Continue, Break, DoWhile While refactor(rslint_parser): Update while loops to match new AST Facade #1774
  • For-Loops: For, ForIn, ForOf. Rename ForStmt, CallExpr and NewExpr #1886
  • Control flow: If, Switch, Try, Throw refactor(rslint_parser): IfStatement Ast Node #1771, refactor(rslint_parser): Try Statement Facade #1770
  • Variable declaration (without patterns) #Update Variable Declaration to match new AST Facade #1775
  • Functions: FunctionDeclaration, FunctionExpression, ArrowFunctionExpression (without patterns) Function Expression/Declaration AST Facade #1786
  • Expressions:
    • "Simple Expressions" Refine AST Facade for simple expressions #1780
    • Assignment
    • Call Rename ForStmt, CallExpr and NewExpr #1886
    • Member Refactor MemberExpression AST structure #1799
    • New Rename ForStmt, CallExpr and NewExpr #1886
    • OptionalCallExpression
    • Super
  • String/Number/BigInt/ Boolean/Null Literals Update literals to match new AST Facade #1776
  • Regex Update literals to match new AST Facade #1776
  • Template literal @ematipico
  • Classes Refactor Class AST Tree Structure #1791
  • Objects Restructure Object AST Tree strcuture #1787
  • Module import Parse Import module item #1856
  • Module export
  • Bindings Rename Pattern to Bindings and share parsing logic with Assignment Target #1839
  • Assignment targets Separate Assignment target from Pattern #1805
  • Directive
  • Rename Literals to ...LiteralExpression Rename *Literal nodes to *LiteralExpression #1800
  • remove TS parsing from JS parsing 📎 Gracefully remove TS parsing from JS parsing #1835
  • create generic way to parse lists 📎 Create generic way to parse lists #1836 @ematipico

Documentation the AST

• Documenting error recovery general rules
• Documenting specific error recoveries in nodes
• Listing differences to Rome Classic AST (no FunctionHead etc) @ematipico

[MichaReiser]

@ematipico can you take a look at the codegen extensions and tick off any that you've already implemented as part of #1722

[ematipico]

In #1715, I created a README.md where I wanted to write down all the conventions that we follow to write the grammar. This will be really helpful for future contributions.

I am going to prepare now a list of differences in the AST that I found.

[ematipico]

Regarding the SyntaxResult bit, I am thinking what we could possible have other then something missing (MissingResult).

Maybe we could have SyntaxResult::Unknown in case we find some Unknown* syntax kind?

[MichaReiser]

Regarding the SyntaxResult bit, I am thinking what we could possible have other then something missing (MissingResult).

Maybe we could have SyntaxResult::Unknown in case we find some Unknown* syntax kind?

The approach we decided on uses ‘Unknown *’ nodes that are part of the corresponding union type. But there might be non_unique, as you outlined for the default clause tough I’m not sure if we should just parse this as an unknown case

[ematipico]

OK. I will start the implementation with an enum, and we can revisit it later if we think it's not needed.

[MichaReiser]

Do we already have a solution for the union types? Would be nice to get the code gen as close to done as possible

[ematipico]

I think the best approach is to explode the enum during the code gen.

Let's take this example:

Foo = 'foo' 
Bar = 'bar'
Lorem = 'lorem'
Ipsum = 'ipsum'
AltOne = Foo | Bar
AltTwo = Lorem | Ipsum


MyNode = AltOne | AltTwo

In this example MyNode will result into an enum that contains two enum. As we said before, enum are just a convenience inside the code, and the green tree will only contain the kind that matter. In this example we might have [email protected] "foo", [email protected] "bar", etc.

During the code gen we can detect enums of enum and make a substitution and explode the enum AltOne and AltTwo in respectively Foo | Bar and Lorem | Ipsum , resulting into something like this.

// before
impl AstNode for MyNode {
	fn cast(syntax: SyntaxNode) -> Option<Self> {
		// this here would fail because kind is "FOO"
		let res = match syntax.kind() {
			ALT_ONE => => MyNode::AltOne(AltOne { syntax }),
			ALT_TWO => => MyNode::AltTwo(AltTwo { syntax }),
			_ => None
		}
	}
}

// after
impl AstNode for MyNode {
	fn cast(syntax: SyntaxNode) -> Option<Self> {
		// this here would fail because kind is "FOO"
		let res = match syntax.kind() {
			FOO => => MyNode::Foo(Foo { syntax }),
			BAR => => MyNode::Bar(Bar { syntax }),
			// lorem and ipsum too
			_ => None
		}
	}
}

[MichaReiser]

That makes sense. I was initially worried that it will make it hard to convert a statement to a declaration and then pass it to a function but that’s easy, just call ‘Decl::cast(stmt)’

[MichaReiser]

Support inline token-union types. For example, the binary expression operator can be any of ==, +, -, .... That's why it's defined as operator: ( '==' | '+' | '-' ...). The source gen should only generate a single field for the operator that returns a SyntaxToken

This is not yet implemented. For example, the code gen generates

impl BinExpr {
	pub fn l_angle_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [<]) }
	pub fn r_angle_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [>]) }
	pub fn less_than_equal_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [<=])
	}
	pub fn greater_than_equal_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [>=])
	}
	pub fn equality_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [==]) }
	pub fn strict_equality_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [===])
	}
	pub fn inequality_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [!=]) }
	pub fn strict_inequality_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [!==])
	}
	pub fn plus_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [+]) }
	pub fn minus_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [-]) }
	pub fn star_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [*]) }
	pub fn divide_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [/]) }
	pub fn reminder_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [%]) }
	pub fn exponent_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [**]) }
	pub fn left_shift_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [<<]) }
	pub fn right_shift_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [>>])
	}
	pub fn unsigned_right_shift_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [>>>])
	}
	pub fn amp_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [&]) }
	pub fn bitwise_or_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [|]) }
	pub fn bitwise_xor_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [^]) }
	pub fn nullish_coalescing_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [??])
	}
	pub fn logical_or_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T ! [||]) }
	pub fn logical_and_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T ! [&&])
	}
	pub fn in_token(&self) -> Option<SyntaxToken> { support::token(&self.syntax, T![in]) }
	pub fn instanceof_token(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax, T![instanceof])
	}
}

instead of

impl BinExpr {
	pub fn operator(&self) -> Option<SyntaxToken> {
		support::token(&self.syntax)
	}
}

[ematipico]

@MichaReiser I am tackling the issue in your last comment and I believe the implementation would need to be different.

The function support::token needs to know what token to retrieve. I think the final result should be something like this:

impl BinExpr {
	pub fn operator(&self) -> Option<SyntaxToken> {
		// new function find_token
		support::find_token(&self.syntax, [T![&&], T![==]]) // an array of all the possible expected tokens
	}
}

And the function find_token might be something like this:

	pub(super) fn find_token(
		parent: SyntaxNode,
		possible_kinds: &[SyntaxKind],
	) -> Option<SyntaxToken> {
		parent
			.children_with_tokens()
			.filter_map(|it| it.into_token())
			.find(|it| {
				possible_kinds
					.iter()
					.any(|possible_kind| *possible_kind == it.kind())
			})
	}

[MichaReiser]

Closing this because most AST changes have been implemented. There are some more proposed changes that were discussed in #1868 and are probably worth doing at some point but implementing these changes isn't of the utmost importance at the time being.

The unknown nodes work isn't finished yet. The main outstanding questions are:

• Do we want to stick to unknown nodes or use an alternative approach, for example, setting a has_diagnostic flag
• When is a node's kind changed to an unknown kind. Only for grammatical errors or also in cases of semantic errors?

The next steps are discussed in #1848 and I propose to first write a few analyzers to get some real-world experiences with potential issues before making any decision.