{"thread":{"id":"705","subject":"git-diff-tree -z HEAD | git-diff-helper -z fails for me","startedAt":"2005-05-23T09:02:06Z","lastAt":"2005-05-24T08:10:48Z","messageCount":10,"participants":["Thomas Glanzmann","Junio C Hamano","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"3804","messageId":"20050523090206.GJ23388@cip.informatik.uni-erlangen.de","threadId":"705","inReplyTo":null,"subject":"git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Thomas Glanzmann","fromEmail":"sithglan@stud.uni-erlangen.de","sentAt":"2005-05-23T09:02:06Z","receivedAt":"2005-05-23T09:02:06Z","isPatch":false,"sender":{"key":"sithglan@stud.uni-erlangen.de","avatar":null},"body":"Hello,\nthis fails:\n\n\t(faui00u) [~/work/git/yagf] git-diff-tree -z HEAD | git-diff-helper -z\n\t03c70739ae572ea9832b97dfcf9ca2594702efe8 (from 30e756ea8569bb429b7073b304acd8a960f77e4b)\n\t:100755 100755 f2e04c3b45b2a5ab5cf53228025158902c9de5be b93fd0310e51eea4d48d42c6ad83399cff8ab56egitgit(faui00u) [~/work/git/yagf]\n\nBut:\n\n\t(faui00u) [~/work/git/yagf] git-diff-tree -z HEAD 30e756ea8569bb429b7073b304acd8a960f77e4b | git-diff-helper -z\n\tdiff --git a/git b/git\n\t--- a/git\n\t+++ b/git\n\t@@ -540,11 +540,11 @@ changes\n\n\t\tif (defined ($options{'L'})) {\n\t\t\tpull('-o', shift);\n\t-               system(\"git-rev-tree HEAD '^REMOTE_HEAD' | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v $git_diff_tree_options\");\n\t+               system(\"git-rev-tree HEAD ^REMOTE_HEAD | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v $git_diff_tree_options\");\n\n\t\t} elsif (defined ($options{'R'})) {\n\t\t\tpull('-o', shift);\n\t-               system(\"git-rev-tree REMOTE_HEAD '^HEAD' | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v $git_diff_tree_options\");\n\t+               system(\"git-rev-tree REMOTE_HEAD ^HEAD | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v $git_diff_tree_options\");\n\n\t\t} else {\n\t\t\tsystem(\"git-rev-list HEAD | git-diff-tree --stdin -v $git_diff_tree_options\");\n\nworks? What I am doing wrong here?\n\n\tThomas\n"},{"id":"3808","messageId":"7vwtpp6goy.fsf@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"20050523090206.GJ23388@cip.informatik.uni-erlangen.de","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-23T16:38:21Z","receivedAt":"2005-05-23T16:38:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"Tg\" == Thomas Glanzmann <sithglan@stud.uni-erlangen.de> writes:\n\nTg> Hello,\nTg> this fails:\n\nTg> \t(faui00u) [~/work/git/yagf] git-diff-tree -z HEAD | git-diff-helper -z\nTg> \t03c70739ae572ea9832b97dfcf9ca2594702efe8 (from 30e756ea8569bb429b7073b304acd8a960f77e4b)\nTg> \t:100755 100755 f2e04c3b45b2a5ab5cf53228025158902c9de5be b93fd0310e51eea4d48d42c6ad83399cff8ab56egitgit(faui00u) [~/work/git/yagf]\n\nTg> What I am doing wrong here?\n\nNothing.  I'm an idiot.\n\nLinus, do you mind if I say with \"-z\" git-diff-tree should not\ndo _any_ header thing?\n\n\n"},{"id":"3809","messageId":"Pine.LNX.4.58.0505231119570.2307@ppc970.osdl.org","threadId":"705","inReplyTo":"7vwtpp6goy.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-23T18:21:59Z","receivedAt":"2005-05-23T18:21:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 23 May 2005, Junio C Hamano wrote:\n> \n> Tg> \t(faui00u) [~/work/git/yagf] git-diff-tree -z HEAD | git-diff-helper -z\n> Tg> \t03c70739ae572ea9832b97dfcf9ca2594702efe8 (from 30e756ea8569bb429b7073b304acd8a960f77e4b)\n> Tg> \t:100755 100755 f2e04c3b45b2a5ab5cf53228025158902c9de5be b93fd0310e51eea4d48d42c6ad83399cff8ab56egitgit(faui00u) [~/work/git/yagf]\n> \n> Tg> What I am doing wrong here?\n> \n> Nothing.  I'm an idiot.\n> \n> Linus, do you mind if I say with \"-z\" git-diff-tree should not\n> do _any_ header thing?\n\nHow about instead making sure that any \"extra\" text be NUL-terminated and\nnever start with ':' after a NUL (which will automatically be true, since\nit's either \"diff-tree \" + ascii for the verbose case, or just the tree\nname).\n\nThat way git-diff-helper automatically does the right thing when it just \npasses lines (where \"lines\" is defined as being NUL-terminated) that it \ndoesn't understand through unmodified.\n\n\t\tLinus\n"},{"id":"3812","messageId":"7vpsvh3hp0.fsf@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"Pine.LNX.4.58.0505231119570.2307@ppc970.osdl.org","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-23T18:44:59Z","receivedAt":"2005-05-23T18:44:59Z","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> How about instead making sure that any \"extra\" text be NUL-terminated and\nLT> never start with ':' after a NUL (which will automatically be true, since\nLT> it's either \"diff-tree \" + ascii for the verbose case, or just the tree\nLT> name).\n\nMakes much more sense although it has certain amount of Yuck\nfactor ;-).\n\n\n"},{"id":"3815","messageId":"7v7jhp3gms.fsf@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"7vpsvh3hp0.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-23T19:07:55Z","receivedAt":"2005-05-23T19:07:55Z","isPatch":false,"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> How about instead making sure that any \"extra\" text be NUL-terminated and\nLT> never start with ':' after a NUL (which will automatically be true, since\nLT> it's either \"diff-tree \" + ascii for the verbose case, or just the tree\nLT> name).\n\nJCH> Makes much more sense although it has certain amount of Yuck\nJCH> factor ;-).\n\n------------\nNUL terminate diff-tree header lines under -z.\n\nThomas Glanzmann noticed that diff-tree -z HEAD piped to\ndiff-helper -z did not work.  Since diff-helper -z expects NUL\nterminated lines, we should generate such.\n\nThe output side of the diff-helper should always be using '\\n'\ntermination; earlier it used the same line_termination used for\nthe input side, which was a mistake.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n*** Against your head, not my head that already has the\n*** rename/copy fix.\n*** Only rightly tested with the exact command line Thomas used.\n\ncd /opt/packrat/playpen/public/in-place/git/git.junio/\njit-diff\n# - linus: Don't care about st_dev in the index file\n# + (working tree)\ndiff --git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -121,7 +121,7 @@ int main(int ac, const char **av) {\n \t\tif (status) {\n \t\tunrecognized:\n \t\t\tdiff_flush(diff_output_style);\n-\t\t\tprintf(\"%s%c\", sb1.buf, line_termination);\n+\t\t\tprintf(\"%s\\n\", sb1.buf);\n \t\t}\n \t}\n \tif (detect_rename)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -277,7 +277,18 @@ static int call_diff_flush(void)\n \tif (nr_paths)\n \t\tdiffcore_pathspec(paths);\n \tif (header) {\n-\t\tprintf(\"%s\", header);\n+\t\tif (diff_output_format == DIFF_FORMAT_MACHINE) {\n+\t\t\tconst char *ep, *cp;\n+\t\t\tfor (cp = header; *cp; cp = ep) {\n+\t\t\t\tep = strchr(cp, '\\n');\n+\t\t\t\tif (ep == 0) ep = cp + strlen(cp);\n+\t\t\t\tprintf(\"%.*s%c\", ep-cp, cp, 0);\n+\t\t\t\tif (*ep) ep++;\n+\t\t\t}\n+\t\t}\n+\t\telse {\n+\t\t\tprintf(\"%s\", header);\n+\t\t}\n \t\theader = NULL;\n \t}\n \tdiff_flush(diff_output_format);\n\n\n"},{"id":"3820","messageId":"Pine.LNX.4.58.0505231644560.2307@ppc970.osdl.org","threadId":"705","inReplyTo":"7vpsvh3hp0.fsf@assigned-by-dhcp.cox.net","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-23T23:47:02Z","receivedAt":"2005-05-23T23:47:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 23 May 2005, Junio C Hamano wrote:\n> \n> LT> How about instead making sure that any \"extra\" text be NUL-terminated and\n> LT> never start with ':' after a NUL (which will automatically be true, since\n> LT> it's either \"diff-tree \" + ascii for the verbose case, or just the tree\n> LT> name).\n> \n> Makes much more sense although it has certain amount of Yuck\n> factor ;-).\n\nActually, your solution is the yucky one.\n\nYou didn't realize that your whole DIFF_FORMAT_MACHINE case really can be \nwritten as just\n\n\tprintf(\"%s%c\", header, 0);\n\nie you print the header as _one_ long line, instead of splitting it up \ninto many. It's still a perfectly valid line, and perfectly unrecognizable \nas such.\n\nNow, maybe diff-helper is unhappy about such long lines, but that should \nbe solvable..\n\n\t\tLinus\n"},{"id":"3822","messageId":"7vll651nth.fsf@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"Pine.LNX.4.58.0505231644560.2307@ppc970.osdl.org","subject":"Re: git-diff-tree -z HEAD | git-diff-helper -z fails for me","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T00:15:38Z","receivedAt":"2005-05-24T00:15:38Z","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> Actually, your solution is the yucky one.\n\nNod.\n\nBy the way, there seems to be a big\nscrewup in the pruning code and currently -C does not work at\nall.  Just to let you know that I am already looking into it.\n\n"},{"id":"3829","messageId":"7vzmulzaqs.fsf_-_@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"7vll651nth.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] Fix diff-pruning logic which was running prune too early.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T01:14:03Z","receivedAt":"2005-05-24T01:14:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"For later stages to reorder patches, pruning logic and rename\ndetection logic should not decide which delete to discard\n(because another entry said it will take over the file as a\nrename) until the very end.  Also fix some tests that were\nassuming the earlier \"last one is rename or keep everything else\nis copy\" semantics of diff-raw format, which no longer is true.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\ndiff-cache.c             |    1 \ndiff-files.c             |    1 \ndiff-tree.c              |    2 \ndiff.c                   |  156 +++++++++++++++++++----------------------------\ndiff.h                   |    2 \ndiffcore-rename.c        |   25 -------\ndiffcore.h               |    2 \nt/t4005-diff-rename-2.sh |    7 --\n8 files changed, 69 insertions(+), 127 deletions(-)\n\ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -229,7 +229,6 @@ int main(int argc, const char **argv)\n \tret = diff_cache(active_cache, active_nr);\n \tif (detect_rename)\n \t\tdiffcore_rename(detect_rename, diff_score_opt);\n-\tdiffcore_prune();\n \tif (pickaxe)\n \t\tdiffcore_pickaxe(pickaxe);\n \tif (2 <= argc)\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -115,7 +115,6 @@ int main(int argc, const char **argv)\n \t}\n \tif (detect_rename)\n \t\tdiffcore_rename(detect_rename, diff_score_opt);\n-\tdiffcore_prune();\n \tif (pickaxe)\n \t\tdiffcore_pickaxe(pickaxe);\n \tif (1 < argc)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -266,10 +266,8 @@ static int call_diff_flush(void)\n {\n \tif (detect_rename)\n \t\tdiffcore_rename(detect_rename, diff_score_opt);\n-\tdiffcore_prune();\n \tif (pickaxe)\n \t\tdiffcore_pickaxe(pickaxe);\n-\n \tif (diff_queue_is_empty()) {\n \t\tdiff_flush(DIFF_FORMAT_NO_OUTPUT, 0);\n \t\treturn 0;\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -12,9 +12,6 @@ static const char *diff_opts = \"-pu\";\n static unsigned char null_sha1[20] = { 0, };\n \n static int reverse_diff;\n-static int generate_patch;\n-static int line_termination = '\\n';\n-static int inter_name_termination = '\\t';\n \n static const char *external_diff(void)\n {\n@@ -502,7 +499,9 @@ struct diff_filepair *diff_queue(struct \n \treturn dp;\n }\n \n-static void diff_flush_raw(struct diff_filepair *p)\n+static void diff_flush_raw(struct diff_filepair *p,\n+\t\t\t   int line_termination,\n+\t\t\t   int inter_name_termination)\n {\n \tint two_paths;\n \tchar status[10];\n@@ -566,10 +565,6 @@ static void diff_flush_patch(struct diff\n \tconst char *name, *other;\n \tchar msg_[PATH_MAX*2+200], *msg;\n \n-\t/* diffcore_prune() keeps \"stay\" entries for diff-raw\n-\t * copy/rename detection, but when we are generating\n-\t * patches we do not need them.\n-\t */\n \tif (diff_unmodified_pair(p))\n \t\treturn;\n \n@@ -585,7 +580,7 @@ static void diff_flush_patch(struct diff\n \t\t\t\"similarity index %d%%\\n\"\n \t\t\t\"copy from %s\\n\"\n \t\t\t\"copy to %s\\n\",\n-\t\t\t(int)(0.5 + p->score * 100/MAX_SCORE),\n+\t\t\t(int)(0.5 + p->score * 100.0/MAX_SCORE),\n \t\t\tp->one->path, p->two->path);\n \t\tmsg = msg_;\n \t\tbreak;\n@@ -594,7 +589,7 @@ static void diff_flush_patch(struct diff\n \t\t\t\"similarity index %d%%\\n\"\n \t\t\t\"rename old %s\\n\"\n \t\t\t\"rename new %s\\n\",\n-\t\t\t(int)(0.5 + p->score * 100/MAX_SCORE),\n+\t\t\t(int)(0.5 + p->score * 100.0/MAX_SCORE),\n \t\t\tp->one->path, p->two->path);\n \t\tmsg = msg_;\n \t\tbreak;\n@@ -630,105 +625,82 @@ int diff_needs_to_stay(struct diff_queue\n \treturn 0;\n }\n \n-static int diff_used_as_source(struct diff_queue_struct *q, int lim,\n-\t\t\t       struct diff_filespec *it)\n+int diff_queue_is_empty(void)\n {\n-\tint i;\n-\tfor (i = 0; i < lim; i++) {\n-\t\tstruct diff_filepair *p = q->queue[i++];\n-\t\tif (!strcmp(p->one->path, it->path))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\treturn q->nr == 0;\n }\n \n-void diffcore_prune(void)\n+static void diff_resolve_rename_copy(void)\n {\n-\t/*\n-\t * Although rename/copy detection wants to have \"no-change\"\n-\t * entries fed into them, the downstream do not need to see\n-\t * them, unless we had rename/copy for the same path earlier.\n-\t * This function removes such entries.\n-\t *\n-\t * The applications that use rename/copy should:\n-\t *\n-\t * (1) feed change and \"no-change\" entries via diff_queue().\n-\t * (2) call diffcore_rename, and any other future diffcore_xxx\n-\t *     that would benefit by still having \"no-change\" entries.\n-\t * (3) call diffcore_prune\n-\t * (4) call other diffcore_xxx that do not need to see\n-\t *     \"no-change\" entries.\n-\t * (5) call diff_flush().\n-\t */\n-\tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct diff_queue_struct outq;\n \tint i;\n-\n-\toutq.queue = NULL;\n-\toutq.nr = outq.alloc = 0;\n-\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n-\t\tif (!diff_unmodified_pair(p) ||\n-\t\t    diff_used_as_source(q, i, p->one))\n-\t\t\tdiff_q(&outq, p);\n-\t\telse\n-\t\t\tfree(p);\n+\t\tp->status = 0;\n+\t\tif (DIFF_PAIR_UNMERGED(p))\n+\t\t\tp->status = 'U';\n+\t\telse if (!DIFF_FILE_VALID((p)->one))\n+\t\t\tp->status = 'N';\n+\t\telse if (!DIFF_FILE_VALID((p)->two)) {\n+\t\t\t/* maybe earlier one said 'R', meaning\n+\t\t\t * it will take it, in which case we do\n+\t\t\t * not need to keep 'D'.\n+\t\t\t */\n+\t\t\tint j;\n+\t\t\tfor (j = 0; j < i; j++) {\n+\t\t\t\tstruct diff_filepair *pp = q->queue[j];\n+\t\t\t\tif (pp->status == 'R' &&\n+\t\t\t\t    !strcmp(pp->one->path, p->one->path))\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (j < i)\n+\t\t\t\tcontinue;\n+\t\t\tp->status = 'D';\n+\t\t}\n+\t\telse if (strcmp(p->one->path, p->two->path)) {\n+\t\t\t/* This is rename or copy.  Which one is it? */\n+\t\t\tif (diff_needs_to_stay(q, i+1, p->one))\n+\t\t\t\tp->status = 'C';\n+\t\t\telse\n+\t\t\t\tp->status = 'R';\n+\t\t}\n+\t\telse if (memcmp(p->one->sha1, p->two->sha1, 20))\n+\t\t\tp->status = 'M';\n+\t\telse {\n+\t\t\t/* we do not need this one */\n+\t\t\tp->status = 0;\n+\t\t}\n \t}\n-\tfree(q->queue);\n-\t*q = outq;\n-\treturn;\n-}\n-\n-int diff_queue_is_empty(void)\n-{\n-\tstruct diff_queue_struct *q = &diff_queued_diff;\n-\treturn q->nr == 0;\n }\n \n void diff_flush(int diff_output_style, int resolve_rename_copy)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n+\tint line_termination = '\\n';\n+\tint inter_name_termination = '\\t';\n \n-\tgenerate_patch = 0;\n-\tswitch (diff_output_style) {\n-\tcase DIFF_FORMAT_HUMAN:\n-\t\tline_termination = '\\n';\n-\t\tinter_name_termination = '\\t';\n-\t\tbreak;\n-\tcase DIFF_FORMAT_MACHINE:\n+\tif (diff_output_style == DIFF_FORMAT_MACHINE)\n \t\tline_termination = inter_name_termination = 0;\n-\t\tbreak;\n-\tcase DIFF_FORMAT_PATCH:\n-\t\tgenerate_patch = 1;\n-\t\tbreak;\n-\t}\n+\tif (resolve_rename_copy)\n+\t\tdiff_resolve_rename_copy();\n+\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n-\t\tif (resolve_rename_copy) {\n-\t\t\tif (DIFF_PAIR_UNMERGED(p))\n-\t\t\t\tp->status = 'U';\n-\t\t\telse if (!DIFF_FILE_VALID((p)->one))\n-\t\t\t\tp->status = 'N';\n-\t\t\telse if (!DIFF_FILE_VALID((p)->two))\n-\t\t\t\tp->status = 'D';\n-\t\t\telse if (strcmp(p->one->path, p->two->path)) {\n-\t\t\t\t/* This is rename or copy.  Which one is it? */\n-\t\t\t\tif (diff_needs_to_stay(q, i+1, p->one))\n-\t\t\t\t\tp->status = 'C';\n-\t\t\t\telse\n-\t\t\t\t\tp->status = 'R';\n-\t\t\t}\n-\t\t\telse\n-\t\t\t\tp->status = 'M';\n-\t\t}\n-\t\tif (generate_patch)\n+\t\tif (p->status == 0)\n+\t\t\tcontinue;\n+\t\tswitch (diff_output_style) {\n+\t\tcase DIFF_FORMAT_PATCH:\n \t\t\tdiff_flush_patch(p);\n-\t\telse\n-\t\t\tdiff_flush_raw(p);\n+\t\t\tbreak;\n+\t\tcase DIFF_FORMAT_HUMAN:\n+\t\tcase DIFF_FORMAT_MACHINE:\n+\t\t\tdiff_flush_raw(p, line_termination,\n+\t\t\t\t       inter_name_termination);\n+\t\t\tbreak;\n+\t\t}\n \t}\n-\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tdiff_free_filespec_data(p->one);\n@@ -755,9 +727,9 @@ void diff_addremove(int addremove, unsig\n \t * with something like '=' or '*' (I haven't decided\n \t * which but should not make any difference).\n \t * Feeding the same new and old to diff_change() \n-\t * also has the same effect.  diffcore_prune() should\n-\t * be used to filter uninteresting ones out before the\n-\t * final output happens.\n+\t * also has the same effect.\n+\t * Before the final output happens, they are pruned after\n+\t * merged into rename/copy pairs as appropriate.\n \t */\n \tif (reverse_diff)\n \t\taddremove = (addremove == '+' ? '-' :\ndiff --git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -39,8 +39,6 @@ extern void diff_setup(int reverse);\n \n extern void diffcore_rename(int rename_copy, int minimum_score);\n \n-extern void diffcore_prune(void);\n-\n extern void diffcore_pickaxe(const char *needle);\n extern void diffcore_pathspec(const char **pathspec);\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -133,10 +133,7 @@ static void record_rename_pair(struct di\n \t * The downstream diffcore transformers are free to reorder\n \t * the entries as long as they keep file pairs that has the\n \t * same p->one->path in earlier rename_rank to appear before\n-\t * later ones.  This ordering is used by the diff_flush()\n-\t * logic to tell renames from copies, and also used by the\n-\t * diffcore_prune() logic to omit unnecessary\n-\t * \"no-modification\" entries.\n+\t * later ones.\n \t *\n \t * To the final output routine, and in the diff-raw format\n \t * output, a rename/copy that is based on a path that has a\n@@ -271,14 +268,8 @@ void diffcore_rename(int detect_rename, \n \n \t/* We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n-\t *\n-\t * With the current callers, we should not have already\n-\t * matched entries at this point, but it is nonetheless\n-\t * checked for sanity.\n \t */\n \tfor (i = 0; i < created.nr; i++) {\n-\t\tif (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)\n-\t\t\tcontinue; /* we have matched exactly already */\n \t\tfor (h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {\n \t\t\tstruct diff_rename_pool *p = srcs[h];\n \t\t\tfor (j = 0; j < p->nr; j++) {\n@@ -386,25 +377,13 @@ void diffcore_rename(int detect_rename, \n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->two)) {\n \t\t\t/* deleted */\n-\t\t\tif (p->one->xfrm_flags & RENAME_SRC_GONE)\n-\t\t\t\t; /* rename/copy deleted it already */\n-\t\t\telse\n-\t\t\t\tdiff_queue(q, p->one, p->two);\n+\t\t\tdiff_queue(q, p->one, p->two);\n \t\t}\n \t\telse if (strcmp(p->one->path, p->two->path)) {\n \t\t\t/* rename or copy */\n \t\t\tstruct diff_filepair *dp =\n \t\t\t\tdiff_queue(q, p->one, p->two);\n \t\t\tdp->score = p->score;\n-\n-\t\t\t/* if we have a later entry that is a rename/copy\n-\t\t\t * that depends on p->one, then we copy here.\n-\t\t\t * otherwise we rename it.\n-\t\t\t */\n-\t\t\tif (!diff_needs_to_stay(&outq, i+1, p->one))\n-\t\t\t\t/* this is the last one, so mark it as gone.\n-\t\t\t\t */\n-\t\t\t\tp->one->xfrm_flags |= RENAME_SRC_GONE;\n \t\t}\n \t\telse\n \t\t\t/* otherwise it is a modified (or \"stay\") entry */\ndiff --git a/diffcore.h b/diffcore.h\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -12,8 +12,6 @@\n #define DEFAULT_MINIMUM_SCORE 5000\n \n #define RENAME_DST_MATCHED 01\n-#define RENAME_SRC_GONE    02\n-#define RENAME_SCORE_SHIFT 8\n \n struct diff_filespec {\n \tunsigned char sha1[20];\ndiff --git a/t/t4005-diff-rename-2.sh b/t/t4005-diff-rename-2.sh\n--- a/t/t4005-diff-rename-2.sh\n+++ b/t/t4005-diff-rename-2.sh\n@@ -147,14 +147,13 @@ test_expect_success \\\n ################################################################\n \n # tree has COPYING and rezrov.  work tree has the same COPYING and\n-# copy-edited COPYING.1, and unchanged rezrov.  We should see\n-# unmodified COPYING in the output, so that downstream diff-helper can\n-# notice.  We should not say anything about rezrov.\n+# copy-edited COPYING.1, and unchanged rezrov.  We should not say\n+# anything about rezrov nor COPYING, since the revised again diff-raw\n+# nows how to say Copy.\n \n git-diff-cache -C $tree >current\n cat >expected <<\\EOF\n :100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0603b3238a076dc6c8022aedc6648fa523a17178 C1234\tCOPYING\tCOPYING.1\n-:100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 6ff87c4664981e4397625791c8ea3bbb5f2279a3 M\tCOPYING\n EOF\n \n test_expect_success \\\n------------------------------------------------\n\n"},{"id":"3845","messageId":"7vk6lpyz5i.fsf_-_@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"7vll651nth.fsf@assigned-by-dhcp.cox.net","subject":"interim report on a big screwup with diff -M and -C.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T05:24:25Z","receivedAt":"2005-05-24T05:24:25Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Regrettably this is just an interim progress report not a full\nsolution, but there is a big screwup between the way rename/copy\ndetector records detection results and the way unmodified pair\npruner removes uninteresting filepairs, which results in double\nfree segfaults.  This makes -M and -C flags practically unusable\nand I am redoing the rename/copy detector right now.  Hopefully\nyou will hear back from me by tomorrow morning.\n\n"},{"id":"3848","messageId":"7vu0ktvybb.fsf@assigned-by-dhcp.cox.net","threadId":"705","inReplyTo":"7vk6lpyz5i.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Redo rename/copy detection logic.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T08:10:48Z","receivedAt":"2005-05-24T08:10:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Earlier implementation had a major screw-up in the memory\nmanagement area.  Rename/copy logic sometimes borrowed a pointer\nto a structure without any provision for downstream to determine\nwhich pointer is shared and which is not.  This resulted in the\nlater clean-up code to sometimes double free such structure,\nresulting in a segfault.  This made -M and -C useless.\n\nAnother problem the earlier implementation had was that it\nreordered the patches, and forced the logic to differentiate\nrenames and copies to depend on that particular order.  This\nproblem was fixed by teaching rename/copy detection logic not to\ndo any reordering, and rename-copy differentiator not to depend\non the order of the patches.  The diffs will leave rename/copy\ndetector in the same destination path order as the patch that\nwas fed into it.  Some test vectors have been reordered to\naccommodate this change.\n\nIt also adds a sanity check logic to the human-readable diff-raw\noutput to detect paths with embedded TAB and LF characters,\nwhich cannot be expressed with that format.  This idea came up\nduring a discussion with Chris Wedgwood.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\ndiff.c                         |  117 ++++++++++--\ndiffcore-rename.c              |  393 +++++++++++++++++++----------------------\ndiffcore.h                     |   16 +\nt/t4003-diff-rename-1.sh       |   16 -\nt/t4004-diff-rename-symlink.sh |   14 -\nt/t4005-diff-rename-2.sh       |   18 -\n6 files changed, 318 insertions(+), 256 deletions(-)\n\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -493,8 +493,6 @@ struct diff_filepair *diff_queue(struct \n \tdp->one = one;\n \tdp->two = two;\n \tdp->score = 0;\n-\tdp->orig_order = queue->nr;\n-\tdp->rename_rank = 0;\n \tdiff_q(queue, dp);\n \treturn dp;\n }\n@@ -505,6 +503,17 @@ static void diff_flush_raw(struct diff_f\n {\n \tint two_paths;\n \tchar status[10];\n+\n+\tif (line_termination) {\n+\t\tconst char *err = \"path %s cannot be expressed without -z\";\n+\t\tif (strchr(p->one->path, line_termination) ||\n+\t\t    strchr(p->one->path, inter_name_termination))\n+\t\t\tdie(err, p->one->path);\n+\t\tif (strchr(p->two->path, line_termination) ||\n+\t\t    strchr(p->two->path, inter_name_termination))\n+\t\t\tdie(err, p->two->path);\n+\t}\n+\n \tswitch (p->status) {\n \tcase 'C': case 'R':\n \t\ttwo_paths = 1;\n@@ -628,41 +637,110 @@ int diff_needs_to_stay(struct diff_queue\n int diff_queue_is_empty(void)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\treturn q->nr == 0;\n+\tint i;\n+\tfor (i = 0; i < q->nr; i++)\n+\t\tif (!diff_unmodified_pair(q->queue[i]))\n+\t\t\treturn 0;\n+\treturn 1;\n }\n \n-static void diff_resolve_rename_copy(void)\n+#if DIFF_DEBUG\n+void diff_debug_filespec(struct diff_filespec *s, int x, const char *one)\n+{\n+\tfprintf(stderr, \"queue[%d] %s (%s) %s %06o %s\\n\",\n+\t\tx, one ? : \"\",\n+\t\ts->path,\n+\t\tDIFF_FILE_VALID(s) ? \"valid\" : \"invalid\",\n+\t\ts->mode,\n+\t\ts->sha1_valid ? sha1_to_hex(s->sha1) : \"\");\n+\tfprintf(stderr, \"queue[%d] %s size %lu flags %d\\n\",\n+\t\tx, one ? : \"\",\n+\t\ts->size, s->xfrm_flags);\n+}\n+\n+void diff_debug_filepair(const struct diff_filepair *p, int i)\n+{\n+\tdiff_debug_filespec(p->one, i, \"one\");\n+\tdiff_debug_filespec(p->two, i, \"two\");\n+\tfprintf(stderr, \"score %d, status %c\\n\",\n+\t\tp->score, p->status ? : '?');\n+}\n+\n+void diff_debug_queue(const char *msg, struct diff_queue_struct *q)\n {\n \tint i;\n-\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\tif (msg)\n+\t\tfprintf(stderr, \"%s\\n\", msg);\n+\tfprintf(stderr, \"q->nr = %d\\n\", q->nr);\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n+\t\tdiff_debug_filepair(p, i);\n+\t}\n+}\n+#endif\n+\n+static void diff_resolve_rename_copy(void)\n+{\n+\tint i, j;\n+\tstruct diff_filepair *p, *pp;\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\n+\t/* This should not depend on the ordering of things. */\n+\n+\tdiff_debug_queue(\"resolve-rename-copy\", q);\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tp = q->queue[i];\n \t\tp->status = 0;\n \t\tif (DIFF_PAIR_UNMERGED(p))\n \t\t\tp->status = 'U';\n \t\telse if (!DIFF_FILE_VALID((p)->one))\n \t\t\tp->status = 'N';\n \t\telse if (!DIFF_FILE_VALID((p)->two)) {\n-\t\t\t/* maybe earlier one said 'R', meaning\n-\t\t\t * it will take it, in which case we do\n-\t\t\t * not need to keep 'D'.\n+\t\t\t/* Deletion record should be omitted if there\n+\t\t\t * is another entry that is a rename or a copy\n+\t\t\t * and it uses this one as the source.  Then we\n+\t\t\t * can say the other one is a rename.\n \t\t\t */\n-\t\t\tint j;\n-\t\t\tfor (j = 0; j < i; j++) {\n-\t\t\t\tstruct diff_filepair *pp = q->queue[j];\n-\t\t\t\tif (pp->status == 'R' &&\n-\t\t\t\t    !strcmp(pp->one->path, p->one->path))\n+\t\t\tfor (j = 0; j < q->nr; j++) {\n+\t\t\t\tpp = q->queue[j];\n+\t\t\t\tif (!strcmp(pp->one->path, p->one->path) &&\n+\t\t\t\t    strcmp(pp->one->path, pp->two->path))\n \t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tif (j < i)\n-\t\t\t\tcontinue;\n+\t\t\tif (j < q->nr)\n+\t\t\t\tcontinue; /* has rename/copy */\n \t\t\tp->status = 'D';\n \t\t}\n \t\telse if (strcmp(p->one->path, p->two->path)) {\n-\t\t\t/* This is rename or copy.  Which one is it? */\n-\t\t\tif (diff_needs_to_stay(q, i+1, p->one))\n-\t\t\t\tp->status = 'C';\n-\t\t\telse\n+\t\t\t/* See if there is somebody else anywhere that\n+\t\t\t * will keep the path (either modified or\n+\t\t\t * unmodified).  If so, we have to be a copy,\n+\t\t\t * not a rename.  In addition, if there is\n+\t\t\t * some other rename or copy that comes later\n+\t\t\t * than us that uses the same source, we\n+\t\t\t * cannot be a rename either.\n+\t\t\t */\n+\t\t\tfor (j = 0; j < q->nr; j++) {\n+\t\t\t\tpp = q->queue[j];\n+\t\t\t\tif (strcmp(pp->one->path, p->one->path))\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (!strcmp(pp->one->path, pp->two->path)) {\n+\t\t\t\t\tif (DIFF_FILE_VALID(pp->two)) {\n+\t\t\t\t\t\t/* non-delete */\n+\t\t\t\t\t\tp->status = 'C';\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\t/* pp is a rename/copy ... */\n+\t\t\t\tif (i < j) {\n+\t\t\t\t\t/* ... and comes later than us */\n+\t\t\t\t\tp->status = 'C';\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (!p->status)\n \t\t\t\tp->status = 'R';\n \t\t}\n \t\telse if (memcmp(p->one->sha1, p->two->sha1, 20))\n@@ -672,6 +750,7 @@ static void diff_resolve_rename_copy(voi\n \t\t\tp->status = 0;\n \t\t}\n \t}\n+\tdiff_debug_queue(\"resolve-rename-copy done\", q);\n }\n \n void diff_flush(int diff_output_style, int resolve_rename_copy)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,29 +6,92 @@\n #include \"diffcore.h\"\n #include \"delta.h\"\n \n-struct diff_rename_pool {\n-\tstruct diff_filespec **s;\n-\tint nr, alloc;\n-};\n-\n-static void diff_rename_pool_clear(struct diff_rename_pool *pool)\n-{\n-\tpool->s = NULL; pool->nr = pool->alloc = 0;\n-}\n+/* Table of rename/copy destinations */\n \n-static void diff_rename_pool_add(struct diff_rename_pool *pool,\n-\t\t\t\t struct diff_filespec *s)\n-{\n-\tif (S_ISDIR(s->mode))\n-\t\treturn;  /* no trees, please */\n-\n-\tif (pool->alloc <= pool->nr) {\n-\t\tpool->alloc = alloc_nr(pool->alloc);\n-\t\tpool->s = xrealloc(pool->s,\n-\t\t\t\t   sizeof(*(pool->s)) * pool->alloc);\n+static struct diff_rename_dst {\n+\tstruct diff_filespec *two;\n+\tstruct diff_filepair *pair;\n+} *rename_dst;\n+static int rename_dst_nr, rename_dst_alloc;\n+\n+static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n+\t\t\t\t\t\t int insert_ok)\n+{\n+\tint first, last;\n+\n+\tfirst = 0;\n+\tlast = rename_dst_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n+\t\tint cmp = strcmp(two->path, dst->two->path);\n+\t\tif (!cmp)\n+\t\t\treturn dst;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n \t}\n-\tpool->s[pool->nr] = s;\n-\tpool->nr++;\n+\t/* not found */\n+\tif (!insert_ok)\n+\t\treturn NULL;\n+\t/* insert to make it at \"first\" */\n+\tif (rename_dst_alloc <= rename_dst_nr) {\n+\t\trename_dst_alloc = alloc_nr(rename_dst_alloc);\n+\t\trename_dst = xrealloc(rename_dst,\n+\t\t\t\t      rename_dst_alloc * sizeof(*rename_dst));\n+\t}\n+\trename_dst_nr++;\n+\tif (first < rename_dst_nr)\n+\t\tmemmove(rename_dst + first + 1, rename_dst + first,\n+\t\t\t(rename_dst_nr - first - 1) * sizeof(*rename_dst));\n+\trename_dst[first].two = two;\n+\trename_dst[first].pair = NULL;\n+\treturn &(rename_dst[first]);\n+}\n+\n+static struct diff_rename_src {\n+\tstruct diff_filespec *one;\n+\tunsigned src_used : 1;\n+} *rename_src;\n+static int rename_src_nr, rename_src_alloc;\n+\n+static struct diff_rename_src *locate_rename_src(struct diff_filespec *one,\n+\t\t\t\t\t\t int insert_ok)\n+{\n+\tint first, last;\n+\n+\tfirst = 0;\n+\tlast = rename_src_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct diff_rename_src *src = &(rename_src[next]);\n+\t\tint cmp = strcmp(one->path, src->one->path);\n+\t\tif (!cmp)\n+\t\t\treturn src;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\t/* not found */\n+\tif (!insert_ok)\n+\t\treturn NULL;\n+\t/* insert to make it at \"first\" */\n+\tif (rename_src_alloc <= rename_src_nr) {\n+\t\trename_src_alloc = alloc_nr(rename_src_alloc);\n+\t\trename_src = xrealloc(rename_src,\n+\t\t\t\t      rename_src_alloc * sizeof(*rename_src));\n+\t}\n+\trename_src_nr++;\n+\tif (first < rename_src_nr)\n+\t\tmemmove(rename_src + first + 1, rename_src + first,\n+\t\t\t(rename_src_nr - first - 1) * sizeof(*rename_src));\n+\trename_src[first].one = one;\n+\trename_src[first].src_used = 0;\n+\treturn &(rename_src[first]);\n }\n \n static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst)\n@@ -46,8 +109,8 @@ static int is_exact_match(struct diff_fi\n }\n \n struct diff_score {\n-\tstruct diff_filespec *src;\n-\tstruct diff_filespec *dst;\n+\tint src; /* index in rename_src */\n+\tint dst; /* index in rename_dst */\n \tint score;\n \tint rank;\n };\n@@ -113,92 +176,28 @@ static int estimate_similarity(struct di\n \treturn score;\n }\n \n-static void record_rename_pair(struct diff_queue_struct *outq,\n-\t\t\t       struct diff_filespec *src,\n-\t\t\t       struct diff_filespec *dst,\n-\t\t\t       int rank,\n-\t\t\t       int score)\n+static void record_rename_pair(struct diff_queue_struct *renq,\n+\t\t\t       int dst_index, int src_index, int score)\n {\n-\t/*\n-\t * These ranks are used to sort the final output, because there\n-\t * are certain dependencies:\n-\t *\n-\t *  1. rename/copy that depends on deleted ones.\n-\t *  2. deletions in the original.\n-\t *  3. rename/copy that depends on the pre-edit image of kept files.\n-\t *  4. additions, modifications and no-modifications in the original.\n-\t *  5. rename/copy that depends on the post-edit image of kept files\n-\t *     (note that we currently do not detect such rename/copy).\n-\t *\n-\t * The downstream diffcore transformers are free to reorder\n-\t * the entries as long as they keep file pairs that has the\n-\t * same p->one->path in earlier rename_rank to appear before\n-\t * later ones.\n-\t *\n-\t * To the final output routine, and in the diff-raw format\n-\t * output, a rename/copy that is based on a path that has a\n-\t * later entry that shares the same p->one->path and is not a\n-\t * deletion is a copy.  Otherwise it is a rename.\n-\t */\n+\tstruct diff_filespec *one, *two, *src, *dst;\n+\tstruct diff_filepair *dp;\n \n-\tstruct diff_filepair *dp = diff_queue(outq, src, dst);\n-\tdp->rename_rank = rank * 2 + 1;\n-\tdp->score = score;\n-\tdst->xfrm_flags |= RENAME_DST_MATCHED;\n-}\n+\tif (rename_dst[dst_index].pair)\n+\t\tdie(\"internal error: dst already matched.\");\n \n-#if 0\n-static void debug_filespec(struct diff_filespec *s, int x, const char *one)\n-{\n-\tfprintf(stderr, \"queue[%d] %s (%s) %s %06o %s\\n\",\n-\t\tx, one,\n-\t\ts->path,\n-\t\tDIFF_FILE_VALID(s) ? \"valid\" : \"invalid\",\n-\t\ts->mode,\n-\t\ts->sha1_valid ? sha1_to_hex(s->sha1) : \"\");\n-\tfprintf(stderr, \"queue[%d] %s size %lu flags %d\\n\",\n-\t\tx, one,\n-\t\ts->size, s->xfrm_flags);\n-}\n+\tsrc = rename_src[src_index].one;\n+\tone = alloc_filespec(src->path);\n+\tfill_filespec(one, src->sha1, src->mode);\n \n-static void debug_filepair(const struct diff_filepair *p, int i)\n-{\n-\tdebug_filespec(p->one, i, \"one\");\n-\tdebug_filespec(p->two, i, \"two\");\n-\tfprintf(stderr, \"pair rank %d, orig order %d, score %d\\n\",\n-\t\tp->rename_rank, p->orig_order, p->score);\n-}\n+\tdst = rename_dst[dst_index].two;\n+\ttwo = alloc_filespec(dst->path);\n+\tfill_filespec(two, dst->sha1, dst->mode);\n \n-static void debug_queue(const char *msg, struct diff_queue_struct *q)\n-{\n-\tint i;\n-\tif (msg)\n-\t\tfprintf(stderr, \"%s\\n\", msg);\n-\tfprintf(stderr, \"q->nr = %d\\n\", q->nr);\n-\tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_filepair *p = q->queue[i];\n-\t\tdebug_filepair(p, i);\n-\t}\n-}\n-#else\n-#define debug_queue(a,b) do { ; /*nothing*/ } while(0)\n-#endif\n+\tdp = diff_queue(renq, one, two);\n+\tdp->score = score;\n \n-/*\n- * We sort the outstanding diff entries according to the rank (see\n- * comment at the beginning of record_rename_pair) and tiebreak with\n- * the order in the original input.\n- */\n-static int rank_compare(const void *a_, const void *b_)\n-{\n-\tconst struct diff_filepair *a = *(const struct diff_filepair **)a_;\n-\tconst struct diff_filepair *b = *(const struct diff_filepair **)b_;\n-\tint a_rank = a->rename_rank;\n-\tint b_rank = b->rename_rank;\n-\n-\tif (a_rank != b_rank)\n-\t\treturn a_rank - b_rank;\n-\treturn a->orig_order - b->orig_order;\n+\trename_src[src_index].src_used = 1;\n+\trename_dst[dst_index].pair = dp;\n }\n \n /*\n@@ -232,24 +231,15 @@ int diff_scoreopt_parse(const char *opt)\n void diffcore_rename(int detect_rename, int minimum_score)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct diff_queue_struct outq;\n-\tstruct diff_rename_pool created, deleted, stay;\n-\tstruct diff_rename_pool *(srcs[2]);\n+\tstruct diff_queue_struct renq, outq;\n \tstruct diff_score *mx;\n-\tint h, i, j;\n-\tint num_create, num_src, dst_cnt, src_cnt;\n+\tint i, j;\n+\tint num_create, num_src, dst_cnt;\n \n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_MINIMUM_SCORE;\n-\toutq.queue = NULL;\n-\toutq.nr = outq.alloc = 0;\n-\n-\tdiff_rename_pool_clear(&created);\n-\tdiff_rename_pool_clear(&deleted);\n-\tdiff_rename_pool_clear(&stay);\n-\n-\tsrcs[0] = &deleted;\n-\tsrcs[1] = &stay;\n+\trenq.queue = NULL;\n+\trenq.nr = renq.alloc = 0;\n \n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -257,76 +247,70 @@ void diffcore_rename(int detect_rename, \n \t\t\tif (!DIFF_FILE_VALID(p->two))\n \t\t\t\tcontinue; /* unmerged */\n \t\t\telse\n-\t\t\t\tdiff_rename_pool_add(&created, p->two);\n+\t\t\t\tlocate_rename_dst(p->two, 1);\n \t\telse if (!DIFF_FILE_VALID(p->two))\n-\t\t\tdiff_rename_pool_add(&deleted, p->one);\n+\t\t\tlocate_rename_src(p->one, 1);\n \t\telse if (1 < detect_rename) /* find copy, too */\n-\t\t\tdiff_rename_pool_add(&stay, p->one);\n+\t\t\tlocate_rename_src(p->one, 1);\n \t}\n-\tif (created.nr == 0)\n+\tif (rename_dst_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n \t/* We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n-\tfor (i = 0; i < created.nr; i++) {\n-\t\tfor (h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {\n-\t\t\tstruct diff_rename_pool *p = srcs[h];\n-\t\t\tfor (j = 0; j < p->nr; j++) {\n-\t\t\t\tif (!is_exact_match(p->s[j], created.s[i]))\n-\t\t\t\t\tcontinue;\n-\t\t\t\trecord_rename_pair(&outq,\n-\t\t\t\t\t\t   p->s[j], created.s[i], h,\n-\t\t\t\t\t\t   MAX_SCORE);\n-\t\t\t\tbreak; /* we are done with this entry */\n-\t\t\t}\n+\tfor (i = 0; i < rename_dst_nr; i++) {\n+\t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tfor (j = 0; j < rename_src_nr; j++) {\n+\t\t\tstruct diff_filespec *one = rename_src[j].one;\n+\t\t\tif (!is_exact_match(one, two))\n+\t\t\t\tcontinue;\n+\t\t\trecord_rename_pair(&renq, i, j, MAX_SCORE);\n+\t\t\tbreak; /* we are done with this entry */\n \t\t}\n \t}\n-\tdebug_queue(\"done detecting exact\", &outq);\n+\tdiff_debug_queue(\"done detecting exact\", &renq);\n \n \t/* Have we run out the created file pool?  If so we can avoid\n \t * doing the delta matrix altogether.\n \t */\n-\tif (outq.nr == created.nr)\n+\tif (renq.nr == rename_dst_nr)\n \t\tgoto flush_rest;\n \n-\tnum_create = (created.nr - outq.nr);\n-\tnum_src = deleted.nr + stay.nr;\n+\tnum_create = (rename_dst_nr - renq.nr);\n+\tnum_src = rename_src_nr;\n \tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n-\tfor (dst_cnt = i = 0; i < created.nr; i++) {\n+\tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tint base = dst_cnt * num_src;\n-\t\tif (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)\n+\t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n-\t\tfor (src_cnt = h = 0; h < sizeof(srcs)/sizeof(srcs[0]); h++) {\n-\t\t\tstruct diff_rename_pool *p = srcs[h];\n-\t\t\tfor (j = 0; j < p->nr; j++, src_cnt++) {\n-\t\t\t\tstruct diff_score *m = &mx[base + src_cnt];\n-\t\t\t\tm->src = p->s[j];\n-\t\t\t\tm->dst = created.s[i];\n-\t\t\t\tm->score = estimate_similarity(m->src, m->dst,\n-\t\t\t\t\t\t\t       minimum_score);\n-\t\t\t\tm->rank = h;\n-\t\t\t}\n+\t\tfor (j = 0; j < rename_src_nr; j++) {\n+\t\t\tstruct diff_filespec *one = rename_src[j].one;\n+\t\t\tstruct diff_score *m = &mx[base+j];\n+\t\t\tm->src = j;\n+\t\t\tm->dst = i;\n+\t\t\tm->score = estimate_similarity(one, two,\n+\t\t\t\t\t\t       minimum_score);\n \t\t}\n \t\tdst_cnt++;\n \t}\n \t/* cost matrix sorted by most to least similar pair */\n \tqsort(mx, num_create * num_src, sizeof(*mx), score_compare);\n \tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tif (mx[i].dst->xfrm_flags & RENAME_DST_MATCHED)\n-\t\t\tcontinue; /* alreayd done, either exact or fuzzy. */\n+\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n+\t\tif (dst->pair)\n+\t\t\tcontinue; /* already done, either exact or fuzzy. */\n \t\tif (mx[i].score < minimum_score)\n \t\t\tbreak; /* there is not any more diffs applicable. */\n-\t\trecord_rename_pair(&outq,\n-\t\t\t\t  mx[i].src, mx[i].dst, mx[i].rank,\n-\t\t\t\t  mx[i].score);\n+\t\trecord_rename_pair(&renq, mx[i].dst, mx[i].src, mx[i].score);\n \t}\n \tfree(mx);\n-\tdebug_queue(\"done detecting fuzzy\", &outq);\n+\tdiff_debug_queue(\"done detecting fuzzy\", &renq);\n \n  flush_rest:\n \t/* At this point, we have found some renames and copies and they\n-\t * are kept in outq.  The original list is still in *q.\n+\t * are kept in renq.  The original list is still in *q.\n \t *\n \t * Scan the original list and move them into the outq; we will sort\n \t * outq and swap it into the queue supplied to pass that to\n@@ -335,68 +319,61 @@ void diffcore_rename(int detect_rename, \n \t * See comments at the top of record_rename_pair for numbers used\n \t * to assign rename_rank.\n \t */\n+\toutq.queue = NULL;\n+\toutq.nr = outq.alloc = 0;\n \tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_filepair *dp, *p = q->queue[i];\n-\t\tif (!DIFF_FILE_VALID(p->one)) {\n-\t\t\t/* creation or unmerged entries */\n-\t\t\tdp = diff_queue(&outq, p->one, p->two);\n-\t\t\tdp->rename_rank = 4;\n-\t\t}\n-\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t/* deletion */\n-\t\t\tdp = diff_queue(&outq, p->one, p->two);\n-\t\t\tdp->rename_rank = 2;\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tstruct diff_rename_src *src = locate_rename_src(p->one, 0);\n+\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two, 0);\n+\t\tstruct diff_filepair *pair_to_free = NULL;\n+\n+\t\tif (dst) {\n+\t\t\t/* creation */\n+\t\t\tif (dst->pair) {\n+\t\t\t\t/* renq has rename/copy already to produce\n+\t\t\t\t * this file, so we do not emit the creation\n+\t\t\t\t * record in the output.\n+\t\t\t\t */\n+\t\t\t\tdiff_q(&outq, dst->pair);\n+\t\t\t\tpair_to_free = p;\n+\t\t\t}\n+\t\t\telse\n+\t\t\t\t/* no matching rename/copy source, so record\n+\t\t\t\t * this as a creation.\n+\t\t\t\t */\n+\t\t\t\tdiff_q(&outq, p);\n \t\t}\n+\t\telse if (!diff_unmodified_pair(p))\n+\t\t\t/* all the other cases need to be recorded as is */\n+\t\t\tdiff_q(&outq, p);\n \t\telse {\n-\t\t\t/* modification, or stay as is */\n-\t\t\tdp = diff_queue(&outq, p->one, p->two);\n-\t\t\tdp->rename_rank = 4;\n-\t\t}\n-\t\tfree(p);\n-\t}\n-\tdebug_queue(\"done copying original\", &outq);\n-\n-\t/* Sort outq */\n-\tqsort(outq.queue, outq.nr, sizeof(outq.queue[0]), rank_compare);\n-\n-\tdebug_queue(\"done sorting\", &outq);\n-\n-\tfree(q->queue);\n-\tq->nr = q->alloc = 0;\n-\tq->queue = NULL;\n-\n-\t/* Copy it out to q, removing duplicates. */\n-\tfor (i = 0; i < outq.nr; i++) {\n-\t\tstruct diff_filepair *p = outq.queue[i];\n-\t\tif (!DIFF_FILE_VALID(p->one)) {\n-\t\t\t/* created or unmerged */\n-\t\t\tif (p->two->xfrm_flags & RENAME_DST_MATCHED)\n-\t\t\t\t; /* rename/copy created it already */\n+\t\t\t/* unmodified pair needs to be recorded only if\n+\t\t\t * it is used as the source of rename/copy\n+\t\t\t */\n+\t\t\tif (src && src->src_used)\n+\t\t\t\tdiff_q(&outq, p);\n \t\t\telse\n-\t\t\t\tdiff_queue(q, p->one, p->two);\n-\t\t}\n-\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t/* deleted */\n-\t\t\tdiff_queue(q, p->one, p->two);\n+\t\t\t\tpair_to_free = p;\n \t\t}\n-\t\telse if (strcmp(p->one->path, p->two->path)) {\n-\t\t\t/* rename or copy */\n-\t\t\tstruct diff_filepair *dp =\n-\t\t\t\tdiff_queue(q, p->one, p->two);\n-\t\t\tdp->score = p->score;\n+\t\tif (pair_to_free) {\n+\t\t\tdiff_free_filespec_data(pair_to_free->one);\n+\t\t\tdiff_free_filespec_data(pair_to_free->two);\n+\t\t\tfree(pair_to_free);\n \t\t}\n-\t\telse\n-\t\t\t/* otherwise it is a modified (or \"stay\") entry */\n-\t\t\tdiff_queue(q, p->one, p->two);\n-\t\tfree(p);\n \t}\n+\tdiff_debug_queue(\"done copying original\", &outq);\n \n-\tfree(outq.queue);\n-\tdebug_queue(\"done collapsing\", q);\n+\tfree(renq.queue);\n+\tfree(q->queue);\n+\t*q = outq;\n+\tdiff_debug_queue(\"done collapsing\", q);\n \n  cleanup:\n-\tfree(created.s);\n-\tfree(deleted.s);\n-\tfree(stay.s);\n+\tfree(rename_dst);\n+\trename_dst = NULL;\n+\trename_dst_nr = rename_dst_alloc = 0;\n+\tfree(rename_src);\n+\trename_src = NULL;\n+\trename_src_nr = rename_src_alloc = 0;\n \treturn;\n }\ndiff --git a/diffcore.h b/diffcore.h\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -40,11 +40,6 @@ struct diff_filepair {\n \tstruct diff_filespec *one;\n \tstruct diff_filespec *two;\n \tint score; /* only valid when one and two are different paths */\n-\tint orig_order; /* the original order of insertion into the queue */\n-\tint rename_rank; /* rename/copy dependency needs to enforce\n-\t\t\t  * certain ordering of patches that later\n-\t\t\t  * diffcore transformations should not break.\n-\t\t\t  */\n \tint status; /* M C R N D U (see Documentation/diff-format.txt) */\n };\n #define DIFF_PAIR_UNMERGED(p) \\\n@@ -67,4 +62,15 @@ extern void diff_q(struct diff_queue_str\n extern int diff_needs_to_stay(struct diff_queue_struct *, int,\n \t\t\t      struct diff_filespec *);\n \n+#define DIFF_DEBUG 0\n+#if DIFF_DEBUG\n+void diff_debug_filespec(struct diff_filespec *, int, const char *);\n+void diff_debug_filepair(const struct diff_filepair *, int);\n+void diff_debug_queue(const char *, struct diff_queue_struct *);\n+#else\n+#define diff_debug_filespec(a,b,c) do {} while(0)\n+#define diff_debug_filepair(a,b) do {} while(0)\n+#define diff_debug_queue(a,b) do {} while(0)\n+#endif\n+\n #endif\ndiff --git a/t/t4003-diff-rename-1.sh b/t/t4003-diff-rename-1.sh\n--- a/t/t4003-diff-rename-1.sh\n+++ b/t/t4003-diff-rename-1.sh\n@@ -78,14 +78,6 @@ test_expect_success \\\n \n GIT_DIFF_OPTS=--unified=0 git-diff-cache -C -p $tree >current\n cat >expected <<\\EOF\n-diff --git a/COPYING b/COPYING.1\n-copy from COPYING\n-copy to COPYING.1\n---- a/COPYING\n-+++ b/COPYING.1\n-@@ -6 +6 @@\n-- HOWEVER, in order to allow a migration to GPLv3 if that seems like\n-+ However, in order to allow a migration to GPLv3 if that seems like\n diff --git a/COPYING b/COPYING\n --- a/COPYING\n +++ b/COPYING\n@@ -98,6 +90,14 @@ diff --git a/COPYING b/COPYING\n @@ -12 +12 @@\n -\tThis file is licensed under the GPL v2, or a later version\n +\tThis file is licensed under the G.P.L v2, or a later version\n+diff --git a/COPYING b/COPYING.1\n+copy from COPYING\n+copy to COPYING.1\n+--- a/COPYING\n++++ b/COPYING.1\n+@@ -6 +6 @@\n+- HOWEVER, in order to allow a migration to GPLv3 if that seems like\n++ However, in order to allow a migration to GPLv3 if that seems like\n EOF\n \n test_expect_success \\\ndiff --git a/t/t4004-diff-rename-symlink.sh b/t/t4004-diff-rename-symlink.sh\n--- a/t/t4004-diff-rename-symlink.sh\n+++ b/t/t4004-diff-rename-symlink.sh\n@@ -35,6 +35,13 @@ test_expect_success \\\n \n GIT_DIFF_OPTS=--unified=0 git-diff-cache -M -p $tree >current\n cat >expected <<\\EOF\n+diff --git a/bozbar b/bozbar\n+new file mode 120000\n+--- /dev/null\n++++ b/bozbar\n+@@ -0,0 +1 @@\n++xzzzy\n+\\ No newline at end of file\n diff --git a/frotz b/nitfol\n similarity index 100%\n copy from frotz\n@@ -50,13 +57,6 @@ deleted file mode 100644\n @@ -1 +0,0 @@\n -xyzzy\n \\ No newline at end of file\n-diff --git a/bozbar b/bozbar\n-new file mode 120000\n---- /dev/null\n-+++ b/bozbar\n-@@ -0,0 +1 @@\n-+xzzzy\n-\\ No newline at end of file\n EOF\n \n test_expect_success \\\ndiff --git a/t/t4005-diff-rename-2.sh b/t/t4005-diff-rename-2.sh\n--- a/t/t4005-diff-rename-2.sh\n+++ b/t/t4005-diff-rename-2.sh\n@@ -101,8 +101,8 @@ test_expect_success \\\n \n git-diff-cache -C $tree >current\n cat >expected <<\\EOF\n-:100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0603b3238a076dc6c8022aedc6648fa523a17178 C1234\tCOPYING\tCOPYING.1\n :100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 06c67961bbaed34a127f76d261f4c0bf73eda471 M\tCOPYING\n+:100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0603b3238a076dc6c8022aedc6648fa523a17178 C1234\tCOPYING\tCOPYING.1\n EOF\n \n test_expect_success \\\n@@ -118,14 +118,6 @@ test_expect_success \\\n mv expected diff-raw\n GIT_DIFF_OPTS=--unified=0 git-diff-helper <diff-raw >current\n cat >expected <<\\EOF\n-diff --git a/COPYING b/COPYING.1\n-copy from COPYING\n-copy to COPYING.1\n---- a/COPYING\n-+++ b/COPYING.1\n-@@ -6 +6 @@\n-- HOWEVER, in order to allow a migration to GPLv3 if that seems like\n-+ However, in order to allow a migration to GPLv3 if that seems like\n diff --git a/COPYING b/COPYING\n --- a/COPYING\n +++ b/COPYING\n@@ -138,6 +130,14 @@ diff --git a/COPYING b/COPYING\n @@ -12 +12 @@\n -\tThis file is licensed under the GPL v2, or a later version\n +\tThis file is licensed under the G.P.L v2, or a later version\n+diff --git a/COPYING b/COPYING.1\n+copy from COPYING\n+copy to COPYING.1\n+--- a/COPYING\n++++ b/COPYING.1\n+@@ -6 +6 @@\n+- HOWEVER, in order to allow a migration to GPLv3 if that seems like\n++ However, in order to allow a migration to GPLv3 if that seems like\n EOF\n \n test_expect_success \\\n------------------------------------------------\n\n"}]}