THIRD-PARTY-LICENSE Documentation

Official TypeScript developer resources and documentation for oxc-project/THIRD-PARTY-LICENSE. Verified technical context for AI.

0 stars TypeScript TypeScript 1 file ยท ~20,052 tokens
RAW Doc

1. Project Overview & Quickstart (oxc-project/THIRD-PARTY-LICENSE)

THIRD-PARTY-LICENSE

Open-source repository oxc-project/THIRD-PARTY-LICENSE

Repository Details

Note: High-volume repository documentation is actively indexed and synchronized by YakaAI.

2. Official Technical Reference & Guides (oxc-project/oxc-project.github.io)

File: README.md

Oxc Website

oxc.rs powered by oxc.void.app

Contributing

Install vite-plus if you don't have it already.

Then run:

sh
vp install
vp run dev

Source code for the playground

https://github.com/oxc-project/playground

File: src/docs/learn/parser_in_rust/ast.md

title: Abstract Syntax Tree outline: deep

AST

The parser in the upcoming chapter is responsible for turning Tokens into an abstract syntax tree (AST).
It is much nicer to work on the AST compared to the source text.

All JavaScript toolings work on the AST level, for example:

  • A linter (e.g. ESLint) checks the AST for errors
  • A formatter (e.g.prettier) prints the AST back to JavaScript text
  • A minifier (e.g. terser) transforms the AST
  • A bundler connects all import and export statements between ASTs from different files

In this chapter, let's construct a JavaScript AST by using Rust structs and enums.

Getting familiar with the AST

To get ourselves comfortable with an AST, let's visit ASTExplorer and see what it looks like.
On the top panel, select JavaScript, and then acorn, type in var a and we will see a tree view and a JSON view.

json
{
  "type": "Program",
  "start": 0,
  "end": 5,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 5,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 5,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 5,
            "name": "a"
          },
          "init": null
        }
      ],
      "kind": "var"
    }
  ],
  "sourceType": "script"
}

Since this is a tree, every object is a node with a type name (e.g. Program, VariableDeclaration, VariableDeclarator, Identifier).
start and end are the offsets from the source.

estree

estree is a community standard grammar specification for JavaScript,
it defines all the AST nodes so different tools
can be compatible with each other.

The basic building block for any AST node is the Node type:

rust
#[derive(Debug, Default, Clone, Copy, Serialize, PartialEq, Eq)]
pub struct Node {
    /// Start offset in source
    pub start: usize,

    /// End offset in source
    pub end: usize,
}

impl Node {
    pub fn new(start: usize, end: usize) -> Self {
        Self { start, end }
    }
}

AST for var a is defined as

rust
pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

pub struct VariableDeclarator {
    pub node: Node,
    pub id: BindingIdentifier,
    pub init: Option<Expression>,
}

pub struct BindingIdentifier {
    pub node: Node,
    pub name: String,
}

pub enum Expression {
}

Rust does not have inheritance, so Node is added to each struct (this is called "composition over Inheritance").

Statements and Expressions are enums because they will be expanded with a lot of other node types, for example:

rust
pub enum Expression {
    AwaitExpression(AwaitExpression),
    YieldExpression(YieldExpression),
}

pub struct AwaitExpression {
    pub node: Node,
    pub expression: Box<Expression>,
}

pub struct YieldExpression {
    pub node: Node,
    pub expression: Box<Expression>,
}

The Box is needed because self-referential structs are not allowed in Rust.

:::info
JavaScript grammar has a lot of nuisances, read the grammar tutorial for amusement.
:::

Rust Optimizations

Memory Allocations

We need to look out for heap-allocated structs such as Vec and Box because heap allocations are not cheap.

Take a look at the real world implementation from swc,
we can see that an AST can have lots of Boxs and Vecs, and also note that the Statement and Expression enums contain
a dozen of enum variants.

Memory Arena

Using the global memory allocator for the AST is actually not really efficient.
Every Box and Vec are allocated on demand and then dropped separately.
What we would like to do is pre-allocate memory and drop it in wholesale.

:::info
See also Arenas in Rust and Flattening ASTs for more background on storing ASTs in memory arenas.
:::

bumpalo is a very good candidate for our use case, according to its documentation:

Bump allocation is a fast, but limited approach to allocation.
We have a chunk of memory, and we maintain a pointer within that memory. Whenever we allocate an object,
we do a quick check that we have enough capacity left in our chunk to allocate the object and then update the pointer by the objectโ€™s size. Thatโ€™s it!

The disadvantage of bump allocation is that there is no general way to deallocate individual objects or reclaim the memory region for a no-longer-in-use object.

These trade offs make bump allocation well-suited for phase-oriented allocations. That is, a group of objects that will all be allocated during the same program phase, used, and then can all be deallocated together as a group.

By using bumpalo::collections::Vec and bumpalo::boxed::Box, our AST will have lifetimes added to it:

rust
use bumpalo::collections::Vec;
use bumpalo::boxed::Box;

pub enum Expression<'a> {
    AwaitExpression(Box<'a, AwaitExpression>),
    YieldExpression(Box<'a, YieldExpression>),
}

pub struct AwaitExpression<'a> {
    pub node: Node,
    pub expression: Expression<'a>,
}

pub struct YieldExpression<'a> {
    pub node: Node,
    pub expression: Expression<'a>,
}

:::info
Please be cautious if we are not comfortable dealing with lifetimes at this stage.
Our program will work fine without a memory arena.

Code in the following chapters does not demonstrate the use of a memory arena for simplicity.
:::

Enum Size

The first optimization we are going to make is to reduce the size of the enums.

It is known that the byte size of a Rust enum is the union of all its variants.
For example, the following enum will take up 56 bytes (1 byte for the tag, 48 bytes for the payload, and 8 bytes for alignment).

rust
enum Name {
    Anonymous, // 0 byte payload
    Nickname(String), // 24 byte payload
    FullName{ first: String, last: String }, // 48 byte payload
}

:::info
This example is taken from this blog post
:::

As for the Expression and Statement enums, they can take up to more than 200 bytes with our current setup.

These 200 bytes need to be passed around, or accessed every time we do a matches!(expr, Expression::AwaitExpression(_)) check,
which is not very cache friendly for performance.

A better approach would be to box the enum variants and only carry 16 bytes around.

rust
pub enum Expression {
    AwaitExpression(Box<AwaitExpression>),
    YieldExpression(Box<YieldExpression>),
}

pub struct AwaitExpression {
    pub node: Node,
    pub expression: Expression,
}

pub struct YieldExpression {
    pub node: Node,
    pub expression: Expression,
}

To make sure the enums are indeed 16 bytes on 64-bit systems, we can use std::mem::size_of.

rust
#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
}

"no bloat enum sizes" test cases can often be seen in the Rust compiler source code for ensuring small enum sizes.

rust
// https://github.com/rust-lang/rust/blob/9c20b2a8cc7588decb6de25ac6a7912dcef24d65/compiler/rustc_ast/src/ast.rs#L3033-L3042

// Some nodes are used a lot. Make sure they don't unintentionally get bigger.
#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
mod size_asserts {
    use super::*;
    use rustc_data_structures::static_assert_size;
    // These are in alphabetical order, which is easy to maintain.
    static_assert_size!(AssocItem, 160);
    static_assert_size!(AssocItemKind, 72);
    static_assert_size!(Attribute, 32);
    static_assert_size!(Block, 48);

To find other large types, we can run

bash
RUSTFLAGS=-Zprint-type-sizes cargo +nightly build -p name_of_the_crate --release

and see

text
print-type-size type: `ast::js::Statement`: 16 bytes, alignment: 8 bytes
print-type-size     discriminant: 8 bytes
print-type-size     variant `BlockStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `BreakStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `ContinueStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `DebuggerStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes

JSON Serialization

serde can be used serialize the AST to JSON. Some techniques are needed to make it estree compatible.
Here are some examples:

rust
use serde::Serialize;

#[derive(Debug, Clone, Serialize, PartialEq)]
#[serde(tag = "type")]
#[cfg_attr(feature = "estree", serde(rename = "Identifier"))]
pub struct IdentifierReference {
    #[serde(flatten)]
    pub node: Node,
    pub name: Atom,
}

#[derive(Debug, Clone, Serialize, PartialEq, Hash)]
#[serde(tag = "type")]
#[cfg_attr(feature = "estree", serde(rename = "Identifier"))]
pub struct BindingIdentifier {
    #[serde(flatten)]
    pub node: Node,
    pub name: Atom,
}

#[derive(Debug, Serialize, PartialEq)]
#[serde(untagged)]
pub enum Expression<'a> {
    ...
}
  • serde(tag = "type") is used to make the struct name a "type" field, i.e. { "type" : "..." }
  • cfg_attr + serde(rename) is used to rename different struct names to the same name, since estree does not distinguish different identifiers
  • serde(untagged) on the enum is used to not create an extra JSON object for the enum

