{"thread":{"id":"660","subject":"[PATCH] Detect renames in diff family.","startedAt":"2005-05-19T10:32:35Z","lastAt":"2005-05-26T03:17:22Z","messageCount":43,"participants":["Junio C Hamano","Linus Torvalds","Joel Becker","Nicolas Pitre","H. Peter Anvin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"3541","messageId":"7vu0kz1p6k.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":null,"subject":"[PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T10:32:35Z","receivedAt":"2005-05-19T10:32:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This patch rips out the rename detection engine from diff-helper\nand moves it to the diff core, and updates the internal calling\nconvention used by diff-tree family into the diff core. In\norder to give the same option name to diff-tree family as well\nas to diff-helper, I've changed the earlier diff-helper '-r'\noption to '-M' (stands for Move; sorry but the natural\nabbreviation 'r' for 'rename' is already taken for 'recursive').\n\nAlthough I did a fair amount of test with the git-diff-tree with\nexisting rename commits in the core GIT repository, this should\nstill be considered beta (preview) release. This patch depends\non the diff-delta patch I stole from Nico. Please give it a\ngood beating.\n\nSpecial request for Linus is to check if I did not screw up the\nvarious calls into the diff core from diff-tree. Essentially\nthe idea is to start one patchset session with diff_setup() and\nclose it with diff_flush() before you start another patchset\nsession.\n\nThis implements almost everything I wanted to see in this series\nof patch, except a few minor cleanups in the calling convention\ninto diff core, but that will be a separate cleanup patch.\n\nSigned-off-by: Junio C Hamano \n---\n\nDocumentation/git-diff-cache.txt | 5 \nDocumentation/git-diff-files.txt | 5 \nDocumentation/git-diff-helper.txt | 4 \nDocumentation/git-diff-tree.txt | 5 \ndiff-cache.c | 16 +\ndiff-files.c | 11 -\ndiff-helper.c | 209 ++-----------------\ndiff-tree.c | 25 +-\ndiff.c | 410 +++++++++++++++++++++++++++++++++++---\ndiff.h | 19 -\ngit-apply-patch-script | 3 \nt/t4001-diff-rename.sh | 60 +++++\n12 files changed, 533 insertions(+), 239 deletions(-)\nt/t4001-diff-rename.sh (. --> 100644)\n\ndiff --git a/Documentation/git-diff-cache.txt b/Documentation/git-diff-cache.txt\n--- a/Documentation/git-diff-cache.txt\n+++ b/Documentation/git-diff-cache.txt\n@@ -9,7 +9,7 @@\n \n SYNOPSIS\n --------\n-'git-diff-cache' [-p] [-r] [-z] [-m] [--cached] \n+'git-diff-cache' [-p] [-r] [-z] [-m] [-M] [--cached] \n \n DESCRIPTION\n -----------\n@@ -33,6 +33,9 @@\n -z::\n \t\\0 line termination on output\n \n+-M::\n+\tDetect renames; implies -p.\n+\n --cached::\n \tdo not consider the on-disk file at all\n \ndiff --git a/Documentation/git-diff-files.txt b/Documentation/git-diff-files.txt\n--- a/Documentation/git-diff-files.txt\n+++ b/Documentation/git-diff-files.txt\n@@ -9,7 +9,7 @@\n \n SYNOPSIS\n --------\n-'git-diff-files' [-p] [-q] [-r] [-z] [...]\n+'git-diff-files' [-p] [-q] [-r] [-z] [-M] [...]\n \n DESCRIPTION\n -----------\n@@ -26,6 +26,9 @@\n -q::\n \tRemain silent even on nonexisting files\n \n+-M::\n+\tDetect renames; implies -p.\n+\n -r::\n \tThis flag does not mean anything. It is there only to match\n \tgit-diff-tree. Unlike git-diff-tree, git-diff-files always looks\ndiff --git a/Documentation/git-diff-helper.txt b/Documentation/git-diff-helper.txt\n--- a/Documentation/git-diff-helper.txt\n+++ b/Documentation/git-diff-helper.txt\n@@ -9,7 +9,7 @@\n \n SYNOPSIS\n --------\n-'git-diff-helper' [-z] [-R] [-r]\n+'git-diff-helper' [-z] [-R] [-M]\n \n DESCRIPTION\n -----------\n@@ -31,7 +31,7 @@\n \twould show a diff to bring the working file back to what\n \tis in the .\n \n--r::\n+-M::\n \tDetect renames.\n \n \ndiff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt\n--- a/Documentation/git-diff-tree.txt\n+++ b/Documentation/git-diff-tree.txt\n@@ -9,7 +9,7 @@\n \n SYNOPSIS\n --------\n-'git-diff-tree' [-p] [-r] [-z] [--stdin] [-m] [-s] [-v] []\\*\n+'git-diff-tree' [-p] [-r] [-z] [--stdin] [-M] [-m] [-s] [-v] []\\*\n \n DESCRIPTION\n -----------\n@@ -33,6 +33,9 @@\n \tgenerate patch (see section on generating patches). For\n \tgit-diff-tree, this flag implies '-r' as well.\n \n+-M::\n+\tDetect renames; implies -p, in turn implying also '-r'.\n+\n -r::\n \trecurse\n \ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -5,6 +5,7 @@\n static int generate_patch = 0;\n static int match_nonexisting = 0;\n static int line_termination = '\\n';\n+static int detect_rename = 0;\n \n /* A file entry went away or appeared */\n static void show_file(const char *prefix, struct cache_entry *ce, unsigned char *sha1, unsigned int mode)\n@@ -165,13 +166,14 @@\n }\n \n static char *diff_cache_usage =\n-\"git-diff-cache [-p] [-r] [-z] [-m] [--cached] \";\n+\"git-diff-cache [-p] [-r] [-z] [-m] [-M] [--cached] \";\n \n int main(int argc, char **argv)\n {\n \tunsigned char tree_sha1[20];\n \tvoid *tree;\n \tunsigned long size;\n+\tint ret;\n \n \tread_cache();\n \twhile (argc > 2) {\n@@ -186,6 +188,10 @@\n \t\t\tgenerate_patch = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"-M\")) {\n+\t\t\tgenerate_patch = detect_rename = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = '\\0';\n \t\t\tcontinue;\n@@ -204,6 +210,9 @@\n \tif (argc != 2 || get_sha1(argv[1], tree_sha1))\n \t\tusage(diff_cache_usage);\n \n+\tif (generate_patch)\n+\t\tdiff_setup(detect_rename, 0, 0, 0, 0);\n+\n \tmark_merge_entries();\n \n \ttree = read_object_with_reference(tree_sha1, \"tree\", &size, 0);\n@@ -212,5 +221,8 @@\n \tif (read_tree(tree, size, 1))\n \t\tdie(\"unable to read tree object %s\", argv[1]);\n \n-\treturn diff_cache(active_cache, active_nr);\n+\tret = diff_cache(active_cache, active_nr);\n+\tif (generate_patch)\n+\t\tdiff_flush();\n+\treturn ret;\n }\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -7,10 +7,11 @@\n #include \"diff.h\"\n \n static const char *diff_files_usage =\n-\"diff-files [-p] [-q] [-r] [-z] [paths...]\";\n+\"diff-files [-p] [-q] [-r] [-z] [-M] [paths...]\";\n \n static int generate_patch = 0;\n static int line_termination = '\\n';\n+static int detect_rename = 0;\n static int silent = 0;\n \n static int matches_pathspec(struct cache_entry *ce, char **spec, int cnt)\n@@ -79,6 +80,9 @@\n \t\t\t; /* no-op */\n \t\telse if (!strcmp(argv[1], \"-z\"))\n \t\t\tline_termination = 0;\n+\t\telse if (!strcmp(argv[1], \"-M\")) {\n+\t\t\tdetect_rename = generate_patch = 1;\n+\t\t}\n \t\telse\n \t\t\tusage(diff_files_usage);\n \t\targv++; argc--;\n@@ -92,6 +96,9 @@\n \t\texit(1);\n \t}\n \n+\tif (generate_patch)\n+\t\tdiff_setup(detect_rename, 0, 0, 0, 0);\t\t\n+\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct stat st;\n \t\tunsigned int oldmode, mode;\n@@ -132,5 +139,7 @@\n \t\tshow_modified(oldmode, mode, ce->sha1, null_sha1,\n \t\t\t ce->name);\n \t}\n+\tif (generate_patch)\n+\t\tdiff_flush();\n \treturn 0;\n }\ndiff --git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -6,160 +6,23 @@\n #include \"strbuf.h\"\n #include \"diff.h\"\n \n-static int matches_pathspec(const char *name, const char **spec, int cnt)\n-{\n-\tint i;\n-\tint namelen = strlen(name);\n-\tfor (i = 0; i < cnt; i++) {\n-\t\tint speclen = strlen(spec[i]);\n-\t\tif (! strncmp(spec[i], name, speclen) &&\n-\t\t speclen <= namelen &&\n-\t\t (name[speclen] == 0 ||\n-\t\t name[speclen] == '/'))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n static int detect_rename = 0;\n \n-/*\n- * We do not detect circular renames. Just hold created and deleted\n- * entries and later attempt to match them up. If they do not match,\n- * then spit them out as deletes or creates as original.\n- */\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-\tchar path[1];\n-} *createdfile, *deletedfile;\n-\n-static void hold_spec(const char *path,\n-\t\t struct diff_spec *old, struct diff_spec *new)\n-{\n-\tstruct diff_spec_hold **list, *elem;\n-\tlist = (! old->file_valid) ? &createdfile : &deletedfile;\n-\telem = xmalloc(sizeof(*elem) + strlen(path));\n-\tstrcpy(elem->path, path);\n-\telem->next = *list;\n-\t*list = elem;\n-\telem->old = *old;\n-\telem->new = *new;\n-\telem->matched = 0;\n-}\n-\n-#define MINIMUM_SCORE 7000\n-int estimate_similarity(struct diff_spec *one, struct diff_spec *two)\n-{\n-\t/* Return how similar they are, representing the score as an\n-\t * integer between 0 and 10000.\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 */\n-\n-\tif (one->sha1_valid && two->sha1_valid &&\n-\t !memcmp(one->blob_sha1, two->blob_sha1, 20))\n-\t\treturn 10000;\n-\treturn 0;\n-}\n-\n-static void flush_renames(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-\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-\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\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-\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\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\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}\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-\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-\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-}\n-\n-static int parse_oneside_change(const char *cp, struct diff_spec *one,\n-\t\t\t\tchar *path)\n+static int parse_oneside_change(const char *cp, int *mode,\n+\t\t\t\tunsigned char *sha1, char *path)\n {\n-\tint ch;\n+\tint ch, m;\n \n-\tone->file_valid = one->sha1_valid = 1;\n-\tone->mode = 0;\n+\tm = 0;\n \twhile ((ch = *cp) && '0' <= ch && ch <= '7') {\n-\t\tone->mode = (one->mode << 3) | (ch - '0');\n+\t\tm = (m << 3) | (ch - '0');\n \t\tcp++;\n \t}\n-\n+\t*mode = m;\n \tif (strncmp(cp, \"\\tblob\\t\", 6))\n \t\treturn -1;\n \tcp += 6;\n-\tif (get_sha1_hex(cp, one->blob_sha1))\n+\tif (get_sha1_hex(cp, sha1))\n \t\treturn -1;\n \tcp += 40;\n \tif (*cp++ != '\\t')\n@@ -168,79 +31,63 @@\n \treturn 0;\n }\n \n-static int parse_diff_raw_output(const char *buf,\n-\t\t\t\t const char **spec, int cnt, int reverse)\n+static int parse_diff_raw_output(const char *buf)\n {\n-\tstruct diff_spec old, new;\n \tchar path[PATH_MAX];\n+\tunsigned char old_sha1[20], new_sha1[20];\n \tconst char *cp = buf;\n-\tint ch;\n+\tint ch, old_mode, new_mode;\n \n \tswitch (*cp++) {\n \tcase 'U':\n-\t\tif (!cnt || matches_pathspec(cp + 1, spec, cnt))\n-\t\t\tdiff_unmerge(cp + 1);\n-\t\treturn 0;\n+\t\tdiff_unmerge(cp + 1);\n+\t\tbreak;\n \tcase '+':\n-\t\told.file_valid = 0;\n-\t\tparse_oneside_change(cp, &new, path);\n+\t\tparse_oneside_change(cp, &new_mode, new_sha1, path);\n+\t\tdiff_addremove('+', new_mode, new_sha1, path, NULL);\n \t\tbreak;\n \tcase '-':\n-\t\tnew.file_valid = 0;\n-\t\tparse_oneside_change(cp, &old, path);\n+\t\tparse_oneside_change(cp, &old_mode, old_sha1, path);\n+\t\tdiff_addremove('-', old_mode, old_sha1, path, NULL);\n \t\tbreak;\n \tcase '*':\n-\t\told.file_valid = old.sha1_valid =\n-\t\t\tnew.file_valid = new.sha1_valid = 1;\n-\t\told.mode = new.mode = 0;\n+\t\told_mode = new_mode = 0;\n \t\twhile ((ch = *cp) && ('0' <= ch && ch <= '7')) {\n-\t\t\told.mode = (old.mode << 3) | (ch - '0');\n+\t\t\told_mode = (old_mode << 3) | (ch - '0');\n \t\t\tcp++;\n \t\t}\n \t\tif (strncmp(cp, \"->\", 2))\n \t\t\treturn -1;\n \t\tcp += 2;\n \t\twhile ((ch = *cp) && ('0' <= ch && ch <= '7')) {\n-\t\t\tnew.mode = (new.mode << 3) | (ch - '0');\n+\t\t\tnew_mode = (new_mode << 3) | (ch - '0');\n \t\t\tcp++;\n \t\t}\n \t\tif (strncmp(cp, \"\\tblob\\t\", 6))\n \t\t\treturn -1;\n \t\tcp += 6;\n-\t\tif (get_sha1_hex(cp, old.blob_sha1))\n+\t\tif (get_sha1_hex(cp, old_sha1))\n \t\t\treturn -1;\n \t\tcp += 40;\n \t\tif (strncmp(cp, \"->\", 2))\n \t\t\treturn -1;\n \t\tcp += 2;\n-\t\tif (get_sha1_hex(cp, new.blob_sha1))\n+\t\tif (get_sha1_hex(cp, new_sha1))\n \t\t\treturn -1;\n \t\tcp += 40;\n \t\tif (*cp++ != '\\t')\n \t\t\treturn -1;\n \t\tstrcpy(path, cp);\n+\t\tdiff_change(old_mode, new_mode, old_sha1, new_sha1, path, 0);\n \t\tbreak;\n \tdefault:\n \t\treturn -1;\n \t}\n-\n-\tif (detect_rename && old.file_valid != new.file_valid) {\n-\t\t/* hold these */\n-\t\thold_spec(path, &old, &new);\n-\t\treturn 0;\n-\t}\n-\n-\tif (!cnt || matches_pathspec(path, spec, cnt)) {\n-\t\tif (reverse)\n-\t\t\trun_external_diff(path, NULL, &new, &old);\n-\t\telse\n-\t\t\trun_external_diff(path, NULL, &old, &new);\n-\t}\n \treturn 0;\n }\n \n static const char *diff_helper_usage =\n-\t\"git-diff-helper [-r] [-R] [-z] paths...\";\n+\t\"git-diff-helper [-z] [-R] [-M] paths...\";\n \n int main(int ac, const char **av) {\n \tstruct strbuf sb;\n@@ -254,7 +101,7 @@\n \t\t\treverse = 1;\n \t\telse if (av[1][1] == 'z')\n \t\t\tline_termination = 0;\n-\t\telse if (av[1][1] == 'r')\n+\t\telse if (av[1][1] == 'M')\n \t\t\tdetect_rename = 1;\n \t\telse\n \t\t\tusage(diff_helper_usage);\n@@ -262,18 +109,20 @@\n \t}\n \t/* the remaining parameters are paths patterns */\n \n+\tdiff_setup(detect_rename, 0, reverse, av+1, ac-1);\n+\n \twhile (1) {\n \t\tint status;\n \t\tread_line(&sb, stdin, line_termination);\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\tstatus = parse_diff_raw_output(sb.buf);\n \t\tif (status) {\n-\t\t\tflush_renames(av+1, ac-1, reverse);\n+\t\t\tdiff_flush();\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+\tdiff_flush();\n \treturn 0;\n }\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -9,6 +9,7 @@\n static int read_stdin = 0;\n static int line_termination = '\\n';\n static int generate_patch = 0;\n+static int detect_rename = 0;\n static const char *header = NULL;\n static const char *header_prefix = \"\";\n \n@@ -281,6 +282,18 @@\n \treturn retval;\n }\n \n+static int diff_tree_sha1_top(const unsigned char *old,\n+\t\t\t const unsigned char *new, const char *base)\n+{\n+\tint ret;\n+\tif (generate_patch)\n+\t\tdiff_setup(detect_rename, 0, 0, 0, 0);\n+\tret = diff_tree_sha1(old, new, base);\n+\tif (generate_patch)\n+\t\tdiff_flush();\n+\treturn ret;\n+}\n+\n static int get_one_line(const char *msg, unsigned long len)\n {\n \tint ret = 0;\n@@ -377,7 +390,7 @@\n \t\tif (get_sha1_hex(buf + offset + 7, parent))\n \t\t\treturn -1;\n \t\theader = generate_header(name, sha1_to_hex(parent), buf, size);\n-\t\tdiff_tree_sha1(parent, commit, \"\");\n+\t\tdiff_tree_sha1_top(parent, commit, \"\");\n \t\tif (!header && verbose_header)\n \t\t\theader_prefix = \"\\ndiff-tree \";\n \t\toffset += 48;\n@@ -401,14 +414,14 @@\n \t\tline[81] = 0;\n \t\tsprintf(this_header, \"%s (from %s)\\n\", line, line+41);\n \t\theader = this_header;\n-\t\treturn diff_tree_sha1(parent, commit, \"\");\n+\t\treturn diff_tree_sha1_top(parent, commit, \"\");\n \t}\n \tline[40] = 0;\n \treturn diff_tree_commit(commit, line);\n }\n \n static char *diff_tree_usage =\n-\"diff-tree [-p] [-r] [-z] [--stdin] [-m] [-s] [-v] \";\n+\"diff-tree [-p] [-r] [-z] [--stdin] [-M] [-m] [-s] [-v] \";\n \n int main(int argc, char **argv)\n {\n@@ -447,6 +460,10 @@\n \t\t\trecursive = generate_patch = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"-M\")) {\n+\t\t\tdetect_rename = recursive = generate_patch = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = '\\0';\n \t\t\tcontinue;\n@@ -490,7 +507,7 @@\n \t\tdiff_tree_commit(sha1[0], NULL);\n \t\tbreak;\n \tcase 2:\n-\t\tdiff_tree_sha1(sha1[0], sha1[1], \"\");\n+\t\tdiff_tree_sha1_top(sha1[0], sha1[1], \"\");\n \t\tbreak;\n \t}\n \ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -7,8 +7,10 @@\n #include \n #include \"cache.h\"\n #include \"diff.h\"\n+#include \"delta.h\"\n \n static const char *diff_opts = \"-pu\";\n+static unsigned char null_sha1[20] = { 0, };\n \n static const char *external_diff(void)\n {\n@@ -79,6 +81,18 @@\n \tchar tmp_path[50];\n } diff_temp[2];\n \n+struct diff_spec {\n+\tunsigned char blob_sha1[20];\n+\tunsigned short mode;\t /* file mode */\n+\tunsigned sha1_valid : 1; /* if true, use blob_sha1 and trust mode;\n+\t\t\t\t * however with a NULL SHA1, read them\n+\t\t\t\t * from the file system.\n+\t\t\t\t * if false, use the name and read mode from\n+\t\t\t\t * the filesystem.\n+\t\t\t\t */\n+\tunsigned file_valid : 1; /* if false the file does not even exist */\n+};\n+\n static void builtin_diff(const char *name_a,\n \t\t\t const char *name_b,\n \t\t\t struct diff_tempfile *temp)\n@@ -160,7 +174,7 @@\n \tstruct cache_entry *ce;\n \tstruct stat st;\n \tint pos, len;\n-\t\n+\n \t/* We do not read the cache ourselves here, because the\n \t * benchmark with my previous version that always reads cache\n \t * shows that it makes things worse for diff-tree comparing\n@@ -214,9 +228,6 @@\n \t\t\t struct diff_tempfile *temp,\n \t\t\t struct diff_spec *one)\n {\n-\tstatic unsigned char null_sha1[20] = { 0, };\n-\tint use_work_tree = 0;\n-\n \tif (!one->file_valid) {\n \tnot_a_valid_file:\n \t\t/* A '-' entry produces this for file-2, and\n@@ -228,12 +239,8 @@\n \t\treturn;\n \t}\n \n-\tif (one->sha1_valid &&\n-\t (!memcmp(one->blob_sha1, null_sha1, sizeof(null_sha1)) ||\n-\t work_tree_matches(name, one->blob_sha1)))\n-\t\tuse_work_tree = 1;\n-\n-\tif (!one->sha1_valid || use_work_tree) {\n+\tif (!one->sha1_valid ||\n+\t work_tree_matches(name, one->blob_sha1)) {\n \t\tstruct stat st;\n \t\ttemp->name = name;\n \t\tif (lstat(temp->name, &st) < 0) {\n@@ -295,22 +302,59 @@\n \tremove_tempfile();\n }\n \n+static int detect_rename;\n+static int reverse_diff;\n+static const char **pathspec;\n+static int speccnt;\n+static int diff_rename_minimum_score;\n+\n+static int matches_pathspec(const char *name)\n+{\n+\tint i;\n+\tint namelen;\n+\n+\tif (speccnt == 0)\n+\t\treturn 1;\n+\n+\tnamelen = strlen(name);\n+\tfor (i = 0; i < speccnt; i++) {\n+\t\tint speclen = strlen(pathspec[i]);\n+\t\tif (! strncmp(pathspec[i], name, speclen) &&\n+\t\t speclen <= namelen &&\n+\t\t (name[speclen] == 0 || name[speclen] == '/'))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n /* An external diff command takes:\n *\n * diff-cmd name infile1 infile1-sha1 infile1-mode \\\n- * infile2 infile2-sha1 infile2-mode.\n+ * infile2 infile2-sha1 infile2-mode [ rename-to ]\n *\n */\n-void run_external_diff(const char *name,\n-\t\t const char *other,\n-\t\t struct diff_spec *one,\n-\t\t struct diff_spec *two)\n+static void run_external_diff(const char *name,\n+\t\t\t const char *other,\n+\t\t\t struct diff_spec *one,\n+\t\t\t struct diff_spec *two)\n {\n \tstruct diff_tempfile *temp = diff_temp;\n \tpid_t pid;\n \tint status;\n \tstatic int atexit_asked = 0;\n \n+\tif (reverse_diff) {\n+\t\tstruct diff_spec *tmp_spec;\n+\t\ttmp_spec = one; one = two; two = tmp_spec;\n+\t\tif (other) {\n+\t\t\tconst char *tmp;\n+\t\t\ttmp = name; name = other; other = tmp;\n+\t\t}\n+\t}\n+\n+\tif (!matches_pathspec(name) && (!other || !matches_pathspec(other)))\n+\t\treturn;\n+\n \tif (one && two) {\n \t\tprepare_temp_file(name, &temp[0], one);\n \t\tprepare_temp_file(other ? : name, &temp[1], two);\n@@ -329,14 +373,23 @@\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\tif (!other && pgm) {\n-\t\t\tif (one && two)\n-\t\t\t\texeclp(pgm, pgm,\n-\t\t\t\t name,\n-\t\t\t\t temp[0].name, temp[0].hex, temp[0].mode,\n-\t\t\t\t temp[1].name, temp[1].hex, temp[1].mode,\n-\t\t\t\t NULL);\n+\t\tif (pgm) {\n+\t\t\tif (one && two) {\n+\t\t\t\tconst char *exec_arg[9];\n+\t\t\t\tconst char **arg = &exec_arg[0];\n+\t\t\t\t*arg++ = pgm;\n+\t\t\t\t*arg++ = name;\n+\t\t\t\t*arg++ = temp[0].name;\n+\t\t\t\t*arg++ = temp[0].hex;\n+\t\t\t\t*arg++ = temp[0].mode;\n+\t\t\t\t*arg++ = temp[1].name;\n+\t\t\t\t*arg++ = temp[1].hex;\n+\t\t\t\t*arg++ = temp[1].mode;\n+\t\t\t\tif (other)\n+\t\t\t\t\t*arg++ = other;\n+\t\t\t\t*arg = 0;\n+\t\t\t\texecvp(pgm, (char *const*) exec_arg);\n+\t\t\t}\n \t\t\telse\n \t\t\t\texeclp(pgm, pgm, name, NULL);\n \t\t}\n@@ -367,6 +420,293 @@\n \tremove_tempfile();\n }\n \n+/*\n+ * We do not detect circular renames. Just hold created and deleted\n+ * entries and later attempt to match them up. If they do not match,\n+ * then spit them out as deletes or creates as original.\n+ */\n+\n+static struct diff_spec_hold {\n+\tstruct diff_spec_hold *next;\n+\tstruct diff_spec it;\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+static void hold_diff(const char *name,\n+\t\t struct diff_spec *one,\n+\t\t struct diff_spec *two)\n+{\n+\tstruct diff_spec_hold **list, *elem;\n+\n+\tif (one->file_valid && two->file_valid)\n+\t\tdie(\"internal error\");\n+\n+\tif (!detect_rename) {\n+\t\trun_external_diff(name, NULL, one, two);\n+\t\treturn;\n+\t}\n+\telem = xmalloc(sizeof(*elem) + strlen(name));\n+\tstrcpy(elem->path, name);\n+\telem->size = 0;\n+\telem->data = NULL;\n+\telem->flags = 0;\n+\tif (one->file_valid) {\n+\t\tlist = &deletedfile;\n+\t\telem->it = *one;\n+\t}\n+\telse {\n+\t\tlist = &createdfile;\n+\t\telem->it = *two;\n+\t}\n+\telem->next = *list;\n+\t*list = elem;\n+}\n+\n+static int populate_data(struct diff_spec_hold *s)\n+{\n+\tchar type[20];\n+\n+\tif (s->data)\n+\t\treturn 0;\n+\tif (s->it.sha1_valid) {\n+\t\ts->data = read_sha1_file(s->it.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_remaining_diff(struct diff_spec_hold *elem,\n+\t\t\t\t int on_created_list)\n+{\n+\tstatic struct diff_spec null_file_spec;\n+\n+\tnull_file_spec.file_valid = 0;\n+\tfor ( ; elem ; elem = elem->next) {\n+\t\tfree_data(elem);\n+\t\tif (elem->flags & MATCHED)\n+\t\t\tcontinue;\n+\t\tif (on_created_list)\n+\t\t\trun_external_diff(elem->path, NULL,\n+\t\t\t\t\t &null_file_spec, &elem->it);\n+\t\telse\n+\t\t\trun_external_diff(elem->path, NULL,\n+\t\t\t\t\t &elem->it, &null_file_spec);\n+\t}\n+}\n+\n+static int is_exact_match(struct diff_spec_hold *src,\n+\t\t\t struct diff_spec_hold *dst)\n+{\n+\tif (src->it.sha1_valid && dst->it.sha1_valid &&\n+\t !memcmp(src->it.blob_sha1, dst->it.blob_sha1, 20))\n+\t\treturn 1;\n+\tif (populate_data(src) || populate_data(dst))\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 1;\n+\treturn 0;\n+}\n+\n+#define MINIMUM_SCORE 5000\n+int estimate_similarity(struct diff_spec_hold *src, struct diff_spec_hold *dst)\n+{\n+\t/* src points at a deleted file and dst points at a created\n+\t * file. They may be quite similar, in which case we want to\n+\t * say src is renamed to dst.\n+\t *\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+\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 *\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+struct diff_score {\n+\tstruct diff_spec_hold *src;\n+\tstruct diff_spec_hold *dst;\n+\tint score;\n+};\n+\n+static int score_compare(const void *a_, const void *b_)\n+{\n+\tconst struct diff_score *a = a_, *b = b_;\n+\treturn b->score - a->score;\n+}\n+\n+static void flush_rename_pair(struct diff_spec_hold *src,\n+\t\t\t struct diff_spec_hold *dst)\n+{\n+\tsrc->flags |= MATCHED;\n+\tdst->flags |= MATCHED;\n+\tfree_data(src);\n+\tfree_data(dst);\n+\trun_external_diff(src->path, dst->path,\n+\t\t\t &src->it, &dst->it);\n+}\n+\n+static void free_held_diff(struct diff_spec_hold *list)\n+{\n+\tstruct diff_spec_hold *h;\n+\tfor (h = list; list; list = h) {\n+\t\th = list->next;\n+\t\tfree_data(list);\n+\t\tfree(list);\n+\t}\n+}\n+\n+void diff_flush(void)\n+{\n+\tint num_create, num_delete, c, d;\n+\tstruct diff_spec_hold *elem, *src, *dst;\n+\tstruct diff_score *mx;\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 (dst = createdfile; dst; dst = dst->next) {\n+\t\tfor (src = deletedfile; src; src = src->next) {\n+\t\t\tif (! is_exact_match(src, dst))\n+\t\t\t\tcontinue;\n+\t\t\tflush_rename_pair(src, dst);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\t/* Count surviving candidates */\n+\tfor (num_create = 0, elem = createdfile; elem; elem = elem->next)\n+\t\tif (!(elem->flags & MATCHED))\n+\t\t\tnum_create++;\n+\n+\tfor (num_delete = 0, elem = deletedfile; elem; elem = elem->next)\n+\t\tif (!(elem->flags & MATCHED))\n+\t\t\tnum_delete++;\n+\n+\tif (num_create == 0 || num_delete == 0)\n+\t\tgoto exit_path;\n+\n+\tmx = xmalloc(sizeof(*mx) * num_create * num_delete);\n+\tfor (c = 0, dst = createdfile; dst; dst = dst->next) {\n+\t\tint base = c * num_delete;\n+\t\tif (dst->flags & MATCHED)\n+\t\t\tcontinue;\n+\t\tfor (d = 0, src = deletedfile; src; src = src->next) {\n+\t\t\tstruct diff_score *m = &mx[base+d];\n+\t\t\tif (src->flags & MATCHED)\n+\t\t\t\tcontinue;\n+\t\t\tm->src = src;\n+\t\t\tm->dst = dst;\n+\t\t\tm->score = estimate_similarity(src, dst);\n+\t\t\td++;\n+\t\t}\n+\t\tc++;\n+\t}\n+\tqsort(mx, num_create*num_delete, sizeof(*mx), score_compare); \n+\n+ \tfor (c = 0; c < num_create * num_delete; c++) {\n+\t\tsrc = mx[c].src;\n+\t\tdst = mx[c].dst;\n+\t\tif ((src->flags & MATCHED) || (dst->flags & MATCHED))\n+\t\t\tcontinue;\n+\t\tfprintf(stderr,\n+\t\t\t\"**score ** %d %s %s\\n\",\n+\t\t\tmx[c].score, src->path, dst->path);\n+\t}\n+\n+ \tfor (c = 0; c < num_create * num_delete; c++) {\n+\t\tsrc = mx[c].src;\n+\t\tdst = mx[c].dst;\n+\t\tif ((src->flags & MATCHED) || (dst->flags & MATCHED))\n+\t\t\tcontinue;\n+\t\tif (mx[c].score < diff_rename_minimum_score)\n+\t\t\tbreak;\n+\t\tflush_rename_pair(src, dst);\n+\t}\n+\n+ exit_path:\n+\tflush_remaining_diff(createdfile, 1);\n+\tflush_remaining_diff(deletedfile, 0);\n+\tfree_held_diff(createdfile);\n+\tfree_held_diff(deletedfile);\n+\tcreatedfile = deletedfile = NULL;\n+}\n+\n+void diff_setup(int detect_rename_, int minimum_score_, int reverse_diff_,\n+\t\tconst char **pathspec_, int speccnt_)\n+{\n+\tfree_held_diff(createdfile);\n+\tfree_held_diff(deletedfile);\n+\tcreatedfile = deletedfile = NULL;\n+\n+\tdetect_rename = detect_rename_;\n+\treverse_diff = reverse_diff_;\n+\tpathspec = pathspec_;\n+\tspeccnt = speccnt_;\n+\tdiff_rename_minimum_score = minimum_score_ ? : MINIMUM_SCORE;\n+}\n+\n void diff_addremove(int addremove, unsigned mode,\n \t\t const unsigned char *sha1,\n \t\t const char *base, const char *path)\n@@ -376,7 +716,8 @@\n \n \tmemcpy(spec[0].blob_sha1, sha1, 20);\n \tspec[0].mode = mode;\n-\tspec[0].sha1_valid = spec[0].file_valid = 1;\n+\tspec[0].sha1_valid = !!memcmp(sha1, null_sha1, 20);\n+\tspec[0].file_valid = 1;\n \tspec[1].file_valid = 0;\n \n \tif (addremove == '+') {\n@@ -384,12 +725,12 @@\n \t} else {\n \t\tone = spec; two = one + 1;\n \t}\n-\t\n+\n \tif (path) {\n \t\tstrcpy(concatpath, base);\n \t\tstrcat(concatpath, path);\n \t}\n-\trun_external_diff(path ? concatpath : base, NULL, one, two);\n+\thold_diff(path ? concatpath : base, one, two);\n }\n \n void diff_change(unsigned old_mode, unsigned new_mode,\n@@ -399,17 +740,22 @@\n \tchar concatpath[PATH_MAX];\n \tstruct diff_spec spec[2];\n \n+\tif (path) {\n+\t\tstrcpy(concatpath, base);\n+\t\tstrcat(concatpath, path);\n+\t}\n+\n \tmemcpy(spec[0].blob_sha1, old_sha1, 20);\n \tspec[0].mode = old_mode;\n \tmemcpy(spec[1].blob_sha1, new_sha1, 20);\n \tspec[1].mode = new_mode;\n-\tspec[0].sha1_valid = spec[0].file_valid = 1;\n-\tspec[1].sha1_valid = spec[1].file_valid = 1;\n+\tspec[0].sha1_valid = !!memcmp(old_sha1, null_sha1, 20);\n+\tspec[1].sha1_valid = !!memcmp(new_sha1, null_sha1, 20);\n+\tspec[1].file_valid = spec[0].file_valid = 1;\n \n-\tif (path) {\n-\t\tstrcpy(concatpath, base);\n-\t\tstrcat(concatpath, path);\n-\t}\n+\t/* We do not look at changed files as candidate for\n+\t * rename detection ever.\n+\t */\n \trun_external_diff(path ? concatpath : base, NULL, &spec[0], &spec[1]);\n }\n \ndiff --git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -17,21 +17,10 @@\n \n extern void diff_unmerge(const char *path);\n \n-/* These are for diff-helper */\n+extern void diff_setup(int detect_rename, int minimum_score,\n+\t\t int reverse,\n+\t\t const char **spec, int cnt);\n \n-struct diff_spec {\n-\tunsigned char blob_sha1[20];\n-\tunsigned short mode;\t /* file mode */\n-\tunsigned sha1_valid : 1; /* if true, use blob_sha1 and trust mode;\n-\t\t\t\t * however with a NULL SHA1, read them\n-\t\t\t\t * from the file system.\n-\t\t\t\t * if false, use the name and read mode from\n-\t\t\t\t * the filesystem.\n-\t\t\t\t */\n-\tunsigned file_valid : 1; /* if false the file does not even exist */\n-};\n-\n-extern void run_external_diff(const char *name, const char *other,\n-\t\t\t struct diff_spec *, struct diff_spec *);\n+extern void diff_flush(void);\n \n #endif /* DIFF_H */\ndiff --git a/git-apply-patch-script b/git-apply-patch-script\n--- a/git-apply-patch-script\n+++ b/git-apply-patch-script\n@@ -11,6 +11,9 @@\n 1)\n echo >&2 \"cannot handle unmerged diff on path $1.\"\n exit 1 ;;\n+8)\n+ echo >&2 \"cannot handle rename diff between $1 and $8 yet.\"\n+ exit 1 ;;\n esac\n name=\"$1\" tmp1=\"$2\" hex1=\"$3\" mode1=\"$4\" tmp2=\"$5\" hex2=\"$6\" mode2=\"$7\"\n \ndiff --git a/t/t4001-diff-rename.sh b/t/t4001-diff-rename.sh\nnew file mode 100644\n--- /dev/null\n+++ b/t/t4001-diff-rename.sh\n@@ -0,0 +1,60 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+\n+test_description='Test rename detection in diff engine.\n+\n+'\n+. ./test-lib.sh\n+\n+echo >path0 'Line 1\n+Line 2\n+Line 3\n+Line 4\n+Line 5\n+Line 6\n+Line 7\n+Line 8\n+Line 9\n+Line 10\n+line 11\n+Line 12\n+Line 13\n+Line 14\n+Line 15\n+'\n+\n+test_expect_success \\\n+ 'update-cache --add a file.' \\\n+ 'git-update-cache --add path0'\n+\n+test_expect_success \\\n+ 'write that tree.' \\\n+ 'tree=$(git-write-tree)'\n+\n+sed -e 's/line/Line/' path1\n+rm -f path0\n+test_expect_success \\\n+ 'renamed and edited the file.' \\\n+ 'git-update-cache --add --remove path0 path1'\n+\n+test_expect_success \\\n+ 'git-diff-cache -p -M after rename and editing.' \\\n+ 'git-diff-cache -p -M $tree >current'\n+cat >expected <<\\EOF\n+diff --git a/path0 b/path1\n+rename old path0\n+rename new path1\n+--- a/path0\n++++ b/path1\n+@@ -8,7 +8,7 @@ Line 7\n+ Line 8\n+ Line 9\n+ Line 10\n+-line 11\n++Line 11\n+ Line 12\n+ Line 13\n+ Line 14\n+EOF\n------------------------------------------------\n\n"},{"id":"3556","messageId":"Pine.LNX.4.58.0505190901340.2322@ppc970.osdl.org","threadId":"660","inReplyTo":"7vu0kz1p6k.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T16:19:28Z","receivedAt":"2005-05-19T16:19:28Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Junio C Hamano wrote:\n> \n> Special request for Linus is to check if I did not screw up the\n> various calls into the diff core from diff-tree. Essentially\n> the idea is to start one patchset session with diff_setup() and\n> close it with diff_flush() before you start another patchset\n> session.\n\nIt all looks ok from a quick setup, and with this I can now do\n\n\tgit-whatchanged -M\n\nin the kernel, and searching for renames I find:\n\n\tdiff --git a/arch/um/kernel/sys_call_table.c b/arch/um/sys-x86_64/sys_call_table.c\n\trename old arch/um/kernel/sys_call_table.c\n\trename new arch/um/sys-x86_64/sys_call_table.c\n\t--- a/arch/um/kernel/sys_call_table.c\n\t+++ b/arch/um/sys-x86_64/sys_call_table.c\n\t@@ -1,4 +1,4 @@\n\t-/* \n\t+/*\n\t * Copyright (C) 2000 Jeff Dike (jdike@karaya.com)\n\t * Copyright 2003 PathScale, Inc.\n\t * Licensed under the GPL\n\t@@ -14,6 +14,12 @@\n\t #include \"sysdep/syscalls.h\"\n\t #include \"kern_util.h\"\n\t \n\t+#ifdef CONFIG_NFSD\n\t....\n\nwhich looks quite correct.\n\nI notice that you left some debugging output in there (\"**score **\" \nstuff), and I'll remove it, but it's merged and pushed out and passed my \ntrivial tests. \n\n[ rambling mode on: ]\n\nOne thing that struck me is that there is nothing wrong with having the \nsame old file marked twice for a rename, or considering new files to be \ncopies of old files. So if we ever allow that, then \"rename\" may be the \nwrong name for this, since the logic certainly allows the old file to \nstill exist (or be removed and show up multiple times in a new guise).\n\nIn other words, let's say that we create a new architecture or a new \nfilesystem, and we have tons of _new_ files, but not a lot of removed \nfiles. It would literally be very cool to see that the new files are based \non contents of old files, and that it would thus potentially be very \ninteresting to see a diff like\n\n\tdiff --git a/arch/i386/kernel/irq.c b/arch/x86-64/kernel/irq.c\n\tbased-on old arch/i386/kernel/irq.c\n\tcreates new arch/x86-64/kernel/irq.c\n\t--- arch/i386/kernel/irq.c\n\t+++ arch/x86_64/kernel/irq.c\n\t@@ -1,205 +1,31 @@\n\t /*\n\t- * linux/arch/i386/kernel/irq.c\n\t+ * linux/arch/x86_64/kernel/irq.c\n\t *\n\t * Copyright (C) 1992, 1998 Linus Torvalds, Ingo Molnar\n\t *\n\t...\n\n(the above is a made-up example, but it's at least _half-way_ valid).\n\nI'm not suggesting you actually do this, if only because it's quite\nexpensive: it means that any newly added file would have to be compared\nwith _all_ files in the previous archive, which is just too damn\nexpensive. But I'd like people to kind of keep this in mind as a\npossibility, because maybe wasting CPU time in a big way might actually be\nacceptable in some cases, and having a separate flag to enable this kind \nof thing might be interesting, no?\n\n\t\tLinus\n"},{"id":"3561","messageId":"7v4qcz16n6.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505190901340.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T17:13:01Z","receivedAt":"2005-05-19T17:13:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> I notice that you left some debugging output in there (\"**score **\" \nLT> stuff), and I'll remove it, but it's merged and pushed out and passed my \nLT> trivial tests. \n\nOops,... thanks. I still had some doubts about it and that's\nwhy I said it was beta, but that is fine. My doubts are minor:\n\n - the command line interface \"-M\" to read \"-M\" or \"-M[0-9]\"\n (one digit); -M defaults to -M5 and give the cut-off point at\n similarity score 5000, -M9 at 9000, etc.\n\n - I was debating myself if adding something like this was a\n good idea (using scale between 0 and 9 corresponding the\n -M[0-9] option):\n\n\tdiff --git a/arch/um/kernel/sys_call_table.c b/arch/um/sys-x86_64/sys_call_table.c\n *** rename similarity index 8\n\trename old arch/um/kernel/sys_call_table.c\n\trename new arch/um/sys-x86_64/sys_call_table.c\n\t--- a/arch/um/kernel/sys_call_table.c\n\t+++ b/arch/um/sys-x86_64/sys_call_table.c\n\n - I have been assuming that diff_delta uses its two input\n read-only but have not verified that myself yet.\n\n - I did not check for leaks and knew I had outdated comments in\n some while doing the diff core interface cleanups.\n\nA bit of clean-up patch, which may not apply exactly if you\nremoved the **score** stuff is attached.\n\nSigned-off-by: Junio C Hamano \n---\n# - HEAD: Detect renames in diff family.\n# + 11: Cleanup and leak fix after rename in diff family patch.\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -85,12 +85,10 @@ struct diff_spec {\n \tunsigned char blob_sha1[20];\n \tunsigned short mode;\t /* file mode */\n \tunsigned sha1_valid : 1; /* if true, use blob_sha1 and trust mode;\n-\t\t\t\t * however with a NULL SHA1, read them\n-\t\t\t\t * from the file system.\n-\t\t\t\t * if false, use the name and read mode from\n+\t\t\t\t * if false, use the name and read from\n \t\t\t\t * the filesystem.\n \t\t\t\t */\n-\tunsigned file_valid : 1; /* if false the file does not even exist */\n+\tunsigned file_valid : 1; /* if false the file does not exist */\n };\n \n static void builtin_diff(const char *name_a,\n@@ -506,6 +504,7 @@ static void free_data(struct diff_spec_h\n \telse if (s->flags & SHOULD_MUNMAP)\n \t\tmunmap(s->data, s->size);\n \ts->flags &= ~(SHOULD_FREE|SHOULD_MUNMAP);\n+\ts->data = 0;\n }\n \n static void flush_remaining_diff(struct diff_spec_hold *elem,\n@@ -625,9 +624,17 @@ void diff_flush(void)\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 (dst = createdfile; dst; dst = dst->next) {\n+\t\tif (dst->flags & MATCHED)\n+\t\t\tcontinue;\n \t\tfor (src = deletedfile; src; src = src->next) {\n+\t\t\tif (src->flags & MATCHED)\n+\t\t\t\tcontinue;\n \t\t\tif (! is_exact_match(src, dst))\n \t\t\t\tcontinue;\n \t\t\tflush_rename_pair(src, dst);\n@@ -665,6 +672,7 @@ void diff_flush(void)\n \t}\n \tqsort(mx, num_create*num_delete, sizeof(*mx), score_compare); \n \n+#if 0\n \tfor (c = 0; c < num_create * num_delete; c++) {\n \t\tsrc = mx[c].src;\n \t\tdst = mx[c].dst;\n@@ -674,6 +682,7 @@ void diff_flush(void)\n \t\t\t\"**score ** %d %s %s\\n\",\n \t\t\tmx[c].score, src->path, dst->path);\n \t}\n+#endif\n \n \tfor (c = 0; c < num_create * num_delete; c++) {\n \t\tsrc = mx[c].src;\n@@ -684,6 +693,7 @@ void diff_flush(void)\n \t\t\tbreak;\n \t\tflush_rename_pair(src, dst);\n \t}\n+\tfree(mx);\n \n exit_path:\n \tflush_remaining_diff(createdfile, 1);\n\n"},{"id":"3562","messageId":"Pine.LNX.4.58.0505191029331.2322@ppc970.osdl.org","threadId":"660","inReplyTo":"7v4qcz16n6.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T17:31:39Z","receivedAt":"2005-05-19T17:31:39Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Junio C Hamano wrote:\n> \n> - I have been assuming that diff_delta uses its two input\n> read-only but have not verified that myself yet.\n\nSince test-delta uses mmap(PROT_READ), we'd get SIGSEGV if diff_delta \nactually wrote to the thing. So this is a safe assumption.\n\n\t\tLinus\n"},{"id":"3564","messageId":"20050519174606.GF22946@ca-server1.us.oracle.com","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505190901340.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Joel Becker","fromEmail":"joel.becker@oracle.com","sentAt":"2005-05-19T17:46:06Z","receivedAt":"2005-05-19T17:46:06Z","isPatch":true,"sender":{"key":"joel.becker@oracle.com","avatar":null},"body":"On Thu, May 19, 2005 at 09:19:28AM -0700, Linus Torvalds wrote:\n> In other words, let's say that we create a new architecture or a new \n> filesystem, and we have tons of _new_ files, but not a lot of removed \n> files. It would literally be very cool to see that the new files are based \n> on contents of old files, and that it would thus potentially be very \n> interesting to see a diff like\n\n\tSubversion encourages exactly this with the 'svn cp' command.\nJust as knowing when a file was renamed allows you to track the history\npast its first appearance under the current name, 'cp' allows you to\nfollow the history even if the original name still exists. I have found\nthis useful more than once.\n\tNow, whether you track this up front with an expensive commit or\nuse tools to discover the relationship at query time (ala your\nwhy-rename-tracking-isnt-needed argument) is a different question. As\nwe all know, most tools ask the user to explicitly declare the\nrelationship at the time it happens with 'svn rename' and 'svn cp' or\nthe analog. But git could do the comparisons, with appropriate\nheuristics, at the time someone asks.\n\nJoel\n\n-- \n\nLife's Little Instruction Book #335\n\n\t\"Every so often, push your luck.\"\n\nJoel Becker\nSenior Member of Technical Staff\nOracle\nE-mail: joel.becker@oracle.com\nPhone: (650) 506-8127\n"},{"id":"3567","messageId":"Pine.LNX.4.62.0505191426000.20274@localhost.localdomain","threadId":"660","inReplyTo":"7v4qcz16n6.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T18:29:46Z","receivedAt":"2005-05-19T18:29:46Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Junio C Hamano wrote:\n\n> - the command line interface \"-M\" to read \"-M\" or \"-M[0-9]\"\n> (one digit); -M defaults to -M5 and give the cut-off point at\n> similarity score 5000, -M9 at 9000, etc.\n\nWhy not a fractional value instead? -M1 is 100% the same while -M.95 \nallows for some 5% changes.\n\nThis is clear and not based on some arbitrary level values.\n\n> - I have been assuming that diff_delta uses its two input\n> read-only but have not verified that myself yet.\n\nIt does.\n\n\nNicolas\n"},{"id":"3569","messageId":"7vy8abys5a.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7v4qcz16n6.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T18:42:09Z","receivedAt":"2005-05-19T18:42:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Replying to myself.\n\nJCH> Oops,... thanks. I still had some doubts about it and that's\nJCH> why I said it was beta, but that is fine. My doubts are minor:\n\nHere is another \"doubt\" point. I am almost embarrassed to ask\nthis, but what's the right way to express the following? I\ncould not figure out how to silence const warnings from gcc\nwithout using the cast there, which defeats the whole point of\nconst warnings:\n\n\tif (!pid) {\n\t\tconst char *pgm = external_diff();\n\t\tif (pgm) {\n\t\t\tif (one && two) {\n\t\t\t\tconst char *exec_arg[9];\n\t\t\t\tconst char **arg = &exec_arg[0];\n\t\t\t\t*arg++ = pgm;\n\t\t\t\t*arg++ = name;\n\t\t\t\t*arg++ = temp[0].name;\n\t\t\t\t*arg++ = temp[0].hex;\n\t\t\t\t*arg++ = temp[0].mode;\n\t\t\t\t*arg++ = temp[1].name;\n\t\t\t\t*arg++ = temp[1].hex;\n\t\t\t\t*arg++ = temp[1].mode;\n\t\t\t\tif (other)\n\t\t\t\t\t*arg++ = other;\n\t\t\t\t*arg = 0;\n\t\t\t\texecvp(pgm, (char *const*) exec_arg);\n\t\t\t}\n\nHere, pgm and name are const, execvp expects char *const argv[]\nas its second argument.\n\n"},{"id":"3571","messageId":"7vsm0jyryf.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.62.0505191426000.20274@localhost.localdomain","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T18:46:16Z","receivedAt":"2005-05-19T18:46:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre writes:\n\nNP> On Thu, 19 May 2005, Junio C Hamano wrote:\n>> - the command line interface \"-M\" to read \"-M\" or \"-M[0-9]\"\n>> (one digit); -M defaults to -M5 and give the cut-off point at\n>> similarity score 5000, -M9 at 9000, etc.\n\nNP> Why not a fractional value instead? -M1 is 100% the same while -M.95 \nNP> allows for some 5% changes.\n\nWe are essentially saying the same thing. Internally diff core\nuses score between 0 and 10000 but single digit proposed above\nor fractional both hides that from the user by normalizing the\nscale to something less arbitrary (in my case 0-9 in your case\n0-1.0).\n\n\n\n"},{"id":"3570","messageId":"7voeb7yrwf.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.62.0505191426000.20274@localhost.localdomain","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T18:47:28Z","receivedAt":"2005-05-19T18:47:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre writes:\n\n>> - I have been assuming that diff_delta uses its two input\n>> read-only but have not verified that myself yet.\n\nNP> It does.\n\nThanks (also thanks to Linus for pointing out the PROT_READ in\nthe test program).\n\n"},{"id":"3573","messageId":"Pine.LNX.4.58.0505191148470.2322@ppc970.osdl.org","threadId":"660","inReplyTo":"7vy8abys5a.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T18:55:52Z","receivedAt":"2005-05-19T18:55:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Junio C Hamano wrote:\n> \n> Here is another \"doubt\" point. I am almost embarrassed to ask\n> this, but what's the right way to express the following? I\n> could not figure out how to silence const warnings from gcc\n> without using the cast there, which defeats the whole point of\n> const warnings:\n\nYou're not doing this right.\n\nLike it or not, \"execvp()\" does not take a pointer to \"const char *\".\n\nIt takes a pointer to a constant array of _non-const_ \"char *\".\n\nWhich is not what you have. You have a non-const array of \"const char *\", \nand as a result, you need the cast.\n\nIn other words, you really need\n\n\tchar *exec_arg[9];\n\nor, if you can indeed set the array to be const, you can make it be\n\n\tchar *const exec_arg[9] = {\n\t\tpgm, name,\n\t\ttemp[0].name, temp[0].hex, temp[0].mode,\n\t\ttemp[1].name, temp[1].hex, temp[1].mode,\n\t}\n\nwhich would work, except to avoid warnings it obviously requires that none\nof the strings themselves are \"const\" (which isn't true).\n\nIOW, you're screwed. \"execvp()\" really should take an argument of type\n\"const char * const *\", but it doesn't for historical reasons.\n\n\t\tLinus\n"},{"id":"3574","messageId":"Pine.LNX.4.62.0505191456040.20274@localhost.localdomain","threadId":"660","inReplyTo":"7vsm0jyryf.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T18:58:05Z","receivedAt":"2005-05-19T18:58:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Junio C Hamano wrote:\n\n> >>>>> \"NP\" == Nicolas Pitre writes:\n> \n> NP> On Thu, 19 May 2005, Junio C Hamano wrote:\n> >> - the command line interface \"-M\" to read \"-M\" or \"-M[0-9]\"\n> >> (one digit); -M defaults to -M5 and give the cut-off point at\n> >> similarity score 5000, -M9 at 9000, etc.\n> \n> NP> Why not a fractional value instead? -M1 is 100% the same while -M.95 \n> NP> allows for some 5% changes.\n> \n> We are essentially saying the same thing. Internally diff core\n> uses score between 0 and 10000 but single digit proposed above\n> or fractional both hides that from the user by normalizing the\n> scale to something less arbitrary (in my case 0-9 in your case\n> 0-1.0).\n\nYes, but 0-9 is putting a bound on the accuracy. What if someone wants \nnot more than 2% difference?\n\n\nNicolas\n"},{"id":"3577","messageId":"7vk6lvyou1.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505191148470.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T19:53:42Z","receivedAt":"2005-05-19T19:53:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> IOW, you're screwed. \"execvp()\" really should take an argument of type\nLT> \"const char * const *\", but it doesn't for historical reasons.\n\nThat's what I suspected.\n\n"},{"id":"3578","messageId":"428CF317.5010103@zytor.com","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505191148470.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-05-19T20:12:07Z","receivedAt":"2005-05-19T20:12:07Z","isPatch":true,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> IOW, you're screwed. \"execvp()\" really should take an argument of type\n> \"const char * const *\", but it doesn't for historical reasons.\n> \n\nThe real problem, IMNSHO, is that C doesn't allow a pointer to a pointer \nto a non-const object to be implicitly treated as a pointer to a pointer \nto a const object. C should have required those two pointer classes to \nhave the same representation (which they would in any sane, and pretty \nmuch any insane, system) and therefore a lot of functions could have the \nadditional consts added to their prototypes.\n\nAt least one can do casts on sane architectures... :-/\n\n\t-hpa\n"},{"id":"3581","messageId":"7vy8abx8ay.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.62.0505191456040.20274@localhost.localdomain","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T20:36:05Z","receivedAt":"2005-05-19T20:36:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre writes:\n\nNP> Yes, but 0-9 is putting a bound on the accuracy. What if someone wants \nNP> not more than 2% difference?\n\nThat statement is correct, but I think you are looking at it\nfrom a developer perspective.\n\nI suspect people would not want to pay the price of having\nalways to type many digits for the benefit of being able to\nspecify differences of 2% and 5%. Would you also complain gzip\nonly lets you say -1 .. -9 and not -1.63 ;-)?\n\n"},{"id":"3584","messageId":"Pine.LNX.4.62.0505191643030.20274@localhost.localdomain","threadId":"660","inReplyTo":"7vy8abx8ay.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T20:48:13Z","receivedAt":"2005-05-19T20:48:13Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Junio C Hamano wrote:\n\n> >>>>> \"NP\" == Nicolas Pitre writes:\n> \n> NP> Yes, but 0-9 is putting a bound on the accuracy. What if someone wants \n> NP> not more than 2% difference?\n> \n> That statement is correct, but I think you are looking at it\n> from a developer perspective.\n> \n> I suspect people would not want to pay the price of having\n> always to type many digits for the benefit of being able to\n> specify differences of 2% and 5%. Would you also complain gzip\n> only lets you say -1 .. -9 and not -1.63 ;-)?\n\nAre we talking about git plumbing or porcelain here?\n\n\nNicolas\n"},{"id":"3585","messageId":"7vll6ayjok.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.62.0505191643030.20274@localhost.localdomain","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T21:44:59Z","receivedAt":"2005-05-19T21:44:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre writes:\n\nNP> Are we talking about git plumbing or porcelain here?\n\nWe are talking about the Plumbing. Thank you for reminding me,\nbut sometimes people end up using the bare Plumbing.\n\nAs I stated before, I do not do Porcelain [*1*]; my main\ninterest lies in helping Linus and Linux Kernel development\nprocess, by helping him in the Plumbing area and making the use\nof bare Plumbing layer a confortable enough experience.\n\nMy ultimate goal is to make the Plumbing useful enough to make\nwhat Porcelain layers do more or less irrelevant ;-).\n\n[Footnote]\n\n*1* Yes I do have my own Porcelain layer, and personally I feel\nsome of the things it does and some of the approaches it takes\nare quite good, but I do not advocate it more than necessary on\nthis list.\n\n"},{"id":"3587","messageId":"Pine.LNX.4.58.0505191516350.2322@ppc970.osdl.org","threadId":"660","inReplyTo":"7vll6ayjok.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T22:26:39Z","receivedAt":"2005-05-19T22:26:39Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Junio C Hamano wrote:\n> \n> We are talking about the Plumbing. Thank you for reminding me,\n> but sometimes people end up using the bare Plumbing.\n\nThere's a pretty simple and nice way to make it both useful and easy to do \nto arbitrary precision.\n\nThink of the number following the -M as the mantissa.\n\nSo -M9 means 0.9 aka \"90% match\" (or \"difference\", depending on which way\nyou want to go), and in general -Mx would have the \"10% increments\" thing.\n\nBut since it's a fraction, you just give more precision by adding more \nnumbers, and -M99 would be \"99% match\", while \"-M02\" would be \"2% match\"\n\nThen it would be logical for a plain -M to be 100% match / 0% difference\n(ie only show renames that are exact), since a \"0% match\" / 100%\ndifference is nonsensical.\n\nAlternatively, we'd have -M (without any number) just default to \nsomething, and you'd give a separate number of how closely you want to \nmach things, ie\n\n\t# These all mean the same thing: (default) 20% difference\n\tgit-diff-tree -M\n\tgit-diff-tree -M --match=80\n\tgit-diff-tree -M --differ=20\n\n\t# show only renames that are perfect matches.\n\tgit-diff-tree -M --match=100\n\n\t# show _everything_ as a rename, except the\n\t# matching matrix means that we prefer better\n\t# matches over worse\n\tgit-diff-tree -M --match=0\n\nHmm?\n\n\t\tLinus\n"},{"id":"3590","messageId":"7vhdgyyeom.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505191516350.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T23:32:57Z","receivedAt":"2005-05-19T23:32:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Not quite a related topic, but unless we start to support the\ncopy detection you recommended against, my understanding is that\n-M does not do anything useful for git-diff-files. Is there a\ngood use case for it? I am not advocating for its removal so\nplease leave the command line option there.\n\n\n"},{"id":"3592","messageId":"Pine.LNX.4.58.0505191656310.2322@ppc970.osdl.org","threadId":"660","inReplyTo":"7vhdgyyeom.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-20T00:10:53Z","receivedAt":"2005-05-20T00:10:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Junio C Hamano wrote:\n>\n> Not quite a related topic, but unless we start to support the\n> copy detection you recommended against, my understanding is that\n> -M does not do anything useful for git-diff-files. Is there a\n> good use case for it? I am not advocating for its removal so\n> please leave the command line option there.\n\nHmm.. You're right, but it feels kind of wrong. Clearly we support\nremovals in diff-files, but you're right, we can never have something show\nup as an addition, since we only ever compare against files that are\nalready mentioned in the cache.\n\nOn the other hand, a unmerged entry really _could_ be a new file, could it \nnot? Even if we right now always report it as \"Unmerged path\"? If it's a \ncase of existing in stage 2/3 only, it really should show up as a new file \ndiff for git-diff-files, no?\n\nOr am I just being confused and/or stupid?\n\n\t\tLinus\n"},{"id":"3593","messageId":"7vy8aawwm9.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505191656310.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-20T00:48:30Z","receivedAt":"2005-05-20T00:48:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> Hmm.. You're right, but it feels kind of wrong. Clearly we\nLT> support removals in diff-files, but you're right, we can\nLT> never have something show up as an addition, since we only\nLT> ever compare against files that are already mentioned in the\nLT> cache.\n\nLT> Or am I just being confused and/or stupid?\n\nNo, you are not confused nor stupid. We discussed something\nrelated to this about three weeks ago. We ended up not doing\nwhat we discussed, but if we had adopted the convention of the\ndelayed addition to the cache I described as \"magic SHA1\" in the\nquoted message below, that would have been the \"intent to add\"\nthat diff-files would report as an addition.\n\nTo:\tLinus Torvalds \nCc:\tgit@vger.kernel.org\nSubject: Re: [PATCH] Really fix git-merge-one-file-script this time.\nFrom:\tJunio C Hamano \nDate:\tSun, 01 May 2005 11:38:15 -0700\nMessage-ID: <7vzmveu6zs.fsf@assigned-by-dhcp.cox.net>\n\n (... some discussion omitted ...)\nI am wondering if the following changes would make sense and\nmake things easier for you:\n\n * git-merge-one-file-script is changed to register the path\n with --cacheinfo using magic SHA1 0{40} instead of using the\n resulting file on the filesystem. Do keep the current\n behaviour of leaving the merge results of trivial merges\n (both kind) in the work tree.\n\n * git-write-tree is changed to refuse to write from a cache\n that records the magic SHA1.\n\n * git-ls-files acquires a new option --merged to notice the\n magic SHA1 and shows the paths that have such SHA1.\n\n * git-update-cache acquires a new option --resolve to notice\n the magic SHA1 and:\n\n - if the named path is not in the work tree anymore, delete\n the entry.\n\n - if the named path exists in the work tree, compute the\n latest SHA1 for that file and update the entry.\n\nChanges other than the first two listed above are purely\noptional, since the Porcelain layer can implement them without\nthe Plumbing support. Not doing them would keep the Plumbing\nsomewhat cleaner by not having to know about this magic SHA1\nconvention. On the other hand, we already use that convention\nin git-diff-cache, so it may even be a consistent change to make\nthese optional changes. Essentially, the magic SHA1 in the\ncache means \"I know the user wants me to keep an eye on this\npath when it matters\" [*2*].\n\n[Footnotes]\n\n (... footnote *1* omitted ...)\n\n*2* This convention would also make an implementation of \"SCM\nadd\" in the Porcelain layer a bit more efficient. A typical\nworkflow without such a convention would consist of:\n\n * Create a file and start editing.\n * \"SCM add\" file, causing \"git-update-cache --add -- file\".\n * Do more changes, and review.\n * \"SCM commit\" which does\"git-update-cache\" changed files,\n \"git-write-tree\" and \"git-commit-tree\" to commit.\n\nwhich wastes one extra blob object per \"SCM add\". My gut\nfeeling is that more than 80% of the time \"SCM add\" is followed\nby some edit to the added file before \"SCM commit\", unless it is\nthe initial import. If we adopt that convention, \"SCM add\"\nwould register with --cacheinfo with the magic SHA1 without\ncreating the useless blob, and \"SCM commit\" will be written to\nlazily pick things up from the work tree.\n\n"},{"id":"3687","messageId":"7vzmuokjhg.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505190901340.2322@ppc970.osdl.org","subject":"Re: [PATCH] Detect renames in diff family.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T09:37:31Z","receivedAt":"2005-05-21T09:37:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> [ rambling mode on: ]\n\nLT> One thing that struck me is that there is nothing wrong with having the \nLT> same old file marked twice for a rename, or considering new files to be \nLT> copies of old files. So if we ever allow that, then \"rename\" may be the \nLT> wrong name for this, since the logic certainly allows the old file to \nLT> still exist (or be removed and show up multiple times in a new guise).\n\nPeople say be careful what you wish and for a reason. You may\nget it ;-). I am sending the following:\n\n [PATCH 1/3] Diff overhaul, adding half of copy detection.\n [PATCH 2/3] Introducing software archaeologist's tool \"pickaxe\".\n [PATCH 3/3] Diff overhaul, adding the other half of copy detection.\n\n\n"},{"id":"3688","messageId":"7vu0kwkjeq.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vzmuokjhg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 1/3] Diff overhaul, adding half of copy detection.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T09:39:09Z","receivedAt":"2005-05-21T09:39:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This introduces the diff-core, the layer between the diff-tree\nfamily and the external diff interface engine. The calls to the\ninterface diff-tree family uses (diff_change and diff_addremove)\nhave not changed and will not change. The purpose of the\ndiff-core layer is to provide an infrastructure to transform the\nset of differences sent from the applications, before sending\nthem to the external diff interface.\n\nThe recently introduced rename detection code has been rewritten\nto use the diff-core facility. When applications send in\nseparate creates and deletes, matching ones are transformed into\na single rename-and-edit diff, and sent out to the external diff\ninterface as such.\n\nThis patch also enhances the rename detection code further to be\nable to detect copies. Currently this happens only as long as\ncopy sources appear as part of the modified files, but there\nalready is enough provision for callers to report unmodified\nfiles to diff-core, so that they can be also used as copy source\ncandidates. Extending the callers this way will be done in a\nseparate patch.\n\nPlease see and marvel at how well this works by trying out the\nnewly added t/t4003-diff-rename-1.sh test script.\n\nSigned-off-by: Junio C Hamano \n---\n\nDocumentation/git-diff-cache.txt | 5 \nDocumentation/git-diff-files.txt | 5 \nDocumentation/git-diff-helper.txt | 4 \nDocumentation/git-diff-tree.txt | 6 \nMakefile | 5 \ndiff-cache.c | 8 \ndiff-files.c | 7 \ndiff-helper.c | 25 +\ndiff-tree.c | 8 \ndiff.c | 703 +++++++++++++++-----------------------\ndiffcore-rename.c | 443 +++++++++++++++++++++++\ndiffcore.h | 60 +++\ngit-apply-patch-script | 2 \nt/t0000-basic.sh | 2 \nt/t4001-diff-rename.sh | 4 \nt/t4003-diff-rename-1.sh | 93 +++++\n16 files changed, 946 insertions(+), 434 deletions(-)\nnew file (100644): diffcore-rename.c\nnew file (100644): diffcore.h\nnew file (100755): t/t4003-diff-rename-1.sh\n\ndiff --git a/Documentation/git-diff-cache.txt b/Documentation/git-diff-cache.txt\n--- a/Documentation/git-diff-cache.txt\n+++ b/Documentation/git-diff-cache.txt\n@@ -9,7 +9,7 @@ git-diff-cache - Compares content and mo\n \n SYNOPSIS\n --------\n-'git-diff-cache' [-p] [-r] [-z] [-m] [-M] [-R] [--cached] \n+'git-diff-cache' [-p] [-r] [-z] [-m] [-M] [-R] [-C] [--cached] \n \n DESCRIPTION\n -----------\n@@ -36,6 +36,9 @@ OPTIONS\n -M::\n \tDetect renames; implies -p.\n \n+-C::\n+\tDetect copies as well as renames; implies -p.\n+\n -R::\n \tOutput diff in reverse.\n \ndiff --git a/Documentation/git-diff-files.txt b/Documentation/git-diff-files.txt\n--- a/Documentation/git-diff-files.txt\n+++ b/Documentation/git-diff-files.txt\n@@ -9,7 +9,7 @@ git-diff-files - Compares files in the w\n \n SYNOPSIS\n --------\n-'git-diff-files' [-p] [-q] [-r] [-z] [-M] [-R] [...]\n+'git-diff-files' [-p] [-q] [-r] [-z] [-M] [-C] [-R] [...]\n \n DESCRIPTION\n -----------\n@@ -32,6 +32,9 @@ OPTIONS\n -M::\n \tDetect renames; implies -p.\n \n+-C::\n+\tDetect copies as well as renames; implies -p.\n+\n -r::\n \tThis flag does not mean anything. It is there only to match\n \tgit-diff-tree. Unlike git-diff-tree, git-diff-files always looks\ndiff --git a/Documentation/git-diff-helper.txt b/Documentation/git-diff-helper.txt\n--- a/Documentation/git-diff-helper.txt\n+++ b/Documentation/git-diff-helper.txt\n@@ -9,7 +9,7 @@ git-diff-helper - Generates patch format\n \n SYNOPSIS\n --------\n-'git-diff-helper' [-z] [-R] [-M]\n+'git-diff-helper' [-z] [-R] [-M] [-C]\n \n DESCRIPTION\n -----------\n@@ -34,6 +34,8 @@ OPTIONS\n -M::\n \tDetect renames.\n \n+-C::\n+\tDetect copies as well as renames.\n \n See Also\n --------\ndiff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt\n--- a/Documentation/git-diff-tree.txt\n+++ b/Documentation/git-diff-tree.txt\n@@ -9,7 +9,7 @@ git-diff-tree - Compares the content and\n \n SYNOPSIS\n --------\n-'git-diff-tree' [-p] [-r] [-z] [--stdin] [-M] [-R] [-m] [-s] [-v] []\\*\n+'git-diff-tree' [-p] [-r] [-z] [--stdin] [-M] [-R] [-C] [-m] [-s] [-v] []\\*\n \n DESCRIPTION\n -----------\n@@ -36,6 +36,10 @@ OPTIONS\n -M::\n \tDetect renames; implies -p, in turn implying also '-r'.\n \n+-C::\n+\tDetect copies as well as renames; implies -p, in turn\n+\timplying also '-r'.\n+\n -R::\n \tOutput diff in reverse.\n \ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -45,7 +45,7 @@ LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n \n LIB_H += diff.h\n-LIB_OBJS += diff.o\n+LIB_OBJS += diff.o diffcore-rename.o\n \n LIB_OBJS += gitenv.o\n \n@@ -121,9 +121,10 @@ object.o: $(LIB_H)\n read-cache.o: $(LIB_H)\n sha1_file.o: $(LIB_H)\n usage.o: $(LIB_H)\n-diff.o: $(LIB_H)\n strbuf.o: $(LIB_H)\n gitenv.o: $(LIB_H)\n+diff.o: $(LIB_H)\n+diffcore-rename.o : $(LIB_H)\n \n test: all\n \tmake -C t/ all\ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -153,7 +153,7 @@ static void mark_merge_entries(void)\n }\n \n static char *diff_cache_usage =\n-\"git-diff-cache [-p] [-r] [-z] [-m] [-M] [-R] [--cached] \";\n+\"git-diff-cache [-p] [-r] [-z] [-m] [-M] [-C] [-R] [--cached] \";\n \n int main(int argc, char **argv)\n {\n@@ -180,6 +180,12 @@ int main(int argc, char **argv)\n \t\t\tdiff_score_opt = diff_scoreopt_parse(arg);\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strncmp(arg, \"-C\", 2)) {\n+\t\t\tgenerate_patch = 1;\n+\t\t\tdetect_rename = 2;\n+\t\t\tdiff_score_opt = diff_scoreopt_parse(arg);\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = '\\0';\n \t\t\tcontinue;\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -7,7 +7,7 @@\n #include \"diff.h\"\n \n static const char *diff_files_usage =\n-\"git-diff-files [-p] [-q] [-r] [-z] [-M] [-R] [paths...]\";\n+\"git-diff-files [-p] [-q] [-r] [-z] [-M] [-C] [-R] [paths...]\";\n \n static int generate_patch = 0;\n static int line_termination = '\\n';\n@@ -71,6 +71,11 @@ int main(int argc, char **argv)\n \t\t\tdiff_score_opt = diff_scoreopt_parse(argv[1]);\n \t\t\tdetect_rename = generate_patch = 1;\n \t\t}\n+\t\telse if (!strncmp(argv[1], \"-C\", 2)) {\n+\t\t\tdiff_score_opt = diff_scoreopt_parse(argv[1]);\n+\t\t\tdetect_rename = 2;\n+\t\t\tgenerate_patch = 1;\n+\t\t}\n \t\telse\n \t\t\tusage(diff_files_usage);\n \t\targv++; argc--;\ndiff --git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -8,6 +8,7 @@\n \n static int detect_rename = 0;\n static int diff_score_opt = 0;\n+static int generate_patch = 1;\n \n static int parse_oneside_change(const char *cp, int *mode,\n \t\t\t\tunsigned char *sha1, char *path)\n@@ -20,7 +21,8 @@ static int parse_oneside_change(const ch\n \t\tcp++;\n \t}\n \t*mode = m;\n-\tif (strncmp(cp, \"\\tblob\\t\", 6) && strncmp(cp, \" blob \", 6))\n+\tif (strncmp(cp, \"\\tblob\\t\", 6) && strncmp(cp, \" blob \", 6) &&\n+\t strncmp(cp, \"\\ttree\\t\", 6) && strncmp(cp, \" tree \", 6))\n \t\treturn -1;\n \tcp += 6;\n \tif (get_sha1_hex(cp, sha1))\n@@ -44,11 +46,13 @@ static int parse_diff_raw_output(const c\n \t\tdiff_unmerge(cp + 1);\n \t\tbreak;\n \tcase '+':\n-\t\tparse_oneside_change(cp, &new_mode, new_sha1, path);\n+\t\tif (parse_oneside_change(cp, &new_mode, new_sha1, path))\n+\t\t\treturn -1;\n \t\tdiff_addremove('+', new_mode, new_sha1, path, NULL);\n \t\tbreak;\n \tcase '-':\n-\t\tparse_oneside_change(cp, &old_mode, old_sha1, path);\n+\t\tif (parse_oneside_change(cp, &old_mode, old_sha1, path))\n+\t\t\treturn -1;\n \t\tdiff_addremove('-', old_mode, old_sha1, path, NULL);\n \t\tbreak;\n \tcase '*':\n@@ -64,7 +68,8 @@ static int parse_diff_raw_output(const c\n \t\t\tnew_mode = (new_mode << 3) | (ch - '0');\n \t\t\tcp++;\n \t\t}\n-\t\tif (strncmp(cp, \"\\tblob\\t\", 6) && strncmp(cp, \" blob \", 6))\n+\t\tif (strncmp(cp, \"\\tblob\\t\", 6) && strncmp(cp, \" blob \", 6) &&\n+\t\t strncmp(cp, \"\\ttree\\t\", 6) && strncmp(cp, \" tree \", 6))\n \t\t\treturn -1;\n \t\tcp += 6;\n \t\tif (get_sha1_hex(cp, old_sha1))\n@@ -88,7 +93,7 @@ static int parse_diff_raw_output(const c\n }\n \n static const char *diff_helper_usage =\n-\t\"git-diff-helper [-z] [-R] [-M] paths...\";\n+\t\"git-diff-helper [-z] [-R] [-M] [-C] paths...\";\n \n int main(int ac, const char **av) {\n \tstruct strbuf sb;\n@@ -102,17 +107,25 @@ int main(int ac, const char **av) {\n \t\t\treverse = 1;\n \t\telse if (av[1][1] == 'z')\n \t\t\tline_termination = 0;\n+\t\telse if (av[1][1] == 'p') /* hidden from the help */\n+\t\t\tgenerate_patch = 0;\n \t\telse if (av[1][1] == 'M') {\n \t\t\tdetect_rename = 1;\n \t\t\tdiff_score_opt = diff_scoreopt_parse(av[1]);\n \t\t}\n+\t\telse if (av[1][1] == 'C') {\n+\t\t\tdetect_rename = 2;\n+\t\t\tdiff_score_opt = diff_scoreopt_parse(av[1]);\n+\t\t}\n \t\telse\n \t\t\tusage(diff_helper_usage);\n \t\tac--; av++;\n \t}\n \t/* the remaining parameters are paths patterns */\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse, -1, av+1, ac-1);\n+\tdiff_setup(detect_rename, diff_score_opt, reverse,\n+\t\t (generate_patch ? -1 : line_termination),\n+\t\t av+1, ac-1);\n \n \twhile (1) {\n \t\tint status;\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -430,7 +430,7 @@ static int diff_tree_stdin(char *line)\n }\n \n static char *diff_tree_usage =\n-\"git-diff-tree [-p] [-r] [-z] [--stdin] [-M] [-R] [-m] [-s] [-v] \";\n+\"git-diff-tree [-p] [-r] [-z] [--stdin] [-M] [-C] [-R] [-m] [-s] [-v] \";\n \n int main(int argc, char **argv)\n {\n@@ -478,6 +478,12 @@ int main(int argc, char **argv)\n \t\t\tdiff_score_opt = diff_scoreopt_parse(arg);\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strncmp(arg, \"-C\", 2)) {\n+\t\t\tdetect_rename = 2;\n+\t\t\trecursive = generate_patch = 1;\n+\t\t\tdiff_score_opt = diff_scoreopt_parse(arg);\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = '\\0';\n \t\t\tcontinue;\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -7,12 +7,17 @@\n #include \n #include \"cache.h\"\n #include \"diff.h\"\n-#include \"delta.h\"\n+#include \"diffcore.h\"\n \n static const char *diff_opts = \"-pu\";\n static unsigned char null_sha1[20] = { 0, };\n-#define MAX_SCORE 10000\n-#define DEFAULT_MINIMUM_SCORE 5000\n+\n+static int detect_rename;\n+static int reverse_diff;\n+static int diff_raw_output = -1;\n+static const char **pathspec;\n+static int speccnt;\n+static int minimum_score;\n \n static const char *external_diff(void)\n {\n@@ -77,26 +82,16 @@ static char *sq_expand(const char *src)\n }\n \n static struct diff_tempfile {\n-\tconst char *name;\n+\tconst char *name; /* filename external diff should read from */\n \tchar hex[41];\n \tchar mode[10];\n \tchar tmp_path[50];\n } diff_temp[2];\n \n-struct diff_spec {\n-\tunsigned char blob_sha1[20];\n-\tunsigned short mode;\t /* file mode */\n-\tunsigned sha1_valid : 1; /* if true, use blob_sha1 and trust mode;\n-\t\t\t\t * if false, use the name and read from\n-\t\t\t\t * the filesystem.\n-\t\t\t\t */\n-\tunsigned file_valid : 1; /* if false the file does not exist */\n-};\n-\n static void builtin_diff(const char *name_a,\n \t\t\t const char *name_b,\n \t\t\t struct diff_tempfile *temp,\n-\t\t\t int rename_score)\n+\t\t\t const char *xfrm_msg)\n {\n \tint i, next_at, cmd_size;\n \tconst char *diff_cmd = \"diff -L'%s%s' -L'%s%s'\";\n@@ -151,14 +146,9 @@ static void builtin_diff(const char *nam\n \t\t\tprintf(\"old mode %s\\n\", temp[0].mode);\n \t\t\tprintf(\"new mode %s\\n\", temp[1].mode);\n \t\t}\n-\t\tif (strcmp(name_a, name_b)) {\n-\t\t\tif (0 < rename_score)\n-\t\t\t\tprintf(\"rename similarity index %d%%\\n\",\n-\t\t\t\t (int)(0.5+\n-\t\t\t\t\t rename_score*100.0/MAX_SCORE));\n-\t\t\tprintf(\"rename old %s\\n\", name_a);\n-\t\t\tprintf(\"rename new %s\\n\", name_b);\n-\t\t}\n+\t\tif (xfrm_msg && xfrm_msg[0])\n+\t\t\tfputs(xfrm_msg, stdout);\n+\n \t\tif (strncmp(temp[0].mode, temp[1].mode, 3))\n \t\t\t/* we do not run diff between different kind\n \t\t\t * of objects.\n@@ -169,6 +159,28 @@ static void builtin_diff(const char *nam\n \texeclp(\"/bin/sh\",\"sh\", \"-c\", cmd, NULL);\n }\n \n+struct diff_filespec *alloc_filespec(const char *path)\n+{\n+\tint namelen = strlen(path);\n+\tstruct diff_filespec *spec = xmalloc(sizeof(*spec) + namelen + 1);\n+\tspec->path = (char *)(spec + 1);\n+\tstrcpy(spec->path, path);\n+\tspec->should_free = spec->should_munmap = spec->file_valid = 0;\n+\tspec->xfrm_flags = 0;\n+\tspec->size = 0;\n+\tspec->data = 0;\n+\treturn spec;\n+}\n+\n+void fill_filespec(struct diff_filespec *spec, const unsigned char *sha1,\n+\t\t unsigned short mode)\n+{\n+\tspec->mode = mode;\n+\tmemcpy(spec->sha1, sha1, 20);\n+\tspec->sha1_valid = !!memcmp(sha1, null_sha1, 20);\n+\tspec->file_valid = 1;\n+}\n+\n /*\n * Given a name and sha1 pair, if the dircache tells us the file in\n * the work tree has that object contents, return true, so that\n@@ -201,13 +213,86 @@ static int work_tree_matches(const char \n \t\treturn 0;\n \tce = active_cache[pos];\n \tif ((lstat(name, &st) < 0) ||\n-\t !S_ISREG(st.st_mode) ||\n+\t !S_ISREG(st.st_mode) || /* careful! */\n \t ce_match_stat(ce, &st) ||\n \t memcmp(sha1, ce->sha1, 20))\n \t\treturn 0;\n+\t/* we return 1 only when we can stat, it is a regular file,\n+\t * stat information matches, and sha1 recorded in the cache\n+\t * matches. I.e. we know the file in the work tree really is\n+\t * the same as the pair.\n+\t */\n \treturn 1;\n }\n \n+/*\n+ * While doing rename detection and pickaxe operation, we may need to\n+ * grab the data for the blob (or file) for our own in-core comparison.\n+ * diff_filespec has data and size fields for this purpose.\n+ */\n+int diff_populate_filespec(struct diff_filespec *s)\n+{\n+\tint err = 0;\n+\tif (!s->file_valid)\n+\t\tdie(\"internal error: asking to populate invalid file.\");\n+\tif (S_ISDIR(s->mode))\n+\t\treturn -1;\n+\n+\tif (s->data)\n+\t\treturn err;\n+\tif (!s->sha1_valid ||\n+\t work_tree_matches(s->path, s->sha1)) {\n+\t\tstruct stat st;\n+\t\tint fd;\n+\t\tif (lstat(s->path, &st) < 0) {\n+\t\t\tif (errno == ENOENT) {\n+\t\t\terr_empty:\n+\t\t\t\terr = -1;\n+\t\t\tempty:\n+\t\t\t\ts->data = \"\";\n+\t\t\t\ts->size = 0;\n+\t\t\t\treturn err;\n+\t\t\t}\n+\t\t}\n+\t\ts->size = st.st_size;\n+\t\tif (!s->size)\n+\t\t\tgoto empty;\n+\t\tif (S_ISLNK(st.st_mode)) {\n+\t\t\tint ret;\n+\t\t\ts->data = xmalloc(s->size);\n+\t\t\ts->should_free = 1;\n+\t\t\tret = readlink(s->path, s->data, s->size);\n+\t\t\tif (ret < 0) {\n+\t\t\t\tfree(s->data);\n+\t\t\t\tgoto err_empty;\n+\t\t\t}\n+\t\t\treturn 0;\n+\t\t}\n+\t\tfd = open(s->path, O_RDONLY);\n+\t\tif (fd < 0)\n+\t\t\tgoto err_empty;\n+\t\ts->data = mmap(NULL, s->size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\ts->should_munmap = 1;\n+\t\tclose(fd);\n+\t}\n+\telse {\n+\t\tchar type[20];\n+\t\ts->data = read_sha1_file(s->sha1, type, &s->size);\n+\t\ts->should_free = 1;\n+\t}\n+\treturn 0;\n+}\n+\n+void diff_free_filespec_data(struct diff_filespec *s)\n+{\n+\tif (s->should_free)\n+\t\tfree(s->data);\n+\telse if (s->should_munmap)\n+\t\tmunmap(s->data, s->size);\n+\ts->should_free = s->should_munmap = 0;\n+\ts->data = 0;\n+}\n+\n static void prep_temp_blob(struct diff_tempfile *temp,\n \t\t\t void *blob,\n \t\t\t unsigned long size,\n@@ -231,7 +316,7 @@ static void prep_temp_blob(struct diff_t\n \n static void prepare_temp_file(const char *name,\n \t\t\t struct diff_tempfile *temp,\n-\t\t\t struct diff_spec *one)\n+\t\t\t struct diff_filespec *one)\n {\n \tif (!one->file_valid) {\n \tnot_a_valid_file:\n@@ -245,13 +330,12 @@ static void prepare_temp_file(const char\n \t}\n \n \tif (!one->sha1_valid ||\n-\t work_tree_matches(name, one->blob_sha1)) {\n+\t work_tree_matches(name, one->sha1)) {\n \t\tstruct stat st;\n-\t\ttemp->name = name;\n-\t\tif (lstat(temp->name, &st) < 0) {\n+\t\tif (lstat(name, &st) < 0) {\n \t\t\tif (errno == ENOENT)\n \t\t\t\tgoto not_a_valid_file;\n-\t\t\tdie(\"stat(%s): %s\", temp->name, strerror(errno));\n+\t\t\tdie(\"stat(%s): %s\", name, strerror(errno));\n \t\t}\n \t\tif (S_ISLNK(st.st_mode)) {\n \t\t\tint ret;\n@@ -263,31 +347,27 @@ static void prepare_temp_file(const char\n \t\t\t\tdie(\"readlink(%s)\", name);\n \t\t\tprep_temp_blob(temp, buf, st.st_size,\n \t\t\t\t (one->sha1_valid ?\n-\t\t\t\t\tone->blob_sha1 : null_sha1),\n+\t\t\t\t\tone->sha1 : null_sha1),\n \t\t\t\t (one->sha1_valid ?\n \t\t\t\t\tone->mode : S_IFLNK));\n \t\t}\n \t\telse {\n+\t\t\t/* we can borrow from the file in the work tree */\n+\t\t\ttemp->name = name;\n \t\t\tif (!one->sha1_valid)\n \t\t\t\tstrcpy(temp->hex, sha1_to_hex(null_sha1));\n \t\t\telse\n-\t\t\t\tstrcpy(temp->hex, sha1_to_hex(one->blob_sha1));\n+\t\t\t\tstrcpy(temp->hex, sha1_to_hex(one->sha1));\n \t\t\tsprintf(temp->mode, \"%06o\",\n \t\t\t\tS_IFREG |ce_permissions(st.st_mode));\n \t\t}\n \t\treturn;\n \t}\n \telse {\n-\t\tvoid *blob;\n-\t\tchar type[20];\n-\t\tunsigned long size;\n-\n-\t\tblob = read_sha1_file(one->blob_sha1, type, &size);\n-\t\tif (!blob || strcmp(type, \"blob\"))\n-\t\t\tdie(\"unable to read blob object for %s (%s)\",\n-\t\t\t name, sha1_to_hex(one->blob_sha1));\n-\t\tprep_temp_blob(temp, blob, size, one->blob_sha1, one->mode);\n-\t\tfree(blob);\n+\t\tif (diff_populate_filespec(one))\n+\t\t\tdie(\"cannot read data blob for %s\", one->path);\n+\t\tprep_temp_blob(temp, one->data, one->size,\n+\t\t\t one->sha1, one->mode);\n \t}\n }\n \n@@ -307,13 +387,6 @@ static void remove_tempfile_on_signal(in\n \tremove_tempfile();\n }\n \n-static int detect_rename;\n-static int reverse_diff;\n-static int diff_raw_output = -1;\n-static const char **pathspec;\n-static int speccnt;\n-static int minimum_score;\n-\n static int matches_pathspec(const char *name)\n {\n \tint i;\n@@ -341,9 +414,9 @@ static int matches_pathspec(const char *\n */\n static void run_external_diff(const char *name,\n \t\t\t const char *other,\n-\t\t\t struct diff_spec *one,\n-\t\t\t struct diff_spec *two,\n-\t\t\t int rename_score)\n+\t\t\t struct diff_filespec *one,\n+\t\t\t struct diff_filespec *two,\n+\t\t\t const char *xfrm_msg)\n {\n \tstruct diff_tempfile *temp = diff_temp;\n \tpid_t pid;\n@@ -373,7 +446,7 @@ static void run_external_diff(const char\n \t\tconst char *pgm = external_diff();\n \t\tif (pgm) {\n \t\t\tif (one && two) {\n-\t\t\t\tconst char *exec_arg[9];\n+\t\t\t\tconst char *exec_arg[10];\n \t\t\t\tconst char **arg = &exec_arg[0];\n \t\t\t\t*arg++ = pgm;\n \t\t\t\t*arg++ = name;\n@@ -383,9 +456,11 @@ static void run_external_diff(const char\n \t\t\t\t*arg++ = temp[1].name;\n \t\t\t\t*arg++ = temp[1].hex;\n \t\t\t\t*arg++ = temp[1].mode;\n-\t\t\t\tif (other)\n+\t\t\t\tif (other) {\n \t\t\t\t\t*arg++ = other;\n-\t\t\t\t*arg = NULL;\n+\t\t\t\t\t*arg++ = xfrm_msg;\n+\t\t\t\t}\n+\t\t\t\t*arg = 0;\n \t\t\t\texecvp(pgm, (char *const*) exec_arg);\n \t\t\t}\n \t\t\telse\n@@ -395,7 +470,7 @@ static void run_external_diff(const char\n \t\t * otherwise we use the built-in one.\n \t\t */\n \t\tif (one && two)\n-\t\t\tbuiltin_diff(name, other ? : name, temp, rename_score);\n+\t\t\tbuiltin_diff(name, other ? : name, temp, xfrm_msg);\n \t\telse\n \t\t\tprintf(\"* Unmerged path %s\\n\", name);\n \t\texit(0);\n@@ -418,335 +493,166 @@ static void run_external_diff(const char\n \tremove_tempfile();\n }\n \n-/*\n- * We do not detect circular renames. Just hold created and deleted\n- * entries and later attempt to match them up. If they do not match,\n- * then spit them out as deletes or creates as original.\n- */\n-\n-static struct diff_spec_hold {\n-\tstruct diff_spec_hold *next;\n-\tstruct diff_spec it;\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-static void hold_diff(const char *name,\n-\t\t struct diff_spec *one,\n-\t\t struct diff_spec *two)\n-{\n-\tstruct diff_spec_hold **list, *elem;\n-\n-\tif (one->file_valid && two->file_valid)\n-\t\tdie(\"internal error\");\n-\n-\tif (!detect_rename) {\n-\t\trun_external_diff(name, NULL, one, two, -1);\n-\t\treturn;\n-\t}\n-\telem = xmalloc(sizeof(*elem) + strlen(name));\n-\tstrcpy(elem->path, name);\n-\telem->size = 0;\n-\telem->data = NULL;\n-\telem->flags = 0;\n-\tif (one->file_valid) {\n-\t\tlist = &deletedfile;\n-\t\telem->it = *one;\n-\t}\n-\telse {\n-\t\tlist = &createdfile;\n-\t\telem->it = *two;\n-\t}\n-\telem->next = *list;\n-\t*list = elem;\n-}\n-\n-static int populate_data(struct diff_spec_hold *s)\n+int diff_scoreopt_parse(const char *opt)\n {\n-\tchar type[20];\n+\tint diglen, num, scale, i;\n+\tif (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C'))\n+\t\treturn -1; /* that is not a -M nor -C option */\n+\tdiglen = strspn(opt+2, \"0123456789\");\n+\tif (diglen == 0 || strlen(opt+2) != diglen)\n+\t\treturn 0; /* use default */\n+\tsscanf(opt+2, \"%d\", &num);\n+\tfor (i = 0, scale = 1; i < diglen; i++)\n+\t\tscale *= 10;\n \n-\tif (s->data)\n-\t\treturn 0;\n-\tif (s->it.sha1_valid) {\n-\t\ts->data = read_sha1_file(s->it.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+\t/* user says num divided by scale and we say internally that\n+\t * is MAX_SCORE * num / scale.\n+\t */\n+\treturn MAX_SCORE * num / scale;\n }\n \n-static void free_data(struct diff_spec_hold *s)\n+void diff_setup(int detect_rename_, int minimum_score_, int reverse_diff_,\n+\t\tint diff_raw_output_,\n+\t\tconst char **pathspec_, int speccnt_)\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-\ts->data = NULL;\n+\tdetect_rename = detect_rename_;\n+\treverse_diff = reverse_diff_;\n+\tpathspec = pathspec_;\n+\tdiff_raw_output = diff_raw_output_;\n+\tspeccnt = speccnt_;\n+\tminimum_score = minimum_score_ ? : DEFAULT_MINIMUM_SCORE;\n }\n \n-static void flush_remaining_diff(struct diff_spec_hold *elem,\n-\t\t\t\t int on_created_list)\n-{\n-\tstatic struct diff_spec null_file_spec;\n+static struct diff_queue_struct queued_diff;\n \n-\tnull_file_spec.file_valid = 0;\n-\tfor ( ; elem ; elem = elem->next) {\n-\t\tfree_data(elem);\n-\t\tif (elem->flags & MATCHED)\n-\t\t\tcontinue;\n-\t\tif (on_created_list)\n-\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t &null_file_spec, &elem->it, -1);\n-\t\telse\n-\t\t\trun_external_diff(elem->path, NULL,\n-\t\t\t\t\t &elem->it, &null_file_spec, -1);\n+struct diff_file_pair *diff_queue(struct diff_queue_struct *queue,\n+\t\t\t\t struct diff_filespec *one,\n+\t\t\t\t struct diff_filespec *two)\n+{\n+\tstruct diff_file_pair *dp = xmalloc(sizeof(*dp));\n+\tdp->one = one;\n+\tdp->two = two;\n+\tdp->xfrm_msg = 0;\n+\tdp->orig_order = queue->nr;\n+\tdp->xfrm_work = 0;\n+\tif (queue->alloc <= queue->nr) {\n+\t\tqueue->alloc = alloc_nr(queue->alloc);\n+\t\tqueue->queue = xrealloc(queue->queue,\n+\t\t\t\t sizeof(dp) * queue->alloc);\n \t}\n+\tqueue->queue[queue->nr++] = dp;\n+\treturn dp;\n }\n \n-static int is_exact_match(struct diff_spec_hold *src,\n-\t\t\t struct diff_spec_hold *dst)\n+static const char *git_object_type(unsigned mode)\n {\n-\tif (src->it.sha1_valid && dst->it.sha1_valid &&\n-\t !memcmp(src->it.blob_sha1, dst->it.blob_sha1, 20))\n-\t\treturn 1;\n-\tif (populate_data(src) || populate_data(dst))\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 1;\n-\treturn 0;\n+\treturn S_ISDIR(mode) ? \"tree\" : \"blob\";\n }\n \n-static int estimate_similarity(struct diff_spec_hold *src, struct diff_spec_hold *dst)\n+static void diff_flush_raw(struct diff_file_pair *p)\n {\n-\t/* src points at a deleted file and dst points at a created\n-\t * file. They may be quite similar, in which case we want to\n-\t * say src is renamed to dst.\n-\t *\n-\t * Compare them and return how similar they are, representing\n-\t * the score as an integer between 0 and 10000, except\n-\t * where they match exactly it is considered better than anything\n-\t * else.\n-\t */\n-\tvoid *delta;\n-\tunsigned long delta_size;\n-\tint score;\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 * minimum_score/MAX_SCORE edits; that is, delta_size must be smaller\n-\t * than (src->size + dst->size)/2 * minimum_score/MAX_SCORE,\n-\t * which means...\n-\t */\n-\n-\tif ((src->size+dst->size)*minimum_score < delta_size*MAX_SCORE*2)\n-\t\treturn 0;\n+\tstruct diff_filespec *it;\n+\tint addremove;\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+\t/* raw output does not have a way to express rename nor copy */\n+\tif (strcmp(p->one->path, p->two->path))\n+\t\treturn;\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 *\n-\t * Now we will give some score to it. 100% edit gets\n-\t * 0 points and 0% edit gets MAX_SCORE points. That is, every\n-\t * 1/MAX_SCORE edit gets 1 point penalty. The amount of penalty is:\n-\t *\n-\t * (delta_size * 2 / (src->size + dst->size)) * MAX_SCORE\n-\t *\n-\t */\n-\tscore = MAX_SCORE-(MAX_SCORE*2*delta_size/(src->size+dst->size));\n-\tif (score < 0) return 0;\n-\tif (MAX_SCORE < score) return MAX_SCORE;\n-\treturn score;\n-}\n+\tif (p->one->file_valid && p->two->file_valid) {\n+\t\tchar hex[41];\n+\t\tstrcpy(hex, sha1_to_hex(p->one->sha1));\n+\t\tprintf(\"*%06o->%06o %s %s->%s %s%c\",\n+\t\t p->one->mode, p->two->mode,\n+\t\t git_object_type(p->one->mode),\n+\t\t hex, sha1_to_hex(p->two->sha1),\n+\t\t p->one->path, diff_raw_output);\n+\t\treturn;\n+\t}\n \n-struct diff_score {\n-\tstruct diff_spec_hold *src;\n-\tstruct diff_spec_hold *dst;\n-\tint score;\n-};\n+\tif (p->one->file_valid) {\n+\t\tit = p->one;\n+\t\taddremove = '-';\n+\t} else {\n+\t\tit = p->two;\n+\t\taddremove = '+';\n+\t}\n \n-static int score_compare(const void *a_, const void *b_)\n-{\n-\tconst struct diff_score *a = a_, *b = b_;\n-\treturn b->score - a->score;\n+\tprintf(\"%c%06o %s %s %s%c\",\n+\t addremove,\n+\t it->mode, git_object_type(it->mode),\n+\t sha1_to_hex(it->sha1), it->path, diff_raw_output);\n }\n \n-static void flush_rename_pair(struct diff_spec_hold *src,\n-\t\t\t struct diff_spec_hold *dst,\n-\t\t\t int rename_score)\n+static void diff_flush_patch(struct diff_file_pair *p)\n {\n-\tsrc->flags |= MATCHED;\n-\tdst->flags |= MATCHED;\n-\tfree_data(src);\n-\tfree_data(dst);\n-\trun_external_diff(src->path, dst->path,\n-\t\t\t &src->it, &dst->it, rename_score);\n-}\n+\tconst char *name, *other;\n \n-static void free_held_diff(struct diff_spec_hold *list)\n-{\n-\tstruct diff_spec_hold *h;\n-\tfor (h = list; list; list = h) {\n-\t\th = list->next;\n-\t\tfree_data(list);\n-\t\tfree(list);\n-\t}\n+\tname = p->one->path;\n+\tother = (strcmp(name, p->two->path) ? p->two->path : NULL);\n+\tif ((p->one->file_valid && S_ISDIR(p->one->mode)) ||\n+\t (p->two->file_valid && S_ISDIR(p->two->mode)))\n+\t\treturn; /* no tree diffs in patch format */ \n+\n+\trun_external_diff(name, other, p->one, p->two, p->xfrm_msg);\n }\n \n-void diff_flush(void)\n+static int identical(struct diff_filespec *one, struct diff_filespec *two)\n {\n-\tint num_create, num_delete, c, d;\n-\tstruct diff_spec_hold *elem, *src, *dst;\n-\tstruct diff_score *mx;\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/* This function is written stricter than necessary to support\n+\t * the currently implemented transformers, but the idea is to\n+\t * let transformers to produce diff_file_pairs any way they want,\n+\t * and filter and clean them up here before producing the output.\n \t */\n-\tfor (dst = createdfile; dst; dst = dst->next) {\n-\t\tif (dst->flags & MATCHED)\n-\t\t\tcontinue;\n-\t\tfor (src = deletedfile; src; src = src->next) {\n-\t\t\tif (src->flags & MATCHED)\n-\t\t\t\tcontinue;\n-\t\t\tif (! is_exact_match(src, dst))\n-\t\t\t\tcontinue;\n-\t\t\tflush_rename_pair(src, dst, MAX_SCORE);\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\n-\t/* Count surviving candidates */\n-\tfor (num_create = 0, elem = createdfile; elem; elem = elem->next)\n-\t\tif (!(elem->flags & MATCHED))\n-\t\t\tnum_create++;\n-\n-\tfor (num_delete = 0, elem = deletedfile; elem; elem = elem->next)\n-\t\tif (!(elem->flags & MATCHED))\n-\t\t\tnum_delete++;\n-\n-\tif (num_create == 0 || num_delete == 0)\n-\t\tgoto exit_path;\n-\n-\tmx = xmalloc(sizeof(*mx) * num_create * num_delete);\n-\tfor (c = 0, dst = createdfile; dst; dst = dst->next) {\n-\t\tint base = c * num_delete;\n-\t\tif (dst->flags & MATCHED)\n-\t\t\tcontinue;\n-\t\tfor (d = 0, src = deletedfile; src; src = src->next) {\n-\t\t\tstruct diff_score *m = &mx[base+d];\n-\t\t\tif (src->flags & MATCHED)\n-\t\t\t\tcontinue;\n-\t\t\tm->src = src;\n-\t\t\tm->dst = dst;\n-\t\t\tm->score = estimate_similarity(src, dst);\n-\t\t\td++;\n-\t\t}\n-\t\tc++;\n-\t}\n-\tqsort(mx, num_create*num_delete, sizeof(*mx), score_compare);\n-\n-#if 0\n- \tfor (c = 0; c < num_create * num_delete; c++) {\n-\t\tsrc = mx[c].src;\n-\t\tdst = mx[c].dst;\n-\t\tif ((src->flags & MATCHED) || (dst->flags & MATCHED))\n-\t\t\tcontinue;\n-\t\tfprintf(stderr,\n-\t\t\t\"**score ** %d %s %s\\n\",\n-\t\t\tmx[c].score, src->path, dst->path);\n-\t}\n-#endif\n-\n- \tfor (c = 0; c < num_create * num_delete; c++) {\n-\t\tsrc = mx[c].src;\n-\t\tdst = mx[c].dst;\n-\t\tif ((src->flags & MATCHED) || (dst->flags & MATCHED))\n-\t\t\tcontinue;\n-\t\tif (mx[c].score < minimum_score)\n-\t\t\tbreak;\n-\t\tflush_rename_pair(src, dst, mx[c].score);\n-\t}\n-\tfree(mx);\n-\n- exit_path:\n-\tflush_remaining_diff(createdfile, 1);\n-\tflush_remaining_diff(deletedfile, 0);\n-\tfree_held_diff(createdfile);\n-\tfree_held_diff(deletedfile);\n-\tcreatedfile = deletedfile = NULL;\n-}\n \n-int diff_scoreopt_parse(const char *opt)\n-{\n-\tint diglen, num, scale, i;\n-\tif (opt[0] != '-' || opt[1] != 'M')\n-\t\treturn -1; /* that is not -M option */\n-\tdiglen = strspn(opt+2, \"0123456789\");\n-\tif (diglen == 0 || strlen(opt+2) != diglen)\n-\t\treturn 0; /* use default */\n-\tsscanf(opt+2, \"%d\", &num);\n-\tfor (i = 0, scale = 1; i < diglen; i++)\n-\t\tscale *= 10;\n+\tif (!one->file_valid && !two->file_valid)\n+\t\treturn 1; /* not interesting */\n \n-\t/* user says num divided by scale and we say internally that\n-\t * is MAX_SCORE * num / scale.\n+\t/* deletion, addition, mode change and renames are all interesting. */\n+\tif ((one->file_valid != two->file_valid) || (one->mode != two->mode) ||\n+\t strcmp(one->path, two->path))\n+\t\treturn 0;\n+\n+\t/* both are valid and point at the same path. that is, we are\n+\t * dealing with a change.\n \t */\n-\treturn MAX_SCORE * num / scale;\n+\tif (one->sha1_valid && two->sha1_valid &&\n+\t !memcmp(one->sha1, two->sha1, sizeof(one->sha1)))\n+\t\treturn 1; /* no change */\n+\tif (!one->sha1_valid && !two->sha1_valid)\n+\t\treturn 1; /* both look at the same file on the filesystem. */\n+\treturn 0;\n }\n \n-void diff_setup(int detect_rename_, int minimum_score_, int reverse_diff_,\n-\t\tint diff_raw_output_,\n-\t\tconst char **pathspec_, int speccnt_)\n+static void diff_flush_one(struct diff_file_pair *p)\n {\n-\tfree_held_diff(createdfile);\n-\tfree_held_diff(deletedfile);\n-\tcreatedfile = deletedfile = NULL;\n-\n-\tdetect_rename = detect_rename_;\n-\treverse_diff = reverse_diff_;\n-\tpathspec = pathspec_;\n-\tdiff_raw_output = diff_raw_output_;\n-\tspeccnt = speccnt_;\n-\tminimum_score = minimum_score_ ? : DEFAULT_MINIMUM_SCORE;\n+\tif (identical(p->one, p->two))\n+\t\treturn;\n+\tif (0 <= diff_raw_output)\n+\t\tdiff_flush_raw(p);\n+\telse\n+\t\tdiff_flush_patch(p);\n }\n \n-static const char *git_object_type(unsigned mode)\n+void diff_flush(void)\n {\n-\treturn S_ISDIR(mode) ? \"tree\" : \"blob\";\n+\tstruct diff_queue_struct *q = &queued_diff;\n+\tint i;\n+\n+\tif (detect_rename)\n+\t\tdiff_detect_rename(q, detect_rename, minimum_score);\n+\tfor (i = 0; i < q->nr; i++)\n+\t\tdiff_flush_one(q->queue[i]);\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_file_pair *p = q->queue[i];\n+\t\tdiff_free_filespec_data(p->one);\n+\t\tdiff_free_filespec_data(p->two);\n+\t\tfree(p->xfrm_msg);\n+\t\tfree(p);\n+\t}\n+\tfree(q->queue);\n+\tq->queue = NULL;\n+\tq->nr = q->alloc = 0;\n }\n \n void diff_addremove(int addremove, unsigned mode,\n@@ -754,41 +660,35 @@ void diff_addremove(int addremove, unsig\n \t\t const char *base, const char *path)\n {\n \tchar concatpath[PATH_MAX];\n-\tstruct diff_spec spec[2], *one, *two;\n+\tstruct diff_filespec *one, *two;\n \n+\t/* This may look odd, but it is a preparation for\n+\t * feeding \"there are unchanged files which should\n+\t * not produce diffs, but when you are doing copy\n+\t * detection you would need them, so here they are\"\n+\t * entries to the diff-core. They will be prefixed\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() should\n+\t * also have the same effect. diff_flush() should\n+\t * filter the identical ones out at the final output\n+\t * stage.\n+\t */\n \tif (reverse_diff)\n-\t\taddremove = (addremove == '+' ? '-' : '+');\n-\n-\tif (0 <= diff_raw_output) {\n-\t\tif (!path)\n-\t\t\tpath = \"\";\n-\t\tprintf(\"%c%06o %s %s %s%s%c\",\n-\t\t addremove,\n-\t\t mode,\n-\t\t git_object_type(mode), sha1_to_hex(sha1),\n-\t\t base, path, diff_raw_output);\n-\t\treturn;\n-\t}\n-\tif (S_ISDIR(mode))\n-\t\treturn;\n+\t\taddremove = (addremove == '+' ? '-' :\n+\t\t\t addremove == '-' ? '+' : addremove);\n \n-\tmemcpy(spec[0].blob_sha1, sha1, 20);\n-\tspec[0].mode = mode;\n-\tspec[0].sha1_valid = !!memcmp(sha1, null_sha1, 20);\n-\tspec[0].file_valid = 1;\n-\tspec[1].file_valid = 0;\n-\n-\tif (addremove == '+') {\n-\t\tone = spec + 1; two = spec;\n-\t} else {\n-\t\tone = spec; two = one + 1;\n-\t}\n+\tif (!path) path = \"\";\n+\tsprintf(concatpath, \"%s%s\", base, path);\n+\tone = alloc_filespec(concatpath);\n+\ttwo = alloc_filespec(concatpath);\n+\n+\tif (addremove != '+')\n+\t\tfill_filespec(one, sha1, mode);\n+\tif (addremove != '-')\n+\t\tfill_filespec(two, sha1, mode);\n \n-\tif (path) {\n-\t\tstrcpy(concatpath, base);\n-\t\tstrcat(concatpath, path);\n-\t}\n-\thold_diff(path ? concatpath : base, one, two);\n+\tdiff_queue(&queued_diff, one, two);\n }\n \n void diff_change(unsigned old_mode, unsigned new_mode,\n@@ -796,7 +696,7 @@ void diff_change(unsigned old_mode, unsi\n \t\t const unsigned char *new_sha1,\n \t\t const char *base, const char *path) {\n \tchar concatpath[PATH_MAX];\n-\tstruct diff_spec spec[2];\n+\tstruct diff_filespec *one, *two;\n \n \tif (reverse_diff) {\n \t\tunsigned tmp;\n@@ -804,41 +704,14 @@ void diff_change(unsigned old_mode, unsi\n \t\ttmp = old_mode; old_mode = new_mode; new_mode = tmp;\n \t\ttmp_c = old_sha1; old_sha1 = new_sha1; new_sha1 = tmp_c;\n \t}\n+\tif (!path) path = \"\";\n+\tsprintf(concatpath, \"%s%s\", base, path);\n+\tone = alloc_filespec(concatpath);\n+\ttwo = alloc_filespec(concatpath);\n+\tfill_filespec(one, old_sha1, old_mode);\n+\tfill_filespec(two, new_sha1, new_mode);\n \n-\tif (0 <= diff_raw_output) {\n-\t\tchar old_hex[41];\n-\t\tstrcpy(old_hex, sha1_to_hex(old_sha1));\n-\n-\t\tif (!path)\n-\t\t\tpath = \"\";\n-\t\tprintf(\"*%06o->%06o %s %s->%s %s%s%c\",\n-\t\t old_mode, new_mode,\n-\t\t git_object_type(new_mode),\n-\t\t old_hex, sha1_to_hex(new_sha1),\n-\t\t base, path, diff_raw_output);\n-\t\treturn;\n-\t}\n-\tif (S_ISDIR(new_mode))\n-\t\treturn;\n-\n-\tif (path) {\n-\t\tstrcpy(concatpath, base);\n-\t\tstrcat(concatpath, path);\n-\t}\n-\n-\tmemcpy(spec[0].blob_sha1, old_sha1, 20);\n-\tspec[0].mode = old_mode;\n-\tmemcpy(spec[1].blob_sha1, new_sha1, 20);\n-\tspec[1].mode = new_mode;\n-\tspec[0].sha1_valid = !!memcmp(old_sha1, null_sha1, 20);\n-\tspec[1].sha1_valid = !!memcmp(new_sha1, null_sha1, 20);\n-\tspec[1].file_valid = spec[0].file_valid = 1;\n-\n-\t/* We do not look at changed files as candidate for\n-\t * rename detection ever.\n-\t */\n-\trun_external_diff(path ? concatpath : base, NULL,\n-\t\t\t &spec[0], &spec[1], -1);\n+\tdiff_queue(&queued_diff, one, two);\n }\n \n void diff_unmerge(const char *path)\n@@ -847,5 +720,5 @@ void diff_unmerge(const char *path)\n \t\tprintf(\"U %s%c\", path, diff_raw_output);\n \t\treturn;\n \t}\n-\trun_external_diff(path, NULL, NULL, NULL, -1);\n+\trun_external_diff(path, NULL, NULL, NULL, NULL);\n }\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nnew file mode 100644\n--- /dev/null\n+++ b/diffcore-rename.c\n@@ -0,0 +1,443 @@\n+/*\n+ * Copyright (C) 2005 Junio C Hamano\n+ */\n+#include \"cache.h\"\n+#include \"diff.h\"\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+\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; /* rename/copy patch for tree does not make sense. */\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+\t}\n+\tpool->s[pool->nr] = s;\n+\tpool->nr++;\n+}\n+\n+static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst)\n+{\n+\tif (src->sha1_valid && dst->sha1_valid &&\n+\t !memcmp(src->sha1, dst->sha1, 20))\n+\t\treturn 1;\n+\tif (diff_populate_filespec(src) || diff_populate_filespec(dst))\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 1;\n+\treturn 0;\n+}\n+\n+struct diff_score {\n+\tstruct diff_filespec *src;\n+\tstruct diff_filespec *dst;\n+\tint score;\n+\tint rank;\n+};\n+\n+static int estimate_similarity(struct diff_filespec *src,\n+\t\t\t struct diff_filespec *dst,\n+\t\t\t int minimum_score)\n+{\n+\t/* src points at a file that existed in the original tree (or\n+\t * optionally a file in the destination tree) and dst points\n+\t * at a newly created file. They may be quite similar, in which\n+\t * case we want to say src is renamed to dst or src is copied into\n+\t * dst, and then some edit has been applied to dst.\n+\t *\n+\t * Compare them and return how similar they are, representing\n+\t * the score as an integer between 0 and 10000, except\n+\t * where they match exactly it is considered better than anything\n+\t * else.\n+\t */\n+\tvoid *delta;\n+\tunsigned long delta_size;\n+\tint score;\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 * minimum_score/MAX_SCORE edits; that is, delta_size must be smaller\n+\t * than (src->size + dst->size)/2 * minimum_score/MAX_SCORE,\n+\t * which means...\n+\t */\n+\n+\tif ((src->size+dst->size)*minimum_score < delta_size*MAX_SCORE*2)\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 *\n+\t * Now we will give some score to it. 100% edit gets\n+\t * 0 points and 0% edit gets MAX_SCORE points. That is, every\n+\t * 1/MAX_SCORE edit gets 1 point penalty. The amount of penalty is:\n+\t *\n+\t * (delta_size * 2 / (src->size + dst->size)) * MAX_SCORE\n+\t *\n+\t */\n+\tscore = MAX_SCORE-(MAX_SCORE*2*delta_size/(src->size+dst->size));\n+\tif (score < 0) return 0;\n+\tif (MAX_SCORE < score) return MAX_SCORE;\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+{\n+\t/* The rank is used to sort the final output, because there\n+\t * are certain dependencies.\n+\t *\n+\t * - rank #0 depends on deleted ones.\n+\t * - rank #1 depends on kept files before they are modified.\n+\t * - rank #2 depends on kept files after they are modified;\n+\t * currently not used.\n+\t *\n+\t * Therefore, the final output order should be:\n+\t *\n+\t * 1. rank #0 rename/copy diffs.\n+\t * 2. deletions in the original.\n+\t * 3. rank #1 rename/copy diffs.\n+\t * 4. additions and modifications in the original.\n+\t * 5. rank #2 rename/copy diffs; currently not used.\n+\t *\n+\t * To achieve this sort order, we give xform_work the number\n+\t * above.\n+\t */\n+\tstruct diff_file_pair *dp = diff_queue(outq, src, dst);\n+\tdp->xfrm_work = (rank * 2 + 1) | (score<xfrm_flags |= RENAME_DST_MATCHED;\n+}\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\ts->file_valid ? \"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+static void debug_filepair(const struct diff_file_pair *p, int i)\n+{\n+\tdebug_filespec(p->one, i, \"one\");\n+\tdebug_filespec(p->two, i, \"two\");\n+\tfprintf(stderr, \"pair flags %d, orig order %d, score %d\\n\",\n+\t\t(p->xfrm_work & ((1<orig_order,\n+\t\t(p->xfrm_work >> RENAME_SCORE_SHIFT));\n+}\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_file_pair *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+\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_file_pair *a = *(const struct diff_file_pair **)a_;\n+\tconst struct diff_file_pair *b = *(const struct diff_file_pair **)b_;\n+\tint a_rank = a->xfrm_work & ((1<xfrm_work & ((1<orig_order - b->orig_order;\n+}\n+\n+/*\n+ * We sort the rename similarity matrix with the score, in descending\n+ * order (more similar first).\n+ */\n+static int score_compare(const void *a_, const void *b_)\n+{\n+\tconst struct diff_score *a = a_, *b = b_;\n+\treturn b->score - a->score;\n+}\n+\n+static int needs_to_stay(struct diff_queue_struct *q, int i,\n+\t\t\t struct diff_filespec *it)\n+{\n+\t/* If it will be used in later entry (either stay or used\n+\t * as the source of rename/copy), we need to copy, not rename.\n+\t */\n+\twhile (i < q->nr) {\n+\t\tstruct diff_file_pair *p = q->queue[i++];\n+\t\tif (!p->two->file_valid)\n+\t\t\tcontinue; /* removed is fine */\n+\t\tif (strcmp(p->one->path, it->path))\n+\t\t\tcontinue; /* not relevant */\n+\n+\t\t/* p has its src set to *it and it is not a delete;\n+\t\t * it will be used for in-place change or rename/copy,\n+\t\t * so we cannot rename it out.\n+\t\t */\n+\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+void diff_detect_rename(struct diff_queue_struct *q,\n+\t\t\tint detect_rename,\n+\t\t\tint minimum_score)\n+{\n+\tstruct diff_queue_struct outq;\n+\tstruct diff_rename_pool created, deleted, stay;\n+\tstruct diff_rename_pool *(srcs[2]);\n+\tstruct diff_score *mx;\n+\tint h, i, j;\n+\tint num_create, num_src, dst_cnt, src_cnt;\n+\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+\n+\t/* NEEDSWORK:\n+\t * (1) make sure we properly ignore but pass trees.\n+\t *\n+\t * (2) make sure we do right thing on the same path deleted\n+\t * and created in the same patch.\n+\t */\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_file_pair *p = q->queue[i];\n+\t\tif (!p->one->file_valid)\n+\t\t\tif (!p->two->file_valid)\n+\t\t\t\tcontinue; /* ignore nonsense */\n+\t\t\telse\n+\t\t\t\tdiff_rename_pool_add(&created, p->two);\n+\t\telse if (!p->two->file_valid)\n+\t\t\tdiff_rename_pool_add(&deleted, p->one);\n+\t\telse if (1 < detect_rename) /* find copy, too */\n+\t\t\tdiff_rename_pool_add(&stay, p->one);\n+\t}\n+\tif (created.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+\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+\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+\t\t}\n+\t}\n+\tdebug_queue(\"done detecting exact\", &outq);\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+\t\tgoto flush_rest;\n+\n+\tnum_create = (created.nr - outq.nr);\n+\tnum_src = deleted.nr + stay.nr;\n+\tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n+\tfor (dst_cnt = i = 0; i < created.nr; i++) {\n+\t\tint base = dst_cnt * num_src;\n+\t\tif (created.s[i]->xfrm_flags & RENAME_DST_MATCHED)\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\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\tif (mx[i].score < minimum_score)\n+\t\t\tcontinue;\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}\n+\tfree(mx);\n+\tdebug_queue(\"done detecting fuzzy\", &outq);\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 *\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+\t * downstream, so we assign the sort keys in this loop.\n+\t *\n+\t * See comments at the top of record_rename_pair for numbers used\n+\t * to assign xfrm_work.\n+\t *\n+\t * Note that we have not annotated the diff_file_pair with any comment\n+\t * so there is nothing other than p to free.\n+\t */\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_file_pair *dp, *p = q->queue[i];\n+\t\tif (!p->one->file_valid) {\n+\t\t\tif (p->two->file_valid) {\n+\t\t\t\t/* creation */\n+\t\t\t\tdp = diff_queue(&outq, p->one, p->two);\n+\t\t\t\tdp->xfrm_work = 4;\n+\t\t\t}\n+\t\t\t/* otherwise it is a nonsense; just ignore it */\n+\t\t}\n+\t\telse if (!p->two->file_valid) {\n+\t\t\t/* deletion */\n+\t\t\tdp = diff_queue(&outq, p->one, p->two);\n+\t\t\tdp->xfrm_work = 2;\n+\t\t}\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->xfrm_work = 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_file_pair *p = outq.queue[i];\n+\t\tif (!p->one->file_valid) {\n+\t\t\t/* created */\n+\t\t\tif (p->two->xfrm_flags & RENAME_DST_MATCHED)\n+\t\t\t\t; /* rename/copy created it already */\n+\t\t\telse\n+\t\t\t\tdiff_queue(q, p->one, p->two);\n+\t\t}\n+\t\telse if (!p->two->file_valid) {\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}\n+\t\telse if (strcmp(p->one->path, p->two->path)) {\n+\t\t\t/* rename or copy */\n+\t\t\tstruct diff_file_pair *dp =\n+\t\t\t\tdiff_queue(q, p->one, p->two);\n+\t\t\tint msglen = (strlen(p->one->path) +\n+\t\t\t\t strlen(p->two->path) + 100);\n+\t\t\tint score = (p->xfrm_work >> RENAME_SCORE_SHIFT);\n+\t\t\tdp->xfrm_msg = xmalloc(msglen);\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 (needs_to_stay(&outq, i+1, p->one)) {\n+\t\t\t\t/* copy it */\n+\t\t\t\tsprintf(dp->xfrm_msg,\n+\t\t\t\t\t\"similarity index %d%%\\n\"\n+\t\t\t\t\t\"copy from %s\\n\"\n+\t\t\t\t\t\"copy to %s\\n\",\n+\t\t\t\t\t(int)(0.5 + score * 100 / MAX_SCORE),\n+\t\t\t\t\tp->one->path, p->two->path);\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\t/* rename it, and mark it as gone. */\n+\t\t\t\tp->one->xfrm_flags |= RENAME_SRC_GONE;\n+\t\t\t\tsprintf(dp->xfrm_msg,\n+\t\t\t\t\t\"similarity index %d%%\\n\"\n+\t\t\t\t\t\"rename old %s\\n\"\n+\t\t\t\t\t\"rename new %s\\n\",\n+\t\t\t\t\t(int)(0.5 + score * 100 / MAX_SCORE),\n+\t\t\t\t\tp->one->path, p->two->path);\n+\t\t\t}\n+\t\t}\n+\t\telse\n+\t\t\t/* otherwise it is a modified (or stayed) entry */\n+\t\t\tdiff_queue(q, p->one, p->two);\n+\t\tfree(p);\n+\t}\n+\n+\tfree(outq.queue);\n+\tdebug_queue(\"done collapsing\", q);\n+\n+ cleanup:\n+\tfree(created.s);\n+\tfree(deleted.s);\n+\tfree(stay.s);\n+\treturn;\n+}\ndiff --git a/diffcore.h b/diffcore.h\nnew file mode 100644\n--- /dev/null\n+++ b/diffcore.h\n@@ -0,0 +1,60 @@\n+/*\n+ * Copyright (C) 2005 Junio C Hamano\n+ */\n+#ifndef _DIFFCORE_H_\n+#define _DIFFCORE_H_\n+\n+/* This header file is internal between diff.c and its diff transformers\n+ * (e.g. diffcore-rename, diffcore-pickaxe). Never include this header\n+ * in anything else.\n+ */\n+#define MAX_SCORE 10000\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];\n+\tchar *path;\n+\tvoid *data;\n+\tunsigned long size;\n+\tint xfrm_flags;\t\t /* for use by the xfrm */\n+\tunsigned short mode;\t /* file mode */\n+\tunsigned sha1_valid : 1; /* if true, use sha1 and trust mode;\n+\t\t\t\t * if false, use the name and read from\n+\t\t\t\t * the filesystem.\n+\t\t\t\t */\n+\tunsigned file_valid : 1; /* if false the file does not exist */\n+\tunsigned should_free : 1; /* data should be free()'ed */\n+\tunsigned should_munmap : 1; /* data should be munmap()'ed */\n+};\n+\n+extern struct diff_filespec *alloc_filespec(const char *);\n+extern void fill_filespec(struct diff_filespec *, const unsigned char *,\n+\t\t\t unsigned short);\n+\n+extern int diff_populate_filespec(struct diff_filespec *);\n+extern void diff_free_filespec_data(struct diff_filespec *);\n+\n+struct diff_file_pair {\n+\tstruct diff_filespec *one;\n+\tstruct diff_filespec *two;\n+\tchar *xfrm_msg;\n+\tint orig_order; /* the original order of insertion into the queue */\n+\tint xfrm_work; /* for use by tramsformers, not by diffcore */\n+};\n+\n+struct diff_queue_struct {\n+\tstruct diff_file_pair **queue;\n+\tint alloc;\n+\tint nr;\n+};\n+\n+extern struct diff_file_pair *diff_queue(struct diff_queue_struct *,\n+\t\t\t\t\t struct diff_filespec *,\n+\t\t\t\t\t struct diff_filespec *);\n+extern void diff_detect_rename(struct diff_queue_struct *, int, int);\n+\n+#endif\ndiff --git a/git-apply-patch-script b/git-apply-patch-script\n--- a/git-apply-patch-script\n+++ b/git-apply-patch-script\n@@ -11,7 +11,7 @@ case \"$#\" in\n 1)\n echo >&2 \"cannot handle unmerged diff on path $1.\"\n exit 1 ;;\n-8)\n+8 | 9)\n echo >&2 \"cannot handle rename diff between $1 and $8 yet.\"\n exit 1 ;;\n esac\ndiff --git a/t/t0000-basic.sh b/t/t0000-basic.sh\n--- a/t/t0000-basic.sh\n+++ b/t/t0000-basic.sh\n@@ -32,7 +32,7 @@ test_expect_success \\\n find .git/objects -type d -print >full-of-directories\n test_expect_success \\\n '.git/objects should have 256 subdirectories.' \\\n- 'test \"$(wc -l full-of-directories | sed -e \"s/ .*//\")\" = 257'\n+ 'test $(cat full-of-directories | wc -l) = 257'\n \n ################################################################\n # Basics of the basics\ndiff --git a/t/t4001-diff-rename.sh b/t/t4001-diff-rename.sh\n--- a/t/t4001-diff-rename.sh\n+++ b/t/t4001-diff-rename.sh\n@@ -31,7 +31,7 @@ test_expect_success \\\n \n test_expect_success \\\n 'write that tree.' \\\n- 'tree=$(git-write-tree)'\n+ 'tree=$(git-write-tree) && echo $tree'\n \n sed -e 's/line/Line/' path1\n rm -f path0\n@@ -61,6 +61,6 @@ EOF\n \n test_expect_success \\\n 'validate the output.' \\\n- 'diff -I \"rename similarity.*\" >/dev/null current expected'\n+ 'diff -I \"similarity.*\" >/dev/null current expected'\n \n test_done\ndiff --git a/t/t4003-diff-rename-1.sh b/t/t4003-diff-rename-1.sh\nnew file mode 100755\n--- /dev/null\n+++ b/t/t4003-diff-rename-1.sh\n@@ -0,0 +1,93 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+\n+test_description='More rename detection\n+\n+'\n+. ./test-lib.sh\n+\n+test_expect_success \\\n+ 'prepare reference tree' \\\n+ 'cat ../../COPYING >COPYING &&\n+ git-update-cache --add COPYING &&\n+ tree=$(git-write-tree) &&\n+ echo $tree'\n+\n+test_expect_success \\\n+ 'prepare work tree' \\\n+ 'sed -e 's/HOWEVER/However/' COPYING.1 &&\n+ sed -e 's/GPL/G.P.L/g' COPYING.2 &&\n+ rm -f COPYING &&\n+ git-update-cache --add --remove COPYING COPYING.?'\n+\n+GIT_DIFF_OPTS=-u0 git-diff-cache -M $tree |\n+sed -e 's/\\([0-9][0-9]*\\)/#/g' >current &&\n+cat >expected <<\\EOF\n+diff --git a/COPYING b/COPYING.#\n+similarity index #%\n+copy from COPYING\n+copy to COPYING.#\n+--- a/COPYING\n++++ b/COPYING.#\n+@@ -# +# @@\n+- HOWEVER, in order to allow a migration to GPLv# if that seems like\n++ However, in order to allow a migration to GPLv# if that seems like\n+diff --git a/COPYING b/COPYING.#\n+similarity index #%\n+rename old COPYING\n+rename new COPYING.#\n+--- a/COPYING\n++++ b/COPYING.#\n+@@ -# +# @@\n+- Note that the only valid version of the GPL as far as this project\n++ Note that the only valid version of the G.P.L as far as this project\n+@@ -# +# @@\n+- HOWEVER, in order to allow a migration to GPLv# if that seems like\n++ HOWEVER, in order to allow a migration to G.P.Lv# if that seems like\n+@@ -# +# @@\n+-\tThis file is licensed under the GPL v#, or a later version\n++\tThis file is licensed under the G.P.L v#, or a later version\n+EOF\n+\n+test_expect_success \\\n+ 'validate output from rename/copy detection' \\\n+ 'diff -u current expected'\n+\n+test_expect_success \\\n+ 'prepare work tree again' \\\n+ 'mv COPYING.2 COPYING &&\n+ git-update-cache --add --remove COPYING COPYING.1'\n+\n+GIT_DIFF_OPTS=-u0 git-diff-cache -C $tree |\n+sed -e 's/\\([0-9][0-9]*\\)/#/g' >current\n+cat >expected <<\\EOF\n+diff --git a/COPYING b/COPYING.#\n+similarity index #%\n+copy from COPYING\n+copy to COPYING.#\n+--- a/COPYING\n++++ b/COPYING.#\n+@@ -# +# @@\n+- HOWEVER, in order to allow a migration to GPLv# if that seems like\n++ However, in order to allow a migration to GPLv# if that seems like\n+diff --git a/COPYING b/COPYING\n+--- a/COPYING\n++++ b/COPYING\n+@@ -# +# @@\n+- Note that the only valid version of the GPL as far as this project\n++ Note that the only valid version of the G.P.L as far as this project\n+@@ -# +# @@\n+- HOWEVER, in order to allow a migration to GPLv# if that seems like\n++ HOWEVER, in order to allow a migration to G.P.Lv# if that seems like\n+@@ -# +# @@\n+-\tThis file is licensed under the GPL v#, or a later version\n++\tThis file is licensed under the G.P.L v#, or a later version\n+EOF\n+\n+test_expect_success \\\n+ 'validate output from rename/copy detection' \\\n+ 'diff -u current expected'\n+\n+test_done\n------------------------------------------------\n\n"},{"id":"3689","messageId":"7voeb4kjda.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vzmuokjhg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 2/3] Introducing software archaeologist's tool \"pickaxe\".","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T09:40:01Z","receivedAt":"2005-05-21T09:40:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This steals the \"pickaxe\" feature from JIT and make it available\nto the bare Plumbing layer. From the command line, the user\ngives a string he is intersted in.\n\nUsing the diff-core infrastructure previously introduced, it\nfilters the differences to limit the output only to the diffs\nbetween and where the string appears only in one but\nnot in the other. For example:\n\n $ ./git-rev-list HEAD | ./git-diff-tree -Sdiff-tree-helper --stdin -M\n\nwould show the diffs that touch the string \"diff-tree-helper\".\n\nIn real software-archaeologist application, you would typically\nlook for a few to several lines of code and see where that code\ncame from.\n\nThe \"pickaxe\" module runs after \"rename/copy detection\" module,\nso it even crosses the file rename boundary, as the above\nexample demonstrates.\n\nSigned-off-by: Junio C Hamano \n---\n\nDocumentation/git-diff-cache.txt | 6 +++-\nDocumentation/git-diff-files.txt | 6 +++-\nDocumentation/git-diff-helper.txt | 6 +++-\nDocumentation/git-diff-tree.txt | 5 ++-\nMakefile | 3 +-\ndiff-cache.c | 11 +++++--\ndiff-files.c | 9 ++++--\ndiff-helper.c | 10 ++++--\ndiff-tree.c | 15 ++++++----\ndiff.c | 23 +++++++++------\ndiff.h | 1 \ndiffcore-pickaxe.c | 56 ++++++++++++++++++++++++++++++++++++++\ndiffcore-rename.c | 29 +++++++------------\ndiffcore.h | 11 ++++---\n14 files changed, 140 insertions(+), 51 deletions(-)\nnew file (100644): diffcore-pickaxe.c\n\ndiff --git a/Documentation/git-diff-cache.txt b/Documentation/git-diff-cache.txt\n--- a/Documentation/git-diff-cache.txt\n+++ b/Documentation/git-diff-cache.txt\n@@ -9,7 +9,7 @@ git-diff-cache - Compares content and mo\n \n SYNOPSIS\n --------\n-'git-diff-cache' [-p] [-r] [-z] [-m] [-M] [-R] [-C] [--cached] \n+'git-diff-cache' [-p] [-r] [-z] [-m] [-M] [-R] [-C] [-S] [--cached] \n \n DESCRIPTION\n -----------\n@@ -39,6 +39,10 @@ OPTIONS\n -C::\n \tDetect copies as well as renames; implies -p.\n \n+-S::\n+\tLook for differences that contains the change in .\n+\n+\n -R::\n \tOutput diff in reverse.\n \ndiff --git a/Documentation/git-diff-files.txt b/Documentation/git-diff-files.txt\n--- a/Documentation/git-diff-files.txt\n+++ b/Documentation/git-diff-files.txt\n@@ -9,7 +9,7 @@ git-diff-files - Compares files in the w\n \n SYNOPSIS\n --------\n-'git-diff-files' [-p] [-q] [-r] [-z] [-M] [-C] [-R] [...]\n+'git-diff-files' [-p] [-q] [-r] [-z] [-M] [-C] [-R] [-S] [...]\n \n DESCRIPTION\n -----------\n@@ -35,6 +35,10 @@ OPTIONS\n -C::\n \tDetect copies as well as renames; implies -p.\n \n+-S::\n+\tLook for differences that contains the change in .\n+\n+\n -r::\n \tThis flag does not mean anything. It is there only to match\n \tgit-diff-tree. Unlike git-diff-tree, git-diff-files always looks\ndiff --git a/Documentation/git-diff-helper.txt b/Documentation/git-diff-helper.txt\n--- a/Documentation/git-diff-helper.txt\n+++ b/Documentation/git-diff-helper.txt\n@@ -9,7 +9,7 @@ git-diff-helper - Generates patch format\n \n SYNOPSIS\n --------\n-'git-diff-helper' [-z] [-R] [-M] [-C]\n+'git-diff-helper' [-z] [-R] [-M] [-C] [-S]\n \n DESCRIPTION\n -----------\n@@ -37,6 +37,10 @@ OPTIONS\n -C::\n \tDetect copies as well as renames.\n \n+-S::\n+\tLook for differences that contains the change in .\n+\n+\n See Also\n --------\n The section on generating patches in link:git-diff-cache.html[git-diff-cache]\ndiff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt\n--- a/Documentation/git-diff-tree.txt\n+++ b/Documentation/git-diff-tree.txt\n@@ -9,7 +9,7 @@ git-diff-tree - Compares the content and\n \n SYNOPSIS\n --------\n-'git-diff-tree' [-p] [-r] [-z] [--stdin] [-M] [-R] [-C] [-m] [-s] [-v] []\\*\n+'git-diff-tree' [-p] [-r] [-z] [--stdin] [-M] [-R] [-C] [-S] [-m] [-s] [-v] []\\*\n \n DESCRIPTION\n -----------\n@@ -43,6 +43,9 @@ OPTIONS\n -R::\n \tOutput diff in reverse.\n \n+-S::\n+\tLook for differences that contains the change in .\n+\n -r::\n \trecurse\n \ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -45,7 +45,7 @@ LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n \n LIB_H += diff.h\n-LIB_OBJS += diff.o diffcore-rename.o\n+LIB_OBJS += diff.o diffcore-rename.o diffcore-pickaxe.o\n \n LIB_OBJS += gitenv.o\n \n@@ -125,6 +125,7 @@ strbuf.o: $(LIB_H)\n gitenv.o: $(LIB_H)\n diff.o: $(LIB_H)\n diffcore-rename.o : $(LIB_H)\n+diffcore-pickaxe.o : $(LIB_H)\n \n test: all\n \tmake -C t/ all\ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -8,6 +8,7 @@ static int line_termination = '\\n';\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n+static char *pickaxe = 0;\n \n /* A file entry went away or appeared */\n static void show_file(const char *prefix, struct cache_entry *ce, unsigned char *sha1, unsigned int mode)\n@@ -153,7 +154,7 @@ static void mark_merge_entries(void)\n }\n \n static char *diff_cache_usage =\n-\"git-diff-cache [-p] [-r] [-z] [-m] [-M] [-C] [-R] [--cached] \";\n+\"git-diff-cache [-p] [-r] [-z] [-m] [-M] [-C] [-R] [-S] [--cached] \";\n \n int main(int argc, char **argv)\n {\n@@ -194,6 +195,10 @@ int main(int argc, char **argv)\n \t\t\treverse_diff = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"-S\")) {\n+\t\t\tpickaxe = arg + 2;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"-m\")) {\n \t\t\tmatch_nonexisting = 1;\n \t\t\tcontinue;\n@@ -208,8 +213,8 @@ int main(int argc, char **argv)\n \tif (argc != 2 || get_sha1(argv[1], tree_sha1))\n \t\tusage(diff_cache_usage);\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse_diff,\n-\t\t (generate_patch ? -1 : line_termination),\n+\tdiff_setup(detect_rename, diff_score_opt, pickaxe,\n+\t\t reverse_diff, (generate_patch ? -1 : line_termination),\n \t\t NULL, 0);\n \n \tmark_merge_entries();\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -7,13 +7,14 @@\n #include \"diff.h\"\n \n static const char *diff_files_usage =\n-\"git-diff-files [-p] [-q] [-r] [-z] [-M] [-C] [-R] [paths...]\";\n+\"git-diff-files [-p] [-q] [-r] [-z] [-M] [-C] [-R] [-S] [paths...]\";\n \n static int generate_patch = 0;\n static int line_termination = '\\n';\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n+static char *pickaxe = 0;\n static int silent = 0;\n \n static int matches_pathspec(struct cache_entry *ce, char **spec, int cnt)\n@@ -67,6 +68,8 @@ int main(int argc, char **argv)\n \t\t\tline_termination = 0;\n \t\telse if (!strcmp(argv[1], \"-R\"))\n \t\t\treverse_diff = 1;\n+\t\telse if (!strcmp(argv[1], \"-S\"))\n+\t\t\tpickaxe = argv[1] + 2;\n \t\telse if (!strncmp(argv[1], \"-M\", 2)) {\n \t\t\tdiff_score_opt = diff_scoreopt_parse(argv[1]);\n \t\t\tdetect_rename = generate_patch = 1;\n@@ -89,8 +92,8 @@ int main(int argc, char **argv)\n \t\texit(1);\n \t}\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse_diff,\n-\t\t (generate_patch ? -1 : line_termination),\n+\tdiff_setup(detect_rename, diff_score_opt, pickaxe,\n+\t\t reverse_diff, (generate_patch ? -1 : line_termination),\n \t\t NULL, 0);\n \n \tfor (i = 0; i < entries; i++) {\ndiff --git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -9,6 +9,7 @@\n static int detect_rename = 0;\n static int diff_score_opt = 0;\n static int generate_patch = 1;\n+static char *pickaxe = 0;\n \n static int parse_oneside_change(const char *cp, int *mode,\n \t\t\t\tunsigned char *sha1, char *path)\n@@ -93,7 +94,7 @@ static int parse_diff_raw_output(const c\n }\n \n static const char *diff_helper_usage =\n-\t\"git-diff-helper [-z] [-R] [-M] [-C] paths...\";\n+\t\"git-diff-helper [-z] [-R] [-M] [-C] [-S] paths...\";\n \n int main(int ac, const char **av) {\n \tstruct strbuf sb;\n@@ -117,14 +118,17 @@ int main(int ac, const char **av) {\n \t\t\tdetect_rename = 2;\n \t\t\tdiff_score_opt = diff_scoreopt_parse(av[1]);\n \t\t}\n+\t\telse if (av[1][1] == 'S') {\n+\t\t\tpickaxe = av[1] + 2;\n+\t\t}\n \t\telse\n \t\t\tusage(diff_helper_usage);\n \t\tac--; av++;\n \t}\n \t/* the remaining parameters are paths patterns */\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse,\n-\t\t (generate_patch ? -1 : line_termination),\n+\tdiff_setup(detect_rename, diff_score_opt, pickaxe,\n+\t\t reverse, (generate_patch ? -1 : line_termination),\n \t\t av+1, ac-1);\n \n \twhile (1) {\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -13,6 +13,7 @@ static int generate_patch = 0;\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n+static char *pickaxe = 0;\n static const char *header = NULL;\n static const char *header_prefix = \"\";\n \n@@ -271,8 +272,8 @@ static int diff_tree_sha1_top(const unsi\n {\n \tint ret;\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse_diff,\n-\t\t (generate_patch ? -1 : line_termination),\n+\tdiff_setup(detect_rename, diff_score_opt, pickaxe,\n+\t\t reverse_diff, (generate_patch ? -1 : line_termination),\n \t\t NULL, 0);\n \tret = diff_tree_sha1(old, new, base);\n \tdiff_flush();\n@@ -285,8 +286,8 @@ static int diff_root_tree(const unsigned\n \tvoid *tree;\n \tunsigned long size;\n \n-\tdiff_setup(detect_rename, diff_score_opt, reverse_diff,\n-\t\t (generate_patch ? -1 : line_termination),\n+\tdiff_setup(detect_rename, diff_score_opt, pickaxe,\n+\t\t reverse_diff, (generate_patch ? -1 : line_termination),\n \t\t NULL, 0);\n \ttree = read_object_with_reference(new, \"tree\", &size, NULL);\n \tif (!tree)\n@@ -430,7 +431,7 @@ static int diff_tree_stdin(char *line)\n }\n \n static char *diff_tree_usage =\n-\"git-diff-tree [-p] [-r] [-z] [--stdin] [-M] [-C] [-R] [-m] [-s] [-v] \";\n+\"git-diff-tree [-p] [-r] [-z] [--stdin] [-M] [-C] [-R] [-S] [-m] [-s] [-v] \";\n \n int main(int argc, char **argv)\n {\n@@ -473,6 +474,10 @@ int main(int argc, char **argv)\n \t\t\trecursive = generate_patch = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strncmp(arg, \"-S\", 2)) {\n+\t\t\tpickaxe = arg + 2;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strncmp(arg, \"-M\", 2)) {\n \t\t\tdetect_rename = recursive = generate_patch = 1;\n \t\t\tdiff_score_opt = diff_scoreopt_parse(arg);\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -17,6 +17,7 @@ static int reverse_diff;\n static int diff_raw_output = -1;\n static const char **pathspec;\n static int speccnt;\n+static const char *pickaxe;\n static int minimum_score;\n \n static const char *external_diff(void)\n@@ -511,8 +512,9 @@ int diff_scoreopt_parse(const char *opt)\n \treturn MAX_SCORE * num / scale;\n }\n \n-void diff_setup(int detect_rename_, int minimum_score_, int reverse_diff_,\n-\t\tint diff_raw_output_,\n+void diff_setup(int detect_rename_, int minimum_score_,\n+\t\tchar *pickaxe_,\n+\t\tint reverse_diff_, int diff_raw_output_,\n \t\tconst char **pathspec_, int speccnt_)\n {\n \tdetect_rename = detect_rename_;\n@@ -521,15 +523,16 @@ void diff_setup(int detect_rename_, int \n \tdiff_raw_output = diff_raw_output_;\n \tspeccnt = speccnt_;\n \tminimum_score = minimum_score_ ? : DEFAULT_MINIMUM_SCORE;\n+\tpickaxe = pickaxe_;\n }\n \n static struct diff_queue_struct queued_diff;\n \n-struct diff_file_pair *diff_queue(struct diff_queue_struct *queue,\n+struct diff_filepair *diff_queue(struct diff_queue_struct *queue,\n \t\t\t\t struct diff_filespec *one,\n \t\t\t\t struct diff_filespec *two)\n {\n-\tstruct diff_file_pair *dp = xmalloc(sizeof(*dp));\n+\tstruct diff_filepair *dp = xmalloc(sizeof(*dp));\n \tdp->one = one;\n \tdp->two = two;\n \tdp->xfrm_msg = 0;\n@@ -549,7 +552,7 @@ static const char *git_object_type(unsig\n \treturn S_ISDIR(mode) ? \"tree\" : \"blob\";\n }\n \n-static void diff_flush_raw(struct diff_file_pair *p)\n+static void diff_flush_raw(struct diff_filepair *p)\n {\n \tstruct diff_filespec *it;\n \tint addremove;\n@@ -583,7 +586,7 @@ static void diff_flush_raw(struct diff_f\n \t sha1_to_hex(it->sha1), it->path, diff_raw_output);\n }\n \n-static void diff_flush_patch(struct diff_file_pair *p)\n+static void diff_flush_patch(struct diff_filepair *p)\n {\n \tconst char *name, *other;\n \n@@ -600,7 +603,7 @@ static int identical(struct diff_filespe\n {\n \t/* This function is written stricter than necessary to support\n \t * the currently implemented transformers, but the idea is to\n-\t * let transformers to produce diff_file_pairs any way they want,\n+\t * let transformers to produce diff_filepairs any way they want,\n \t * and filter and clean them up here before producing the output.\n \t */\n \n@@ -623,7 +626,7 @@ static int identical(struct diff_filespe\n \treturn 0;\n }\n \n-static void diff_flush_one(struct diff_file_pair *p)\n+static void diff_flush_one(struct diff_filepair *p)\n {\n \tif (identical(p->one, p->two))\n \t\treturn;\n@@ -640,11 +643,13 @@ void diff_flush(void)\n \n \tif (detect_rename)\n \t\tdiff_detect_rename(q, detect_rename, minimum_score);\n+\tif (pickaxe)\n+\t\tdiff_pickaxe(q, pickaxe);\n \tfor (i = 0; i < q->nr; i++)\n \t\tdiff_flush_one(q->queue[i]);\n \n \tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_file_pair *p = q->queue[i];\n+\t\tstruct diff_filepair *p = q->queue[i];\n \t\tdiff_free_filespec_data(p->one);\n \t\tdiff_free_filespec_data(p->two);\n \t\tfree(p->xfrm_msg);\ndiff --git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -20,6 +20,7 @@ extern void diff_unmerge(const char *pat\n extern int diff_scoreopt_parse(const char *opt);\n \n extern void diff_setup(int detect_rename, int minimum_score,\n+\t\t char *pickaxe,\n \t\t int reverse, int raw_output,\n \t\t const char **spec, int cnt);\n \ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nnew file mode 100644\n--- /dev/null\n+++ b/diffcore-pickaxe.c\n@@ -0,0 +1,56 @@\n+/*\n+ * Copyright (C) 2005 Junio C Hamano\n+ */\n+#include \"cache.h\"\n+#include \"diff.h\"\n+#include \"diffcore.h\"\n+#include \"delta.h\"\n+\n+static int contains(struct diff_filespec *one,\n+\t\t const char *needle, unsigned long len)\n+{\n+\tunsigned long offset, sz;\n+\tconst char *data;\n+\tif (diff_populate_filespec(one))\n+\t\treturn 0;\n+\tsz = one->size;\n+\tdata = one->data;\n+\tfor (offset = 0; offset + len <= sz; offset++)\n+\t\t if (!strncmp(needle, data + offset, len))\n+\t\t\t return 1;\n+\treturn 0;\n+}\n+\n+void diff_pickaxe(struct diff_queue_struct *q, const char *needle)\n+{\n+\tunsigned long len = strlen(needle);\n+\tint i;\n+\tstruct diff_queue_struct outq;\n+\toutq.queue = NULL;\n+\toutq.nr = outq.alloc = 0;\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tif (!p->one->file_valid) {\n+\t\t\tif (!p->two->file_valid)\n+\t\t\t\tcontinue; /* ignore nonsense */\n+\t\t\t/* created */\n+\t\t\tif (contains(p->two, needle, len))\n+\t\t\t\tdiff_queue(&outq, p->one, p->two);\n+\t\t}\n+\t\telse if (!p->two->file_valid) {\n+\t\t\tif (contains(p->one, needle, len))\n+\t\t\t\tdiff_queue(&outq, p->one, p->two);\n+\t\t}\n+\t\telse if (contains(p->one, needle, len) !=\n+\t\t\t contains(p->two, needle, len))\n+\t\t\tdiff_queue(&outq, p->one, p->two);\n+\t}\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tfree(p);\n+\t}\n+\tfree(q->queue);\n+\t*q = outq;\n+\treturn;\n+}\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -129,7 +129,7 @@ static void record_rename_pair(struct di\n \t * To achieve this sort order, we give xform_work the number\n \t * above.\n \t */\n-\tstruct diff_file_pair *dp = diff_queue(outq, src, dst);\n+\tstruct diff_filepair *dp = diff_queue(outq, src, dst);\n \tdp->xfrm_work = (rank * 2 + 1) | (score<xfrm_flags |= RENAME_DST_MATCHED;\n }\n@@ -148,7 +148,7 @@ static void debug_filespec(struct diff_f\n \t\ts->size, s->xfrm_flags);\n }\n \n-static void debug_filepair(const struct diff_file_pair *p, int i)\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@@ -165,7 +165,7 @@ static void debug_queue(const char *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_file_pair *p = q->queue[i];\n+\t\tstruct diff_filepair *p = q->queue[i];\n \t\tdebug_filepair(p, i);\n \t}\n }\n@@ -180,8 +180,8 @@ static void debug_queue(const char *msg,\n */\n static int rank_compare(const void *a_, const void *b_)\n {\n-\tconst struct diff_file_pair *a = *(const struct diff_file_pair **)a_;\n-\tconst struct diff_file_pair *b = *(const struct diff_file_pair **)b_;\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->xfrm_work & ((1<xfrm_work & ((1<nr) {\n-\t\tstruct diff_file_pair *p = q->queue[i++];\n+\t\tstruct diff_filepair *p = q->queue[i++];\n \t\tif (!p->two->file_valid)\n \t\t\tcontinue; /* removed is fine */\n \t\tif (strcmp(p->one->path, it->path))\n@@ -243,15 +243,8 @@ void diff_detect_rename(struct diff_queu\n \tsrcs[0] = &deleted;\n \tsrcs[1] = &stay;\n \n-\t/* NEEDSWORK:\n-\t * (1) make sure we properly ignore but pass trees.\n-\t *\n-\t * (2) make sure we do right thing on the same path deleted\n-\t * and created in the same patch.\n-\t */\n-\n \tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_file_pair *p = q->queue[i];\n+\t\tstruct diff_filepair *p = q->queue[i];\n \t\tif (!p->one->file_valid)\n \t\t\tif (!p->two->file_valid)\n \t\t\t\tcontinue; /* ignore nonsense */\n@@ -340,11 +333,11 @@ void diff_detect_rename(struct diff_queu\n \t * See comments at the top of record_rename_pair for numbers used\n \t * to assign xfrm_work.\n \t *\n-\t * Note that we have not annotated the diff_file_pair with any comment\n+\t * Note that we have not annotated the diff_filepair with any comment\n \t * so there is nothing other than p to free.\n \t */\n \tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_file_pair *dp, *p = q->queue[i];\n+\t\tstruct diff_filepair *dp, *p = q->queue[i];\n \t\tif (!p->one->file_valid) {\n \t\t\tif (p->two->file_valid) {\n \t\t\t\t/* creation */\n@@ -378,7 +371,7 @@ void diff_detect_rename(struct diff_queu\n \n \t/* Copy it out to q, removing duplicates. */\n \tfor (i = 0; i < outq.nr; i++) {\n-\t\tstruct diff_file_pair *p = outq.queue[i];\n+\t\tstruct diff_filepair *p = outq.queue[i];\n \t\tif (!p->one->file_valid) {\n \t\t\t/* created */\n \t\t\tif (p->two->xfrm_flags & RENAME_DST_MATCHED)\n@@ -395,7 +388,7 @@ void diff_detect_rename(struct diff_queu\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_file_pair *dp =\n+\t\t\tstruct diff_filepair *dp =\n \t\t\t\tdiff_queue(q, p->one, p->two);\n \t\t\tint msglen = (strlen(p->one->path) +\n \t\t\t\t strlen(p->two->path) + 100);\ndiff --git a/diffcore.h b/diffcore.h\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -38,7 +38,7 @@ extern void fill_filespec(struct diff_fi\n extern int diff_populate_filespec(struct diff_filespec *);\n extern void diff_free_filespec_data(struct diff_filespec *);\n \n-struct diff_file_pair {\n+struct diff_filepair {\n \tstruct diff_filespec *one;\n \tstruct diff_filespec *two;\n \tchar *xfrm_msg;\n@@ -47,14 +47,15 @@ struct diff_file_pair {\n };\n \n struct diff_queue_struct {\n-\tstruct diff_file_pair **queue;\n+\tstruct diff_filepair **queue;\n \tint alloc;\n \tint nr;\n };\n \n-extern struct diff_file_pair *diff_queue(struct diff_queue_struct *,\n-\t\t\t\t\t struct diff_filespec *,\n-\t\t\t\t\t struct diff_filespec *);\n+extern struct diff_filepair *diff_queue(struct diff_queue_struct *,\n+\t\t\t\t\tstruct diff_filespec *,\n+\t\t\t\t\tstruct diff_filespec *);\n extern void diff_detect_rename(struct diff_queue_struct *, int, int);\n+extern void diff_pickaxe(struct diff_queue_struct *, const char *);\n \n #endif\n------------------------------------------------\n\n"},{"id":"3690","messageId":"7vfywgkj90.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vzmuokjhg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 3/3] Diff overhaul, adding the other half of copy detection.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T09:42:35Z","receivedAt":"2005-05-21T09:42:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This patch extends diff-cache and diff-files to report the\nunmodified files to diff-core as well when -C (copy detection)\nis in effect, so that the unmodified files can also be used as\nthe source candidates. The existing test t4003 has been\nextended to cover this case.\n\nSigned-off-by: Junio C Hamano \n---\n\ndiff-cache.c | 3 ++-\ndiff-files.c | 2 +-\nt/t4003-diff-rename-1.sh | 38 +++++++++++++++++++++++++++++++++++++-\n3 files changed, 40 insertions(+), 3 deletions(-)\n\ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -71,7 +71,8 @@ static int show_modified(struct cache_en\n \t}\n \n \toldmode = old->ce_mode;\n-\tif (mode == oldmode && !memcmp(sha1, old->sha1, 20))\n+\tif (mode == oldmode && !memcmp(sha1, old->sha1, 20) &&\n+\t detect_rename < 2)\n \t\treturn 0;\n \n \tmode = ntohl(mode);\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -126,7 +126,7 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \t\tchanged = ce_match_stat(ce, &st);\n-\t\tif (!changed)\n+\t\tif (!changed && detect_rename < 2)\n \t\t\tcontinue;\n \n \t\toldmode = ntohl(ce->ce_mode);\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@@ -22,6 +22,10 @@ test_expect_success \\\n rm -f COPYING &&\n git-update-cache --add --remove COPYING COPYING.?'\n \n+# tree has COPYING. work tree has COPYING.1 and COPYING.2,\n+# both are slightly edited. So we say you copy-and-edit one,\n+# and rename-and-edit the other.\n+\n GIT_DIFF_OPTS=-u0 git-diff-cache -M $tree |\n sed -e 's/\\([0-9][0-9]*\\)/#/g' >current &&\n cat >expected <<\\EOF\n@@ -58,7 +62,11 @@ test_expect_success \\\n test_expect_success \\\n 'prepare work tree again' \\\n 'mv COPYING.2 COPYING &&\n- git-update-cache --add --remove COPYING COPYING.1'\n+ git-update-cache --add --remove COPYING COPYING.1 COPYING.2'\n+\n+# tree has COPYING. work tree has COPYING and COPYING.1,\n+# both are slightly edited. So we say you edited one,\n+# and copy-and-edit the other.\n \n GIT_DIFF_OPTS=-u0 git-diff-cache -C $tree |\n sed -e 's/\\([0-9][0-9]*\\)/#/g' >current\n@@ -90,4 +98,32 @@ test_expect_success \\\n 'validate output from rename/copy detection' \\\n 'diff -u current expected'\n \n+test_expect_success \\\n+ 'prepare work tree once again' \\\n+ 'cat ../../COPYING >COPYING &&\n+ git-update-cache --add --remove COPYING COPYING.1'\n+\n+# tree has COPYING. work tree has the same COPYING and COPYING.1,\n+# but COPYING is not edited. We say you copy-and-edit COPYING.1;\n+# this is only possible because -C mode now reports the unmodified\n+# file to the diff-core.\n+\n+GIT_DIFF_OPTS=-u0 git-diff-cache -C $tree |\n+sed -e 's/\\([0-9][0-9]*\\)/#/g' >current\n+cat >expected <<\\EOF\n+diff --git a/COPYING b/COPYING.#\n+similarity index #%\n+copy from COPYING\n+copy to COPYING.#\n+--- a/COPYING\n++++ b/COPYING.#\n+@@ -# +# @@\n+- HOWEVER, in order to allow a migration to GPLv# if that seems like\n++ However, in order to allow a migration to GPLv# if that seems like\n+EOF\n+\n+test_expect_success \\\n+ 'validate output from rename/copy detection' \\\n+ 'diff -u current expected'\n+\n test_done\n------------------------------------------------\n\n"},{"id":"3691","messageId":"7vpsvkj3bu.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vfywgkj90.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Teach diff-tree to report unmodified paths for -C option.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T10:11:49Z","receivedAt":"2005-05-21T10:11:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus, I have a bit of design issue that there is no way for the\ndiff-core layer to affect the behaviour of the caller. It is\nnot too big a problem with others, but for diff-tree the effect\nis prominent.\n\nIf you do this:\n\n ./git-rev-list HEAD | ./git-diff-tree -Sdiff-tree-helper --stdin -M\n\nyou will get many uninteresting headers from git-diff-tree,\nuntil you hit something \"interesting\". What I want to see in\nthis case is probably to omit the header and commit information\ndiff-tree usually gives while \"pickaxe\" filters everything out\n(i.e. nothing interesting to report), and teach diff-tree to do\nthe header thing only when diff-core says there is something\ninteresting. So far I haven't found a good way to do this.\n\nAnother useless comment. For obvious reasons, there is nothing\nwe can do about the diff-helper to add \"the other half of copy\ndetection information\", because what it can tell diff-core is\nlimited to its input, which usually is just differences prepared\nby somebody else, and it cannot know anything about unchanged\nfiles. When I started pushing '-p' flag to diff-tree family, I\nremember that your reaction was neutral to moderately negative\n(\"I'd tolerate, although I think it is redundant and you are not\neven generating diff yourself anyway\" as opposed to \"That's just\ngreat\"). I think now you would thank me for shoving the diff\ninterface into them ;-).\n\nI did not touch diff-tree for full-scale -C option in the last\nseries, but if you want to have it, it is easy.\n\nThis one is untested but it should just work (TM).\n\nSigned-off-by: Junio C Hamano \n---\n# - HEAD: Diff overhaul, adding the other half of copy detection.\n# + (working tree)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -117,7 +117,7 @@ static int compare_tree_entry(void *tree\n \t\tshow_file(\"+\", tree2, size2, base);\n \t\treturn 1;\n \t}\n-\tif (!memcmp(sha1, sha2, 20) && mode1 == mode2)\n+\tif (!memcmp(sha1, sha2, 20) && mode1 == mode2 && detect_rename < 2)\n \t\treturn 0;\n \n \t/*\n\n\n"},{"id":"3693","messageId":"7vll68j1i6.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vpsvkj3bu.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Teach diff-tree to report unmodified paths for -C option.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T10:51:13Z","receivedAt":"2005-05-21T10:51:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JCH\" == Junio C Hamano writes:\n\nJCH> Linus, I have a bit of design issue that...\n\nAnother thing I forgot to mention, even in the documentation.\nCurrently all the diff-tree family says -M and -C imply -p which\nis by itself sensible, because rename-edit and copy-edit cannot\nbe expressed with the diff-raw format (the format only takes one\npath).\n\nOn the other hand, pickaxe is really a diff filter, so it can\nwork with both diff-raw and diff-patch format. Here is my\nfavorite example, in git.pasky aka cogito archive:\n\n ./git-rev-list pasky |\n ./git-diff-tree --stdin -S'static const char *tag_cached = \"\";\n static const char *tag_unmerged = \"\";\n static const char *tag_removed = \"\";'\n\n.....\nffbe1addd5a5b7b7c2f987625a5aa6c1d22e3705 (from 20d37ef67286e5131d2333d7b4662bc70f9d4937)\n20d37ef67286e5131d2333d7b4662bc70f9d4937 (from e78d97723cd77d46d8767a5a27965077249fd080)\n*100644->100644 blob 58b5aee94ee76c9201c580d271fcb6aaf20d421f->a2d8cbb2f8d0090a496177cd38f252786d29c3d6 ls-files.c\ne78d97723cd77d46d8767a5a27965077249fd080 (from cc167ccaeb1adcdc392f9e03ed1225762ea3cf96)\ncc167ccaeb1adcdc392f9e03ed1225762ea3cf96 (from 4df1e7950787197f7cad081b98f9ffe6c4089fc9)\n.....\n\n\n\n"},{"id":"3701","messageId":"Pine.LNX.4.58.0505211016140.2206@ppc970.osdl.org","threadId":"660","inReplyTo":"7vfywgkj90.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half of copy detection.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-21T17:25:06Z","receivedAt":"2005-05-21T17:25:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 21 May 2005, Junio C Hamano wrote:\n>\n> This patch extends diff-cache and diff-files to report the\n> unmodified files to diff-core as well when -C (copy detection)\n> is in effect, so that the unmodified files can also be used as\n> the source candidates. The existing test t4003 has been\n> extended to cover this case.\n\nI love how I can just say \"oh, keep in mind that we might want to..\" and \n24 hours later you did it.\n\nApplied and pushed out, and I enjoyed seeing the output of \n\n\tgit-whatchanged -C\n\nand doing a \"/^copy\" that shows it figuring out (correctly) that \ngit-resolve-script was based on git-pull-script. Very cool.\n\nI'm also somewhat surprised by the fact that it even seems to be usable on\nthe kernel tree:\n\n\tdiff --git a/include/asm-um/archparam-i386.h b/include/asm-um/elf-i386.h\n\tsimilarity index 89%\n\tcopy from include/asm-um/archparam-i386.h\n\tcopy to include/asm-um/elf-i386.h\n\t--- a/include/asm-um/archparam-i386.h\n\t+++ b/include/asm-um/elf-i386.h\n\t...\n\ncool. \n\n\t\t\tLinus\n"},{"id":"3703","messageId":"7vzmuoh2ma.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211016140.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T18:10:05Z","receivedAt":"2005-05-21T18:10:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> I love how I can just say \"oh, keep in mind that we might\nLT> want to..\" and 24 hours later you did it.\n\nNah, it's more like 40 hours, but yes I am here to serve your\nwishes ;-).\n\nLT> I'm also somewhat surprised by the fact that it even seems\nLT> to be usable on the kernel tree:\n\nSurprised? Correctness-wise and/or performance-wise?\n\n"},{"id":"3704","messageId":"Pine.LNX.4.58.0505211124440.2206@ppc970.osdl.org","threadId":"660","inReplyTo":"7vzmuoh2ma.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-21T18:27:23Z","receivedAt":"2005-05-21T18:27:23Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 21 May 2005, Junio C Hamano wrote:\n> \n> LT> I'm also somewhat surprised by the fact that it even seems\n> LT> to be usable on the kernel tree:\n> \n> Surprised? Correctness-wise and/or performance-wise?\n\nPerformance-wise. It seems to be quite usable, even doing just a plain\n\"git-whatchanged -C\" on the kernel with no limits on what it does.\n\nNow, all of the actual test-cases I looked at were actually parts of\npatches where the source file _had_ been modified, so I didn't see a case\nwhere it selected any of the random 17,000 files that were _not_ modified,\nand I didn't double-check further than your commit message saying that it \nreally does that, so..\n\n\t\tLinus\n"},{"id":"3705","messageId":"Pine.LNX.4.58.0505211128570.2206@ppc970.osdl.org","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211124440.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-21T18:34:03Z","receivedAt":"2005-05-21T18:34:03Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 21 May 2005, Linus Torvalds wrote:\n> \n> Now, all of the actual test-cases I looked at were actually parts of\n> patches where the source file _had_ been modified, so I didn't see a case\n> where it selected any of the random 17,000 files that were _not_ modified,\n> and I didn't double-check further than your commit message saying that it \n> really does that, so..\n\nOh, I decided to double-check, and no, it doesn't actually do a full copy \ncheck for diff-tree. Only for diff-cache and diff-files.\n\nWhich is a sensible default, and I note that you sent a separate email for \ntesting the extreme case. I'll try that out too, just for fun,\n\n\t\tLinus\n"},{"id":"3709","messageId":"Pine.LNX.4.58.0505211137250.2206@ppc970.osdl.org","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211128570.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-21T18:45:30Z","receivedAt":"2005-05-21T18:45:30Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 21 May 2005, Linus Torvalds wrote:\n> \n> Which is a sensible default, and I note that you sent a separate email for \n> testing the extreme case. I'll try that out too, just for fun,\n\nHmm.. It's not working well. Not only does it take a lot of CPU time (do \nan fsck first to make sure you're not seekign the disk all over the \nplace), but it \"finds\" lots of things like this:\n\n\tdiff --git a/drivers/usb/misc/emi62_fw_m.h b/drivers/media/dvb/bt8xx/dst_ca.h\n\tsimilarity index 99%\n\tcopy from drivers/usb/misc/emi62_fw_m.h\n\tcopy to drivers/media/dvb/bt8xx/dst_ca.h\n\t--- a/drivers/usb/misc/emi62_fw_m.h\n\t+++ b/drivers/media/dvb/bt8xx/dst_ca.h\n\t@@ -1,8853 +1,58 @@\n\t /*\n\t- * This file is generated from three different files, provided by Emagic.\n\t- */\n\t-/* generated Tue Jun 3 21:36:11 EEST 2003 */\n\t+ CA-driver for TwinHan DST Frontend/Card\n \nwhich looks quite bogus (it they aren't similar at all, and the diff is \nhuge).\n\nI think that your similarity check has a tendency to do bad things if one \nof the files is huge: in this case we have\n\n\ttorvalds@ppc970:~/v2.6/linux> wc -c drivers/media/dvb/bt8xx/dst_ca.h drivers/usb/misc/emi62_fw_m.h\n\t 1591 drivers/media/dvb/bt8xx/dst_ca.h\n\t795679 drivers/usb/misc/emi62_fw_m.h\n\t797270 total\n\nand you consider them \"similar\", probably because it turns out that \na delta that just removes everything is very small (it's just a \"delete \nbytes x-y\") so you compare that \"small\" delta to a \"large total file\" and \nyou think it's an almost perfect match.\n\nNow, for _renames_ that is actually half-way the right thing to do, but \nfor copies, you should compare the size not to the _sum_ of the two files, \nbut to just the size of the file that you generate.\n\nBut it's a fun example ;)\n\n\t\tLinus\n"},{"id":"3714","messageId":"7vvf5cgxsx.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211124440.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T19:54:06Z","receivedAt":"2005-05-21T19:54:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> On Sat, 21 May 2005, Junio C Hamano wrote:\n>> \nLT> I'm also somewhat surprised by the fact that it even seems\nLT> to be usable on the kernel tree:\n>> \n>> Surprised? Correctness-wise and/or performance-wise?\n\nLT> Performance-wise. It seems to be quite usable, even doing just a plain\nLT> \"git-whatchanged -C\" on the kernel with no limits on what it does.\n\nThat is probably because you do not have the feeding of \"same\"\nin diff-tree.\n\n\n"},{"id":"3716","messageId":"7vk6lsgx1p.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211137250.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T20:10:26Z","receivedAt":"2005-05-21T20:10:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> Hmm.. It's not working well. Not only does it take a lot of\nLT> CPU time...\n\nLT> \ttorvalds@ppc970:~/v2.6/linux> wc -c drivers/media/dvb/bt8xx/dst_ca.h drivers/usb/misc/emi62_fw_m.h\nLT> \t 1591 drivers/media/dvb/bt8xx/dst_ca.h\nLT> \t795679 drivers/usb/misc/emi62_fw_m.h\nLT> \t797270 total\n\nYup. diffcore-rename bases the similarity index on the average\nof src and dst files. Maybe the similarity check should also\nsay they should be comparable size, like this upfront before\neven going into delta:\n\n abs(src-dst) < avg(src,dst) * (1 - minscore/maxscore)\n\n"},{"id":"3723","messageId":"7v1x80gruc.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7voeb4kjda.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Constness fix for pickaxe option.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T22:02:51Z","receivedAt":"2005-05-21T22:02:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Constness fix for pickaxe option.\n\nSigned-off-by: Junio C Hamano \n---\n\ndiff-cache.c | 2 +-\ndiff-files.c | 2 +-\ndiff-helper.c | 2 +-\ndiff-tree.c | 2 +-\ndiff.c | 2 +-\ndiff.h | 2 +-\n6 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/diff-cache.c b/diff-cache.c\n--- a/diff-cache.c\n+++ b/diff-cache.c\n@@ -8,7 +8,7 @@ static int line_termination = '\\n';\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n-static char *pickaxe = 0;\n+static const char *pickaxe = 0;\n \n /* A file entry went away or appeared */\n static void show_file(const char *prefix, struct cache_entry *ce, unsigned char *sha1, unsigned int mode)\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -14,7 +14,7 @@ static int line_termination = '\\n';\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n-static char *pickaxe = 0;\n+static const char *pickaxe = 0;\n static int silent = 0;\n \n static int matches_pathspec(struct cache_entry *ce, char **spec, int cnt)\ndiff --git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -9,7 +9,7 @@\n static int detect_rename = 0;\n static int diff_score_opt = 0;\n static int generate_patch = 1;\n-static char *pickaxe = 0;\n+static const char *pickaxe = 0;\n \n static int parse_oneside_change(const char *cp, int *mode,\n \t\t\t\tunsigned char *sha1, char *path)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -13,7 +13,7 @@ static int generate_patch = 0;\n static int detect_rename = 0;\n static int reverse_diff = 0;\n static int diff_score_opt = 0;\n-static char *pickaxe = 0;\n+static const char *pickaxe = 0;\n static const char *header = NULL;\n static const char *header_prefix = \"\";\n \ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -513,7 +513,7 @@ int diff_scoreopt_parse(const char *opt)\n }\n \n void diff_setup(int detect_rename_, int minimum_score_,\n-\t\tchar *pickaxe_,\n+\t\tconst char *pickaxe_,\n \t\tint reverse_diff_, int diff_raw_output_,\n \t\tconst char **pathspec_, int speccnt_)\n {\ndiff --git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -20,7 +20,7 @@ extern void diff_unmerge(const char *pat\n extern int diff_scoreopt_parse(const char *opt);\n \n extern void diff_setup(int detect_rename, int minimum_score,\n-\t\t char *pickaxe,\n+\t\t const char *pickaxe,\n \t\t int reverse, int raw_output,\n \t\t const char **spec, int cnt);\n \n------------------------------------------------\n\n"},{"id":"3725","messageId":"Pine.LNX.4.58.0505211514360.2206@ppc970.osdl.org","threadId":"660","inReplyTo":"7v1x80gruc.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Constness fix for pickaxe option.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-21T22:16:02Z","receivedAt":"2005-05-21T22:16:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 21 May 2005, Junio C Hamano wrote:\n>\n> Constness fix for pickaxe option.\n\nBtw, this:\n\n\tstatic const char *pickaxe = 0;\n\nmay be legal C, but that doesn't make it less crap.\n\nIt's a pointer. If you want to make it a NULL pointer, make it a NULL \npointer:\n\n\tstatic const char *pickaxe = NULL;\n\nand don't try to stuff an integer into a pointer. Yeah, yeah, the integer \nzero is magic and special, but that's a bug in the C language, and we \nshould try to not perpetuate it.\n\n\t\tLinus\n"},{"id":"3727","messageId":"7v7jhsfauh.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7vfywgkj90.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Tweak diffcore-rename heuristics.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T22:55:18Z","receivedAt":"2005-05-21T22:55:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The heuristics so far was to compare file size change and xdelta\nsize against the average of file size before and after the\nchange. This patch uses the smaller of pre- and post- change\nfile size instead.\n\nIt also makes a very small performance fix. I didn't measure\nit; I do not expect it to make any practical difference, but\nwhile scanning an already sorted list, breaking out in the\nmiddle is the right thing.\n\nSigned-off-by: Junio C Hamano \n---\n\ndiffcore-rename.c | 38 ++++++++++++++++++++------------------\n1 files changed, 20 insertions(+), 18 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -68,37 +68,39 @@ static int estimate_similarity(struct di\n \t * else.\n \t */\n \tvoid *delta;\n-\tunsigned long delta_size;\n+\tunsigned long delta_size, base_size;\n \tint score;\n \n \tdelta_size = ((src->size < dst->size) ?\n \t\t (dst->size - src->size) : (src->size - dst->size));\n+\tbase_size = ((src->size < dst->size) ? src->size : dst->size);\n \n-\t/* We would not consider rename followed by more than\n-\t * minimum_score/MAX_SCORE edits; that is, delta_size must be smaller\n-\t * than (src->size + dst->size)/2 * minimum_score/MAX_SCORE,\n-\t * which means...\n+\t/* We would not consider edits that change the file size so\n+\t * drastically. delta_size must be smaller than\n+\t * minimum_score/MAX_SCORE * min(src->size, dst->size).\n+\t * Note that base_size == 0 case is handled here already\n+\t * and the final score computation below would not have a\n+\t * divide-by-zero issue.\n \t */\n-\n-\tif ((src->size+dst->size)*minimum_score < delta_size*MAX_SCORE*2)\n+\tif (base_size * minimum_score < delta_size * MAX_SCORE)\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+\t/*\n+\t * We currently punt here, but we may later end up parsing the\n+\t * delta to really assess the extent of damage. A big consecutive\n+\t * remove would produce small delta_size that affects quite a\n+\t * big portion of the file.\n+\t */\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 *\n-\t * Now we will give some score to it. 100% edit gets\n-\t * 0 points and 0% edit gets MAX_SCORE points. That is, every\n-\t * 1/MAX_SCORE edit gets 1 point penalty. The amount of penalty is:\n-\t *\n-\t * (delta_size * 2 / (src->size + dst->size)) * MAX_SCORE\n-\t *\n+\t/*\n+\t * Now we will give some score to it. 100% edit gets 0 points\n+\t * and 0% edit gets MAX_SCORE points.\n \t */\n-\tscore = MAX_SCORE-(MAX_SCORE*2*delta_size/(src->size+dst->size));\n+\tscore = MAX_SCORE - (MAX_SCORE * delta_size / base_size); \n \tif (score < 0) return 0;\n \tif (MAX_SCORE < score) return MAX_SCORE;\n \treturn score;\n@@ -314,7 +316,7 @@ void diff_detect_rename(struct diff_queu\n \t\tif (mx[i].dst->xfrm_flags & RENAME_DST_MATCHED)\n \t\t\tcontinue; /* alreayd done, either exact or fuzzy. */\n \t\tif (mx[i].score < minimum_score)\n-\t\t\tcontinue;\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------------------------------------------------\n\n"},{"id":"3795","messageId":"7vmzqm77wl.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"7v4qcwihu1.fsf@assigned-by-dhcp.cox.net","subject":"Now I think I am done with diff...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-23T06:50:34Z","receivedAt":"2005-05-23T06:50:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"I\" == Junio C Hamano said:\n\nJCH> Now I think I am done with diff,...\n\nI think I have fixed the diff-raw output routine enough to\naddress the rename and copy distinction issues (although I chose\nnot to give individual entries \"this is a copy\" or \"this is a\nrename\" indicators).\n\nAnd I thought I was really done with diff this time, but here\nare some leftover issues I would like to further address, not\nnecessarily in this order, and not necessarily promising to do\nall of them.\n\n - Make \"diff-raw human readable\" output quite different from\n \"diff-raw machine readable\" format. I think human readable\n format should be more like \"concise version of diff-patch\n format for human consumption\", not the current \"LF and TAB\n separated version of machine readable output\", to enhance\n readability. This includes:\n\n (1) not repeating paths when src and dst are the same\n (i.e. most of the time);\n\n (2) substituting src/dst with /dev/null when talking about\n creation or deletion;\n\n (3) prefixing the src and dst with '+' or '*' or '-'.\n\n Currently I do not intend to add _parsing_ of such output to\n diff-helper because you can always use -z on both ends of the\n pipe (and as yourself said \"Sure. Although I doubt people use\n the raw diff output except to (a) feed to diff-helper or (b)\n check that it's non-empty.\"), but I have to sleep on this.\n\n - Add an option to cause diff-tree three-brothers not to call\n diffcore_prune() at all. This will essentially produce\n something like a merge of two output from ls-files or\n ls-trees commands, but with renames/copies resolved. I do\n not know how useful this would be, especially now the\n immediate problem of diff_flush() pruning all the\n \"non-change\" entries is (hopefully) fixed.\n\n - Give pickaxe an option to cause it to produce diffs for the\n entire commit, not just the found file.\n\n - Experiment with the patch reordering I talked about in the\n previous message.\n\n - Add the support of \"copied from post-edit image\" detection in\n rename/copy logic. Currently I compare only with pre-edit\n image for modified files.\n\n - Read and understand the patch-delta.c, to make rename/copy\n similarity estimator more accurate. As you pointed out, it\n does very bad things on big consecutive deletes.\n\n - Think about performance issues around \"diff-tree -C\" stuff.\n\n - Think more about the problem with the patch output between\n two symbolic links, and how to fix it (I've been quietly\n thinking about this for some time ;-)). I think the current\n output of just comparing the two readlink results and\n generating a normal diff between them is broken and hazardous\n if such a thing is mistakenly fed to patch -p1.\n\n - Teach JIT about the diff-raw format changes.\n\n"},{"id":"3846","messageId":"7vbr71xjyt.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505211137250.2206@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T05:37:46Z","receivedAt":"2005-05-24T05:37:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> Hmm.. It's not working well. Not only does it take a lot of CPU time (do \nLT> an fsck first to make sure you're not seekign the disk all over the \nLT> place), but it \"finds\" lots of things like this:\n\nThe \"finds logs of funny things\" problem should have been fixed\nby now, and I am fixing a big screwup now as I reported. I have\ntwo ideas on speeding up diff-tree -C I want to run by you.\n\nI have not measured things yet, but I think the big CPU waste is\ncoming from either expanding all the blobs and/or running the\ndiff-delta on many file pairs. If that is indeed the cause,\nthen helping the upfront check in the similarity estimator that\nrefuses to consider a file pair whose file size change is too\nbig may be a good way to resolve this problem.\n\nOne approach, which I think is an unacceptable change at this\nstage (but I would seriously consider if this _were_ a week and\nhalf old project), is to record the blob size as part of the\nobject ID. We say object size is \"unsigned long\" everywhere, so\nI am talking about making the object ID from 20-byte SHA1 to\n24-byte SHA1 plus 4-byte integer in the network byte order.\n\nSince I think the above is inpractical, the second best approach\nwould be to piggy-back on the optimization used in uncached\ndiff-cache, which avoids blob expansion if cache says what we\nhave in the work tree already matches the object we are\ninterested in.\n\nWhen -C is in effect, we would make diff-tree read the current\ncache first, so that diff_populate_filespec() can borrow from\nthe current work tree when a path in the tree we are looking at\nhas not changed. This would obviously be effective only when we\nare talking about recent history.\n\nThoughts?\n\n\n"},{"id":"3847","messageId":"Pine.LNX.4.58.0505232314510.2307@ppc970.osdl.org","threadId":"660","inReplyTo":"7vbr71xjyt.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-24T06:19:49Z","receivedAt":"2005-05-24T06:19:49Z","isPatch":true,"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> I have not measured things yet, but I think the big CPU waste is\n> coming from either expanding all the blobs and/or running the\n> diff-delta on many file pairs. If that is indeed the cause,\n> then helping the upfront check in the similarity estimator that\n> refuses to consider a file pair whose file size change is too\n> big may be a good way to resolve this problem.\n\nSince pretty much all the blobs will be expanded in the working directory\nanyway, it sounds like that would be the way to go. \n\n> One approach, which I think is an unacceptable change at this\n> stage (but I would seriously consider if this _were_ a week and\n> half old project), is to record the blob size as part of the\n> object ID. We say object size is \"unsigned long\" everywhere, so\n> I am talking about making the object ID from 20-byte SHA1 to\n> 24-byte SHA1 plus 4-byte integer in the network byte order.\n\nYou can actually get the blob size fairly easily for non-delta objects, by \njust unpacking the beginning of it. But since we have the files..\n\nThat said, I don't think -C is that important. I personally don't see it\nas a thing I'd run normally - it's more of a thing I might do between\nreleases rather than for something like git-whatchanged that looks at\nevery commit. It's an interesting thing to have _available_, but I don't\nthink it's a huge problem if it is a lot more expensive than the more\nnormal \"-M\".\n\n\t\tLinus\n"},{"id":"3849","messageId":"7vll65vy10.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505232314510.2307@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T08:16:59Z","receivedAt":"2005-05-24T08:16:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> Since pretty much all the blobs will be expanded in the working directory\nLT> anyway, it sounds like that would be the way to go. \nLT> That said, I don't think -C is that important...\n\nOK, so the short version is, diff-cache like optimization may be\ninteresting to try out, but practically it would not be much\nuseful anyway, so I should do it if I am really bored and have\nnothing else interesting to do ;-).\n\n\n"},{"id":"3851","messageId":"Pine.LNX.4.58.0505240129420.2307@ppc970.osdl.org","threadId":"660","inReplyTo":"7vll65vy10.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-24T08:31:52Z","receivedAt":"2005-05-24T08:31:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 24 May 2005, Junio C Hamano wrote:\n> \n> OK, so the short version is, diff-cache like optimization may be\n> interesting to try out, but practically it would not be much\n> useful anyway, so I should do it if I am really bored and have\n> nothing else interesting to do ;-).\n\nYup. I think it's more important to get the rest calmed down again, and \nfix the things that got broken. Sadly, \"git-whatchanged -s\" was one such \nthing.\n\n(I think that's just because the \"silent\" test used to depend on the \nmagical behaviour of the \"header\" thing, and now that the header \ngeneration and suppression is sane, \"silent\" doesn't work any more)\n\n\t\tLinus\n"},{"id":"3853","messageId":"7vr7fxuh8b.fsf@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505240129420.2307@ppc970.osdl.org","subject":"Re: [PATCH 3/3] Diff overhaul, adding the other half...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-24T09:05:08Z","receivedAt":"2005-05-24T09:05:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> (I think that's just because the \"silent\" test used to depend on the \nLT> magical behaviour of the \"header\" thing, and now that the header \nLT> generation and suppression is sane, \"silent\" doesn't work any more)\n\nI think you will be more efficient for this task but I'm willing\nto volunteer if you let me know how \"silent\" should behave. The\ndocumentation says it is useful only with -v and supresses the\ndiffs, so if that is the only thing it does, I think something\nlike this is sufficient? Not tested enough but I am going to\ncrash for the day now.\n\n------------\nUse DIFF_FORMAT_NO_OUTPUT to implement diff-tree -s option.\n\nInstead of checking silent flag all over the place, simply use\nthe NO_OUTPUT option diffcore provides to suppress the diff\noutput.\n\nSigned-off-by: Junio C Hamano \n---\ncd /opt/packrat/playpen/public/in-place/git/git.junio/\njit-diff\n# - HEAD: Allow symlinks in the leading path in checkout-cache --prefix=\n# + (working tree)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -2,7 +2,6 @@\n #include \"cache.h\"\n #include \"diff.h\"\n \n-static int silent = 0;\n static int show_root_diff = 0;\n static int verbose_header = 0;\n static int ignore_merges = 1;\n@@ -67,9 +66,6 @@ static void show_file(const char *prefix\n \tconst char *path;\n \tconst unsigned char *sha1 = extract(tree, size, &path, &mode);\n \n-\tif (silent)\n-\t\treturn;\n-\n \tif (recursive && S_ISDIR(mode)) {\n \t\tchar type[20];\n \t\tunsigned long size;\n@@ -132,9 +128,6 @@ static int compare_tree_entry(void *tree\n \t\treturn retval;\n \t}\n \n-\tif (silent)\n-\t\treturn 0;\n-\n \tdiff_change(mode1, mode2, sha1, sha2, base, path1);\n \treturn 0;\n }\n@@ -395,8 +388,7 @@ static char *generate_header(const char \n \t\tif (this_header[offset-1] != '\\n')\n \t\t\tthis_header[offset++] = '\\n';\n \t\t/* Add _another_ EOLN if we are doing diff output */\n-\t\tif (!silent)\n-\t\t\tthis_header[offset++] = '\\n';\n+\t\tthis_header[offset++] = '\\n';\n \t\tthis_header[offset] = 0;\n \t}\n \n@@ -442,8 +434,6 @@ static int diff_tree_commit(const unsign\n \t\t\t * Don't print multiple merge entries if we\n \t\t\t * don't print the diffs.\n \t\t\t */\n-\t\t\tif (silent)\n-\t\t\t\tbreak;\n \t\t}\n \t\toffset += 48;\n \t}\n@@ -540,7 +530,7 @@ int main(int argc, const char **argv)\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(arg, \"-s\")) {\n-\t\t\tsilent = 1;\n+\t\t\tdiff_output_format = DIFF_FORMAT_NO_OUTPUT;\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(arg, \"-v\")) {\n\nCompilation finished at Tue May 24 02:03:10\n\n\n\n"},{"id":"3968","messageId":"7vzmuiekvx.fsf_-_@assigned-by-dhcp.cox.net","threadId":"660","inReplyTo":"Pine.LNX.4.58.0505232314510.2307@ppc970.osdl.org","subject":"[RFC/PATCH] Detect copies harder in diff-tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-26T03:17:22Z","receivedAt":"2005-05-26T03:17:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds writes:\n\nLT> That said, I don't think -C is that important.\n\nBy now, you know I won't listen ;-).\n\nI've done preliminary --detect-copies-harder (that is to feed all\nthe unmodified files to diffcore when doing -C) and --use-cache\n(this is to allow diffcore to avoid expanding blob when there is\na already matching file in the work tree) changes to diff-tree.\n\nThis example is from the linux-2.6 tree, with the tip of the\ntree in the work tree and the cache, and looking at the commit\nwhen include/asm-um was cleaned up (May 5th). The first one\ndoes not detect copies from \"unmodified\" files, but the latter\ntwo do. In this commit there isn't any copy that \"harder\"\nversion finds but ordinary one doesn't.\n\n: siamese; time ../git.junio/git-diff-tree -r \\\n -C dbc35cc73f2edd6e39d7e814dbb6eddad6294665 >/dev/null\nreal 0m0.010s\nuser 0m0.010s\nsys 0m0.000s\n: siamese; time ../git.junio/git-diff-tree -r --detect-copies-harder \\\n -C dbc35cc73f2edd6e39d7e814dbb6eddad6294665 >/dev/null\nreal 0m19.938s\nuser 0m11.520s\nsys 0m1.240s\n: siamese; time ../git.junio/git-diff-tree -r \\\n --detect-copies-harder --use-cache -C \\\n dbc35cc73f2edd6e39d7e814dbb6eddad6294665 >/dev/null\nreal 0m5.858s\nuser 0m5.110s\nsys 0m0.710s\n\n------------\nAdd --detect-copies-harder and --use-cache to diff-tree.\n\nThis adds two new options to diff-tree. Even when -C is used,\ndiff-tree does not normally feed \"unmodified\" filepair to the\ndiffcore, so copy detection is done only among the files that\nhave changed. With --detect-copies-harder, it can also detect\ncopies made from an unmodified file (this behavior is the\ndefault for diff-files and diff-cache). When this option is\nused, it is recommended to also give --use-cache, which lets\ndiffcore to avoid expanding blob when the work tree has the same\nfile unmodified.\n\nSigned-off-by: Junio C Hamano \n---\ncd /opt/packrat/playpen/public/in-place/git/git.junio/\njit-diff\n# - linus: git-rev-list: add \"end\" commit and \"--header\" flag\n# + (working tree)\ndiff --git a/diff-tree.c b/diff-tree.c\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -6,6 +6,8 @@ static int show_root_diff = 0;\n static int verbose_header = 0;\n static int ignore_merges = 1;\n static int recursive = 0;\n+static int use_cache = 0;\n+static int detect_copies_harder = 0;\n static int show_tree_entry_in_recursive = 0;\n static int read_stdin = 0;\n static int diff_output_format = DIFF_FORMAT_HUMAN;\n@@ -108,7 +110,8 @@ static int compare_tree_entry(void *tree\n \t\tshow_file(\"+\", tree2, size2, base);\n \t\treturn 1;\n \t}\n-\tif (!memcmp(sha1, sha2, 20) && mode1 == mode2)\n+\tif (!memcmp(sha1, sha2, 20) && mode1 == mode2 &&\n+\t (detect_rename != DIFF_DETECT_COPY || !detect_copies_harder))\n \t\treturn 0;\n \n \t/*\n@@ -549,6 +552,14 @@ int main(int argc, const char **argv)\n \t\t\tread_stdin = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--use-cache\")) {\n+\t\t\tuse_cache = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"--detect-copies-harder\")) {\n+\t\t\tdetect_copies_harder = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--root\")) {\n \t\t\tshow_root_diff = 1;\n \t\t\tcontinue;\n@@ -566,6 +577,16 @@ int main(int argc, const char **argv)\n \t\t\tpathlens[i] = strlen(paths[i]);\n \t}\n \n+\tif (detect_rename && use_cache && !active_cache) {\n+\t\t/* read-cache does not die even when it fails\n+\t\t * so it is safe for us to do this here. Also\n+\t\t * it does not smudge active_cache or active_nr\n+\t\t * when it fails, so we do not have to worry about\n+\t\t * cleaning it up oufselves either.\n+\t\t */\n+\t\tread_cache();\n+\t}\n+\n \tswitch (nr_sha1) {\n \tcase 0:\n \t\tif (!read_stdin)\n\nCompilation finished at Wed May 25 19:59:09\n\n"}]}