threads / patch / 26223

patch, 3 partsdiffcore-rename: fall back to -C when -C -C busts the rename limit

Subject: [PATCH 3/3] diffcore-rename: fall back to -C when -C -C busts the rename limit

## tl;dr

5 messages between Jan 6, 2011 and Jan 6, 2011. Diffs are folded; open one to read it.

replies: 4people: 2as markdown or json

Junio C Hamano· Jan 6, 2011, 21:50 UTC · lore

[PATCH 0/3] Falling back "diff -C -C" to "diff -C" more gracefully

In a project with many paths, "diff -C -C" may have too many rename source candidates (as it tries to use all existing paths) but the rename source candidates "diff -C" would use may still fit under the rename detection limit. Currently, we punt and disable the inexact rename detection altogether even in such a case.

This weatherballoon series illustrates how diffcore-rename can be tweaked to allow "-C -C" to fall back to "-C". Somebody should write a test, but not today ;-).

Junio C Hamano (3):
  diffcore-rename: refactor "too many candidates" logic
  diffcore-rename: record filepair for rename src
  diffcore-rename: fall back to -C when -C -C busts the rename limit

 diffcore-rename.c |   97 ++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 71 insertions(+), 26 deletions(-)

-- 
1.7.4.rc1.214.g2a4f9

Junio C Hamano· Jan 6, 2011, 21:50 UTC · re: Junio C Hamano · lore

[PATCH 1/3] diffcore-rename: refactor "too many candidates" logic

Move the logic to a separate function, to be enhanced by later patches in the series.

While at it, swap the condition used in the if statement from "if it is too big then do this" to "if it would fit then do this".

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 diffcore-rename.c |   39 +++++++++++++++++++++++++--------------
 1 files changed, 25 insertions(+), 14 deletions(-)

Show changes to diffcore-rename.c +25 −14

diff --git a/diffcore-rename.c b/diffcore-rename.c
index df41be5..6ab050d 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -414,11 +414,34 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)
 		m[worst] = *o;
 }
 
+static int too_many_rename_candidates(int num_create,
+				      struct diff_options *options)
+{
+	int rename_limit = options->rename_limit;
+	int num_src = rename_src_nr;
+
+	/*
+	 * This basically does a test for the rename matrix not
+	 * growing larger than a "rename_limit" square matrix, ie:
+	 *
+	 *    num_create * num_src > rename_limit * rename_limit
+	 *
+	 * but handles the potential overflow case specially (and we
+	 * assume at least 32-bit integers)
+	 */
+	if (rename_limit <= 0 || rename_limit > 32767)
+		rename_limit = 32767;
+	if ((num_create <= rename_limit || num_src <= rename_limit) &&
+	    (num_create * num_src <= rename_limit * rename_limit))
+		return 0;
+
+	return 1;
+}
+
 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_score *mx;
@@ -484,19 +507,7 @@ void diffcore_rename(struct diff_options *options)
 	if (!num_create)
 		goto cleanup;
 
