[PATCH] Detect renames in diff family.

This rips out the rename detection engine from diff-helper and moves it
to the diff core, and updates the internal calling convention used by
diff-tree family into the diff core.  In order to give the same option
name to diff-tree family as well as to diff-helper, I've changed the
earlier diff-helper '-r' option to '-M' (stands for Move; sorry but the
natural abbreviation 'r' for 'rename' is already taken for 'recursive').

Although I did a fair amount of test with the git-diff-tree with
existing rename commits in the core GIT repository, this should still be
considered beta (preview) release.  This patch depends on the diff-delta
infrastructure just committed.

This implements almost everything I wanted to see in this series of
patch, except a few minor cleanups in the calling convention into diff
core, but that will be a separate cleanup patch.

Signed-off-by: Junio C Hamano <junkio@cox.net>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

1 files changed, 29 insertions, 180 deletions

diff --git a/diff-helper.c b/diff-helper.c
index 2877ddc..5b0feb1 100644
--- a/diff-helper.c
+++ b/diff-helper.c
@@ -6,160 +6,23 @@
 #include "strbuf.h"
 #include "diff.h"
 
-static int matches_pathspec(const char *name, const char **spec, int cnt)
-{
-	int i;
-	int namelen = strlen(name);
-	for (i = 0; i < cnt; i++) {
-		int speclen = strlen(spec[i]);
-		if (! strncmp(spec[i], name, speclen) &&
-		    speclen <= namelen &&
-		    (name[speclen] == 0 ||
-		     name[speclen] == '/'))
-			return 1;
-	}
-	return 0;
-}
-
 static int detect_rename = 0;
 
