5 ms·

Is there a good reason why diff tools generally don’t use AST?

by LudwigNagasena 5y ago

skywal_l 5y ago
Performances is one I guess.
- db48x 5y ago
  Also there are a lot of languages out there, each with their own special and unique syntaxes.
danbruc 5y ago
Because it is much easier, you don't have to build and maintain parsers for hundreds of languages. And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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. Also not all text files even follow any useful grammar at all. 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.
- NateEag 5y ago
  This tool is built on tree-sitter (https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/), so presumably it doesn't need to maintain parsers at all. 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?"
  - danbruc 5y ago
    Someone still has to build and maintain the parsers, you are just outsourcing this. And I added a bit to my comment, I tend to believe that parsing is the easy part, but that is admittedly more a gut feeling and not based on any real knowledge of that problem space.
    - NateEag 5y ago
      That's certainly a good point. 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.
- RyEgswuCsn 5y ago
  > And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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?
  - danbruc 5y ago
    With only basic knowledge in the domain I would assume it is hard and ugly. If the file is malformed, there is almost certainly an infinite number of possible edits to make the file adhere to the grammar, hence there can not be any algorithm that just provides the one and only correct syntax tree. This in turn means that you have to come up with heuristics that identify reasonable changes which fix the file and that is probably not easy. Also, if you do this online in an IDE, the problem becomes probably easier [1] - if you have a valid file and then make it invalid by deleting an operator in the middle of some expression, you can still essentially use the syntax tree from just before the deletion. If, on the other hand, you get a malformed file, you might have a harder time. [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.
    - jhgb 5y ago
      "If the file is malformed, there is almost certainly an infinite number of possible edits to make the file adhere to the grammar, hence there can not be any algorithm that just provides the one and only correct syntax tree. This in turn means that you have to come up with heuristics that identify reasonable changes which fix the file and that is probably not easy." Don't we call such heuristics "test suites"?
      - 5y ago
- mekster 5y ago
  > Because it is much easier, you don't have to build and maintain parsers for hundreds of languages. Seems there's a good open market for such a lazy reason.
- LudwigNagasena 5y ago
  > And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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.
nanochad 5y ago
Wilfred 5y ago
It's really hard! :) (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.
eatonphil 5y ago
What happens when you have an invalid file/AST?
- Wilfred 5y ago
  tree-sitter inserts error nodes and gives you an AST for all inputs. It seems to work well in practice.

Is there a good reason why diff tools generally don’t use AST?

skywal_l 5y ago

Performances is one I guess.

db48x 5y ago
Also there are a lot of languages out there, each with their own special and unique syntaxes.

danbruc 5y ago

Because it is much easier, you don't have to build and maintain parsers for hundreds of languages. And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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. Also not all text files even follow any useful grammar at all. 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.

NateEag 5y ago
This tool is built on tree-sitter (https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/), so presumably it doesn't need to maintain parsers at all. 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?"
- danbruc 5y ago
  Someone still has to build and maintain the parsers, you are just outsourcing this. And I added a bit to my comment, I tend to believe that parsing is the easy part, but that is admittedly more a gut feeling and not based on any real knowledge of that problem space.
  - NateEag 5y ago
    That's certainly a good point. 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.
RyEgswuCsn 5y ago
> And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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?
- danbruc 5y ago
  With only basic knowledge in the domain I would assume it is hard and ugly. If the file is malformed, there is almost certainly an infinite number of possible edits to make the file adhere to the grammar, hence there can not be any algorithm that just provides the one and only correct syntax tree. This in turn means that you have to come up with heuristics that identify reasonable changes which fix the file and that is probably not easy. Also, if you do this online in an IDE, the problem becomes probably easier [1] - if you have a valid file and then make it invalid by deleting an operator in the middle of some expression, you can still essentially use the syntax tree from just before the deletion. If, on the other hand, you get a malformed file, you might have a harder time. [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.
  - jhgb 5y ago
    "If the file is malformed, there is almost certainly an infinite number of possible edits to make the file adhere to the grammar, hence there can not be any algorithm that just provides the one and only correct syntax tree. This in turn means that you have to come up with heuristics that identify reasonable changes which fix the file and that is probably not easy." Don't we call such heuristics "test suites"?
    - 5y ago
mekster 5y ago
> Because it is much easier, you don't have to build and maintain parsers for hundreds of languages. Seems there's a good open market for such a lazy reason.
LudwigNagasena 5y ago
> And you don't need need just any parser, you need very robust ones that can deal with malformed files well. 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.

nanochad 5y ago

Wilfred 5y ago

It's really hard! :) (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.

eatonphil 5y ago

What happens when you have an invalid file/AST?

Wilfred 5y ago
tree-sitter inserts error nodes and gives you an AST for all inputs. It seems to work well in practice.