Call for volunteers: add tree-sitter support to major modes

I've been rebuilding my own Typescript major mode on top of the tree-sitter work mentioned in this post, and so far it's been a breeze to work with. I have a git repo here which builds the `tree-sitter` emacs branch plus all external deps inside a Docker container, in case you're interested in playing with tree-sitter: https://github.com/orzechowskid/emacs-docker .

Can you please ELI5 what tree-sitter is and the benefits that it provides for major modes?

Basically a library that allows users (of the library) to do things based on the abstract syntax tree (AST) of the code. This means you get access to the actual structure of the code which opens a lot of possibilities. The "naive" way and the way most editors handle syntax highlighting is basically by string matching/regex. This works great 99% of times but can go wrong in certain edge cases. Treesitter actually parses the code and gives access to the AST which then allows for things like 100% correct syntax highlighting. It can improve other domains as well, some of those are listed in the mail: > font-lock > indentation > navigation (beginning-of-defun-function etc.) > imenu > which-func > thing-at-point

[deleted]

C++ parsers are extremely context-sensitive, so I would be interested to see if it's feasible to add one to Emacs without needing to pull in parts of GCC.

There's [treesitter-cpp](https://github.com/tree-sitter/tree-sitter-cpp) parser that works to some extent already. However, for complex language like c++, I think it would be better to use lsp's semantic highlighting instead

I've forked `tree-sitter-langs` with https://github.com/kiennq/tree-sitter-langs that can be used to convert from the current `emacs-tree-sitter` syntax to the built-in treesit's syntax. Based on https://github.com/emacs-tree-sitter/tree-sitter-langs/pull/99. If you want to try, here is `use-package` configuration: ``` elisp (use-package treesit-langs :quelpa (treesit-langs :repo "kiennq/tree-sitter-langs" :fetcher github :files ("tree-sitter-langs-build.el" "treesit-*.el" "queries") :version-type elpa) :defer t :hook ((prog-mode yaml-mode) . (lambda () (unless (bound-and-true-p polymode-mode) (let ((buf (current-buffer))) (x:defer 0 (when (buffer-live-p buf) (with-current-buffer buf (ignore-errors (treesit-hl-enable))))))))) :custom (tree-sitter-langs-grammar-dir (expand-file-name ".cache/tree-sitter/" user-emacs-directory)) (tree-sitter-langs-git-dir nil)) ```

The request asks to "add" tree-sitter support to those prog modes. Does that mean convert all those existing operations, font-lock, indent, etc to use only tree-sitter or does it mean they're asking to have two implementations of those functions, one with TS and one without? "Add" vs "Convert" seems like a key distinction.

I don't know, I guess they will offer the "old way" since tree-sitter is not as light weight as the old system **I guess**. Maybe someone who is more involved in the emacs development can answer this.

Tree-sitter provides *syntactic* features: highlighting, motion, and indentation. Language Server Protocol provides *semantic* features: completion, goto-definition, and linting. I explain it in https://youtu.be/fnaWvVQABYs. GNU is requesting rewrites of major modes such as c-mode to leverage tree-sitter's up-to-the-keystroke parse tree. On top of being premature, the directive is also the wrong and needlessly labor intensive approach. People should work on the *grammars*, not the C or elisp code, which has the added benefit of helping other tree-sitter-enabled editors like neovim. I explain it in https://youtu.be/QHlB6w8HFao.

Unwatchable & as clear as mud.

[deleted]

> Tree-sitter provides syntactic features: highlighting, motion, and indentation. tree-sitter provides a concrete syntax tree; no more, no less. what you do with it is entirely up to you. the third-party emacs-tree-sitter package provides CST manipulation tools and syntax-highlighting functionality, but those are not features intrinsic to tree-sitter itself. the `tree-sitter` emacs branch provides CST manipulation tools and syntax-highlighting functionality too, plus indentation functionality. but, again, those are not features of tree-sitter itself. > People should work on the grammars, not the C or elisp code, which has the added benefit of helping other tree-sitter-enabled editors like neovim. much of that work has already been done, since as you note tree-sitter is already being used in other IDEs. but since tree-sitter itself is just a tool to turn source code into CSTs, you still need to write code to actually do anything with those CSTs. that's what the post to emacs-devel is requesting.

