Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Difftastic: Syntax-aware structured diff tool

github.com

Post reply on HN
Print view View original

51–60 of 62 posts

Re: Difftastic: Syntax-aware structured diff tool

#51

Post by Wilfred »

vcmiraldo wrote: post #29

That is a really difficult problem for more reasons than what fits in this comment :) In fact, I got my PhD studying this very problem ( https://victorcmiraldo.github.io/data/MiraldoPhD.pdf ). I did not find any description of how your diffing algorithm works nor how you represent a patch. I'd be really curious to know more.

Wow, thank you for the pointer! I've added it to https://github.com/Wilfred/difftastic/wiki/Structural-Diffs as I'm trying to understand the other solutions in this space.

Difftastic does not create a patch or worry about merging. That's a hard problem that I'm not trying to solve. Instead, it builds two ASTs, then marks each node as unchanged or novel.

To compute the diff, I use a graph search. Each vertex represents a position in both the left and right ASTs.

Suppose you're comparing A with X A.

Start node:

  Left: A   Right: X A
        ^          ^
The possible next nodes are:

(1) Treat A on the left as novel.

  Left: A   Right: X A
         ^         ^
(2) Treat X on the right as novel.

  Left: A   Right: X A
        ^            ^
Both (1) and (2) are the same 'distance', but (2) is closer to the end node, because there's a edge from (2) to the end that marks A as unchanged.

I've implemented this using Dijkstra's algorithm. My graph is directed and acyclic, so there are faster algorithms like topological sort. However, I don't construct the whole graph in advance (that would take O(N^2) memory) so instead I construct the graph nodes as necessary.

(This is very similar to Autochrome, which I've linked in the README. Autochrome has a worked example which is really helpful.)

At some point I think I'll have to use A* search instead. If there are more than 500 lines of code with lots of changes, difftastic can take a few seconds to terminate due to the naive graph search.

Re: Difftastic: Syntax-aware structured diff tool

#52

Post by Wilfred »

runeks wrote: post #49

It's a great idea, but I don't think defining the syntax of a programming language as a syntax.toml file will work for enough programming languages for this to be useful. You're basically rewriting the parser of your language in a DSL that isn't as expressive as the language the parser is written in. I think you'd need another parser/syntax interface for this to work. E.g. running a binary that you can submit source…

Yeah, so it's basically a lexer with an extremely simplistic parser.

Compiler parsers aren't a great fit for difftastic. They discard comments, they may not give you output if there are syntax errors, and they're usually tied to a specific language version.

Since this format works well for Comby (Rijnard's talk is excellent: https://www.youtube.com/watch?v=JMZLBB_BFNg ) I'm hopeful it's an adequate solution for Difftastic.

It will also users to add their own custom syntax/config formats.

That said, using tree-sitter might be an option. It's more forgiving than compiler parsers.

Re: Difftastic: Syntax-aware structured diff tool

#53

Post by Wilfred »

vcmiraldo wrote: post #35
dan-robertson wrote: post #31

Earlier quoted context omitted.

I think the diffing is the “obvious” graph search algorithm between trees, where a “tree” is a list of atoms or trees (think lisp lists). Basically to diff a tree of n top-level elements against one of m elements, construct a graph where nodes lie on an (n+1)x(m+1) grid. Each node (a,b) corresponds to having looked at a elements of the first and matched them to b elements of the second list. Add edges (a,b)->(a+1,b)…

From you description it seems like we're just computing the standard insert-delete tree-edit-distance. These tend to be slow. This implies that the patch language only supports insertion, deletion and modification of nodes, which is a shame since refactorings, moves and duplications are also common operations in the source-code domain. Additionally, if the patch language only supports insertion, deletion and modifica…

Yep, that's a fair description. Note that I'm not providing a merge algorithm, just a pretty way of viewing changes.

I did look at modelling moves in an earlier prototype, but it's incredibly hard to display the result in a coherent way when there are also insertions. It was also easier to drop it when I moved to Dijkstra.

As you can see in the screenshot in the readme, it does support inserting tree nodes whilst preserving children, which covers a ton of cases.

Re: Difftastic: Syntax-aware structured diff tool

#54

Post by mikepurvis »

Wilfred wrote: post #48
mikepurvis wrote: post #40

I'd feel so much more motivation for checking out alternative diff tools if there was a better story for integrating them with the review tools in Github, GitLab, etc. I know there's nothing anyone can do about that— it's something the Git hosts themselves have to enable, or I have to see enough benefit in it to go to an dedicated review tool to make the bother of that worthwhile. I believe Gerrit has a pluggable dif…

Definitely! I still look at diffs in the terminal pretty often, but all my code reviews are in rendered HTML. That said, there needs to be a credible tool before review tools can adopt it! GitHub does a line-based diff with word-based highlighting, which is probably the best you can do without syntactic smarts.

It would be neat if there was a way to supply a "diff hint" or something right in your git commit metadata. Obviously the receiver/reviewer/renderer can ultimately do whatever they want, but it would helpful if I as the one preparing the change could at least specify intent.

I guess projects like the kernel where the review system is built around emailed patches kind of already get this for free— once committed, the change will be rendered according to the local user's git settings, but during the review itself, it will be a diff prepared by the change's author that will be under discussion.

In a glorious future where GitLab has four different diff options, it would be great if I could specify that I want it to default to the hinted diff tool, falling back to my preferred one if there is no hint.

Re: Difftastic: Syntax-aware structured diff tool

#55

Post by dan-robertson »

Wilfred wrote: post #46
dan-robertson wrote: post #33

I personally am much more excited by “sliders” than the structure-aware diffs. Marking additions between [], it is the difference between e.g. handle_case [some new case over multiple lines handle_case] some existing case [ check_invariant(); } function newFunc(){ ... ] check_invariant(); } And [handle_case some new case] handle_case old case [function newFunc(){ ... check_invariant(); }]

I agree sliders are a problem, and I hope to have a solution there. Syntactic differs already do better because they understand that parentheses/brackets are paired. Difftastic does OK with this example: https://imgur.com/a/pVlVBo5

Yeah I’m keen to see your solution.

FWIW, the formatting of the snippets I wrote above was as two separate diffs for additions with the new additions (ie green parts) represented with [square brackets].

Re: Difftastic: Syntax-aware structured diff tool

#56

Post by maw »

Wilfred wrote: post #45
davidkunz wrote: post #3

To ease the pain in conventional differs, we use a pre-commit hook to format the source code (prettier). This way we only see differences if something _actually_ changed.

A syntactic differ like Difftastic is very helpful when your codebase is autoformatted. Formatters often reflow code. Given the code: foo(one, two, three); If you add an argument and reformat: foo( one, two, new, three ); A line-based diff can make it hard to spot what's changed.

When I was still formatting code manually (... -ish; emacs did a lot of the tedious work for me) I eventually settled on a style very similar to your four-argument example, precisely because it makes diffs easier to read.

For the same reason, I asciibetically sorted things when it made sense.

Now I use prettier and black and I'm mostly satisfied by them, but their reflow behavior puts the lie to "[black] makes code review faster by producing the smallest diffs possible."

Re: Difftastic: Syntax-aware structured diff tool

#57

Post by lpapez »

TotempaaltJ wrote: post #27
Cthulhu_ wrote: post #9

Earlier quoted context omitted.

I think code formatting should be mandatory and one of the first things you adopt in your project. Resist code style rule changes as much as possible, and if you do, apply them across the whole codebase in one go to avoid churn and noise in diffs down the line. And if you do make style changes, put them in a separate commit at the very least so the diffs are cleaner and code reviews are easier. In my project I use go…

And if you do decide to do single-commit massive style changes, add the commits to an ignore revs file: http://git-scm.com/docs/git-config#Documentation/git-config....

Did not know that thing existed, super useful. Thanks a ton.

Re: Difftastic: Syntax-aware structured diff tool

#58

Post by zhengyi13 »

Wilfred wrote: post #52
runeks wrote: post #49

It's a great idea, but I don't think defining the syntax of a programming language as a syntax.toml file will work for enough programming languages for this to be useful. You're basically rewriting the parser of your language in a DSL that isn't as expressive as the language the parser is written in. I think you'd need another parser/syntax interface for this to work. E.g. running a binary that you can submit source…

Yeah, so it's basically a lexer with an extremely simplistic parser. Compiler parsers aren't a great fit for difftastic. They discard comments, they may not give you output if there are syntax errors, and they're usually tied to a specific language version. Since this format works well for Comby (Rijnard's talk is excellent: https://www.youtube.com/watch?v=JMZLBB_BFNg ) I'm hopeful it's an adequate solution for Difft…

FWIW, as soon as I saw this project, I wondered specifically about Treesitter's applicability to this problem, and I found https://github.com/afnanenayet/diffsitter.

Maybe there's something to be learned there?

Re: Difftastic: Syntax-aware structured diff tool

#59

Post by fragmede »

tlamponi wrote: post #39

Surely far from being as elaborate as the linked tool, but I use the following git command a few dozen times daily: git diff --word-diff=color --word-diff-regex='\w+' I added two aliases to my .gitconfig, one for diff and one for show: [alias] word-show = show --word-diff=color --word-diff-regex='\\w+' word-diff = diff --word-diff=color --word-diff-regex='\\w+' Those small things improved development and reviewing a…

A tiny bit of shell golf - I have similar aliased to wdiff (or even wd if you're especially parsimonious).

Re: Difftastic: Syntax-aware structured diff tool

#60

Post by vcmiraldo »

Wilfred wrote: post #51
vcmiraldo wrote: post #29

That is a really difficult problem for more reasons than what fits in this comment :) In fact, I got my PhD studying this very problem ( https://victorcmiraldo.github.io/data/MiraldoPhD.pdf ). I did not find any description of how your diffing algorithm works nor how you represent a patch. I'd be really curious to know more.

Wow, thank you for the pointer! I've added it to https://github.com/Wilfred/difftastic/wiki/Structural-Diffs as I'm trying to understand the other solutions in this space. Difftastic does not create a patch or worry about merging. That's a hard problem that I'm not trying to solve. Instead, it builds two ASTs, then marks each node as unchanged or novel. To compute the diff, I use a graph search. Each vertex represent…

Thanks for the reply Wilfred! I was not familiar with Autochrome, I will certainly have a look!

That's interesting, I like the idea of not worrying about patching nor merging, giving you a tool that is focused on "communicating the differences to a human", and indeed, it means you don't have to worry about a whole bag of problems.

One insight that I came across (more info on Chap 5 of my thesis) is that not considering or handling duplication means you incur a quadratic slowdown in your search algorithm. For example, say you're diffing `A` against `Bin A A`. If you can't understand that `A` was duplicated, which `A` do you copy? You have to evaluate both options even though it really doesn't matter which one you copy.

One good middle ground for speeding up your algorithm while not having to worry about displaying duplications is to have an intermediate step where first you diff with duplication detection, but then you just go over the result and make arbitrary choices about which duplicate to copy and which to insert/delete.

Post reply on HN