{"thread":{"id":"16159","subject":"libxdiff and patience diff","startedAt":"2008-11-04T00:40:01Z","lastAt":"2009-01-10T11:36:46Z","messageCount":67,"participants":["Pierre Habouzit","Davide Libenzi","Johannes Schindelin","Linus Torvalds","Adeodato Simó","Clemens Buchacher","Junio C Hamano","Jeff King","Sam Vilain"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"94831","messageId":"20081104004001.GB29458@artemis.corp","threadId":"16159","inReplyTo":null,"subject":"libxdiff and patience diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-04T00:40:01Z","receivedAt":"2008-11-04T00:40:01Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"Hi Davide,\n\nI've been working tonight, trying to make libxdiff support the patience\ndiff algorithm, but I've totally failed, because I _thought_ I\nunderstood what xdl_split was doing, but it appears I don't.\n\n\n[ For the readers playing at home, the patience diff algorithm is\n explained after my sig. ]\n\n\nWhat I did is to:\n(1) add a flag to the xenv in xdl_split that says that I want a\n patience \"split\".\n(2) Then in xdl_split, if that bit is set, I compute the longest common\n subsequence from the patience diff.\n(3) for each split it computes I call xdl_recs_cmp on that interval.\n\n\nWhat I thought it would achieve is that I force some boundaries at which\nlibxdiff _must_ resync. Though, it seems that for some reason it doesn't\nwork, probably because the \"ha\" stuff and the boundaries absolutely\ndon't work the way I thought it did.\n\nSo where is the place I should do that ? I suspect it should be\npartly in xprepare.c but I'm a bit stuck right now.\n\n\nAny pointer on how the stuff in xprepare.c and xdiffi.c work would help\ngreatly, it's really not self-evident to me :)\n\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n\n\n\nPatience diff\n=============\n\nBasically, it's an algorithm that considers line from the left file A\nand the right file B.\n\nIt searches for lines that are unique *IN* A and unique *IN* B as well.\nThen using a clever O(n log log n) where n is that number of lines, you\nextract the longer common sequence of those lines.\n\nThis defines two splits of file A and B. For each corresponding chunks,\nyou then reduce the lines matching at the beginning and the end, and\nreiterate the algorithm on the interior of that space, until there are\n_no_ unique lines at all, and then you apply a usual diff algorithm to\ngenerate the diff in that final section.\n\nhttp://alfedenzo.livejournal.com/170301.html has a nice visual\nexplanation of the fact, even if it forgets about the \"zones\" trimming\nthat helps for the efficiency. It's also often wrong to generate the\nstacks in the order shown on the blog, because you recurse from the max\nline to the min line, which is not the natural order to work on a diff.\nBut that's just a matter of \"inverting\" all the comparisons which is\npretty obvious to do.\n\n\nThe difference of output can be seen on http://glandium.org/blog/?p=120\nwhere the patience diff picks the line\n \"include $(topsrcdir)/config/rules.mk\"\nas being unique on the left and the right file, hence will use it as\nsync point rather than using it in a diff.\n\n"},{"id":"94841","messageId":"Pine.LNX.4.64.0811031904130.9116@alien.or.mcafeemobile.com","threadId":"16159","inReplyTo":"20081104004001.GB29458@artemis.corp","subject":"Re: libxdiff and patience diff","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2008-11-04T03:17:37Z","receivedAt":"2008-11-04T03:17:37Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n\n> Hi Davide,\n> \n> I've been working tonight, trying to make libxdiff support the patience\n> diff algorithm, but I've totally failed, because I _thought_ I\n> understood what xdl_split was doing, but it appears I don't.\n> \n> \n> [ For the readers playing at home, the patience diff algorithm is\n> explained after my sig. ]\n> \n> \n> What I did is to:\n> (1) add a flag to the xenv in xdl_split that says that I want a\n> patience \"split\".\n> (2) Then in xdl_split, if that bit is set, I compute the longest common\n> subsequence from the patience diff.\n> (3) for each split it computes I call xdl_recs_cmp on that interval.\n> \n> \n> What I thought it would achieve is that I force some boundaries at which\n> libxdiff _must_ resync. Though, it seems that for some reason it doesn't\n> work, probably because the \"ha\" stuff and the boundaries absolutely\n> don't work the way I thought it did.\n> \n> So where is the place I should do that ? I suspect it should be\n> partly in xprepare.c but I'm a bit stuck right now.\n> \n> \n> Any pointer on how the stuff in xprepare.c and xdiffi.c work would help\n> greatly, it's really not self-evident to me :)\n\nWhat makes you think it'd self-evident to me? :)\nSeriously, I forgot stuff I wrote the last month, this is way beyond my \nmemory limits.\nYou definitely need to look at xprepare.c, especially at xdl_trim_ends() \nand xdl_cleanup_records(). Lines are re-arranged in indexes, and this \nmight screw up your logic if you're not prepared for it.\nWhat xdl_split() does, is find the start of an LCS and return the \ncoordinate. Then xdl_recs_cmp() does the box reducing (first two \"for\" \nloops) and different-lines marking (first and second \"if\").\n\n\n\n- Davide\n"},{"id":"94855","messageId":"alpine.DEB.1.00.0811040627020.24407@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"20081104004001.GB29458@artemis.corp","subject":"Re: libxdiff and patience diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-04T05:39:48Z","receivedAt":"2008-11-04T05:39:48Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Nov 2008, Pierre Habouzit wrote:\n\n> I've been working tonight, trying to make libxdiff support the patience \n> diff algorithm, but I've totally failed, because I _thought_ I \n> understood what xdl_split was doing, but it appears I don't.\n\nI thought about it, too, at the GitTogether, although I want to finish my \njGit diff first.\n\nThe main idea I had about patience diff is that you can reuse a lot of \nfunctions in libxdiff.\n\nBut the requirement of taking just unique lines/hashes into account, and \n_after_ splitting up, _again_ determine uniqueness _just_ in the \nbetween-hunk part made me think that it may be wiser to have a separate \nfunction for the patience diff stuff.\n\nBasically, you would start to have libxdiff split the lines and hash them \nas normal, but then determine the unique hashes (I'd start with the \nsmaller text, just to have a better chance to end up with unique hashes).\n\nOnce they are determined, you can search for those exact lines (hash \nfirst) in the post-document.\n\nOnce that is done, you'd have to find the longest common subsequence, \nwhich you could do using the existing infrastructure, but that would \nrequire more work (as we already know the lines are unique).\n\nAfter that, you would have to recurse to the same algorithm _between_ \nknown chunks. Eventually, that would have to resort to classical libxdiff \n(if there are no, or not enough, unique lines).\n\nCiao,\nDscho\n"},{"id":"94870","messageId":"20081104083042.GB3788@artemis.corp","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0811040627020.24407@pacific.mpi-cbg.de","subject":"Re: libxdiff and patience diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-04T08:30:42Z","receivedAt":"2008-11-04T08:30:42Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Nov 04, 2008 at 05:39:48AM +0000, Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> \n> > I've been working tonight, trying to make libxdiff support the patience \n> > diff algorithm, but I've totally failed, because I _thought_ I \n> > understood what xdl_split was doing, but it appears I don't.\n> \n> I thought about it, too, at the GitTogether, although I want to finish my \n> jGit diff first.\n> \n> The main idea I had about patience diff is that you can reuse a lot of \n> functions in libxdiff.\n> \n> But the requirement of taking just unique lines/hashes into account, and \n> _after_ splitting up, _again_ determine uniqueness _just_ in the \n> between-hunk part made me think that it may be wiser to have a separate \n> function for the patience diff stuff.\n> \n> Basically, you would start to have libxdiff split the lines and hash them \n> as normal, but then determine the unique hashes (I'd start with the \n> smaller text, just to have a better chance to end up with unique hashes).\n> \n> Once they are determined, you can search for those exact lines (hash \n> first) in the post-document.\n\nActually my current implementation just puts all the hashes into an\narray, sorts them by hash (which is O(n log(n)) with the position from\nleft or right file it's in, ordered by increasing right position. (and\nthe struct is filled with the left pos to -1 if the right pos is set,\nand vice versa).\n\nThe I scan the array to find patterns of two consecutive hashes exactly,\nand collapse it into the proper {left pos, right pos} tuple if it was\nindeed a unique line in both files.\n\nThis results into an array I sort again by right pos then, and we can\nwork on that for the stack sorting, and I do it, and then I have my LCS.\n\n\nThis is the complete brute-force algorithm which requires a temporary\narray of the size of the number of lines on the left + the right, and a\ntemporary array for the stacks which _may_ end up being as large as the\nsmallest number of lines between the left or right file in the worst\ncase I'd say (roughly).\n\nThen I just remember a list of split points, and I recurse in all the\nsub splits again. It has a fixed point which may or may not need\nlibxdiff recursion in it.\n\nThis code is actually written, naive and unoptimized but it doesn't work\nprobably because I didn't plug that in the proper place :)\n\n> Once that is done, you'd have to find the longest common subsequence, \n> which you could do using the existing infrastructure, but that would \n> require more work (as we already know the lines are unique).\n\nPatience diff gives you the algorithm to do that, it's pretty simple,\nand is more efficient than the current infrastructure (in time, I don't\nknow for space though).\n\n> After that, you would have to recurse to the same algorithm _between_ \n> known chunks. Eventually, that would have to resort to classical libxdiff \n> (if there are no, or not enough, unique lines).\n\nYeah, that's the point, the problem is, I believe more and more that I\nshould prepare the LCS from patience diff in xprepare.c, but I grok\nabsolutely nothing at what the chastore_t and similar stuff is. I\nunderstand it's about hashing, but the exact stuff it does eludes me. In\nfact when I look at the records I have in xdiffi.c I had the impression\nthey were already somehow collapsed, which makes it a too late point to\napply the patience diff ...\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"94871","messageId":"20081104083303.GC3788@artemis.corp","threadId":"16159","inReplyTo":"Pine.LNX.4.64.0811031904130.9116@alien.or.mcafeemobile.com","subject":"Re: libxdiff and patience diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-04T08:33:03Z","receivedAt":"2008-11-04T08:33:03Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Nov 04, 2008 at 03:17:37AM +0000, Davide Libenzi wrote:\n> On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> \n> > Hi Davide,\n> > \n> > I've been working tonight, trying to make libxdiff support the patience\n> > diff algorithm, but I've totally failed, because I _thought_ I\n> > understood what xdl_split was doing, but it appears I don't.\n> > \n> > \n> > [ For the readers playing at home, the patience diff algorithm is\n> > explained after my sig. ]\n> > \n> > \n> > What I did is to:\n> > (1) add a flag to the xenv in xdl_split that says that I want a\n> > patience \"split\".\n> > (2) Then in xdl_split, if that bit is set, I compute the longest common\n> > subsequence from the patience diff.\n> > (3) for each split it computes I call xdl_recs_cmp on that interval.\n> > \n> > \n> > What I thought it would achieve is that I force some boundaries at which\n> > libxdiff _must_ resync. Though, it seems that for some reason it doesn't\n> > work, probably because the \"ha\" stuff and the boundaries absolutely\n> > don't work the way I thought it did.\n> > \n> > So where is the place I should do that ? I suspect it should be\n> > partly in xprepare.c but I'm a bit stuck right now.\n> > \n> > \n> > Any pointer on how the stuff in xprepare.c and xdiffi.c work would help\n> > greatly, it's really not self-evident to me :)\n> \n> What makes you think it'd self-evident to me? :)\n> Seriously, I forgot stuff I wrote the last month, this is way beyond my \n> memory limits.\n> You definitely need to look at xprepare.c, especially at xdl_trim_ends() \n> and xdl_cleanup_records(). Lines are re-arranged in indexes, and this \n> might screw up your logic if you're not prepared for it.\n> What xdl_split() does, is find the start of an LCS and return the \n> coordinate. Then xdl_recs_cmp() does the box reducing (first two \"for\" \n> loops) and different-lines marking (first and second \"if\").\n\nWell it's what I thought it did indeed, that's why before recursing into\nthat bit, I tried to extract a full LCS from the patience diff algorithm\nand recurse into that for each interval it gives, which _should_ work,\nbut doesn't at all :/\n\nOkay maybe I should re-read my algorithm slowly and check that I've not\nmade something silly (like chaining the list in the reverse order or god\nknows what), but my debug functions let me believe that I did that fine.\n\nI'll look into it tonight.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"94893","messageId":"alpine.DEB.1.00.0811041447170.24407@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"20081104083042.GB3788@artemis.corp","subject":"Re: libxdiff and patience diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-04T14:34:37Z","receivedAt":"2008-11-04T14:34:37Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Nov 2008, Pierre Habouzit wrote:\n\n> On Tue, Nov 04, 2008 at 05:39:48AM +0000, Johannes Schindelin wrote:\n> \n> > On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> > \n> > > I've been working tonight, trying to make libxdiff support the \n> > > patience diff algorithm, but I've totally failed, because I \n> > > _thought_ I understood what xdl_split was doing, but it appears I \n> > > don't.\n> > \n> > I thought about it, too, at the GitTogether, although I want to finish \n> > my jGit diff first.\n> > \n> > The main idea I had about patience diff is that you can reuse a lot of \n> > functions in libxdiff.\n> > \n> > But the requirement of taking just unique lines/hashes into account, \n> > and _after_ splitting up, _again_ determine uniqueness _just_ in the \n> > between-hunk part made me think that it may be wiser to have a \n> > separate function for the patience diff stuff.\n> > \n> > Basically, you would start to have libxdiff split the lines and hash \n> > them as normal, but then determine the unique hashes (I'd start with \n> > the smaller text, just to have a better chance to end up with unique \n> > hashes).\n> > \n> > Once they are determined, you can search for those exact lines (hash \n> > first) in the post-document.\n> \n> Actually my current implementation just puts all the hashes into an \n> array, sorts them by hash (which is O(n log(n)) with the position from \n> left or right file it's in, ordered by increasing right position. (and \n> the struct is filled with the left pos to -1 if the right pos is set, \n> and vice versa).\n\nYeah, that would be much more efficient using a hash-multiset. Still \nlinear size (albeit twice as much). And you can already discard double \nentries early (although you have to keep one pointer in the hash-multiset \nto prevent other identical lines from being misdetected as \"unique\").\n\n> The I scan the array to find patterns of two consecutive hashes exactly, \n> and collapse it into the proper {left pos, right pos} tuple if it was \n> indeed a unique line in both files.\n> \n> This results into an array I sort again by right pos then, and we can \n> work on that for the stack sorting, and I do it, and then I have my LCS.\n> \n> \n> This is the complete brute-force algorithm which requires a temporary \n> array of the size of the number of lines on the left + the right, and a \n> temporary array for the stacks which _may_ end up being as large as the \n> smallest number of lines between the left or right file in the worst \n> case I'd say (roughly).\n> \n> Then I just remember a list of split points, and I recurse in all the\n> sub splits again. It has a fixed point which may or may not need\n> libxdiff recursion in it.\n\nI am not sure that you really end up with patience diff that way. I \n_think_ that you need to determine the longest sequence of unique lines \nwhich has the property of being ordered in both texts first, and only \n_then_ recurse into the not-yet-handled lines.\n\n> > Once that is done, you'd have to find the longest common subsequence, \n> > which you could do using the existing infrastructure, but that would \n> > require more work (as we already know the lines are unique).\n> \n> Patience diff gives you the algorithm to do that, it's pretty simple,\n> and is more efficient than the current infrastructure (in time, I don't\n> know for space though).\n\nActually, IIRC it is pretty easy to see that the time complexity is linear \n(and therefore, the space complexity, too).\n\n> > After that, you would have to recurse to the same algorithm _between_ \n> > known chunks. Eventually, that would have to resort to classical \n> > libxdiff (if there are no, or not enough, unique lines).\n> \n> Yeah, that's the point, the problem is, I believe more and more that I \n> should prepare the LCS from patience diff in xprepare.c, but I grok \n> absolutely nothing at what the chastore_t and similar stuff is. I \n> understand it's about hashing, but the exact stuff it does eludes me.\n\nYes, I do not like the short and unintuitive names either.\n\nAFAIU chastore_t is just a generic extensible array of elements that have \nsize \"isize\", and initially there are \"icount\" of them.\n\n> In fact when I look at the records I have in xdiffi.c I had the \n> impression they were already somehow collapsed, which makes it a too \n> late point to apply the patience diff ...\n\nAFAICS xdiffi.c contains the classical diff algorithm (incidentally, I the \ninventor of that algorithm is about 50 meters away from me at this very \nmoment). It should not have anything of interest to you, except for the \nfall-back case.\n\nSo I think that you should add a new file xpatience.c.\n\nIn that, I'd implement that hash multi-set, and use a prepared xdfenv_t to \nfill it (smaller file first, then you can traverse the other file, \nchecking for uniqueness in that file and for a match in the other file at \nthe same time).\n\nYou _could_ build the longest list of ordered pairs at the same time, too, \nbut that may make the code a bit too complex.\n\nCiao,\nDscho\n"},{"id":"94896","messageId":"20081104152351.GA21842@artemis.corp","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0811041447170.24407@pacific.mpi-cbg.de","subject":"Re: libxdiff and patience diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-04T15:23:51Z","receivedAt":"2008-11-04T15:23:51Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Nov 04, 2008 at 02:34:37PM +0000, Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> \n> > On Tue, Nov 04, 2008 at 05:39:48AM +0000, Johannes Schindelin wrote:\n> > \n> > > On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> > > \n> > > > I've been working tonight, trying to make libxdiff support the \n> > > > patience diff algorithm, but I've totally failed, because I \n> > > > _thought_ I understood what xdl_split was doing, but it appears I \n> > > > don't.\n> > > \n> > > I thought about it, too, at the GitTogether, although I want to finish \n> > > my jGit diff first.\n> > > \n> > > The main idea I had about patience diff is that you can reuse a lot of \n> > > functions in libxdiff.\n> > > \n> > > But the requirement of taking just unique lines/hashes into account, \n> > > and _after_ splitting up, _again_ determine uniqueness _just_ in the \n> > > between-hunk part made me think that it may be wiser to have a \n> > > separate function for the patience diff stuff.\n> > > \n> > > Basically, you would start to have libxdiff split the lines and hash \n> > > them as normal, but then determine the unique hashes (I'd start with \n> > > the smaller text, just to have a better chance to end up with unique \n> > > hashes).\n> > > \n> > > Once they are determined, you can search for those exact lines (hash \n> > > first) in the post-document.\n> > \n> > Actually my current implementation just puts all the hashes into an \n> > array, sorts them by hash (which is O(n log(n)) with the position from \n> > left or right file it's in, ordered by increasing right position. (and \n> > the struct is filled with the left pos to -1 if the right pos is set, \n> > and vice versa).\n> \n> Yeah, that would be much more efficient using a hash-multiset. Still \n> linear size (albeit twice as much). And you can already discard double \n> entries early (although you have to keep one pointer in the hash-multiset \n> to prevent other identical lines from being misdetected as \"unique\").\n\nProbably, I just wanted something to work first, and then optimize it\nusing the proper structure.\n\n> I am not sure that you really end up with patience diff that way. I \n> _think_ that you need to determine the longest sequence of unique lines \n> which has the property of being ordered in both texts first, and only \n> _then_ recurse into the not-yet-handled lines.\n\nI must have been using really bad english because it's what I do ;)\n\n> > > Once that is done, you'd have to find the longest common subsequence, \n> > > which you could do using the existing infrastructure, but that would \n> > > require more work (as we already know the lines are unique).\n> > \n> > Patience diff gives you the algorithm to do that, it's pretty simple,\n> > and is more efficient than the current infrastructure (in time, I don't\n> > know for space though).\n> \n> Actually, IIRC it is pretty easy to see that the time complexity is linear \n> (and therefore, the space complexity, too).\n\nWell the space complexity of the patience diff would be linear too for\nme, though I'm afraid that the current state of my implementation has a\nbig factor front ;)\n\n\n> > In fact when I look at the records I have in xdiffi.c I had the \n> > impression they were already somehow collapsed, which makes it a too \n> > late point to apply the patience diff ...\n> \n> AFAICS xdiffi.c contains the classical diff algorithm (incidentally, I the \n> inventor of that algorithm is about 50 meters away from me at this very \n> moment). It should not have anything of interest to you, except for the \n> fall-back case.\n> \n> So I think that you should add a new file xpatience.c.\n> \n> In that, I'd implement that hash multi-set, and use a prepared xdfenv_t to \n> fill it (smaller file first, then you can traverse the other file, \n> checking for uniqueness in that file and for a match in the other file at \n> the same time).\n> \n> You _could_ build the longest list of ordered pairs at the same time, too, \n> but that may make the code a bit too complex.\n\nWell, technically, if I'm correct, xdiffi.c already has a pruned list of\nhashed (I suppose ->ha is a hash value somehow ?) lines (pruned from\nlines without a match left or right), and I was massaging that. Though\nit absolutely fails so I fear I didn't understand what the ha stuff is\nfor real.\n\nAttached is my current work (YES it is horrible, it's WIP), probably\nmost of it can be put in an xpatience.c file, but still, I absolutely\ndon't understand what gets wrong. On the simple example from\nglandium.org it _looks_ like it catches the \"unique\" include line fine,\nbut somehow not.\n\nThe nasty thing about the patience diff is that it still needs the usual\ndiff algorithm once it has split the file into chunks separated by\n\"unique lines\". So you cannot make really independant stuff. What I\ncould do is put most of the xpatience diff into xpatience.c but it would\nstill have to use some functions from xdiffi.c that are currently\nprivate, so it messes somehow the files more than it's worth IMHO.\n\n\nAnyways, I'm waiting for a client to finally setup his network for the\ntest I'm supposed to do right now, I'll try to have a closer look\ntonight...\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n\n\ndiff --git a/diff.c b/diff.c\nindex f644947..0901cdc 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2447,6 +2447,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\toptions->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;\n \telse if (!strcmp(arg, \"--ignore-space-at-eol\"))\n \t\toptions->xdl_opts |= XDF_IGNORE_WHITESPACE_AT_EOL;\n+\telse if (!strcmp(arg, \"--patience\"))\n+\t\toptions->xdl_opts |= XDF_USE_PATIENCE;\n \n \t/* flags options */\n \telse if (!strcmp(arg, \"--binary\")) {\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 84fff58..bba915c 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -32,6 +32,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE (1 << 2)\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n+#define XDF_USE_PATIENCE (1 << 5)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 9d0324a..1a5b13a 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -37,8 +37,235 @@ typedef struct s_xdpsplit {\n \tint min_lo, min_hi;\n } xdpsplit_t;\n \n+typedef struct s_xduniqmatch {\n+\tstruct s_xduniqmatch *next;\n+\tlong i1, i2, len;\n+} xduniqmatch_t;\n+\n+typedef struct s_xdp_ha {\n+\tstruct s_xdp_ha *up, *down;\n+\tstruct s_xdp_ha *left;\n+\tlong ha;\n+\tlong off1;\n+\tlong off2;\n+} xdp_ha_t;\n+\n+\n+static xduniqmatch_t *xdl_uniq_match_alloc(long i1, long i2, long len)\n+{\n+\txduniqmatch_t *match = xdl_malloc(sizeof(xduniqmatch_t));\n+\tif (match) {\n+\t\tmatch->next = NULL;\n+\t\tmatch->i1 = i1;\n+\t\tmatch->i2 = i2;\n+\t\tmatch->len = len;\n+\t}\n+\treturn match;\n+}\n+\n+static xduniqmatch_t *xdl_uniq_popfree(xduniqmatch_t *lst)\n+{\n+\txduniqmatch_t *next = lst->next;\n+\txdl_free(lst);\n+\treturn next;\n+}\n+\n+static int xdp_ha_cmp_by_ha(const void *a1, const void *a2)\n+{\n+\tconst xdp_ha_t *ha1 = a1;\n+\tconst xdp_ha_t *ha2 = a2;\n+\tif (ha1->ha == ha2->ha) {\n+\t\treturn ha1->off2 - ha2->off2;\n+\t}\n+\treturn ha1->ha - ha2->ha;\n+}\n+\n+static int xdp_ha_cmp_by_off2(const void *a1, const void *a2)\n+{\n+\tconst xdp_ha_t *ha1 = a1;\n+\tconst xdp_ha_t *ha2 = a2;\n+\treturn ha2->off2 - ha1->off2;\n+}\n+\n+static int patience_bisect_stack(xdp_ha_t **stacks, long len, long off1)\n+{\n+\tlong l = 0, r = len;\n+\n+\twhile (l < r) {\n+\t\tlong i = (r + l) / 2;\n+\n+\t\tif (off1 < stacks[i]->off1) {\n+\t\t\tl = i + 1;\n+\t\t} else {\n+\t\t\tr = i;\n+\t\t}\n+\t}\n+\treturn l;\n+}\n+\n+static int xdl_patience_split_aux(xduniqmatch_t *lcs, xdp_ha_t *ha)\n+{\n+\txduniqmatch_t *tmp;\n+\n+\twhile (ha) {\n+\t\ttmp = xdl_uniq_match_alloc(ha->off1, ha->off2, 1);\n+\t\tif (!tmp)\n+\t\t\treturn -1;\n+\t\ttmp->next = lcs->next;\n+\t\tlcs->next = tmp;\n+\t\tlcs = tmp;\n+\n+\t\twhile ((ha = ha->down ? ha->down : ha->left)) {\n+\t\t\tif (lcs->i1 + lcs->len + 1 == ha->off1 && lcs->i2 + lcs->len + 1 == ha->off2) {\n+\t\t\t\tlcs->len++;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n+static int xdl_patience_split(unsigned long const *ha1, unsigned long const *ha2,\n+\t\t\t xduniqmatch_t *begin, xduniqmatch_t *end)\n+{\n+\txdp_ha_t *recs;\n+\tlong off1 = begin->i1 + begin->len, lim1 = end->i1;\n+\tlong off2 = begin->i2 + begin->len, lim2 = end->i2;\n+\tlong len, i, j, uniq;\n+\n+\tlen = lim1 - off1 + lim2 - off2;\n+\trecs = (xdp_ha_t *)xdl_malloc(sizeof(xdp_ha_t) * len);\n+\tif (recs == NULL)\n+\t\treturn -1;\n+\n+\tfor (i = 0, j = off1; j < lim1 - off1; j++, i++) {\n+\t\trecs[i].ha = ha1[j];\n+\t\trecs[i].off1 = j;\n+\t\trecs[i].off2 = -1;\n+\t\trecs[i].up = recs[i].down = recs[i].left = NULL;\n+\t}\n+\tfor (j = off2; j < lim2; j++, i++) {\n+\t\trecs[i].ha = ha2[j];\n+\t\trecs[i].off1 = -1;\n+\t\trecs[i].off2 = j;\n+\t\trecs[i].up = recs[i].down = recs[i].left = NULL;\n+\t}\n+\n+\tqsort(recs, len, sizeof(xdp_ha_t), xdp_ha_cmp_by_ha);\n+\n+\tuniq = 0;\n+\tfor (i = 0; i < len - 1; ) {\n+\t\tlong ha = recs[i].ha;\n+\n+\t\tif (ha != recs[i + 1].ha) {\n+\t\t\ti++;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (i < len - 2 && ha == recs[i + 2].ha) {\n+\t\t\ti += 3;\n+\t\t\twhile (i < len - 1 && recs[i].ha == ha && i < len - 1) {\n+\t\t\t\ti++;\n+\t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (recs[i].off2 < 0 && recs[i + 1].off1 < 0) {\n+\t\t\tlong a, b;\n+\t\t\trecs[uniq].ha = ha;\n+\t\t\ta = recs[uniq].off1 = recs[i].off1;\n+\t\t\tb = recs[uniq].off2 = recs[i + 1].off2;\n+\t\t\tuniq++;\n+\t\t}\n+\t\ti += 2;\n+\t}\n+\n+\tif (uniq) {\n+\t\txdp_ha_t **stacks;\n+\t\tlong alloc, len;\n+\n+\t\tqsort(recs, uniq, sizeof(xdp_ha_t), xdp_ha_cmp_by_off2);\n+\n+\t\talloc = xdl_bogosqrt(uniq);\n+\t\tstacks = xdl_malloc(sizeof(xdp_ha_t *) * alloc);\n \n+\t\tif (stacks == NULL)\n+\t\t\tgoto error;\n \n+\t\tlen = 1;\n+\t\tstacks[0] = recs;\n+\n+\t\tfor (i = 1; i < uniq; i++) {\n+\t\t\tlong off1 = recs[i].off1;\n+\t\t\tlong k;\n+\n+\t\t\tif (off1 < stacks[len - 1]->off1) {\n+\t\t\t\tif (len >= alloc) {\n+\t\t\t\t\talloc *= 2;\n+\t\t\t\t\tstacks = xdl_realloc(stacks, sizeof(xdp_ha_t *) * alloc);\n+\t\t\t\t\tif (!stacks)\n+\t\t\t\t\t\tgoto error;\n+\t\t\t\t}\n+\t\t\t\tstacks[k = len++] = NULL;\n+\t\t\t} else {\n+\t\t\t\tk = patience_bisect_stack(stacks, len - 1, off1);\n+\t\t\t}\n+\n+\t\t\tif (k > 0) {\n+\t\t\t\trecs[i].left = stacks[k - 1];\n+\t\t\t}\n+\t\t\tif (stacks[k]) {\n+\t\t\t\tstacks[k]->down = &recs[i];\n+\t\t\t\trecs[i].up = stacks[k];\n+\t\t\t}\n+\t\t\tstacks[k] = &recs[i];\n+\t\t}\n+\n+\t\tif (xdl_patience_split_aux(begin, stacks[len - 1]) < 0) {\n+\t\t\txdl_free(stacks);\n+\t\t\tgoto error;\n+\t\t}\n+\n+\t\txdl_free(stacks);\n+\t}\n+\n+\txdl_free(recs);\n+\treturn 0;\n+\n+error:\n+\txdl_free(recs);\n+\treturn -1;\n+}\n+\n+static int xdl_patience_lcs(xdfenv_t *xe, xduniqmatch_t *begin, xduniqmatch_t *end)\n+{\n+\tunsigned long const *ha1 = xe->xdf1.ha, *ha2 = xe->xdf2.ha;\n+\tlong off1 = begin->i1 + begin->len, lim1 = end->i1;\n+\tlong off2 = begin->i2 + begin->len, lim2 = end->i2;\n+\txduniqmatch_t *next;\n+\n+\tfor (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);\n+\tfor (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);\n+\n+\tbegin->len += off1 - begin->i1;\n+\tend->len += end->i1 - lim1;\n+\tend->i1 = lim1;\n+\tend->i2 = lim2;\n+\n+\tif (off1 == lim1 || off2 == lim2)\n+\t\treturn 0;\n+\n+\tif (xdl_patience_split(ha1, ha2, begin, end))\n+\t\treturn -1;\n+\n+\tfor (next = begin->next; next != end; begin = next, next = begin->next) {\n+\t\tif (xdl_patience_lcs(xe, begin, next) < 0)\n+\t\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n \n static long xdl_split(unsigned long const *ha1, long off1, long lim1,\n \t\t unsigned long const *ha2, long off2, long lim2,\n@@ -321,13 +548,13 @@ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,\n \treturn 0;\n }\n \n-\n int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\txdfenv_t *xe) {\n \tlong ndiags;\n \tlong *kvd, *kvdf, *kvdb;\n \txdalgoenv_t xenv;\n \tdiffdata_t dd1, dd2;\n+\tint need_min = (xpp->flags & XDF_NEED_MINIMAL) != 0;\n \n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n@@ -364,12 +591,54 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tdd2.rchg = xe->xdf2.rchg;\n \tdd2.rindex = xe->xdf2.rindex;\n \n-\tif (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,\n-\t\t\t kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {\n+\tif (xpp->flags & XDF_USE_PATIENCE) {\n+\t\txduniqmatch_t *lcs;\n+\t\tlong i1, i2;\n+\n+\t\tlcs = xdl_uniq_match_alloc(0, 0, 0);\n+\t\tif (!lcs)\n+\t\t\tgoto error;\n+\t\tlcs->next = xdl_uniq_match_alloc(xe->xdf1.nreff, xe->xdf2.nreff, 0);\n+\t\tif (!lcs->next || xdl_patience_lcs(xe, lcs, lcs->next) < 0) {\n+\t\t\twhile ((lcs = xdl_uniq_popfree(lcs)));\n+\t\t\tgoto error;\n+\t\t}\n \n-\t\txdl_free(kvd);\n-\t\txdl_free_env(xe);\n-\t\treturn -1;\n+\t\ti1 = i2 = lcs->len;\n+\t\tif (lcs->len) {\n+\t\t\tfprintf(stderr, \"skip %ld:%ld -> %ld:%ld\\n\",\n+\t\t\t\tlcs->i1, i1, lcs->i2, i2);\n+\t\t}\n+\n+\t\twhile ((lcs = xdl_uniq_popfree(lcs))) {\n+\t\t\tfprintf(stderr, \"usual %ld:%ld -> %ld:%ld\\n\",\n+\t\t\t\ti1, lcs->i1, i2, lcs->i2);\n+\t\t\tfprintf(stderr, \"l/r: %ld / %ld\\n\",\n+\t\t\t\txe->xdf1.rindex[lcs->i1],\n+\t\t\t\txe->xdf2.rindex[lcs->i2]);\n+\t\t\tif (xdl_recs_cmp(&dd1, i1, lcs->i1, &dd2, i2, lcs->i2,\n+\t\t\t\t\t kvdf, kvdb, need_min, &xenv) < 0) {\n+\t\t\t\twhile ((lcs = xdl_uniq_popfree(lcs)));\n+\t\t\t\tgoto error;\n+\t\t\t}\n+\t\t\ti1 = lcs->i1 + lcs->len;\n+\t\t\ti2 = lcs->i2 + lcs->len;\n+\t\t\tif (lcs->len) {\n+\t\t\t\tfprintf(stderr, \"skip %ld:%ld -> %ld:%ld (len %ld)\\n\",\n+\t\t\t\t\tlcs->i1, i1, lcs->i2, i2, lcs->len);\n+\t\t\t\tfprintf(stderr, \"l/r: %ld / %ld\\n\",\n+\t\t\t\t\txe->xdf1.rindex[lcs->i1 + lcs->len],\n+\t\t\t\t\txe->xdf2.rindex[lcs->i2 + lcs->len]);\n+\t\t\t}\n+\t\t}\n+\t} else {\n+\t\tif (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,\n+\t\t\t\t kvdf, kvdb, need_min, &xenv) < 0) {\n+error:\n+\t\t\txdl_free(kvd);\n+\t\t\txdl_free_env(xe);\n+\t\t\treturn -1;\n+\t\t}\n \t}\n \n \txdl_free(kvd);\n"},{"id":"94897","messageId":"alpine.DEB.1.00.0811041650510.24407@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"20081104152351.GA21842@artemis.corp","subject":"Re: libxdiff and patience diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-04T15:57:44Z","receivedAt":"2008-11-04T15:57:44Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 4 Nov 2008, Pierre Habouzit wrote:\n\n> The nasty thing about the patience diff is that it still needs the usual\n> diff algorithm once it has split the file into chunks separated by\n> \"unique lines\".\n\nActually, it should try to apply patience diff again in those chunks, \nseparately.\n\n> So you cannot make really independant stuff. What I could do is put most \n> of the xpatience diff into xpatience.c but it would still have to use \n> some functions from xdiffi.c that are currently private, so it messes \n> somehow the files more than it's worth IMHO.\n\nI think it is better that you use the stuff from xdiffi.c through a well \ndefined interface, i.e. _not_ mess up the code by mingling it together \nwith the code in xdiffi.c. The code is hard enough to read already.\n\nOh, BTW, \"ha\" is a hash of the lines which is used to make the line \nmatching more performant. You will see a lot of \"ha\" comparisons before \nactually calling xdl_recmatch() for that reason. Incidentally, this is \nalso the hash that I'd use for the hash multi-set I was referring to.\n\nOh, and I am not sure that it is worth your time trying to get it to run \nwith the linear list, since you cannot reuse that code afterwards, and \nhave to spend the same amount of time to redo it with the hash set.\n\nI am awfully short on time, so it will take some days until I can review \nwhat you have already, unfortunately.\n\nCiao,\nDscho\n"},{"id":"94898","messageId":"20081104161548.GB21842@artemis.corp","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0811041650510.24407@pacific.mpi-cbg.de","subject":"Re: libxdiff and patience diff","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-11-04T16:15:48Z","receivedAt":"2008-11-04T16:15:48Z","isPatch":false,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Nov 04, 2008 at 03:57:44PM +0000, Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 4 Nov 2008, Pierre Habouzit wrote:\n> \n> > The nasty thing about the patience diff is that it still needs the usual\n> > diff algorithm once it has split the file into chunks separated by\n> > \"unique lines\".\n> \n> Actually, it should try to apply patience diff again in those chunks, \n> separately.\n\nyes it's what I do, but this has a fixed point as soon as you don't find\nunique lines between the new found ones, or that that space is \"empty\".\nE.g. you could have the two following hunks:\n\nFile A File B\n1 2\n2 1\n1 2\n2 1\n1 2\n2\n1\n\nThe simple leading/trailing reduction will do nothing, and you don't\nhave any shared unique lines, on that you must apply the usual diff\nalgorithm.\n\n> > So you cannot make really independant stuff. What I could do is put most \n> > of the xpatience diff into xpatience.c but it would still have to use \n> > some functions from xdiffi.c that are currently private, so it messes \n> > somehow the files more than it's worth IMHO.\n> \n> I think it is better that you use the stuff from xdiffi.c through a well \n> defined interface, i.e. _not_ mess up the code by mingling it together \n> with the code in xdiffi.c. The code is hard enough to read already.\n\nHmmm. I'll see to that later, once I have something that works.\n\n> Oh, BTW, \"ha\" is a hash of the lines which is used to make the line \n> matching more performant. You will see a lot of \"ha\" comparisons before \n> actually calling xdl_recmatch() for that reason. Incidentally, this is \n> also the hash that I'd use for the hash multi-set I was referring to.\n\nYeah, that's what I assumed it would be.\n\n> Oh, and I am not sure that it is worth your time trying to get it to run \n> with the linear list, since you cannot reuse that code afterwards, and \n> have to spend the same amount of time to redo it with the hash set.\n\nHaving the linear list (actually an array) work would show me I hook at\nthe proper place. Replacing a data structure doesn't makes me afraid\nbecause I've split the functions properly.\n\n> I am awfully short on time, so it will take some days until I can review \n> what you have already, unfortunately.\n\nNP, it was just in case, because I'm horribly stuck with that code right\nnow ;)\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"99084","messageId":"alpine.DEB.1.00.0901011730190.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"20081104152351.GA21842@artemis.corp","subject":"[PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-01T16:38:09Z","receivedAt":"2009-01-01T16:38:09Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nNothing fancy, really, just a straight-forward implementation of the\nheavily under-documented and under-analyzed paience diff algorithm.\n\nOne thing is a bit ugly: the libxdiff interface does not allow to\ncalculate diffs of ranges of lines. So instead of reusing an initialized\nenvironment (with line hashes and all), the simple structure of mmfile_t\nis exploited to fake an mmfile_t of a file _part_, reusing the file's\nbuffer.\n\nAnd this mmfile_t pair gets a new environment, recalculating hashes and \nall.\n\nDavide, I think it would be easier to refactor xdl_do_diff() to take line\nranges, and use that interface both in xpatience.c and in xmerge.c. \n(Although I do not know if you took xmerge.c at all; you seemed a bit \nreluctant about it back when I sent it to you.)\n\nFor those interested in studying the code, I suggest starting with the \nshort comment at the beginning of xpatience.c and then working yourself up \nfrom the end (i.e. xdl_do_patience_diff()).\n\nIt might be a good idea to think about using this code in our merging code\nonce it is well reviewed and tested, as it might help a substantial number\nof otherwise non-trivial merge conflicts.\n\nOh, and the bash completions are so trivial I did not even bother to test\nthem.\n\nHappy new year.\n\nJohannes Schindelin (3):\n Implement the patience diff algorithm\n Introduce the diff option '--patience'\n bash completions: Add the --patience option\n\n Documentation/diff-options.txt | 3 +\n Makefile | 2 +-\n contrib/completion/git-completion.bash | 2 +\n diff.c | 2 +\n t/t4033-diff-patience.sh | 168 ++++++++++++++\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xpatience.c | 374 ++++++++++++++++++++++++++++++++\n 9 files changed, 556 insertions(+), 1 deletions(-)\n create mode 100755 t/t4033-diff-patience.sh\n create mode 100644 xdiff/xpatience.c\n"},{"id":"99085","messageId":"alpine.DEB.1.00.0901011738240.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901011730190.30769@pacific.mpi-cbg.de","subject":"[PATCH 1/3] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-01T16:38:38Z","receivedAt":"2009-01-01T16:38:38Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nThe patience diff algorithm produces slightly more intuitive output\nthan the classic Myers algorithm, as it does not try to minimize the\nnumber of +/- lines first, but tries to preserve the lines that are\nunique.\n\nTo this end, it first determines lines that are unique in both files,\nthen the maximal sequence which preserves the order (relative to both\nfiles) is extracted.\n\nStarting from this initial set of common lines, the rest of the lines\nis handled recursively, with Myers' algorithm as a fallback when\nthe patience algorithm fails (due to no common unique lines).\n\nSigned-off-by: Johannes Schindelin \n---\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xpatience.c | 374 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 380 insertions(+), 0 deletions(-)\n create mode 100644 xdiff/xpatience.c\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 361f802..4da052a 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -32,6 +32,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE (1 << 2)\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n+#define XDF_PATIENCE_DIFF (1 << 5)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 9d0324a..3e97462 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -329,6 +329,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \txdalgoenv_t xenv;\n \tdiffdata_t dd1, dd2;\n \n+\tif (xpp->flags & XDF_PATIENCE_DIFF)\n+\t\treturn xdl_do_patience_diff(mf1, mf2, xpp, xe);\n+\n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n \t\treturn -1;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex 3e099dc..ad033a8 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -55,5 +55,7 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);\n void xdl_free_script(xdchange_t *xscr);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg);\n+int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *env);\n \n #endif /* #if !defined(XDIFFI_H) */\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nnew file mode 100644\nindex 0000000..6687940\n--- /dev/null\n+++ b/xdiff/xpatience.c\n@@ -0,0 +1,374 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+#include \"xinclude.h\"\n+#include \"xtypes.h\"\n+#include \"xdiff.h\"\n+\n+/*\n+ * The basic idea of patience diff is to find lines that are unique in\n+ * both files. These are intuitively the ones that we want to see as\n+ * common lines.\n+ *\n+ * The maximal ordered sequence of such line pairs (where ordered means\n+ * that the order in the sequence agrees with the order of the lines in\n+ * both files) naturally defines an initial set of common lines.\n+ *\n+ * Now, the algorithm tries to extend the set of common lines by growing\n+ * the line ranges where the files have identical lines.\n+ *\n+ * Between those common lines, the patience diff algorithm is applied\n+ * recursively, until no unique line pairs can be found; these line ranges\n+ * are handled by the well-known Myers algorithm.\n+ */\n+\n+#define NON_UNIQUE ULONG_MAX\n+\n+/*\n+ * This is a hash mapping from line hash to line numbers in the first and\n+ * second file.\n+ */\n+struct hashmap {\n+\tint nr, alloc;\n+\tstruct entry {\n+\t\tunsigned long hash;\n+\t\t/*\n+\t\t * 0 = unused entry, 1 = first line, 2 = second, etc.\n+\t\t * line2 is NON_UNIQUE if the line is not unique\n+\t\t * in either the first or the second file.\n+\t\t */\n+\t\tunsigned long line1, line2;\n+\t\t/*\n+\t\t * \"next\" & \"previous\" are used for the longest common\n+\t\t * sequence;\n+\t\t * initially, \"next\" reflects only the order in file1.\n+\t\t */\n+\t\tstruct entry *next, *previous;\n+\t} *entries, *first, *last;\n+\t/* were common records found? */\n+\tunsigned long has_matches;\n+\tmmfile_t *file1, *file2;\n+\txdfenv_t *env;\n+\txpparam_t const *xpp;\n+};\n+\n+/* The argument \"pass\" is 1 for the first file, 2 for the second. */\n+static void insert_record(int line, struct hashmap *map, int pass)\n+{\n+\txrecord_t **records = pass == 1 ?\n+\t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n+\txrecord_t *record = records[line - 1], *other;\n+\t/*\n+\t * After xdl_prepare_env() (or more precisely, due to\n+\t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n+\t * is _not_ the hash anymore, but a linearized version of it. In\n+\t * other words, the \"ha\" member is guaranteed to start with 0 and\n+\t * the second record's ha can only be 0 or 1, etc.\n+\t *\n+\t * So we multiply ha by 2 in the hope that the hashing was\n+\t * \"unique enough\".\n+\t */\n+\tint index = (int)((record->ha << 1) % map->alloc);\n+\n+\twhile (map->entries[index].line1) {\n+\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n+\t\tif (map->entries[index].hash != record->ha ||\n+\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n+\t\t\t\t\tother->ptr, other->size,\n+\t\t\t\t\tmap->xpp->flags)) {\n+\t\t\tif (++index >= map->alloc)\n+\t\t\t\tindex = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (pass == 2)\n+\t\t\tmap->has_matches = 1;\n+\t\tif (pass == 1 || map->entries[index].line2)\n+\t\t\tmap->entries[index].line2 = NON_UNIQUE;\n+\t\telse\n+\t\t\tmap->entries[index].line2 = line;\n+\t\treturn;\n+\t}\n+\tif (pass == 2)\n+\t\treturn;\n+\tmap->entries[index].line1 = line;\n+\tmap->entries[index].hash = record->ha;\n+\tif (!map->first)\n+\t\tmap->first = map->entries + index;\n+\tif (map->last) {\n+\t\tmap->last->next = map->entries + index;\n+\t\tmap->entries[index].previous = map->last;\n+\t}\n+\tmap->last = map->entries + index;\n+\tmap->nr++;\n+}\n+\n+/*\n+ * This function has to be called for each recursion into the inter-hunk\n+ * parts, as previously non-unique lines can become unique when being\n+ * restricted to a smaller part of the files.\n+ *\n+ * It is assumed that env has been prepared using xdl_prepare().\n+ */\n+static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tstruct hashmap *result,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tresult->file1 = file1;\n+\tresult->file2 = file2;\n+\tresult->xpp = xpp;\n+\tresult->env = env;\n+\n+\t/* We know exactly how large we want the hash map */\n+\tresult->alloc = count1 * 2;\n+\tresult->entries = (struct entry *)\n+\t\txdl_malloc(result->alloc * sizeof(struct entry));\n+\tif (!result->entries)\n+\t\treturn -1;\n+\tmemset(result->entries, 0, result->alloc * sizeof(struct entry));\n+\n+\t/* First, fill with entries from the first file */\n+\twhile (count1--)\n+\t\tinsert_record(line1++, result, 1);\n+\n+\t/* Then search for matches in the second file */\n+\twhile (count2--)\n+\t\tinsert_record(line2++, result, 2);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Find the longest sequence with a smaller last element (meaning a smaller\n+ * line2, as we construct the sequence with entries ordered by line1).\n+ */\n+static int binary_search(struct entry **sequence, int longest,\n+\t\tstruct entry *entry)\n+{\n+\tint left = -1, right = longest;\n+\n+\twhile (left + 1 < right) {\n+\t\tint middle = (left + right) / 2;\n+\t\t/* by construction, no two entries can be equal */\n+\t\tif (sequence[middle]->line2 > entry->line2)\n+\t\t\tright = middle;\n+\t\telse\n+\t\t\tleft = middle;\n+\t}\n+\t/* return the index in \"sequence\", _not_ the sequence length */\n+\treturn left;\n+}\n+\n+/*\n+ * The idea is to start with the list of common unique lines sorted by\n+ * the order in file1. For each of these pairs, the longest (partial)\n+ * sequence whose last element's line2 is smaller is determined.\n+ *\n+ * For efficiency, the sequences are kept in a list containing exactly one\n+ * item per sequence length: the sequence with the smallest last\n+ * element (in terms of line2).\n+ */\n+static struct entry *find_longest_common_sequence(struct hashmap *map)\n+{\n+\tstruct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));\n+\tint longest = 0, i;\n+\tstruct entry *entry;\n+\n+\tfor (entry = map->first; entry; entry = entry->next) {\n+\t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n+\t\t\tcontinue;\n+\t\ti = binary_search(sequence, longest, entry);\n+\t\tentry->previous = i < 0 ? NULL : sequence[i];\n+\t\tsequence[++i] = entry;\n+\t\tif (i == longest)\n+\t\t\tlongest++;\n+\t}\n+\n+\t/* No common unique lines were found */\n+\tif (!longest)\n+\t\treturn NULL;\n+\n+\t/* Iterate starting at the last element, adjusting the \"next\" members */\n+\tentry = sequence[longest - 1];\n+\tentry->next = NULL;\n+\twhile (entry->previous) {\n+\t\tentry->previous->next = entry;\n+\t\tentry = entry->previous;\n+\t}\n+\treturn entry;\n+}\n+\n+static int match(struct hashmap *map, int line1, int line2)\n+{\n+\txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n+\txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n+\treturn xdl_recmatch(record1->ptr, record1->size,\n+\t\trecord2->ptr, record2->size, map->xpp->flags);\n+}\n+\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2);\n+\n+static int walk_common_sequence(struct hashmap *map, struct entry *first,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tint end1 = line1 + count1, end2 = line2 + count2;\n+\tint next1, next2;\n+\n+\tfor (;;) {\n+\t\t/* Try to grow the line ranges of common lines */\n+\t\tif (first) {\n+\t\t\tnext1 = first->line1;\n+\t\t\tnext2 = first->line2;\n+\t\t\twhile (next1 > line1 && next2 > line2 &&\n+\t\t\t\t\tmatch(map, next1 - 1, next2 - 1)) {\n+\t\t\t\tnext1--;\n+\t\t\t\tnext2--;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tnext1 = end1;\n+\t\t\tnext2 = end2;\n+\t\t}\n+\t\twhile (line1 < next1 && line2 < next2 &&\n+\t\t\t\tmatch(map, line1, line2)) {\n+\t\t\tline1++;\n+\t\t\tline2++;\n+\t\t}\n+\n+\t\t/* Recurse */\n+\t\tif (next1 > line1 || next2 > line2) {\n+\t\t\tstruct hashmap submap;\n+\n+\t\t\tmemset(&submap, 0, sizeof(submap));\n+\t\t\tif (patience_diff(map->file1, map->file2,\n+\t\t\t\t\tmap->xpp, map->env,\n+\t\t\t\t\tline1, next1 - line1,\n+\t\t\t\t\tline2, next2 - line2))\n+\t\t\t\treturn -1;\n+\t\t}\n+\n+\t\tif (!first)\n+\t\t\treturn 0;\n+\n+\t\twhile (first->next &&\n+\t\t\t\tfirst->next->line1 == first->line1 + 1 &&\n+\t\t\t\tfirst->next->line2 == first->line2 + 1)\n+\t\t\tfirst = first->next;\n+\n+\t\tline1 = first->line1 + 1;\n+\t\tline2 = first->line2 + 1;\n+\n+\t\tfirst = first->next;\n+\t}\n+}\n+\n+static int fall_back_to_classic_diff(struct hashmap *map,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\t/*\n+\t * This probably does not work outside Git, since\n+\t * we have a very simple mmfile structure.\n+\t *\n+\t * Note: ideally, we would reuse the prepared environment, but\n+\t * the libxdiff interface does not (yet) allow for diffing only\n+\t * ranges of lines instead of the whole files.\n+\t */\n+\tmmfile_t subfile1, subfile2;\n+\txpparam_t xpp;\n+\txdfenv_t env;\n+\n+\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n+\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n+\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n+\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n+\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n+\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n+\txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n+\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n+\t\treturn -1;\n+\n+\tmemcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n+\tmemcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Recursively find the longest common sequence of unique lines,\n+ * and if none was found, ask xdl_do_diff() to do the job.\n+ *\n+ * This function assumes that env was prepared with xdl_prepare_env().\n+ */\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct hashmap map;\n+\tstruct entry *first;\n+\tint result = 0;\n+\n+\t/* trivial case: one side is empty */\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tmemset(&map, 0, sizeof(map));\n+\tif (fill_hashmap(file1, file2, xpp, env, &map,\n+\t\t\tline1, count1, line2, count2))\n+\t\treturn -1;\n+\n+\t/* are there any matching lines at all? */\n+\tif (!map.has_matches) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tfirst = find_longest_common_sequence(&map);\n+\tif (first)\n+\t\tresult = walk_common_sequence(&map, first,\n+\t\t\tline1, count1, line2, count2);\n+\telse\n+\t\tresult = fall_back_to_classic_diff(&map,\n+\t\t\tline1, count1, line2, count2);\n+\n+\treturn result;\n+}\n+\n+int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env)\n+{\n+\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n+\t\treturn -1;\n+\n+\t/* environment is cleaned up in xdl_diff() */\n+\treturn patience_diff(file1, file2, xpp, env,\n+\t\t\t1, env->xdf1.nrec, 1, env->xdf2.nrec);\n+}\n-- \n1.6.1.rc3.412.ga72b\n"},{"id":"99087","messageId":"alpine.DEB.1.00.0901011738430.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901011730190.30769@pacific.mpi-cbg.de","subject":"[PATCH 2/3] Introduce the diff option '--patience'","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-01T16:39:17Z","receivedAt":"2009-01-01T16:39:17Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nThis commit teaches Git to produce diff output using the patience diff\nalgorithm with the diff option '--patience'.\n\nSigned-off-by: Johannes Schindelin \n---\n\n\tgit log --check complains about this patch, for obvious reasons.\n\n Documentation/diff-options.txt | 3 +\n Makefile | 2 +-\n diff.c | 2 +\n t/t4033-diff-patience.sh | 168 ++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 174 insertions(+), 1 deletions(-)\n create mode 100755 t/t4033-diff-patience.sh\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 671f533..15ef35a 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -36,6 +36,9 @@ endif::git-format-patch[]\n --patch-with-raw::\n \tSynonym for \"-p --raw\".\n \n+--patience:\n+\tGenerate a diff using the \"patience diff\" algorithm.\n+\n --stat[=width[,name-width]]::\n \tGenerate a diffstat. You can override the default\n \toutput width for 80-column terminal by \"--stat=width\".\ndiff --git a/Makefile b/Makefile\nindex 154cf34..2217873 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1287,7 +1287,7 @@ $(LIB_FILE): $(LIB_OBJS)\n \t$(QUIET_AR)$(RM) $@ && $(AR) rcs $@ $(LIB_OBJS)\n \n XDIFF_OBJS=xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \\\n-\txdiff/xmerge.o\n+\txdiff/xmerge.o xdiff/xpatience.o\n $(XDIFF_OBJS): xdiff/xinclude.h xdiff/xmacros.h xdiff/xdiff.h xdiff/xtypes.h \\\n \txdiff/xutils.h xdiff/xprepare.h xdiff/xdiffi.h xdiff/xemit.h\n \ndiff --git a/diff.c b/diff.c\nindex 56b80f9..67718b7 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2472,6 +2472,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\toptions->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;\n \telse if (!strcmp(arg, \"--ignore-space-at-eol\"))\n \t\toptions->xdl_opts |= XDF_IGNORE_WHITESPACE_AT_EOL;\n+\telse if (!strcmp(arg, \"--patience\"))\n+\t\toptions->xdl_opts |= XDF_PATIENCE_DIFF;\n \n \t/* flags options */\n \telse if (!strcmp(arg, \"--binary\")) {\ndiff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\nnew file mode 100755\nindex 0000000..63c1b00\n--- /dev/null\n+++ b/t/t4033-diff-patience.sh\n@@ -0,0 +1,168 @@\n+#!/bin/sh\n+\n+test_description='patience diff algorithm'\n+\n+. ./test-lib.sh\n+\n+cat > file1 << EOF\n+#include \n+\n+// Frobs foo heartily\n+int frobnitz(int foo)\n+{\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+ printf(\"Your answer is: \");\n+ printf(\"%d\\n\", foo);\n+ }\n+}\n+\n+int fact(int n)\n+{\n+ if(n > 1)\n+ {\n+ return fact(n-1) * n;\n+ }\n+ return 1;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+ frobnitz(fact(10));\n+}\n+EOF\n+\n+cat > file2 << EOF\n+#include \n+\n+int fib(int n)\n+{\n+ if(n > 2)\n+ {\n+ return fib(n-1) + fib(n-2);\n+ }\n+ return 1;\n+}\n+\n+// Frobs foo heartily\n+int frobnitz(int foo)\n+{\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+ printf(\"%d\\n\", foo);\n+ }\n+}\n+\n+int main(int argc, char **argv)\n+{\n+ frobnitz(fib(10));\n+}\n+EOF\n+\n+cat > expect << EOF\n+diff --git a/file1 b/file2\n+index 6faa5a3..e3af329 100644\n+--- a/file1\n++++ b/file2\n+@@ -1,26 +1,25 @@\n+ #include \n+ \n++int fib(int n)\n++{\n++ if(n > 2)\n++ {\n++ return fib(n-1) + fib(n-2);\n++ }\n++ return 1;\n++}\n++\n+ // Frobs foo heartily\n+ int frobnitz(int foo)\n+ {\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+- printf(\"Your answer is: \");\n+ printf(\"%d\\n\", foo);\n+ }\n+ }\n+ \n+-int fact(int n)\n+-{\n+- if(n > 1)\n+- {\n+- return fact(n-1) * n;\n+- }\n+- return 1;\n+-}\n+-\n+ int main(int argc, char **argv)\n+ {\n+- frobnitz(fact(10));\n++ frobnitz(fib(10));\n+ }\n+EOF\n+\n+test_expect_success 'patience diff' '\n+\n+\ttest_must_fail git diff --no-index --patience file1 file2 > output &&\n+\ttest_cmp expect output\n+\n+'\n+\n+test_expect_success 'patience diff output is valid' '\n+\n+\tmv file2 expect &&\n+\tgit apply < output &&\n+\ttest_cmp expect file2\n+\n+'\n+\n+cat > uniq1 << EOF\n+1\n+2\n+3\n+4\n+5\n+6\n+EOF\n+\n+cat > uniq2 << EOF\n+a\n+b\n+c\n+d\n+e\n+f\n+EOF\n+\n+cat > expect << EOF\n+diff --git a/uniq1 b/uniq2\n+index b414108..0fdf397 100644\n+--- a/uniq1\n++++ b/uniq2\n+@@ -1,6 +1,6 @@\n+-1\n+-2\n+-3\n+-4\n+-5\n+-6\n++a\n++b\n++c\n++d\n++e\n++f\n+EOF\n+\n+test_expect_success 'completely different files' '\n+\n+\ttest_must_fail git diff --no-index --patience uniq1 uniq2 > output &&\n+\ttest_cmp expect output\n+\n+'\n+\n+test_done\n-- \n1.6.1.rc3.412.ga72b\n"},{"id":"99086","messageId":"alpine.DEB.1.00.0901011739240.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901011730190.30769@pacific.mpi-cbg.de","subject":"[PATCH 3/3] bash completions: Add the --patience option","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-01T16:39:37Z","receivedAt":"2009-01-01T16:39:37Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nSigned-off-by: Johannes Schindelin \n---\n contrib/completion/git-completion.bash | 2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex a046441..b3e1e22 100755\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -777,6 +777,7 @@ _git_diff ()\n \t\t\t--no-prefix --src-prefix= --dst-prefix=\n \t\t\t--base --ours --theirs\n \t\t\t--inter-hunk-context=\n+\t\t\t--patience\n \t\t\t\"\n \t\treturn\n \t\t;;\n@@ -969,6 +970,7 @@ _git_log ()\n \t\t\t--parents --children --full-history\n \t\t\t--merge\n \t\t\t--inter-hunk-context=\n+\t\t\t--patience\n \t\t\t\"\n \t\treturn\n \t\t;;\n-- \n1.6.1.rc3.412.ga72b\n"},{"id":"99098","messageId":"alpine.LFD.2.00.0901011134210.5086@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901011730190.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-01T19:45:21Z","receivedAt":"2009-01-01T19:45:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Jan 2009, Johannes Schindelin wrote:\n> \n> Nothing fancy, really, just a straight-forward implementation of the\n> heavily under-documented and under-analyzed paience diff algorithm.\n\nExactly because the patience diff is so under-documented, could you \nperhaps give a few examples of how it differs in the result, and why it's \nso wonderful? Yes, yes, I can google, and no, no, nothing useful shows up \nexcept for *totally* content-free fanboisms. \n\nSo could we have some actual real data on it?\n\n\t\t\tLinus\n"},{"id":"99100","messageId":"alpine.LFD.2.00.0901011151440.5086@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011134210.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-01T20:00:10Z","receivedAt":"2009-01-01T20:00:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Jan 2009, Linus Torvalds wrote:\n> \n> So could we have some actual real data on it?\n\n.. and some testing. I tried to get some limited data for the kernel \nmyself, by doing\n\n\tgit log --patience -p v2.6.28.. > ~/patience\n\nbut I just got a core-dump instead.\n\nPinpointing it to a specific commit shows a smaller failure case:\n\n\tgit show -p --patience 05d564fe00c05bf8ff93948057ca1acb5bc68e10\n\nwhich might help you debug this.\n\n\t\t\tLinus\n\n---\n#0 0x00000000004cce73 in xdl_get_rec (xdf=0x7fffcb1e08d0, ri=-9, rec=0x7fffcb1e0778) at xdiff/xemit.c:36\n#1 0x00000000004cced1 in xdl_emit_record (xdf=0x7fffcb1e08d0, ri=-9, pre=0x4eef79 \"-\", ecb=0x7fffcb1e0bc0)\n at xdiff/xemit.c:46\n#2 0x00000000004cd4e6 in xdl_emit_diff (xe=0x7fffcb1e08d0, xscr=0x1111daf0, ecb=0x7fffcb1e0bc0, \n xecfg=0x7fffcb1e0b80) at xdiff/xemit.c:179\n#3 0x00000000004caa2c in xdl_diff (mf1=0x7fffcb1e0a40, mf2=0x7fffcb1e0a30, xpp=0x7fffcb1e0bd0, \n xecfg=0x7fffcb1e0b80, ecb=0x7fffcb1e0bc0) at xdiff/xdiffi.c:559\n#4 0x00000000004c088d in xdi_diff (mf1=0x7fffcb1e0c00, mf2=0x7fffcb1e0bf0, xpp=0x7fffcb1e0bd0, \n xecfg=0x7fffcb1e0b80, xecb=0x7fffcb1e0bc0) at xdiff-interface.c:137\n#5 0x00000000004c0914 in xdi_diff_outf (mf1=0x7fffcb1e0c00, mf2=0x7fffcb1e0bf0, fn=0x475448 , \n consume_callback_data=0x7fffcb1e0b40, xpp=0x7fffcb1e0bd0, xecfg=0x7fffcb1e0b80, xecb=0x7fffcb1e0bc0)\n at xdiff-interface.c:154\n#6 0x00000000004780dc in builtin_diff (name_a=0x25cf6f0 \"fs/nfs/nfs4xdr.c\", name_b=0x25cf6f0 \"fs/nfs/nfs4xdr.c\", \n one=0x25cf690, two=0x26ae110, xfrm_msg=0xf659900 \"index 7dde309..29656c5 100644\", o=0x7fffcb1e1088, \n complete_rewrite=0) at diff.c:1486\n#7 0x00000000004796e4 in run_diff_cmd (pgm=0x0, name=0x25cf6f0 \"fs/nfs/nfs4xdr.c\", other=0x0, \n attr_path=0x25cf6f0 \"fs/nfs/nfs4xdr.c\", one=0x25cf690, two=0x26ae110, \n xfrm_msg=0xf659900 \"index 7dde309..29656c5 100644\", o=0x7fffcb1e1088, complete_rewrite=0) at diff.c:2024\n#8 0x0000000000479e2e in run_diff (p=0xaffece0, o=0x7fffcb1e1088) at diff.c:2158\n#9 0x000000000047b959 in diff_flush_patch (p=0xaffece0, o=0x7fffcb1e1088) at diff.c:2743\n#10 0x000000000047c942 in diff_flush (options=0x7fffcb1e1088) at diff.c:3184\n#11 0x0000000000488b75 in log_tree_diff_flush (opt=0x7fffcb1e0f40) at log-tree.c:451\n#12 0x0000000000488d17 in log_tree_diff (opt=0x7fffcb1e0f40, commit=0x2673198, log=0x7fffcb1e0ec0) at log-tree.c:503\n#13 0x0000000000488da4 in log_tree_commit (opt=0x7fffcb1e0f40, commit=0x2673198) at log-tree.c:526\n#14 0x000000000043218d in cmd_log_walk (rev=0x7fffcb1e0f40) at builtin-log.c:201\n#15 0x0000000000432bae in cmd_log (argc=4, argv=0x7fffcb1e14b0, prefix=0x0) at builtin-log.c:423\n#16 0x000000000040486b in run_command (p=0x70c7b0, argc=4, argv=0x7fffcb1e14b0) at git.c:243\n#17 0x0000000000404a1c in handle_internal_command (argc=4, argv=0x7fffcb1e14b0) at git.c:387\n#18 0x0000000000404c6e in main (argc=4, argv=0x7fffcb1e14b0) at git.c:484\n"},{"id":"99102","messageId":"20090101204652.GA26128@chistera.yi.org","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011134210.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-01T20:46:52Z","receivedAt":"2009-01-01T20:46:52Z","isPatch":true,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"* Linus Torvalds [Thu, 01 Jan 2009 11:45:21 -0800]:\n\n> On Thu, 1 Jan 2009, Johannes Schindelin wrote:\n\n> > Nothing fancy, really, just a straight-forward implementation of the\n> > heavily under-documented and under-analyzed paience diff algorithm.\n\n> Exactly because the patience diff is so under-documented, could you \n> perhaps give a few examples of how it differs in the result, and why it's \n> so wonderful? Yes, yes, I can google, and no, no, nothing useful shows up \n> except for *totally* content-free fanboisms. \n\n> So could we have some actual real data on it?\n\nFor me, the cases where I find patience output to be of substantial\nhigher readability are those involving a rewrite of several consecutive\nparagraphs (i.e., lines of code separated by blank lines). Compare:\n\n-8<- git -8<-\n@@ -51,29 +51,30 @@ def mbox_update(bug):\n f.close()\n else:\n # make a list of Message-Id we have\n- fp1 = file(path, 'ab+')\n- ids1 = [ x.get('Message-Id') for x in mailbox.UnixMailbox(fp1) ]\n+ msgids = { x.get('Message-Id') for x in mailbox.mbox(path) }\n \n- # get remote mbox again\n- fp2 = tempfile.TemporaryFile()\n- retrieve_mbox(bug, fp2)\n+ with tempfile.NamedTemporaryFile() as tmpfd:\n+ # retrieve the remote mbox again\n+ retrieve_mbox(bug, tmpfd)\n \n- # parse its messages\n- fp2.seek(0)\n- parser = email.Parser.Parser()\n- msgs2 = dict((x['Message-Id'], x)\n- for x in mailbox.UnixMailbox(fp2, parser.parse))\n+ # parse its messages\n+ parser = email.parser.Parser()\n+ new_msgids = { x['Message-Id']: x\n+ for x in mailbox.mbox(tmpfd.name, parser.parse) }\n \n- # now append the new ones\n- for msgid in set(msgs2.keys()) - set(ids1):\n- fp1.write('\\n' + msgs2[msgid].as_string(unixfrom=True))\n+ with open(path, 'a+') as fd:\n+ # now append the new messages\n+ for msgid in new_msgids.keys() - msgids:\n+ fd.write('\\n' + new_msgids[msgid].as_string(unixfrom=True))\n \n return path\n->8- git ->8-\n\nwith:\n\n-8<- bzr patience -8<-\n@@ -51,29 +51,30 @@\n f.close()\n else:\n # make a list of Message-Id we have\n- fp1 = file(path, 'ab+')\n- ids1 = [ x.get('Message-Id') for x in mailbox.UnixMailbox(fp1) ]\n-\n- # get remote mbox again\n- fp2 = tempfile.TemporaryFile()\n- retrieve_mbox(bug, fp2)\n-\n- # parse its messages\n- fp2.seek(0)\n- parser = email.Parser.Parser()\n- msgs2 = dict((x['Message-Id'], x)\n- for x in mailbox.UnixMailbox(fp2, parser.parse))\n-\n- # now append the new ones\n- for msgid in set(msgs2.keys()) - set(ids1):\n- fp1.write('\\n' + msgs2[msgid].as_string(unixfrom=True))\n+ msgids = { x.get('Message-Id') for x in mailbox.mbox(path) }\n+\n+ with tempfile.NamedTemporaryFile() as tmpfd:\n+ # retrieve the remote mbox again\n+ retrieve_mbox(bug, tmpfd)\n+\n+ # parse its messages\n+ parser = email.parser.Parser()\n+ new_msgids = { x['Message-Id']: x\n+ for x in mailbox.mbox(tmpfd.name, parser.parse) }\n+\n+ with open(path, 'a+') as fd:\n+ # now append the new messages\n+ for msgid in new_msgids.keys() - msgids:\n+ fd.write('\\n' + new_msgids[msgid].as_string(unixfrom=True))\n \n return path\n->8- bzr patience ->8-\n\nI don't know about you, but I find the latter much easier to read,\nbecause the whole context of each version is always available.\n\nAs you see, in (at least) this case is just a matter of considering the\nblank lines worthy of presented as common, or not.\n\nI'll note that in this particular case, `git diff` yielded the very same\nresults with or without --patience. I don't know why that is, Johannes?\nI'll also note that /usr/bin/diff produces (in this case) something\ncloser to patience than to git.\n\nI'm attaching both versions of the file in case they are useful to\nanybody.\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \nI promise you. Once I enter into an exclusive relationship, I sleep with\nvery few people.\n -- Denny Crane\n\n\n#! /usr/bin/python\n## vim: fileencoding=utf-8\n\n\"\"\"Open Debian BTS mboxes with Mutt, à la /usr/bin/bts show --mbox.\n\nA cache of mboxes is kept, and changed mboxes will be merged with existing\nfiles instead of replacing them, so that e.g. read-status is preserved for each\nmessage.\n\"\"\"\n\nimport os\nimport re\nimport sys\nimport urllib\nimport mailbox\nimport tempfile\nimport email.Parser\n\nMBOX_DIR = os.path.expanduser('~/.mail/y.bug-cache')\n\n##\n\ndef main():\n if len(sys.argv) != 2:\n print >>sys.stderr, 'Usage: %s ' % (sys.argv[0],)\n sys.exit(1)\n\n bug = re.sub(r'[^0-9]', '', sys.argv[1])\n if not re.match(r'\\d{4,}$', bug):\n print >>sys.stderr, \\\n 'E: %s does not seem a valid number' % (sys.argv[1],)\n sys.exit(1)\n\n path = mbox_update(bug)\n invoke_mailer(path)\n\n##\n\ndef mbox_update(bug):\n \"\"\"Return a path with an up-to-date copy of the mbox for bug.\"\"\"\n path = os.path.join(MBOX_DIR, bug + '.mbox')\n\n if not os.path.exists(path):\n f = file(path, 'wb')\n try:\n retrieve_mbox(bug, f)\n except:\n os.unlink(path)\n raise\n else:\n f.close()\n else:\n # make a list of Message-Id we have\n fp1 = file(path, 'ab+')\n ids1 = [ x.get('Message-Id') for x in mailbox.UnixMailbox(fp1) ]\n\n # get remote mbox again\n fp2 = tempfile.TemporaryFile()\n retrieve_mbox(bug, fp2)\n\n # parse its messages\n fp2.seek(0)\n parser = email.Parser.Parser()\n msgs2 = dict((x['Message-Id'], x)\n for x in mailbox.UnixMailbox(fp2, parser.parse))\n\n # now append the new ones\n for msgid in set(msgs2.keys()) - set(ids1):\n fp1.write('\\n' + msgs2[msgid].as_string(unixfrom=True))\n\n return path\n\ndef retrieve_mbox(bug, fileobj):\n \"\"\"Retrieve mbox for bug from bugs.debian.org, writing it to fileobj.\"\"\"\n for line in urllib.urlopen(\n 'http://bugs.debian.org/cgi-bin/bugreport.cgi?mboxstatus=yes;mboxmaint=yes;mbox=yes;bug=%s' % (bug,)):\n fileobj.write(line)\n\ndef invoke_mailer(path):\n \"\"\"Exec mutt, opening path.\"\"\"\n os.execlp('mutt', 'mutt', '-f', path)\n\n##\n\nif __name__ == '__main__':\n try:\n sys.exit(main())\n except KeyboardInterrupt:\n print >>sys.stderr, '\\nCancelled.'\n sys.exit(1)\n\n\n#! /usr/bin/python3\n\n\"\"\"Open Debian BTS mboxes with Mutt, à la /usr/bin/bts show --mbox.\n\nA cache of mboxes is kept, and changed mboxes will be merged with existing\nfiles instead of replacing them, so that e.g. read-status is preserved for each\nmessage.\n\"\"\"\n\nimport os\nimport re\nimport sys\nimport mailbox\nimport tempfile\nimport email.parser\nimport urllib.request\n\nMBOX_DIR = os.path.expanduser('~/.mail/y.bug-cache')\n\n##\n\ndef main():\n if len(sys.argv) != 2:\n print('Usage: {0} '.format(sys.argv[0]), file=sys.stderr)\n return 1\n else:\n bug = re.sub(r'[^0-9]', '', sys.argv[1])\n\n if not re.search(r'^\\d{4,}$', bug):\n print('E: {0} does not seem a valid number'.format(sys.argv[1]),\n file=sys.stderr)\n return 1\n\n path = mbox_update(bug)\n invoke_mailer(path)\n\n##\n\ndef mbox_update(bug):\n \"\"\"Return a path with an up-to-date copy of the mbox for bug.\"\"\"\n path = os.path.join(MBOX_DIR, bug + '.mbox')\n\n if not os.path.exists(path):\n f = open(path, 'wb')\n try:\n retrieve_mbox(bug, f)\n except:\n os.unlink(path)\n raise\n else:\n f.close()\n else:\n # make a list of Message-Id we have\n msgids = { x.get('Message-Id') for x in mailbox.mbox(path) }\n\n with tempfile.NamedTemporaryFile() as tmpfd:\n # retrieve the remote mbox again\n retrieve_mbox(bug, tmpfd)\n\n # parse its messages\n parser = email.parser.Parser()\n new_msgids = { x['Message-Id']: x\n for x in mailbox.mbox(tmpfd.name, parser.parse) }\n\n with open(path, 'a+') as fd:\n # now append the new messages\n for msgid in new_msgids.keys() - msgids:\n fd.write('\\n' + new_msgids[msgid].as_string(unixfrom=True))\n\n return path\n\ndef retrieve_mbox(bug, fileobj):\n \"\"\"Retrieve mbox for bug from bugs.debian.org, writing it to fileobj.\"\"\"\n url = urllib.request.urlopen(\n 'http://bugs.debian.org/cgi-bin/bugreport.cgi?'\n 'mboxstatus=yes;mboxmaint=yes;mbox=yes;bug={0}'.format(bug))\n for line in url.fp: # http://bugs.python.org/issue4608\n fileobj.write(line)\n\ndef invoke_mailer(path):\n \"\"\"Exec mutt, opening path.\"\"\"\n os.execlp('mutt', 'mutt', '-f', path)\n\n##\n\nif __name__ == '__main__':\n try:\n sys.exit(main())\n except KeyboardInterrupt:\n print('\\nCancelled.', file=sys.stderr)\n sys.exit(1)\n"},{"id":"99140","messageId":"alpine.LFD.2.00.0901011747010.5086@localhost.localdomain","threadId":"16159","inReplyTo":"20090101204652.GA26128@chistera.yi.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-02T01:56:13Z","receivedAt":"2009-01-02T01:56:13Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 1 Jan 2009, Adeodato Simó wrote:\n> \n> For me, the cases where I find patience output to be of substantial\n> higher readability are those involving a rewrite of several consecutive\n> paragraphs (i.e., lines of code separated by blank lines). Compare:\n\nI don't think that's a \"patience diff\" issue.\n\nThat's simply an issue of merging consecutive diff fragments together if \nthey are close-by, and that's independent of the actual diff algorithm \nitself.\n\n> I'll note that in this particular case, `git diff` yielded the very same\n> results with or without --patience. I don't know why that is, Johannes?\n> I'll also note that /usr/bin/diff produces (in this case) something\n> closer to patience than to git.\n\nSee above - I really don't think this has anything to do with \"patience vs \nnon-patience\". It's more akin to the things we do for our merge conflict \nmarkers: if we have two merge conflicts next to each other, with just a \ncouple of lines in between, we coalesce the merge conflicts into one \nlarger one instead.\n\nWe don't do that for regular diffs - they're always kept minimal (ok, not \nreally minimal, but as close to minimal as the algorithm finds them).\n\nSee commit f407f14deaa14ebddd0d27238523ced8eca74393 for the git merge \nconflict merging. We _could_ do similar things for regular diffs. It's \nsometimes useful, sometimes not.\n\n\t\tLinus\n"},{"id":"99156","messageId":"20090102105537.GA14691@localhost","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011747010.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2009-01-02T10:55:38Z","receivedAt":"2009-01-02T10:55:38Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Thu, Jan 01, 2009 at 05:56:13PM -0800, Linus Torvalds wrote:\n> See above - I really don't think this has anything to do with \"patience vs \n> non-patience\". It's more akin to the things we do for our merge conflict \n> markers: if we have two merge conflicts next to each other, with just a \n> couple of lines in between, we coalesce the merge conflicts into one \n> larger one instead.\n\nBut patience diff does more than that. Take a look at \"git diff\" and \"git\ndiff --patience\" output below (taken from [1]). You can see that patience\ndiff produces two separate hunks, one removing a function and one adding a\nfunction. Merging consecutive diff fragments would have produced one big\nhunk instead.\n\n*** git diff ****************************** git diff --patience **********\n #include | #include \n |\n+int fib(int n) |-// Frobs foo heartily\n+{ |-int frobnitz(int foo)\n+ if(n > 2) |+int fib(int n)\n+ { | {\n+ return fib(n-1) + fib(n-2); |- int i;\n+ } |- for(i = 0; i < 10; i++)\n+ return 1; |+ if(n > 2)\n+} | {\n+ |- printf(\"Your answer is: \");\n // Frobs foo heartily |- printf(\"%d\\n\", foo);\n int frobnitz(int foo) |+ return fib(n-1) + fib(n-2);\n { | }\n int i; |+ return 1;\n for(i = 0; i < 10; i++) | }\n { |\n- printf(\"Your answer is: \"); |-int fact(int n)\n printf(\"%d\\n\", foo); |+// Frobs foo heartily\n } |+int frobnitz(int foo)\n } | {\n |- if(n > 1)\n-int fact(int n) |+ int i;\n-{ |+ for(i = 0; i < 10; i++)\n- if(n > 1) | {\n- { |- return fact(n-1) * n;\n- return fact(n-1) * n; |+ printf(\"%d\\n\", foo);\n- } | }\n- return 1; |- return 1;\n-} | }\n- |\n int main(int argc, char **argv) | int main(int argc, char **argv)\n { | {\n- frobnitz(fact(10)); |- frobnitz(fact(10));\n+ frobnitz(fib(10)); |+ frobnitz(fib(10));\n } | }\n\n[1] http://alfedenzo.livejournal.com/170301.html\n"},{"id":"99158","messageId":"20090102105856.GB14691@localhost","threadId":"16159","inReplyTo":"20090102105537.GA14691@localhost","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2009-01-02T10:58:56Z","receivedAt":"2009-01-02T10:58:56Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Only two choices, and I still get it wrong. The diffs should be labeled the\nother way around, of course.\n\n*** git diff --patience ******************** git diff ********************\n #include | #include \n |\n+int fib(int n) |-// Frobs foo heartily\n+{ |-int frobnitz(int foo)\n+ if(n > 2) |+int fib(int n)\n+ { | {\n+ return fib(n-1) + fib(n-2); |- int i;\n+ } |- for(i = 0; i < 10; i++)\n+ return 1; |+ if(n > 2)\n+} | {\n+ |- printf(\"Your answer is: \");\n // Frobs foo heartily |- printf(\"%d\\n\", foo);\n int frobnitz(int foo) |+ return fib(n-1) + fib(n-2);\n { | }\n int i; |+ return 1;\n for(i = 0; i < 10; i++) | }\n { |\n- printf(\"Your answer is: \"); |-int fact(int n)\n printf(\"%d\\n\", foo); |+// Frobs foo heartily\n } |+int frobnitz(int foo)\n } | {\n |- if(n > 1)\n-int fact(int n) |+ int i;\n-{ |+ for(i = 0; i < 10; i++)\n- if(n > 1) | {\n- { |- return fact(n-1) * n;\n- return fact(n-1) * n; |+ printf(\"%d\\n\", foo);\n- } | }\n- return 1; |- return 1;\n-} | }\n- |\n int main(int argc, char **argv) | int main(int argc, char **argv)\n { | {\n- frobnitz(fact(10)); |- frobnitz(fact(10));\n+ frobnitz(fib(10)); |+ frobnitz(fib(10));\n } | }\n"},{"id":"99159","messageId":"7vocyqc6lu.fsf@gitster.siamese.dyndns.org","threadId":"16159","inReplyTo":"20090102105537.GA14691@localhost","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-02T11:03:41Z","receivedAt":"2009-01-02T11:03:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Clemens Buchacher writes:\n\n> But patience diff does more than that. Take a look at \"git diff\" and \"git\n> diff --patience\" output below (taken from [1]).\n>\n> *** git diff ****************************** git diff --patience **********\n> #include | #include \n\nI suspect you have the above labels backwards...\n"},{"id":"99172","messageId":"alpine.LFD.2.00.0901020833000.5086@localhost.localdomain","threadId":"16159","inReplyTo":"20090102105856.GB14691@localhost","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-02T16:42:04Z","receivedAt":"2009-01-02T16:42:04Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Jan 2009, Clemens Buchacher wrote:\n>\n> Only two choices, and I still get it wrong. The diffs should be labeled the\n> other way around, of course.\n\nYes, this one is a real patience diff change, but it's also the same one \nthat I've seen in the google fanboi findings. What google did _not_ show \nwas any real-life examples, or anybody doing any critical analysis.\n\nSo I was hoping for something else than a single \"in this case patience \ndiff works really well\". I was hoping to see what it does in real life. \nBut when I tried it on the kernel archive, I get a core dump.\n\nFor example, in real life, files are bigger, and unique lines are not \nnecessarily always common (generated files, whatever). Depending on unique \nline ordering may work fine in 95% of all cases, but do you know that it \nworks fine in general? Does it work when 50% of lines are unique? I \nbelieve it does. Does ti work when just 1% of lines are unique? I just \ndon't know.\n\nAnd I haven't seen _any_ real critical analysis of it. Anywhere.\n\n\t\t\tLinus\n"},{"id":"99183","messageId":"alpine.DEB.1.00.0901021914420.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011151440.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T18:17:34Z","receivedAt":"2009-01-02T18:17:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 1 Jan 2009, Linus Torvalds wrote:\n\n> On Thu, 1 Jan 2009, Linus Torvalds wrote:\n> > \n> > So could we have some actual real data on it?\n> \n> .. and some testing. I tried to get some limited data for the kernel \n> myself, by doing\n> \n> \tgit log --patience -p v2.6.28.. > ~/patience\n> \n> but I just got a core-dump instead.\n> \n> Pinpointing it to a specific commit shows a smaller failure case:\n> \n> \tgit show -p --patience 05d564fe00c05bf8ff93948057ca1acb5bc68e10\n> \n> which might help you debug this.\n\nThanks. I am on it. valgrind finds an earlier place in \nxdl_change_compact() which I think is rather more sensible, but at the \nsame time a bit worrisome, too, as I did not expect any errors _that_ \nlate in the game (I did not touch that code).\n\nBTW the \"-p\" is not necessary with \"show\", indeed, you cannot even switch \nit off.\n\nCiao,\nDscho\n"},{"id":"99185","messageId":"alpine.DEB.1.00.0901021918100.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901020833000.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T18:46:35Z","receivedAt":"2009-01-02T18:46:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 2 Jan 2009, Linus Torvalds wrote:\n\n\n> On Fri, 2 Jan 2009, Clemens Buchacher wrote:\n> >\n> > Only two choices, and I still get it wrong. The diffs should be \n> > labeled the other way around, of course.\n> \n> Yes, this one is a real patience diff change, but it's also the same one \n> that I've seen in the google fanboi findings. What google did _not_ show \n> was any real-life examples, or anybody doing any critical analysis.\n\nFWIW it's the test case in the commit introducing the --patience option.\n\n> So I was hoping for something else than a single \"in this case patience \n> diff works really well\". I was hoping to see what it does in real life.\n\nI will dig out a real-world example where I _know_ patience diff would \nhave helped. (I remember that I rewrote a pretty large diff which was \nsent on this list, only to understand what it actually does, and I am \npretty certain this is a good real-world showcase.)\n\nBut yes, I agree, the thing does not matter _all_ that much in reality.\n\nThe case where I expect a real improvement is when you modify a function \nand insert a function just before it, and Myers' algorithm matches mainly \nempty lines and lines ending in curly brackets.\n\nIn other words: something I tried to tackle with ee95ec5d(xdl_merge(): \nintroduce XDL_MERGE_ZEALOUS_ALNUM) for merges.\n\nThe typical look of such a diff is something like this:\n\n-<... some function header ...>\n+<... a completely different function header ...>\n {\n-\t<... variables ...>\n+\t<... other variables ...>\n \n \tfor (i = 0; i < 10; i++) {\n-\t\t<... some code ...>\n+\t\t<... some code doing something completely different ...>\n\t}\n \n \treturn 0;\n }\n\n+<... the function header which was removed earlier ...>\n+{\n \t<... refactored _and also reindented_ code ...>\n\n> And I haven't seen _any_ real critical analysis of it. Anywhere.\n\nNeither have I. Let alone something close to documentation.\n\nFor example, when the \"patience diff algorithm\" is explained, it looks \nmore like a longest common sequence algorithm when the input is already \nsorted in the first item.\n\nFurther, there is no rigorous analysis of the runtime (I figured that the \noriginal runtime is O(nm) where \"n\" is the number of lines and \"m\" is the \nlength of the maximal ordered sequence of common unique lines, and my \nimplementation can only improve that to O(n log(m))).\n\nThis could be improved, I think, for the most common case where you have \npretty long common _continuous_ sequences of unique lines, i.e. large \nranges of lines that are identical.\n\nThe runtime is especially horrible in the light of the runtime of Myers' \nalgorithm, which uses O(n d), where d is the edit distance, i.e. the \nnumber of lines added + number of lines removed. (Note: in the real \nworld, there are substantial speed ups for consecutive edits, i.e. line \nranges where there are no common lines at all.)\n\nAlso, I am less than thrilled by the job the fanbois did coming up with \n\"convincing\" evidence: exactly as you pointed out, there are _no_ \nreal-world examples where it helps.\n\nAnd the worst part: one can only _guess_ what motivated patience diff. I \nimagine it came from the observation that function headers are unique, and \nthat you usually want to preserve as much context around them.\n\nCiao,\nDscho\n"},{"id":"99187","messageId":"alpine.LFD.2.00.0901021045290.5086@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901021914420.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-02T18:49:05Z","receivedAt":"2009-01-02T18:49:05Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Jan 2009, Johannes Schindelin wrote:\n> \n> BTW the \"-p\" is not necessary with \"show\", indeed, you cannot even switch \n> it off.\n\nI was just switching back-and-forth between \"git log\" and \"git show\" so \nthe -p came from just that, and is not necessary.\n\nAnd you _can_ suppress the patch generation - use \"-s\".\n\n\t\t\tLinus\n"},{"id":"99188","messageId":"20090102185003.GA21135@chistera.yi.org","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011747010.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-02T18:50:03Z","receivedAt":"2009-01-02T18:50:03Z","isPatch":true,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"* Linus Torvalds [Thu, 01 Jan 2009 17:56:13 -0800]:\n\n> On Thu, 1 Jan 2009, Adeodato Simó wrote:\n\n> > For me, the cases where I find patience output to be of substantial\n> > higher readability are those involving a rewrite of several consecutive\n> > paragraphs (i.e., lines of code separated by blank lines). Compare:\n\n> I don't think that's a \"patience diff\" issue.\n\nAh, I see.\n\n> That's simply an issue of merging consecutive diff fragments together if \n> they are close-by, and that's independent of the actual diff algorithm \n> itself.\n\n> > I'll note that in this particular case, `git diff` yielded the very same\n> > results with or without --patience. I don't know why that is, Johannes?\n> > I'll also note that /usr/bin/diff produces (in this case) something\n> > closer to patience than to git.\n\n> See above - I really don't think this has anything to do with \"patience vs \n> non-patience\". It's more akin to the things we do for our merge conflict \n> markers: if we have two merge conflicts next to each other, with just a \n> couple of lines in between, we coalesce the merge conflicts into one \n> larger one instead.\n\n> We don't do that for regular diffs - they're always kept minimal (ok, not \n> really minimal, but as close to minimal as the algorithm finds them).\n\n> See commit f407f14deaa14ebddd0d27238523ced8eca74393 for the git merge \n> conflict merging. We _could_ do similar things for regular diffs. It's \n> sometimes useful, sometimes not.\n\nIndependently of patience diff, then, I'd very much support changes to\nimprove the diff I pasted.\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \nDebugging is twice as hard as writing the code in the first place. Therefore,\nif you write the code as cleverly as possible, you are, by definition, not\nsmart enough to debug it.\n -- Brian W. Kernighan\n"},{"id":"99189","messageId":"20090102185137.GA9129@coredump.intra.peff.net","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901021914420.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-01-02T18:51:38Z","receivedAt":"2009-01-02T18:51:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 02, 2009 at 07:17:34PM +0100, Johannes Schindelin wrote:\n\n> BTW the \"-p\" is not necessary with \"show\", indeed, you cannot even switch \n> it off.\n\nHalf true:\n\n $ git grep -A1 '\"-s\"' diff.c\n diff.c: else if (!strcmp(arg, \"-s\"))\n diff.c- options->output_format |= DIFF_FORMAT_NO_OUTPUT;\n\n-Peff\n"},{"id":"99192","messageId":"alpine.LFD.2.00.0901021050450.5086@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901021918100.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-02T19:03:07Z","receivedAt":"2009-01-02T19:03:07Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Jan 2009, Johannes Schindelin wrote:\n> \n> FWIW it's the test case in the commit introducing the --patience option.\n\nWell, it's also the test-case in the very first hit on google for \n\"patience diff\" (with the quotes).\n\nIn fact, it's the _only_ one I ever found ;)\n\n> And the worst part: one can only _guess_ what motivated patience diff. I \n> imagine it came from the observation that function headers are unique, and \n> that you usually want to preserve as much context around them.\n\nWell, I do like the notion of giving more weight to unique lines - I think \nit makes sense. That said, I suspect it would make almost as much sense to \ngive more weight simply to _longer_ lines, and I suspect the standard \nMyers' algorithm could possibly be simply extended to take line size into \naccount when calculating the weights.\n\nBecause the problem with diffs for C doesn't really tend to be as much \nabout non-unique lines as about just _trivial_ lines that are mostly empty \nor contain just braces etc. Those are quite arguably almost totally \nworthless for equality testing.\n\nAnd btw, don't get me wrong - I don't think there is anything wrong with \nthe patience diff. I think it's a worthy thing to try, and I'm not at all \narguing against it. However, I do think that the people arguing for it \noften do so based on less-than-very-logical arguments, and it's entirely \npossible that other approaches are better (eg the \"weight by size\" thing \nrather than \"weight by uniqueness\").\n\nThe thing about unique lines is that there are no guarantees at all that \nthey even exist, so a uniqueness-based thing will always have to fall back \non anything else. That, to me, implies that the whole notion is somewhat \nmis-designed: it's clearly not a generic concept.\n\n(In contrast, taking the length of the matching lines into account would \nnot have that kind of bad special case)\n\n\t\t\tLinus\n"},{"id":"99193","messageId":"alpine.DEB.1.00.0901022007280.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901021045290.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T19:07:44Z","receivedAt":"2009-01-02T19:07:44Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 2 Jan 2009, Linus Torvalds wrote:\n\n> On Fri, 2 Jan 2009, Johannes Schindelin wrote:\n> > \n> > BTW the \"-p\" is not necessary with \"show\", indeed, you cannot even \n> > switch it off.\n> \n> I was just switching back-and-forth between \"git log\" and \"git show\" so \n> the -p came from just that, and is not necessary.\n> \n> And you _can_ suppress the patch generation - use \"-s\".\n\nAh, another thing learnt.\n\nThanks,\nDscho\n"},{"id":"99194","messageId":"alpine.DEB.1.00.0901022008490.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901021050450.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T19:22:44Z","receivedAt":"2009-01-02T19:22:44Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 2 Jan 2009, Linus Torvalds wrote:\n\n> On Fri, 2 Jan 2009, Johannes Schindelin wrote:\n> \n> > And the worst part: one can only _guess_ what motivated patience diff. \n> > I imagine it came from the observation that function headers are \n> > unique, and that you usually want to preserve as much context around \n> > them.\n> \n> Well, I do like the notion of giving more weight to unique lines - I think \n> it makes sense. That said, I suspect it would make almost as much sense to \n> give more weight simply to _longer_ lines, and I suspect the standard \n> Myers' algorithm could possibly be simply extended to take line size into \n> account when calculating the weights.\n\nI think that it makes more sense with the common unique lines, because \nthey are _unambiguously_ common. That is, if possible, we would like to \nkeep them as common lines.\n\nBTW this also opens the door for more automatic code movement detection.\n\nAs for the longer lines: what exactly would you want to put \"weight\" on? \nThe edit distance is the number of plusses and minusses, and this is the \nthing that actually is pretty critical for the performance: the larger the \ndistance, the longer it takes. So if you want to put a different \"weight\" \non a line, i.e. something else than a \"1\", you are risking a substantially \nworse performance.\n\nAnd I am still not convinced that longer lines should get more weight. A \nline starting with \"exit:\" can be much more important than 8 tabs followed \nby a curly bracket.\n\n> Because the problem with diffs for C doesn't really tend to be as much \n> about non-unique lines as about just _trivial_ lines that are mostly empty \n> or contain just braces etc. Those are quite arguably almost totally \n> worthless for equality testing.\n\nOh, but then we get very C specific. Let's not go there.\n\n> And btw, don't get me wrong - I don't think there is anything wrong with \n> the patience diff. I think it's a worthy thing to try, and I'm not at \n> all arguing against it.\n\nI never took you to be opposed. I myself mainly implemented it because I \nwanted to play with it, and have something more useful than what I found \nin the whole wide web.\n\n> However, I do think that the people arguing for it often do so based on \n> less-than-very-logical arguments, and it's entirely possible that other \n> approaches are better (eg the \"weight by size\" thing rather than \"weight \n> by uniqueness\").\n\nActually, I think it is very possible that merging hunks if there are not \nenough alnums between them could make a whole lot of sense.\n\nBut IIRC it was shot down and replaced by the not-so-specific-to-C \nalgorithm to merge hunks when the output is shorter than having separate \nhunks.\n\n> The thing about unique lines is that there are no guarantees at all that \n> they even exist, so a uniqueness-based thing will always have to fall \n> back on anything else. That, to me, implies that the whole notion is \n> somewhat mis-designed: it's clearly not a generic concept.\n> \n> (In contrast, taking the length of the matching lines into account would \n> not have that kind of bad special case)\n\nHowever, we know that humans like to start from the unique features they \nsee, and continue from there.\n\nAnd while it is quite possible that it is the wrong approach (see all that \nsecurity theater at the airport, and some nice rational analyses about the \ncost/benefit equations there), imitating humans is still the thing that \nwill convince most humans.\n\nCiao,\nDscho\n"},{"id":"99196","messageId":"20090102193904.GB9129@coredump.intra.peff.net","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901021050450.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-01-02T19:39:04Z","receivedAt":"2009-01-02T19:39:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 02, 2009 at 11:03:07AM -0800, Linus Torvalds wrote:\n\n> Well, it's also the test-case in the very first hit on google for \n> \"patience diff\" (with the quotes).\n> \n> In fact, it's the _only_ one I ever found ;)\n\nIf you just want to see the results on some real-world cases (and don't\ncare about measuring performance), try installing bzr and using their\npatiencediff test program as a GIT_EXTERNAL_DIFF.\n\nOn Debian, it's:\n\n $ sudo apt-get install bzr\n $ cat >$HOME/patience <<'EOF'\n #!/bin/sh\n exec python /usr/share/pyshared/bzrlib/patiencediff.py \"$2\" \"$5\"\n EOF\n $ chmod 755 patience\n $ GIT_EXTERNAL_DIFF=$HOME/patience git diff\n\nOther distributions presumably install patiencediff.py somewhere\nsimilar (or you can maybe even pull it from the source, but presumably\nyou have to install some other bzr modules, too).\n\n-Peff\n"},{"id":"99197","messageId":"20090102195053.GA10876@coredump.intra.peff.net","threadId":"16159","inReplyTo":"20090102193904.GB9129@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-01-02T19:50:53Z","receivedAt":"2009-01-02T19:50:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 02, 2009 at 02:39:04PM -0500, Jeff King wrote:\n\n> If you just want to see the results on some real-world cases (and don't\n> care about measuring performance), try installing bzr and using their\n> patiencediff test program as a GIT_EXTERNAL_DIFF.\n> \n> On Debian, it's:\n> \n> $ sudo apt-get install bzr\n> $ cat >$HOME/patience <<'EOF'\n> #!/bin/sh\n> exec python /usr/share/pyshared/bzrlib/patiencediff.py \"$2\" \"$5\"\n> EOF\n> $ chmod 755 patience\n> $ GIT_EXTERNAL_DIFF=$HOME/patience git diff\n\nFor added fun, try this:\n\n-- >8 --\n#!/bin/sh\n\ncanonical() {\n grep '^[ +-]' | egrep -v '^(---|\\+\\+\\+)'\n}\n\ngit rev-list --no-merges HEAD | while read rev; do\n git diff-tree -p $rev^ $rev | canonical >git.out\n GIT_EXTERNAL_DIFF=$HOME/patience git diff $rev^ $rev | canonical >bzr.out\n echo \"`diff -U0 git.out bzr.out | wc -l` $rev\"\ndone\n-- 8< --\n\nI'm running it on git.git now. It looks like both algorithms return the\nsame patch for most cases. Some of the differences are interesting,\nthough.\n\nFor example, f83b9ba209's commit message indicates that it moves the\n\"--format-patch\" paragraph. Which is what \"git diff\" shows. Patience\ndiff shows it as moving other text _around_ that paragraph.\n\n-Peff\n"},{"id":"99200","messageId":"20090102205208.GA9273@coredump.intra.peff.net","threadId":"16159","inReplyTo":"20090102195053.GA10876@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-01-02T20:52:08Z","receivedAt":"2009-01-02T20:52:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 02, 2009 at 02:50:53PM -0500, Jeff King wrote:\n\n> For example, f83b9ba209's commit message indicates that it moves the\n> \"--format-patch\" paragraph. Which is what \"git diff\" shows. Patience\n> diff shows it as moving other text _around_ that paragraph.\n\nHere's another interesting one: d592b315. The commit removes dashes\nfrom git commands in test scripts. Git says:\n\n echo \"tag-one-line\" >expect &&\n- git-tag -l | grep \"^tag-one-line\" >actual &&\n+ git tag -l | grep \"^tag-one-line\" >actual &&\n test_cmp expect actual &&\n- git-tag -n0 -l | grep \"^tag-one-line\" >actual &&\n+ git tag -n0 -l | grep \"^tag-one-line\" >actual &&\n test_cmp expect actual &&\n- git-tag -n0 -l tag-one-line >actual &&\n+ git tag -n0 -l tag-one-line >actual &&\n test_cmp expect actual &&\n\nwhereas patience says:\n\n echo \"tag-one-line\" >expect &&\n- git-tag -l | grep \"^tag-one-line\" >actual &&\n- test_cmp expect actual &&\n- git-tag -n0 -l | grep \"^tag-one-line\" >actual &&\n- test_cmp expect actual &&\n- git-tag -n0 -l tag-one-line >actual &&\n+ git tag -l | grep \"^tag-one-line\" >actual &&\n+ test_cmp expect actual &&\n+ git tag -n0 -l | grep \"^tag-one-line\" >actual &&\n+ test_cmp expect actual &&\n+ git tag -n0 -l tag-one-line >actual &&\n test_cmp expect actual &&\n\nwhich is exactly what patience is advertised to do: it's treating the\nnon-unique lines as uninteresting markers. But in this case they _are_\ninteresting, and I think the git output is more readable. And this is a\ncase where your \"weight lines by length instead of uniqueness\"\nsuggestion would perform better, I think.\n\n-Peff\n"},{"id":"99208","messageId":"alpine.DEB.1.00.0901022157260.27818@racer","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901020833000.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T21:59:27Z","receivedAt":"2009-01-02T21:59:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 2 Jan 2009, Linus Torvalds wrote:\n\n> So I was hoping for something else than a single \"in this case patience \n> diff works really well\". I was hoping to see what it does in real life. \n\nFunnily, I think the test case you sent me is a pretty good example. Look \nat this hunk (without patience diff):\n\n@@ -4205,25 +4205,25 @@ out:\n */\n static int nfs4_xdr_dec_setattr(struct rpc_rqst *rqstp, __be32 *p, struct nfs_se\n {\n- struct xdr_stream xdr;\n- struct compound_hdr hdr;\n- int status;\n-\n- xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);\n- status = decode_compound_hdr(&xdr, &hdr);\n- if (status)\n- goto out;\n- status = decode_putfh(&xdr);\n- if (status)\n- goto out;\n- status = decode_setattr(&xdr, res);\n- if (status)\n- goto out;\n+ struct xdr_stream xdr;\n+ struct compound_hdr hdr;\n+ int status;\n+\n+ xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);\n\n... and then it goes on with the whole reindented function. Compare this \nto the same hunk _with_ patience diff:\n\n@@ -4205,25 +4205,25 @@ out:\n */\n static int nfs4_xdr_dec_setattr(struct rpc_rqst *rqstp, __be32 *p, struct nfs_se\n {\n- struct xdr_stream xdr;\n- struct compound_hdr hdr;\n- int status;\n+ struct xdr_stream xdr;\n+ struct compound_hdr hdr;\n+ int status;\n\n- xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);\n- status = decode_compound_hdr(&xdr, &hdr);\n- if (status)\n- goto out;\n- status = decode_putfh(&xdr);\n- if (status)\n- goto out;\n- status = decode_setattr(&xdr, res);\n- if (status)\n- goto out;\n+ xdr_init_decode(&xdr, &rqstp->rq_rcv_buf, p);\n+ status = decode_compound_hdr(&xdr, &hdr);\n\n... and again the rest is reindented code.\n\nThe difference? The common empty line. I actually find it more readable \nto have the separation between the declarations and the code also in the \ndiff.\n\nThis is just a very feeble example, but you get the idea from there.\n\nOh, you might object that the empty line is not unique. But actually it \nis, because the patience diff recurses into ever smaller line ranges until \nit finally comes to such a small range that the empty line _is_ unique.\n\nAnd in my analysis of the complexity, I stupidly left out that recursion \npart. So: patience diff is _substantially_ more expensive than Myers'.\n\n> But when I tried it on the kernel archive, I get a core dump.\n\nI also got this trying on the git.git repository, with commit \nbe3cfa85([PATCH] Diff-tree-helper take two.) Funnily, I almost got there \ntrying the same before sending the first revision, but I got impatient and \nstopped early. Tsk, tsk.\n\nNow I tried with my complete clone of git.git together with all of my \ntopic branches, and it runs through without segmentation fault. Patch \nfollows.\n\nCiao,\nDscho\n"},{"id":"99210","messageId":"alpine.DEB.1.00.0901022220380.27818@racer","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011151440.5086@localhost.localdomain","subject":"[PATCH 1/3 v2] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T21:59:32Z","receivedAt":"2009-01-02T21:59:32Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nThe patience diff algorithm produces slightly more intuitive output\nthan the classic Myers algorithm, as it does not try to minimize the\nnumber of +/- lines first, but tries to preserve the lines that are\nunique.\n\nTo this end, it first determines lines that are unique in both files,\nthen the maximal sequence which preserves the order (relative to both\nfiles) is extracted.\n\nStarting from this initial set of common lines, the rest of the lines\nis handled recursively, with Myers' algorithm as a fallback when\nthe patience algorithm fails (due to no common unique lines).\n\nSigned-off-by: Johannes Schindelin \n---\n\n\tI did not realize that xdl_prepare_env() initializes the arrays in\n\trchg (which tell which lines are not common). Unfortunately, there\n\tare ambiguities, e.g. with empty lines, and my implementation wanted\n\tto take other common lines, disagreeing with the previous\n\tinitialization.\n\n\tInterdiff follows.\n\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xpatience.c | 385 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 391 insertions(+), 0 deletions(-)\n create mode 100644 xdiff/xpatience.c\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 361f802..4da052a 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -32,6 +32,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE (1 << 2)\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n+#define XDF_PATIENCE_DIFF (1 << 5)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 9d0324a..3e97462 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -329,6 +329,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \txdalgoenv_t xenv;\n \tdiffdata_t dd1, dd2;\n \n+\tif (xpp->flags & XDF_PATIENCE_DIFF)\n+\t\treturn xdl_do_patience_diff(mf1, mf2, xpp, xe);\n+\n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n \t\treturn -1;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex 3e099dc..ad033a8 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -55,5 +55,7 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);\n void xdl_free_script(xdchange_t *xscr);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg);\n+int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *env);\n \n #endif /* #if !defined(XDIFFI_H) */\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nnew file mode 100644\nindex 0000000..d01cbdd\n--- /dev/null\n+++ b/xdiff/xpatience.c\n@@ -0,0 +1,385 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+#include \"xinclude.h\"\n+#include \"xtypes.h\"\n+#include \"xdiff.h\"\n+\n+/*\n+ * The basic idea of patience diff is to find lines that are unique in\n+ * both files. These are intuitively the ones that we want to see as\n+ * common lines.\n+ *\n+ * The maximal ordered sequence of such line pairs (where ordered means\n+ * that the order in the sequence agrees with the order of the lines in\n+ * both files) naturally defines an initial set of common lines.\n+ *\n+ * Now, the algorithm tries to extend the set of common lines by growing\n+ * the line ranges where the files have identical lines.\n+ *\n+ * Between those common lines, the patience diff algorithm is applied\n+ * recursively, until no unique line pairs can be found; these line ranges\n+ * are handled by the well-known Myers algorithm.\n+ */\n+\n+#define NON_UNIQUE ULONG_MAX\n+\n+/*\n+ * This is a hash mapping from line hash to line numbers in the first and\n+ * second file.\n+ */\n+struct hashmap {\n+\tint nr, alloc;\n+\tstruct entry {\n+\t\tunsigned long hash;\n+\t\t/*\n+\t\t * 0 = unused entry, 1 = first line, 2 = second, etc.\n+\t\t * line2 is NON_UNIQUE if the line is not unique\n+\t\t * in either the first or the second file.\n+\t\t */\n+\t\tunsigned long line1, line2;\n+\t\t/*\n+\t\t * \"next\" & \"previous\" are used for the longest common\n+\t\t * sequence;\n+\t\t * initially, \"next\" reflects only the order in file1.\n+\t\t */\n+\t\tstruct entry *next, *previous;\n+\t} *entries, *first, *last;\n+\t/* were common records found? */\n+\tunsigned long has_matches;\n+\tmmfile_t *file1, *file2;\n+\txdfenv_t *env;\n+\txpparam_t const *xpp;\n+};\n+\n+/* The argument \"pass\" is 1 for the first file, 2 for the second. */\n+static void insert_record(int line, struct hashmap *map, int pass)\n+{\n+\txrecord_t **records = pass == 1 ?\n+\t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n+\txrecord_t *record = records[line - 1], *other;\n+\t/*\n+\t * After xdl_prepare_env() (or more precisely, due to\n+\t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n+\t * is _not_ the hash anymore, but a linearized version of it. In\n+\t * other words, the \"ha\" member is guaranteed to start with 0 and\n+\t * the second record's ha can only be 0 or 1, etc.\n+\t *\n+\t * So we multiply ha by 2 in the hope that the hashing was\n+\t * \"unique enough\".\n+\t */\n+\tint index = (int)((record->ha << 1) % map->alloc);\n+\n+\twhile (map->entries[index].line1) {\n+\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n+\t\tif (map->entries[index].hash != record->ha ||\n+\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n+\t\t\t\t\tother->ptr, other->size,\n+\t\t\t\t\tmap->xpp->flags)) {\n+\t\t\tif (++index >= map->alloc)\n+\t\t\t\tindex = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (pass == 2)\n+\t\t\tmap->has_matches = 1;\n+\t\tif (pass == 1 || map->entries[index].line2)\n+\t\t\tmap->entries[index].line2 = NON_UNIQUE;\n+\t\telse\n+\t\t\tmap->entries[index].line2 = line;\n+\t\treturn;\n+\t}\n+\tif (pass == 2)\n+\t\treturn;\n+\tmap->entries[index].line1 = line;\n+\tmap->entries[index].hash = record->ha;\n+\tif (!map->first)\n+\t\tmap->first = map->entries + index;\n+\tif (map->last) {\n+\t\tmap->last->next = map->entries + index;\n+\t\tmap->entries[index].previous = map->last;\n+\t}\n+\tmap->last = map->entries + index;\n+\tmap->nr++;\n+}\n+\n+/*\n+ * This function has to be called for each recursion into the inter-hunk\n+ * parts, as previously non-unique lines can become unique when being\n+ * restricted to a smaller part of the files.\n+ *\n+ * It is assumed that env has been prepared using xdl_prepare().\n+ */\n+static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tstruct hashmap *result,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tresult->file1 = file1;\n+\tresult->file2 = file2;\n+\tresult->xpp = xpp;\n+\tresult->env = env;\n+\n+\t/* We know exactly how large we want the hash map */\n+\tresult->alloc = count1 * 2;\n+\tresult->entries = (struct entry *)\n+\t\txdl_malloc(result->alloc * sizeof(struct entry));\n+\tif (!result->entries)\n+\t\treturn -1;\n+\tmemset(result->entries, 0, result->alloc * sizeof(struct entry));\n+\n+\t/* First, fill with entries from the first file */\n+\twhile (count1--)\n+\t\tinsert_record(line1++, result, 1);\n+\n+\t/* Then search for matches in the second file */\n+\twhile (count2--)\n+\t\tinsert_record(line2++, result, 2);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Find the longest sequence with a smaller last element (meaning a smaller\n+ * line2, as we construct the sequence with entries ordered by line1).\n+ */\n+static int binary_search(struct entry **sequence, int longest,\n+\t\tstruct entry *entry)\n+{\n+\tint left = -1, right = longest;\n+\n+\twhile (left + 1 < right) {\n+\t\tint middle = (left + right) / 2;\n+\t\t/* by construction, no two entries can be equal */\n+\t\tif (sequence[middle]->line2 > entry->line2)\n+\t\t\tright = middle;\n+\t\telse\n+\t\t\tleft = middle;\n+\t}\n+\t/* return the index in \"sequence\", _not_ the sequence length */\n+\treturn left;\n+}\n+\n+/*\n+ * The idea is to start with the list of common unique lines sorted by\n+ * the order in file1. For each of these pairs, the longest (partial)\n+ * sequence whose last element's line2 is smaller is determined.\n+ *\n+ * For efficiency, the sequences are kept in a list containing exactly one\n+ * item per sequence length: the sequence with the smallest last\n+ * element (in terms of line2).\n+ */\n+static struct entry *find_longest_common_sequence(struct hashmap *map)\n+{\n+\tstruct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));\n+\tint longest = 0, i;\n+\tstruct entry *entry;\n+\n+\tfor (entry = map->first; entry; entry = entry->next) {\n+\t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n+\t\t\tcontinue;\n+\t\ti = binary_search(sequence, longest, entry);\n+\t\tentry->previous = i < 0 ? NULL : sequence[i];\n+\t\tsequence[++i] = entry;\n+\t\tif (i == longest)\n+\t\t\tlongest++;\n+\t}\n+\n+\t/* No common unique lines were found */\n+\tif (!longest)\n+\t\treturn NULL;\n+\n+\t/* Iterate starting at the last element, adjusting the \"next\" members */\n+\tentry = sequence[longest - 1];\n+\tentry->next = NULL;\n+\twhile (entry->previous) {\n+\t\tentry->previous->next = entry;\n+\t\tentry = entry->previous;\n+\t}\n+\treturn entry;\n+}\n+\n+static int match(struct hashmap *map, int line1, int line2)\n+{\n+\txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n+\txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n+\treturn xdl_recmatch(record1->ptr, record1->size,\n+\t\trecord2->ptr, record2->size, map->xpp->flags);\n+}\n+\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2);\n+\n+static int walk_common_sequence(struct hashmap *map, struct entry *first,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tint end1 = line1 + count1, end2 = line2 + count2;\n+\tint next1, next2;\n+\n+\tfor (;;) {\n+\t\t/* Try to grow the line ranges of common lines */\n+\t\tif (first) {\n+\t\t\tnext1 = first->line1;\n+\t\t\tnext2 = first->line2;\n+\t\t\twhile (next1 > line1 && next2 > line2 &&\n+\t\t\t\t\tmatch(map, next1 - 1, next2 - 1)) {\n+\t\t\t\tnext1--;\n+\t\t\t\tnext2--;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tnext1 = end1;\n+\t\t\tnext2 = end2;\n+\t\t}\n+\t\twhile (line1 < next1 && line2 < next2 &&\n+\t\t\t\tmatch(map, line1, line2)) {\n+\t\t\tline1++;\n+\t\t\tline2++;\n+\t\t}\n+\n+\t\t/* Recurse */\n+\t\tif (next1 > line1 || next2 > line2) {\n+\t\t\tstruct hashmap submap;\n+\n+\t\t\tmemset(&submap, 0, sizeof(submap));\n+\t\t\tif (patience_diff(map->file1, map->file2,\n+\t\t\t\t\tmap->xpp, map->env,\n+\t\t\t\t\tline1, next1 - line1,\n+\t\t\t\t\tline2, next2 - line2))\n+\t\t\t\treturn -1;\n+\t\t}\n+\n+\t\tif (!first)\n+\t\t\treturn 0;\n+\n+\t\twhile (first->next &&\n+\t\t\t\tfirst->next->line1 == first->line1 + 1 &&\n+\t\t\t\tfirst->next->line2 == first->line2 + 1)\n+\t\t\tfirst = first->next;\n+\n+\t\tline1 = first->line1 + 1;\n+\t\tline2 = first->line2 + 1;\n+\n+\t\tfirst = first->next;\n+\t}\n+}\n+\n+static int fall_back_to_classic_diff(struct hashmap *map,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\t/*\n+\t * This probably does not work outside Git, since\n+\t * we have a very simple mmfile structure.\n+\t *\n+\t * Note: ideally, we would reuse the prepared environment, but\n+\t * the libxdiff interface does not (yet) allow for diffing only\n+\t * ranges of lines instead of the whole files.\n+\t */\n+\tmmfile_t subfile1, subfile2;\n+\txpparam_t xpp;\n+\txdfenv_t env;\n+\n+\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n+\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n+\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n+\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n+\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n+\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n+\txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n+\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n+\t\treturn -1;\n+\n+\tmemcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n+\tmemcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n+\n+\txdl_free_env(&env);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Recursively find the longest common sequence of unique lines,\n+ * and if none was found, ask xdl_do_diff() to do the job.\n+ *\n+ * This function assumes that env was prepared with xdl_prepare_env().\n+ */\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct hashmap map;\n+\tstruct entry *first;\n+\tint result = 0;\n+\n+\t/* trivial case: one side is empty */\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tmemset(&map, 0, sizeof(map));\n+\tif (fill_hashmap(file1, file2, xpp, env, &map,\n+\t\t\tline1, count1, line2, count2))\n+\t\treturn -1;\n+\n+\t/* are there any matching lines at all? */\n+\tif (!map.has_matches) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tfirst = find_longest_common_sequence(&map);\n+\tif (first)\n+\t\tresult = walk_common_sequence(&map, first,\n+\t\t\tline1, count1, line2, count2);\n+\telse\n+\t\tresult = fall_back_to_classic_diff(&map,\n+\t\t\tline1, count1, line2, count2);\n+\n+\treturn result;\n+}\n+\n+int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env)\n+{\n+\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n+\t\treturn -1;\n+\n+\t/*\n+\t * It is a pity that xdl_cleanup_records() not only marks those\n+\t * lines as changes that are only present in one file, but also\n+\t * lines that have multiple matches and happen to be in a \"run\n+\t * of discardable lines\" that patience diff happens to split\n+\t * differently.\n+\t */\n+\tmemset(env->xdf1.rchg, 0, env->xdf1.nrec);\n+\tmemset(env->xdf2.rchg, 0, env->xdf2.nrec);\n+\t/* environment is cleaned up in xdl_diff() */\n+\treturn patience_diff(file1, file2, xpp, env,\n+\t\t\t1, env->xdf1.nrec, 1, env->xdf2.nrec);\n+}\n-- \n1.6.1.rc3.224.g95ac9\n"},{"id":"99212","messageId":"alpine.DEB.1.00.0901022221140.27818@racer","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901022220380.27818@racer","subject":"Re: [PATCH 1/3 v2] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-02T21:59:36Z","receivedAt":"2009-01-02T21:59:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nThe interdiff between v1 and v2 of PATCH 1/3. As you can see, I also \nadded a cleanup of an intermediate xdlenv.\n\nCiao,\nDscho\n\n xdiff/xpatience.c | 11 +++++++++++\n 1 files changed, 11 insertions(+), 0 deletions(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex 6687940..d01cbdd 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -309,6 +309,8 @@ static int fall_back_to_classic_diff(struct hashmap *map,\n \tmemcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n \tmemcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n \n+\txdl_free_env(&env);\n+\n \treturn 0;\n }\n \n@@ -368,6 +370,15 @@ int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,\n \tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n \t\treturn -1;\n \n+\t/*\n+\t * It is a pity that xdl_cleanup_records() not only marks those\n+\t * lines as changes that are only present in one file, but also\n+\t * lines that have multiple matches and happen to be in a \"run\n+\t * of discardable lines\" that patience diff happens to split\n+\t * differently.\n+\t */\n+\tmemset(env->xdf1.rchg, 0, env->xdf1.nrec);\n+\tmemset(env->xdf2.rchg, 0, env->xdf2.nrec);\n \t/* environment is cleaned up in xdl_diff() */\n \treturn patience_diff(file1, file2, xpp, env,\n \t\t\t1, env->xdf1.nrec, 1, env->xdf2.nrec);\n-- \n1.6.1.rc3.224.g95ac9\n"},{"id":"99229","messageId":"alpine.LFD.2.00.0901021500530.3179@localhost.localdomain","threadId":"16159","inReplyTo":"20090102205208.GA9273@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-02T23:05:12Z","receivedAt":"2009-01-02T23:05:12Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 2 Jan 2009, Jeff King wrote:\n> \n> Here's another interesting one: d592b315. The commit removes dashes\n> from git commands in test scripts. Git says:\n> \n> echo \"tag-one-line\" >expect &&\n> - git-tag -l | grep \"^tag-one-line\" >actual &&\n> + git tag -l | grep \"^tag-one-line\" >actual &&\n> test_cmp expect actual &&\n> - git-tag -n0 -l | grep \"^tag-one-line\" >actual &&\n> + git tag -n0 -l | grep \"^tag-one-line\" >actual &&\n> test_cmp expect actual &&\n> - git-tag -n0 -l tag-one-line >actual &&\n> + git tag -n0 -l tag-one-line >actual &&\n> test_cmp expect actual &&\n> \n> whereas patience says:\n> \n> echo \"tag-one-line\" >expect &&\n> - git-tag -l | grep \"^tag-one-line\" >actual &&\n> - test_cmp expect actual &&\n> - git-tag -n0 -l | grep \"^tag-one-line\" >actual &&\n> - test_cmp expect actual &&\n> - git-tag -n0 -l tag-one-line >actual &&\n> + git tag -l | grep \"^tag-one-line\" >actual &&\n> + test_cmp expect actual &&\n> + git tag -n0 -l | grep \"^tag-one-line\" >actual &&\n> + test_cmp expect actual &&\n> + git tag -n0 -l tag-one-line >actual &&\n> test_cmp expect actual &&\n\nYeah, the bazaar version clearly is inferior here. But again, I don't \nthink that's actually a patience diff issue, I think it's because the \nbazaar diff has merged consecutive diff lines too aggressively.\n\nI suspect both patience and the straight Mayers diff (that git uses) \nactually finds exactly the same differences, and then bazaar has a \"merge \ncloseby -/ pairs together if there is just a single unmodified line in \nbetween them\". \n\nAnd _that_ is where it should care whether the unmodified line is complex \nor not. If it's complex, you shouldn't merge it into the -/+ region.\n\n(but yes, it's possible that the bazaar diff uses \"uniqueness\" as a \ncomplexity analysis marker, and while that is somewhat valid, it is _not_ \nvalid enough to be useful. Unique lines tend to be complex, but complex \nlines are _not_ always unique)\n\n\t\tLinus\n"},{"id":"99258","messageId":"20090103162411.GA9234@chistera.yi.org","threadId":"16159","inReplyTo":"20090102193904.GB9129@coredump.intra.peff.net","subject":"Bazaar's patience diff as GIT_EXTERNAL_DIFF","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-03T16:24:11Z","receivedAt":"2009-01-03T16:24:11Z","isPatch":false,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"* Jeff King [Fri, 02 Jan 2009 14:39:04 -0500]:\n\n> If you just want to see the results on some real-world cases (and don't\n> care about measuring performance), try installing bzr and using their\n> patiencediff test program as a GIT_EXTERNAL_DIFF.\n\n> On Debian, it's:\n\n> $ sudo apt-get install bzr\n> $ cat >$HOME/patience <<'EOF'\n> #!/bin/sh\n> exec python /usr/share/pyshared/bzrlib/patiencediff.py \"$2\" \"$5\"\n> EOF\n> $ chmod 755 patience\n> $ GIT_EXTERNAL_DIFF=$HOME/patience git diff\n\nIn case somebody's interested, I have this script lying around that does\nthat, and knows how to colorize the output using bzrtools, and honoring\ncolor.{diff,ui}. No support for color.diff., though.\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \n- Oh my God, you're pimping me out for a new roof?\n- And windows!\n -- Andrew and Bree Van De Kamp\n\n\n#! /usr/bin/python\n\nimport os\nimport sys\nimport stat\nimport subprocess\n\nfrom bzrlib.patiencediff import unified_diff, PatienceSequenceMatcher\ntry:\n from bzrlib.plugins.bzrtools.colordiff import DiffWriter\nexcept ImportError:\n _have_colordiff = False\nelse:\n _have_colordiff = True\n\n##\n\ndef main():\n path = sys.argv[1]\n file1 = open(sys.argv[2], 'rb')\n file2 = open(sys.argv[5], 'rb')\n\n if use_color():\n writer = DiffWriter(sys.stdout, check_style=True)\n else:\n writer = sys.stdout\n\n for line in unified_diff(\n file1.readlines(), file2.readlines(),\n path, path, sequencematcher=PatienceSequenceMatcher):\n writer.write(line)\n\n##\n\ndef use_color():\n if not _have_colordiff:\n return False\n\n for c in ['color.diff', 'color.ui']:\n p = subprocess.Popen(\n ['git', 'config', '--get', c], stdout=subprocess.PIPE)\n if p.wait() == 0:\n when = p.stdout.readline().strip()\n break\n else:\n return False\n\n if when == 'always':\n return True\n elif when in ['false', 'never']:\n return False\n elif when in ['true', 'auto']:\n stdout = sys.stdout.fileno()\n return (os.isatty(stdout) or\n stat.S_ISFIFO(os.fstat(sys.stdout.fileno()).st_mode))\n else:\n return False\n\n##\n\nif __name__ == '__main__':\n sys.exit(main())\n"},{"id":"99461","messageId":"20090106111712.GB30766@artemis.corp","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901011134210.5086@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2009-01-06T11:17:12Z","receivedAt":"2009-01-06T11:17:12Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:\n> \n> Nothing fancy, really, just a straight-forward implementation of the\n> heavily under-documented and under-analyzed paience diff algorithm.\n\nBtw, what is the status of this series ? I see it neither in pu nor in\nnext. And I would gladly see it included in git.\n\nOn jeu, jan 01, 2009 at 07:45:21 +0000, Linus Torvalds wrote:\n> \n> \n> On Thu, 1 Jan 2009, Johannes Schindelin wrote:\n> > \n> > Nothing fancy, really, just a straight-forward implementation of the\n> > heavily under-documented and under-analyzed paience diff algorithm.\n> \n> Exactly because the patience diff is so under-documented, could you \n> perhaps give a few examples of how it differs in the result, and why it's \n> so wonderful? Yes, yes, I can google, and no, no, nothing useful shows up \n> except for *totally* content-free fanboisms. \n> \n> So could we have some actual real data on it?\n\nFor example, look at the following (shamelessly stolen from the real\nlife example http://glandium.org/blog/?p=120).\n\nWith orig.mk reading:\n ] include $(DEPTH)/config/autoconf.mk\n ] \n ] include $(topsrcdir)/config/rules.mk\n ] \n ] libs::\n ] $(INSTALL) $(srcdir)/nsKillAll.js $(DIST)/bin/components\n ] \n ] clean::\n ] rm -f $(DIST)/bin/components/nsKillAll.js\n\nWith patched.mk reading:\n ] include $(DEPTH)/config/autoconf.mk\n ] \n ] EXTRA_COMPONENTS = nsKillAll.js\n ] \n ] include $(topsrcdir)/config/rules.mk\n ] \n ] clean::\n ] rm -f $(DIST)/bin/components/nsKillAll.js\n\nYou get:\n\nNormal git diff | patience diff\n---------------------------------------------------+------------------------------------------\n include $(DEPTH)/config/autoconf.mk | include $(DEPTH)/config/autoconf.mk\n |\n-include $(topsrcdir)/config/rules.mk | +EXTRA_COMPONENTS = nsKillAll.js\n+EXTRA_COMPONENTS = nsKillAll.js | +\n | include $(topsrcdir)/config/rules.mk\n-libs:: |\n- $(INSTALL) $(srcdir)/... | -libs::\n+include $(topsrcdir)/config/rules.mk | - $(INSTALL) $(srcdir)/...\n | -\n clean:: | clean::\n rm -f $(DIST)/bin/components/nsKillAll.js | rm -f $(DIST)/bin/components/nsKillAll.js\n\n\n\nI've checked in many projects I have under git, the differences between\ngit log -p and git log -p --patience. The patience algorithm is really\nreally more readable with it involves code moves with changes in the\nmoved sections. If the section you move across is smaller than the moved\nones, the patience algorithm will show the moved code as removed where\nit was and added where it now is, changes included. The current diff\nwill rather move the smaller invariend section you move across and\npresent mangled diffs involving the function prototypes making it less\nthan readable.\n\nOf course, moving code _and_ modifying it at the same time is rather bad\nstyle. BUt (1) it happens and the fact it's bad style is a bad argument\nto not show a decent diff of it (2) if you construct diffs of a range of\ncommits it happens a lot.\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"99462","messageId":"20090106113943.GA28659@artemis.corp","threadId":"16159","inReplyTo":"20090106111712.GB30766@artemis.corp","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2009-01-06T11:39:43Z","receivedAt":"2009-01-06T11:39:43Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Jan 06, 2009 at 11:17:12AM +0000, Pierre Habouzit wrote:\n> On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:\n> > \n> > Nothing fancy, really, just a straight-forward implementation of the\n> > heavily under-documented and under-analyzed paience diff algorithm.\n> \n> Btw, what is the status of this series ? I see it neither in pu nor in\n> next. And I would gladly see it included in git.\n\nJohannes: I've not had time to investigate, but when finding what I\npresent in the end of this mail, I ran:\n\n git log -p > log-normal\n git log -p --patience > log-patience\n\nin git.git.\n\nI saw that patience diff is slower than normal diff, which is expected,\nbut I had to kill the latter command because it leaks like hell. I've\nnot investigated yet (And yes I'm running your latest posted series).\n\n> On jeu, jan 01, 2009 at 07:45:21 +0000, Linus Torvalds wrote:\n> > On Thu, 1 Jan 2009, Johannes Schindelin wrote:\n> > > \n> > > Nothing fancy, really, just a straight-forward implementation of the\n> > > heavily under-documented and under-analyzed paience diff algorithm.\n> > \n> > Exactly because the patience diff is so under-documented, could you \n> > perhaps give a few examples of how it differs in the result, and why it's \n> > so wonderful? Yes, yes, I can google, and no, no, nothing useful shows up \n> > except for *totally* content-free fanboisms. \n> > \n> > So could we have some actual real data on it?\n\n> I've checked in many projects I have under git, the differences between\n> git log -p and git log -p --patience. The patience algorithm is really\n> really more readable with it involves code moves with changes in the\n> moved sections. If the section you move across is smaller than the moved\n> ones, the patience algorithm will show the moved code as removed where\n> it was and added where it now is, changes included. The current diff\n> will rather move the smaller invariend section you move across and\n> present mangled diffs involving the function prototypes making it less\n> than readable.\n\nActually git.git has a canonical example of this in 214a34d22.\n\nFor those not having the --patience diff applied locally, attached are\nthe two patches git show / git show --patience give. It's of course a\nmatter of taste, but I like the patience version a lot more.\n\nI'm also curious to see what a merge conflict with such a move would\nlook like (e.g. inverting some of the added arguments to the factorized\nfunction of 214a34d22 or something similar). I'm somehow convinced that\nit would generate a nicer conflict somehow.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n\n\ncommit 214a34d22ec59ec7e1166772f06ecf8799f96c96\nAuthor: Florian Weimer \nDate: Sun Aug 31 17:45:04 2008 +0200\n\n git-svn: Introduce SVN::Git::Editor::_chg_file_get_blob\n \n Signed-off-by: Florian Weimer \n Acked-by: Eric Wong \n\ndiff --git a/git-svn.perl b/git-svn.perl\nindex 0479f41..2c3e13f 100755\n--- a/git-svn.perl\n+++ b/git-svn.perl\n@@ -3663,28 +3663,35 @@ sub change_file_prop {\n \t$self->SUPER::change_file_prop($fbat, $pname, $pval, $self->{pool});\n }\n \n-sub chg_file {\n-\tmy ($self, $fbat, $m) = @_;\n-\tif ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {\n-\t\t$self->change_file_prop($fbat,'svn:executable','*');\n-\t} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {\n-\t\t$self->change_file_prop($fbat,'svn:executable',undef);\n-\t}\n-\tmy $fh = Git::temp_acquire('git_blob');\n-\tif ($m->{mode_b} =~ /^120/) {\n+sub _chg_file_get_blob ($$$$) {\n+\tmy ($self, $fbat, $m, $which) = @_;\n+\tmy $fh = Git::temp_acquire(\"git_blob_$which\");\n+\tif ($m->{\"mode_$which\"} =~ /^120/) {\n \t\tprint $fh 'link ' or croak $!;\n \t\t$self->change_file_prop($fbat,'svn:special','*');\n-\t} elsif ($m->{mode_a} =~ /^120/ && $m->{mode_b} !~ /^120/) {\n+\t} elsif ($m->{mode_a} =~ /^120/ && $m->{\"mode_$which\"} !~ /^120/) {\n \t\t$self->change_file_prop($fbat,'svn:special',undef);\n \t}\n-\tmy $size = $::_repository->cat_blob($m->{sha1_b}, $fh);\n-\tcroak \"Failed to read object $m->{sha1_b}\" if ($size < 0);\n+\tmy $blob = $m->{\"sha1_$which\"};\n+\treturn ($fh,) if ($blob =~ /^0{40}$/);\n+\tmy $size = $::_repository->cat_blob($blob, $fh);\n+\tcroak \"Failed to read object $blob\" if ($size < 0);\n \t$fh->flush == 0 or croak $!;\n \tseek $fh, 0, 0 or croak $!;\n \n \tmy $exp = ::md5sum($fh);\n \tseek $fh, 0, 0 or croak $!;\n+\treturn ($fh, $exp);\n+}\n \n+sub chg_file {\n+\tmy ($self, $fbat, $m) = @_;\n+\tif ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {\n+\t\t$self->change_file_prop($fbat,'svn:executable','*');\n+\t} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {\n+\t\t$self->change_file_prop($fbat,'svn:executable',undef);\n+\t}\n+\tmy ($fh, $exp) = _chg_file_get_blob $self, $fbat, $m, 'b';\n \tmy $pool = SVN::Pool->new;\n \tmy $atd = $self->apply_textdelta($fbat, undef, $pool);\n \tmy $got = SVN::TxDelta::send_stream($fh, @$atd, $pool);\n\n\ncommit 214a34d22ec59ec7e1166772f06ecf8799f96c96\nAuthor: Florian Weimer \nDate: Sun Aug 31 17:45:04 2008 +0200\n\n git-svn: Introduce SVN::Git::Editor::_chg_file_get_blob\n \n Signed-off-by: Florian Weimer \n Acked-by: Eric Wong \n\ndiff --git a/git-svn.perl b/git-svn.perl\nindex 0479f41..2c3e13f 100755\n--- a/git-svn.perl\n+++ b/git-svn.perl\n@@ -3663,6 +3663,27 @@ sub change_file_prop {\n \t$self->SUPER::change_file_prop($fbat, $pname, $pval, $self->{pool});\n }\n \n+sub _chg_file_get_blob ($$$$) {\n+\tmy ($self, $fbat, $m, $which) = @_;\n+\tmy $fh = Git::temp_acquire(\"git_blob_$which\");\n+\tif ($m->{\"mode_$which\"} =~ /^120/) {\n+\t\tprint $fh 'link ' or croak $!;\n+\t\t$self->change_file_prop($fbat,'svn:special','*');\n+\t} elsif ($m->{mode_a} =~ /^120/ && $m->{\"mode_$which\"} !~ /^120/) {\n+\t\t$self->change_file_prop($fbat,'svn:special',undef);\n+\t}\n+\tmy $blob = $m->{\"sha1_$which\"};\n+\treturn ($fh,) if ($blob =~ /^0{40}$/);\n+\tmy $size = $::_repository->cat_blob($blob, $fh);\n+\tcroak \"Failed to read object $blob\" if ($size < 0);\n+\t$fh->flush == 0 or croak $!;\n+\tseek $fh, 0, 0 or croak $!;\n+\n+\tmy $exp = ::md5sum($fh);\n+\tseek $fh, 0, 0 or croak $!;\n+\treturn ($fh, $exp);\n+}\n+\n sub chg_file {\n \tmy ($self, $fbat, $m) = @_;\n \tif ($m->{mode_b} =~ /755$/ && $m->{mode_a} !~ /755$/) {\n@@ -3670,21 +3691,7 @@ sub chg_file {\n \t} elsif ($m->{mode_b} !~ /755$/ && $m->{mode_a} =~ /755$/) {\n \t\t$self->change_file_prop($fbat,'svn:executable',undef);\n \t}\n-\tmy $fh = Git::temp_acquire('git_blob');\n-\tif ($m->{mode_b} =~ /^120/) {\n-\t\tprint $fh 'link ' or croak $!;\n-\t\t$self->change_file_prop($fbat,'svn:special','*');\n-\t} elsif ($m->{mode_a} =~ /^120/ && $m->{mode_b} !~ /^120/) {\n-\t\t$self->change_file_prop($fbat,'svn:special',undef);\n-\t}\n-\tmy $size = $::_repository->cat_blob($m->{sha1_b}, $fh);\n-\tcroak \"Failed to read object $m->{sha1_b}\" if ($size < 0);\n-\t$fh->flush == 0 or croak $!;\n-\tseek $fh, 0, 0 or croak $!;\n-\n-\tmy $exp = ::md5sum($fh);\n-\tseek $fh, 0, 0 or croak $!;\n-\n+\tmy ($fh, $exp) = _chg_file_get_blob $self, $fbat, $m, 'b';\n \tmy $pool = SVN::Pool->new;\n \tmy $atd = $self->apply_textdelta($fbat, undef, $pool);\n \tmy $got = SVN::TxDelta::send_stream($fh, @$atd, $pool);\n"},{"id":"99497","messageId":"alpine.DEB.1.00.0901062037250.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"20090106111712.GB30766@artemis.corp","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-06T19:40:02Z","receivedAt":"2009-01-06T19:40:02Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 6 Jan 2009, Pierre Habouzit wrote:\n\n> On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:\n> > \n> > Nothing fancy, really, just a straight-forward implementation of the\n> > heavily under-documented and under-analyzed paience diff algorithm.\n> \n> Btw, what is the status of this series ? I see it neither in pu nor in \n> next. And I would gladly see it included in git.\n\nAFAICT people wanted to be reasonably sure that it is worth the effort.\n\nAlthough I would like to see it in once it is fleshed out -- even if it \ndoes not meet our usefulness standard -- because people said Git is \ninferior for not providing a patience diff. If we have --patience, we can \nsay \"but we have it, it's just not useful, check for yourself\".\n\n> On jeu, jan 01, 2009 at 07:45:21 +0000, Linus Torvalds wrote:\n> > \n> > So could we have some actual real data on it?\n> \n> For example, look at the following (shamelessly stolen from the real\n> life example http://glandium.org/blog/?p=120).\n\nDue to the lines being much longer than 80 characters, this example was \nnot useful to me.\n\nCiao,\nDscho\n"},{"id":"99581","messageId":"20090107143926.GB831@artemis.corp","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901062037250.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2009-01-07T14:39:26Z","receivedAt":"2009-01-07T14:39:26Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Jan 06, 2009 at 07:40:02PM +0000, Johannes Schindelin wrote:\n> Hi,\n> \n> On Tue, 6 Jan 2009, Pierre Habouzit wrote:\n> \n> > On jeu, jan 01, 2009 at 04:38:09 +0000, Johannes Schindelin wrote:\n> > > \n> > > Nothing fancy, really, just a straight-forward implementation of the\n> > > heavily under-documented and under-analyzed paience diff algorithm.\n> > \n> > Btw, what is the status of this series ? I see it neither in pu nor in \n> > next. And I would gladly see it included in git.\n> \n> AFAICT people wanted to be reasonably sure that it is worth the effort.\n\nFair enough.\n\n> Although I would like to see it in once it is fleshed out -- even if it \n> does not meet our usefulness standard -- because people said Git is \n> inferior for not providing a patience diff. If we have --patience, we can \n> say \"but we have it, it's just not useful, check for yourself\".\n\nWell I believe it's useful, but maybe the standard algorithm could be\ntweaked the way Linus proposes to make the \"long\" lines weight louder or\nso.\n\n> Due to the lines being much longer than 80 characters, this example was \n> not useful to me.\n\nI hope the other one was ;)\n\nWRT the leaks, you want to squash the attached patch on the proper\npatches of your series (maybe the xdl_free on map.entries could be put\nin a hasmap_destroy or similar btw, but valgrind reports no more leaks\nin xdiff now). As of timings, with the current implementation, patience\ndiff is around 30% slower than the default implementation, which is a\nbit worse than what I would expect, probably due to the fact that you\nhad to work around the libxdiff interface I guess.\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex d01cbdd..c2ffb03 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -203,8 +203,10 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \t}\n \n \t/* No common unique lines were found */\n-\tif (!longest)\n+\tif (!longest) {\n+\t\txdl_free(sequence);\n \t\treturn NULL;\n+\t}\n \n \t/* Iterate starting at the last element, adjusting the \"next\" members */\n \tentry = sequence[longest - 1];\n@@ -213,6 +215,7 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \t\tentry->previous->next = entry;\n \t\tentry = entry->previous;\n \t}\n+\txdl_free(sequence);\n \treturn entry;\n }\n \n@@ -350,6 +353,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n \t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n \t\twhile(count2--)\n \t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\txdl_free(map.entries);\n \t\treturn 0;\n \t}\n \n@@ -361,6 +365,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n \t\tresult = fall_back_to_classic_diff(&map,\n \t\t\tline1, count1, line2, count2);\n \n+\txdl_free(map.entries);\n \treturn result;\n }\n \n"},{"id":"99595","messageId":"alpine.DEB.1.00.0901071610290.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"20090107143926.GB831@artemis.corp","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T17:01:53Z","receivedAt":"2009-01-07T17:01:53Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Pierre Habouzit wrote:\n\n> On Tue, Jan 06, 2009 at 07:40:02PM +0000, Johannes Schindelin wrote:\n> \n> > Although I would like to see it in once it is fleshed out -- even if \n> > it does not meet our usefulness standard -- because people said Git is \n> > inferior for not providing a patience diff. If we have --patience, we \n> > can say \"but we have it, it's just not useful, check for yourself\".\n> \n> Well I believe it's useful, but maybe the standard algorithm could be \n> tweaked the way Linus proposes to make the \"long\" lines weight louder or \n> so.\n\nI think this \"weighting idea\" is a bit too much of handwaving to start \nanything close to a design; as I pointed out, anything that has something \ndifferent than a 1 for a deleted/added line affects performance \nnegatively.\n\n> WRT the leaks, you want to squash the attached patch on the proper\n> patches of your series (maybe the xdl_free on map.entries could be put\n> in a hasmap_destroy or similar btw, but valgrind reports no more leaks\n> in xdiff now).\n\nThanks!\n\nI also squashed in a patch that avoids calling xdl_cleanup_records() and \nthen memset()ing the rchg array to 0 (which worked around the segmentation \nfault).\n\nPatch 1/3 v3 follows,\nDscho\n"},{"id":"99596","messageId":"alpine.DEB.1.00.0901071802190.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901071610290.7496@intel-tinevez-2-302","subject":"[PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T17:04:09Z","receivedAt":"2009-01-07T17:04:09Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nThe patience diff algorithm produces slightly more intuitive output\nthan the classic Myers algorithm, as it does not try to minimize the\nnumber of +/- lines first, but tries to preserve the lines that are\nunique.\n\nTo this end, it first determines lines that are unique in both files,\nthen the maximal sequence which preserves the order (relative to both\nfiles) is extracted.\n\nStarting from this initial set of common lines, the rest of the lines\nis handled recursively, with Myers' algorithm as a fallback when\nthe patience algorithm fails (due to no common unique lines).\n\nThis patch includes memory leak fixes by Pierre Habouzit.\n\nSigned-off-by: Johannes Schindelin \n---\n\n\tThis comes close to 'next' quality, IMHO.\n\n\tChanges vs v2: Pierre's memory leak fixes, and it now avoids \n\tcalling xdl_cleanup_records() and then throwing away the \n\tresults for patience diff.\n\n\tPierre, could you do the performance tests again? I _think_ it \n\tmight be somewhat faster now because of the xdl_cleanup_records()\n\tavoidance.\n\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xpatience.c | 381 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xprepare.c | 3 +-\n 5 files changed, 389 insertions(+), 1 deletions(-)\n create mode 100644 xdiff/xpatience.c\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 361f802..4da052a 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -32,6 +32,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE (1 << 2)\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n+#define XDF_PATIENCE_DIFF (1 << 5)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 9d0324a..3e97462 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -329,6 +329,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \txdalgoenv_t xenv;\n \tdiffdata_t dd1, dd2;\n \n+\tif (xpp->flags & XDF_PATIENCE_DIFF)\n+\t\treturn xdl_do_patience_diff(mf1, mf2, xpp, xe);\n+\n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n \t\treturn -1;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex 3e099dc..ad033a8 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -55,5 +55,7 @@ int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);\n void xdl_free_script(xdchange_t *xscr);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg);\n+int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *env);\n \n #endif /* #if !defined(XDIFFI_H) */\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nnew file mode 100644\nindex 0000000..e42c16a\n--- /dev/null\n+++ b/xdiff/xpatience.c\n@@ -0,0 +1,381 @@\n+/*\n+ * LibXDiff by Davide Libenzi ( File Differential Library )\n+ * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin\n+ *\n+ * This library is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ *\n+ * This library is distributed in the hope that it will be useful,\n+ * but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ * Lesser General Public License for more details.\n+ *\n+ * You should have received a copy of the GNU Lesser General Public\n+ * License along with this library; if not, write to the Free Software\n+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n+ *\n+ * Davide Libenzi \n+ *\n+ */\n+#include \"xinclude.h\"\n+#include \"xtypes.h\"\n+#include \"xdiff.h\"\n+\n+/*\n+ * The basic idea of patience diff is to find lines that are unique in\n+ * both files. These are intuitively the ones that we want to see as\n+ * common lines.\n+ *\n+ * The maximal ordered sequence of such line pairs (where ordered means\n+ * that the order in the sequence agrees with the order of the lines in\n+ * both files) naturally defines an initial set of common lines.\n+ *\n+ * Now, the algorithm tries to extend the set of common lines by growing\n+ * the line ranges where the files have identical lines.\n+ *\n+ * Between those common lines, the patience diff algorithm is applied\n+ * recursively, until no unique line pairs can be found; these line ranges\n+ * are handled by the well-known Myers algorithm.\n+ */\n+\n+#define NON_UNIQUE ULONG_MAX\n+\n+/*\n+ * This is a hash mapping from line hash to line numbers in the first and\n+ * second file.\n+ */\n+struct hashmap {\n+\tint nr, alloc;\n+\tstruct entry {\n+\t\tunsigned long hash;\n+\t\t/*\n+\t\t * 0 = unused entry, 1 = first line, 2 = second, etc.\n+\t\t * line2 is NON_UNIQUE if the line is not unique\n+\t\t * in either the first or the second file.\n+\t\t */\n+\t\tunsigned long line1, line2;\n+\t\t/*\n+\t\t * \"next\" & \"previous\" are used for the longest common\n+\t\t * sequence;\n+\t\t * initially, \"next\" reflects only the order in file1.\n+\t\t */\n+\t\tstruct entry *next, *previous;\n+\t} *entries, *first, *last;\n+\t/* were common records found? */\n+\tunsigned long has_matches;\n+\tmmfile_t *file1, *file2;\n+\txdfenv_t *env;\n+\txpparam_t const *xpp;\n+};\n+\n+/* The argument \"pass\" is 1 for the first file, 2 for the second. */\n+static void insert_record(int line, struct hashmap *map, int pass)\n+{\n+\txrecord_t **records = pass == 1 ?\n+\t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n+\txrecord_t *record = records[line - 1], *other;\n+\t/*\n+\t * After xdl_prepare_env() (or more precisely, due to\n+\t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n+\t * is _not_ the hash anymore, but a linearized version of it. In\n+\t * other words, the \"ha\" member is guaranteed to start with 0 and\n+\t * the second record's ha can only be 0 or 1, etc.\n+\t *\n+\t * So we multiply ha by 2 in the hope that the hashing was\n+\t * \"unique enough\".\n+\t */\n+\tint index = (int)((record->ha << 1) % map->alloc);\n+\n+\twhile (map->entries[index].line1) {\n+\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n+\t\tif (map->entries[index].hash != record->ha ||\n+\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n+\t\t\t\t\tother->ptr, other->size,\n+\t\t\t\t\tmap->xpp->flags)) {\n+\t\t\tif (++index >= map->alloc)\n+\t\t\t\tindex = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (pass == 2)\n+\t\t\tmap->has_matches = 1;\n+\t\tif (pass == 1 || map->entries[index].line2)\n+\t\t\tmap->entries[index].line2 = NON_UNIQUE;\n+\t\telse\n+\t\t\tmap->entries[index].line2 = line;\n+\t\treturn;\n+\t}\n+\tif (pass == 2)\n+\t\treturn;\n+\tmap->entries[index].line1 = line;\n+\tmap->entries[index].hash = record->ha;\n+\tif (!map->first)\n+\t\tmap->first = map->entries + index;\n+\tif (map->last) {\n+\t\tmap->last->next = map->entries + index;\n+\t\tmap->entries[index].previous = map->last;\n+\t}\n+\tmap->last = map->entries + index;\n+\tmap->nr++;\n+}\n+\n+/*\n+ * This function has to be called for each recursion into the inter-hunk\n+ * parts, as previously non-unique lines can become unique when being\n+ * restricted to a smaller part of the files.\n+ *\n+ * It is assumed that env has been prepared using xdl_prepare().\n+ */\n+static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tstruct hashmap *result,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tresult->file1 = file1;\n+\tresult->file2 = file2;\n+\tresult->xpp = xpp;\n+\tresult->env = env;\n+\n+\t/* We know exactly how large we want the hash map */\n+\tresult->alloc = count1 * 2;\n+\tresult->entries = (struct entry *)\n+\t\txdl_malloc(result->alloc * sizeof(struct entry));\n+\tif (!result->entries)\n+\t\treturn -1;\n+\tmemset(result->entries, 0, result->alloc * sizeof(struct entry));\n+\n+\t/* First, fill with entries from the first file */\n+\twhile (count1--)\n+\t\tinsert_record(line1++, result, 1);\n+\n+\t/* Then search for matches in the second file */\n+\twhile (count2--)\n+\t\tinsert_record(line2++, result, 2);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Find the longest sequence with a smaller last element (meaning a smaller\n+ * line2, as we construct the sequence with entries ordered by line1).\n+ */\n+static int binary_search(struct entry **sequence, int longest,\n+\t\tstruct entry *entry)\n+{\n+\tint left = -1, right = longest;\n+\n+\twhile (left + 1 < right) {\n+\t\tint middle = (left + right) / 2;\n+\t\t/* by construction, no two entries can be equal */\n+\t\tif (sequence[middle]->line2 > entry->line2)\n+\t\t\tright = middle;\n+\t\telse\n+\t\t\tleft = middle;\n+\t}\n+\t/* return the index in \"sequence\", _not_ the sequence length */\n+\treturn left;\n+}\n+\n+/*\n+ * The idea is to start with the list of common unique lines sorted by\n+ * the order in file1. For each of these pairs, the longest (partial)\n+ * sequence whose last element's line2 is smaller is determined.\n+ *\n+ * For efficiency, the sequences are kept in a list containing exactly one\n+ * item per sequence length: the sequence with the smallest last\n+ * element (in terms of line2).\n+ */\n+static struct entry *find_longest_common_sequence(struct hashmap *map)\n+{\n+\tstruct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));\n+\tint longest = 0, i;\n+\tstruct entry *entry;\n+\n+\tfor (entry = map->first; entry; entry = entry->next) {\n+\t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n+\t\t\tcontinue;\n+\t\ti = binary_search(sequence, longest, entry);\n+\t\tentry->previous = i < 0 ? NULL : sequence[i];\n+\t\tsequence[++i] = entry;\n+\t\tif (i == longest)\n+\t\t\tlongest++;\n+\t}\n+\n+\t/* No common unique lines were found */\n+\tif (!longest) {\n+\t\txdl_free(sequence);\n+\t\treturn NULL;\n+\t}\n+\n+\t/* Iterate starting at the last element, adjusting the \"next\" members */\n+\tentry = sequence[longest - 1];\n+\tentry->next = NULL;\n+\twhile (entry->previous) {\n+\t\tentry->previous->next = entry;\n+\t\tentry = entry->previous;\n+\t}\n+\txdl_free(sequence);\n+\treturn entry;\n+}\n+\n+static int match(struct hashmap *map, int line1, int line2)\n+{\n+\txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n+\txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n+\treturn xdl_recmatch(record1->ptr, record1->size,\n+\t\trecord2->ptr, record2->size, map->xpp->flags);\n+}\n+\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2);\n+\n+static int walk_common_sequence(struct hashmap *map, struct entry *first,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tint end1 = line1 + count1, end2 = line2 + count2;\n+\tint next1, next2;\n+\n+\tfor (;;) {\n+\t\t/* Try to grow the line ranges of common lines */\n+\t\tif (first) {\n+\t\t\tnext1 = first->line1;\n+\t\t\tnext2 = first->line2;\n+\t\t\twhile (next1 > line1 && next2 > line2 &&\n+\t\t\t\t\tmatch(map, next1 - 1, next2 - 1)) {\n+\t\t\t\tnext1--;\n+\t\t\t\tnext2--;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tnext1 = end1;\n+\t\t\tnext2 = end2;\n+\t\t}\n+\t\twhile (line1 < next1 && line2 < next2 &&\n+\t\t\t\tmatch(map, line1, line2)) {\n+\t\t\tline1++;\n+\t\t\tline2++;\n+\t\t}\n+\n+\t\t/* Recurse */\n+\t\tif (next1 > line1 || next2 > line2) {\n+\t\t\tstruct hashmap submap;\n+\n+\t\t\tmemset(&submap, 0, sizeof(submap));\n+\t\t\tif (patience_diff(map->file1, map->file2,\n+\t\t\t\t\tmap->xpp, map->env,\n+\t\t\t\t\tline1, next1 - line1,\n+\t\t\t\t\tline2, next2 - line2))\n+\t\t\t\treturn -1;\n+\t\t}\n+\n+\t\tif (!first)\n+\t\t\treturn 0;\n+\n+\t\twhile (first->next &&\n+\t\t\t\tfirst->next->line1 == first->line1 + 1 &&\n+\t\t\t\tfirst->next->line2 == first->line2 + 1)\n+\t\t\tfirst = first->next;\n+\n+\t\tline1 = first->line1 + 1;\n+\t\tline2 = first->line2 + 1;\n+\n+\t\tfirst = first->next;\n+\t}\n+}\n+\n+static int fall_back_to_classic_diff(struct hashmap *map,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\t/*\n+\t * This probably does not work outside Git, since\n+\t * we have a very simple mmfile structure.\n+\t *\n+\t * Note: ideally, we would reuse the prepared environment, but\n+\t * the libxdiff interface does not (yet) allow for diffing only\n+\t * ranges of lines instead of the whole files.\n+\t */\n+\tmmfile_t subfile1, subfile2;\n+\txpparam_t xpp;\n+\txdfenv_t env;\n+\n+\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n+\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n+\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n+\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n+\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n+\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n+\txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n+\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n+\t\treturn -1;\n+\n+\tmemcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n+\tmemcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n+\n+\txdl_free_env(&env);\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Recursively find the longest common sequence of unique lines,\n+ * and if none was found, ask xdl_do_diff() to do the job.\n+ *\n+ * This function assumes that env was prepared with xdl_prepare_env().\n+ */\n+static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct hashmap map;\n+\tstruct entry *first;\n+\tint result = 0;\n+\n+\t/* trivial case: one side is empty */\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tmemset(&map, 0, sizeof(map));\n+\tif (fill_hashmap(file1, file2, xpp, env, &map,\n+\t\t\tline1, count1, line2, count2))\n+\t\treturn -1;\n+\n+\t/* are there any matching lines at all? */\n+\tif (!map.has_matches) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\txdl_free(map.entries);\n+\t\treturn 0;\n+\t}\n+\n+\tfirst = find_longest_common_sequence(&map);\n+\tif (first)\n+\t\tresult = walk_common_sequence(&map, first,\n+\t\t\tline1, count1, line2, count2);\n+\telse\n+\t\tresult = fall_back_to_classic_diff(&map,\n+\t\t\tline1, count1, line2, count2);\n+\n+\txdl_free(map.entries);\n+\treturn result;\n+}\n+\n+int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,\n+\t\txpparam_t const *xpp, xdfenv_t *env)\n+{\n+\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n+\t\treturn -1;\n+\n+\t/* environment is cleaned up in xdl_diff() */\n+\treturn patience_diff(file1, file2, xpp, env,\n+\t\t\t1, env->xdf1.nrec, 1, env->xdf2.nrec);\n+}\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex a43aa72..1689085 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -290,7 +290,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \n \txdl_free_classifier(&cf);\n \n-\tif (xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n+\t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n-- \n1.6.0.2.GIT\n"},{"id":"99598","messageId":"alpine.DEB.1.10.0901071001360.16651@alien.or.mcafeemobile.com","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901071802190.7496@intel-tinevez-2-302","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2009-01-07T18:10:09Z","receivedAt":"2009-01-07T18:10:09Z","isPatch":true,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 7 Jan 2009, Johannes Schindelin wrote:\n\n> \n> The patience diff algorithm produces slightly more intuitive output\n> than the classic Myers algorithm, as it does not try to minimize the\n> number of +/- lines first, but tries to preserve the lines that are\n> unique.\n\nJohannes, sorry I had not time to follow this one. A couple of minor \ncomments that arose just at glancing at the patch.\n\n\n\n> +/*\n> + * LibXDiff by Davide Libenzi ( File Differential Library )\n> + * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin\n> + *\n> + * This library is free software; you can redistribute it and/or\n> + * modify it under the terms of the GNU Lesser General Public\n> + * License as published by the Free Software Foundation; either\n> + * version 2.1 of the License, or (at your option) any later version.\n> + *\n> + * This library is distributed in the hope that it will be useful,\n> + * but WITHOUT ANY WARRANTY; without even the implied warranty of\n> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n> + * Lesser General Public License for more details.\n> + *\n> + * You should have received a copy of the GNU Lesser General Public\n> + * License along with this library; if not, write to the Free Software\n> + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n> + *\n> + * Davide Libenzi \n\nYou do not need to give me credit for something I don't even know how it \nworks ;)\n\n\n\n> +static int fall_back_to_classic_diff(struct hashmap *map,\n> +\t\tint line1, int count1, int line2, int count2)\n> +{\n> +\t/*\n> +\t * This probably does not work outside Git, since\n> +\t * we have a very simple mmfile structure.\n> +\t *\n> +\t * Note: ideally, we would reuse the prepared environment, but\n> +\t * the libxdiff interface does not (yet) allow for diffing only\n> +\t * ranges of lines instead of the whole files.\n> +\t */\n> +\tmmfile_t subfile1, subfile2;\n> +\txpparam_t xpp;\n> +\txdfenv_t env;\n> +\n> +\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n> +\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n> +\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n> +\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n> +\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n> +\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n> +\txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n> +\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n> +\t\treturn -1;\n\nxdiff allows for diffing ranges, and the most efficent method is exactly \nhow you did ;) Once you know the lines pointers, there's no need to pass \nit the whole file and have it scan it whole to find the lines range it has \nto diff. Just pass the limited view like you did.\n\n\n- Davide\n"},{"id":"99601","messageId":"alpine.DEB.1.00.0901071924350.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"alpine.DEB.1.10.0901071001360.16651@alien.or.mcafeemobile.com","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T18:32:42Z","receivedAt":"2009-01-07T18:32:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Davide Libenzi wrote:\n\n> On Wed, 7 Jan 2009, Johannes Schindelin wrote:\n> \n> > The patience diff algorithm produces slightly more intuitive output \n> > than the classic Myers algorithm, as it does not try to minimize the \n> > number of +/- lines first, but tries to preserve the lines that are \n> > unique.\n> \n> Johannes, sorry I had not time to follow this one.\n\nWhat? You mean you actually took some time off around Christmas???\n\n:-)\n\n> A couple of minor comments that arose just at glancing at the patch.\n\nThanks.\n\n> > +/*\n> > + * LibXDiff by Davide Libenzi ( File Differential Library )\n> > + * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin\n> > + *\n> > + * This library is free software; you can redistribute it and/or\n> > + * modify it under the terms of the GNU Lesser General Public\n> > + * License as published by the Free Software Foundation; either\n> > + * version 2.1 of the License, or (at your option) any later version.\n> > + *\n> > + * This library is distributed in the hope that it will be useful,\n> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of\n> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n> > + * Lesser General Public License for more details.\n> > + *\n> > + * You should have received a copy of the GNU Lesser General Public\n> > + * License along with this library; if not, write to the Free Software\n> > + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n> > + *\n> > + * Davide Libenzi \n> \n> You do not need to give me credit for something I don't even know how it \n> works ;)\n\nWell, I meant to pass the copyright to you, or at least share it.\n\n> > +static int fall_back_to_classic_diff(struct hashmap *map,\n> > +\t\tint line1, int count1, int line2, int count2)\n> > +{\n> > +\t/*\n> > +\t * This probably does not work outside Git, since\n> > +\t * we have a very simple mmfile structure.\n> > +\t *\n> > +\t * Note: ideally, we would reuse the prepared environment, but\n> > +\t * the libxdiff interface does not (yet) allow for diffing only\n> > +\t * ranges of lines instead of the whole files.\n> > +\t */\n> > +\tmmfile_t subfile1, subfile2;\n> > +\txpparam_t xpp;\n> > +\txdfenv_t env;\n> > +\n> > +\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n> > +\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n> > +\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n> > +\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n> > +\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n> > +\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n> > +\txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n> > +\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n> > +\t\treturn -1;\n> \n> xdiff allows for diffing ranges, and the most efficent method is exactly \n> how you did ;) Once you know the lines pointers, there's no need to pass \n> it the whole file and have it scan it whole to find the lines range it \n> has to diff. Just pass the limited view like you did.\n\nHeh.\n\nCould it be that you misread my patch, and assumed that I faked an \nxdfenv?\n\nI did not, but instead faked two mmfiles, which is only as simple as I did \nit because in git.git, we only have contiguous mmfiles. (I recall that \nlibxdiff allows for ropes instead of arrays.)\n\nThe way I did it has one big shortcoming: I need to prepare an xdfenv for \nthe subfiles even if I already prepared one for the complete files. IOW \nthe lines are rehashed all over again.\n\nCiao,\nDscho\n"},{"id":"99604","messageId":"alpine.LFD.2.00.0901071056470.3057@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.DEB.1.10.0901071001360.16651@alien.or.mcafeemobile.com","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-07T18:59:03Z","receivedAt":"2009-01-07T18:59:03Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 7 Jan 2009, Davide Libenzi wrote:\n> \n> xdiff allows for diffing ranges, and the most efficent method is exactly \n> how you did ;)\n\nNo, the performance problem is how it needs to re-hash everything. xdiff \ndoesn't seem to have any way to use a \"subset of the hash\", so what the \npatience diff does is to use a subset of the mmfile, and then that will \nforce all the rehashing to take place, which is kind of sad.\n\nIt would be nice (for patience diff) if it could partition the _hashes_ \ninstead of partitioning the _data_. That way it wouldn't need to rehash. \nSee?\n\n\t\tLinus\n"},{"id":"99607","messageId":"alpine.DEB.1.00.0901072056480.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901071056470.3057@localhost.localdomain","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T20:00:40Z","receivedAt":"2009-01-07T20:00:40Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Linus Torvalds wrote:\n\n> On Wed, 7 Jan 2009, Davide Libenzi wrote:\n> > \n> > xdiff allows for diffing ranges, and the most efficent method is \n> > exactly how you did ;)\n> \n> No, the performance problem is how it needs to re-hash everything. xdiff \n> doesn't seem to have any way to use a \"subset of the hash\", so what the \n> patience diff does is to use a subset of the mmfile, and then that will \n> force all the rehashing to take place, which is kind of sad.\n> \n> It would be nice (for patience diff) if it could partition the _hashes_ \n> instead of partitioning the _data_. That way it wouldn't need to rehash. \n> See?\n\nActually, for libxdiff (non-patience), this is not possible, as \nxdl_cleanup_records() rewrites the hashes so that they are in a contiguous \ninterval (0, ..., N-1), where N is the number of distinct lines found.\n\nI am also pretty certain that at least the non-patience part needs the \nmaximum of that \"hash\" to be as small as possible.\n\nHaving said that, if Linus likes patience diff enough to want it faster, \nDscho will improve the speed by avoiding the rehashing for the patience \ndiff part (although the lines for which patience has to fall back to Myers \ndiff will _still_ rehash, but that does not hurt _that_ much in practice).\n\nCiao,\nDscho\n"},{"id":"99608","messageId":"alpine.DEB.1.10.0901071159060.17115@alien.or.mcafeemobile.com","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901071924350.7496@intel-tinevez-2-302","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2009-01-07T20:09:01Z","receivedAt":"2009-01-07T20:09:01Z","isPatch":true,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 7 Jan 2009, Johannes Schindelin wrote:\n\n> Heh.\n> \n> Could it be that you misread my patch, and assumed that I faked an \n> xdfenv?\n> \n> I did not, but instead faked two mmfiles, which is only as simple as I did \n> it because in git.git, we only have contiguous mmfiles. (I recall that \n> libxdiff allows for ropes instead of arrays.)\n> \n> The way I did it has one big shortcoming: I need to prepare an xdfenv for \n> the subfiles even if I already prepared one for the complete files. IOW \n> the lines are rehashed all over again.\n\nI told you I just glanced at the code :)\nIn that way, if you guys decide to merge this new algo, you'll need to \nsplit the prepare from the optimize, and feed it with an already prepared \nenv.\nBefore going that way, have you ever tried to tweak xdl_cleanup_records \nand xdl_clean_mmatch to reduce the level of optimization, and see the \nresults you get? It is possible that you won't need two different algos \ninside git.\n\n\n\n- Davide\n"},{"id":"99609","messageId":"alpine.DEB.1.10.0901071210180.17115@alien.or.mcafeemobile.com","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901071056470.3057@localhost.localdomain","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2009-01-07T20:11:09Z","receivedAt":"2009-01-07T20:11:09Z","isPatch":true,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 7 Jan 2009, Linus Torvalds wrote:\n\n> On Wed, 7 Jan 2009, Davide Libenzi wrote:\n> > \n> > xdiff allows for diffing ranges, and the most efficent method is exactly \n> > how you did ;)\n> \n> No, the performance problem is how it needs to re-hash everything. xdiff \n> doesn't seem to have any way to use a \"subset of the hash\", so what the \n> patience diff does is to use a subset of the mmfile, and then that will \n> force all the rehashing to take place, which is kind of sad.\n> \n> It would be nice (for patience diff) if it could partition the _hashes_ \n> instead of partitioning the _data_. That way it wouldn't need to rehash. \n> See?\n\nYeah, saw that afterwards ;)\n\n\n\n- Davide\n"},{"id":"99610","messageId":"1231359317.6011.12.camel@maia.lan","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901062037250.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-01-07T20:15:17Z","receivedAt":"2009-01-07T20:15:17Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Tue, 2009-01-06 at 20:40 +0100, Johannes Schindelin wrote:\n> Although I would like to see it in once it is fleshed out -- even if it \n> does not meet our usefulness standard -- because people said Git is \n> inferior for not providing a patience diff. If we have --patience, we can \n> say \"but we have it, it's just not useful, check for yourself\".\n\nWhatever happens, the current deterministic diff algorithm needs to stay\nfor generating patch-id's... those really can't be allowed to change.\n\nSam.\n"},{"id":"99611","messageId":"alpine.DEB.1.00.0901072110340.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"alpine.DEB.1.10.0901071159060.17115@alien.or.mcafeemobile.com","subject":"Re: [PATCH v3 1/3] Implement the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T20:19:12Z","receivedAt":"2009-01-07T20:19:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Davide Libenzi wrote:\n\n> On Wed, 7 Jan 2009, Johannes Schindelin wrote:\n> \n> > Could it be that you misread my patch, and assumed that I faked an \n> > xdfenv?\n> > \n> > I did not, but instead faked two mmfiles, which is only as simple as I did \n> > it because in git.git, we only have contiguous mmfiles. (I recall that \n> > libxdiff allows for ropes instead of arrays.)\n> > \n> > The way I did it has one big shortcoming: I need to prepare an xdfenv for \n> > the subfiles even if I already prepared one for the complete files. IOW \n> > the lines are rehashed all over again.\n> \n> I told you I just glanced at the code :)\n> In that way, if you guys decide to merge this new algo, you'll need to \n> split the prepare from the optimize, and feed it with an already prepared \n> env.\n\nRight.\n\n> Before going that way, have you ever tried to tweak xdl_cleanup_records \n> and xdl_clean_mmatch to reduce the level of optimization, and see the \n> results you get? It is possible that you won't need two different algos \n> inside git.\n\nNo, I hadn't thought that libxdiff already determines uniqueness before \nactually running xdl_do_diff().\n\nI also have to admit that I am not as clever as other people, and had \nquite a hard time figuring out as much as I did (for example, that rchg[i] \n== 1 means that this line is to be added/deleted, and that i is in the \nrange 0, ..., N - 1 rather than 1, ..., N).\n\nSo it is quite possible that something patience-like can be done earlier.\n\nHowever, I do not see a way to implement the recursion necessary for the \npatience diff. Remember:\n\n\tpatience(line range):\n\t\tfind unique lines\n\t\tif no unique lines found:\n\t\t\tresort to classical diff\n\t\t\treturn\n\t\textract the longest common sequence of unique common lines\n\t\tbetween those, recurse\n\nWhen recursing, previously non-unique lines can turn unique, of course. \nAnd I do not see how that recursion could be done before \nxdl_clean_mmatch(), short of redoing the hashing and cleaning records up.\n\nOf course, it might well be possible, but I am already out of my depth \nreading something like \"rdis0\" and \"rpdis1\", and being close to despair.\n\n:')\n\nCiao,\nDscho\n\n\t\t\n"},{"id":"99612","messageId":"alpine.LFD.2.00.0901071222300.3057@localhost.localdomain","threadId":"16159","inReplyTo":"1231359317.6011.12.camel@maia.lan","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-07T20:25:27Z","receivedAt":"2009-01-07T20:25:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 8 Jan 2009, Sam Vilain wrote:\n> \n> Whatever happens, the current deterministic diff algorithm needs to stay\n> for generating patch-id's... those really can't be allowed to change.\n\nSure they can.\n\nWe never cache patch-id's over a long time. And we _have_ changed xdiff to \nmodify the output of the patches before, quite regardless of any patience \nissues: see commit 9b28d55401a529ff08c709f42f66e765c93b0a20, which \nadmittedly doesn't affect any _normal_ diffs, but can generate subtly \ndifferent results for some cases.\n\nIt's true that we want the diff algorithm to be deterministic in the sense \nthat over the run of a _single_ rebase operation, the diff between two \nfiles should give similar and deterministic results, but that's certainly \ntrue of patience diff too.\n\n\t\t\tLinus\n"},{"id":"99613","messageId":"alpine.DEB.1.00.0901072121260.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"1231359317.6011.12.camel@maia.lan","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T20:38:36Z","receivedAt":"2009-01-07T20:38:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 8 Jan 2009, Sam Vilain wrote:\n\n> On Tue, 2009-01-06 at 20:40 +0100, Johannes Schindelin wrote:\n> > Although I would like to see it in once it is fleshed out -- even if it \n> > does not meet our usefulness standard -- because people said Git is \n> > inferior for not providing a patience diff. If we have --patience, we can \n> > say \"but we have it, it's just not useful, check for yourself\".\n> \n> Whatever happens, the current deterministic diff algorithm needs to stay\n> for generating patch-id's... those really can't be allowed to change.\n\nOh, there is no discussion about replacing the diff algorithm we have \nright now.\n\nEven if we never output patch-ids anywhere, so we always recalculate them, \nand therefore would be free to replace the diff algorithm with something \nelse.\n\nThe thing why I do not want patience diff to replace the existing code \nis:\n\n- patience diff is slower,\n- patience diff is often not worth it (produces the same, maybe even \n worse output), and\n- patience diff needs the existing code as a fallback anyway.\n\nWhere it could possibly help to change existing behavior is with merging.\n\nSo maybe somebody has some time to play with, and can apply this patch:\n\n-- snip --\ndiff --git a/ll-merge.c b/ll-merge.c\nindex fa2ca52..f731026 100644\n--- a/ll-merge.c\n+++ b/ll-merge.c\n@@ -79,6 +79,8 @@ static int ll_xdl_merge(const struct ll_merge_driver *drv_unused,\n \tmemset(&xpp, 0, sizeof(xpp));\n \tif (git_xmerge_style >= 0)\n \t\tstyle = git_xmerge_style;\n+\tif (getenv(\"GIT_PATIENCE_MERGE\"))\n+\t\txpp.flags |= XDF_PATIENCE_DIFF;\n \treturn xdl_merge(orig,\n \t\t\t src1, name1,\n \t\t\t src2, name2,\n-- snap --\n\nAfter compiling and installing, something like this should be fun to \nwatch:\n\n\t$ git rev-list --all --parents | \\\n\t grep \" .* \" | \\\n\t while read commit parent1 parent2 otherparents\n\t do\n\t\ttest -z \"$otherparents\" || continue\n\t\tgit checkout $parent1 &&\n\t\tgit merge $parent2 &&\n\t\tgit diff > without-patience.txt &&\n\t\tgit reset --hard $parent1 &&\n\t\tGIT_PATIENCE_MERGE=1 git merge $parent2 &&\n\t\tgit diff > with-patience.txt &&\n\t\tif ! cmp without-patience.txt with-patience.txt\n\t\tthen\n\t\t\techo '==============================='\n\t\t\techo \"differences found in merge $commit\"\n\t\t\techo \"without patience: $(wc -l < without-patience.txt)\"\n\t\t\techo \"with patience: $(wc -l < with-patience.txt)\"\n\t\t\techo '-------------------------------'\n\t\t\techo 'without patience:'\n\t\t\tcat without-patience.txt\n\t\t\techo '-------------------------------'\n\t\t\techo 'with patience:'\n\t\t\tcat with-patience.txt\n\t\tfi ||\n\t\texit\n\t done | tee patience-merge.out\n\nCiao,\nDscho\n"},{"id":"99614","messageId":"7v63kqall2.fsf@gitster.siamese.dyndns.org","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901072121260.7496@intel-tinevez-2-302","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-07T20:48:57Z","receivedAt":"2009-01-07T20:48:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> After compiling and installing, something like this should be fun to \n> watch:\n>\n> \t$ git rev-list --all --parents | \\\n> \t grep \" .* \" | \\\n> \t while read commit parent1 parent2 otherparents\n> \t do\n> \t\ttest -z \"$otherparents\" || continue\n> \t\tgit checkout $parent1 &&\n> \t\tgit merge $parent2 &&\n> \t\tgit diff > without-patience.txt &&\n> ...\n> \t\tif ! cmp without-patience.txt with-patience.txt\n> \t\tthen\n> \t\t\techo '==============================='\n> \t\t\techo \"differences found in merge $commit\"\n> ...\n> \t\t\tcat with-patience.txt\n> \t\tfi ||\n> \t\texit\n> \t done | tee patience-merge.out\n\nAn even more interesting test would be possible by dropping \"&&\" from the\ntwo \"git merge\" invocations.\n\n - Your sample will exit at the first conflicting merge otherwise.\n\n - You may find cases where one resolves cleanly while the other leaves\n conflicts.\n"},{"id":"99621","messageId":"alpine.DEB.1.00.0901072213570.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"7v63kqall2.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T22:00:07Z","receivedAt":"2009-01-07T22:00:07Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > After compiling and installing, something like this should be fun to \n> > watch:\n> >\n> > \t$ git rev-list --all --parents | \\\n> > \t grep \" .* \" | \\\n> > \t while read commit parent1 parent2 otherparents\n> > \t do\n> > \t\ttest -z \"$otherparents\" || continue\n> > \t\tgit checkout $parent1 &&\n> > \t\tgit merge $parent2 &&\n> > \t\tgit diff > without-patience.txt &&\n> > ...\n> > \t\tif ! cmp without-patience.txt with-patience.txt\n> > \t\tthen\n> > \t\t\techo '==============================='\n> > \t\t\techo \"differences found in merge $commit\"\n> > ...\n> > \t\t\tcat with-patience.txt\n> > \t\tfi ||\n> > \t\texit\n> > \t done | tee patience-merge.out\n> \n> An even more interesting test would be possible by dropping \"&&\" from the\n> two \"git merge\" invocations.\n> \n> - Your sample will exit at the first conflicting merge otherwise.\n> \n> - You may find cases where one resolves cleanly while the other leaves\n> conflicts.\n\nYeah, that's why I always put \"like\" into that phrase \"something like \nthis\"... :-)\n\nActually, I had to read something and did not want my box to sit idle \nwhile I was doing that, so...\n\nThe most interesting thing to me was: of the 4072 merges I have in my \nlocal git.git clone, only 66 show a difference.\n\nThe next interesting thing: none -- I repeat, none! -- resulted in only \none of both methods having conflicts. In all cases, if patience merge had \nconflicts, so had the classical merge, and vice versa. I would have \nexpected patience merge to handle some conflicts more gracefully.\n\nSo let's go on to the next metric: what are the differences in the --cc \ndiffs' line counts?\n\nOn average, patience merge produced 1.03225806451613 more lines of --cc \ndiff, and the standard deviation between the line counts is \n42.9823669772587.\n\nSo from the line counts' point of view, the difference is lost in the \nnoise.\n\nSo let's look at a concrete example. I take \n41a3e3aa9bdaede9ab7afed206428c1b071060d2, as it is one of the three merges \nwith minimal --cc diff line counts (they all have 33 lines) and where \npatience merge makes a difference.\n\nThis is the --cc diff without patience merge:\n\n-- snip --\ndiff --cc git-am.sh\nindex a391254,5a7695e..0000000\n--- a/git-am.sh\n+++ b/git-am.sh\n@@@ -327,11 -327,20 +327,28 @@@ d\n \t\t\techo \"Patch is empty. Was it split wrong?\"\n \t\t\tstop_here $this\n \t\t}\n++<<<<<<< HEAD:git-am.sh\n +\t\tSUBJECT=\"$(sed -n '/^Subject/ s/Subject: //p' \"$dotest/info\")\"\n +\t\tcase \"$keep_subject\" in -k) SUBJECT=\"[PATCH] $SUBJECT\" ;; esac\n +\n +\t\t(printf '%s\\n\\n' \"$SUBJECT\"; cat \"$dotest/msg\") |\n +\t\t\tgit stripspace > \"$dotest/msg-clean\"\n++=======\n+ \t\tif test -f \"$dotest/rebasing\" &&\n+ \t\t\tcommit=$(sed -e 's/^From \\([0-9a-f]*\\) .*/\\1/' \\\n+ \t\t\t\t-e q \"$dotest/$msgnum\") &&\n+ \t\t\ttest \"$(git cat-file -t \"$commit\")\" = commit\n+ \t\tthen\n+ \t\t\tgit cat-file commit \"$commit\" |\n+ \t\t\tsed -e '1,/^$/d' >\"$dotest/msg-clean\"\n+ \t\telse\n+ \t\t\tSUBJECT=\"$(sed -n '/^Subject/ s/Subject: //p' \"$dotest/info\")\"\n+ \t\t\tcase \"$keep_subject\" in -k) SUBJECT=\"[PATCH] $SUBJECT\" ;; esac\n+ \n+ \t\t\t(echo \"$SUBJECT\" ; echo ; cat \"$dotest/msg\") |\n+ \t\t\t\tgit stripspace > \"$dotest/msg-clean\"\n+ \t\tfi\n++>>>>>>> 5e835cac8622373724235d299f1331ac4cf81ccf:git-am.sh\n \t\t;;\n \tesac\n \n-- snap --\n\nCompare this with the --cc diff _with_ patience merge:\n\n-- snip --\ndiff --cc git-am.sh\nindex a391254,5a7695e..0000000\n--- a/git-am.sh\n+++ b/git-am.sh\n@@@ -327,11 -327,20 +327,25 @@@ d\n \t\t\techo \"Patch is empty. Was it split wrong?\"\n \t\t\tstop_here $this\n \t\t}\n- \t\tSUBJECT=\"$(sed -n '/^Subject/ s/Subject: //p' \"$dotest/info\")\"\n- \t\tcase \"$keep_subject\" in -k) SUBJECT=\"[PATCH] $SUBJECT\" ;; esac\n- \n+ \t\tif test -f \"$dotest/rebasing\" &&\n+ \t\t\tcommit=$(sed -e 's/^From \\([0-9a-f]*\\) .*/\\1/' \\\n+ \t\t\t\t-e q \"$dotest/$msgnum\") &&\n+ \t\t\ttest \"$(git cat-file -t \"$commit\")\" = commit\n+ \t\tthen\n+ \t\t\tgit cat-file commit \"$commit\" |\n+ \t\t\tsed -e '1,/^$/d' >\"$dotest/msg-clean\"\n+ \t\telse\n+ \t\t\tSUBJECT=\"$(sed -n '/^Subject/ s/Subject: //p' \"$dotest/info\")\"\n+ \t\t\tcase \"$keep_subject\" in -k) SUBJECT=\"[PATCH] $SUBJECT\" ;; esac\n+ \n++<<<<<<< HEAD:git-am.sh\n +\t\t(printf '%s\\n\\n' \"$SUBJECT\"; cat \"$dotest/msg\") |\n +\t\t\tgit stripspace > \"$dotest/msg-clean\"\n++=======\n+ \t\t\t(echo \"$SUBJECT\" ; echo ; cat \"$dotest/msg\") |\n+ \t\t\t\tgit stripspace > \"$dotest/msg-clean\"\n+ \t\tfi\n++>>>>>>> 5e835cac8622373724235d299f1331ac4cf81ccf:git-am.sh\n \t\t;;\n \tesac\n \n-- snap --\n\nSo, the patience merge resulted in a much smaller _conflict_.\n\nHowever, another such merge is 276328ffb87cefdc515bee5f09916aea6e0244ed. \nThis is the --cc diff without patience merge:\n\n-- snip --\ndiff --cc diff.c\nindex 4e4e439,f91f256..0000000\n--- a/diff.c\n+++ b/diff.c\n@@@ -1498,19 -1464,13 +1498,28 @@@ static void builtin_diff(const char *na\n \tchar *a_one, *b_two;\n \tconst char *set = diff_get_color_opt(o, DIFF_METAINFO);\n \tconst char *reset = diff_get_color_opt(o, DIFF_RESET);\n +\tconst char *a_prefix, *b_prefix;\n +\n +\tdiff_set_mnemonic_prefix(o, \"a/\", \"b/\");\n +\tif (DIFF_OPT_TST(o, REVERSE_DIFF)) {\n +\t\ta_prefix = o->b_prefix;\n +\t\tb_prefix = o->a_prefix;\n +\t} else {\n +\t\ta_prefix = o->a_prefix;\n +\t\tb_prefix = o->b_prefix;\n +\t}\n \n++<<<<<<< HEAD:diff.c\n +\ta_one = quote_two(a_prefix, name_a + (*name_a == '/'));\n +\tb_two = quote_two(b_prefix, name_b + (*name_b == '/'));\n++=======\n+ \t/* Never use a non-valid filename anywhere if at all possible */\n+ \tname_a = DIFF_FILE_VALID(one) ? name_a : name_b;\n+ \tname_b = DIFF_FILE_VALID(two) ? name_b : name_a;\n+ \n+ \ta_one = quote_two(o->a_prefix, name_a + (*name_a == '/'));\n+ \tb_two = quote_two(o->b_prefix, name_b + (*name_b == '/'));\n++>>>>>>> e261cf94848d31868c21fb11cade51c30dfcdbe7:diff.c\n \tlbl[0] = DIFF_FILE_VALID(one) ? a_one : \"/dev/null\";\n \tlbl[1] = DIFF_FILE_VALID(two) ? b_two : \"/dev/null\";\n \tfprintf(o->file, \"%sdiff --git %s %s%s\\n\", set, a_one, b_two, reset);\n-- snap --\n\nAnd this is _with_ patience merge:\n\n-- snip --\ndiff --cc diff.c\nindex 4e4e439,f91f256..0000000\n--- a/diff.c\n+++ b/diff.c\n@@@ -1498,19 -1464,13 +1498,28 @@@ static void builtin_diff(const char *na\n \tchar *a_one, *b_two;\n \tconst char *set = diff_get_color_opt(o, DIFF_METAINFO);\n \tconst char *reset = diff_get_color_opt(o, DIFF_RESET);\n +\tconst char *a_prefix, *b_prefix;\n +\n++<<<<<<< HEAD:diff.c\n +\tdiff_set_mnemonic_prefix(o, \"a/\", \"b/\");\n +\tif (DIFF_OPT_TST(o, REVERSE_DIFF)) {\n +\t\ta_prefix = o->b_prefix;\n +\t\tb_prefix = o->a_prefix;\n +\t} else {\n +\t\ta_prefix = o->a_prefix;\n +\t\tb_prefix = o->b_prefix;\n +\t}\n \n +\ta_one = quote_two(a_prefix, name_a + (*name_a == '/'));\n +\tb_two = quote_two(b_prefix, name_b + (*name_b == '/'));\n++=======\n+ \t/* Never use a non-valid filename anywhere if at all possible */\n+ \tname_a = DIFF_FILE_VALID(one) ? name_a : name_b;\n+ \tname_b = DIFF_FILE_VALID(two) ? name_b : name_a;\n+ \n+ \ta_one = quote_two(o->a_prefix, name_a + (*name_a == '/'));\n+ \tb_two = quote_two(o->b_prefix, name_b + (*name_b == '/'));\n++>>>>>>> e261cf94848d31868c21fb11cade51c30dfcdbe7:diff.c\n \tlbl[0] = DIFF_FILE_VALID(one) ? a_one : \"/dev/null\";\n \tlbl[1] = DIFF_FILE_VALID(two) ? b_two : \"/dev/null\";\n \tfprintf(o->file, \"%sdiff --git %s %s%s\\n\", set, a_one, b_two, reset);\n-- snap --\n\nSo again, we have no clear winner.\n\nTherefore I counted the lines between conflict markers (actually, a perl \nscript did). Of these 66 merges, on average patience merge produced \n4.46774193548387 _fewer_ lines between conflict markers.\n\nTake that with a grain of salt, though: the standard deviation of this \ndifference is a hefty 121.163046639509 lines.\n\nThe worst case for patience diff was the merge \n4698ef555a1706fe322a68a02a21fb1087940ac3, where the --cc diff line counts \nare 1300 (without) vs 1301 (with patience merge), but the lines between \nconflict markers are 197 vs a ridiculous 826 lines!\n\nBut you should take that also with a grain of salt: this merge is a \n_subtree_ merge, and my test redid it as a _non-subtree_ merge.\n\nSo I restricted the analysis to the non-subtree merges, and now \nnon-patience merge comes out 6.97297297297297 conflict lines fewer than \npatience merge, with a standard deviation of 58.941106657867 (with a total \ncount of 37 merges).\n\nNote that ~7 lines difference with a standard deviation of ~59 lines is \npretty close to ~0 lines difference.\n\nIn the end, the additional expense of patience merge might just not be \nworth it.\n\nCiao,\nDscho\n"},{"id":"99625","messageId":"20090107224504.GA29537@artemis.corp","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901072213570.7496@intel-tinevez-2-302","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2009-01-07T22:45:04Z","receivedAt":"2009-01-07T22:45:04Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Wed, Jan 07, 2009 at 10:00:07PM +0000, Johannes Schindelin wrote:\n> Therefore I counted the lines between conflict markers (actually, a perl \n> script did). Of these 66 merges, on average patience merge produced \n> 4.46774193548387 _fewer_ lines between conflict markers.\n> \n> Take that with a grain of salt, though: the standard deviation of this \n> difference is a hefty 121.163046639509 lines.\n> \n> The worst case for patience diff was the merge \n> 4698ef555a1706fe322a68a02a21fb1087940ac3, where the --cc diff line counts \n> are 1300 (without) vs 1301 (with patience merge), but the lines between \n> conflict markers are 197 vs a ridiculous 826 lines!\n> \n> But you should take that also with a grain of salt: this merge is a \n> _subtree_ merge, and my test redid it as a _non-subtree_ merge.\n> \n> So I restricted the analysis to the non-subtree merges, and now \n> non-patience merge comes out 6.97297297297297 conflict lines fewer than \n> patience merge, with a standard deviation of 58.941106657867 (with a total \n> count of 37 merges).\n> \n> Note that ~7 lines difference with a standard deviation of ~59 lines is \n> pretty close to ~0 lines difference.\n> \n> In the end, the additional expense of patience merge might just not be \n> worth it.\n\nDepends, if it can help generating nicer merges, it's good to have.\n\nWe could have an option to git-merge that tries hard to generate the\nsmallest conflict possible. _that_ would really really be worth it. I\nmean, I've had really really tricky conflicts to work with where\ngit-merge genrated ridiculously big conflicts, and where I hard to\nresort using UI tools to perform the merge (meld IIRC to name it), and\ngiven how slow and crappy those tools are, I would gladly restart a\nmerge with a --generate-smallest-conflicts-as-possible if it can save me\nfrom those merge tools.\n\nYMMV though.\n\nPS: I never thought the patience diff is a silver bullet, it's just yet\n another tool in the toolbox.\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"99627","messageId":"alpine.DEB.1.00.0901080001410.7496@intel-tinevez-2-302","threadId":"16159","inReplyTo":"20090107224504.GA29537@artemis.corp","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-07T23:03:18Z","receivedAt":"2009-01-07T23:03:18Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 7 Jan 2009, Pierre Habouzit wrote:\n\n> On Wed, Jan 07, 2009 at 10:00:07PM +0000, Johannes Schindelin wrote:\n> > Therefore I counted the lines between conflict markers (actually, a perl \n> > script did). Of these 66 merges, on average patience merge produced \n> > 4.46774193548387 _fewer_ lines between conflict markers.\n> > \n> > Take that with a grain of salt, though: the standard deviation of this \n> > difference is a hefty 121.163046639509 lines.\n> > \n> > The worst case for patience diff was the merge \n> > 4698ef555a1706fe322a68a02a21fb1087940ac3, where the --cc diff line counts \n> > are 1300 (without) vs 1301 (with patience merge), but the lines between \n> > conflict markers are 197 vs a ridiculous 826 lines!\n> > \n> > But you should take that also with a grain of salt: this merge is a \n> > _subtree_ merge, and my test redid it as a _non-subtree_ merge.\n> > \n> > So I restricted the analysis to the non-subtree merges, and now \n> > non-patience merge comes out 6.97297297297297 conflict lines fewer than \n> > patience merge, with a standard deviation of 58.941106657867 (with a total \n> > count of 37 merges).\n> > \n> > Note that ~7 lines difference with a standard deviation of ~59 lines is \n> > pretty close to ~0 lines difference.\n> > \n> > In the end, the additional expense of patience merge might just not be \n> > worth it.\n> \n> Depends, if it can help generating nicer merges, it's good to have.\n> \n> We could have an option to git-merge that tries hard to generate the\n> smallest conflict possible.\n\nI also showed you examples, in addition to numbers, exactly to point out \nthat shorter conflicts do not necessarily mean nicer conflicts.\n\nCiao,\nDscho\n"},{"id":"99657","messageId":"49656581.4010805@vilain.net","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901071222300.3057@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-01-08T02:31:29Z","receivedAt":"2009-01-08T02:31:29Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> On Thu, 8 Jan 2009, Sam Vilain wrote:\n> \n>> Whatever happens, the current deterministic diff algorithm needs to stay\n>> for generating patch-id's... those really can't be allowed to change.\n>> \n>\n> Sure they can.\n>\n> We never cache patch-id's over a long time. And we _have_ changed xdiff to \n> modify the output of the patches before, quite regardless of any patience \n> issues: see commit 9b28d55401a529ff08c709f42f66e765c93b0a20, which \n> admittedly doesn't affect any _normal_ diffs, but can generate subtly \n> different results for some cases.\n> \n\nThere's at least one person who thinks that they should be deterministic \nenough to be able to be placed in commit messages;\n\nhttp://article.gmane.org/gmane.comp.version-control.git/95671\n\nNow of course the git cherry-pick feature to add the old patch ID to the \ncommit message isn't written yet; but unless there was a fall-back mode \nto produce a \"stable\" patch ID, these breadcrumbs would become (even \nmore) worthless.\n\nSam\n"},{"id":"100981","messageId":"20090108195511.GA8734@chistera.yi.org","threadId":"16159","inReplyTo":null,"subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-08T19:55:11Z","receivedAt":"2009-01-08T19:55:11Z","isPatch":true,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"* Linus Torvalds [Fri, 02 Jan 2009 08:42:04 -0800]:\n\n> Yes, this one is a real patience diff change, but it's also the same one \n> that I've seen in the google fanboi findings. What google did _not_ show \n> was any real-life examples, or anybody doing any critical analysis.\n\nThis comes a bit late and maybe it's redundant, but somebody just sent\nto a Debian mailing list a patch that was hard to read, and patience\nimproved it. (I realize it's quite similar in spirit to the \"toy\npatience example\" that google returns, but this at list is a *real*\nexample where patience helped me read a patch.)\n\nI'm also attaching bzr diff output, because it's still more readable\nIMHO. (I realize that's independent of patience, as you explained, but\nI'm making a point that it'd be nice to have this addressed by somebody\nknowledgeable.)\n\nThanks,\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \n- Are you sure we're good?\n- Always.\n -- Rory and Lorelai\n\n\ndiff --git util_sock.c util_sock.c\nindex e20768e..f7b9145 100644\n--- util_sock.c\n+++ util_sock.c\n@@ -1037,40 +1037,109 @@ NTSTATUS read_data(int fd, char *buffer, size_t N)\n }\n \n /****************************************************************************\n- Write data to a fd.\n+ Write all data from an iov array\n ****************************************************************************/\n \n-ssize_t write_data(int fd, const char *buffer, size_t N)\n+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)\n {\n-\tsize_t total=0;\n-\tssize_t ret;\n-\tchar addr[INET6_ADDRSTRLEN];\n+\tint i;\n+\tsize_t to_send;\n+\tssize_t thistime;\n+\tsize_t sent;\n+\tstruct iovec *iov_copy, *iov;\n \n-\twhile (total < N) {\n-\t\tret = sys_write(fd,buffer + total,N - total);\n+\tto_send = 0;\n+\tfor (i=0; i 0) {\n+\t\t\tif (thistime < iov[0].iov_len) {\n+\t\t\t\tchar *new_base =\n+\t\t\t\t\t(char *)iov[0].iov_base + thistime;\n+\t\t\t\tiov[0].iov_base = new_base;\n+\t\t\t\tiov[0].iov_len -= thistime;\n+\t\t\t\tbreak;\n \t\t\t}\n-\t\t\treturn -1;\n+\t\t\tthistime -= iov[0].iov_len;\n+\t\t\tiov += 1;\n+\t\t\tiovcnt -= 1;\n \t\t}\n \n-\t\tif (ret == 0) {\n-\t\t\treturn total;\n+\t\tthistime = sys_writev(fd, iov, iovcnt);\n+\t\tif (thistime <= 0) {\n+\t\t\tbreak;\n \t\t}\n+\t\tsent += thistime;\n+\t}\n+\n+\tTALLOC_FREE(iov_copy);\n+\treturn sent;\n+}\n+\n+/****************************************************************************\n+ Write data to a fd.\n+****************************************************************************/\n+\n+/****************************************************************************\n+ Write data to a fd.\n+****************************************************************************/\n+\n+ssize_t write_data(int fd, const char *buffer, size_t N)\n+{\n+\tssize_t ret;\n+\tstruct iovec iov;\n+\n+\tiov.iov_base = CONST_DISCARD(char *, buffer);\n+\tiov.iov_len = N;\n+\n+\tret = write_data_iov(fd, &iov, 1);\n+\tif (ret >= 0) {\n+\t\treturn ret;\n+\t}\n \n-\t\ttotal += ret;\n+\tif (fd == get_client_fd()) {\n+\t\tchar addr[INET6_ADDRSTRLEN];\n+\t\t/*\n+\t\t * Try and give an error message saying what client failed.\n+\t\t */\n+\t\tDEBUG(0, (\"write_data: write failure in writing to client %s. \"\n+\t\t\t \"Error %s\\n\", get_peer_addr(fd,addr,sizeof(addr)),\n+\t\t\t strerror(errno)));\n+\t} else {\n+\t\tDEBUG(0,(\"write_data: write failure. Error = %s\\n\",\n+\t\t\t strerror(errno) ));\n \t}\n-\treturn (ssize_t)total;\n+\n+\treturn -1;\n }\n \n /****************************************************************************\n\n\ndiff --git util_sock.c util_sock.c\nindex e20768e..f7b9145 100644\n--- util_sock.c\n+++ util_sock.c\n@@ -1037,40 +1037,109 @@ NTSTATUS read_data(int fd, char *buffer, size_t N)\n }\n \n /****************************************************************************\n+ Write all data from an iov array\n+****************************************************************************/\n+\n+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)\n+{\n+\tint i;\n+\tsize_t to_send;\n+\tssize_t thistime;\n+\tsize_t sent;\n+\tstruct iovec *iov_copy, *iov;\n+\n+\tto_send = 0;\n+\tfor (i=0; i 0) {\n+\t\t\tif (thistime < iov[0].iov_len) {\n+\t\t\t\tchar *new_base =\n+\t\t\t\t\t(char *)iov[0].iov_base + thistime;\n+\t\t\t\tiov[0].iov_base = new_base;\n+\t\t\t\tiov[0].iov_len -= thistime;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tthistime -= iov[0].iov_len;\n+\t\t\tiov += 1;\n+\t\t\tiovcnt -= 1;\n+\t\t}\n+\n+\t\tthistime = sys_writev(fd, iov, iovcnt);\n+\t\tif (thistime <= 0) {\n+\t\t\tbreak;\n+\t\t}\n+\t\tsent += thistime;\n+\t}\n+\n+\tTALLOC_FREE(iov_copy);\n+\treturn sent;\n+}\n+\n+/****************************************************************************\n+ Write data to a fd.\n+****************************************************************************/\n+\n+/****************************************************************************\n Write data to a fd.\n ****************************************************************************/\n \n ssize_t write_data(int fd, const char *buffer, size_t N)\n {\n-\tsize_t total=0;\n \tssize_t ret;\n-\tchar addr[INET6_ADDRSTRLEN];\n+\tstruct iovec iov;\n \n-\twhile (total < N) {\n-\t\tret = sys_write(fd,buffer + total,N - total);\n+\tiov.iov_base = CONST_DISCARD(char *, buffer);\n+\tiov.iov_len = N;\n \n-\t\tif (ret == -1) {\n-\t\t\tif (fd == get_client_fd()) {\n-\t\t\t\t/* Try and give an error message saying\n-\t\t\t\t * what client failed. */\n-\t\t\t\tDEBUG(0,(\"write_data: write failure in \"\n-\t\t\t\t\t\"writing to client %s. Error %s\\n\",\n-\t\t\t\t\tget_peer_addr(fd,addr,sizeof(addr)),\n-\t\t\t\t\tstrerror(errno) ));\n-\t\t\t} else {\n-\t\t\t\tDEBUG(0,(\"write_data: write failure. \"\n-\t\t\t\t\t\"Error = %s\\n\", strerror(errno) ));\n-\t\t\t}\n-\t\t\treturn -1;\n-\t\t}\n-\n-\t\tif (ret == 0) {\n-\t\t\treturn total;\n-\t\t}\n+\tret = write_data_iov(fd, &iov, 1);\n+\tif (ret >= 0) {\n+\t\treturn ret;\n+\t}\n \n-\t\ttotal += ret;\n+\tif (fd == get_client_fd()) {\n+\t\tchar addr[INET6_ADDRSTRLEN];\n+\t\t/*\n+\t\t * Try and give an error message saying what client failed.\n+\t\t */\n+\t\tDEBUG(0, (\"write_data: write failure in writing to client %s. \"\n+\t\t\t \"Error %s\\n\", get_peer_addr(fd,addr,sizeof(addr)),\n+\t\t\t strerror(errno)));\n+\t} else {\n+\t\tDEBUG(0,(\"write_data: write failure. Error = %s\\n\",\n+\t\t\t strerror(errno) ));\n \t}\n-\treturn (ssize_t)total;\n+\n+\treturn -1;\n }\n \n /****************************************************************************\n\n\n--- util_sock.c\n+++ util_sock.c\n@@ -1037,40 +1037,109 @@\n }\n \n /****************************************************************************\n+ Write all data from an iov array\n+****************************************************************************/\n+\n+ssize_t write_data_iov(int fd, const struct iovec *orig_iov, int iovcnt)\n+{\n+\tint i;\n+\tsize_t to_send;\n+\tssize_t thistime;\n+\tsize_t sent;\n+\tstruct iovec *iov_copy, *iov;\n+\n+\tto_send = 0;\n+\tfor (i=0; i 0) {\n+\t\t\tif (thistime < iov[0].iov_len) {\n+\t\t\t\tchar *new_base =\n+\t\t\t\t\t(char *)iov[0].iov_base + thistime;\n+\t\t\t\tiov[0].iov_base = new_base;\n+\t\t\t\tiov[0].iov_len -= thistime;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tthistime -= iov[0].iov_len;\n+\t\t\tiov += 1;\n+\t\t\tiovcnt -= 1;\n+\t\t}\n+\n+\t\tthistime = sys_writev(fd, iov, iovcnt);\n+\t\tif (thistime <= 0) {\n+\t\t\tbreak;\n+\t\t}\n+\t\tsent += thistime;\n+\t}\n+\n+\tTALLOC_FREE(iov_copy);\n+\treturn sent;\n+}\n+\n+/****************************************************************************\n+ Write data to a fd.\n+****************************************************************************/\n+\n+/****************************************************************************\n Write data to a fd.\n ****************************************************************************/\n \n ssize_t write_data(int fd, const char *buffer, size_t N)\n {\n-\tsize_t total=0;\n \tssize_t ret;\n-\tchar addr[INET6_ADDRSTRLEN];\n-\n-\twhile (total < N) {\n-\t\tret = sys_write(fd,buffer + total,N - total);\n-\n-\t\tif (ret == -1) {\n-\t\t\tif (fd == get_client_fd()) {\n-\t\t\t\t/* Try and give an error message saying\n-\t\t\t\t * what client failed. */\n-\t\t\t\tDEBUG(0,(\"write_data: write failure in \"\n-\t\t\t\t\t\"writing to client %s. Error %s\\n\",\n-\t\t\t\t\tget_peer_addr(fd,addr,sizeof(addr)),\n-\t\t\t\t\tstrerror(errno) ));\n-\t\t\t} else {\n-\t\t\t\tDEBUG(0,(\"write_data: write failure. \"\n-\t\t\t\t\t\"Error = %s\\n\", strerror(errno) ));\n-\t\t\t}\n-\t\t\treturn -1;\n-\t\t}\n-\n-\t\tif (ret == 0) {\n-\t\t\treturn total;\n-\t\t}\n-\n-\t\ttotal += ret;\n-\t}\n-\treturn (ssize_t)total;\n+\tstruct iovec iov;\n+\n+\tiov.iov_base = CONST_DISCARD(char *, buffer);\n+\tiov.iov_len = N;\n+\n+\tret = write_data_iov(fd, &iov, 1);\n+\tif (ret >= 0) {\n+\t\treturn ret;\n+\t}\n+\n+\tif (fd == get_client_fd()) {\n+\t\tchar addr[INET6_ADDRSTRLEN];\n+\t\t/*\n+\t\t * Try and give an error message saying what client failed.\n+\t\t */\n+\t\tDEBUG(0, (\"write_data: write failure in writing to client %s. \"\n+\t\t\t \"Error %s\\n\", get_peer_addr(fd,addr,sizeof(addr)),\n+\t\t\t strerror(errno)));\n+\t} else {\n+\t\tDEBUG(0,(\"write_data: write failure. Error = %s\\n\",\n+\t\t\t strerror(errno) ));\n+\t}\n+\n+\treturn -1;\n }\n \n /****************************************************************************\n"},{"id":"99740","messageId":"20090108200611.GA9694@chistera.yi.org","threadId":"16159","inReplyTo":"20090108195511.GA8734@chistera.yi.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-08T20:06:11Z","receivedAt":"2009-01-08T20:06:11Z","isPatch":true,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"(My apologies for breaking the thread.)\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \n«¡Pero si es tan español que debe de tener el cerebro en forma de botijo,\ncon pitorro y todo!»\n -- Javier Cercas, “La velocidad de la luz”\n"},{"id":"99763","messageId":"7v7i552clz.fsf@gitster.siamese.dyndns.org","threadId":"16159","inReplyTo":"20090108195511.GA8734@chistera.yi.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-09T06:54:32Z","receivedAt":"2009-01-09T06:54:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Adeodato Simó writes:\n\n> * Linus Torvalds [Fri, 02 Jan 2009 08:42:04 -0800]:\n>\n>> Yes, this one is a real patience diff change, but it's also the same one \n>> that I've seen in the google fanboi findings. What google did _not_ show \n>> was any real-life examples, or anybody doing any critical analysis.\n>\n> This comes a bit late and maybe it's redundant, but somebody just sent\n> to a Debian mailing list a patch that was hard to read, and patience\n> improved it. (I realize it's quite similar in spirit to the \"toy\n> patience example\" that google returns, but this at list is a *real*\n> example where patience helped me read a patch.)\n>\n> I'm also attaching bzr diff output, because it's still more readable\n> IMHO. (I realize that's independent of patience, as you explained, but\n> I'm making a point that it'd be nice to have this addressed by somebody\n> knowledgeable.)\n\nI found thd difference between the Bzr diff and Dscho diff somewhat\ninteresting. It shows that sometimes it makes the results easier to read\nto consider blank lines (and lines with only punctuation marks) that match\nto be non-matching when they appear inside a block of other consecutive\nnon-matching lines, even though the result may become larger.\n\nThe part Bzr gives this result:\n\n> +/****************************************************************************\n> Write data to a fd.\n> ****************************************************************************/\n> \n> ssize_t write_data(int fd, const char *buffer, size_t N)\n> {\n> -\tsize_t total=0;\n> \tssize_t ret;\n> -\tchar addr[INET6_ADDRSTRLEN];\n> ... all \"removed\"\n> -\twhile (total < N) {\n> -\t\ttotal += ret;\n> -\t}\n> -\treturn (ssize_t)total;\n> +\tstruct iovec iov;\n> +\n> +\tiov.iov_base = CONST_DISCARD(char *, buffer);\n> ... all \"added\"\n> +\n> +\n> +\treturn -1;\n> }\n> \n> /****************************************************************************\n\nis shown by the Dscho git-diff like this:\n\n> Write data to a fd.\n> ****************************************************************************/\n> \n> ssize_t write_data(int fd, const char *buffer, size_t N)\n> {\n> -\tsize_t total=0;\n> \tssize_t ret;\n> -\tchar addr[INET6_ADDRSTRLEN];\n> +\tstruct iovec iov;\n> \n> -\twhile (total < N) {\n> -\t\tret = sys_write(fd,buffer + total,N - total);\n> +\tiov.iov_base = CONST_DISCARD(char *, buffer);\n> +\tiov.iov_len = N;\n> \n> -\t\tif (ret == -1) {\n> -\t\t\tif (fd == get_client_fd()) {\n> ... all \"removed\"\n> -\n> -\t\tif (ret == 0) {\n> -\t\t\treturn total;\n> -\t\t}\n> +\tret = write_data_iov(fd, &iov, 1);\n> +\tif (ret >= 0) {\n> +\t\treturn ret;\n> +\t}\n> \n> -\t\ttotal += ret;\n> +\tif (fd == get_client_fd()) {\n> +\t\tchar addr[INET6_ADDRSTRLEN];\n> ... all \"added\"\n> +\t\tDEBUG(0,(\"write_data: write failure. Error = %s\\n\",\n> +\t\t\t strerror(errno) ));\n> \t}\n> -\treturn (ssize_t)total;\n> +\n> +\treturn -1;\n> }\n\nIf we find the \"common\" context lines that have only blank and punctuation\nletters in Dscho output, turn each of them into \"-\" and \"+\", and rearrange\nthem so that all \"-\" are together followed by \"+\", it will match Bzr\noutput.\n"},{"id":"99790","messageId":"alpine.DEB.1.00.0901091405460.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"7v7i552clz.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-09T13:07:28Z","receivedAt":"2009-01-09T13:07:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 8 Jan 2009, Junio C Hamano wrote:\n\n> If we find the \"common\" context lines that have only blank and \n> punctuation letters in Dscho output, turn each of them into \"-\" and \"+\", \n> and rearrange them so that all \"-\" are together followed by \"+\", it will \n> match Bzr output.\n\nSo we'd need something like this (I still think we should treat curly \nbrackets the same as punctuation, and for good measure I just handled \neverything that is not alphanumerical the same):\n\n-- snipsnap --\n[TOY PATCH] Add diff option '--collapse-non-alnums'\n\nWith the option --collapse-non-alnums, there will be no interhunks\nconsisting solely of non-alphanumerical letters.\n\nSigned-off-by: Johannes Schindelin \n---\n diff.c | 2 ++\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++-\n 3 files changed, 50 insertions(+), 1 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex c7ddb60..4b387fb 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2503,6 +2503,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\toptions->xdl_opts |= XDF_IGNORE_WHITESPACE_AT_EOL;\n \telse if (!strcmp(arg, \"--patience\"))\n \t\toptions->xdl_opts |= XDF_PATIENCE_DIFF;\n+\telse if (!strcmp(arg, \"--collapse-non-alnums\"))\n+\t\toptions->xdl_opts |= XDF_COLLAPSE_NON_ALNUMS;\n \n \t/* flags options */\n \telse if (!strcmp(arg, \"--binary\")) {\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 4da052a..a444f9a 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -33,6 +33,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n #define XDF_PATIENCE_DIFF (1 << 5)\n+#define XDF_COLLAPSE_NON_ALNUMS (1 << 6)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 3e97462..b8e7ee8 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -396,6 +396,50 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n \treturn xch;\n }\n \n+static int xdl_record_contains_alnum(xrecord_t *record)\n+{\n+\tlong i;\n+\tfor (i = 0; i < record->size; i++)\n+\t\tif (isalnum(record->ptr[i]))\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n+static int xdl_collapse_non_alnum(xdfile_t *xdf, xdfile_t *xdfo)\n+{\n+\tlong ix, ixo, len = 0;\n+\n+\t/*\n+\t * Collapse all interhunk parts consisting solely of non-alnum\n+\t * characters into the hunks.\n+\t */\n+\tfor (ix = 0, ixo = 0; ix < xdf->nrec && ixo < xdfo->nrec; ix++, ixo++) {\n+\t\tif (xdf->rchg[ix] == 1 || xdfo->rchg[ixo] == 1) {\n+\t\t\t/* collapse non-alnum interhunks */\n+\t\t\twhile (len > 0) {\n+\t\t\t\txdf->rchg[ix - len] = 1;\n+\t\t\t\txdfo->rchg[ixo - len] = 1;\n+\t\t\t\tlen--;\n+\t\t\t}\n+\n+\t\t\t/* look for end of hunk */\n+\t\t\twhile (ix < xdf->nrec && xdf->rchg[ix] == 1)\n+\t\t\t\tix++;\n+\t\t\twhile (ixo < xdfo->nrec && xdfo->rchg[ixo] == 1)\n+\t\t\t\tixo++;\n+\t\t\tif (ix >= xdf->nrec)\n+\t\t\t\treturn 0;\n+\t\t\tlen = !xdl_record_contains_alnum(xdf->recs[ix]);\n+\t\t}\n+\t\telse if (len > 0) {\n+\t\t\tif (xdl_record_contains_alnum(xdf->recs[ix]))\n+\t\t\t\tlen = 0;\n+\t\t\telse\n+\t\t\t\tlen++;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n \n int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \tlong ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n@@ -548,7 +592,9 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \n \t\treturn -1;\n \t}\n-\tif (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||\n+\tif (((xpp->flags & XDF_COLLAPSE_NON_ALNUMS) &&\n+\t xdl_collapse_non_alnum(&xe.xdf1, &xe.xdf2)) ||\n+\t xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||\n \t xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||\n \t xdl_build_script(&xe, &xscr) < 0) {\n \n-- \n1.6.1.203.gc8be3\n"},{"id":"99795","messageId":"20090109155907.GA29039@chistera.yi.org","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901091405460.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Adeodato Simó","fromEmail":"dato@net.com.org.es","sentAt":"2009-01-09T15:59:07Z","receivedAt":"2009-01-09T15:59:07Z","isPatch":true,"sender":{"key":"dato@net.com.org.es","avatar":"https://gravatar.com/avatar/952ec7d5d5663eb8baf631b5c37f9c58480a881920dd5f8a2d3a71f969b72b53?d=mp&s=160"},"body":"* Johannes Schindelin [Fri, 09 Jan 2009 14:07:28 +0100]:\n\n> > If we find the \"common\" context lines that have only blank and \n> > punctuation letters in Dscho output, turn each of them into \"-\" and \"+\", \n> > and rearrange them so that all \"-\" are together followed by \"+\", it will \n> > match Bzr output.\n\n> So we'd need something like this (I still think we should treat curly \n> brackets the same as punctuation, and for good measure I just handled \n> everything that is not alphanumerical the same):\n\nNice. With this patch of yours, --patience --collapse-non-alnums\nproduces the same output as bzr for this last test case (the util_sock.c\none). However, also for this last case, without --patience, diff\n--collapse-non-alnums finds *no* common lines at all. Mentioning in case\nyou'd be interested in knowing.\n\nCheers,\n\n-- \nAdeodato Simó dato at net.com.org.es\nDebian Developer adeodato at debian.org\n \n- You look beaten.\n- I just caught Tara laughing with another man.\n- Are you sure they weren't just... kissing or something?\n- No, they were laughing.\n -- Denny Crane and Alan Shore\n"},{"id":"99804","messageId":"alpine.LFD.2.00.0901091001260.6528@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901091405460.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-09T18:09:22Z","receivedAt":"2009-01-09T18:09:22Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 9 Jan 2009, Johannes Schindelin wrote:\n> \n> -- snipsnap --\n> [TOY PATCH] Add diff option '--collapse-non-alnums'\n\nI really don't think it should be about \"alnum\".\n\nThink about languages that use \"begin\" and \"end\" instead of \"{\" \"}\".\n\nI think we'd be better off just looking at the size, but _this_ is a \nreally good area where \"uniqueness\" matters.\n\nDon't combine unique lines, but lines that have the same hash as a \nthousand other lines? Go right ahead.\n\n\t\tLinus\n"},{"id":"99805","messageId":"alpine.LFD.2.00.0901091011350.6528@localhost.localdomain","threadId":"16159","inReplyTo":"alpine.LFD.2.00.0901091001260.6528@localhost.localdomain","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-01-09T18:13:10Z","receivedAt":"2009-01-09T18:13:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 9 Jan 2009, Linus Torvalds wrote:\n>\n> Don't combine unique lines, but lines that have the same hash as a \n> thousand other lines? Go right ahead.\n\nOh, and even then, don't ever combine fragments unless it's a single line, \nand unless you can really stop with just one or two combines. Because we \ndon't want to combine 100 one-liner changes (on every other line) into one \n300-line change.\n\n\t\tLinus\n"},{"id":"99818","messageId":"7vvdsoyzej.fsf@gitster.siamese.dyndns.org","threadId":"16159","inReplyTo":"alpine.DEB.1.00.0901091405460.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-01-09T20:53:24Z","receivedAt":"2009-01-09T20:53:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> On Thu, 8 Jan 2009, Junio C Hamano wrote:\n>\n>> If we find the \"common\" context lines that have only blank and \n>> punctuation letters in Dscho output, turn each of them into \"-\" and \"+\", \n>> and rearrange them so that all \"-\" are together followed by \"+\", it will \n>> match Bzr output.\n>\n> So we'd need something like this (I still think we should treat curly \n> brackets the same as punctuation, and for good measure I just handled \n> everything that is not alphanumerical the same):\n\nI meant by punctuation to include curlies (my wording may have been wrong\nbut from the example with \" }\" line it should have been obvious).\n\nBut I agree with both points Linus raised. The criteria to pick what to\npretend unmatching should be \"small insignificant lines\" (small goes for\nboth size and also number of consecutive \"insignificant\" lines), and the\ncoallescing should be done to join a block of consecutive changed lines of\na significant size (so you do not join two 1 or 2-line \"changed line\"\nblocks by pretending that a 1-line unchanged insignificant line in between\nthem is unmatching).\n"},{"id":"99872","messageId":"alpine.DEB.1.00.0901101232130.30769@pacific.mpi-cbg.de","threadId":"16159","inReplyTo":"7vvdsoyzej.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 0/3] Teach Git about the patience diff algorithm","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-01-10T11:36:46Z","receivedAt":"2009-01-10T11:36:46Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 9 Jan 2009, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > On Thu, 8 Jan 2009, Junio C Hamano wrote:\n> >\n> >> If we find the \"common\" context lines that have only blank and \n> >> punctuation letters in Dscho output, turn each of them into \"-\" and \"+\", \n> >> and rearrange them so that all \"-\" are together followed by \"+\", it will \n> >> match Bzr output.\n> >\n> > So we'd need something like this (I still think we should treat curly \n> > brackets the same as punctuation, and for good measure I just handled \n> > everything that is not alphanumerical the same):\n> \n> I meant by punctuation to include curlies (my wording may have been wrong\n> but from the example with \" }\" line it should have been obvious).\n> \n> But I agree with both points Linus raised. The criteria to pick what to\n> pretend unmatching should be \"small insignificant lines\" (small goes for\n> both size and also number of consecutive \"insignificant\" lines), and the\n> coallescing should be done to join a block of consecutive changed lines of\n> a significant size (so you do not join two 1 or 2-line \"changed line\"\n> blocks by pretending that a 1-line unchanged insignificant line in between\n> them is unmatching).\n\nOf course, the number should be configurable as with the inter-hunk \ncontext.\n\nHowever, I'll not have much time to work on this feature, and it would \ndefinitely need some experimenting to find the best parameters, e.g. \nmaximal number of inter-hunk lines, maybe even an inter-hunk/hunk ratio, \nalnums, or as Linus suggests the length of the line (of which I am still \nnot convinced).\n\nCiao,\nDscho\n"}]}