Unfortunately the only edge case current emacs parsing does not work well for me also is not solvable by treesitter: c macros ( I hate them and please if treesitter solves this please correct me!). For example: ``` #if EXAMPLE if (abc) { #else if (xyz) { #endif // Do sth. } ``` Anyways I hope treesitter is more robust to this at least.

That's honestly the easy part. The tough part is figuring what to do when the AST is invalid, which it is after most keystrokes. font-lock always used per-line parsing with as little context as possible (unfortunately necessary for things like /\* comments) specifically to keep the analysis stable as you add and delete code. People didn't go into syntax highlighting thinking "we don't need no fancy parser, i got me some regexen". It's designed that way because of the difficult problem of analyzing code that is being edited, which is a common occurrence in a text editor.

It made sense to me. Someone's bits are being burned by what appears to be an Emacs-branded volcano. Cool.

This is anecdotal, but I remember one of treesitter's show-case examples, either on reddit somewhere in /r/emacs, either on the tree-sitter website, showed macro syntax highlighting, but it was for a DSL (emacs's C sources that implement the Elisp interpreter). If your use-case is similar, I think there is hope.

Can you share more on how tree-sitter solves the problem of invalid ASTs?

That volcano is supposed to be a tree. And I wonder why no one wants me on their Pictionary team.

That they believe each major mode requires bespoke tree-sitter knowledge should indicate to you GNU has missed the point of tree-sitter.

very exciting stuff, i hope this works will get new and brillant ideas as we have seen in the neovim ecosystem since they have moved ts/lsp into the core editor. related is theodor's modes https://git.sr.ht/~theo/tree-sitter-modes/tree

Add, not convert. Rest assured ;-)

what is the alternative?

> C++ parsers are extremely context-sensitive What do you mean by this? I'm trying to parse, but I lack some context...