File: src/docs/learn/parser_in_rust/errors.md

title: Dealing with Errors outline: deep

Dealing with Errors

Quoting from the Dragon Book

Most programming language specifications do not describe how a compiler should respond to errors; error handling is left to the compiler designer.
Planning the error handling right from the start can both simplify the structure of a compiler and improve its handling of errors.

A fully recoverable parser can construct an AST no matter what we throw at it.
For tools such as linter or formatter, one would wish for a fully recoverable parser so we can act on part of the program.

A panicking parser will abort if there is any grammar mismatch, and a partially recoverable parser will recover from deterministic grammars.

For example, given a grammatically incorrect while statement while true {}, we know it is missing round brackets,
and the only punctuation it can have are round brackets, so we can still return a valid AST and indicate its missing brackets.

Most JavaScript parsers out there are partially recoverable, so we'll do the same and build a partially recoverable parser.

:::info
The Biome parser is a fully recoverable parser.
:::

Rust has the Result type for returning and propagating errors.
In conjunction with the ? syntax, the parse functions will remain simple and clean.

It is common to wrap the Result type so we can replace the error later:

rust
pub type Result<T> = std::result::Result<T, ()>;

Our parse functions will return a Result, for example:

rust
pub fn parse_binding_pattern(&mut self, ctx: Context) -> Result> {
    match self.cur_kind() {
        Kind::LCurly => self.parse_object_binding_pattern(ctx),
        Kind::LBrack => self.parse_array_binding_pattern(ctx),
        kind if kind.is_binding_identifier() => {
          // ... code omitted
        }
        _ => Err(()), // [!code highlight]
    }
}

We can add an expect function for returning an error if the current token does not match the grammar:

rust
/// Expect a `Kind` or return error
pub fn expect(&mut self, kind: Kind) -> Result<()> {
    if !self.at(kind) {
        return Err(())
    }
    self.advance();
    Ok(())
}

And use it as such:

rust
pub fn parse_paren_expression(&mut self, ctx: Context) -> Result<Expression> {
    self.expect(Kind::LParen)?;
    let expression = self.parse_expression(ctx)?;
    self.expect(Kind::RParen)?;
    Ok(expression)
}

:::info

For completeness, the lexer function read_next_token should also return Result
when an unexpected char is found when lexing.

:::

The `Error` Trait

To return specific errors, we need to fill in the Err part of Result:

rust
pub type Result<T> = std::result::Result<T, SyntaxError>;
                                            ^^^^^^^^^^^
#[derive(Debug)]
pub enum SyntaxError {
    UnexpectedToken(String),
    AutoSemicolonInsertion(String),
    UnterminatedMultiLineComment(String),
}

We call it SyntaxError because all "early error"s defined in the grammar section of the ECMAScript specification are syntax errors.

To make this a proper Error, it needs to implement the Error Trait. For cleaner code, we can use macros from the thiserror crate:

rust
#[derive(Debug, Error)]
pub enum SyntaxError {
    #[error("Unexpected Token")]
    UnexpectedToken,

    #[error("Expected a semicolon or an implicit semicolon after a statement, but found none")]
    AutoSemicolonInsertion,

    #[error("Unterminated multi-line comment")]
    UnterminatedMultiLineComment,
}

We can then add an expect helper function for throwing an error if the token does not match:

rust
/// Expect a `Kind` or return error
pub fn expect(&mut self, kind: Kind) -> Result<()> {
    if self.at(kind) {
        return Err(SyntaxError::UnexpectedToken);
    }
    self.advance(kind);
    Ok(())
}

The parse_debugger_statement can now use the expect function for proper error management:

rust
fn parse_debugger_statement(&mut self) -> Result<Statement> {
    let node = self.start_node();
    self.expect(Kind::Debugger)?;
    Ok(Statement::DebuggerStatement {
        node: self.finish_node(node),
    })
}

Notice the ? after the expect,
it is a syntactic sugar called the "question mark operator" for making the
function return early if the expect function returns a Err.

Fancy Error Report

miette is one of the nicest error reporting crate out there,
it provides a fancy colored output

Add miette to your Cargo.toml

toml
[dependencies]
miette = { version = "5", features = ["fancy"] }

We can wrap our Error with miette and not modify the Result type defined in our parser:

rust
pub fn main() -> Result<()> {
    let source_code = "".to_string();
    let file_path = "test.js".to_string();
    let mut parser = Parser::new(&source_code);
    parser.parse().map_err(|error| {
        miette::Error::new(error).with_source_code(miette::NamedSource::new(file_path, source_code))
    })
}

File: src/docs/learn/parser_in_rust/intro.md

title: Introduction outline: deep

Introduction

We are in The Third Age of JavaScript,
the common trend right now is to author JavaScript tools in Rust or Go for their performance gains.

But authoring JavaScript tools are challenging, let alone writing them in Rust.
I have struggled a lot when learning these technologies,
and I wish fewer people to take the same struggling journey.

I want to make my own contribution to the community by writing this guide,
so you don't have to take the same journey as I had.

There are only a handful of developers on the Rust side, and I would like to see you here and join us,
so we can build better and faster tools for everyone to enjoy.

Overview

For this guide, the standard compiler frontend phases will be applied:

text
Source Text --> Lexer --> Token --> Parser --> AST

Writing a JavaScript parser is fairly easy,
it is 10% architectural decisions and 90% hard work on the fine-grained details.

The architectural decisions will mostly affect two categories:

  • the performance of our parser
  • how nice it is to consume our AST

Knowing all the options and trade-offs before building a parser in Rust will make our whole journey much smoother.

Performance

The key to a performant Rust program is to allocate less memory and use fewer CPU cycles.

It is mostly transparent where memory allocations are made just by looking for heap-allocated objects such as a Vec, Box or String.
Reasoning about their usage will give us a sense of how fast our program will be - the more we allocate, the slower our program will be.

Rust gives us the power of zero-cost abstractions, we don't need to worry too much about abstractions causing slower performance.
Be careful with our algorithmic complexities and we will be all good to go.

:::info
You should also read The Rust Performance Book.
:::

Rust Source Code

Whenever the performance of a function call cannot be deduced,
do not be afraid to click the "source" button on the Rust documentation and read the source code,
they are easy to understand most of the time.

:::info
When navigating the Rust source code, searching for a definition is simply looking for
fn function_name, struct struct_name, enum enum_name, etc.
This is one advantage of having constant grammar in Rust (compared to JavaScript ๐Ÿ˜‰).
:::

File: src/docs/learn/parser_in_rust/lexer.md

title: Lexer outline: deep

Lexer

Token

The lexer, also known as tokenizer or scanner, is responsible for transforming source text into tokens.
The tokens will later be consumed by the parser so we don't have to worry about whitespaces and comments from the original text.

Let's start simple and transform a single + text into a token.

rust
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// Token Type
    pub kind: Kind,

    /// Start offset in source
    pub start: usize,

    /// End offset in source
    pub end: usize,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Kind {
    Eof, // end of file
    Plus,
}

A single + gives us

text
[
    Token { kind: Kind::Plus, start: 0, end: 1 },
    Token { kind: Kind::Eof,  start: 1, end: 1 }
]

To loop through the string, we can either keep track of an index and pretend that we are writing C code,
or we can take a look at the string documentation
and find ourselves a Chars iterator to work with.

:::info
The Chars iterator abstracts away the tracking index and boundary checking to make us feel truly safe.

It gives us an Option<char> when we call chars.next().
But please note that a char is not a 0-255 ASCII value,
it is a utf8 Unicode point value with the range of 0 to 0x10FFFF.
:::

Let's define a starter lexer abstraction

rust
use std::str::Chars;

struct Lexer<'a> {
    /// Source Text
    source: &'a str,

    /// The remaining characters
    chars: Chars<'a>
}

impl<'a> Lexer<'a> {
    pub fn new(source: &'a str) -> Self {
        Self {
            source,
            chars: source.chars()
        }
    }
}

:::info
The lifetime 'a here indicates the iterator has a reference to somewhere, it references to a &'a str in this case.
:::

To convert the source text to tokens, just keep calling chars.next() and match on the returned chars.
The final token will always be Kind::Eof.

