9 ms·

Difftastic, the fantastic diff

698 points by goranmoomin 4y ago

trishume 4y ago
This is a really cool example of tree diffing via path finding. I noticed that this was the approach I used when I did tree diffing, and sure enough looks like this was inspired by autochrome which was inspired by my post (https://thume.ca/2017/06/17/tree-diffing/ https://thume.ca/2017/06/17/tree-diffing/). I'm curious exactly why A* failed here. It worked great for me, as long as you design a good heuristic. I imagine it might have been complicated to design a good heuristic with an expanded move set. I see autochrome had to abandon A* and has an explanation of why, but that explanation shouldn't apply to difftastic I think.
- dan-robertson 4y ago
  I think (maybe I’m wrong) that your graph searches correspond to diffing single lists and you can have an expensive diagonal step to recurse into two sublists whereas the tool in this post has extra nodes for every token and extra edges for inserting/deleting delimiters. That seems to be the biggest difference to me and I guess is what you mean by it being complicated to design a good heuristic for the expanded move set. I agree it sounds complicated. I think that my guess was that bigger graphs would make things harder but that isn’t a reason for A* to fail.
mfrw 4y ago
Although, I do not have much to add; using `difftastic`[0] & `delta` [1] is a very cool combo to make _git_ a little more approachable for newbies like me. I use delta as my daily driver but sometimes when I want the contextual info, switching to `env GIT_EXTERNAL_DIFF=difft git log -p --ext-diff` gives a better picture. [0]: https://github.com/Wilfred/difftastic https://github.com/Wilfred/difftastic [1]: https://github.com/dandavison/delta https://github.com/dandavison/delta
- lapser 4y ago
  I've been using delta for a long while, but this is the first time I've heard of difftastic. Why wouldn't you want the context all the time?
  - mfrw 4y ago
    I feel the visual eye-candy provided by delta far more appealing than what difft does. Also, delta is much more configurable and has nice binding for moving through hunks. That's probably the only reason, otherwise, you are correct. I would want the context always.
  - WakiMiko 4y ago
    difftastic doesn't show whitespace or formatting changes
yosito 4y ago
This makes sense to me on a high level, but I would love to see more practical examples so I can quickly wrap my head around use cases without having to download and use the tool first.
siraben 4y ago
Since this is built on top of tree-sitter, it can be extended[0] to work with other languages as well, no matter how obscure, as long as a tree-sitter grammar exists. This IMO really highlights the power of having an ecosystem built around tools like tree-sitter because they allow for powerful dev UX tools to be more democratized. Excellent syntax highlighting, error recovery, linting, now tree-sensitive diffing can be provided to languages big and small. [0] https://difftastic.wilfred.me.uk/adding_a_parser.html https://difftastic.wilfred.me.uk/adding_a_parser.html
- titaniczero 4y ago
  My neovim is drooling over this! > This IMO really highlights the power of having an ecosystem built around tools like tree-sitter because they allow for powerful dev UX tools to be more democratized LSP is also an example of this and it is also an example of how dangerous it can be when these tools are backed by big companies: https://news.ycombinator.com/item?id=31760684 https://news.ycombinator.com/item?id=31760684
  - chii 4y ago
    Why is it dangerous? If microsoft, tomorrow, pulled the plug on the pylance LSP and removed all access, and the only thing left is the opensource version, the world is still at a better position than if they hadn't invested any money or opensourced anything. This is strictly different from google owning chrome, because with that ownership, they have the ability to dictate protocols for the web. The LSP is a protocol, which now is quite widespread, and will continue to survive and be enhanced, regardless of microsoft's involvement or not. The fact that they can choose to make some language servers close-sourced sucks, but being able to access a closed source component is _still_ strictly better than having zero access in the first place.
    - titaniczero 4y ago
      Embrace, extend, and extinguish [1]. This is the extend phase. Microsoft has the resources and ability to make better language servers which could be closed source now, so people end up switching to those tools, owned by Microsoft, with better language servers, killing other editors if they are not able to catch up. E.g.: Why would a C# programmer use Neovim if the language server is worse than the one that VSCode has? (Which is now proprietary and closed-source). The difference right now is insignificant, but the future tools and features that they are adding to the new proprietary C# language server will not be available for other editors. [1] https://en.wikipedia.org/wiki/Embrace,_extend,_and_extinguish https://en.wikipedia.org/wiki/Embrace,_extend,_and_extinguis...
idiocratic 4y ago
Great article. It’s inspiring to see what applications some simple algorithms can have. Kudos for building the tool and sharing your approach.
Gehinnn 4y ago
It would be so cool if there was a json output, so that other tools (eg VS Code) can use this diffing algorithm! Thanks for explaining the algorithm!
- ChadNauseam 4y ago
  It’s a bit out of date but my fork adds this functionality https://github.com/anchpop/difftastic https://github.com/anchpop/difftastic
X-Cubed 4y ago
SemanticMerge is an existing commercial product that works in a similar fashion. I've found it much nicer to use than text-based diff tools. https://www.plasticscm.com/semanticmerge/documentation/intro-guide/semanticmerge-intro-guide https://www.plasticscm.com/semanticmerge/documentation/intro...
- ziftface 4y ago
  It looks like difftastic can support way more languages. I haven't used semantic merge (or even heard about it before this) so idk if its language support is somehow better though.
- radicalbyte 4y ago
  One of the better merge tools but I'd only recommend it if your language of choice is supported. Otherwise, BeyondCompare is just as good.
  - soperj 4y ago
    I like BeyondCompare, as a free option, I really like Meld, it's similar.
janaagaard 4y ago
Is this something you can turn on be default for Git when working with others that don’t use Difftastic, or could that lead to some weird behaviors? (I don’t know enough about the internals of Git to answer this myself.)
- Sander_Marechal 4y ago
  IIRC the configurable diff tool is just to show diffs to the user, not for internal storage. So everyone on your project can use a different diff tool without problems.
- mfrw 4y ago
  An analogy would be like of the editor. Think of this tool as the editor that one uses. It does not matter to git what editor one uses; similarly, it does not matter what diff pager one uses :) Yes, you can turn it on without having any side-effects for others.