-/*
- * We do not detect circular renames.  Just hold created and deleted
- * entries and later attempt to match them up.  If they do not match,
- * then spit them out as deletes or creates as original.
- */
-
-static struct diff_spec_hold {
-	struct diff_spec_hold *next;
-	struct diff_spec_hold *matched;
-	struct diff_spec old, new;
-	char path[1];
-} *createdfile, *deletedfile;
-
-static void hold_spec(const char *path,
-		      struct diff_spec *old, struct diff_spec *new)
-{
-	struct diff_spec_hold **list, *elem;
-	list = (! old->file_valid) ? &createdfile : &deletedfile;
-	elem = xmalloc(sizeof(*elem) + strlen(path));
-	strcpy(elem->path, path);
-	elem->next = *list;
-	*list = elem;
-	elem->old = *old;
-	elem->new = *new;
-	elem->matched = 0;
-}
-
-#define MINIMUM_SCORE 7000
-int estimate_similarity(struct diff_spec *one, struct diff_spec *two)
-{
-	/* Return how similar they are, representing the score as an
-	 * integer between 0 and 10000.
-	 *
-	 * This version is very dumb and detects exact matches only.
-	 * Wnen Nico's delta stuff gets in, I'll use the delta
-	 * algorithm to estimate the similarity score in core.
-	 */
-
-	if (one->sha1_valid && two->sha1_valid &&
-	    !memcmp(one->blob_sha1, two->blob_sha1, 20))
-		return 10000;
-	return 0;
-}
-
-static void flush_renames(const char **spec, int cnt, int reverse)
-{
-	struct diff_spec_hold *rename_src, *rename_dst, *elem;
-	struct diff_spec_hold *leftover = NULL;
-	int score, best_score;
-
-	while (createdfile) {
-		rename_dst = createdfile;
-		createdfile = rename_dst->next;
-		best_score = MINIMUM_SCORE;
-		rename_src = NULL;
-		for (elem = deletedfile;
-		     elem;
-		     elem = elem->next) {
-			if (elem->matched)
-				continue;
-			score = estimate_similarity(&elem->old,
-						    &rename_dst->new);
-			if (best_score < score) {
-				rename_src = elem;
-				best_score = score;
-			}
-		}
-		if (rename_src) {
-			rename_src->matched = rename_dst;
-			rename_dst->matched = rename_src;
-
-			if (!cnt ||
-			    matches_pathspec(rename_src->path, spec, cnt) ||
-			    matches_pathspec(rename_dst->path, spec, cnt)) {
-				if (reverse)
-					run_external_diff(rename_dst->path,
-							  rename_src->path,
-							  &rename_dst->new,
-							  &rename_src->old);
-				else
-					run_external_diff(rename_src->path,
-							  rename_dst->path,
-							  &rename_src->old,
-							  &rename_dst->new);
-			}
-		}
-		else {
-			rename_dst->next = leftover;
-			leftover = rename_dst;
-		}
-	}
-
-	/* unmatched deletes */
-	for (elem = deletedfile; elem; elem = elem->next) {
-		if (elem->matched)
-			continue;
-		if (!cnt ||
-		    matches_pathspec(elem->path, spec, cnt)) {
-			if (reverse)
-				run_external_diff(elem->path, NULL,
-						  &elem->new, &elem->old);
-			else
-				run_external_diff(elem->path, NULL,
-						  &elem->old, &elem->new);
-		}
-	}
-
-	/* unmatched creates */
-	for (elem = leftover; elem; elem = elem->next) {
-		if (!cnt ||
-		    matches_pathspec(elem->path, spec, cnt)) {
-			if (reverse)
-				run_external_diff(elem->path, NULL,
-						  &elem->new, &elem->old);
-			else
-				run_external_diff(elem->path, NULL,
-						  &elem->old, &elem->new);
-		}
-	}
-}
-
-static int parse_oneside_change(const char *cp, struct diff_spec *one,
-				char *path)
+static int parse_oneside_change(const char *cp, int *mode,
+				unsigned char *sha1, char *path)
 {
-	int ch;
+	int ch, m;
 
-	one->file_valid = one->sha1_valid = 1;
-	one->mode = 0;
+	m = 0;
 	while ((ch = *cp) && '0' <= ch && ch <= '7') {
-		one->mode = (one->mode << 3) | (ch - '0');
+		m = (m << 3) | (ch - '0');
 		cp++;
 	}
-
+	*mode = m;
 	if (strncmp(cp, "\tblob\t", 6))
 		return -1;
 	cp += 6;
-	if (get_sha1_hex(cp, one->blob_sha1))
+	if (get_sha1_hex(cp, sha1))
 		return -1;
 	cp += 40;
 	if (*cp++ != '\t')
@@ -168,79 +31,63 @@ static int parse_oneside_change(const char *cp, struct diff_spec *one,
 	return 0;
 }
 
-static int parse_diff_raw_output(const char *buf,
-				 const char **spec, int cnt, int reverse)
+static int parse_diff_raw_output(const char *buf)
 {
-	struct diff_spec old, new;
 	char path[PATH_MAX];
+	unsigned char old_sha1[20], new_sha1[20];
 	const char *cp = buf;
-	int ch;
+	int ch, old_mode, new_mode;
 
 	switch (*cp++) {
 	case 'U':
-		if (!cnt || matches_pathspec(cp + 1, spec, cnt))
-			diff_unmerge(cp + 1);
-		return 0;
+		diff_unmerge(cp + 1);
+		break;
 	case '+':
-		old.file_valid = 0;
-		parse_oneside_change(cp, &new, path);
+		parse_oneside_change(cp, &new_mode, new_sha1, path);
+		diff_addremove('+', new_mode, new_sha1, path, NULL);
 		break;
 	case '-':
-		new.file_valid = 0;
-		parse_oneside_change(cp, &old, path);
+		parse_oneside_change(cp, &old_mode, old_sha1, path);
+		diff_addremove('-', old_mode, old_sha1, path, NULL);
 		break;
 	case '*':
-		old.file_valid = old.sha1_valid =
-			new.file_valid = new.sha1_valid = 1;
-		old.mode = new.mode = 0;
+		old_mode = new_mode = 0;
 		while ((ch = *cp) && ('0' <= ch && ch <= '7')) {
-			old.mode = (old.mode << 3) | (ch - '0');
+			old_mode = (old_mode << 3) | (ch - '0');
 			cp++;
 		}
 		if (strncmp(cp, "->", 2))
 			return -1;
 		cp += 2;
 		while ((ch = *cp) && ('0' <= ch && ch <= '7')) {
-			new.mode = (new.mode << 3) | (ch - '0');
+			new_mode = (new_mode << 3) | (ch - '0');
 			cp++;
 		}
 		if (strncmp(cp, "\tblob\t", 6))
 			return -1;
 		cp += 6;
-		if (get_sha1_hex(cp, old.blob_sha1))
+		if (get_sha1_hex(cp, old_sha1))
 			return -1;
 		cp += 40;
 		if (strncmp(cp, "->", 2))
 			return -1;
 		cp += 2;
-		if (get_sha1_hex(cp, new.blob_sha1))
+		if (get_sha1_hex(cp, new_sha1))
 			return -1;
 		cp += 40;
 		if (*cp++ != '\t')
 			return -1;
 		strcpy(path, cp);
+		diff_change(old_mode, new_mode, old_sha1, new_sha1, path, 0);
 		break;
 	default:
 		return -1;
 	}
-
-	if (detect_rename && old.file_valid != new.file_valid) {
-		/* hold these */
-		hold_spec(path, &old, &new);
-		return 0;
-	}
-
-	if (!cnt || matches_pathspec(path, spec, cnt)) {
-		if (reverse)
-			run_external_diff(path, NULL, &new, &old);
-		else
-			run_external_diff(path, NULL, &old, &new);
-	}
 	return 0;
 }
 
 static const char *diff_helper_usage =
-	"git-diff-helper [-r] [-R] [-z] paths...";
+	"git-diff-helper [-z] [-R] [-M] paths...";
 
 int main(int ac, const char **av) {
 	struct strbuf sb;
@@ -254,7 +101,7 @@ int main(int ac, const char **av) {
 			reverse = 1;
 		else if (av[1][1] == 'z')
 			line_termination = 0;
-		else if (av[1][1] == 'r')
+		else if (av[1][1] == 'M')
 			detect_rename = 1;
 		else
 			usage(diff_helper_usage);
@@ -262,18 +109,20 @@ int main(int ac, const char **av) {
 	}
 	/* the remaining parameters are paths patterns */
 
+	diff_setup(detect_rename, 0, reverse, av+1, ac-1);
+
 	while (1) {
 		int status;
 		read_line(&sb, stdin, line_termination);
 		if (sb.eof)
 			break;
-		status = parse_diff_raw_output(sb.buf, av+1, ac-1, reverse);
+		status = parse_diff_raw_output(sb.buf);
 		if (status) {
-			flush_renames(av+1, ac-1, reverse);
+			diff_flush();
 			printf("%s%c", sb.buf, line_termination);
 		}
 	}
 
-	flush_renames(av+1, ac-1, reverse);
+	diff_flush();
 	return 0;
 }