rust
impl<'a> Lexer<'a> {
    fn read_next_kind(&mut self) -> Kind {
        while let Some(c) = self.chars.next() {
            match c {
              '+' => return Kind::Plus,
              _ => {}
            }
        }
        Kind::Eof
    }

    fn read_next_token(&mut self) -> Token {
        let start = self.offset();
        let kind = self.read_next_kind();
        let end = self.offset();
        Token { kind, start, end }
    }

    /// Get the length offset from the source text, in UTF-8 bytes
    fn offset(&self) -> usize {
        self.source.len() - self.chars.as_str().len()
    }
}

The .len() and .as_str().len() method calls inside fn offset feel like O(n), so let's dig deeper.

.as_str() returns a pointer to a string slice

rust
// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/iter.rs#L112-L115

pub fn as_str(&self) -> &'a str {
    // SAFETY: `Chars` is only made from a str, which guarantees the iter is valid UTF-8.
    unsafe { from_utf8_unchecked(self.iter.as_slice()) }
}

A slice is a view into a block of memory represented as a pointer and a length.
The .len() method returns the metadata stored inside the slice

rust
// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L157-L159

pub const fn len(&self) -> usize {
    self.as_bytes().len()
}
rust
// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L323-L325

pub const fn as_bytes(&self) -> &[u8] {
    // SAFETY: const sound because we transmute two types with the same layout
    unsafe { mem::transmute(self) }
}
rust
// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/mod.rs#L129-L138

pub const fn len(&self) -> usize {
    // FIXME: Replace with `crate::ptr::metadata(self)` when that is const-stable.
    // As of this writing this causes a "Const-stable functions can only call other
    // const-stable functions" error.

    // SAFETY: Accessing the value from the `PtrRepr` union is safe since *const T
    // and PtrComponents<T> have the same memory layouts. Only std can make this
    // guarantee.
    unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata }
}

All the above code will get compiled into a single data access, so .as_str().len() is actually O(1).

Peek

To tokenize multi-character operators such as ++ or +=, a helper function peek is required:

rust
fn peek(&self) -> Option<char> {
    self.chars.clone().next()
}

We don't want to advance the original chars iterator so we clone the iterator and advance the index.

:::info
The clone is cheap if we dig into the source code,
it just copies the tracking and boundary index.

rust
// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/iter.rs#L148-L152

impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
    }
}

:::

The difference between peek and chars.next() is the former will always return the same next char,
while the later will move forward and return a different char.

To demonstrate, consider the string abc:

  • repeated peek() call returns Some(a), Some(a), Some(a), ...
  • repeated chars.next() call returns Some('a'), Some('b'), Some('c'), None.

Equipped with peek, tokenizing ++ and += are just nested if statements.

Here is a real-world implementation from jsparagus:

rust
// https://github.com/mozilla-spidermonkey/jsparagus/blob/master/crates/parser/src/lexer.rs#L1769-L1791

'+' => match self.peek() {
    Some('+') => {
        self.chars.next();
        return self.set_result(
            TerminalId::Increment,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    Some('=') => {
        self.chars.next();
        return self.set_result(
            TerminalId::AddAssign,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    _ => return self.set_result(
        TerminalId::Plus,
        SourceLocation::new(start, self.offset()),
        TokenValue::None,
    ),
},

The above logic applies to all operators, so let us expand our knowledge on lexing JavaScript.

JavaScript

A lexer written in Rust is rather boring, it feels like writing C code
where we write long chained if statements and check for each char and then return the respective token.

The real fun begins when we start lexing for JavaScript.

Let's open up the ECMAScript Language Specification and re-learn JavaScript.

:::tip
I still remember the first time I opened up the specification and went into a little corner
and cried in agony because it feels like reading foreign text with jargons everywhere.
So head over to my guide on reading the specification if things don't make sense.
:::

Comments

Comments have no semantic meaning, they can be skipped if we are writing a runtime,
but they need to be taken into consideration if we are writing a linter or a bundler.

Identifiers and Unicode

We mostly code in ASCII,
but Chapter 11 ECMAScript Language: Source Text
states the source text should be in Unicode.
And Chapter 12.6 Names and Keywords
states the identifiers are interpreted according to the Default Identifier Syntax given in Unicode Standard Annex #31.
In detail:

text
IdentifierStartChar ::
    UnicodeIDStart

IdentifierPartChar ::
    UnicodeIDContinue

UnicodeIDStart ::
    any Unicode code point with the Unicode property โ€œID_Startโ€

UnicodeIDContinue ::
    any Unicode code point with the Unicode property โ€œID_Continueโ€

This means that we can write var เฒ _เฒ  but not var ๐Ÿฆ€,
เฒ  has the Unicode property "ID_Start" while ๐Ÿฆ€ does not.

:::info

I published the unicode-id-start crate for this exact purpose.
unicode_id_start::is_id_start(char) and unicode_id_start::is_id_continue(char) can be called to check Unicode.

:::

Keywords

All the keywords such as if, while and for
need to be tokenized and interpreted as a whole.
They need to be added to the token kind enum so we don't have to make string comparisons in the parser.

rust
pub enum Kind {
    Identifier,
    If,
    While,
    For
}

:::tip
undefined is not a keyword, it is unnecessary to add it here.
:::

Tokenizing keywords will just be matching the identifier from above.

rust
fn match_keyword(&self, ident: &str) -> Kind {
    // all keywords are 1 < length <= 10
    if ident.len() == 1 || ident.len() > 10 {
        return Kind::Identifier;
    }
    match ident {
        "if" => Kind::If,
        "while" => Kind::While,
        "for" => Kind::For,
        _ => Kind::Identifier
    }
}

Token Value

We often need to compare identifiers, numbers and strings in later stages of the compiler phases,
for example testing against identifiers inside a linter.

These values are currently in plain source text,
let's convert them to Rust types so they are easier to work with.

rust{4-6}
pub enum Kind {
    Eof, // end of file
    Plus,
    Identifier,
    Number,
    String,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// Token Type
    pub kind: Kind,

    /// Start offset in source
    pub start: usize,

    /// End offset in source
    pub end: usize,

    pub value: TokenValue,// [!code highlight]
}

#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(String),
}

When an identifier foo or string "bar" is tokenized , we get

text
Token { kind: Kind::Identifier, start: 0, end: 2, value: TokenValue::String("foo") }
Token { kind: Kind::String, start: 0, end: 4, value: TokenValue::String("bar") }

To convert them to Rust strings, call let s = self.source[token.start..token.end].to_string()
and save it with token.value = TokenValue::String(s).

When we tokenize a number 1.23, we get a token with Token { start: 0, end: 3 }.
To convert it to Rust f64, we can use the string parse
method by calling self.source[token.start..token.end].parse::<f64>(), and then save the value into token.value.
For binary, octal and integers, an example of their parsing techniques can be found in jsparagus.

Rust Optimizations

Smaller Tokens

It is tempting to put the token values inside the Kind enum and aim for simpler and safer code:

rust
pub enum Kind {
    Number(f64),
    String(String),
}

But it is known that the byte size of a Rust enum is the union of all its variants.
This enum packs a lot of bytes compared to the original enum, which has only 1 byte.
There will be heavy usages of this Kind enum in the parser,
dealing with a 1 byte enum will obviously be faster than a multi-byte enum.

String Interning

It is not performant to use String in compilers, mainly due to:

  • String is a heap allocated object
  • String comparison is an O(n) operation

String Interning solves these problems by
storing only one copy of each distinct string value with a unique identifier in a cache.
There will only be one heap allocation per distinct identifier or string, and string comparisons become O(1).

There are lots of string interning libraries on crates.io
with different pros and cons.

A sufficient starting point is to use string-cache,
it has an Atom type and a compile time atom!("string") interface.

With string-cache, TokenValue becomes

rust
#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(Atom), // [!code highlight]
}

and string comparison becomes matches!(value, TokenValue::String(atom!("string"))).

File: src/docs/learn/parser_in_rust/parser.md

id: parser title: Parser

Parser

The parser we are going to construct is called a recursive descent parser,
it is the manual process of going down the grammar and building up the AST.

The parser starts simple, it holds the source code, the lexer, and the current token consumed from the lexer.

rust
pub struct Parser<'a> {
    /// Source Code
    source: &'a str,

    lexer: Lexer<'a>,

    /// Current Token consumed from the lexer
    cur_token: Token,

    /// The end range of the previous token
    prev_token_end: usize,
}

impl<'a> Parser<'a> {
    pub fn new(source: &'a str) -> Self {
        Self {
            source,
            lexer: Lexer::new(source),
            cur_token: Token::default(),
        }
    }

    pub fn parse(&mut self) -> Program<'a> {
        Ok(Program {
            node: Node {
                start: 0,
                end: self.source.len(),
            }
            body: vec![]
        })
    }
}