-	/*
-	 * This basically does a test for the rename matrix not
-	 * growing larger than a "rename_limit" square matrix, ie:
-	 *
-	 *    num_create * num_src > rename_limit * rename_limit
-	 *
-	 * but handles the potential overflow case specially (and we
-	 * assume at least 32-bit integers)
-	 */
-	if (rename_limit <= 0 || rename_limit > 32767)
-		rename_limit = 32767;
-	if ((num_create > rename_limit && num_src > rename_limit) ||
-	    (num_create * num_src > rename_limit * rename_limit)) {
+	if (too_many_rename_candidates(num_create, options)) {
 		if (options->warn_on_too_large_rename)
 			warning("too many files (created: %d deleted: %d), skipping inexact rename detection", num_create, num_src);
 		goto cleanup;

-- 
1.7.4.rc1.214.g2a4f9

Junio C Hamano· Jan 6, 2011, 21:50 UTC · re: Junio C Hamano · lore

[PATCH 2/3] diffcore-rename: record filepair for rename src

This will allow us to later skip unmodified entries added due to "-C -C". We might also want to do something similar to rename_dst side, but that would only be for the sake of symmetry and not necessary for this series.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 diffcore-rename.c |   23 ++++++++++++-----------
 1 files changed, 12 insertions(+), 11 deletions(-)

Show changes to diffcore-rename.c +12 −11

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 6ab050d..9ce81b6 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -54,22 +54,23 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
 
 /* Table of rename/copy src files */
 static struct diff_rename_src {
-	struct diff_filespec *one;
+	struct diff_filepair *p;
 	unsigned short score; /* to remember the break score */
 } *rename_src;
 static int rename_src_nr, rename_src_alloc;
 
-static struct diff_rename_src *register_rename_src(struct diff_filespec *one,
-						   unsigned short score)
+static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
 {
 	int first, last;
+	struct diff_filespec *one = p->one;
+	unsigned short score = p->score;
 
 	first = 0;
 	last = rename_src_nr;
 	while (last > first) {
 		int next = (last + first) >> 1;
 		struct diff_rename_src *src = &(rename_src[next]);
-		int cmp = strcmp(one->path, src->one->path);
+		int cmp = strcmp(one->path, src->p->one->path);
 		if (!cmp)
 			return src;
 		if (cmp < 0) {
@@ -89,7 +90,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filespec *one,
 	if (first < rename_src_nr)
 		memmove(rename_src + first + 1, rename_src + first,
 			(rename_src_nr - first - 1) * sizeof(*rename_src));
-	rename_src[first].one = one;
+	rename_src[first].p = p;
 	rename_src[first].score = score;
 	return &(rename_src[first]);
 }
@@ -204,7 +205,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)
 	if (rename_dst[dst_index].pair)
 		die("internal error: dst already matched.");
 
-	src = rename_src[src_index].one;
+	src = rename_src[src_index].p->one;
 	src->rename_used++;
 	src->count++;
 
@@ -384,7 +385,7 @@ static int find_exact_renames(void)
 
 	init_hash(&file_table);
 	for (i = 0; i < rename_src_nr; i++)
-		insert_file_table(&file_table, -1, i, rename_src[i].one);
+		insert_file_table(&file_table, -1, i, rename_src[i].p->one);
 
 	for (i = 0; i < rename_dst_nr; i++)
 		insert_file_table(&file_table, 1, i, rename_dst[i].two);
@@ -472,7 +473,7 @@ void diffcore_rename(struct diff_options *options)
 			 */
 			if (p->broken_pair && !p->score)
 				p->one->rename_used++;
-			register_rename_src(p->one, p->score);
+			register_rename_src(p);
 		}
 		else if (detect_rename == DIFF_DETECT_COPY) {
 			/*
@@ -480,7 +481,7 @@ void diffcore_rename(struct diff_options *options)
 			 * one, to indicate ourselves as a user.
 			 */
 			p->one->rename_used++;
-			register_rename_src(p->one, p->score);
+			register_rename_src(p);
 		}
 	}
 	if (rename_dst_nr == 0 || rename_src_nr == 0)
@@ -526,7 +527,7 @@ void diffcore_rename(struct diff_options *options)
 			m[j].dst = -1;
 
 		for (j = 0; j < rename_src_nr; j++) {
-			struct diff_filespec *one = rename_src[j].one;
+			struct diff_filespec *one = rename_src[j].p->one;
 			struct diff_score this_src;
 			this_src.score = estimate_similarity(one, two,
 							     minimum_score);
@@ -556,7 +557,7 @@ void diffcore_rename(struct diff_options *options)
 		dst = &rename_dst[mx[i].dst];
 		if (dst->pair)
 			continue; /* already done, either exact or fuzzy. */
-		if (rename_src[mx[i].src].one->rename_used)
+		if (rename_src[mx[i].src].p->one->rename_used)
 			continue;
 		record_rename_pair(mx[i].dst, mx[i].src, mx[i].score);
 		rename_count++;

-- 
1.7.4.rc1.214.g2a4f9

Junio C Hamano· Jan 6, 2011, 21:50 UTC · re: Junio C Hamano · lore

When there are too many paths in the project, the number of rename source candidates "git diff -C -C" finds will exceed the rename detection limit, and no inexact rename detection is performed. We however could fall back to "git diff -C" if the number of paths modified are sufficiently small.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 diffcore-rename.c |   37 +++++++++++++++++++++++++++++++++++--
 1 files changed, 35 insertions(+), 2 deletions(-)

Show changes to diffcore-rename.c +35 −2

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 9ce81b6..4851af3 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -415,11 +415,18 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)
 		m[worst] = *o;
 }
 
