28 ms·

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 clos

by gefh 9y ago

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

taeric 9y ago
This is a bit of a holy grail, that in practice isn't actually that important. https://stackoverflow.com/questions/523307/semantic-diff-utilities 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.)
- zaptheimpaler 9y ago
  As a newbie to how diff-ing is done in production, does git use vanilla edit-distance diffing too?
  - peff 9y ago
    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 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.
- ProblemFactory 9y ago
  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.
srean 9y ago
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.
adekok 9y ago
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...
- slavik81 9y ago
  Chopping up the code by function is not enough. The same problem exists for blocks within functions, like with a sequence of if statements.
  - adekok 9y ago
    Yes... that should go without saying.
teabee89 9y ago
Here you go, it's called Tichy diff: http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%2083-459.pdf 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-diff-walter-tichys-papers.html http://bryanpendleton.blogspot.com/2010/04/more-study-of-dif...
- hoorayimhelping 9y ago
  Your first link, (http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%2083-459.pdf http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%...) seems broken. It redirects me here: http://docs.lib.purdue.edu/cstech/ http://docs.lib.purdue.edu/cstech/
  - teabee89 9y ago
    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/publication/220439403_The_String-to-String_Correction_Problem_With_Block_Moves/links/53d63a7f0cf228d363ea46d3/The-String-to-String-Correction-Problem-With-Block-Moves.pdf https://www.researchgate.net/profile/Walter_Tichy/publicatio... For some reason, I cannot edit my previous comment :(
austincheney 9y ago
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 http://prettydiff.com/guide/unrelated_diff.xhtml
deleted 9y ago
[deleted]

by gefh 9y ago

taeric 9y ago

This is a bit of a holy grail, that in practice isn't actually that important. https://stackoverflow.com/questions/523307/semantic-diff-utilities 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.)

zaptheimpaler 9y ago
As a newbie to how diff-ing is done in production, does git use vanilla edit-distance diffing too?
- peff 9y ago
  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 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.
ProblemFactory 9y ago
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.

srean 9y ago

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.

adekok 9y ago

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

slavik81 9y ago
Chopping up the code by function is not enough. The same problem exists for blocks within functions, like with a sequence of if statements.
- adekok 9y ago
  Yes... that should go without saying.

teabee89 9y ago

Here you go, it's called Tichy diff: http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%2083-459.pdf 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-diff-walter-tichys-papers.html http://bryanpendleton.blogspot.com/2010/04/more-study-of-dif...

hoorayimhelping 9y ago
Your first link, (http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%2083-459.pdf http://ftp.cs.purdue.edu/research/technical_reports/1983/TR%...) seems broken. It redirects me here: http://docs.lib.purdue.edu/cstech/ http://docs.lib.purdue.edu/cstech/
- teabee89 9y ago
  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/publication/220439403_The_String-to-String_Correction_Problem_With_Block_Moves/links/53d63a7f0cf228d363ea46d3/The-String-to-String-Correction-Problem-With-Block-Moves.pdf https://www.researchgate.net/profile/Walter_Tichy/publicatio... For some reason, I cannot edit my previous comment :(

austincheney 9y ago

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 http://prettydiff.com/guide/unrelated_diff.xhtml

deleted 9y ago

[deleted]