Helper functions

The current token cur_token: Token holds the current token returned from the lexer.
We'll make the parser code cleaner by adding some helper functions for navigating and inspecting this token.

rust
impl<'a> Parser<'a> {
    fn start_node(&self) -> Node {
        let token = self.cur_token();
        Node::new(token.start, 0)
    }

    fn finish_node(&self, node: Node) -> Node {
        Node::new(node.start, self.prev_token_end)
    }

    fn cur_token(&self) -> &Token {
        &self.cur_token
    }

    fn cur_kind(&self) -> Kind {
        self.cur_token.kind
    }

    /// Checks if the current index has token `Kind`
    fn at(&self, kind: Kind) -> bool {
        self.cur_kind() == kind
    }

    /// Advance if we are at `Kind`
    fn bump(&mut self, kind: Kind) {
        if self.at(kind) {
            self.advance();
        }
    }

    /// Advance any token
    fn bump_any(&mut self) {
        self.advance();
    }

    /// Advance and return true if we are at `Kind`, return false otherwise
    fn eat(&mut self, kind: Kind) -> bool {
        if self.at(kind) {
            self.advance();
            return true;
        }
        false
    }

    /// Move to the next token
    fn advance(&mut self) {
        let token = self.lexer.next_token();
        self.prev_token_end = self.cur_token.end;
        self.cur_token = token;
    }
}

Parse Functions

The DebuggerStatement is the most simple statement to parse, so let's try and parse it and return a valid program

rust
impl<'a> Parser<'a> {
    pub fn parse(&mut self) -> Program {
        let stmt = self.parse_debugger_statement();
        let body = vec![stmt];
        Program {
            node: Node {
                start: 0,
                end: self.source.len(),
            }
            body,
        }
    }

    fn parse_debugger_statement(&mut self) -> Statement {
        let node = self.start_node();
        // NOTE: the token returned from the lexer is `Kind::Debugger`, we'll fix this later.
        self.bump_any();
        Statement::DebuggerStatement {
            node: self.finish_node(node),
        }
    }
}

All the other parse functions build on these primitive helper functions,
for example parsing the while statement in swc:

rust
// https://github.com/swc-project/swc/blob/554b459e26b24202f66c3c58a110b3f26bbd13cd/crates/swc_ecma_parser/src/parser/stmt.rs#L952-L970

fn parse_while_stmt(&mut self) -> PResult<Stmt> {
    let start = cur_pos!(self);

    assert_and_bump!(self, "while");

    expect!(self, '(');
    let test = self.include_in_expr(true).parse_expr()?;
    expect!(self, ')');

    let ctx = Context {
        is_break_allowed: true,
        is_continue_allowed: true,
        ..self.ctx()
    };
    let body = self.with_ctx(ctx).parse_stmt(false).map(Box::new)?;

    let span = span!(self, start);
    Ok(Stmt::While(WhileStmt { span, test, body }))
}

Parsing Expressions

The grammar for expressions is deeply nested and recursive,
which may cause stack overflow on long expressions (for example in this TypeScript test),

To avoid recursion, we can use a technique called "Pratt Parsing". A more in-depth tutorial can be found here, written by the author of Rust-Analyzer.
And a Rust version here in Rome.

Lists

There are lots of places where we need to parse a list separated by a punctuation, for example [a, b, c] or {a, b, c}.

The code for parsing lists are all similar, we can use the template method pattern
to avoid duplication by using traits.

rust
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/parser/parse_lists.rs#L131-L157

fn parse_list(&mut self, p: &mut Parser) -> CompletedMarker {
    let elements = self.start_list(p);
    let mut progress = ParserProgress::default();
    let mut first = true;
    while !p.at(JsSyntaxKind::EOF) && !self.is_at_list_end(p) {
        if first {
            first = false;
        } else {
            self.expect_separator(p);

            if self.allow_trailing_separating_element() && self.is_at_list_end(p) {
                break;
            }
        }

        progress.assert_progressing(p);

        let parsed_element = self.parse_element(p);

        if parsed_element.is_absent() && p.at(self.separating_element_kind()) {
            // a missing element
            continue;
        } else if self.recover(p, parsed_element).is_err() {
            break;
        }
    }
    self.finish_list(p, elements)
}

This pattern can also prevent us from infinite loops, specifically progress.assert_progressing(p);.

Implementation details can then be provided for different lists, for example:

rust
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/syntax/expr.rs#L1543-L1580

struct ArrayElementsList;

impl ParseSeparatedList for ArrayElementsList {
    fn parse_element(&mut self, p: &mut Parser) -> ParsedSyntax {
        match p.cur() {
            T![...] => parse_spread_element(p, ExpressionContext::default()),
            T![,] => Present(p.start().complete(p, JS_ARRAY_HOLE)),
            _ => parse_assignment_expression_or_higher(p, ExpressionContext::default()),
        }
    }

    fn is_at_list_end(&self, p: &mut Parser) -> bool {
        p.at(T![']'])
    }

    fn recover(&mut self, p: &mut Parser, parsed_element: ParsedSyntax) -> RecoveryResult {
        parsed_element.or_recover(
            p,
            &ParseRecovery::new(
                JS_UNKNOWN_EXPRESSION,
                EXPR_RECOVERY_SET.union(token_set!(T![']'])),
            ),
            js_parse_error::expected_array_element,
        )
    }

    fn list_kind() -> JsSyntaxKind {
        JS_ARRAY_ELEMENT_LIST
    }

    fn separating_element_kind(&mut self) -> JsSyntaxKind {
        T![,]
    }

    fn allow_trailing_separating_element(&self) -> bool {
        true
    }
}

Cover Grammar

Detailed in cover grammar, there are times when we need to convert an Expression to a BindingIdentifier. Dynamic languages such as JavaScript can simply rewrite the node type:

javascript reference
https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/lval.js#L11-L26

But in Rust, we need to do a struct to struct transformation. A nice and clean way to do this is to use an trait.

rust
pub trait CoverGrammar<'a, T>: Sized {
    fn cover(value: T, p: &mut Parser<'a>) -> Result<Self>;
}

The trait accepts T as the input type, and Self and the output type, so we can define the following:

rust
impl<'a> CoverGrammar<'a, Expression<'a>> for BindingPattern<'a> {
    fn cover(expr: Expression<'a>, p: &mut Parser<'a>) -> Result<Self> {
        match expr {
            Expression::Identifier(ident) => Self::cover(ident.unbox(), p),
            Expression::ObjectExpression(expr) => Self::cover(expr.unbox(), p),
            Expression::ArrayExpression(expr) => Self::cover(expr.unbox(), p),
            _ => Err(()),
        }
    }
}

impl<'a> CoverGrammar<'a, ObjectExpression<'a>> for BindingPattern<'a> {
    fn cover(obj_expr: ObjectExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
        ...
        BindingIdentifier::ObjectPattern(ObjectPattern { .. })
    }
}

impl<'a> CoverGrammar<'a, ArrayExpression<'a>> for BindingPattern<'a> {
    fn cover(expr: ArrayExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
        ...
        BindingIdentifier::ArrayPattern(ArrayPattern { .. })
    }
}

Then for anywhere we need to convert an Expression to BindingPattern,
call BindingPattern::cover(expression).

TypeScript

So you are done with JavaScript and you want to challenge parsing TypeScript?
The bad news is that there is no specification,
but the good news is that the TypeScript parser is in a single file ๐Ÿ™ƒ.

JSX vs TSX

For the following code,

javascript
let foo = <string> bar;

It is a syntax error if this is tsx (Unterminated JSX),
but it is correct VariableDeclaration with TSTypeAssertion.

Lookahead

In certain places, the parser need to lookahead and peek more than one token to determine the correct grammar.

TSIndexSignature

For example, to parse TSIndexSignature, consider the following two cases:

typescript
type A = { readonly [a: number]: string }
           ^__________________________^ TSIndexSignature

type B = { [a]: string }
           ^_________^ TSPropertySignature