- tuetuopay 4y ago
  You can turn it on safely. Git does not store diffs (like a diff chain), but a snapshot of the files at each commit
- Wilfred 4y ago
  You can use difftastic as your default git diff tool, but you can also use it as an opt-in diffing tool. I recommend using it as an opt-in, but defining a git alias so you can do 'git difft'. https://difftastic.wilfred.me.uk/git.html https://difftastic.wilfred.me.uk/git.html has docs.
jbverschoor 4y ago
Nice! Will def check it out. What I don’t understand is why it sees “value”->target as a diff. Also inside the if statement, target was semantically unchanged
- nneonneo 4y ago
  The simple answer is that renaming a variable (or function parameter) is a semantic change - even if it doesn’t, say, change the compiled code, it affects how a human would read and understand the code. Plus, in many languages, function parameter names are indeed semantically meaningful and can be accessed via features like reflection or keyword arguments.
  - Wilfred 4y ago
    Yep, that's correct. Difftastic is only a syntactic analysis, although it often makes the semantic intent clearer.
bifftastic 4y ago
I like the name
mfbx9da4 4y ago
I would love to use this but I can't be bothered to save the text to a file every time. I always paste into https://www.diffnow.com/compare-clips https://www.diffnow.com/compare-clips or http://incaseofstairs.com/jsdiff/ http://incaseofstairs.com/jsdiff/ Does anybody know any better alternatives which work with pasting?
- coremoff 4y ago
  it's not free, but Beyond Compare 4 has a clipboard comparison tool you can install as a task-bar icon in windows (I think that also works in linux, but IIRC it's harder to setup - been a while)
- Kolja 4y ago
  Not sure if I understand correctly, but wouldn't one of the two "operands" need to be a file in any case (the linked tools would require you to paste two times as well)? In that case, assuming that one file is OK and only the other text needs to be pasted, you can diff against stdin. On macOS there is `pbpaste`, which prints the contents of the pasteboard to stdout. This allows you to do `pbpaste | diff the-file -`, with `-` being the commonly used "filename" for stdin.
  - mfbx9da4 4y ago
    Na one file is not okay. I have clipboard history.
