git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 1/2] diffcore-rename: support rename cache

From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Date
Nov 7, 2008, 14:35 UTC
Message-ID
<1226068533-10152-1-git-send-email-pclouds@gmail.com>

This 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
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
Next: Nguyễn Thái Ngọc Duy
Message 1 of 10 in “diffcore-rename: support rename cache”
  1. 1/2 diffcore-rename: support rename cacheNguyễn Thái Ngọc Duy, Nov 7, 2008
  2. 2/2 diffcore-rename: add config option to allow to cache renamesNguyễn Thái Ngọc Duy, Nov 7, 2008
  3. Yann DirsonNov 7, 2008
  4. Junio C HamanoNov 7, 2008
  5. Nguyen Thai Ngoc DuyNov 8, 2008
  6. Yann DirsonNov 8, 2008
  7. Nguyen Thai Ngoc DuyNov 8, 2008
  8. Jeff KingNov 8, 2008
  9. Nguyen Thai Ngoc DuyNov 8, 2008
  10. Jeff KingNov 9, 2008

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.