{"thread":{"id":"646","subject":"[PATCH 0/1] Diff-helper update","startedAt":"2005-05-18T06:28:07Z","lastAt":"2005-05-19T11:11:17Z","messageCount":13,"participants":["Junio C Hamano","Linus Torvalds","Thomas Glanzmann"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"3489","messageId":"7v3bslqc94.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":null,"subject":"[PATCH 0/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-18T06:28:07Z","receivedAt":"2005-05-18T06:28:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is just a cover letter but the next patch implements the\nrename detection I told you about.\n\nThe output from the patched version is attached at the end of\nthis message as a demonstration.\n\nMy plan is to get the documentation and the framework in place\nwith this patch first.  The basic strategy is to hold created\nand deleted files while we parse the incoming diff-tree output,\nand match them up at the end, looking for usefully similar pair.\n\nThe similarity evaluator included in this round of patch detects\nexact renames only, which is not very useful in practice, but\nthat would be improved in the later round.  It will probably be\ndone with the same deltify code Nico is using.\n\n$ git-diff-tree -r \\\n    13ab4462d2aefb252d7c916bd537151856b7c967 \\\n    99665af5c0be0fe4319b39183e84917993153576 | ./git-diff-helper -r\ndiff -git a/Documentation/diff-format.txt b/Documentation/diff-format.txt\n--- a/Documentation/diff-format.txt\n+++ b/Documentation/diff-format.txt\n@@ -45,7 +45,7 @@ with a '-p' option, they do not produce \n instead they produce a patch file.\n ...\ndiff -git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -17,7 +17,7 @@ extern void diff_change(unsigned mode1, \n \n extern void diff_unmerge(const char *path);\n \n-/* These are for diff-tree-helper */\n+/* These are for diff-helper */\n \n struct diff_spec {\n \tunsigned char blob_sha1[20];\ndiff -git a/diff-tree-helper.c b/diff-helper.c\nrename old diff-tree-helper.c\nrename new diff-helper.c\ndiff -git a/Documentation/git-diff-tree-helper.txt b/Documentation/git-diff-helper.txt\nrename old Documentation/git-diff-tree-helper.txt\nrename new Documentation/git-diff-helper.txt\n\n\n"},{"id":"3498","messageId":"Pine.LNX.4.58.0505180821470.18337@ppc970.osdl.org","threadId":"646","inReplyTo":"7v3bslqc94.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-18T15:41:21Z","receivedAt":"2005-05-18T15:41:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 May 2005, Junio C Hamano wrote:\n>\n> This is just a cover letter but the next patch implements the\n> rename detection I told you about.\n\nOk. I now have one more worry: git-diff-tree with \"--stdin\".\n\nI actually find that thing to be surpremely useful, and I use it for not \njust my silly git-whatchanged script, but also to make release notes. I \njust do\n\n\tgit-rev-tree HEAD ^LAST_RELEASE | cut -d' ' -f2 | git-diff-tree -v -s --stdin\n\nand that's wonderful. And sometimes I use \"-p\" instead of \"-s\", because \nI'm not making release notes, but because I'm doing a \"whatchanged\" with \nfull diffs.\n\nIn other words, try something like this on the kernel tree:\n\n\tgit-whatchanged -p include/asm-i386 arch/i386 | less -S\n\nand stare in wonder at just how _useful_ this simple thing is.\n\nMaybe it's just that I've not used all that many different SCM systems,\nand I've certainly not used all the features of the ones I _have_ used, so\nmaybe I never knew, but dammit, I've never seen anybody else do something\nquite that useful (at least doing it fast enough that it _remains_\nuseful).\n\n(Replace \"arch/i386\" with \"drivers/usb\" or \"fs/ext3\" or whatever,\ndepending on just what your area of interest happens to be).\n\nIn other words, I'm very happy with git.\n\nHowever, git-diff-helper doesn't understand these things, and the builtin\ndiff doesn't do the rename thing. Yet it would be very very useful to do.\n\nNow, if you do just a\n\n\tgit-whatchanged include/asm-i386 arch/i386\n\n(or you can even use \"-z\" if you want to), it turns out hat git-diff-tree \nactually does output perfectly usable material. Each \"set of diffs\" is \nclearly separated, and there is no ambiguos material: all lines are \neither:\n - empty or start with a whitespace\n - start with \"diff-tree \", \"Author: \" or \"Date: \"\n - are valid input for diff-helper\n\nSo what I'd suggest is one (or both) of two possibilities:\n - make the internal diff logic also able to do the same rename handling \n   as the external diff-helper. This may or may not be complex, I've not \n   looked at it.\n - change diff-helper subtly: instead of printing \"cannot parse %s\", any\n   nonrecognized line would be a \"ignore this line, but process all\n   pending potential renames\".\n\nThe above would mean that I could either just do\n\n\tgit-whatchanged include/asm-i386 arch/i386 | git-diff-helper\n\nor continue to use\n\n\tgit-whatchanged -p include/asm-i386 arch/i386\n\nand still get the \"nice\" output (and it's a _feature_ that a rename within\nthe arch/i386 then shows up as a rename, but a rename that crosses the\nboundary shows up as a \"create\" or \"delete\" event).\n\nComments? \n\n\t\t\tLinus\n"},{"id":"3504","messageId":"7v64xgpgb0.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505180821470.18337@ppc970.osdl.org","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-18T17:58:11Z","receivedAt":"2005-05-18T17:58:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> However, git-diff-helper doesn't understand these things, and the builtin\nLT> diff doesn't do the rename thing. Yet it would be very very useful to do.\n\nIt is unclear what you meant by \"these things\" in \"doesn't\nunderstand these things\", and what you meant by \"it\" in \"it\nwould be very very useful to do.\"  Could you explain?\n\nAbout the built-in diff not doing the rename , I have a bit\nlonger term (knowing _my_ timescale I'd imagine you would\nunderstand that is not that long ;-) plan to have -p option for\ndiff-* family to use the same rename detection logic that I\nadded to diff-helper in the patch you are commenting on.  It\ninvolves slight change to callers (three diff-* family main\nprograms) to add a call to tell the diff driver \"I've given you\nall the diffs, now go look for renames\") at the end, and the\nrest is changes to what diff.c does internally.\n\nLT> So what I'd suggest is one (or both) of two possibilities:\nLT>  - make the internal diff logic also able to do the same rename handling \nLT>    as the external diff-helper. This may or may not be complex, I've not \nLT>    looked at it.\n\nYes that is part of the plan.  I wanted to do things in these\nsteps:\n\n  - Put rename detect in helper so screwups there would not\n    impact the diff-* family's built-in output, with the initial\n    dumb rename detection.\n\n  - Improve rename detection still keeping the logic and\n    machinery in diff-helper only.  I expect a heuristics\n    similar to the one you posted on the deltification thread\n    would work nicely here as well.\n\n  - Straighten out the GIT_EXTERNAL_DIFF interface so that it\n    can also express renames (the patch I sent currently punts\n    there).  They will get eighth argument (rename destination)\n    only when they are being fed a rename patch.\n    git-apply-patch-script needs to be adjusted for this change.\n\n  - Change diff-helper not to do the rename detection itself,\n    but clean it up so it uses the same diff_addremove(),\n    diff_change(), and diff_unmerge() interface the diff-*\n    family use.  Change the implementation of these three\n    functions so that they do not directly call\n    run_external_diff() but pool changes for later matching when\n    rename detection is in effect.  Add diff_finished() which\n    would flush the rename candidate pools, and call that at the\n    end of program from three diff-* family and diff-helper.\n    The rename detection logic in diff-helper will be moved to\n    this \"inspect the pooled rename candidates, match them up\n    and flush\" part.\n\nThe patch I sent is the first step in the above sequence.\n\nLT>  - change diff-helper subtly: instead of printing \"cannot parse %s\", any\nLT>    nonrecognized line would be a \"ignore this line, but process all\nLT>    pending potential renames\".\n\nOnce the built-in diff driver is straightened out the way I\noutlined above, this change may turn out to be unnecessary, I\nneed to look at the whatchanged output and think a bit more\nabout this later today.\n\n"},{"id":"3505","messageId":"Pine.LNX.4.58.0505181110480.18337@ppc970.osdl.org","threadId":"646","inReplyTo":"7v64xgpgb0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-18T18:14:37Z","receivedAt":"2005-05-18T18:14:37Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 May 2005, Junio C Hamano wrote:\n> >>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n> \n> LT> However, git-diff-helper doesn't understand these things, and the builtin\n> LT> diff doesn't do the rename thing. Yet it would be very very useful to do.\n> \n> It is unclear what you meant by \"these things\" in \"doesn't\n> understand these things\", and what you meant by \"it\" in \"it\n> would be very very useful to do.\"  Could you explain?\n\n\"These things\" being the extra output from \"diff-tree\" that is not a \"diff \nline\".\n\nIf diff-helper just passes the lines it doesn't understand through\nunmodified (_after_ having handled any pending rename logic), it will \nautomatically do the right thing.\n\n> About the built-in diff not doing the rename , I have a bit\n> longer term (knowing _my_ timescale I'd imagine you would\n> understand that is not that long ;-) plan to have -p option for\n> diff-* family to use the same rename detection logic that I\n> added to diff-helper in the patch you are commenting on.\n\nGoodie. I was hoping that was the case, but felt that the diff-helper \nthing should be pretty easy to do.\n\n\t\t\tLinus\n"},{"id":"3508","messageId":"Pine.LNX.4.58.0505181134470.18337@ppc970.osdl.org","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181110480.18337@ppc970.osdl.org","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-18T18:38:46Z","receivedAt":"2005-05-18T18:38:46Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 May 2005, Linus Torvalds wrote:\n> \n> If diff-helper just passes the lines it doesn't understand through\n> unmodified (_after_ having handled any pending rename logic), it will \n> automatically do the right thing.\n\nI took the liberty of doing just that. The only subtle issue was that \nthe strbuf functions would consider an empty line to be EOF, which looked \nwrong and unintentional. Fixing that made the actual diff-helper changes \ntotally trivial, and I can now do\n\n\tgit-rev-list HEAD | git-diff-tree -r -v --stdin | ./git-diff-helper -r | less -S\n\nand it does the right thing for me.\n\n\t\tLinus\n"},{"id":"3511","messageId":"20050518185231.GF4738@cip.informatik.uni-erlangen.de","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181134470.18337@ppc970.osdl.org","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Thomas Glanzmann","fromEmail":"sithglan@stud.uni-erlangen.de","sentAt":"2005-05-18T18:52:31Z","receivedAt":"2005-05-18T18:52:31Z","isPatch":true,"sender":{"key":"sithglan@stud.uni-erlangen.de","avatar":null},"body":"Hello,\n\n> \tgit-rev-list HEAD | git-diff-tree -r -v --stdin | ./git-diff-helper -r | less -S\n\nnice one!\n\n\tThomas\n"},{"id":"3514","messageId":"7vll6cnup4.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181134470.18337@ppc970.osdl.org","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-18T20:30:15Z","receivedAt":"2005-05-18T20:30:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> I took the liberty of doing just that. The only subtle issue was that \nLT> the strbuf functions would consider an empty line to be EOF, which looked \nLT> wrong and unintentional. Fixing that made the actual diff-helper changes \nLT> totally trivial, and I can now do\nLT> \tgit-rev-list HEAD | git-diff-tree -r -v --stdin | ./git-diff-helper -r | less -S\nLT> and it does the right thing for me.\n\nThanks for fixing up strbuf.\n\n@@ -136,8 +268,12 @@ int main(int ac, const char **av) {\n \t\tif (sb.eof)\n \t\t\tbreak;\n \t\tstatus = parse_diff_raw_output(sb.buf, av+1, ac-1, reverse);\n-\t\tif (status)\n-\t\t\tfprintf(stderr, \"cannot parse %s\\n\", sb.buf);\n+\t\tif (status) {\n+\t\t\tflush_renames(av+1, ac-1, reverse);\n+\t\t\tprintf(\"%s%c\", sb.buf, line_termination);\n+\t\t}\n \t}\n+\n+\tflush_renames(av+1, ac-1, reverse);\n \treturn 0;\n }\n\nI suspect doing something like this might be saner instead,\nassuming non raw-diffs come at the end.  \n\n\t\tif (status)\n\t\t\tbreak;\n\t}\n\tflush_renames(av+1, ac-1, reverse);\n\tif (!sb.eof) {\n        \tspit out what we have in sb.eof, sendfile ;-) the\n                rest of the input to the output.\n\t}\n\treturn 0;\n\n"},{"id":"3515","messageId":"Pine.LNX.4.58.0505181338270.18337@ppc970.osdl.org","threadId":"646","inReplyTo":"7vll6cnup4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-18T20:39:21Z","receivedAt":"2005-05-18T20:39:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 May 2005, Junio C Hamano wrote:\n> \n> I suspect doing something like this might be saner instead,\n> assuming non raw-diffs come at the end.  \n\nIt won't ever trigger, since we only exit the loop once we see EOF.\n\nSo the non-diffs at the end will trigger by the exact same \"oh, we didn't \nrecognize it\" logic.\n\n\t\tLinus\n"},{"id":"3525","messageId":"7vacmsnl92.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181338270.18337@ppc970.osdl.org","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-18T23:54:17Z","receivedAt":"2005-05-18T23:54:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> On Wed, 18 May 2005, Junio C Hamano wrote:\n>> \n>> I suspect doing something like this might be saner instead,\n>> assuming non raw-diffs come at the end.  \n\nLT> It won't ever trigger, since we only exit the loop once we see EOF.\n\nI was not talking about correctness, but the readability of the\ncode.  Breaking out from the loop to process raw-diff and\nswitching to straight copy would make our intent more explicit.\n\n"},{"id":"3528","messageId":"7vr7g4m0lz.fsf_-_@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181110480.18337@ppc970.osdl.org","subject":"[preview] diff-helper rename detection.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T02:05:28Z","receivedAt":"2005-05-19T02:05:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\n>> About the built-in diff not doing the rename , I have a bit\n>> longer term (knowing _my_ timescale I'd imagine you would\n>> understand that is not that long ;-) plan to have -p option for\n>> diff-* family to use the same rename detection logic that I\n>> added to diff-helper in the patch you are commenting on.\n\nLT> Goodie. I was hoping that was the case, but felt that the diff-helper \nLT> thing should be pretty easy to do.\n\nThis is not yet a request for inclusion but is a preview\nrequesting for testing and comments, especially from Linus (for\ngeneral usability comments and suggestions for cut-off-points in\nheuristics) and Nico (in case I had blatantly misused the\ndiff-delta interface).\n\nI stole diff-delta part from the delta support patch (but I\ndropped the part that actually touches sha1_file part, hence\nthis does not introduce the deltified object store), and used it\nas an \"extent-of-damage estimator\".  The rename detector logic\nin the previous round was detecting exact renames only (and did\nnot even look at the filesystem so the raw-diff could not come\nfrom diff-files or diff-cache without --cached), but this round\nit actually checks the content.  The interim heuristics is:\n\n  - If exact match in SHA1, or exact match comparing the files,\n    then that is a rename (trivial);\n\n  - If size changed more than 20% that cannot be a rename;\n\n  - If delta produced by the deltification stuff between two is\n    more than 20% of the original, that cannot be a rename;\n\n  - Otherwise pick the deleted-created file pair that has the\n    smallest delta between them.\n\nI've only very lightly tested it but it seems to do the right\nthing.  I fed soemthing like this when I had heavily modified\ndiff-helper.c (diff-helpee.c was taken from the git-ls-files\noutput for diff-helper.c from the cache) and lightly modified\ndiff.c (diffo.c was from the cache), and diffo.c -> diff.c were\nreported as rename, while helpee -> helper was not.\n\n-100644\tblob\tcde27275fad8103084d7ed2d08d246ba4ce6eb9c\tMakefile\n+100644\tblob\tcde27275fad8103084d7ed2d08d246ba4ce6eb9c\tGNUMakefile\n-100644\tblob\t2877ddc4df85179c03cdcc8c7a66831951ec5d97\tdiff-helpee.c\n+100644\tblob\t0000000000000000000000000000000000000000\tdiff-helper.c\n-100644\tblob\t74004e5a3f9fa491b30ab3d5f231826593e4eae4\tdiffo.c\n+100644\tblob\t0000000000000000000000000000000000000000\tdiff.c\n\nNot-signed-off-yet-by: Junio C Hamano <junkio@cox.net>\n---\n# - linus: merge-base: use the new lookup_commit_reference() helper function\n# + 9: diff-helper detects renames with Nico's delta stuff.\ndiff -git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -36,7 +36,7 @@ install: $(PROG) $(SCRIPTS)\n \t$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n-\t tag.o date.o\n+\t tag.o date.o diff-delta.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h\n \ndiff -git a/delta.h b/delta.h\nnew file mode 100644\n--- /dev/null\n+++ b/delta.h\n@@ -0,0 +1,6 @@\n+extern void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t\tvoid *to_buf, unsigned long to_size,\n+\t\t        unsigned long *delta_size);\n+extern void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t\t void *delta_buf, unsigned long delta_size,\n+\t\t\t unsigned long *dst_size);\ndiff -git a/diff-delta.c b/diff-delta.c\nnew file mode 100644\n--- /dev/null\n+++ b/diff-delta.c\n@@ -0,0 +1,330 @@\n+/*\n+ * diff-delta.c: generate a delta between two buffers\n+ *\n+ *  Many parts of this file have been lifted from LibXDiff version 0.10.\n+ *  http://www.xmailserver.org/xdiff-lib.html\n+ *\n+ *  LibXDiff was written by Davide Libenzi <davidel@xmailserver.org>\n+ *  Copyright (C) 2003\tDavide Libenzi\n+ *\n+ *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005.\n+ *\n+ *  This file 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+\n+#include <stdlib.h>\n+#include \"delta.h\"\n+\n+\n+/* block size: min = 16, max = 64k, power of 2 */\n+#define BLK_SIZE 16\n+\n+#define MIN(a, b) ((a) < (b) ? (a) : (b))\n+\n+#define GR_PRIME 0x9e370001\n+#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))\n+\t\n+/* largest prime smaller than 65536 */\n+#define BASE 65521\n+\n+/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */\n+#define NMAX 5552\n+\n+#define DO1(buf, i)  { s1 += buf[i]; s2 += s1; }\n+#define DO2(buf, i)  DO1(buf, i); DO1(buf, i + 1);\n+#define DO4(buf, i)  DO2(buf, i); DO2(buf, i + 2);\n+#define DO8(buf, i)  DO4(buf, i); DO4(buf, i + 4);\n+#define DO16(buf)    DO8(buf, 0); DO8(buf, 8);\n+\n+static unsigned int adler32(unsigned int adler, const unsigned char *buf, int len)\n+{\n+\tint k;\n+\tunsigned int s1 = adler & 0xffff;\n+\tunsigned int s2 = adler >> 16;\n+\n+\twhile (len > 0) {\n+\t\tk = MIN(len, NMAX);\n+\t\tlen -= k;\n+\t\twhile (k >= 16) {\n+\t\t\tDO16(buf);\n+\t\t\tbuf += 16;\n+\t\t\tk -= 16;\n+\t\t}\n+\t\tif (k != 0)\n+\t\t\tdo {\n+\t\t\t\ts1 += *buf++;\n+\t\t\t\ts2 += s1;\n+\t\t\t} while (--k);\n+\t\ts1 %= BASE;\n+\t\ts2 %= BASE;\n+\t}\n+\n+\treturn (s2 << 16) | s1;\n+}\n+\n+static unsigned int hashbits(unsigned int size)\n+{\n+\tunsigned int val = 1, bits = 0;\n+\twhile (val < size && bits < 32) {\n+\t\tval <<= 1;\n+\t       \tbits++;\n+\t}\n+\treturn bits ? bits: 1;\n+}\n+\n+typedef struct s_chanode {\n+\tstruct s_chanode *next;\n+\tint icurr;\n+} chanode_t;\n+\n+typedef struct s_chastore {\n+\tchanode_t *head, *tail;\n+\tint isize, nsize;\n+\tchanode_t *ancur;\n+\tchanode_t *sncur;\n+\tint scurr;\n+} chastore_t;\n+\n+static void cha_init(chastore_t *cha, int isize, int icount)\n+{\n+\tcha->head = cha->tail = NULL;\n+\tcha->isize = isize;\n+\tcha->nsize = icount * isize;\n+\tcha->ancur = cha->sncur = NULL;\n+\tcha->scurr = 0;\n+}\n+\n+static void *cha_alloc(chastore_t *cha)\n+{\n+\tchanode_t *ancur;\n+\tvoid *data;\n+\n+\tancur = cha->ancur;\n+\tif (!ancur || ancur->icurr == cha->nsize) {\n+\t\tancur = malloc(sizeof(chanode_t) + cha->nsize);\n+\t\tif (!ancur)\n+\t\t\treturn NULL;\n+\t\tancur->icurr = 0;\n+\t\tancur->next = NULL;\n+\t\tif (cha->tail)\n+\t\t\tcha->tail->next = ancur;\n+\t\tif (!cha->head)\n+\t\t\tcha->head = ancur;\n+\t\tcha->tail = ancur;\n+\t\tcha->ancur = ancur;\n+\t}\n+\n+\tdata = (void *)ancur + sizeof(chanode_t) + ancur->icurr;\n+\tancur->icurr += cha->isize;\n+\treturn data;\n+}\n+\n+static void cha_free(chastore_t *cha)\n+{\n+\tchanode_t *cur = cha->head;\n+\twhile (cur) {\n+\t\tchanode_t *tmp = cur;\n+\t\tcur = cur->next;\n+\t\tfree(tmp);\n+\t}\n+}\n+\n+typedef struct s_bdrecord {\n+\tstruct s_bdrecord *next;\n+\tunsigned int fp;\n+\tconst unsigned char *ptr;\n+} bdrecord_t;\n+\n+typedef struct s_bdfile {\n+\tconst unsigned char *data, *top;\n+\tchastore_t cha;\n+\tunsigned int fphbits;\n+\tbdrecord_t **fphash;\n+} bdfile_t;\n+\n+static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)\n+{\n+\tunsigned int fphbits;\n+\tint i, hsize;\n+\tconst unsigned char *base, *data, *top;\n+\tbdrecord_t *brec;\n+\tbdrecord_t **fphash;\n+\n+\tfphbits = hashbits(bufsize / BLK_SIZE + 1);\n+\thsize = 1 << fphbits;\n+\tfphash = malloc(hsize * sizeof(bdrecord_t *));\n+\tif (!fphash)\n+\t\treturn -1;\n+\tfor (i = 0; i < hsize; i++)\n+\t\tfphash[i] = NULL;\n+\tcha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);\n+\n+\tbdf->data = data = base = buf;\n+\tbdf->top = top = buf + bufsize;\n+\tdata += (bufsize / BLK_SIZE) * BLK_SIZE;\n+\tif (data == top)\n+\t\tdata -= BLK_SIZE;\n+\n+\tfor ( ; data >= base; data -= BLK_SIZE) {\n+\t\tbrec = cha_alloc(&bdf->cha);\n+\t\tif (!brec) {\n+\t\t\tcha_free(&bdf->cha);\n+\t\t\tfree(fphash);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tbrec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));\n+\t\tbrec->ptr = data;\n+\t\ti = HASH(brec->fp, fphbits);\n+\t\tbrec->next = fphash[i];\n+\t\tfphash[i] = brec;\n+\t}\n+\n+\tbdf->fphbits = fphbits;\n+\tbdf->fphash = fphash;\n+\n+\treturn 0;\n+}\n+\n+static void delta_cleanup(bdfile_t *bdf)\n+{\n+\tfree(bdf->fphash);\n+\tcha_free(&bdf->cha);\n+}\n+\n+#define COPYOP_SIZE(o, s) \\\n+    (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \\\n+     !!(s & 0xff) + !!(s & 0xff00) + 1)\n+\n+void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t void *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size)\n+{\n+\tint i, outpos, outsize, inscnt, csize, msize, moff;\n+\tunsigned int fp;\n+\tconst unsigned char *data, *top, *ptr1, *ptr2;\n+\tunsigned char *out, *orig;\n+\tbdrecord_t *brec;\n+\tbdfile_t bdf;\n+\n+\tif (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 8192;\n+\tout = malloc(outsize);\n+\tif (!out) {\n+\t\tdelta_cleanup(&bdf);\n+\t\treturn NULL;\n+\t}\n+\n+\tdata = to_buf;\n+\ttop = to_buf + to_size;\n+\n+\t/* store reference buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (from_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = from_size;\n+\t\t}\n+\t\ti++;\n+\t\tfrom_size >>= 8;\n+\t} while (from_size);\n+\n+\t/* store target buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (to_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = to_size;\n+\t\t}\n+\t\ti++;\n+\t\tto_size >>= 8;\n+\t} while (to_size);\n+\n+\tinscnt = 0;\n+\tmoff = 0;\n+\twhile (data < top) {\n+\t\tmsize = 0;\n+\t\tfp = adler32(0, data, MIN(top - data, BLK_SIZE));\n+\t\ti = HASH(fp, bdf.fphbits);\n+\t\tfor (brec = bdf.fphash[i]; brec; brec = brec->next) {\n+\t\t\tif (brec->fp == fp) {\n+\t\t\t\tcsize = bdf.top - brec->ptr;\n+\t\t\t\tif (csize > top - data)\n+\t\t\t\t\tcsize = top - data;\n+\t\t\t\tfor (ptr1 = brec->ptr, ptr2 = data; \n+\t\t\t\t     csize && *ptr1 == *ptr2;\n+\t\t\t\t     csize--, ptr1++, ptr2++);\n+\n+\t\t\t\tcsize = ptr1 - brec->ptr;\n+\t\t\t\tif (csize > msize) {\n+\t\t\t\t\tmoff = brec->ptr - bdf.data;\n+\t\t\t\t\tmsize = csize;\n+\t\t\t\t\tif (msize >= 0x10000) {\n+\t\t\t\t\t\tmsize = 0x10000;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!msize || msize < COPYOP_SIZE(moff, msize)) {\n+\t\t\tif (!inscnt)\n+\t\t\t\toutpos++;\n+\t\t\tout[outpos++] = *data++;\n+\t\t\tinscnt++;\n+\t\t\tif (inscnt == 0x7f) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tif (inscnt) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\n+\t\t\tdata += msize;\n+\t\t\torig = out + outpos++;\n+\t\t\ti = 0x80;\n+\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n+\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }\n+\t\t\tmsize >>= 8;\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }\n+\n+\t\t\t*orig = i;\n+\t\t}\n+\n+\t\t/* next time around the largest possible output is 1 + 4 + 3 */\n+\t\tif (outpos > outsize - 8) {\n+\t\t\tvoid *tmp = out;\n+\t\t\toutsize = outsize * 3 / 2;\n+\t\t\tout = realloc(out, outsize);\n+\t\t\tif (!out) {\n+\t\t\t\tfree(tmp);\n+\t\t\t\tdelta_cleanup(&bdf);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (inscnt)\n+\t\tout[outpos - inscnt - 1] = inscnt;\n+\n+\tdelta_cleanup(&bdf);\n+\t*delta_size = outpos;\n+\treturn out;\n+}\ndiff -git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -5,6 +5,7 @@\n #include \"cache.h\"\n #include \"strbuf.h\"\n #include \"diff.h\"\n+#include \"delta.h\"\n \n static int matches_pathspec(const char *name, const char **spec, int cnt)\n {\n@@ -31,8 +32,14 @@ static int detect_rename = 0;\n \n static struct diff_spec_hold {\n \tstruct diff_spec_hold *next;\n-\tstruct diff_spec_hold *matched;\n-\tstruct diff_spec old, new;\n+\tstruct diff_spec old;\n+\tstruct diff_spec new;\n+\tunsigned long size;\n+\tint flags;\n+#define MATCHED 1\n+#define SHOULD_FREE 2\n+#define SHOULD_MUNMAP 4\n+\tvoid *data;\n \tchar path[1];\n } *createdfile, *deletedfile;\n \n@@ -47,101 +54,199 @@ static void hold_spec(const char *path,\n \t*list = elem;\n \telem->old = *old;\n \telem->new = *new;\n-\telem->matched = 0;\n+\telem->size = 0;\n+\telem->data = NULL;\n+\telem->flags = 0;\n+}\n+\n+/* diff_spec sha1_valid flag tells us if mode is to be trusted\n+ * and if blob_sha1 is not null_sha1 then that is also to be\n+ * trusted.  Here we need to know if we need to look at the file\n+ * system.\n+ */\n+static int look_at_fs(struct diff_spec *s)\n+{\n+\tstatic const unsigned char null_sha1[20] = { 0, };\n+\treturn (!s->sha1_valid ||\n+\t\t!memcmp(null_sha1, s->blob_sha1, sizeof(null_sha1)));\n+}\n+\n+static int populate_data(struct diff_spec_hold *s, int use_old)\n+{\n+\tchar type[20];\n+\tstruct diff_spec *u = use_old ? &(s->old) : &(s->new);\n+\n+\tif (!look_at_fs(u)) {\n+\t\ts->data = read_sha1_file(u->blob_sha1, type, &s->size);\n+\t\ts->flags |= SHOULD_FREE;\n+\t}\n+\telse {\n+\t\tstruct stat st;\n+\t\tint fd;\n+\t\tfd = open(s->path, O_RDONLY);\n+\t\tif (fd < 0)\n+\t\t\treturn -1;\n+\t\tif (fstat(fd, &st)) {\n+\t\t\tclose(fd);\n+\t\t\treturn -1;\n+\t\t}\n+\t\ts->size = st.st_size;\n+\t\ts->data = mmap(NULL, s->size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tclose(fd);\n+\t\tif (!s->size)\n+\t\t\ts->data = \"\";\n+\t\telse\n+\t\t\ts->flags |= SHOULD_MUNMAP;\n+\t}\n+\treturn 0;\n+}\n+\n+static void free_data(struct diff_spec_hold *s)\n+{\n+\tif (s->flags & SHOULD_FREE)\n+\t\tfree(s->data);\n+\telse if (s->flags & SHOULD_MUNMAP)\n+\t\tmunmap(s->data, s->size);\n+\ts->flags &= ~(SHOULD_FREE|SHOULD_MUNMAP);\n+}\n+\n+static void flush_rest(struct diff_spec_hold *elem,\n+\t\t       const char **spec, int cnt, int reverse)\n+{\n+\tfor ( ; elem ; elem = elem->next) {\n+\t\tfree_data(elem);\n+\t\tif (elem->flags & MATCHED)\n+\t\t\tcontinue;\n+\t\tif (!cnt ||\n+\t\t    matches_pathspec(elem->path, spec, cnt)) {\n+\t\t\tif (reverse)\n+\t\t\t\trun_external_diff(elem->path, NULL,\n+\t\t\t\t\t\t  &elem->new, &elem->old);\n+\t\t\telse\n+\t\t\t\trun_external_diff(elem->path, NULL,\n+\t\t\t\t\t\t  &elem->old, &elem->new);\n+\t\t}\n+\t}\n }\n \n-#define MINIMUM_SCORE 7000\n-int estimate_similarity(struct diff_spec *one, struct diff_spec *two)\n+#define EXACT_MATCH  10000\n+#define MINIMUM_SCORE 5000\n+int estimate_similarity(struct diff_spec_hold *src,\n+\t\t\tstruct diff_spec_hold *dst,\n+\t\t\tint expect)\n {\n-\t/* Return how similar they are, representing the score as an\n-\t * integer between 0 and 10000.\n+\t/* src points at a deleted file (src->old) and dst points at\n+\t * a created file (dst->new).  They may be quite similar in which\n+\t * case we want to say src->old is renamed to dst->new.\n \t *\n-\t * This version is very dumb and detects exact matches only.\n-\t * Wnen Nico's delta stuff gets in, I'll use the delta\n-\t * algorithm to estimate the similarity score in core.\n+\t * Compare them and return how similar they are, representing\n+\t * the score as an integer between 0 and 10000.  10000 is\n+\t * reserved for the case where they match exactly.\n \t */\n+\tvoid *delta;\n+\tunsigned long delta_size;\n \n-\tif (one->sha1_valid && two->sha1_valid &&\n-\t    !memcmp(one->blob_sha1, two->blob_sha1, 20))\n+\tif (!look_at_fs(&(src->old)) && !look_at_fs(&(dst->new)) &&\n+\t    !memcmp(src->old.blob_sha1, dst->new.blob_sha1, 20))\n \t\treturn 10000;\n-\treturn 0;\n+\tif (populate_data(src, 1) || populate_data(dst, 0))\n+\t\t/* this is an error but will be caught downstream */\n+\t\treturn 0;\n+\tif (src->size == dst->size &&\n+\t    !memcmp(src->data, dst->data, src->size))\n+\t\treturn 10000;\n+\n+\tif (expect == EXACT_MATCH)\n+\t\treturn 0;\n+\n+\tdelta_size = ((src->size < dst->size) ?\n+\t\t      (dst->size - src->size) : (src->size - dst->size));\n+\n+\t/* We would not consider rename followed by more than\n+\t * 20% edits; that is, delta_size must be smaller than\n+\t * (src->size + dst->size)/2 * 0.2, which means...\n+\t */\n+\tif ((src->size + dst->size) < delta_size * 10)\n+\t\treturn 0;\n+\n+\tdelta = diff_delta(src->data, src->size,\n+\t\t\t   dst->data, dst->size,\n+\t\t\t   &delta_size);\n+\tfree(delta);\n+\n+\t/* This \"delta\" is really xdiff with adler32 and all the\n+\t * overheads but it is a quick and dirty approximation.\n+\t * Again, we say there should be less than 20% edit.\n+\t */\n+\tif ((src->size + dst->size) < delta_size * 10)\n+\t\treturn 0;\n+\n+\t/* Now we will give some score to it.  Let's say 20% edit gets\n+\t * 5000 points and 0% edit gets 9000 points.  That is, every\n+\t * 1/20000 edit gets 1 point penalty.  The amount of penalty is:\n+\t *\n+\t * (delta_size * 2 / (src->size + dst->size)) * 20000\n+\t *\n+\t */\n+\treturn 9000 - (40000 * delta_size / (src->size+dst->size));\n }\n \n-static void flush_renames(const char **spec, int cnt, int reverse)\n+static void flush_rename_pairs(int floor_score,\n+\t\t\t       const char **spec, int cnt, int reverse)\n {\n-\tstruct diff_spec_hold *rename_src, *rename_dst, *elem;\n-\tstruct diff_spec_hold *leftover = NULL;\n+\tstruct diff_spec_hold *src, *dst, *elem;\n \tint score, best_score;\n \n-\twhile (createdfile) {\n-\t\trename_dst = createdfile;\n-\t\tcreatedfile = rename_dst->next;\n-\t\tbest_score = MINIMUM_SCORE;\n-\t\trename_src = NULL;\n-\t\tfor (elem = deletedfile;\n-\t\t     elem;\n-\t\t     elem = elem->next) {\n-\t\t\tif (elem->matched)\n+\tfor (dst = createdfile; dst; dst = dst->next) {\n+\t\tif (dst->flags & MATCHED)\n+\t\t\tcontinue;\n+\n+\t\tbest_score = floor_score;\n+\t\tsrc = NULL;\n+\t\tfor (elem = deletedfile; elem; elem = elem->next) {\n+\t\t\tif (elem->flags & MATCHED)\n \t\t\t\tcontinue;\n-\t\t\tscore = estimate_similarity(&elem->old,\n-\t\t\t\t\t\t    &rename_dst->new);\n-\t\t\tif (best_score < score) {\n-\t\t\t\trename_src = elem;\n+\t\t\tscore = estimate_similarity(elem, dst, best_score);\n+\t\t\tif (best_score <= score) {\n+\t\t\t\tsrc = elem;\n \t\t\t\tbest_score = score;\n \t\t\t}\n \t\t}\n-\t\tif (rename_src) {\n-\t\t\trename_src->matched = rename_dst;\n-\t\t\trename_dst->matched = rename_src;\n+\t\tif (src) {\n+\t\t\tsrc->flags |= MATCHED;\n+\t\t\tdst->flags |= MATCHED;\n+\t\t\tfree_data(src);\n+\t\t\tfree_data(dst);\n \n \t\t\tif (!cnt ||\n-\t\t\t    matches_pathspec(rename_src->path, spec, cnt) ||\n-\t\t\t    matches_pathspec(rename_dst->path, spec, cnt)) {\n+\t\t\t    matches_pathspec(src->path, spec, cnt) ||\n+\t\t\t    matches_pathspec(dst->path, spec, cnt)) {\n \t\t\t\tif (reverse)\n-\t\t\t\t\trun_external_diff(rename_dst->path,\n-\t\t\t\t\t\t\t  rename_src->path,\n-\t\t\t\t\t\t\t  &rename_dst->new,\n-\t\t\t\t\t\t\t  &rename_src->old);\n+\t\t\t\t\trun_external_diff(dst->path,\n+\t\t\t\t\t\t\t  src->path,\n+\t\t\t\t\t\t\t  &dst->new,\n+\t\t\t\t\t\t\t  &src->old);\n \t\t\t\telse\n-\t\t\t\t\trun_external_diff(rename_src->path,\n-\t\t\t\t\t\t\t  rename_dst->path,\n-\t\t\t\t\t\t\t  &rename_src->old,\n-\t\t\t\t\t\t\t  &rename_dst->new);\n+\t\t\t\t\trun_external_diff(src->path,\n+\t\t\t\t\t\t\t  dst->path,\n+\t\t\t\t\t\t\t  &src->old,\n+\t\t\t\t\t\t\t  &dst->new);\n \t\t\t}\n \t\t}\n-\t\telse {\n-\t\t\trename_dst->next = leftover;\n-\t\t\tleftover = rename_dst;\n-\t\t}\n \t}\n+}\n \n-\t/* unmatched deletes */\n-\tfor (elem = deletedfile; elem; elem = elem->next) {\n-\t\tif (elem->matched)\n-\t\t\tcontinue;\n-\t\tif (!cnt ||\n-\t\t    matches_pathspec(elem->path, spec, cnt)) {\n-\t\t\tif (reverse)\n-\t\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t\t  &elem->new, &elem->old);\n-\t\t\telse\n-\t\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t\t  &elem->old, &elem->new);\n-\t\t}\n-\t}\n+static void flush_renames(const char **spec, int cnt, int reverse)\n+{\n+\t/* We do this in two steps; first we pick up the exact matches\n+\t * only and then closest match\n+\t */\n \n-\t/* unmatched creates */\n-\tfor (elem = leftover; elem; elem = elem->next) {\n-\t\tif (!cnt ||\n-\t\t    matches_pathspec(elem->path, spec, cnt)) {\n-\t\t\tif (reverse)\n-\t\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t\t  &elem->new, &elem->old);\n-\t\t\telse\n-\t\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t\t  &elem->old, &elem->new);\n-\t\t}\n-\t}\n+\tflush_rename_pairs(EXACT_MATCH, spec, cnt, reverse);\n+\tflush_rename_pairs(MINIMUM_SCORE, spec, cnt, reverse);\n+\n+\tflush_rest(createdfile, spec, cnt, reverse);\n+\tflush_rest(deletedfile, spec, cnt, reverse);\n }\n \n static int parse_oneside_change(const char *cp, struct diff_spec *one,\ndiff -git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -329,7 +329,7 @@ void run_external_diff(const char *name,\n \t\tdie(\"unable to fork\");\n \tif (!pid) {\n \t\tconst char *pgm = external_diff();\n-\t\t/* not passing rename patch to external ones */\n+\t\t/* NEEDSWORK: not passing rename patch to external ones */\n \t\tif (!other && pgm) {\n \t\t\tif (one && two)\n \t\t\t\texeclp(pgm, pgm,\n\n"},{"id":"3529","messageId":"Pine.LNX.4.58.0505181952260.2322@ppc970.osdl.org","threadId":"646","inReplyTo":"7vr7g4m0lz.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [preview] diff-helper rename detection.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T03:01:03Z","receivedAt":"2005-05-19T03:01:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 18 May 2005, Junio C Hamano wrote:\n> \n> This is not yet a request for inclusion but is a preview\n> requesting for testing and comments, especially from Linus (for\n> general usability comments and suggestions for cut-off-points in\n> heuristics) and Nico (in case I had blatantly misused the\n> diff-delta interface).\n\nI think this is great, although I also bet that we'll tweak the heuristics\nlater.\n\nI suspect that one tweak may be to try to find the \"best\" rename first,\nrather than look at files in the order they were discovered (ie you'd\ncreate a _matrix_ of the delta scores, rather than walk through the newly\ncreated files in order). That would then potentially allow for a more\nrelaxed definitions of \"rename\", without any possibility of losing sight\nof a better rename due to finding a bad one first.\n\nBut I think the simple heurstic is probably fine as a first cut.\n\nSo my only nit so far is that you declare \"patch_delta()\", even though you\ndon't actually have it. Just remove it.\n\n\t\tLinus\n"},{"id":"3530","messageId":"7vk6lvnc94.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"Pine.LNX.4.58.0505181952260.2322@ppc970.osdl.org","subject":"Re: [preview] diff-helper rename detection.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T03:08:39Z","receivedAt":"2005-05-19T03:08:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> I suspect that one tweak may be to try to find the \"best\" rename first,\nLT> rather than look at files in the order they were discovered (ie you'd\nLT> create a _matrix_ of the delta scores, rather than walk through the newly\nLT> created files in order). That would then potentially allow for a more\nLT> relaxed definitions of \"rename\", without any possibility of losing sight\nLT> of a better rename due to finding a bad one first.\n\nI thought about that but I opted for simplicity of first picking\nthe exact matches.  I was unsure about the usefulness of relaxed\nmatching to begin with.  But I now realize that to see how useful\nthat would be we need to experiment it and a matrix approach\nwould become necessity for that.\n\nLT> So my only nit so far is that you declare \"patch_delta()\",\nLT> even though you don't actually have it. Just remove it.\n\nI'd rather keep that file as is for later merge with Nico.  It\ncame from the delitification patch and I tried to keep the new\nfiles as they are.\n\n"},{"id":"3542","messageId":"7vis1f1ne2.fsf@assigned-by-dhcp.cox.net","threadId":"646","inReplyTo":"7vacmsnl92.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T11:11:17Z","receivedAt":"2005-05-19T11:11:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JCH\" == Junio C Hamano <junkio@cox.net> writes:\n\n>>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\nLT> On Wed, 18 May 2005, Junio C Hamano wrote:\n>>> \n>>> I suspect doing something like this might be saner instead,\n>>> assuming non raw-diffs come at the end.  \n\nLT> It won't ever trigger, since we only exit the loop once we see EOF.\n\nJCH> I was not talking about correctness, but the readability of the\nJCH> code.  Breaking out from the loop to process raw-diff and\nJCH> switching to straight copy would make our intent more explicit.\n\nI was completely mistaken about what you were talking about.\nYour output (helper's input) is (<non-diff material>* <raw-diff\nmaterial>*)*, so of course we should not break out of the main\nloop.\n\n"}]}