+/*
+ * Returns:
+ * 0 if we are under the limit;
+ * 1 if we need to disable inexact rename detection;
+ * 2 if we would be under the limit if we were given -C instead of -C -C.
+ */
 static int too_many_rename_candidates(int num_create,
 				      struct diff_options *options)
 {
 	int rename_limit = options->rename_limit;
 	int num_src = rename_src_nr;
+	int i;
 
 	/*
 	 * This basically does a test for the rename matrix not
@@ -436,6 +443,19 @@ static int too_many_rename_candidates(int num_create,
 	    (num_create * num_src <= rename_limit * rename_limit))
 		return 0;
 
+	/* Are we running under -C -C? */
+	if (!DIFF_OPT_TST(options, FIND_COPIES_HARDER))
+		return 1;
+
+	/* Would we bust the limit if we were running under -C? */
+	for (num_src = i = 0; i < rename_src_nr; i++) {
+		if (diff_unmodified_pair(rename_src[i].p))
+			continue;
+		num_src++;
+	}
+	if ((num_create <= rename_limit || num_src <= rename_limit) &&
+	    (num_create * num_src <= rename_limit * rename_limit))
+		return 2;
 	return 1;
 }
 
@@ -446,7 +466,7 @@ void diffcore_rename(struct diff_options *options)
 	struct diff_queue_struct *q = &diff_queued_diff;
 	struct diff_queue_struct outq;
 	struct diff_score *mx;
-	int i, j, rename_count;
+	int i, j, rename_count, skip_unmodified = 0;
 	int num_create, num_src, dst_cnt;
 
 	if (!minimum_score)
@@ -508,10 +528,18 @@ void diffcore_rename(struct diff_options *options)
 	if (!num_create)
 		goto cleanup;
 
-	if (too_many_rename_candidates(num_create, options)) {
+	switch (too_many_rename_candidates(num_create, options)) {
+	case 1:
 		if (options->warn_on_too_large_rename)
 			warning("too many files (created: %d deleted: %d), skipping inexact rename detection", num_create, num_src);
 		goto cleanup;
+	case 2:
+		if (options->warn_on_too_large_rename)
+			warning("too many files, falling back to -C");
+		skip_unmodified = 1;
+		break;
+	default:
+		break;
 	}
 
 	mx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));
@@ -529,6 +557,11 @@ void diffcore_rename(struct diff_options *options)
 		for (j = 0; j < rename_src_nr; j++) {
 			struct diff_filespec *one = rename_src[j].p->one;
 			struct diff_score this_src;
+
+			if (skip_unmodified &&
+			    diff_unmodified_pair(rename_src[j].p))
+				continue;
+
 			this_src.score = estimate_similarity(one, two,
 							     minimum_score);
 			this_src.name_score = basename_same(one, two);

-- 
1.7.4.rc1.214.g2a4f9

Jeff King· Jan 6, 2011, 22:28 UTC · re: Junio C Hamano · lore

Re: [PATCH 0/3] Falling back "diff -C -C" to "diff -C" more gracefully

On Thu, Jan 06, 2011 at 01:50:03PM -0800, Junio C Hamano wrote:

> Junio C Hamano (3):
>   diffcore-rename: refactor "too many candidates" logic
>   diffcore-rename: record filepair for rename src
>   diffcore-rename: fall back to -C when -C -C busts the rename limit

I read through the series, and it looks good to me. I didn't do any testing, though. :)

-Peff