Considering lossless AST

[matklad]

Inspired by https://github.com/jgm/djot/issues/105#issuecomment-1316110154

There's such thing as a lossless syntax tree. Basically, it's a tree with the constraint that it's possible to exactly recover the input string from it, print . parse = id. We might, or might not want to use it.

Benefits of full-fidelity trees:

• this is what is needed for IDEs, especially for refactors. During an automated refactor, you want to manipulate the AST without disturbing a particular way the source code was written.
• with ASTs, there's a constant question of how detailed they should be: with a lossless tree, there's no question here, it's always maximally detailed.
• Lossless trees can be much simpler to implement. A typical AST in a statically typed language is a sprawling tree of enums, while for lossless tree each node can be a uniform tupple of (tag, start offset, end offset, children) with the invariant that range of the node is equal to disjoint uiniong of children's ranges. There's no actual data stored in the tree besides offsets, it's all recoverable from the original source

Benefits of AST:

• they more precisely describe the intended semantics of the language. Eg, an AST would store an already unescapted string for an attribute value, while a lossless tree would "store" the original, and provide an accessor function to do escaping on the fly
• they are easier to understand, as they generally compress different syntactic sugars to a single AST construct
• they are more familiar, more standard representation.

[matklad]

In Djot, building a natural lossless tree would be a bit challenging. The "range of parent is disjoint union of children" won't work for indented constructs like lists or blockquotes

>  ```
>  fn main() {
>    "hello"
>  }
>  ```

I think we can invent some reperesentation which would capture this, but it won't be trivial.

[matklad]

In general, my gut feeling that our guiding principle should be this:

• AST is AST, it's a minimal semantic reperesentation
• so, attribute values are "evaliuated", escapes elsewhere are also processed, etc
• as an exception, we do make softbreaks part of the AST, as you might want to reflect them in output, as long as they don't affect semantics of the output
• Specific shape of the AST is a part of the spec

At the same time, implementaions can provide a lossless "stream of matches" which can be used for all purposes where AST is not enough. Matches are not part of the spec, so implementations can approach the problem differently.

[chrisjsewell]

At the same time, implementaions can provide a lossless "stream of matches" which can be used for all purposes where AST is not enough.

Ha yeh, I was just about to ask why you feel this would not be sufficient

[matklad]

cc https://github.com/jgm/djot/issues/97#issuecomment-1314459791

[wooorm]

This is called a CST btw. Concrete syntax tree vs Abstract syntax tree