For type A on the first {, we need to peek 5 tokens (readonly, [, a, : and number) in order to make sure
it is a TSIndexSignature and not a TSPropertySignature.

To make this possible and efficient, the lexer requires a buffer for storing multiple tokens.

Arrow Expressions

Discussed in cover grammar,
we need to convert from Expressions to BindingPatterns when the => token is found after a SequenceExpression.

But this approach does not work for TypeScript as each item inside the () can have TypeScript syntax, there are just too many cases to cover, for example:

typescript
(<x>a, b as c, d!);
(a?: b = {} as c!) => {};

It is recommended to study the TypeScript source code for this specific case. The relevant code are:

text
/* Detailed source-code truncated for AI context efficiency. */

In summary, the TypeScript parser uses a combination of lookahead (fast path) and backtracking to parse arrow functions.

File: src/docs/learn/parser_in_rust/semantic_analysis.md

title: Semantic Analysis outline: deep

Semantic Analysis

Semantic analysis is the process of checking whether our source code is correct or not.
We need to check against all the "Early Error" rules in the ECMAScript specification.

Context

For grammar contexts such as [Yield] or [Await], an error need to be raised when the grammar forbids them, for example:

text
BindingIdentifier[Yield, Await] :
  Identifier
  yield
  await

13.1.1 Static Semantics: Early Errors

BindingIdentifier[Yield, Await] : yield
* It is a Syntax Error if this production has a [Yield] parameter.

* BindingIdentifier[Yield, Await] : await
It is a Syntax Error if this production has an [Await] parameter.

need to raise an error for

javascript
async function* foo() {
  var yield, await;
}

because AsyncGeneratorDeclaration has [+Yield] and [+Await] for AsyncGeneratorBody:

text
AsyncGeneratorBody :
  FunctionBody[+Yield, +Await]

An example in Biome checking for the yield keyword:

rust
// https://github.com/rome/tools/blob/5a059c0413baf1d54436ac0c149a829f0dfd1f4d/crates/rome_js_parser/src/syntax/expr.rs#L1368-L1377

pub(super) fn parse_identifier(p: &mut Parser, kind: JsSyntaxKind) -> ParsedSyntax {
    if !is_at_identifier(p) {
        return Absent;
    }

    let error = match p.cur() {
        T![yield] if p.state.in_generator() => Some(
            p.err_builder("Illegal use of `yield` as an identifier in generator function")
                .primary(p.cur_range(), ""),
        ),

Scope

For declaration errors:

text
14.2.1 Static Semantics: Early Errors

Block : { StatementList }
* It is a Syntax Error if the LexicallyDeclaredNames of StatementList contains any duplicate entries.
* It is a Syntax Error if any element of the LexicallyDeclaredNames of StatementList also occurs in the VarDeclaredNames of StatementList.

We need to add a scope tree. A scope tree has all the vars and lets declared inside it.
It is also a parent pointing tree where we want to navigate up the tree and search for binding identifiers in parent scopes.
The data structure we can use is a indextree.

rust
use indextree::{Arena, Node, NodeId};
use bitflags::bitflags;

pub type Scopes = Arena<Scope>;
pub type ScopeId = NodeId;

bitflags! {
    #[derive(Default)]
    pub struct ScopeFlags: u8 {
        const TOP = 1 << 0;
        const FUNCTION = 1 << 1;
        const ARROW = 1 << 2;
        const CLASS_STATIC_BLOCK = 1 << 4;
        const VAR = Self::TOP.bits | Self::FUNCTION.bits | Self::CLASS_STATIC_BLOCK.bits;
    }
}

#[derive(Debug, Clone)]
pub struct Scope {
    /// [Strict Mode Code](https://tc39.es/ecma262/#sec-strict-mode-code)
    /// [Use Strict Directive Prologue](https://tc39.es/ecma262/#sec-directive-prologues-and-the-use-strict-directive)
    pub strict_mode: bool,

    pub flags: ScopeFlags,

    /// [Lexically Declared Names](https://tc39.es/ecma262/#sec-static-semantics-lexicallydeclarednames)
    pub lexical: IndexMap<Atom, SymbolId, FxBuildHasher>,

    /// [Var Declared Names](https://tc39.es/ecma262/#sec-static-semantics-vardeclarednames)
    pub var: IndexMap<Atom, SymbolId, FxBuildHasher>,

    /// Function Declarations
    pub function: IndexMap<Atom, SymbolId, FxBuildHasher>,
}

The scope tree can either be built inside the parser for performance reasons, or built-in a separate AST pass.

Generally, a ScopeBuilder is needed:

rust
pub struct ScopeBuilder {
    scopes: Scopes,
    root_scope_id: ScopeId,
    current_scope_id: ScopeId,
}

impl ScopeBuilder {
    pub fn current_scope(&self) -> &Scope {
        self.scopes[self.current_scope_id].get()
    }

    pub fn enter_scope(&mut self, flags: ScopeFlags) {
        // Inherit strict mode for functions
        // https://tc39.es/ecma262/#sec-strict-mode-code
        let mut strict_mode = self.scopes[self.root_scope_id].get().strict_mode;
        let parent_scope = self.current_scope();
        if !strict_mode
            && parent_scope.flags.intersects(ScopeFlags::FUNCTION)
            && parent_scope.strict_mode
        {
            strict_mode = true;
        }

        let scope = Scope::new(flags, strict_mode);
        let new_scope_id = self.scopes.new_node(scope);
        self.current_scope_id.append(new_scope_id, &mut self.scopes);
        self.current_scope_id = new_scope_id;
    }

    pub fn leave_scope(&mut self) {
      self.current_scope_id = self.scopes[self.current_scope_id].parent().unwrap();
    }
}

We then call enter_scope and leave_scope accordingly inside the parse functions, for example in acorn:

javascript reference
https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/statement.js#L425-L437

:::info
One of the downsides of this approach is that for arrow functions,
we may need to create a temporary scope and then drop it afterwards if it is not an arrow function but a sequence expression.
This is detailed in cover grammar.
:::

The Visitor Pattern

If we decide to build the scope tree in another pass for simplicity,
then every node in the AST need to be visited in depth-first preorder and build the scope tree.

We can use the Visitor Pattern
to separate out the traversal process from the operations performed on each object.

Upon visit, we can call enter_scope and leave_scope accordingly to build the scope tree.

File: src/docs/learn/ecmascript/grammar.md

title: Grammar outline: deep

Grammar

JavaScript has one of the most challenging grammar to parse,
this tutorial details all the sweat and tears I had while learning it.

LL(1) Grammar

According to Wikipedia,

an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right

The first L means the scanning the source from Left to right,
and the second L means the construction of a Leftmost derivation tree.

Context-free and the (1) in LL(1) means a tree can be constructed by just peeking at the next token and nothing else.

LL Grammars are of particular interest in academia because we are lazy human beings and we want to write programs that generate parsers automatically so we don't need to write parsers by hand.

Unfortunately, most industrial programming languages do not have a nice LL(1) grammar,
and this applies to JavaScript too.

:::info
Mozilla started the jsparagus project a few years ago
and wrote a LALR parser generator in Python.
They haven't updated it much in the past two years and they sent a strong message at the end of js-quirks.md

What have we learned today?

  • Do not write a JS parser.
  • JavaScript has some syntactic horrors in it. But hey, you don't make the world's most widely used programming language by avoiding all mistakes. You do it by shipping a serviceable tool, in the right circumstances, for the right users.

:::

The only practical way to parse JavaScript is to write a recursive descent parser by hand because of the nature of its grammar,
so let's learn all the quirks in the grammar before we shoot ourselves in the foot.

The list below starts simple and will become difficult to grasp,
so please take grab a coffee and take your time.

Identifiers

There are three types of identifiers defined in #sec-identifiers,

text
IdentifierReference[Yield, Await] :
BindingIdentifier[Yield, Await] :
LabelIdentifier[Yield, Await] :

estree and some ASTs do not distinguish the above identifiers,
and the specification does not explain them in plain text.

BindingIdentifiers are declarations and IdentifierReferences are references to binding identifiers.
For example in var foo = bar, foo is a BindingIdentifier and bar is a IdentifierReference in the grammar:

text
VariableDeclaration[In, Yield, Await] :
    BindingIdentifier[?Yield, ?Await] Initializer[?In, ?Yield, ?Await] opt

Initializer[In, Yield, Await] :
    = AssignmentExpression[?In, ?Yield, ?Await]

follow AssignmentExpression into PrimaryExpression we get

text
PrimaryExpression[Yield, Await] :
    IdentifierReference[?Yield, ?Await]

Declaring these identifiers differently in the AST will greatly simply downstream tools, especially for semantic analysis.

rust
pub struct BindingIdentifier {
    pub node: Node,
    pub name: Atom,
}

pub struct IdentifierReference {
    pub node: Node,
    pub name: Atom,
}

Class and Strict Mode

ECMAScript Class is born after strict mode, so they decided that everything inside a class must be strict mode for simplicity.
It is stated as such in #sec-class-definitions with just a Node: A class definition is always strict mode code.

It is easy to declare strict mode by associating it with function scopes, but a class declaration does not have a scope,
we need to keep an extra state just for parsing classes.

rust
// https://github.com/swc-project/swc/blob/f9c4eff94a133fa497778328fa0734aa22d5697c/crates/swc_ecma_parser/src/parser/class_and_fn.rs#L85
fn parse_class_inner(
    &mut self,
    _start: BytePos,
    class_start: BytePos,
    decorators: Vec<Decorator>,
    is_ident_required: bool,
) -> PResult<(Option, Class)> {
    self.strict_mode().parse_with(|p| {
        expect!(p, "class");

Legacy Octal and Use Strict

#sec-string-literals-early-errors disallows escaped legacy octal inside strings "\01":

text
EscapeSequence ::
    LegacyOctalEscapeSequence
    NonOctalDecimalEscapeSequence

It is a Syntax Error if the source text matched by this production is strict mode code.

The best place to detect this is inside the lexer, it can ask the parser for strict mode state and throw errors accordingly.

But, this becomes impossible when mixed with directives:

javascript reference
https://github.com/tc39/test262/blob/747bed2e8aaafe8fdf2c65e8a10dd7ae64f66c47/test/language/literals/string/legacy-octal-escape-sequence-prologue-strict.js#L16-L19

use strict is declared after the escaped legacy octal, yet the syntax error needs to be thrown.
Fortunately, no real code uses directives with legacy octals ... unless you want to pass the test262 case from above.

Non-simple Parameter and Strict Mode

Identical function parameters is allowed in non-strict mode function foo(a, a) { },
and we can forbid this by adding use strict: function foo(a, a) { "use strict" }.
Later on in es6, other grammars were added to function parameters, for example function foo({ a }, b = c) {}.

Now, what happens if we write the following where "01" is a strict mode error?

javascript
function foo(
  value = (function() {
    return "\01";
  }()),
) {
  "use strict";
  return value;
}

More specifically, what should we do if there is a strict mode syntax error inside the parameters thinking from the parser perspective?
So in #sec-function-definitions-static-semantics-early-errors, it just bans this by stating

text
FunctionDeclaration :
FunctionExpression :

It is a Syntax Error if FunctionBodyContainsUseStrict of FunctionBody is true and IsSimpleParameterList of FormalParameters is false.

Chrome throws this error with a mysterious message "Uncaught SyntaxError: Illegal 'use strict' directive in function with non-simple parameter list".

A more in-depth explanation is described in this blog post by the author of ESLint.

:::info

Fun fact, the above rule does not apply if we are targeting es5 in TypeScript, it transpiles to

javascript
function foo(a, b) {
  "use strict";
  if (b === void 0) b = "\01";
}

:::

Parenthesized Expression

Parenthesized expressions are supposed to not have any semantic meanings?
For instance the AST for ((x)) can just be a single IdentifierReference, not ParenthesizedExpression -> ParenthesizedExpression -> IdentifierReference.
And this is the case for JavaScript grammar.

But ... who would have thought it can have runtime meanings.
Found in this estree issue, it shows that

javascript
> fn = function () {};
> fn.name
< "fn"

> (fn) = function () {};
> fn.name
< ''

So eventually acorn and babel added the preserveParens option for compatibility.

Function Declaration in If Statement

If we follow the grammar precisely in #sec-ecmascript-language-statements-and-declarations:

text
Statement[Yield, Await, Return] :
    ... lots of statements

Declaration[Yield, Await] :
    ... declarations

The Statement node we define for our AST would obviously not contain Declaration,

but in Annex B #sec-functiondeclarations-in-ifstatement-statement-clauses,
it allows declaration inside the statement position of if statements in non-strict mode:

javascript
if (x) {
  function foo() {}
} else function bar() {}

Label statement is legit

We probably have never written a single line of labelled statement, but it is legit in modern JavaScript and not banned by strict mode.

The following syntax is correct, it returns a labelled statement (not object literal).

javascript
<Foo
  bar={() => {
    baz: "quaz";
  }}
/>
//   ^^^^^^^^^^^ `LabelledStatement`

`let` is not a keyword

let is not a keyword so it is allowed to appear anywhere unless the grammar explicitly states let is not allowed in such positions.
Parsers need to peek at the token after the let token and decide what it needs to be parsed into, e.g.:

javascript
let a;
let = foo;
let instanceof x;
let + 1;
while (true) let;
a = let[0];

For-in / For-of and the [In] context

If we look at the grammar for for-in and for-of in #prod-ForInOfStatement,
it is immediately confusing to understand how to parse these.

There are two major obstacles for us to understand: the [lookahead โ‰  let] part and the [+In] part.

If we have parsed to for (let, we need to check the peeking token is:

  • not in to disallow for (let in)
  • is {, [ or an identifier to allow for (let {} = foo), for (let [] = foo) and for (let bar = foo)

Once reached the of or in keyword, the right-hand side expression needs to be passed with the correct [+In] context to disallow
the two in expressions in #prod-RelationalExpression:

text
RelationalExpression[In, Yield, Await] :
    [+In] RelationalExpression[+In, ?Yield, ?Await] in ShiftExpression[?Yield, ?Await]
    [+In] PrivateIdentifier in ShiftExpression[?Yield, ?Await]

Note 2: The [In] grammar parameter is needed to avoid confusing the in operator in a relational expression with the in operator in a for statement.

And this is the only application for the [In] context in the entire specification.

Also to note, the grammar [lookahead โˆ‰ { let, async of }] forbids for (async of ...),
and it needs to be explicitly guarded against.

Block-Level Function Declarations

In Annex B.3.2 #sec-block-level-function-declarations-web-legacy-compatibility-semantics,
an entire page is dedicated to explain how FunctionDeclaration is supposed to behave in Block statements.
It boils down to

javascript reference
https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/scope.js#L30-L35

The name of a FunctionDeclaration needs to be treated the same as a var declaration if its inside a function declaration.
This code snippet errors with a re-declaration error since bar is inside a block scope:

javascript
function foo() {
  if (true) {
    var bar;
    function bar() {} // redeclaration error
  }
}

meanwhile, the following does not error because it is inside a function scope, function bar is treated as a var declaration:

javascript
function foo() {
  var bar;
  function bar() {}
}

Grammar Context

The syntactic grammar has 5 context parameters for allowing and disallowing certain constructs,
namely [In], [Return], [Yield], [Await] and [Default].

It is best to keep a context during parsing, for example in Biome:

rust
// https://github.com/rome/tools/blob/5a059c0413baf1d54436ac0c149a829f0dfd1f4d/crates/rome_js_parser/src/state.rs#L404-L425

pub(crate) struct ParsingContextFlags: u8 {
    /// Whether the parser is in a generator function like `function* a() {}`
    /// Matches the `Yield` parameter in the ECMA spec
    const IN_GENERATOR = 1 << 0;
    /// Whether the parser is inside a function
    const IN_FUNCTION = 1 << 1;
    /// Whatever the parser is inside a constructor
    const IN_CONSTRUCTOR = 1 << 2;

    /// Is async allowed in this context. Either because it's an async function or top level await is supported.
    /// Equivalent to the `Async` generator in the ECMA spec
    const IN_ASYNC = 1 << 3;

    /// Whether the parser is parsing a top-level statement (not inside a class, function, parameter) or not
    const TOP_LEVEL = 1 << 4;

    /// Whether the parser is in an iteration or switch statement and
    /// `break` is allowed.
    const BREAK_ALLOWED = 1 << 5;

    /// Whether the parser is in an iteration statement and `continue` is allowed.
    const CONTINUE_ALLOWED = 1 << 6;

And toggle and check these flags accordingly by following the grammar.

AssignmentPattern vs BindingPattern

In estree, the left-hand side of an AssignmentExpression is a Pattern:

text
extend interface AssignmentExpression {
    left: Pattern;
}

and the left-hand side of a VariableDeclarator is a Pattern:

text
interface VariableDeclarator <: Node {
    type: "VariableDeclarator";
    id: Pattern;
    init: Expression | null;
}

A Pattern can be a Identifier, ObjectPattern, ArrayPattern:

text
interface Identifier <: Expression, Pattern {
    type: "Identifier";
    name: string;
}

interface ObjectPattern <: Pattern {
    type: "ObjectPattern";
    properties: [ AssignmentProperty ];
}

interface ArrayPattern <: Pattern {
    type: "ArrayPattern";
    elements: [ Pattern | null ];
}

But from the specification perspective, we have the following JavaScript:

javascript
// AssignmentExpression:
{ foo } = bar;
  ^^^ IdentifierReference
[ foo ] = bar;
  ^^^ IdentifierReference

// VariableDeclarator
var { foo } = bar;
      ^^^ BindingIdentifier
var [ foo ] = bar;
      ^^^ BindingIdentifier

This starts to become confusing because we now have a situation where we cannot directly distinguish whether the Identifier is a BindingIdentifier or a IdentifierReference
inside a Pattern:

rust
enum Pattern {
    Identifier, // Is this a `BindingIdentifier` or a `IdentifierReference`?
    ArrayPattern,
    ObjectPattern,
}

This will lead to all sorts of unnecessary code further down the parser pipeline.
For example, when setting up the scope for semantic analysis, we need to inspect the parents of this Identifier
to determine whether we should bind it to the scope or not.

A better solution is to fully understand the specification and decide what to do.

The grammar for AssignmentExpression and VariableDeclaration are defined as:

text
13.15 Assignment Operators

AssignmentExpression[In, Yield, Await] :
    LeftHandSideExpression[?Yield, ?Await] = AssignmentExpression[?In, ?Yield, ?Await]

13.15.5 Destructuring Assignment

In certain circumstances when processing an instance of the production
AssignmentExpression : LeftHandSideExpression = AssignmentExpression
the interpretation of LeftHandSideExpression is refined using the following grammar:

AssignmentPattern[Yield, Await] :
    ObjectAssignmentPattern[?Yield, ?Await]
    ArrayAssignmentPattern[?Yield, ?Await]
text
14.3.2 Variable Statement

VariableDeclaration[In, Yield, Await] :
    BindingIdentifier[?Yield, ?Await] Initializer[?In, ?Yield, ?Await]opt
    BindingPattern[?Yield, ?Await] Initializer[?In, ?Yield, ?Await]

The specification distinguishes this two grammar by defining them separately with an AssignmentPattern and a BindingPattern.

So in situations like this, do not be afraid to deviate from estree and define extra AST nodes for our parser:

rust
enum BindingPattern {
    BindingIdentifier,
    ObjectBindingPattern,
    ArrayBindingPattern,
}

enum AssignmentPattern {
    IdentifierReference,
    ObjectAssignmentPattern,
    ArrayAssignmentPattern,
}

I was in a super confusing state for a whole week until I finally reached enlightenment:
we need to define an AssignmentPattern node and a BindingPattern node instead of a single Pattern node.

  • estree must be correct because people have been using it for years so it cannot be wrong?
  • how are we going to cleanly distinguish the Identifiers inside the patterns without defining two separate nodes? I just cannot find where the grammar is?
  • After a whole day of navigating the specification ... the grammar for AssignmentPattern is in the 5th subsection of the main section "13.15 Assignment Operators" with the subtitle "Supplemental Syntax" ๐Ÿคฏ - this is really out of place because all grammar is defined in the main section, not like this one defined after the "Runtime Semantics" section

:::tip
The following cases are really difficult to grasp. Here be dragons.
:::

Ambiguous Grammar

Let's first think like a parser and solve the problem - given the / token, is it a division operator or the start of a regex expression?

javascript
a / b;
a / / regex /;
a /= / regex /;
/ regex / / b;
/=/ / /=/;

It is almost impossible, isn't it? Let's break these down and follow the grammar.

The first thing we need to understand is that the syntactic grammar drives the lexical grammar as stated in #sec-ecmascript-language-lexical-grammar

There are several situations where the identification of lexical input elements is sensitive to the syntactic grammar context that is consuming the input elements.

This means that the parser is responsible for telling the lexer which token to return next.
The above example indicates that the lexer needs to return either a / token or a RegExp token.
For getting the correct / or RegExp token, the specification says:

The InputElementRegExp goal symbol is used in all syntactic grammar contexts where a RegularExpressionLiteral is permitted ...
In all other contexts, InputElementDiv is used as the lexical goal symbol.

And the syntax for InputElementDiv and InputElementRegExp are

text
InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator <---------- the `/` and `/=` token
    RightBracePunctuator

InputElementRegExp ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    RightBracePunctuator
    RegularExpressionLiteral <-------- the `RegExp` token

This means whenever the grammar reaches RegularExpressionLiteral, / need to be tokenized as a RegExp token (and throw an error if it does not have a matching /).
All other cases we'll tokenize / as a slash token.

Let's walk through an example:

text
a / / regex /
^ ------------ PrimaryExpression:: IdentifierReference
  ^ ---------- MultiplicativeExpression: MultiplicativeExpression MultiplicativeOperator ExponentiationExpression
    ^^^^^^^^ - PrimaryExpression: RegularExpressionLiteral

This statement does not match any other start of Statement,
so it'll go down the ExpressionStatement route:

ExpressionStatement --> Expression --> AssignmentExpression --> ... -->
MultiplicativeExpression --> ... -->
MemberExpression --> PrimaryExpression --> IdentifierReference.

We stopped at IdentifierReference and not RegularExpressionLiteral,
the statement "In all other contexts, InputElementDiv is used as the lexical goal symbol" applies.
The first slash is a DivPunctuator token.

Since this is a DivPunctuator token,
the grammar MultiplicativeExpression: MultiplicativeExpression MultiplicativeOperator ExponentiationExpression is matched,
the right-hand side is expected to be an ExponentiationExpression.

Now we are at the second slash in a / /.
By following ExponentiationExpression,
we reach PrimaryExpression: RegularExpressionLiteral because RegularExpressionLiteral is the only matching grammar with a /:

text
RegularExpressionLiteral ::
    / RegularExpressionBody / RegularExpressionFlags

This second / will be tokenized as RegExp because
the specification states "The InputElementRegExp goal symbol is used in all syntactic grammar contexts where a RegularExpressionLiteral is permitted".

:::info
As an exercise, try and follow the grammar for /=/ / /=/.
:::

Cover Grammar

Read the V8 blog post on this topic first.

To summarize, the specification states the following three cover grammars:

CoverParenthesizedExpressionAndArrowParameterList

text
PrimaryExpression[Yield, Await] :
    CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]

When processing an instance of the production
PrimaryExpression[Yield, Await] : CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]
    the interpretation of CoverParenthesizedExpressionAndArrowParameterList is refined using the following grammar:

ParenthesizedExpression[Yield, Await] :
    ( Expression[+In, ?Yield, ?Await] )
text
ArrowFunction[In, Yield, Await] :
    ArrowParameters[?Yield, ?Await] [no LineTerminator here] => ConciseBody[?In]

ArrowParameters[Yield, Await] :
    BindingIdentifier[?Yield, ?Await]
    CoverParenthesizedExpressionAndArrowParameterList[?Yield, ?Await]

These definitions defines:

javascript
let foo = (a, b, c); // SequenceExpression
let bar = (a, b, c) => {}; // ArrowExpression
          ^^^^^^^^^ CoverParenthesizedExpressionAndArrowParameterList

A simple but cumbersome approach to solving this problem is to parse it as a Vec<Expression> first,
then write a converter function to convert it to ArrowParameters node, i.e. each individual Expression need to be converted to a BindingPattern.

It should be noted that, if we are building the scope tree within the parser,
i.e. create the scope for arrow expression during parsing,
but do not create one for a sequence expression,
it is not obvious how to do this. esbuild solved this problem by creating a temporary scope first,
and then dropping it if it is not an ArrowExpression.

This is stated in its architecture document:

This is mostly pretty straightforward except for a few places where the parser has pushed a scope and is in the middle of parsing a declaration only to discover that it's not a declaration after all. This happens in TypeScript when a function is forward-declared without a body, and in JavaScript when it's ambiguous whether a parenthesized expression is an arrow function or not until we reach the => token afterwards. This would be solved by doing three passes instead of two so we finish parsing before starting to set up scopes and declare symbols, but we're trying to do this in just two passes. So instead we call popAndDiscardScope() or popAndFlattenScope() instead of popScope() to modify the scope tree later if our assumptions turn out to be incorrect.

CoverCallExpressionAndAsyncArrowHead

text
CallExpression :
    CoverCallExpressionAndAsyncArrowHead

When processing an instance of the production
CallExpression : CoverCallExpressionAndAsyncArrowHead
the interpretation of CoverCallExpressionAndAsyncArrowHead is refined using the following grammar:

CallMemberExpression[Yield, Await] :
    MemberExpression[?Yield, ?Await] Arguments[?Yield, ?Await]
text
AsyncArrowFunction[In, Yield, Await] :
    CoverCallExpressionAndAsyncArrowHead[?Yield, ?Await] [no LineTerminator here] => AsyncConciseBody[?In]

CoverCallExpressionAndAsyncArrowHead[Yield, Await] :
    MemberExpression[?Yield, ?Await] Arguments[?Yield, ?Await]

When processing an instance of the production
AsyncArrowFunction : CoverCallExpressionAndAsyncArrowHead => AsyncConciseBody
the interpretation of CoverCallExpressionAndAsyncArrowHead is refined using the following grammar:

AsyncArrowHead :
    async [no LineTerminator here] ArrowFormalParameters[~Yield, +Await]

These definitions define:

javascript
async (a, b, c); // CallExpression
async (a, b, c) => {} // AsyncArrowFunction
^^^^^^^^^^^^^^^ CoverCallExpressionAndAsyncArrowHead

This looks strange because async is not a keyword. The first async is a function name.

CoverInitializedName

text
13.2.5 Object Initializer

ObjectLiteral[Yield, Await] :
    ...

PropertyDefinition[Yield, Await] :
    CoverInitializedName[?Yield, ?Await]

Note 3: In certain contexts, ObjectLiteral is used as a cover grammar for a more restricted secondary grammar.
The CoverInitializedName production is necessary to fully cover these secondary grammars. However, use of this production results in an early Syntax Error in normal contexts where an actual ObjectLiteral is expected.

13.2.5.1 Static Semantics: Early Errors

In addition to describing an actual object initializer the ObjectLiteral productions are also used as a cover grammar for ObjectAssignmentPattern and may be recognized as part of a CoverParenthesizedExpressionAndArrowParameterList. When ObjectLiteral appears in a context where ObjectAssignmentPattern is required the following Early Error rules are not applied. In addition, they are not applied when initially parsing a CoverParenthesizedExpressionAndArrowParameterList or CoverCallExpressionAndAsyncArrowHead.

PropertyDefinition : CoverInitializedName
    I* t is a Syntax Error if any source text is matched by this production.
text
13.15.1 Static Semantics: Early Errors

AssignmentExpression : LeftHandSideExpression = AssignmentExpression
If LeftHandSideExpression is an ObjectLiteral or an ArrayLiteral, the following Early Error rules are applied:
    * LeftHandSideExpression must cover an AssignmentPattern.

These definitions define:

javascript
({ prop = value } = {}); // ObjectAssignmentPattern
({ prop: value }); // ObjectLiteral with SyntaxError

Parsers need to parse ObjectLiteral with CoverInitializedName,
and throw the syntax error if it does not reach = for ObjectAssignmentPattern.

As an exercise, which one of the following = should throw a syntax error?

javascript
let { x = 1 } = ({ x = 1 } = { x: 1 });

File: src/docs/learn/ecmascript/spec.md

title: Specification outline: deep

Specification

The ECMAScriptยฎ Language Specification (a living standard) details everything about the JavaScript language, so anyone can implement their own JavaScript engine.

The following chapters need to be studied for our parser:

  • Chapter 5: Notational Conventions
  • Chapter 11: ECMAScript Language: Source Text
  • Chapter 12: ECMAScript Language: Lexical Grammar
  • Chapter 13 - 16: Expressions, Statements, Functions, Classes, Scripts and Modules
  • Annex B: Additional ECMAScript Features for Web Browsers
  • Annex C: The Strict Mode of ECMAScript

For navigation inside the specification:

  • Anything clickable has a permanent link, they are shown on the URL as anchors, for example #sec-identifiers
  • Hovering over things may show a tooltip, clicking on References shows all its references

Notational Conventions

Chapter 5.1.5 Grammar Notation is the section we need to read.

The things to note here are:

Recursion

This is how lists are presented in the grammar.

text
ArgumentList :
  AssignmentExpression
  ArgumentList , AssignmentExpression

means

javascript
a, b = 1, c = 2
^_____________^ ArgumentList
   ^__________^ ArgumentList, AssignmentExpression,
          ^___^ AssignmentExpression

Optional

The _opt_ suffix for optional syntax. For example,

text
VariableDeclaration :
  BindingIdentifier Initializer_opt

means

javascript
var binding_identifier;
var binding_identifier = Initializer;
                       ______________ Initializer_opt

Parameters

The [Return] and [In] are parameters of the grammar.

For example

text
ScriptBody :
    StatementList[~Yield, ~Await, ~Return]

means top-level yield, await and return are not allowed in scripts, but

text
ModuleItem :
  ImportDeclaration
  ExportDeclaration
  StatementListItem[~Yield, +Await, ~Return]

allows for top-level await.

Source Text

Chapter 11.2 Types of Source Code tells us that
there is a huge distinction between script code and module code.
And there is a use strict mode that makes the grammar saner by disallowing old JavaScript behaviors.

Script Code is not strict, use strict need to be inserted at the top of the file to make script code strict.
In HTML we write <script src="javascript.js"></script>.

Module Code is automatically strict.
In HTML we write <script type="module" src="main.mjs"></script>.

ECMAScript Language: Lexical Grammar

For more in-depth explanation, read the V8 blog on Understanding the ECMAScript spec.

[Automatic Semicolon Insertion](https://tc39.es/ecma262/#sec-automatic-semicolon-insertion)

This section describes all the rules where we can omit a semicolon while writing JavaScript.
All the explanation boils down to

rust
pub fn asi(&mut self) -> Result<()> {
        if self.eat(Kind::Semicolon) || self.can_insert_semicolon() {
            return Ok(());
        }
        let range = self.prev_node_end..self.cur_token().start;
        Err(SyntaxError::AutoSemicolonInsertion(range.into()))
    }

    pub const fn can_insert_semicolon(&self) -> bool {
        self.cur_token().is_on_new_line || matches!(self.cur_kind(), Kind::RCurly | Kind::Eof)
    }

The asi function need to be manually called where applicable, for example in the end of statement:

rust
fn parse_debugger_statement(&mut self) -> Result<Statement<'a>> {
    let node = self.start_node();
    self.expect(Kind::Debugger)?;
    self.asi()?; // [!code highlight]
    self.ast.debugger_statement(self.finish_node(node))
}

:::info

This section on asi is written with a parser in mind,
it explicitly states that the source text is parsed from left to right,
which makes it almost impossible to write the parser in any other way.
The author of jsparagus made a rant about this here.

The specification for this feature is both very-high-level and weirdly procedural (โ€œWhen, as the source text is parsed from left to right, a token is encountered...โ€, as if the specification is telling a story about a browser. As far as I know, this is the only place in the spec where anything is assumed or implied about the internal implementation details of parsing.) But it would be hard to specify ASI any other way.

:::

Expressions, Statements, Functions, Classes, Scripts and Modules

It takes a while to understand the syntactic grammar, then apply them to writing a parser.

File: src/docs/learn/architecture/ast-tools.md

title: AST Tools outline: deep

AST Tools

The AST Tools task serves as our secret weapon for managing all generated files.
These tools include the AST builder, visitors, traits like ContentEq and ContentHash, and TypeScript types - all of which are machine-generated.

For instance, the following files are automatically generated:

  • crates/oxc_ast/src/generated/ast_builder.rs
  • crates/oxc_ast/src/generated/visit.rs
  • crates/oxc_ast/src/generated/visit_mut.rs
  • crates/oxc_ast/src/generated/derive_content_eq.rs
  • crates/oxc_ast/src/generated/derive_content_hash.rs
  • npm/oxc-types/src/generated/types.d.ts

Background

Rust's compile time is notoriously slow, and using procedural macros to generate this much code worsens the issue.

Requiring users to wait for code generation to complete at build time would significantly hinder the development experience for downstream projects.

Both cold and incremental build times can regress drastically.

The RFC

The team discussed the topic in RFC: codegen AST related codes and agreed on the following requirements and user story:

Requirements

  • No build.rs published to the user.
  • All generated code are checked into git.
  • No nightly.
  • Rust code is source of truth, need to parse types marked #[ast].
  • Avoid compile-time procedural macros as much as possible.

Workflow

  • A user changes code in repo.
  • A watch change picks it up.
  • Parse all types marked #[ast].
  • Record details of all AST types in a schema.
  • Generate code from schema and save to files.

Infrastructure

More details to follow.

Explore Related Technologies & Topics

View All 9,111+ Repositories โ†’

Discover similar high-velocity repositories, agent skills, and OpenAPI specifications across the ecosystem.

โšก MCP Servers Model Context Protocol โ†’ ๐Ÿง  Agent Skills Prompt & rule files โ†’ ๐Ÿ”Œ OpenAPI Specs REST & Swagger schemas โ†’