Indentation tracking

[asvarga]

I threw together a simple wrapper around cstree that adds indentation tracking: https://github.com/asvarga/cstree2d

tl;dr: It defines Syntax2D<S: Syntax> which adds Indent/Dedent/Newline tokens to a Syntax, and defines a display method that handles these indentation changes.

Would you be interested in merging it into cstree as a feature? I could polish it up and file a PR.

[domenicquirl]

Hey @asvarga, thanks for reaching out! Always happy to see people finding cstree to be helpful ☺️

I had a brief look at your project and it mostly seems to be doing what I would expect from whitespace-sensitive languages, which is to define token types for indents and dedents. That said, I'm not quite sure how your approach fits with how cstree is meant to preserve the (full) original source text of a source code file.

What it seems like you want is a way to extract the text of some subtree, such as a piece of code nested inside a doc comment, with the indentation up to its starting point and any comment markers removed, i.e., to take the subtree out of the comment and unindent it. By definition, this intentionally produces a CST that is no longer backed by the original source text and will render to a different textual representation, which seems more like something that the indoc crate you're using for the example does than what cstree does.

For example, you could just as well lex a doc comment as just a comment and then textually remove the comment markers and leading whitespace if you just want to extract the nested text. Or, you could parse the inside of the doc comment (in a special mode or with a flag to indicate semantically skipping the leading comment markers) to get a CST that contains a subtree for the code inside the doc comment, including all of the comment characters and whitespace, and extract the inner code the same way you would mutate that subtree to reflect edits, creating a new tree (or just build a new tree for the inner content entirely, with the actual amount / location of whitespace that you want).

I think the above functionality (helping people with nested parsers and/or extracting subtrees so they "stand on their own" in terms of whitespace / indentation) would be a useful direction to further experiment with and potentially upstream to cstree as additional utilities if you want to have a go. Wrt. your current implementation, I think there are a few more questions that need to be answered first (some of this is only relevant to the example, but might be useful if you're trying to parse an indentation-sensitive language), namely:

• Where do you expect indent / dedent tokens to be created (in the lexer, parser, or in between)? I usually see this as something that happens before the parser, either in the lexer or as a post-processing step on the lexer tokens, so the parser doesn't actually deal with detecting the change in indentation, only processing the previously computed tokens.
  • This matters because a vec of indent texts probably isn't the most efficient way to store the current indent level during parsing, especially since you are essentially doing the same operation again for formatting to recreate the original lines. It might be easier to have the lexer create both whitespace tokens that contain the actual whitespace characters and indent / dedent tokens that contain no text and only represent a change in indentation. At least this allows the parser and the formatting to work as-is.
  • Newlines are a little bit orthogonal to this, since you obviously need to track them to track the indentation level, but I think it should be possible to have them be their own thing in the lexer only without giving them an extra syntax kind in the CST if they are no longer required for formatting.
• How can you safely handle introducing additional tokens on top of the underlying Syntax enum? Right now, you're reserving u32::MAX and a few RawSyntaxKinds below it, but cstree doesn't currently impose any restrictions on how many kinds a user can define beyond the requirement that they need to be convertible to and from u32, so at least in theory your implementation might clash with pre-existing kinds if the original enum either has a lot of variants (maybe unlikely, but possible) or also uses the topmost IDs for some special purpose. The derive for Syntax that is included with cstree does use sequential numbering (and will check that the enum doesn't define its own discriminants here, but other implementations that don't use the macro might not.

Please feel free to continue this discussion if there's anything you think I can help you with!

[asvarga]

My intent was for supporting program transformers that maintain user formatting. For example, replacing

L += [x, y]

with

L.append(x)
L.append(y)

in

def f(L):
    L += [x, y]

should yield

def f(L):
    L.append(x)
    L.append(y)

not

def f(L):
    L.append(x)
L.append(y)

I've realized cstree might not be intended for these kinds of tree transformations though.

As for the implementation, I don't have strong opinions about how a lexer/parser would use it but I'm looking for something language agnostic. My use case uses tree-sitter to parse and then language-specific functions from tree-sitter -> CST that handle the indents.

[domenicquirl]

Hm, interesting... it is definitely intended for cstree to provide a way to edit the produced CSTs (or, well, efficiently create new trees that share nodes through SyntaxNode::replace_with). Your example reminds me of what rust-analyzer has to do when the IDE triggers an assist that edits the code: I think it's basically the same problem of making sure (all of) the inserted code is indented to the same level as the original.

Some of that happens purely textually (like indoc), e.g., here for converting block comments (/*) to line comments (//), which could already work for the example you gave depending on how you compute the substitution. However, if it doesn't, they also have a more general system for tree edits where they basically go through all of the whitespace tokens that are part of the node and replace them with new tokens that have the indentation prefix added or removed.

Doing this naively in cstree is probably not the best UX, since you need to recreate the entire tree for each replacement, but if you're already building up a new tree for the replacement including the corresponding trivia for whitespace (which doesn't need to be just spaces, it could also be Indent and Dedent tokens) is probably not that far off. Have a look at their SyntaxEditor machinery if this is of interest to you - I would be very happy to have a similar utility for edits included in the library if you come up against functionality that is not yet exposed!