Diffsitter: A tree-sitter based AST difftool to get meaningful semantic diffs

cool idea!

have you thought about using the ast representation to regenerate "canonicalized" versions of the source files upon which you can then represent the diffs (and context)?

Indeed, the example seems a little underwhelming.

It does demonstrate that diffsitter can tell that `fn main() {` was not semantically changed at all, while still being able to cope with syntactically invalid code like `fn add_one {`.

But look at the following, where I've attempted to manually convert diffsitter's generated diff into a unified diff format, making it easier to understand what's going on:

    1   fn main() {
    2 -     let x = 1;
    3 - fn add_one {
    4 + }
    5 + fn addition() {
    6   }
    7 + fn add_two() {
    8   }

Look at the closing brace on line 6, which doesn't have a - or + in front of it, meaning that the diff tool has found a closing brace in the old code and one in the new code and decided that they correspond to each other. But this correspondence is not syntactically meaningful. In the old code, that closing brace belongs to `fn main`. In the new code, however, it belongs to `fn addition`, while `fn main`'s closing brace is now represented by the "inserted" closing brace on line 4!

Mixing up braces this way is a typical weakness of traditional diff tools. I'd hope that a syntax-aware diff tool could prevent such mix-ups, and instead generate a diff like:

    1   fn main() {
    2 -     let x = 1;
    3   }
    4 - fn add_one {
    5 - }
    6 + fn addition() {
    7 + }
    8 + fn add_two() {
    9 + }

Even though this diff is one line longer (while diff tools typically aim to produce the shortest possible diff), it's more semantically correct, and would be much easier to deal with if a merge conflict came into play.

Unfortunately, diffsitter does not do this, at least not in that demo. And I don't see how it would be [edit: caused by] a disconnect between how a parser parses the code and how a human parses it. The parser has the same idea of closing braces belonging to particular opening constructs as humans do.

Probably more just a function of my poor heuristics (or lack thereof), diffsitter does equality comparisons on tree sitter nodes, which can also cause weird stuff like this where text gets grouped together.

I'm redoing the diffing algo anyways, so I'll keep this in mind for the next go.

Edit: it's because I decided to split line-by-line a while back because I thought it would make the diffs easier to read (rather than squashing all of the tokens together, which is not very aesthetically pleasing), but also gives us unintuitive results like this.

I would recommend using tree-sitter, it's probably easier not to reinvent the wheel, especially when parsing something like C++. It's also really fast

the language server protocol was a great initiative, it's however very difficult to implement into editors, and the popular language servers, such as the one VScode uses for Python is closed source and only available for VScode...

To be fair, Treesitter is also very hard to use/implement into an editor. It however seem more portable as it can compile to wasm, if you could only figure out how to use it...

I think the problems with Treesitter could be solved with documentation and examples. I don't think the problems with the language server protocol can be fixed as there is too much work to make a full featured language server, so no one will be willing to maintain them.

While the language server turns the editor into a simple io-terminal, Treesitter is like: - here's a tree - you parse it. I would like there to be a middle ground, where you could for example request a list of all variables in scope in the source code on row X. Something ontop of Treesitter, or maybe Treesitter "plugins".

I am doing research into using the Language Server Protocol for applications other than editor integration. Specifically, I am looking at calculating software metrics using the LSP. My use case is definitely doable. However, the LSP is not a great general abstraction layer of source code, something like Diffsitter would probably not be possible.

Someone is working on tree-sitter for Perl too: https://github.com/ganezdragon/tree-sitter-perl

Which is supposed to be difficult, if not impossible: https://www.perlmonks.org/?node_id=663393

I suppose, though, if it's for diffs and syntax highlighting, flaws matter less.

These tools simply don’t work well on anything more complicated than S-expressions. Every time I look into this space I end up disappointed.

Short answer is that it doesn't: it lets tree-sitter do the heavy lifting to parse everything

You are correct. It is indeed possible to use dynamic programming. For more info check out [0]. OP’s project probably takes too long on nontrivial merges in its current state.

[0] https://thume.ca/2017/06/17/tree-diffing/

I've made a incremental parser, and solved it by only re-parsing the changed code block. And the diff would then be the entire branch, but you could compare the old branch with the new branch and get a more fine detailed diff. It's hard to know beforehand what will get better performance, I found that for small files < 100 LOC it was faster to re-parse the entire file.

That one (like most such tools) doesn't handle C++.

Github is also behind the library that diffsitter builds upon: https://github.com/tree-sitter/tree-sitter.

They actually dropped support for diffing and incremental parsing a few months back, when they changed up some internal structures to what they call "precise AST datatypes" (which made diffing quite tricky in the type system).

My impression (from the outside looking in) is that there weren't many people making use of those capabilities, so it wasn't a high priority feature. A bit of a shame, though -- it's a really cool tool and I enjoyed building some things on top of it. I switched to a different front-end, though, when I saw that they had removed those features and all mention of incrementality/differencing from the documentations.

I'd be happy to be wrong about this, if anyone has more up-to-date information about semantic!

Not unless you you have a git hook to ensure that every commit is run through the auto formatter, and you additionally ensure that everyone that commits to the repositories you work on have this hook installed too. And even then, many people still interact with repositories that are outside of their power to enforce such rules upon.

It could be useful if it was modified to become a great merge tool. I've been using kdiff3 as my git mergetool and its always splits my code up at the worst spots because it does not understand python.

no, because the bigger win isn't ingoring whitespacing. It's ignore refactoring changes like renaming functions

Not if they do any sort of alignment (like structs in golang)

This tool works with the author’s intended layout, a big advantage over autoformatters which destroy and replace it poorly (it’s probably an AI-complete problem).