{"thread":{"id":"39564","subject":"GNU diff and git diff - difference on myers algorithm?","startedAt":"2015-06-08T18:34:25Z","lastAt":"2015-07-17T04:23:54Z","messageCount":6,"participants":["Luis R. Rodriguez","Johannes Schindelin","Jacob Keller"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"263280","messageId":"CAB=NE6XRnKAY6t+dxT7vO_4wqngXvULh-CqezEAs2r99FkNCTg@mail.gmail.com","threadId":"39564","inReplyTo":null,"subject":"GNU diff and git diff - difference on myers algorithm?","fromName":"Luis R. Rodriguez","fromEmail":"mcgrof@do-not-panic.com","sentAt":"2015-06-08T18:34:25Z","receivedAt":"2015-06-08T18:34:25Z","isPatch":false,"sender":{"key":"mcgrof@do-not-panic.com","avatar":null},"body":"Based on a cursory review of the git code I get the impression that\nGNU diff and git 'diff' do not share any code for the possible diff\nalgorithms. I'm in particularly curious more about the default \"myers\"\nalgorithm. I can take time to do a precise code review of the\nalgorithms used on both GNU diff and git but if someone can already\nvet for any differences that'd be appreciated as it would save time.\n\n Luis\n"},{"id":"263328","messageId":"0add7d95076f5b112af90d8566c29203@www.dscho.org","threadId":"39564","inReplyTo":"CAB=NE6XRnKAY6t+dxT7vO_4wqngXvULh-CqezEAs2r99FkNCTg@mail.gmail.com","subject":"Re: GNU diff and git diff - difference on myers algorithm?","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2015-06-09T08:25:44Z","receivedAt":"2015-06-09T08:25:44Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Luis,\n\nOn 2015-06-08 20:34, Luis R. Rodriguez wrote:\n> Based on a cursory review of the git code I get the impression that\n> GNU diff and git 'diff' do not share any code for the possible diff\n> algorithms.\n\nIndeed, Git's diff machinery is based[*1*] ofn libxdiff[*2*], not on GNU diff.\n\n> I'm in particularly curious more about the default \"myers\"\n> algorithm.\n\nAre you looking for a freely available implementation of the Myers algorithm? Or are you interested in understanding it?\n\nPlease note that Myers' algorithm is just one first step in most diff implementations (and that other diff algorithms have become popular, in particular because comparing strings can be accelerated by hashing the text lines first, and those hashes can also be used to identify matching pairs of unique lines, giving rise to yet another huge performance boost for typical uses).\n\nThe reason why Myers' algorithm is not sufficient for diff implementations is that it only optimizes the \"edit distance\", i.e. the amount of added/removed lines, while patches should be readable, too, i.e. prefer *consecutive* edits to disjunct ones.\n\nJust to mention one post-processing technique that is so useful that I implemented it for Git[*3*]: the \"patience diff\" algorithm of Bram Cohen (of BitTorrent fame) finds matching pairs of unique lines -- think of a function from which another function is refactored, for example, intuitively you want the diff to keep the signature of the original function as a context line.\n\nDisclaimer: While it is true that Gene and I shared an office for one month, and that I am once again working in the same institute as he does, all my knowledge about this algorithm stems from my reading his paper and implementing the algorithm in Java for use in JGit[*3*].\n\n> I can take time to do a precise code review of the\n> algorithms used on both GNU diff and git but if someone can already\n> vet for any differences that'd be appreciated as it would save time.\n\nAgain, I am curious what your goal is? I am sure I can support your quest better when I understand what the purpose of this code review should be.\n\nCiao,\nJohannes\n\nFootnote *1*: https://github.com/git/git/commit/3443546f6ef57fe28ea5cca232df8e400bfc3883\nFootnote *2*: http://www.xmailserver.org/xdiff-lib.html\nFootnote *3*: https://github.com/git/git/blob/master/xdiff/xpatience.c\nFootnote *4*: https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java\n"},{"id":"263689","messageId":"CAB=NE6VGX332=CvhQM4sc27AM8ae5S1kdRnm5sMfoqkU=b=ebg@mail.gmail.com","threadId":"39564","inReplyTo":"0add7d95076f5b112af90d8566c29203@www.dscho.org","subject":"Re: GNU diff and git diff - difference on myers algorithm?","fromName":"Luis R. Rodriguez","fromEmail":"mcgrof@do-not-panic.com","sentAt":"2015-06-12T18:52:58Z","receivedAt":"2015-06-12T18:52:58Z","isPatch":false,"sender":{"key":"mcgrof@do-not-panic.com","avatar":null},"body":"On Tue, Jun 9, 2015 at 1:25 AM, Johannes Schindelin\n wrote:\n> Hi Luis,\n>\n> On 2015-06-08 20:34, Luis R. Rodriguez wrote:\n>> Based on a cursory review of the git code I get the impression that\n>> GNU diff and git 'diff' do not share any code for the possible diff\n>> algorithms.\n>\n> Indeed, Git's diff machinery is based[*1*] ofn libxdiff[*2*], not on GNU diff.\n\nGreat thanks for the confirmation. Interesting point by Linus on that\ncommit that changed from forking to use GNU diff to libxdiff:\n\n \"generating a diff is not an exact\n science - you can get two different diffs (and you will), and they can\n both be perfectly valid. So it's not possible to \"validate\" the\n libxdiff output by just comparing it against GNU diff.\"\n\nIndeed, simple example is using different starting context lines, or\ndifferent number of context lines. I do however wonder if under\ncertain parameters they *need* to be equal, or if this has been\nstudied exactly before.\n\n>> I'm in particularly curious more about the default \"myers\"\n>> algorithm.\n>\n> Are you looking for a freely available implementation of the Myers algorithm? Or are you interested in understanding it?\n\nI was trying to determine the above, of possibilities of differences.\nNow granted there are the \"diffs\" using different output layouts\nshould differ, and as I note above if you modify the conext preference\nyou might end up with slightly different diffs, but I am also curious\nto know if anyone has done research to see whether or not two hunks\nwhich are slightly different are functionally equivalent. More on the\nreasoning behind this below.\n\n> Please note that Myers' algorithm is just one first step in most diff implementations (and that other diff algorithms have become popular, in particular because comparing strings can be accelerated by hashing the text lines first, and those hashes can also be used to identify matching pairs of unique lines, giving rise to yet another huge performance boost for typical uses).\n\nAwesome.\n\n> The reason why Myers' algorithm is not sufficient for diff implementations is that it only optimizes the \"edit distance\", i.e. the amount of added/removed lines, while patches should be readable, too, i.e. prefer *consecutive* edits to disjunct ones.\n\nIndeed, this is along the lines of what I am looking for but with some\nother tweaks considered, more on this below.\n\n> Just to mention one post-processing technique that is so useful that I implemented it for Git[*3*]: the \"patience diff\" algorithm of Bram Cohen (of BitTorrent fame) finds matching pairs of unique lines -- think of a function from which another function is refactored, for example, intuitively you want the diff to keep the signature of the original function as a context line.\n\nIndeed.\n\n> Disclaimer: While it is true that Gene and I shared an office for one month, and that I am once again working in the same institute as he does, all my knowledge about this algorithm stems from my reading his paper and implementing the algorithm in Java for use in JGit[*3*].\n\n:)\n\n>> I can take time to do a precise code review of the\n>> algorithms used on both GNU diff and git but if someone can already\n>> vet for any differences that'd be appreciated as it would save time.\n>\n> Again, I am curious what your goal is? I am sure I can support your quest better when I understand what the purpose of this code review should be.\n\nOK wells I'm curious about more research / effort when trying to\nevaluate a diff with two seprate but adjoining preprocessor directives\nand if anyone has implemented an optimizaiton option to let the diff\ngenerator join them.\n\nFor example, to let it infer that:\n\n--- a/test.c\n+++ b/test.c\n@@ -10,8 +10,6 @@ int main(int argc, char *argv[])\n\n #ifdef FOO\n a = 4;\n-#endif /* FOO */\n-#ifdef FOO\n a = 5;\n #endif /* FOO */\n\nis possible.\n\n Luis\n"},{"id":"266202","messageId":"CAB=NE6UFMv0qu8fJ1P2-pJCF0tSGKoW+uKhfwt0jV5fj2wZGSQ@mail.gmail.com","threadId":"39564","inReplyTo":"CAB=NE6VGX332=CvhQM4sc27AM8ae5S1kdRnm5sMfoqkU=b=ebg-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org","subject":"Re: GNU diff and git diff - difference on myers algorithm?","fromName":"Luis R. Rodriguez","fromEmail":"mcgrof-3uybbjdb1yh774rrrx3eta@public.gmane.org","sentAt":"2015-07-16T19:07:50Z","receivedAt":"2015-07-16T19:07:50Z","isPatch":false,"sender":{"key":"mcgrof-3uybbjdb1yh774rrrx3eta@public.gmane.org","avatar":null},"body":"On Fri, Jun 12, 2015 at 11:52 AM, Luis R. Rodriguez\n wrote:\n> OK wells I'm curious about more research / effort when trying to\n> evaluate a diff with two seprate but adjoining preprocessor directives\n> and if anyone has implemented an optimizaiton option to let the diff\n> generator join them.\n>\n> For example, to let it infer that:\n>\n> --- a/test.c\n> +++ b/test.c\n> @@ -10,8 +10,6 @@ int main(int argc, char *argv[])\n>\n> #ifdef FOO\n> a = 4;\n> -#endif /* FOO */\n> -#ifdef FOO\n> a = 5;\n> #endif /* FOO */\n>\n> is possible.\n\nAnyone familiar if any tool exists today that would optimize this? Is\nanyone working on it? Would git be a good place for such a thing? I'd\nconsider it as an option to optimize a diff. This for example is\nextremely useful for us working with Coccinelle where we have a tool\nwriting code for us, while such an optimization might be useful to\nCoccinelle it would seem like a rather generic feature, its just not\nclear to me where to give such a tool a proper home.\n\n Luis\n"},{"id":"266223","messageId":"CA+P7+xrOPS6NeQhte-ATdm2Nqo0PpmUAxS+XYzWDvZGtwPtWMw@mail.gmail.com","threadId":"39564","inReplyTo":"CAB=NE6UFMv0qu8fJ1P2-pJCF0tSGKoW+uKhfwt0jV5fj2wZGSQ-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org","subject":"Re: GNU diff and git diff - difference on myers algorithm?","fromName":"Jacob Keller","fromEmail":"jacob.keller-re5jqeeqqe8avxtiumwx3w@public.gmane.org","sentAt":"2015-07-17T04:22:27Z","receivedAt":"2015-07-17T04:22:27Z","isPatch":false,"sender":{"key":"jacob.keller-re5jqeeqqe8avxtiumwx3w@public.gmane.org","avatar":null},"body":"On Thu, Jul 16, 2015 at 12:07 PM, Luis R. Rodriguez\n wrote:\n> On Fri, Jun 12, 2015 at 11:52 AM, Luis R. Rodriguez\n> wrote:\n>> OK wells I'm curious about more research / effort when trying to\n>> evaluate a diff with two seprate but adjoining preprocessor directives\n>> and if anyone has implemented an optimizaiton option to let the diff\n>> generator join them.\n>>\n>> For example, to let it infer that:\n>>\n>> --- a/test.c\n>> +++ b/test.c\n>> @@ -10,8 +10,6 @@ int main(int argc, char *argv[])\n>>\n>> #ifdef FOO\n>> a = 4;\n>> -#endif /* FOO */\n>> -#ifdef FOO\n>> a = 5;\n>> #endif /* FOO */\n>>\n>> is possible.\n>\n> Anyone familiar if any tool exists today that would optimize this? Is\n> anyone working on it? Would git be a good place for such a thing? I'd\n> consider it as an option to optimize a diff. This for example is\n> extremely useful for us working with Coccinelle where we have a tool\n> writing code for us, while such an optimization might be useful to\n> Coccinelle it would seem like a rather generic feature, its just not\n> clear to me where to give such a tool a proper home.\n>\n> Luis\n\nI do not understand exactly what would be optimized in this case?\n\nIn any regards, that's not a diff transformation, that is a code\ntransformation, and I would suggest starting with Coccinelle and\nseeing if you can get that to do what you want.\nhttp://coccinelle.lip6.fr/\n\nRegards,\nJake\n"},{"id":"266224","messageId":"CA+P7+xq=J76N16XETKkUhRJKyShPtg4-K0aMjE5+_LzBJQ-t3A@mail.gmail.com","threadId":"39564","inReplyTo":"CA+P7+xrOPS6NeQhte-ATdm2Nqo0PpmUAxS+XYzWDvZGtwPtWMw-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org","subject":"Re: GNU diff and git diff - difference on myers algorithm?","fromName":"Jacob Keller","fromEmail":"jacob.keller-re5jqeeqqe8avxtiumwx3w@public.gmane.org","sentAt":"2015-07-17T04:23:54Z","receivedAt":"2015-07-17T04:23:54Z","isPatch":false,"sender":{"key":"jacob.keller-re5jqeeqqe8avxtiumwx3w@public.gmane.org","avatar":null},"body":"On Thu, Jul 16, 2015 at 9:22 PM, Jacob Keller wrote:\n> On Thu, Jul 16, 2015 at 12:07 PM, Luis R. Rodriguez\n> wrote:\n>> On Fri, Jun 12, 2015 at 11:52 AM, Luis R. Rodriguez\n>> wrote:\n>>> OK wells I'm curious about more research / effort when trying to\n>>> evaluate a diff with two seprate but adjoining preprocessor directives\n>>> and if anyone has implemented an optimizaiton option to let the diff\n>>> generator join them.\n>>>\n>>> For example, to let it infer that:\n>>>\n>>> --- a/test.c\n>>> +++ b/test.c\n>>> @@ -10,8 +10,6 @@ int main(int argc, char *argv[])\n>>>\n>>> #ifdef FOO\n>>> a = 4;\n>>> -#endif /* FOO */\n>>> -#ifdef FOO\n>>> a = 5;\n>>> #endif /* FOO */\n>>>\n>>> is possible.\n>>\n>> Anyone familiar if any tool exists today that would optimize this? Is\n>> anyone working on it? Would git be a good place for such a thing? I'd\n>> consider it as an option to optimize a diff. This for example is\n>> extremely useful for us working with Coccinelle where we have a tool\n>> writing code for us, while such an optimization might be useful to\n>> Coccinelle it would seem like a rather generic feature, its just not\n>> clear to me where to give such a tool a proper home.\n>>\n>> Luis\n>\n> I do not understand exactly what would be optimized in this case?\n>\n> In any regards, that's not a diff transformation, that is a code\n> transformation, and I would suggest starting with Coccinelle and\n> seeing if you can get that to do what you want.\n> http://coccinelle.lip6.fr/\n>\n> Regards,\n> Jake\n\nI misread your comment. Coccinelle is a tool that could probably be\ncoerced into doing this, but this is not a diff optimization unless I\nam completely understanding it. This is a code transformation concept,\nand doesn't have much to do with finding differences or code changes.\nMy above comment is correct, but I don't think this belongs in diff\nparsing, but rather as part of something like Coccinelle\n\nRegards,\nJake\n"}]}