[HN Gopher] Difftastic, the fantastic diff
___________________________________________________________________
Difftastic, the fantastic diff
Author : pcr910303
Score : 613 points
Date : 2022-09-07 04:20 UTC (18 hours ago)
(HTM) web link (www.wilfred.me.uk)
(TXT) w3m dump (www.wilfred.me.uk)
| pabs3 wrote:
| Reminds me of the token-based git authorship tool, cregit:
|
| https://github.com/cregit/cregit https://lwn.net/Articles/698425/
| https://www.youtube.com/watch?v=iXZV5uAYMJI
| billconan wrote:
| I hope this can be an API too, to support other utility tools.
| bqmjjx0kac wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| yboris wrote:
| My favorite _diff_ tool is _diff2html_ - see the diff in your
| browser as HTML!
|
| 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 wrote:
| What's the advantage of seeing the diff in HTML?
|
| Seems like an unnecessary extra step.
| yboris wrote:
| 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 wrote:
| 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.
| mfrw wrote:
| 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
|
| [1]: https://github.com/dandavison/delta
| lapser wrote:
| 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 wrote:
| 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 wrote:
| difftastic doesn't show whitespace or formatting changes
| pabs3 wrote:
| On cool diff tools, diffoscope is my favourite:
|
| https://diffoscope.org/
| bityard wrote:
| 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 wrote:
| 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/
| ziml77 wrote:
| 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 wrote:
| Semantic merge is no longer available? :(
| ziml77 wrote:
| 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 wrote:
| 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...
| idiocratic wrote:
| Great article. It's inspiring to see what applications some
| simple algorithms can have. Kudos for building the tool and
| sharing your approach.
| grogers wrote:
| 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.
| ruricolist wrote:
| Resolve is another tree-sitter based tool that does this:
|
| https://github.com/grammatech/resolve
| newaccount2021 wrote:
| werdnapk wrote:
| I used to use Araxis Merge [1] years ago and found it worked
| very well.
|
| [1] https://www.araxis.com/merge/index.en
| swozey wrote:
| 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 wrote:
| Sublime Merge was pretty alright, don't know if it's still
| around
| nammi wrote:
| 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
| prirun wrote:
| A friend (Hi Jeff!) wrote DiffMerge:
| https://sourcegear.com/diffmerge - another alternative diff &
| merge.
| emsixteen wrote:
| I use this occasionally on Mac, and it's pretty handy.
| Crashes/throws an error when closing though.
| Gehinnn wrote:
| 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 wrote:
| It's a bit out of date but my fork adds this functionality
| https://github.com/anchpop/difftastic
| _dain_ wrote:
| 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.
| dan-robertson wrote:
| 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 wrote:
| 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 wrote:
| 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.
| X-Cubed wrote:
| 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...
| ziftface wrote:
| 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 wrote:
| 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 wrote:
| I like BeyondCompare, as a free option, I really like Meld,
| it's similar.
| bifftastic wrote:
| I like the name
| janaagaard wrote:
| 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.)
| Wilfred wrote:
| 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 has docs.
| mfrw wrote:
| 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.
| Sander_Marechal wrote:
| 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.
| tuetuopay wrote:
| You can turn it on safely. Git does not store diffs (like a
| diff chain), but a snapshot of the files at each commit
| buffaloPizzaBoy wrote:
| 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
|
| 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).
| AndrewDucker wrote:
| For the semantic side of things, could an LSP server be used?
| Building diffs on top of that would be very handy.
| sanxiyn wrote:
| Not really. This needs a parser that produces a tree, and LSP
| does not provide that.
| yosito wrote:
| 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.
| jesse__ wrote:
| That's a diffing fantastic blog post, thanks for writing it! Not
| to mention the actual tool ;) I'll definitely be trying it out
| mfbx9da4 wrote:
| 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 or
| http://incaseofstairs.com/jsdiff/
|
| Does anybody know any better alternatives which work with
| pasting?
| Kolja wrote:
| 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 wrote:
| Na one file is not okay. I have clipboard history.
| tom_ wrote:
| 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 wrote:
| in emacs you can compare buffers (emacs terminology for windows
| or tabs) without saving them.
| coremoff wrote:
| 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)
| vincentdm wrote:
| 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 wrote:
| The author mentions they're using it with Git and Mercurial.
| There are docs here: https://difftastic.wilfred.me.uk/git.html
| yewenjie wrote:
| One more tree-sitter based diffing tool - diffsitter
|
| https://github.com/afnanenayet/diffsitter
| whoomp12342 wrote:
| no wandows installation :-(
| detaro wrote:
| there are windows releases
| luke-stanley wrote:
| This post reminded me of the Trail Of Bits post about 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.
| jbverschoor wrote:
| 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 wrote:
| 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 wrote:
| Yep, that's correct. Difftastic is only a syntactic analysis,
| although it often makes the semantic intent clearer.
| siraben wrote:
| 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
| titaniczero wrote:
| 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
| chii wrote:
| 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 wrote:
| 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_exti
| nguis...
| diffxx wrote:
| As impressive as the tree-sitter ecosystem is, there is a
| certain danger in building tooling on top of it. Unless tree-
| sitter is used as the parser in the actual language compiler,
| it is almost always going to be an approximation to the
| language grammar. This is somewhat risky if it is important
| that any kind of semantic analysis, including diffing, is
| correct. In the case of difftastic, what worries me is that it
| might be possible to inject malicious code into a repo by
| exploiting a bug in the tree-sitter grammar/parsing
| implementation such that the malicious code is hidden from
| difftastic because, for example, it is treated as whitespace
| when it actually isn't. This of course wouldn't be a problem if
| PRs are being handled by github, but what if down the road
| github starts offering difftastic (or something similar) as a
| diff option for PRs?
|
| Admittedly, this is a somewhat far fetched scenario that I have
| posited but I am somewhat concerned that the proliferation of
| incorrect tree-sitter grammars is going to lead to the worst
| kind of problem down the road: tools that work great _most_ of
| the time.
| kibwen wrote:
| Isn't this the case for any tool that does semantic analysis,
| including any interesting feature of any IDE? Even in the
| realm of basic text editors, there's this classic exploit: if
| your editor and language disagree on what characters are
| allowed to end a line, you can smuggle lines of code into a
| program that appear to be commented out but are actually
| executed (or the inverse, lines that appear to be executed
| but are actually commented out).
| naikrovek wrote:
| in theory a compiler could have a mode which gives any tool
| results it can display as errors or whatever anyone needs.
| I think this was one of the original goals of the language
| server protocol, which I still do not understand the need
| for at all.
|
| I don't know if any languages do this.
|
| in reality damn near all languages are parsed easily enough
| that there is no difference.
| trishume wrote:
| 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/).
|
| 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 wrote:
| 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.
| rossmohax wrote:
| Next step is to make an editor where we type/edit AST, not text.
| leloctai wrote:
| Have you heard about our Lord and savior S-expression?
| rossmohax wrote:
| That's for Lisp only, I am talking about generic editor for
| any language with structure.
| jstimpfle wrote:
| 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.
| robin_reala wrote:
| _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
___________________________________________________________________
(page generated 2022-09-07 23:02 UTC)