AST Trivia handling

[Boshen]

Topic around trivia (comment) handling.

Explanation of trivia: https://github.com/basarat/typescript-book/blob/master/docs/compiler/ast-trivia.md

Research:

esbuild

Doesn't support comments, except some non-trivial comments. https://github.com/evanw/esbuild/search?q=comments&type=issues

eslint

Uses the token list for finding comments

estree

Could not standardize comments. https://github.com/estree/estree/issues/201

tsc https://github.com/microsoft/TypeScript-Compiler-Notes/blob/main/codebase/src/compiler/scanner.md#trivia

swc

• storage: https://github.com/swc-project/swc/blob/main/crates/swc_common/src/comments.rs
• parser: https://github.com/swc-project/swc/blob/main/crates/swc_ecma_parser/src/lexer/util.rs
• printer: https://github.com/swc-project/swc/blob/main/crates/swc_ecma_codegen/src/comments.rs
• stores comments in a hashmap

pub type SingleThreadedCommentsMapInner = FxHashMap<BytePos, Vec<Comment>>;
pub type SingleThreadedCommentsMap = Rc<RefCell<SingleThreadedCommentsMapInner>>;

/// Single-threaded storage for comments.
#[derive(Debug, Clone, Default)]
pub struct SingleThreadedComments {
    leading: SingleThreadedCommentsMap,
    trailing: SingleThreadedCommentsMap,
}

[Boshen]

Option: save all trivias in a BTreeMap<usize, Trivia> keyed by span.start.
Since some comments are actually non-trvial, we should keep a reverse lookup for them? Something like

struct Trivias {
  comments: BTreeMap<u32, (CommentKind, Span)>,
  eslint_configuration_comments: BTreeMap<u32, Span>, // configuration range
  typescript_configuration_comments: ...,
}

eslint_configuration_comments are parsed from eslint-disable, eslint-enable, eslint-disable-next-line.

--

For a printer, we can keep an iterator on BTreeMap, then call peek and next appropriately while printing. But I think we need something more performant than this.

[Boshen]

Hi @MichaReiser, I've started looking into trivias for ASTs, I've done a little bit of research (See the top discussion comment), and came up with a solution for the linter.

All the existing solutions have drawbacks because they were afterthoughts, or could not change the parser.

So the good thing for me right now is to get this right from the start, and I've realized that some comments are actually non-trivial, so they should be parsed into structured data.

Now since you have the most experience around printing trivias, do you have any thoughts and recommendations around these areas?

[MichaReiser]

Thanks for pinging me. I'm closely following your excellent work.

Now since you have the most experience around printing trivias, do you have any thoughts and recommendations around these areas?

You regard me too highly. I just copied Prettier's approach :)

What do you want to use the AST and trivia for? Is the main purpose to extract the trivia, or do you want to preserve it across mutations? If so, what's the mutation API? What trivia do you want to support? Is it just comments or also new lines and whitespace (useful for formatting, how many new lines between are before or after a comment)?

I don't have good answers to these questions but I think it's important to model the ASTs according to your needs.

Your start of OXC triggered me to think about AST design again and I started to collect notes (early draft). One observation that I find interesting is that .net uses a red green tree with SyntaxNode's, SyntaxToken's, and leading and trailing trivia associated with the token. Anders Hejlsberg was the lead architect on the c# team and now works on TypeScript. I understand that TypeScript uses a more classic approach of having regular AST Nodes (sometimes extended to support invalid programs). Why is that? Is the SyntaxTrivia approach overly complicated (probably)? Is it because the AST is mainly used for TypeChecking and was less intended for refactors? It could be worth digging into TypeScript's code base to understand how their AST and trivia handling works (or should we ping Anders Hejlsberg?)

One limitation that I see of SWC's approach is that the nodes directly influence the granularity of which you can query and place comments inside of your program. Your approach (and TypeScript's?) may have the same limitation where you don't know precisely between which to tokens a comment is placed (async /* comment */ function). But whether that's relevant for you depends on your use cases.

struct Trivias {
  comments: BTreeMap<u32, (CommentKind, Span)>,
  eslint_configuration_comments: BTreeMap<u32, Span>, // configuration range
  typescript_configuration_comments: ...,
}

