News for hackers. Stuff that matters.
Re:Myers Diff Algorithm – Code and Interactive Visualization by gefh on Monday July 03, 2017 @02:01PM (#14690185)
I don't want a diff algorithm that finds the mathematically smallest edit distance, I want one that preserves meaningful chunks of code. I never delete the closing } from one function and then the entire function following it except its last }.
Re:Myers Diff Algorithm – Code and Interactive Visualization by teabee89 on Monday July 03, 2017 @07:16PM (#14692161)
Here you go, it's called Tichy diff: http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%...

This 1983 paper is still relevant today, it's an algorithm much better suited for code diffs and I'd like to use this instead. It's the best algorithm for big code refactors. I implemented it in Go, and hope to get back to it.

Learned about it on: http://bryanpendleton.blogspot.com/2010/04/more-study-of-dif...

Re:Myers Diff Algorithm – Code and Interactive Visualization by hoorayimhelping on Monday July 03, 2017 @11:47PM (#14693404)
Re:Myers Diff Algorithm – Code and Interactive Visualization by teabee89 on Tuesday July 04, 2017 @12:36AM (#14693573)
HN hug? :)

The title of the paper is "The String-to-String Correction Problem with Block Moves". You can search for it with filetype:pdf on Google.

Here is another link (even better quality): https://www.researchgate.net/profile/Walter_Tichy/publicatio...

For some reason, I cannot edit my previous comment :(

Re:Myers Diff Algorithm – Code and Interactive Visualization by taeric on Monday July 03, 2017 @02:08PM (#14690233)
This is a bit of a holy grail, that in practice isn't actually that important. https://stackoverflow.com/questions/523307/semantic-diff-uti... has a good overview of some of the possibilities.

Makes for amazing demos. Might some day be what we are all using. My hopes have been dampened severely by how long this has taken to make any head way. (And, honestly, it couples your diff tool to the rest of your tool chain rather heavily. I can see why it has a hard time taking off.)

Re:Myers Diff Algorithm – Code and Interactive Visualization by ProblemFactory on Monday July 03, 2017 @02:41PM (#14690452)
I think you could get 90% of the utility of semantic syntax tree diff by standard text diff + some simple rules.

For example preferring to split on empty (whitespace-only) lines. Almost all languages and coding styles use empty lines as a "semantic separator" marker.

Re:Myers Diff Algorithm – Code and Interactive Visualization by zaptheimpaler on Monday July 03, 2017 @02:14PM (#14690267)
As a newbie to how diff-ing is done in production, does git use vanilla edit-distance diffing too?
Re:Myers Diff Algorithm – Code and Interactive Visualization by peff on Monday July 03, 2017 @02:36PM (#14690424)
Git uses Myers diff, but recently added some heuristics to "shift" the hunks in semantically meaningful ways. See https://github.com/mhagger/diff-slider-tools for the experiments that led to this feature.

It also supports a few other diff algorithms: `--patience` and `--histogram`, but in my experience they produce the same output as Myers in most cases.

Re:Myers Diff Algorithm – Code and Interactive Visualization by adekok on Monday July 03, 2017 @03:56PM (#14690941)
i.e.:

1) convert code sample 1 to AST 2) convert code sample 2 to AST 3) do text-based diffs while paying attention to the ASTs

A closing brace is really part of the function started by the function definition and opening brace. As such, a closing brace from function X should never "match" an opening brace from function Y.

I imagine that simple chopping code into multiple text blocks, one for each function, before passing it to a "diff" routine would accomplish most of that. After all, we already chop code into text blocks by filename...

Re:Myers Diff Algorithm – Code and Interactive Visualization by slavik81 on Monday July 03, 2017 @04:29PM (#14691146)
Chopping up the code by function is not enough. The same problem exists for blocks within functions, like with a sequence of if statements.
Re:Myers Diff Algorithm – Code and Interactive Visualization by adekok on Monday July 03, 2017 @04:46PM (#14691233)
Yes... that should go without saying.
Re:Myers Diff Algorithm – Code and Interactive Visualization by srean on Monday July 03, 2017 @03:31PM (#14690748)
A plausible approach would be to instrument the editor to log 'edit -events'. Then one could fit/learn an appropriate probabilistic model/grammar. After that given two pieces of text A and B it becomes a question of finding the most probable edits that takes you from A to B.

This is far from a new idea. Age old Levenstein distance can be seen as a special case. Here the edit model is very simple. All letter addition, deletion, and substitutions are equally likely. More realistic a model one uses the better the results will look like provided one has enough data to train.

One could train models for specific languages (natural as well as programming). If we have language specific syntax highlighting, why not language specific edit models. One could do personalized models, etc etc.

Re:Myers Diff Algorithm – Code and Interactive Visualization by austincheney on Monday July 03, 2017 @07:17PM (#14692168)
A couple months ago I wrote a diff algorithm that was pretty popular on the front page here, http://prettydiff.com/guide/unrelated_diff.xhtml
Re:Myers Diff Algorithm – Code and Interactive Visualization by rajathagasthya on Monday July 03, 2017 @03:48PM (#14690893)
Another explanation of Myers diff algorithm that I found interesting: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm...
Re:Myers Diff Algorithm – Code and Interactive Visualization by fny on Monday July 03, 2017 @05:45PM (#14691638)
My God that code is terrifying. It looks like output from a code obfuscator.
Re:Myers Diff Algorithm – Code and Interactive Visualization by Boxxed on Monday July 03, 2017 @10:48PM (#14693161)
Pretty sure this is the same Eugene Myers I had worked with a bit in the past -- he's the kind of guy who took, "Wow, this looks complicated," or "I'm having a hard time following this," as the highest sort of compliment.
Re:Myers Diff Algorithm – Code and Interactive Visualization by pbnjay on Monday July 03, 2017 @04:06PM (#14691006)
This algorithm is actually really useful in genomic sequencing - daily usage for me right now. Cool to see it pop up here, although I think it's less generally useful than other edit distance methods.
Re:Myers Diff Algorithm – Code and Interactive Visualization by enriquto on Tuesday July 04, 2017 @04:56AM (#14694528)
Wow! this is a very beautiful code and website

- single letter variables, as in the rest of mathematics

- succinct without being obfuscated

- the whole thing fits on your screen without need to scroll (no dependences, no hidden pieces)

- the complex algorithm is clarified in the text below, breaking it into smaller parts and explaining each one in detail

- comprehensive examples, figures and references

This is truly a model of exposition.

Re:Myers Diff Algorithm – Code and Interactive Visualization by sordina on Tuesday July 04, 2017 @05:06AM (#14694576)
Seems like this would have been super useful when I was creating a Levenshtein transition effect: https://jsfiddle.net/kdqost0z/2/

Not that efficiency really matters much for my use-case!

Re:Myers Diff Algorithm – Code and Interactive Visualization by jgalt212 on Monday July 03, 2017 @07:53PM (#14692369)
I always thought finding the optimal diff (from the user perspective) was an NP Complete problem.
Re:Myers Diff Algorithm – Code and Interactive Visualization by Someone on Tuesday July 04, 2017 @01:38PM (#14697186)
I would expect that to be an unsolvable problem, because there will be plenty of cases where not all users agree on what is the optimal diff.
Re:Myers Diff Algorithm – Code and Interactive Visualization by s_bywater on Monday July 03, 2017 @05:20PM (#14691491)
Wweereee
Re:Myers Diff Algorithm – Code and Interactive Visualization by taeric on Monday July 03, 2017 @01:49PM (#14690107)
Haven't read it yet. Curious about the implication of the title. Expecting article to be that it could be asymptotically faster, but practically slower. :) (That probably says more about how I choose to read headlines than anything else.)

Edit: Read the article now. Incredibly happy to see that the implication was on purpose. :)