- tom_ 4y ago
  I also work this way a lot; in fact, it's probably the majority of my non-VCS-related diff tool use at work. It's very common for me to have data only on the clipboard: watch window output, TTY output, similar-looking snippets posted in Slack, that sort of thing. I use Araxis Merge at work, and Meld at home, both of which can work this way. (Araxis is much better, but I can't justify the cost personally. Meld is fine, just a bit slow.)
- mijoharas 4y ago
  in emacs you can compare buffers (emacs terminology for windows or tabs) without saving them.
robin_reala 4y ago
Fun fact: I thought of diffing programs as working out what has changed. The goal of diffing is actually to work out what hasn’t changed! +1 insightful
vincentdm 4y ago
I see some Clojure examples in the article. We use Clojure almost exclusively and this would be a great replacement for line-based Git diffs, providing much more insight in actual changes. Is there any chance such an alternative differ could be used in Git (and adjacent tools like GitLab), or are we stuck with line-based forever?
- Vinnl 4y ago
  The author mentions they're using it with Git and Mercurial. There are docs here: https://difftastic.wilfred.me.uk/git.html https://difftastic.wilfred.me.uk/git.html
AndrewDucker 4y ago
For the semantic side of things, could an LSP server be used? Building diffs on top of that would be very handy.
- sanxiyn 4y ago
  Not really. This needs a parser that produces a tree, and LSP does not provide that.
luke-stanley 4y ago
This post reminded me of the Trail Of Bits post about Graphtage: https://blog.trailofbits.com/2020/08/28/graphtage/ https://blog.trailofbits.com/2020/08/28/graphtage/ Graphtage is written in Python and can be used as a library. But it seems Difftastic can be used as a git diff tool directly.
whoomp12342 4y ago
no wandows installation :-(
- detaro 4y ago
  there are windows releases
  - whoomp12342 4y ago
    is there an installer? my understanding was that you would have to compile the source code.
rossmohax 4y ago
Next step is to make an editor where we type/edit AST, not text.
- leloctai 4y ago
  Have you heard about our Lord and savior S-expression?
  - rossmohax 4y ago
    That's for Lisp only, I am talking about generic editor for any language with structure.
- jstimpfle 4y ago
  AST is first and foremost a representation of a parse, i.e. it shows how a serialized representation of _something_ was understood by the machine. Due to this constraint, it is unlikely to be the most convenient way for a human to input that something. Take arithmetic expressions, for example. The usual infix syntax as edited in a conventional text editor is very good, probably the best option that humans have for editing arithmetic expressions. Having to edit an AST structure explicitly would almost certainly be a loss in terms of convenience and productivity. Or take a (raster or vector) image editor. They provide interfaces to editing image data in a much more convenient way than editing AST or other internal representations directly.
grogers 4y ago
My dream would be to have a three-way merge tool that worked like this at a semantic level. It feels like merges almost always have the information needed to automatically resolve, but our line-based tools are too simple to see it.
- werdnapk 4y ago
  I used to use Araxis Merge [1] years ago and found it worked very well. [1] https://www.araxis.com/merge/index.en https://www.araxis.com/merge/index.en
  - swozey 4y ago
    Geez, I've been looking at diff programs and the personal licenses for them are so expensive. I get they're incredibly useful when you need them but I personally don't need a 3rd party differ very often. Kaleidoscope is $250ish IIRC. The VSCode extension "Diff & Merge" give you the right/left arrows to merge lines if anyone is looking for a tool that does that. I haven't needed another one since I found that.
    - activitypea 4y ago
      Sublime Merge was pretty alright, don't know if it's still around
      - nammi 4y ago
        It's still around and getting periodic updates. I originally bought it mainly to give Sublime more money (after using the Sublime Text trial for most of college), but it ended up being useful and I use it daily https://www.sublimemerge.com/download https://www.sublimemerge.com/download
    - jereees 4y ago
      This is now supported without extensions in latest vscode
- 4y ago
jesse__ 4y ago
That's a diffing fantastic blog post, thanks for writing it! Not to mention the actual tool ;) I'll definitely be trying it out
bqmjjx0kac 4y ago
I got lost on the last example: `(foo (bar))` -> `(foo (novel) (bar))`. The diff that adds `novel` and a pair of parentheses seemed impossible -- wouldn't you also have to delete and re-add `bar`? Writing this comment it occurs to me that the structural diff doesn't translate to plaintext very well, and thus is not accessible to folks with red-green colorblindness.
- layer8 4y ago
  I think that example is an error. What they possibly meant was you can perform the change by inserting “novel) (”, which may structurally translate to inserting “novel” in the bar list and then splitting that list. Advanced diff tools usually allow configuring the colors, so that if the red/green is a problem, you can change it to red/blue or blue/yellow or whatever.
  - eyelidlessness 4y ago
    I don’t think it was an error, given how the article describes its handling of delimiters. In the example: (foo (bar)) (foo (novel) (bar)) The balanced parentheses around bar “haven’t changed”, but the symbol between them “has”, and the balanced parentheses around bar were “added”. It’s a perfectly valid diff given the approach, even if it’s not ideal, as the author found. The only way you could arrive at “novel) (” given the algorithm, I think, would be something like (foo (bar)) (foo novel) ((bar)) (This might be off too, hard to write code on mobile)
- Wilfred 4y ago
  Thanks for the feedback! I'll look to clarify the wording here. The failed example was a real output that difftastic gave in early versions. I agree that the classic red/green colour scheme of diffs isn't great for colourblind users. I've asked a few colourblind developers and they were happy with terminal ANSI colours (which is what difftastic uses), because they can configure each colour individually.
pabs3 4y ago
Reminds me of the token-based git authorship tool, cregit: https://github.com/cregit/cregit https://github.com/cregit/cregit https://lwn.net/Articles/698425/ https://lwn.net/Articles/698425/ https://www.youtube.com/watch?v=iXZV5uAYMJI https://www.youtube.com/watch?v=iXZV5uAYMJI
pabs3 4y ago
On cool diff tools, diffoscope is my favourite: https://diffoscope.org/ https://diffoscope.org/
- bityard 4y ago
  This looked interesting and I was going to try it out but installing it via `apt` would have pulled in 3 GB of dependencies!
  - pabs3 4y ago
    Try the diffoscope-minimal variant and disable recommends when installing. You'll lose support for a lot of different formats. You can also try it online using the service instead of locally: https://try.diffoscope.org/ https://try.diffoscope.org/
ziml77 4y ago
Smarter diffs are great, but what is especially nice is smarter merges. I would love to see this extended to be able to do the same kinds of auto-merges that SemanticMerge could. I would pay for that functionality (just like I paid for SemanticMerge for years before they took it away to instead entice people to pay for their stupid VCS).
- Gehinnn 4y ago
  Semantic merge is no longer available? :(
  - ziml77 4y ago
    Nope. They integrated the functionality with Plastic SCM. And what's especially annoying is that they don't even grandfather existing customers into being able to continue using SemanticMerge. Once your current license expires, that's it, no more SemanticMerge.
    - Gehinnn 4y ago
      Is there an existing open source effort to recreate that tool? Are the algorithms open? Does the tool work reliably? I find it very sad that potentially revolutionary progress is lost like this...
prirun 4y ago
A friend (Hi Jeff!) wrote DiffMerge: https://sourcegear.com/diffmerge https://sourcegear.com/diffmerge - another alternative diff & merge.
- emsixteen 4y ago
  I use this occasionally on Mac, and it's pretty handy. Crashes/throws an error when closing though.
_dain_ 4y ago
This article loses me when it gets to the "calculating the diff" section. >Autochrome and difftastic represent diffing as a shortest path problem on a directed acyclic graph. A vertex represents a pair of positions: the position in the left-hand side s-expression (before), and the position in the right-hand side s-expression (after). >The goal is to find the shortest route from the start vertex (where both positions are before the first item in the programs) to the end vertex (where both positions are after the last item in the program). I don't understand what this means at all? What is a "position" here? Position of what? If it's a graph, what do the edges represent? The diagrams afterwards aren't very helpful either, I can't make head nor tail of them. They talk about a "start" vertex and an "end" vertex, but before that it said that a vertex is a pair of start-end positions ... I'm totally lost.
- Wilfred 4y ago
  Thanks for the feedback. This is really hard to explain. Autochrome has a brilliant worked example https://fazzone.github.io/autochrome.html https://fazzone.github.io/autochrome.html and it still took me several readings before it clicked. Every graph vertex represents a pair of pointers (or positions) to AST nodes. So in the example, the start program is `A` and the end program is `X A`. The positions point to AST nodes in these programs. I try to use 'vertex' consistently for graph vertices, to avoid confusion with AST/s-expression nodes. If you have any suggestions for better terminology I'd be very interested too :)
dan-robertson 4y ago
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).
- db48x 4y ago
  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.
  - dan-robertson 4y ago
    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.
    - db48x 4y ago
      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.
yboris 4y ago
My favorite diff tool is diff2html - see the diff in your browser as HTML! https://diff2html.xyz/ https://diff2html.xyz/ Install the CLI, run the command (alias diff='diff2html -s side') - I run this at least every time before committing to quickly see all I've done.
- bufferoverflow 4y ago
  What's the advantage of seeing the diff in HTML? Seems like an unnecessary extra step.
  - yboris 4y ago
    Visually easier on my eyes, easier to scroll, I can filter out `package-lock.json` file from the diff (with a command line argument). In the end it's a preference thing, not an "objectively better" thing.
  - Wilfred 4y ago
    Side-by-side diff displays work really great in a browser. You usually have more screen real estate, and you can offer a responsive UI.
yewenjie 4y ago
One more tree-sitter based diffing tool - diffsitter https://github.com/afnanenayet/diffsitter https://github.com/afnanenayet/diffsitter
billconan 4y ago
I hope this can be an API too, to support other utility tools.
buffaloPizzaBoy 4y ago
It is interesting to see the use of the A* path finding algorithm for finding optimal matchings of nodes. The approach from Chawathe et. al splits nodes from the before/after trees into chains by their label in the syntax grammar, and then runs myers’ longest common subsequence on each pair of chains. Some parameters t, f are used to have an approximate ‘equals’ method for subtrees. This iteratively builds a set of matchings between equivalent nodes from the old and new trees. Here’s the paper https://dl.acm.org/doi/10.1145/235968.233366 https://dl.acm.org/doi/10.1145/235968.233366 I’d be curious to see if this approach handles re-ordering of nodes better. The ‘fastMatch’ algorithm described above will typically miss matching cases where a node that is not order sensitive (i.e a function in a namespace can be moved somewhere else in that namespace).
- Wilfred 4y ago
  I've looked at several tree diffing papers, including Chawathe et al, but it's not always easy to assess whether their approach would suit difftastic. I know that sdiff by Arun Isaac is based on applying that paper to Scheme: https://archive.fosdem.org/2021/schedule/event/sexpressiondiff/ https://archive.fosdem.org/2021/schedule/event/sexpressiondi... , although he also reports performance challenges. Most tree diffing papers that I've seen focus on either (1) providing a minimal diff and accepting the performance cost or (2) providing a relatively minimal diff and focusing on the performance. I've generally found that you need a minimal diff to get a good result, so papers in (2) are less applicable. I've also found several cases where there are several possible minimal diffs, but there's a clear 'correct' answer from the user's perspective. Difftastic doesn't handle moves: the edit set is add, remove, or replace similar comment. If you reorder functions, it will take the largest unchanged subset. Moves are hard to model in a diffing algorithm, but they're also very hard to display coherently in the UI. I know a few code forge websites (e.g. Phabricator) show moves in a fairly comprehensible way, although they're all based on line-based diffs.

698 points by goranmoomin 4y ago

This is a really cool example of tree diffing via path finding. I noticed that this was the approach I used when I did tree diffing, and sure enough looks like this was inspired by autochrome which was inspired by my post (https://thume.ca/2017/06/17/tree-diffing/ https://thume.ca/2017/06/17/tree-diffing/). I'm curious exactly why A* failed here. It worked great for me, as long as you design a good heuristic. I imagine it might have been complicated to design a good heuristic with an expanded move set. I see autochrome had to abandon A* and has an explanation of why, but that explanation shouldn't apply to difftastic I think.

dan-robertson 4y ago
I think (maybe I’m wrong) that your graph searches correspond to diffing single lists and you can have an expensive diagonal step to recurse into two sublists whereas the tool in this post has extra nodes for every token and extra edges for inserting/deleting delimiters. That seems to be the biggest difference to me and I guess is what you mean by it being complicated to design a good heuristic for the expanded move set. I agree it sounds complicated. I think that my guess was that bigger graphs would make things harder but that isn’t a reason for A* to fail.

mfrw 4y ago

Although, I do not have much to add; using `difftastic`[0] & `delta` [1] is a very cool combo to make _git_ a little more approachable for newbies like me. I use delta as my daily driver but sometimes when I want the contextual info, switching to `env GIT_EXTERNAL_DIFF=difft git log -p --ext-diff` gives a better picture. [0]: https://github.com/Wilfred/difftastic https://github.com/Wilfred/difftastic [1]: https://github.com/dandavison/delta https://github.com/dandavison/delta

lapser 4y ago
I've been using delta for a long while, but this is the first time I've heard of difftastic. Why wouldn't you want the context all the time?
- mfrw 4y ago
  I feel the visual eye-candy provided by delta far more appealing than what difft does. Also, delta is much more configurable and has nice binding for moving through hunks. That's probably the only reason, otherwise, you are correct. I would want the context always.
- WakiMiko 4y ago
  difftastic doesn't show whitespace or formatting changes

yosito 4y ago

This makes sense to me on a high level, but I would love to see more practical examples so I can quickly wrap my head around use cases without having to download and use the tool first.

siraben 4y ago

Since this is built on top of tree-sitter, it can be extended[0] to work with other languages as well, no matter how obscure, as long as a tree-sitter grammar exists. This IMO really highlights the power of having an ecosystem built around tools like tree-sitter because they allow for powerful dev UX tools to be more democratized. Excellent syntax highlighting, error recovery, linting, now tree-sensitive diffing can be provided to languages big and small. [0] https://difftastic.wilfred.me.uk/adding_a_parser.html https://difftastic.wilfred.me.uk/adding_a_parser.html

titaniczero 4y ago
My neovim is drooling over this! > This IMO really highlights the power of having an ecosystem built around tools like tree-sitter because they allow for powerful dev UX tools to be more democratized LSP is also an example of this and it is also an example of how dangerous it can be when these tools are backed by big companies: https://news.ycombinator.com/item?id=31760684 https://news.ycombinator.com/item?id=31760684
- chii 4y ago
  Why is it dangerous? If microsoft, tomorrow, pulled the plug on the pylance LSP and removed all access, and the only thing left is the opensource version, the world is still at a better position than if they hadn't invested any money or opensourced anything. This is strictly different from google owning chrome, because with that ownership, they have the ability to dictate protocols for the web. The LSP is a protocol, which now is quite widespread, and will continue to survive and be enhanced, regardless of microsoft's involvement or not. The fact that they can choose to make some language servers close-sourced sucks, but being able to access a closed source component is _still_ strictly better than having zero access in the first place.
  - titaniczero 4y ago
    Embrace, extend, and extinguish [1]. This is the extend phase. Microsoft has the resources and ability to make better language servers which could be closed source now, so people end up switching to those tools, owned by Microsoft, with better language servers, killing other editors if they are not able to catch up. E.g.: Why would a C# programmer use Neovim if the language server is worse than the one that VSCode has? (Which is now proprietary and closed-source). The difference right now is insignificant, but the future tools and features that they are adding to the new proprietary C# language server will not be available for other editors. [1] https://en.wikipedia.org/wiki/Embrace,_extend,_and_extinguish https://en.wikipedia.org/wiki/Embrace,_extend,_and_extinguis...

idiocratic 4y ago

Great article. It’s inspiring to see what applications some simple algorithms can have. Kudos for building the tool and sharing your approach.

Gehinnn 4y ago

It would be so cool if there was a json output, so that other tools (eg VS Code) can use this diffing algorithm! Thanks for explaining the algorithm!

ChadNauseam 4y ago
It’s a bit out of date but my fork adds this functionality https://github.com/anchpop/difftastic https://github.com/anchpop/difftastic

X-Cubed 4y ago

SemanticMerge is an existing commercial product that works in a similar fashion. I've found it much nicer to use than text-based diff tools. https://www.plasticscm.com/semanticmerge/documentation/intro-guide/semanticmerge-intro-guide https://www.plasticscm.com/semanticmerge/documentation/intro...

ziftface 4y ago
It looks like difftastic can support way more languages. I haven't used semantic merge (or even heard about it before this) so idk if its language support is somehow better though.
radicalbyte 4y ago
One of the better merge tools but I'd only recommend it if your language of choice is supported. Otherwise, BeyondCompare is just as good.
- soperj 4y ago
  I like BeyondCompare, as a free option, I really like Meld, it's similar.

janaagaard 4y ago

Is this something you can turn on be default for Git when working with others that don’t use Difftastic, or could that lead to some weird behaviors? (I don’t know enough about the internals of Git to answer this myself.)

Sander_Marechal 4y ago
IIRC the configurable diff tool is just to show diffs to the user, not for internal storage. So everyone on your project can use a different diff tool without problems.
mfrw 4y ago
An analogy would be like of the editor. Think of this tool as the editor that one uses. It does not matter to git what editor one uses; similarly, it does not matter what diff pager one uses :) Yes, you can turn it on without having any side-effects for others.
tuetuopay 4y ago
You can turn it on safely. Git does not store diffs (like a diff chain), but a snapshot of the files at each commit
Wilfred 4y ago
You can use difftastic as your default git diff tool, but you can also use it as an opt-in diffing tool. I recommend using it as an opt-in, but defining a git alias so you can do 'git difft'. https://difftastic.wilfred.me.uk/git.html https://difftastic.wilfred.me.uk/git.html has docs.

jbverschoor 4y ago

Nice! Will def check it out. What I don’t understand is why it sees “value”->target as a diff. Also inside the if statement, target was semantically unchanged

nneonneo 4y ago
The simple answer is that renaming a variable (or function parameter) is a semantic change - even if it doesn’t, say, change the compiled code, it affects how a human would read and understand the code. Plus, in many languages, function parameter names are indeed semantically meaningful and can be accessed via features like reflection or keyword arguments.
- Wilfred 4y ago
  Yep, that's correct. Difftastic is only a syntactic analysis, although it often makes the semantic intent clearer.

bifftastic 4y ago

I like the name

mfbx9da4 4y ago

I would love to use this but I can't be bothered to save the text to a file every time. I always paste into https://www.diffnow.com/compare-clips https://www.diffnow.com/compare-clips or http://incaseofstairs.com/jsdiff/ http://incaseofstairs.com/jsdiff/ Does anybody know any better alternatives which work with pasting?

coremoff 4y ago
it's not free, but Beyond Compare 4 has a clipboard comparison tool you can install as a task-bar icon in windows (I think that also works in linux, but IIRC it's harder to setup - been a while)
Kolja 4y ago
Not sure if I understand correctly, but wouldn't one of the two "operands" need to be a file in any case (the linked tools would require you to paste two times as well)? In that case, assuming that one file is OK and only the other text needs to be pasted, you can diff against stdin. On macOS there is `pbpaste`, which prints the contents of the pasteboard to stdout. This allows you to do `pbpaste | diff the-file -`, with `-` being the commonly used "filename" for stdin.
- mfbx9da4 4y ago
  Na one file is not okay. I have clipboard history.
tom_ 4y ago
I also work this way a lot; in fact, it's probably the majority of my non-VCS-related diff tool use at work. It's very common for me to have data only on the clipboard: watch window output, TTY output, similar-looking snippets posted in Slack, that sort of thing. I use Araxis Merge at work, and Meld at home, both of which can work this way. (Araxis is much better, but I can't justify the cost personally. Meld is fine, just a bit slow.)
mijoharas 4y ago
in emacs you can compare buffers (emacs terminology for windows or tabs) without saving them.

robin_reala 4y ago

Fun fact: I thought of diffing programs as working out what has changed. The goal of diffing is actually to work out what hasn’t changed! +1 insightful

vincentdm 4y ago

I see some Clojure examples in the article. We use Clojure almost exclusively and this would be a great replacement for line-based Git diffs, providing much more insight in actual changes. Is there any chance such an alternative differ could be used in Git (and adjacent tools like GitLab), or are we stuck with line-based forever?

Vinnl 4y ago
The author mentions they're using it with Git and Mercurial. There are docs here: https://difftastic.wilfred.me.uk/git.html https://difftastic.wilfred.me.uk/git.html

AndrewDucker 4y ago

For the semantic side of things, could an LSP server be used? Building diffs on top of that would be very handy.

sanxiyn 4y ago
Not really. This needs a parser that produces a tree, and LSP does not provide that.

luke-stanley 4y ago

This post reminded me of the Trail Of Bits post about Graphtage: https://blog.trailofbits.com/2020/08/28/graphtage/ https://blog.trailofbits.com/2020/08/28/graphtage/ Graphtage is written in Python and can be used as a library. But it seems Difftastic can be used as a git diff tool directly.

whoomp12342 4y ago

no wandows installation :-(

detaro 4y ago
there are windows releases
- whoomp12342 4y ago
  is there an installer? my understanding was that you would have to compile the source code.

rossmohax 4y ago

Next step is to make an editor where we type/edit AST, not text.

leloctai 4y ago
Have you heard about our Lord and savior S-expression?
- rossmohax 4y ago
  That's for Lisp only, I am talking about generic editor for any language with structure.
jstimpfle 4y ago
AST is first and foremost a representation of a parse, i.e. it shows how a serialized representation of _something_ was understood by the machine. Due to this constraint, it is unlikely to be the most convenient way for a human to input that something. Take arithmetic expressions, for example. The usual infix syntax as edited in a conventional text editor is very good, probably the best option that humans have for editing arithmetic expressions. Having to edit an AST structure explicitly would almost certainly be a loss in terms of convenience and productivity. Or take a (raster or vector) image editor. They provide interfaces to editing image data in a much more convenient way than editing AST or other internal representations directly.

grogers 4y ago

My dream would be to have a three-way merge tool that worked like this at a semantic level. It feels like merges almost always have the information needed to automatically resolve, but our line-based tools are too simple to see it.

werdnapk 4y ago
I used to use Araxis Merge [1] years ago and found it worked very well. [1] https://www.araxis.com/merge/index.en https://www.araxis.com/merge/index.en
- swozey 4y ago
  Geez, I've been looking at diff programs and the personal licenses for them are so expensive. I get they're incredibly useful when you need them but I personally don't need a 3rd party differ very often. Kaleidoscope is $250ish IIRC. The VSCode extension "Diff & Merge" give you the right/left arrows to merge lines if anyone is looking for a tool that does that. I haven't needed another one since I found that.
  - activitypea 4y ago
    Sublime Merge was pretty alright, don't know if it's still around
    - nammi 4y ago
      It's still around and getting periodic updates. I originally bought it mainly to give Sublime more money (after using the Sublime Text trial for most of college), but it ended up being useful and I use it daily https://www.sublimemerge.com/download https://www.sublimemerge.com/download
  - jereees 4y ago
    This is now supported without extensions in latest vscode
4y ago

jesse__ 4y ago

That's a diffing fantastic blog post, thanks for writing it! Not to mention the actual tool ;) I'll definitely be trying it out

bqmjjx0kac 4y ago

I got lost on the last example: `(foo (bar))` -> `(foo (novel) (bar))`. The diff that adds `novel` and a pair of parentheses seemed impossible -- wouldn't you also have to delete and re-add `bar`? Writing this comment it occurs to me that the structural diff doesn't translate to plaintext very well, and thus is not accessible to folks with red-green colorblindness.

layer8 4y ago
I think that example is an error. What they possibly meant was you can perform the change by inserting “novel) (”, which may structurally translate to inserting “novel” in the bar list and then splitting that list. Advanced diff tools usually allow configuring the colors, so that if the red/green is a problem, you can change it to red/blue or blue/yellow or whatever.
- eyelidlessness 4y ago
  I don’t think it was an error, given how the article describes its handling of delimiters. In the example: (foo (bar)) (foo (novel) (bar)) The balanced parentheses around bar “haven’t changed”, but the symbol between them “has”, and the balanced parentheses around bar were “added”. It’s a perfectly valid diff given the approach, even if it’s not ideal, as the author found. The only way you could arrive at “novel) (” given the algorithm, I think, would be something like (foo (bar)) (foo novel) ((bar)) (This might be off too, hard to write code on mobile)
Wilfred 4y ago
Thanks for the feedback! I'll look to clarify the wording here. The failed example was a real output that difftastic gave in early versions. I agree that the classic red/green colour scheme of diffs isn't great for colourblind users. I've asked a few colourblind developers and they were happy with terminal ANSI colours (which is what difftastic uses), because they can configure each colour individually.

pabs3 4y ago

Reminds me of the token-based git authorship tool, cregit: https://github.com/cregit/cregit https://github.com/cregit/cregit https://lwn.net/Articles/698425/ https://lwn.net/Articles/698425/ https://www.youtube.com/watch?v=iXZV5uAYMJI https://www.youtube.com/watch?v=iXZV5uAYMJI

pabs3 4y ago

On cool diff tools, diffoscope is my favourite: https://diffoscope.org/ https://diffoscope.org/

bityard 4y ago
This looked interesting and I was going to try it out but installing it via `apt` would have pulled in 3 GB of dependencies!
- pabs3 4y ago
  Try the diffoscope-minimal variant and disable recommends when installing. You'll lose support for a lot of different formats. You can also try it online using the service instead of locally: https://try.diffoscope.org/ https://try.diffoscope.org/

ziml77 4y ago

Smarter diffs are great, but what is especially nice is smarter merges. I would love to see this extended to be able to do the same kinds of auto-merges that SemanticMerge could. I would pay for that functionality (just like I paid for SemanticMerge for years before they took it away to instead entice people to pay for their stupid VCS).

Gehinnn 4y ago
Semantic merge is no longer available? :(
- ziml77 4y ago
  Nope. They integrated the functionality with Plastic SCM. And what's especially annoying is that they don't even grandfather existing customers into being able to continue using SemanticMerge. Once your current license expires, that's it, no more SemanticMerge.
  - Gehinnn 4y ago
    Is there an existing open source effort to recreate that tool? Are the algorithms open? Does the tool work reliably? I find it very sad that potentially revolutionary progress is lost like this...

prirun 4y ago

A friend (Hi Jeff!) wrote DiffMerge: https://sourcegear.com/diffmerge https://sourcegear.com/diffmerge - another alternative diff & merge.

emsixteen 4y ago
I use this occasionally on Mac, and it's pretty handy. Crashes/throws an error when closing though.

_dain_ 4y ago

This article loses me when it gets to the "calculating the diff" section. >Autochrome and difftastic represent diffing as a shortest path problem on a directed acyclic graph. A vertex represents a pair of positions: the position in the left-hand side s-expression (before), and the position in the right-hand side s-expression (after). >The goal is to find the shortest route from the start vertex (where both positions are before the first item in the programs) to the end vertex (where both positions are after the last item in the program). I don't understand what this means at all? What is a "position" here? Position of what? If it's a graph, what do the edges represent? The diagrams afterwards aren't very helpful either, I can't make head nor tail of them. They talk about a "start" vertex and an "end" vertex, but before that it said that a vertex is a pair of start-end positions ... I'm totally lost.

Wilfred 4y ago
Thanks for the feedback. This is really hard to explain. Autochrome has a brilliant worked example https://fazzone.github.io/autochrome.html https://fazzone.github.io/autochrome.html and it still took me several readings before it clicked. Every graph vertex represents a pair of pointers (or positions) to AST nodes. So in the example, the start program is `A` and the end program is `X A`. The positions point to AST nodes in these programs. I try to use 'vertex' consistently for graph vertices, to avoid confusion with AST/s-expression nodes. If you have any suggestions for better terminology I'd be very interested too :)

dan-robertson 4y ago

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).

db48x 4y ago
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.
- dan-robertson 4y ago
  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.
  - db48x 4y ago
    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.

yboris 4y ago

My favorite diff tool is diff2html - see the diff in your browser as HTML! https://diff2html.xyz/ https://diff2html.xyz/ Install the CLI, run the command (alias diff='diff2html -s side') - I run this at least every time before committing to quickly see all I've done.

bufferoverflow 4y ago
What's the advantage of seeing the diff in HTML? Seems like an unnecessary extra step.
- yboris 4y ago
  Visually easier on my eyes, easier to scroll, I can filter out `package-lock.json` file from the diff (with a command line argument). In the end it's a preference thing, not an "objectively better" thing.
- Wilfred 4y ago
  Side-by-side diff displays work really great in a browser. You usually have more screen real estate, and you can offer a responsive UI.

yewenjie 4y ago

One more tree-sitter based diffing tool - diffsitter https://github.com/afnanenayet/diffsitter https://github.com/afnanenayet/diffsitter

billconan 4y ago

I hope this can be an API too, to support other utility tools.

buffaloPizzaBoy 4y ago

It is interesting to see the use of the A* path finding algorithm for finding optimal matchings of nodes. The approach from Chawathe et. al splits nodes from the before/after trees into chains by their label in the syntax grammar, and then runs myers’ longest common subsequence on each pair of chains. Some parameters t, f are used to have an approximate ‘equals’ method for subtrees. This iteratively builds a set of matchings between equivalent nodes from the old and new trees. Here’s the paper https://dl.acm.org/doi/10.1145/235968.233366 https://dl.acm.org/doi/10.1145/235968.233366 I’d be curious to see if this approach handles re-ordering of nodes better. The ‘fastMatch’ algorithm described above will typically miss matching cases where a node that is not order sensitive (i.e a function in a namespace can be moved somewhere else in that namespace).

Wilfred 4y ago
I've looked at several tree diffing papers, including Chawathe et al, but it's not always easy to assess whether their approach would suit difftastic. I know that sdiff by Arun Isaac is based on applying that paper to Scheme: https://archive.fosdem.org/2021/schedule/event/sexpressiondiff/ https://archive.fosdem.org/2021/schedule/event/sexpressiondi... , although he also reports performance challenges. Most tree diffing papers that I've seen focus on either (1) providing a minimal diff and accepting the performance cost or (2) providing a relatively minimal diff and focusing on the performance. I've generally found that you need a minimal diff to get a good result, so papers in (2) are less applicable. I've also found several cases where there are several possible minimal diffs, but there's a clear 'correct' answer from the user's perspective. Difftastic doesn't handle moves: the edit set is add, remove, or replace similar comment. If you reorder functions, it will take the largest unchanged subset. Moves are hard to model in a diffing algorithm, but they're also very hard to display coherently in the UI. I know a few code forge websites (e.g. Phabricator) show moves in a fairly comprehensible way, although they're all based on line-based diffs.