Do I understand correctly that the key is the start position of the comment? You can reduce the size of the hash map values by only storing the end position rather than the full span if that's the case (and re-construct the span from key and value when querying).

[Boshen]

Than you for your input on this! Your notes are extremely helpful!

I think I'll study deeper on the decisions made by dart and typescript, since these two are targeted at JavaScript - they have non-trivial comments.

As for AST mutation, I think I would go for the most basic text based approach (for the linter) instead of the "modify AST" approach. This is due to the fact oxc's AST is stuck with a lifetime notation, which makes mutation even more difficult.

[Boshen]

Option: hack it like rustfmt

https://github.com/rust-lang/rustfmt/blob/master/Contributing.md#a-quick-tour-of-rustfmt

[Boshen]

This got me thinking, why can't we save comments as AST nodes?

We are always using visitors, which are traits, we can just override the comment visiting part when it's not relevant.

In this way it'll be easier for the printer?

[Boshen]

Let's study rustfmt and gofmt in detail before making any decisions.

[Boshen]

Good read: https://github.com/dave/dst

[Boshen]

From this tsc doc https://github.com/microsoft/TypeScript-Compiler-Notes/blob/main/codebase/src/compiler/scanner.md#trivia

It seems we need to get trivia ownership correct, otherwise it'll be a disaster while doing text edit and printing.

[Boshen]

https://github.com/dotnet/roslyn/blob/main/docs/wiki/Roslyn-Overview.md#syntax-trivia

[thepassle]

Just wanted to add my 2c to this, having the comments be available on nodes is extremely valuable for static analysis of javascript, consider the following example:

This is TS compilers output, which has a jsDocfield on the VariableStatement. The @ignore tag could signal static analysis tools to ignore this variable entirely, and the @type tag gives additional information about the type of a variable.

I have a tool (written in JS) that analyzes custom elements, and we heavily rely on JSdoc during analysis, because it can completely change the way something should be interpreted, or if it should be interpreted at all.

[thepassle]

Additionally I imagine have the comments available on the node could be useful for the linter, e.g.:

// eslint-disable-next-line
while(true){}

[Boshen]

I'll tackle these problems soon:

• feat(ast,parser): parse jsdoc #168
• feat(linter): configuration comments #100

[thepassle]

Thatd be amazing!

[Boshen]

I came up with a solution to track comments on AST nodes, by only adding 4 bytes to Span:

pub struct Span {
    pub start: u32,
    pub end: u32,
    pub leading_comments_offset: Option<NonZeroU16>,
    pub trailing_comments_offset: Option<NonZeroU16>,
}

To get all leading and trailing comments, we compute

if let Some(offset) = &span.leading_comments_offset {
   let leading_comments = trivias.comments.range(span.start - offset as u32 .. span.start);
}

if let Some(offset) = &span.trailing_comments_offset {
   let trailing_comments = trivias.comments.range(span.end .. span.end + offset as u32);
}

Now the harder part is the inner comments between stuff that doesn't have nodes to attach to, for example:

async /* xxx */ function /* yyy */ foo() {}

prettier formats this to

async function /* xxx */ /* yyy */ foo() {}

Babel returns the attribute "innerComments" on the function AST, and prettier just finds a place to insert these inner comments.

I don't really like this. A research within rust fmt, and it mentions the following https://github.com/rust-lang/rustfmt/blob/master/Contributing.md#a-quick-tour-of-rustfmt:

The crufty corners of Rustfmt are where we hack around the absence of comments in the AST and try to recreate them as best we can.

Our primary tool here is to look between spans for text we've missed. For example, in a function call foo(a, b), we have spans for a and b, in this case, there is only a comma and a single space between the end of a and the start of b, so there is nothing much to do. But if we look at foo(a /* a comment */, b), then between a and b we find the comment.

I'm going to dig deeper to find a solution to these "inner comments".

[MichaReiser]

How do you guarantee that the offset is never 0? E.g

// Copyright ... 

function test() {}

Never mind: It works because the comments lay outside of the span. Interesting idea.