Nguyễn Thái Ngọc DuyThis patch teaches diffcore_rename() to look into $GIT_DIR/rename-cache and make use of it to recreate diff_filepair. With proper cache, there should be no available entry for estimation after exact matching.
Rename caching is per commit. I don't think abitrary tree-tree caching is worth it.
$GIT_DIR/rename-cache spans out like $GIT_DIR/objects. Each file corresponds to one commit. Its content consists of lines like this
<Destination SHA-1> <SPC> <Source SHA-1> <SPC> <Score in decimal> <NL>
This can be used to:
- Make --find-copies-harder pratically usable for moderate-size repositories. The first "git show" on a linux kernel commit was 5.3 sec, it then went down to 0.13 sec. - Give git-svn a chance to (locally) import explicit renames from Subversion - People may correct rename results for better diff, if automatic rename detection is not good enough.
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> --- diff.h | 2 + diffcore-rename.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++- log-tree.c | 2 + t/t4030-rename-cache.sh | 55 ++++++++++++++++++ 4 files changed, 199 insertions(+), 2 deletions(-) create mode 100755 t/t4030-rename-cache.sh
Show changes to 4 files +199 −2
diff.h, diffcore-rename.c, log-tree.c, t/t4030-rename-cache.sh
diff --git a/diff.h b/diff.h index a49d865..8b68f6f 100644 --- a/diff.h +++ b/diff.h @@ -110,6 +110,8 @@ struct diff_options { add_remove_fn_t add_remove; diff_format_fn_t format_callback; void *format_callback_data; + + struct commit *commit; }; enum color_diff { diff --git a/diffcore-rename.c b/diffcore-rename.c index 168a95b..598cc8d 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -5,6 +5,7 @@ #include "diff.h" #include "diffcore.h" #include "hash.h" +#include "commit.h" /* Table of rename/copy destinations */ @@ -409,13 +410,130 @@ static void record_if_better(struct diff_score m[], struct diff_score *o) m[worst] = *o; } +struct cached_filepair { + unsigned char dst[20]; + unsigned char src[20]; + int score; +}; + +static int free_cached_filepair(void *p) +{ + free(p); + return 0; +} + +static void load_rename_cache(struct diff_queue_struct *q, + struct diff_queue_struct *cacheq, + struct diff_options *options) +{ + char *sha1_hex; + FILE *fp; + struct hash_table filepair_table; + struct hash_table src_table; + struct cached_filepair *pp; + int i, hash; + static int no_cache_available = -1; + struct stat st; + char *path; + + if (no_cache_available == -1) + no_cache_available = stat(git_path("rename-cache"), &st) || !S_ISDIR(st.st_mode); + + /* return soon so we don't need to waste CPU */ + if (no_cache_available > 0) + return; + + + /* src_table initialization */ + init_hash(&src_table); + for (i = 0; i < q->nr; i++) { + struct diff_filepair *p = q->queue[i]; + if (DIFF_FILE_VALID(p->one)) { + unsigned int hash = hash_filespec(p->one); + insert_hash(hash, p, &src_table); + } + } + + /* filepair_table initialization */ + init_hash(&filepair_table); + sha1_hex = sha1_to_hex(options->commit->object.sha1); + path = git_path("rename-cache/%c%c/%s",sha1_hex[0], sha1_hex[1], sha1_hex+2); + if (stat(path, &st)) + fp = NULL; + else + fp = fopen(path, "r"); + if (fp) { + char src_sha1_hex[41], dst_sha1_hex[41]; + struct cached_filepair p; + + src_sha1_hex[40] = dst_sha1_hex[40] = '\0'; + while (fscanf(fp, "%40c %40c %d\n", dst_sha1_hex, src_sha1_hex, &p.score) == 3) { + if (get_sha1_hex(src_sha1_hex, p.src) || + get_sha1_hex(dst_sha1_hex, p.dst)) + break; + + pp = xmalloc(sizeof(*pp)); + memcpy(pp, &p, sizeof(*pp)); + memcpy(&hash, p.dst, sizeof(hash)); + insert_hash(hash, pp, &filepair_table); + } + fclose(fp); + } + + for (i = 0; i < q->nr; i++) { + struct diff_filepair *p = q->queue[i]; + struct diff_filepair *dp, *src; + + /* find remote_dst */ + if (DIFF_FILE_VALID(p->one) || + !DIFF_FILE_VALID(p->two) || + (options->single_follow && strcmp(options->single_follow, p->two->path))) + continue; + + memcpy(&hash, p->two->sha1, sizeof(hash)); + pp = lookup_hash(hash, &filepair_table); + if (!pp || memcmp(p->two->sha1, pp->dst, 20)) + continue; + + /* create pair */ + if (is_null_sha1(pp->src)) { + if (DIFF_FILE_VALID(p->one)) + continue; + diff_q(cacheq, p); + q->queue[i] = NULL; + continue; + } + + memcpy(&hash, pp->src, sizeof(hash)); + src = lookup_hash(hash, &src_table); + if (!src || memcmp(pp->src, src->one->sha1, 20)) + continue; + + src->one->rename_used++; + src->one->count++; + p->two->count++; + + dp = diff_queue(NULL, src->one, p->two); + dp->renamed_pair = 1; + dp->score = pp->score; + + diff_q(cacheq, dp); + q->queue[i] = NULL; + diff_free_filepair(p); + } + + for_each_hash(&filepair_table, free_cached_filepair); + free_hash(&src_table); + free_hash(&filepair_table); +} + void diffcore_rename(struct diff_options *options) { int detect_rename = options->detect_rename; int minimum_score = options->rename_score; int rename_limit = options->rename_limit; struct diff_queue_struct *q = &diff_queued_diff; - struct diff_queue_struct outq; + struct diff_queue_struct outq, cacheq; struct diff_score *mx; int i, j, rename_count; int num_create, num_src, dst_cnt; @@ -423,8 +541,19 @@ void diffcore_rename(struct diff_options *options) if (!minimum_score) minimum_score = DEFAULT_RENAME_SCORE; + cacheq.queue = NULL; + cacheq.nr = cacheq.alloc = 0; + + if (detect_rename && options->commit) + load_rename_cache(q, &cacheq, options); + for (i = 0; i < q->nr; i++) { struct diff_filepair *p = q->queue[i]; + + /* was consumed by rename cache */ + if (!p) + continue; + if (!DIFF_FILE_VALID(p->one)) { if (!DIFF_FILE_VALID(p->two)) continue; /* unmerged */ @@ -563,10 +692,17 @@ void diffcore_rename(struct diff_options *options) */ outq.queue = NULL; outq.nr = outq.alloc = 0; - for (i = 0; i < q->nr; i++) { + for (i = j = 0; i < q->nr; i++) { struct diff_filepair *p = q->queue[i]; struct diff_filepair *pair_to_free = NULL; + if (!p) { + if (j >= cacheq.nr) + die("Internal error: running out of cacheq."); + diff_q(&outq, cacheq.queue[j++]); + continue; + } + if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) { /* * Creation @@ -635,6 +771,8 @@ void diffcore_rename(struct diff_options *options) diff_debug_queue("done copying original", &outq); free(q->queue); + if (cacheq.queue) + free(cacheq.queue); *q = outq; diff_debug_queue("done collapsing", q); diff --git a/log-tree.c b/log-tree.c index cec3c06..a67ef6d 100644 --- a/log-tree.c +++ b/log-tree.c @@ -518,6 +518,7 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit) log.commit = commit; log.parent = NULL; opt->loginfo = &log; + opt->diffopt.commit = commit; shown = log_tree_diff(opt, commit, &log); if (!shown && opt->loginfo && opt->always_show_header) { @@ -527,5 +528,6 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit) } opt->loginfo = NULL; maybe_flush_or_die(stdout, "stdout"); + opt->diffopt.commit = NULL; return shown; } diff --git a/t/t4030-rename-cache.sh b/t/t4030-rename-cache.sh new file mode 100755 index 0000000..0d8390c --- /dev/null +++ b/t/t4030-rename-cache.sh @@ -0,0 +1,55 @@ +#!/bin/sh +# +# Copyright (c) 2008 Nguyen Thai Ngoc Duy +# + +test_description='Test diff rename cache' +. ./test-lib.sh + +cat >expected <<EOF + create mode 100644 c + copy a => d (100%) +EOF +test_expect_success 'setup' ' + for i in a b c + do + echo $i > $i + done + cp a d + A_SHA1=$(git hash-object a) + B_SHA1=$(git hash-object b) + C_SHA1=$(git hash-object c) + D_SHA1=$(git hash-object d) + git add a b + git commit -m first + git add c d + git commit -m second + git show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result + test_cmp expected result +' + +cat >expected <<EOF + copy a => c (100%) + copy a => d (100%) +EOF +test_expect_success 'load rename pair cache' ' + P=.git/rename-cache/$(git rev-parse HEAD|sed "s,\(..\)\(.*\),\1/\2,") && + mkdir -p $(dirname $P) + echo $C_SHA1 $A_SHA1 60000 >> $P + git show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result + test_cmp expected result +' + +cat >expected <<EOF + copy a => c (100%) + create mode 100644 d +EOF +test_expect_success 'load create pair cache' ' + P=.git/rename-cache/$(git rev-parse HEAD|sed "s,\(..\)\(.*\),\1/\2,") && + mkdir -p $(dirname $P) + echo $D_SHA1 0000000000000000000000000000000000000000 0 >> $P + git show --pretty=oneline --summary -C -M --find-copies-harder HEAD|sed 1d > result + test_cmp expected result +' + +test_done
-- 1.6.0.3.802.g47c38
