{"thread":{"id":"16226","subject":"[PATCH v2 1/2] diffcore-rename: support rename cache","startedAt":"2008-11-08T11:27:32Z","lastAt":"2008-11-08T11:27:33Z","messageCount":2,"participants":["Nguyễn Thái Ngọc Duy"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"95207","messageId":"1226143653-3758-1-git-send-email-pclouds@gmail.com","threadId":"16226","inReplyTo":null,"subject":"[PATCH v2 1/2] diffcore-rename: support rename cache","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-08T11:27:32Z","receivedAt":"2008-11-08T11:27:32Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This patch teaches diffcore_rename() to look into\n$GIT_DIR/rename-cache and make use of it to recreate diff_filepair.\nWith proper cache, there should be no available entry for estimation\nafter exact matching.\n\nRename caching is per commit. I don't think abitrary tree-tree caching\nis worth it.\n\n$GIT_DIR/rename-cache spans out like $GIT_DIR/objects. Each file\ncorresponds to one commit. Its content consists of lines like this\n\n \n\nThis can be used to:\n\n - Make --find-copies-harder pratically usable for moderate-size\n repositories. The first \"git show\" on a linux kernel commit was 5.3\n sec, it then went down to 0.13 sec.\n - Give git-svn a chance to (locally) import explicit renames from\n Subversion\n - People may correct rename results for better diff, if automatic\n rename detection is not good enough.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n > > > Has anybody thought about interaction between that caching and pathspec\n > > > limited operation?\n > > >\n > >\n > > I didn't. But I think all out-of-pathspec diff pairs are removed\n > > before it reaches diffcore_rename() so the cache has nothing to do\n > > with it (except it still loads full cache for a commit).\n >\n >\n > Well, it could be that an out-of-pathspec pair would have a better\n > score than an in-pathspec one. Maybe cache recording should be turned\n > off when doing pathspec limitation ?\n\n Changes from v1:\n - rebased to next to avoid conflict\n - no longer generate cache if pathspec is used\n\n diff.h | 2 +\n diffcore-rename.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++-\n log-tree.c | 2 +\n t/t4031-rename-cache.sh | 56 ++++++++++++++++++\n 4 files changed, 200 insertions(+), 2 deletions(-)\n create mode 100755 t/t4031-rename-cache.sh\n\ndiff --git a/diff.h b/diff.h\nindex 42582ed..64a1edd 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -111,6 +111,8 @@ struct diff_options {\n \tadd_remove_fn_t add_remove;\n \tdiff_format_fn_t format_callback;\n \tvoid *format_callback_data;\n+\n+\tstruct commit *commit;\n };\n \n enum color_diff {\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 168a95b..598cc8d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,6 +5,7 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"hash.h\"\n+#include \"commit.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -409,13 +410,130 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+struct cached_filepair {\n+\tunsigned char dst[20];\n+\tunsigned char src[20];\n+\tint score;\n+};\n+\n+static int free_cached_filepair(void *p)\n+{\n+\tfree(p);\n+\treturn 0;\n+}\n+\n+static void load_rename_cache(struct diff_queue_struct *q,\n+\t\t\t struct diff_queue_struct *cacheq,\n+\t\t\t struct diff_options *options)\n+{\n+\tchar *sha1_hex;\n+\tFILE *fp;\n+\tstruct hash_table filepair_table;\n+\tstruct hash_table src_table;\n+\tstruct cached_filepair *pp;\n+\tint i, hash;\n+\tstatic int no_cache_available = -1;\n+\tstruct stat st;\n+\tchar *path;\n+\n+\tif (no_cache_available == -1)\n+\t\tno_cache_available = stat(git_path(\"rename-cache\"), &st) || !S_ISDIR(st.st_mode);\n+\n+\t/* return soon so we don't need to waste CPU */\n+\tif (no_cache_available > 0)\n+\t\treturn;\n+\n+\n+\t/* src_table initialization */\n+\tinit_hash(&src_table);\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tif (DIFF_FILE_VALID(p->one)) {\n+\t\t\tunsigned int hash = hash_filespec(p->one);\n+\t\t\tinsert_hash(hash, p, &src_table);\n+\t\t}\n+\t}\n+\n+\t/* filepair_table initialization */\n+\tinit_hash(&filepair_table);\n+\tsha1_hex = sha1_to_hex(options->commit->object.sha1);\n+\tpath = git_path(\"rename-cache/%c%c/%s\",sha1_hex[0], sha1_hex[1], sha1_hex+2);\n+\tif (stat(path, &st))\n+\t\tfp = NULL;\n+\telse\n+\t\tfp = fopen(path, \"r\");\n+\tif (fp) {\n+\t\tchar src_sha1_hex[41], dst_sha1_hex[41];\n+\t\tstruct cached_filepair p;\n+\n+\t\tsrc_sha1_hex[40] = dst_sha1_hex[40] = '\\0';\n+\t\twhile (fscanf(fp, \"%40c %40c %d\\n\", dst_sha1_hex, src_sha1_hex, &p.score) == 3) {\n+\t\t\tif (get_sha1_hex(src_sha1_hex, p.src) ||\n+\t\t\t get_sha1_hex(dst_sha1_hex, p.dst))\n+\t\t\t\tbreak;\n+\n+\t\t\tpp = xmalloc(sizeof(*pp));\n+\t\t\tmemcpy(pp, &p, sizeof(*pp));\n+\t\t\tmemcpy(&hash, p.dst, sizeof(hash));\n+\t\t\tinsert_hash(hash, pp, &filepair_table);\n+\t\t}\n+\t\tfclose(fp);\n+\t}\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tstruct diff_filepair *dp, *src;\n+\n+\t\t/* find remote_dst */\n+\t\tif (DIFF_FILE_VALID(p->one) ||\n+\t\t !DIFF_FILE_VALID(p->two) ||\n+\t\t (options->single_follow && strcmp(options->single_follow, p->two->path)))\n+\t\t\tcontinue;\n+\n+\t\tmemcpy(&hash, p->two->sha1, sizeof(hash));\n+\t\tpp = lookup_hash(hash, &filepair_table);\n+\t\tif (!pp || memcmp(p->two->sha1, pp->dst, 20))\n+\t\t\tcontinue;\n+\n+\t\t/* create pair */\n+\t\tif (is_null_sha1(pp->src)) {\n+\t\t\tif (DIFF_FILE_VALID(p->one))\n+\t\t\t\tcontinue;\n+\t\t\tdiff_q(cacheq, p);\n+\t\t\tq->queue[i] = NULL;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tmemcpy(&hash, pp->src, sizeof(hash));\n+\t\tsrc = lookup_hash(hash, &src_table);\n+\t\tif (!src || memcmp(pp->src, src->one->sha1, 20))\n+\t\t\tcontinue;\n+\n+\t\tsrc->one->rename_used++;\n+\t\tsrc->one->count++;\n+\t\tp->two->count++;\n+\n+\t\tdp = diff_queue(NULL, src->one, p->two);\n+\t\tdp->renamed_pair = 1;\n+\t\tdp->score = pp->score;\n+\n+\t\tdiff_q(cacheq, dp);\n+\t\tq->queue[i] = NULL;\n+\t\tdiff_free_filepair(p);\n+\t}\n+\n+\tfor_each_hash(&filepair_table, free_cached_filepair);\n+\tfree_hash(&src_table);\n+\tfree_hash(&filepair_table);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n \tint minimum_score = options->rename_score;\n \tint rename_limit = options->rename_limit;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct diff_queue_struct outq;\n+\tstruct diff_queue_struct outq, cacheq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count;\n \tint num_create, num_src, dst_cnt;\n@@ -423,8 +541,19 @@ void diffcore_rename(struct diff_options *options)\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n+\tcacheq.queue = NULL;\n+\tcacheq.nr = cacheq.alloc = 0;\n+\n+\tif (detect_rename && options->commit)\n+\t\tload_rename_cache(q, &cacheq, options);\n+\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n+\n+\t\t/* was consumed by rename cache */\n+\t\tif (!p)\n+\t\t\tcontinue;\n+\n \t\tif (!DIFF_FILE_VALID(p->one)) {\n \t\t\tif (!DIFF_FILE_VALID(p->two))\n \t\t\t\tcontinue; /* unmerged */\n@@ -563,10 +692,17 @@ void diffcore_rename(struct diff_options *options)\n \t */\n \toutq.queue = NULL;\n \toutq.nr = outq.alloc = 0;\n-\tfor (i = 0; i < q->nr; i++) {\n+\tfor (i = j = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tstruct diff_filepair *pair_to_free = NULL;\n \n+\t\tif (!p) {\n+\t\t\tif (j >= cacheq.nr)\n+\t\t\t\tdie(\"Internal error: running out of cacheq.\");\n+\t\t\tdiff_q(&outq, cacheq.queue[j++]);\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n \t\t\t * Creation\n@@ -635,6 +771,8 @@ void diffcore_rename(struct diff_options *options)\n \tdiff_debug_queue(\"done copying original\", &outq);\n \n \tfree(q->queue);\n+\tif (cacheq.queue)\n+\t\tfree(cacheq.queue);\n \t*q = outq;\n \tdiff_debug_queue(\"done collapsing\", q);\n \ndiff --git a/log-tree.c b/log-tree.c\nindex 5444f08..040e095 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -522,6 +522,7 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit)\n \tlog.commit = commit;\n \tlog.parent = NULL;\n \topt->loginfo = &log;\n+\topt->diffopt.commit = commit;\n \n \tshown = log_tree_diff(opt, commit, &log);\n \tif (!shown && opt->loginfo && opt->always_show_header) {\n@@ -531,5 +532,6 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit)\n \t}\n \topt->loginfo = NULL;\n \tmaybe_flush_or_die(stdout, \"stdout\");\n+\topt->diffopt.commit = NULL;\n \treturn shown;\n }\ndiff --git a/t/t4031-rename-cache.sh b/t/t4031-rename-cache.sh\nnew file mode 100755\nindex 0000000..f7c53fd\n--- /dev/null\n+++ b/t/t4031-rename-cache.sh\n@@ -0,0 +1,56 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2008 Nguyen Thai Ngoc Duy\n+#\n+\n+test_description='Test diff rename cache'\n+. ./test-lib.sh\n+\n+cat >expected < sub/d (100%)\n+EOF\n+test_expect_success 'setup' '\n+\techo a > a\n+\techo b > b\n+\tmkdir sub\n+\techo c > sub/c\n+\tcp a sub/d\n+\tA_SHA1=$(git hash-object a)\n+\tB_SHA1=$(git hash-object b)\n+\tC_SHA1=$(git hash-object sub/c)\n+\tD_SHA1=$(git hash-object sub/d)\n+\tgit add a b\n+\ttest_tick\n+\tgit commit -m first\n+\tgit add sub\n+\tgit commit -m second\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+cat >expected < sub/c (100%)\n+ copy a => sub/d (100%)\n+EOF\n+test_expect_success 'load rename pair cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\")\n+\tmkdir -p $(dirname $P)\n+\techo $C_SHA1 $A_SHA1 60000 >> $P\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+cat >expected < sub/c (100%)\n+ create mode 100644 sub/d\n+EOF\n+test_expect_success 'load create pair cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\")\n+\tmkdir -p $(dirname $P)\n+\techo $D_SHA1 0000000000000000000000000000000000000000 0 >> $P\n+\tgit show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result\n+\ttest_cmp expected result\n+'\n+\n+test_done\n-- \n1.6.0.3.892.g83538\n"},{"id":"95208","messageId":"1226143653-3758-2-git-send-email-pclouds@gmail.com","threadId":"16226","inReplyTo":"1226143653-3758-1-git-send-email-pclouds@gmail.com","subject":"[PATCH v2 2/2] diffcore-rename: add config option to allow to cache renames","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2008-11-08T11:27:33Z","receivedAt":"2008-11-08T11:27:33Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"If diff.cacherenames is true, then renames will be cached to\n$GIT_DIR/rename-cache. By default, it will not overwrite existing\ncache. Add --refresh-cache to overwrite.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Documentation/config.txt | 5 ++++\n Documentation/diff-options.txt | 5 ++++\n diff.c | 12 +++++++++\n diff.h | 2 +\n diffcore-rename.c | 49 ++++++++++++++++++++++++++++++++++++++++\n t/t4031-rename-cache.sh | 36 +++++++++++++++++++++++++++++\n 6 files changed, 109 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 965ed74..8a7f00e 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -630,6 +630,11 @@ diff.renames::\n \twill enable basic rename detection. If set to \"copies\" or\n \t\"copy\", it will detect copies, as well.\n \n+diff.cacherenames::\n+\tTells git to automatically cache renames when detected. The\n+\tcache resides in $GIT_DIR/rename-cache, which is used by git\n+\tif exists.\n+\n fetch.unpackLimit::\n \tIf the number of objects fetched over the git native\n \ttransfer is below this\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex c62b45c..d477a40 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -102,6 +102,11 @@ endif::git-format-patch[]\n \tTurn off rename detection, even when the configuration\n \tfile gives the default to do so.\n \n+--refresh-rename-cache::\n+\tBy default, when git finds a cached version of a commit, it\n+\twill not overwrite the cache. This option makes git overwrite\n+\told cache or create a new one.\n+\n --check::\n \tWarn if changes introduce trailing whitespace\n \tor an indent that uses a space before a tab. Exits with\ndiff --git a/diff.c b/diff.c\nindex f644947..604cb12 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -26,6 +26,7 @@ int diff_use_color_default = -1;\n static const char *external_diff_cmd_cfg;\n int diff_auto_refresh_index = 1;\n static int diff_mnemonic_prefix;\n+static int diff_cache_renames;\n \n static char diff_colors[][COLOR_MAXLEN] = {\n \t\"\\033[m\",\t/* reset */\n@@ -103,6 +104,11 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"diff.cacherenames\")) {\n+\t\tdiff_cache_renames = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tswitch (userdiff_config(var, value)) {\n \t\tcase 0: break;\n \t\tcase -1: return -1;\n@@ -2272,6 +2278,8 @@ int diff_setup_done(struct diff_options *options)\n \n \tif (options->detect_rename && options->rename_limit < 0)\n \t\toptions->rename_limit = diff_rename_limit_default;\n+\tif (options->detect_rename && diff_cache_renames)\n+\t\t\tDIFF_OPT_SET(options, CACHE_RENAMES);\n \tif (options->setup & DIFF_SETUP_USE_CACHE) {\n \t\tif (!active_cache)\n \t\t\t/* read-cache does not die even when it fails\n@@ -2439,6 +2447,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_OPT_SET(options, RELATIVE_NAME);\n \t\toptions->prefix = arg + 11;\n \t}\n+\telse if (!strcmp(arg, \"--refresh-rename-cache\")) {\n+\t\tDIFF_OPT_SET(options, CACHE_RENAMES);\n+\t\tDIFF_OPT_SET(options, REFRESH_RENAME_CACHE);\n+\t}\n \n \t/* xdiff options */\n \telse if (!strcmp(arg, \"-w\") || !strcmp(arg, \"--ignore-all-space\"))\ndiff --git a/diff.h b/diff.h\nindex 64a1edd..0503b57 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -66,6 +66,8 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,\n #define DIFF_OPT_DIRSTAT_CUMULATIVE (1 << 19)\n #define DIFF_OPT_DIRSTAT_BY_FILE (1 << 20)\n #define DIFF_OPT_ALLOW_TEXTCONV (1 << 21)\n+#define DIFF_OPT_CACHE_RENAMES (1 << 22)\n+#define DIFF_OPT_REFRESH_RENAME_CACHE (1 << 23)\n #define DIFF_OPT_TST(opts, flag) ((opts)->flags & DIFF_OPT_##flag)\n #define DIFF_OPT_SET(opts, flag) ((opts)->flags |= DIFF_OPT_##flag)\n #define DIFF_OPT_CLR(opts, flag) ((opts)->flags &= ~DIFF_OPT_##flag)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 598cc8d..49651ea 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -527,6 +527,44 @@ static void load_rename_cache(struct diff_queue_struct *q,\n \tfree_hash(&filepair_table);\n }\n \n+static void save_rename_cache(struct diff_queue_struct *outq,\n+\t\t\t struct diff_options *options)\n+{\n+\tint i;\n+\tFILE *fp = NULL;\n+\tstruct stat st;\n+\n+\tfor (i = 0;i < outq->nr; i++) {\n+\t\tstruct diff_filepair *dp = outq->queue[i];\n+\n+\t\tif (!(dp->renamed_pair || /* rename pair */\n+\t\t (!DIFF_FILE_VALID(dp->one) && DIFF_FILE_VALID(dp->two)))) /* create pair */\n+\t\t\tcontinue;\n+\n+\t\tif (!fp) {\n+\t\t\tchar *sha1 = sha1_to_hex(options->commit->object.sha1);\n+\t\t\tchar *path = git_path(\"rename-cache/%c%c/%s\", sha1[0], sha1[1], sha1+2);\n+\n+\t\t\t/* Already cached. If not force refresh, move on */\n+\t\t\tif (!stat(path, &st) && !DIFF_OPT_TST(options, REFRESH_RENAME_CACHE))\n+\t\t\t\treturn;\n+\n+\t\t\tsafe_create_leading_directories(path);\n+\t\t\tfp = fopen(path, \"w\");\n+\n+\t\t\tif (!fp)\n+\t\t\t\treturn;\n+\t\t}\n+\n+\t\tfprintf(fp, \"%s \", sha1_to_hex(dp->two->sha1));\n+\t\tfprintf(fp, \"%s %d\\n\",\n+\t\t\tsha1_to_hex(DIFF_FILE_VALID(dp->one) ? dp->one->sha1 : null_sha1),\n+\t\t\tdp->score);\n+\t}\n+\tif (fp)\n+\t\tfclose(fp);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -770,6 +808,17 @@ void diffcore_rename(struct diff_options *options)\n \t}\n \tdiff_debug_queue(\"done copying original\", &outq);\n \n+\t/*\n+\t * Only cache if:\n+\t * - Have a commit hint\n+\t * - diff.cacherenames is on\n+\t * - no pathspec limits\n+\t */\n+\tif (options->commit &&\n+\t DIFF_OPT_TST(options, CACHE_RENAMES) &&\n+\t !options->nr_paths)\n+\t\tsave_rename_cache(&outq, options);\n+\n \tfree(q->queue);\n \tif (cacheq.queue)\n \t\tfree(cacheq.queue);\ndiff --git a/t/t4031-rename-cache.sh b/t/t4031-rename-cache.sh\nindex f7c53fd..2d3f993 100755\n--- a/t/t4031-rename-cache.sh\n+++ b/t/t4031-rename-cache.sh\n@@ -53,4 +53,40 @@ test_expect_success 'load create pair cache' '\n \ttest_cmp expected result\n '\n \n+cat >expected < /dev/null\n+\ttest_cmp expected $P\n+'\n+\n+test_expect_success 'do not save rename cache with limited pathspec' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\")\n+\techo $P\n+\trm $P\n+\tgit config diff.cacherenames true\n+\tgit log --summary -C -M --find-copies-harder HEAD -- sub\n+\t! test -f $P\n+'\n+\n+test_expect_success 'subsequent command does not change cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\")\n+\techo corrupted > $P\n+\t! test_cmp expected $P &&\n+\tgit show --summary -C -M --find-copies-harder HEAD > /dev/null &&\n+\t! test_cmp expected $P\n+'\n+\n+test_expect_success 'overwrite cache with --refresh-rename-cache' '\n+\tP=.git/rename-cache/$(git rev-parse HEAD|sed \"s,\\(..\\)\\(.*\\),\\1/\\2,\")\n+\t! test_cmp expected $P &&\n+\tgit show --summary -C -M --find-copies-harder --refresh-rename-cache HEAD > /dev/null &&\n+\ttest_cmp expected $P\n+'\n+\n test_done\n-- \n1.6.0.3.892.g83538\n"}]}