Don't take my word for it, but I watched a couple of presentations and my [possibly incorrect] impression is that it comes from using immutable data structures. If you're familiar with Clojure at all you'll recognize the many benefits of immutable trees. They mimic mutability by adding a delta. For instance, if you wanted to remove the right half of a binary tree in an "immutable" way, you simply need to create a new root node that points to the original left child, with a nil right pointer. Compared to other purely functional approaches like creating a full copy, this is memory efficient. You get a sort of history for free. Just like Git uses the history of a tree structure to isolate new changes and reason about them, you could imagine a partial, valid AST with a code-section that is in error. This is in contrast to the entire AST being invalid. I'm basing this on the [Strange Loop 2018 talk](https://www.youtube.com/watch?v=Jes3bD6P0To). My extrapolations may be flawed.

[In every revolution there is one man with a vision](https://github.com/commercial-emacs) -- J.T. Kirk (fictional)

a link to a GitHub org and what appears to be a Star Trek quote is not really much to go on, so I might have overlooked something, but I assume you're referring to [the tree-sitter.el file here](https://github.com/commercial-emacs/commercial-emacs/blob/master/lisp/tree-sitter.el)? all I could see of relevance was a mapping of capture names to emacs faces. so when you argue for work to be done on grammars instead of on emacs itself, are you proposing to standardize the capture names in the highlights.scm file which accompanies most (but not all) tree-sitter grammars? I can think of at least three issues with that. four, if you count the fact that this approach would have to be taken for every conceivable feature one could build on top of tree-sitter. not saying it can't be done - it's all just code - but I don't think it's as clear-cut as you make it sound. and if that's not in fact your proposal, then I'd appreciate more information on what you're getting at so I can learn from what other people are thinking and building in this space.

I actually use your tsx mode as my daily driver 😆 are you making your ts mode to work with tree-sitter like that one does?

For example, a b(c); parses differently depending on whether the identifier `c` denotes a type or a variable.

<3 yep, that's the one! now that treesit and eglot are to be shipped with emacs, I'm rewriting tsx-mode.el to take advantage of them and remove a couple of external dependencies. according to the linked post, sounds like I have a month and a half to get it all together :)

C++ inherits the typedef ambiguity from C. In this example: (A) * B; Is this dereferencing the pointer variable B, and casting the result to type A? Or is it a multiplication of A and B? Here, it's the former. typedef int A; int *B; (A) *B; Here it's the latter. int A, B; (A) * B; C++ has other ambiguities. In certain situations, C++ can't distinguish between constructors or function-like casts and declarations. See the "most vexing parse": https://en.wikipedia.org/wiki/Most_vexing_parse Here's one example of this problem that I once read: this is a declaration of x, y, and z as an integer, an integer, and a constant pointer to an integer. int(x), y, *const z; // int x; int y; int *const z; However, this is an expression that casts an existing variable x to int, then sequences to (and does nothing with) the value of an existing variable y, then allocates and discards memory for one integer. int x, y; int(x), y, new int; // ((int(x)), (y), (new int)); For this one, GCC always parses it as a redeclaration, and says that it expected an unqualified-id before 'new', and then marks this as a syntax error, whereas Clang and MSVC parse it as I described. (Edit: GCC is wrong to do this: http://eel.is/c++draft/stmt.ambig). Also, I don't know the name for this, but here's an example where templates can add to the context sensitivity of parsing C++. #if 1 template <typename T> struct S { T t; }; using A = int; #else int S, A, s; #endif int main() { S < A > s; } In the first part, `S` is a template for a type, `A` is a type, and so `S<A> s` declares `s` as an instantiation of the type `S<A>`. However, if you change `#if 1` to `#if 0`, then `S`, `A`, and `s` are variable names. `S < A > s` is equivalent to `(S < A ? 1 : 0) > s`. It compares `S` to `A`, then compares `s` to the result (which is either 1 or 0).

That's fascinating. Thanks for writing this out. I always assumed that any successful programming language would need to be entirely unambiguous. Reading this feels scandalous! It looks like even a fully working type system & compiler couldn't discriminate perfectly. Is this unique to C/C++? Does this mean that reproducible compilations require the exact same versions of build tools?

C++ is infamously difficult to parse. However, most languages don't have a context free grammar. They usually have a macro system, or they have C-style casts combined with user-definable types (which produces the typedef ambiguity), or they have indentation sensitivity. These problems can sometimes be solved by implementing some sort of powerful lexer that feeds the parser the tokens, which allows the parser itself to remain context-free. For example, Python is indentation sensitive, making the language context-sensitive, and to solve this, the lexer maintains a stack of indent levels, and emits tokens representing indent levels as it pushes or pops the stack. Then, the grammar itself can remain context free. For C typedefs, the lexer can just emit different tokens depending on whether the identifier is a typedef name or some other type of identifier—although this requires the lexer to have access to the parser's symbol tables. Without typedefs, and assuming all preprocessor macros have been expanded, C can be represented by a context-free grammar. With C++, its semantics require you to intertwine parsing and semantic analysis that require more than just a powerful lexer. This is because it requires potentially unbounded tokens of lookahead to get the correct rule. The example I mentioned earlier: The parser can't know if the following code is supposed to be a declaration or a statement until after it either reaches the token after the second comma. I've commented out both paths to show where the parser is. int(x), y, /* new int; */ /* *const z; */ You can read about how Clang solves this problem by offloading that part to a module called Sema. I don't really understand it, to be honest, but I think it's interesting. https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc I've never written a parser. I just spend way too much time reading about parsing. Edit: I forgot I was on /r/emacs, rather than /r/ProgrammingLanguages. I'm glad you enjoyed my long explanations, then!

This is a very good talk, thanks for sharing!

I guarantee you that generating an AST with tree-sitter will be fast as heck and accurate compared to regex-based tokenization in elisp, at least for complicated languages (Haskell is a pretty rough one, for example). I make no guarantees that fontification will be any faster or slower as a result of using a tree-sitter AST.

What about folding? Can tree-seitter be used to improve folding (for the many names it comes in Emacs slang) Folding in emacs is wanting anyway but that's another thing

You mean collapsing sections of code? If so, yes

I don't think you really explained why CEDET never took off and cons compared to tree-sitter. Can you elaborate?

I think the sense in which it's not "lightweight" is that it's a new external dependency.