Comment by dan-robertson | Hacker News Reader

Comment by dan-robertson | Hacker News Reader

I like that this seems to have ways to address two common problems with tree diffs:

1. The nesting/unnesting/merging/splitting problem that many tree diff algorithms have a hard time with are handled here by allowing the diff to see insertion/deletion of delimiters. I guess one way to see it is that the tool is doing a text level diff augmented with the tree structures to calculate the cost of diffs and choose the cheapest one it can find.

2. The problem of syntax errors. I think this just depends a lot on how well tree sitter copes with syntax errors (or weird syntax that’s hard to parse or eg a committed merge conflict) but my understanding is that it is designed to cope ok with syntax errors.

I basically felt that tree diffing was not very viable because of these issues but seeing this project I think I’ve changed my mind. I guess it remains to be seen how good performance is though (maybe this isn’t good enough yet if it can sometimes be very slow).

Dealing with syntax errors in parsers is an interesting subject. To do it really well I think you “just” have to make the error into an AST node similar to the other nodes in the tree, so that you always have some kind of AST to work with.

The problem is that you want parsing to be tolerant of errors in the sense that a single syntax error doesn’t cascade to incorrect parses far away. “Just” having an error mode means your grammar is very ambiguous and so you want a parser that will stably choose “reasonable” parses, which I think is hard. (But maybe it’s harder in the abstract and easier with heuristics on indentation and suchlike)

Though, to be clear, I think you put the word in quotes because you think the problem isn’t trivial.

No, it’s not trivial and it does require thinking about your grammar before you decide to lock down your language design. A lot of languages have some pretty obvious synchronization points though, like semicolons and curly braces. If all else fails you can always read up to the next semicolon or curly brace and dump whatever you get into a syntax error node, then keep going. This is especially true if you are implementing an LSP server and so you expect to regularly see incomplete lines simply because the user hasn’t finished typing them in yet.

Ultimately what you really want is many different kinds of specialized error (and warning) nodes for different mistakes users might make. For example, in C++ the statement `auto x = 1,000,000;` is technically correct but probably not in the way the user wanted. So you put a warning node there to record that they might want to use `1'000'000` instead. If you see something like `auto x = 42\n if (y) {…`, then you might guess that there is a missing semicolon before the newline. If a speculative parse of the next line succeeds, then you put a MissingSemicolon node into the AST (instead of one saying that the “if” was unexpected), followed by whatever the speculative parse found.

Now repeat that process for five years as you polish your compiler into a sparking user–friendly gem.

tree-sitter has first class support for parsing errors as ERROR nodes in the output tree. I treat these as just another atom in the s-expression.

In practise I haven't noticed any issues yet. I suspect that difftastic doesn't see many syntax errors because users have fixed most of them by the time they run the diff. When you look at diffs of committed code you hopefully have no parse errors at all.

The tree-sitter parsers could still reject valid code I suppose. I worry slightly more about the parsers getting precedence/associativity wrong, but it would be hard to construct an example that produce identical parse trees due to incorrect precedence.

Reply on news.ycombinator.com