Is there a good reason why diff tools generally don’t use AST?
Finally, even if you have a syntax tree, that is just part of the solution, probably the smaller one. Detecting three lines of code wrapped in a new if statement is easy but also doesn't benefit much from a syntax-aware algorithm. But once you changes names and signatures, extract methods, introduce constants, and so on it will become progressively harder to match subtrees and one is probably quickly approaching the territory of NP-hard and undecidable problems.
I've thought before this is how diffing should be done, and speculated that tree-sitter would make it more feasible.
At this point, whenever I think some language-aware tool ought to exist, my first thought is "Does the language server protocol or tree-sitter make this more feasible?"
Languages usually change slowly, though, so once a good baseline grammar is in place, maintenance is unlikely to be a huge load.
Furthermore, with tools like tree-sitter and the language server protocol, multiple communities benefit from their continued existence, so there's a bigger pool of contributors to the parser.
I very much agree. I feel there has been a trend recently where people (re)discovered how cool and useful ASTs are and now expect everything be using them. I suspect old-school computer scientists might be secretly laughing at this while programming with some Lisp-like languages they invented for themselves.
Jokes aside, I do wonder how modern IDEs manage to parse broken source code into usable ASTs --- is this trivial (CS theory-wise) or are there a lot of engineering secret sauce involved to make it work?
[1] And also harder because if you want to parse the file after each key stroke, you have to be fast. This probably also makes incremental updates to the syntax tree the preferred solution and that might align well with using prior result for error recovery.
Don't we call such heuristics "test suites"?
var foo = bar baz
var foo = barbaz
var foo = "bar baz"
var foo = { bar, baz }
var foo = bar // baz
var foo = bar
//var foo = bar baz
var foo = bar * baz
var foo = bar + baz
var foo = bar.baz
var foo = bar(baz)
var abc = 123
And you actually jumped over the hard part that requires the heuristics, how to modify the input in order to make it parse. Take a 10 kB source file and delete 10 random characters - how will you figure out which characters to put back where? With 100 possible characters, 10,000 positions to insert a character, and having to insert 10 characters, you are looking at something like 10^60 possible modifications. You are certainly not going to try them one after another, each time checking if the modified source file parses, compiles, and passes the test suite.
Not sure what this whole straw man is about. I definitely didn't suggest anything like that. Of course you can only compare two compiling versions of a source file using a test-suite-based heuristics. I thought this whole thing was about "heuristics that identify reasonable changes which fix the file" mentioned above? "Reasonable changes that DON'T fix the file" are clearly recognizable by NOT passing the test suite, just as if it was a human trying to make those changes and finding out that the change that he just did didn't in fact yield the desired results after running the test suite.
> With 100 possible characters, 10,000 positions to insert a character, and having to insert 10 characters, you are looking at something like 10^60 possible modifications.
If you're working with an AST, you're almost certainly not working with characters. That would be immensely wasteful. In fact working with an AST is pretty much the only way in which the set of changes is sufficiently reduced for almost any change to NOT be rejected outright. With character-level modifications, you're facing the problem that almost every edit will be outright rejected as early as at the stage of parsing.
class foo
{
function bar() {
function baz() { }
}
class foo
{
function bar() {
function baz() { }
}
}
Seems there's a good open market for such a lazy reason.
But why? Shouldn’t the code you push into a repository be at least syntactically correct? And even if it is not, one can simply fallback to textual diff.
> Or, if you only pick a small set of supported languages, your diff tool will not work on most files or have to fall back to a structure-agnostic algorithm.
I don’t see how it is a blocker.
(1) Parsing an arbitrary language is hard. Without tree-sitter, difftastic would probably be a lisp-only tool. You also want a parser that preserves comments.
(2) Inputs may not be syntactically well formed.
(3) Efficiently comparing trees is extremely difficult (difftastic is O(N^2) in time and memory).
(4) Displaying tree diffs is equally difficult. Alignment is particularly challenging when your 'unchanged before' and 'unchanged after' are syntactically the same, but textually different.