{"thread":{"id":"647","subject":"[PATCH 1/1] Diff-helper update","startedAt":"2005-05-18T06:29:49Z","lastAt":"2005-05-18T06:29:49Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"3490","messageId":"7vwtpxoxlu.fsf@assigned-by-dhcp.cox.net","threadId":"647","inReplyTo":null,"subject":"[PATCH 1/1] Diff-helper update","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-18T06:29:49Z","receivedAt":"2005-05-18T06:29:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This patch adds a framework and a stub implementation of rename\ndetection to diff-helper program.\n\nThe current stub code is just enough to detect pure renames in\ndiff-tree output and not fancier.  The plan is perhaps to use\nthe same delta code when Nico's delta storage patch is merged\nfor similarity evaluation purposes.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\nDocumentation/git-diff-helper.txt |   12 ++-\ndiff-helper.c                     |  141 +++++++++++++++++++++++++++++++++++++-\ndiff.c                            |   34 +++++----\ndiff.h                            |    2 \n4 files changed, 170 insertions(+), 19 deletions(-)\n\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]\n+'git-diff-helper' [-z] [-R] [-r]\n \n DESCRIPTION\n -----------\n@@ -28,7 +28,12 @@\n \n \t\tgit-diff-cache <tree> | git-diff-helper -R file.c\n \n-would show a diff to bring the working file back to what is in the <tree>.\n+\twould show a diff to bring the working file back to what\n+\tis in the <tree>.\n+\n+-r::\n+\tDetect renames.\n+\n \n See Also\n --------\n@@ -37,7 +42,8 @@\n \n Author\n ------\n-Written by Linus Torvalds <torvalds@osdl.org>\n+Written by Junio C Hamano <junkio@cox.net>\n+\n \n Documentation\n --------------\ndiff -git a/diff-helper.c b/diff-helper.c\n--- a/diff-helper.c\n+++ b/diff-helper.c\n@@ -21,6 +21,129 @@\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 {\n@@ -100,17 +223,24 @@\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, &new, &old);\n+\t\t\trun_external_diff(path, NULL, &new, &old);\n \t\telse\n-\t\t\trun_external_diff(path, &old, &new);\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-\"git-diff-helper [-R] [-z] paths...\";\n+\t\"git-diff-helper [-r] [-R] [-z] paths...\";\n \n int main(int ac, const char **av) {\n \tstruct strbuf sb;\n@@ -124,6 +254,8 @@\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\t\tdetect_rename = 1;\n \t\telse\n \t\t\tusage(diff_helper_usage);\n \t\tac--; av++;\n@@ -139,5 +271,8 @@\n \t\tif (status)\n \t\t\tfprintf(stderr, \"cannot parse %s\\n\", sb.buf);\n \t}\n+\n+\tif (detect_rename)\n+\t\tflush_renames(av+1, ac-1, reverse);\n \treturn 0;\n }\ndiff -git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -79,7 +79,8 @@\n \tchar tmp_path[50];\n } diff_temp[2];\n \n-static void builtin_diff(const char *name,\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 {\n \tint i, next_at;\n@@ -88,9 +89,12 @@\n \tconst char *input_name_sq[2];\n \tconst char *path0[2];\n \tconst char *path1[2];\n-\tconst char *name_sq = sq_expand(name);\n+\tconst char *name_sq[2];\n \tchar *cmd;\n-\t\n+\n+\tname_sq[0] = sq_expand(name_a);\n+\tname_sq[1] = sq_expand(name_b);\n+\n \t/* diff_cmd and diff_arg have 6 %s in total which makes\n \t * the sum of these strings 12 bytes larger than required.\n \t * we use 2 spaces around diff-opts, and we need to count\n@@ -105,7 +109,7 @@\n \t\t\tpath1[i] = \"\";\n \t\t} else {\n \t\t\tpath0[i] = i ? \"b/\" : \"a/\";\n-\t\t\tpath1[i] = name_sq;\n+\t\t\tpath1[i] = name_sq[i];\n \t\t}\n \t\tcmd_size += (strlen(path0[i]) + strlen(path1[i]) +\n \t\t\t     strlen(input_name_sq[i]));\n@@ -122,7 +126,7 @@\n \tnext_at += snprintf(cmd+next_at, cmd_size-next_at,\n \t\t\t    diff_arg, input_name_sq[0], input_name_sq[1]);\n \n-\tprintf(\"diff -git a/%s b/%s\\n\", name, name);\n+\tprintf(\"diff -git a/%s b/%s\\n\", name_a, name_b);\n \tif (!path1[0][0])\n \t\tprintf(\"new file mode %s\\n\", temp[1].mode);\n \telse if (!path1[1][0])\n@@ -132,6 +136,10 @@\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\tprintf(\"rename old %s\\n\", name_a);\n+\t\t\tprintf(\"rename new %s\\n\", name_b);\n+\t\t}\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@@ -157,7 +165,7 @@\n \t * benchmark with my previous version that always reads cache\n \t * shows that it makes things worse for diff-tree comparing\n \t * two linux-2.6 kernel trees in an already checked out work\n-\t * tree.  This is because most diff-tree comparison deals with\n+\t * tree.  This is because most diff-tree comparisons deal with\n \t * only a small number of files, while reading the cache is\n \t * expensive for a large project, and its cost outweighs the\n \t * savings we get by not inflating the object to a temporary\n@@ -294,6 +302,7 @@\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 {\n@@ -304,7 +313,7 @@\n \n \tif (one && two) {\n \t\tprepare_temp_file(name, &temp[0], one);\n-\t\tprepare_temp_file(name, &temp[1], two);\n+\t\tprepare_temp_file(other ? : name, &temp[1], two);\n \t\tif (! atexit_asked &&\n \t\t    (temp[0].name == temp[0].tmp_path ||\n \t\t     temp[1].name == temp[1].tmp_path)) {\n@@ -320,7 +329,8 @@\n \t\tdie(\"unable to fork\");\n \tif (!pid) {\n \t\tconst char *pgm = external_diff();\n-\t\tif (pgm) {\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@@ -334,7 +344,7 @@\n \t\t * otherwise we use the built-in one.\n \t\t */\n \t\tif (one && two)\n-\t\t\tbuiltin_diff(name, temp);\n+\t\t\tbuiltin_diff(name, other ? : name, temp);\n \t\telse\n \t\t\tprintf(\"* Unmerged path %s\\n\", name);\n \t\texit(0);\n@@ -379,7 +389,7 @@\n \t\tstrcpy(concatpath, base);\n \t\tstrcat(concatpath, path);\n \t}\n-\trun_external_diff(path ? concatpath : base, one, two);\n+\trun_external_diff(path ? concatpath : base, NULL, one, two);\n }\n \n void diff_change(unsigned old_mode, unsigned new_mode,\n@@ -400,10 +410,10 @@\n \t\tstrcpy(concatpath, base);\n \t\tstrcat(concatpath, path);\n \t}\n-\trun_external_diff(path ? concatpath : base, &spec[0], &spec[1]);\n+\trun_external_diff(path ? concatpath : base, NULL, &spec[0], &spec[1]);\n }\n \n void diff_unmerge(const char *path)\n {\n-\trun_external_diff(path, NULL, NULL);\n+\trun_external_diff(path, NULL, NULL, NULL);\n }\ndiff -git a/diff.h b/diff.h\n--- a/diff.h\n+++ b/diff.h\n@@ -31,7 +31,7 @@\n \tunsigned file_valid : 1; /* if false the file does not even exist */\n };\n \n-extern void run_external_diff(const char *name,\n+extern void run_external_diff(const char *name, const char *other,\n \t\t\t      struct diff_spec *, struct diff_spec *);\n \n #endif /* DIFF_H */\n------------------------------------------------\n\n"}]}