Diff: -l<num> to limit rename/copy detection.

When many paths are modified, rename detection takes a lot of time.
The new option -l<num> can be used to disable rename detection when
more than <num> paths are possibly created as renames.

Signed-off-by: Junio C Hamano <junkio@cox.net>

5 files changed, 34 insertions, 20 deletions

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 48cf93cc38..616d4a4122 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -35,6 +35,13 @@
 	copy.  This is a very expensive operation for large
 	projects, so use it with caution.
 
+-l<num>::
+	-M and -C options require O(n^2) processing time where n
+	in the number of potential rename/copy targets.  This
+	option prevents rename/copy detection from running if
+	the number of rename/copy targets exceed the specified
+	number.
+
 -S<string>::
 	Look for differences that contains the change in <string>.
 
diff --git a/diff.c b/diff.c
index 77d3166712..cafc755406 100644
--- a/diff.c
+++ b/diff.c
@@ -674,11 +674,12 @@ void diff_setup(struct diff_options *options)
 	options->output_format = DIFF_FORMAT_RAW;
 	options->line_termination = '\n';
 	options->break_opt = -1;
+	options->rename_limit = -1;
 }
 
 int diff_setup_done(struct diff_options *options)
 {
-	if (options->find_copies_harder &&
+	if ((options->find_copies_harder || 0 <= options->rename_limit) &&
 	    options->detect_rename != DIFF_DETECT_COPY)
 		return -1;
 	if (options->setup & DIFF_SETUP_USE_CACHE) {
@@ -704,6 +705,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->output_format = DIFF_FORMAT_PATCH;
 	else if (!strcmp(arg, "-z"))
 		options->line_termination = 0;
+	else if (!strncmp(arg, "-l", 2))
+		options->rename_limit = strtoul(arg+2, NULL, 10);
 	else if (!strcmp(arg, "--name-only"))
 		options->output_format = DIFF_FORMAT_NAME;
 	else if (!strcmp(arg, "-R"))
@@ -1141,7 +1144,7 @@ void diffcore_std(struct diff_options *options)
 	if (options->break_opt != -1)
 		diffcore_break(options->break_opt);
 	if (options->detect_rename)
-		diffcore_rename(options->detect_rename, options->rename_score);
+		diffcore_rename(options);
 	if (options->break_opt != -1)
 		diffcore_merge_broken();
 	if (options->pickaxe)
diff --git a/diff.h b/diff.h
index 5800f15a33..2e32870901 100644
--- a/diff.h
+++ b/diff.h
@@ -21,6 +21,7 @@ struct diff_options {
 	int pickaxe_opts;
 	int rename_score;
 	int reverse_diff;
+	int rename_limit;
 	int setup;
 };
 
@@ -61,23 +62,22 @@ extern void diffcore_std_no_resolve(struct diff_options *);
 
 #define COMMON_DIFF_OPTIONS_HELP \
 "\ncommon diff options:\n" \
-"  -r		diff recursively (only meaningful in diff-tree)\n" \
-"  -z		output diff-raw with lines terminated with NUL.\n" \
-"  -p		output patch format.\n" \
-"  -u		synonym for -p.\n" \
-"  --name-only	show only names of changed files.\n" \
-"  --name-only-z\n" \
-"		same as --name-only but terminate lines with NUL.\n" \
-"  -R		swap input file pairs.\n" \
-"  -B		detect complete rewrites.\n" \
-"  -M		detect renames.\n" \
-"  -C		detect copies.\n" \
+"  -r            diff recursively (only meaningful in diff-tree)\n" \
+"  -z            output diff-raw with lines terminated with NUL.\n" \
+"  -p            output patch format.\n" \
+"  -u            synonym for -p.\n" \
+"  --name-only   show only names of changed files.\n" \
+"  -R            swap input file pairs.\n" \
+"  -B            detect complete rewrites.\n" \
+"  -M            detect renames.\n" \
+"  -C            detect copies.\n" \
 "  --find-copies-harder\n" \
-"		try unchanged files as candidate for copy detection.\n" \
-"  -O<file>	reorder diffs according to the <file>.\n" \
-"  -S<string>	find filepair whose only one side contains the string.\n" \
+"                try unchanged files as candidate for copy detection.\n" \
+"  -l<n>         limit rename attempts up to <n> paths.\n" \
+"  -O<file>      reorder diffs according to the <file>.\n" \
+"  -S<string>    find filepair whose only one side contains the string.\n" \
 "  --pickaxe-all\n" \
-"		show all files diff when -S is used and hit is found.\n"
+"                show all files diff when -S is used and hit is found.\n"
 
 extern int diff_queue_is_empty(void);
 
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 092cf68de6..e17dd90058 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -249,8 +249,11 @@ static int compute_stays(struct diff_queue_struct *q,
 	return 1;
 }
 
-void diffcore_rename(int detect_rename, int minimum_score)
+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;
@@ -279,7 +282,8 @@ void diffcore_rename(int detect_rename, int minimum_score)
 		else if (detect_rename == DIFF_DETECT_COPY)
 			register_rename_src(p->one, 1);
 	}
-	if (rename_dst_nr == 0)
+	if (rename_dst_nr == 0 ||
+	    (0 <= rename_limit && rename_limit < rename_dst_nr))
 		goto cleanup; /* nothing to do */
 
 	/* We really want to cull the candidates list early
diff --git a/diffcore.h b/diffcore.h
index f1b5ca748c..a38acb13e1 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -85,7 +85,7 @@ extern void diff_q(struct diff_queue_struct *, struct diff_filepair *);
 
 extern void diffcore_pathspec(const char **pathspec);
 extern void diffcore_break(int);
-extern void diffcore_rename(int rename_copy, int);
+extern void diffcore_rename(struct diff_options *);
 extern void diffcore_merge_broken(void);
 extern void diffcore_pickaxe(const char *needle, int opts);
 extern void diffcore_order(const char *orderfile);