[RFC PATCH v2 0/2] Detection of directory renames

[RFC PATCH v2 0/2] Detection of directory renames

[Yann Dirson]

This is an update of my previous patch.  It brings:
* a couple of fixes to annoying segfaults
* a testsuite showing where we're standing.
* getting rid of POSIX dirname
* improvement of debug messages

The code is still full of FIXME's, not ready for inclusin into any
branch whatsoever, and I'd be happy to hear about it if you can make
it break in a way or another - at least in a way not yet shown by the
testsuite :)

-- 
Yann Dirson    <ydirson@altern.org> |
Debian-related: <dirson@debian.org> |   Support Debian GNU/Linux:
                                    |  Freedom, Power, Stability, Gratis
     http://ydirson.free.fr/        | Check <http://www.debian.org/>

[PATCH 1/2] Introduce rename factorization in diffcore.

[Yann Dirson]

Rename factorization tries to group together files moving from and to
identical directories - the most common case being directory renames.
This feature is activated by the new --factorize-renames diffcore
flag.

This is only the first step, adding the basic functionnality and
adding support to raw diff output (and it breaks unified-diff output
which does not know how to handle that stuff yet).

Even the output format may not be kept as is.  For now both the result
of "mv a b" and "mv a/* b/" are displayed as "Rnnn a/ b/", which is
probably not what we want.  "Rnnn a/* b/" could be a good choice for
the latter if we want them to be distinguished, and even if we want
them to look the same.

Other future developements to be made on top of this include:
* extension of unified-diff format to express this
* application of such new diffs
* teach git-svn (and others ?) to make use of that flag
* merge correctly in case of addition into a moved dir
* detect "directory splits" so merge can flag a conflict on file adds
* use inexact dir renames to bump score of below-threshold renames
  from/to same locations
* add yours here
---

 diff-lib.c        |    6 +
 diff.c            |    5 +
 diff.h            |    3 +
 diffcore-rename.c |  227 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 diffcore.h        |    1 
 tree-diff.c       |    4 +
 6 files changed, 235 insertions(+), 11 deletions(-)

diff --git a/diff-lib.c b/diff-lib.c
index ae96c64..dcc4c2c 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -179,7 +179,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 		changed = ce_match_stat(ce, &st, ce_option);
 		if (!changed) {
 			ce_mark_uptodate(ce);
-			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
+			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
+			    !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))
 				continue;
 		}
 		oldmode = ce->ce_mode;
@@ -310,7 +311,8 @@ static int show_modified(struct oneway_unpack_data *cbdata,
 
 	oldmode = old->ce_mode;
 	if (mode == oldmode && !hashcmp(sha1, old->sha1) &&
-	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
+	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
+	    !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))
 		return 0;
 
 	diff_change(&revs->diffopt, oldmode, mode,
diff --git a/diff.c b/diff.c
index e368fef..f91fcf6 100644
--- a/diff.c
+++ b/diff.c
@@ -2437,6 +2437,11 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		DIFF_OPT_SET(options, REVERSE_DIFF);
 	else if (!strcmp(arg, "--find-copies-harder"))
 		DIFF_OPT_SET(options, FIND_COPIES_HARDER);
+	else if (!strcmp(arg, "--factorize-renames")) {
+		DIFF_OPT_SET(options, FACTORIZE_RENAMES);
+		if (!options->detect_rename)
+			options->detect_rename = DIFF_DETECT_RENAME;
+	}
 	else if (!strcmp(arg, "--follow"))
 		DIFF_OPT_SET(options, FOLLOW_RENAMES);
 	else if (!strcmp(arg, "--color"))
diff --git a/diff.h b/diff.h
index a49d865..db1658b 100644
--- a/diff.h
+++ b/diff.h
@@ -65,6 +65,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_OPT_IGNORE_SUBMODULES   (1 << 18)
 #define DIFF_OPT_DIRSTAT_CUMULATIVE  (1 << 19)
 #define DIFF_OPT_DIRSTAT_BY_FILE     (1 << 20)
+#define DIFF_OPT_FACTORIZE_RENAMES   (1 << 21)
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)
 #define DIFF_OPT_CLR(opts, flag)    ((opts)->flags &= ~DIFF_OPT_##flag)
@@ -220,6 +221,8 @@ extern void diffcore_std(struct diff_options *);
 "  -C            detect copies.\n" \
 "  --find-copies-harder\n" \
 "                try unchanged files as candidate for copy detection.\n" \
+"  --factorize-renames\n" \
+"                factorize renames of all files of a directory.\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" \
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 1b2ebb4..fc789bc 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -52,6 +52,32 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
 	return &(rename_dst[first]);
 }
 
+static struct diff_rename_dst *locate_rename_dst_dir(struct diff_filespec *dir)
+{
+	/* code mostly duplicated from locate_rename_dst - not sure we
+	 * could merge them efficiently,though
+	 */
+	int first, last;
+	int dirlength = strlen(dir->path);
+
+	first = 0;
+	last = rename_dst_nr;
+	while (last > first) {
+		int next = (last + first) >> 1;
+		struct diff_rename_dst *dst = &(rename_dst[next]);
+		int cmp = strncmp(dir->path, dst->two->path, dirlength);
+		if (!cmp)
+			return dst;
+		if (cmp < 0) {
+			last = next;
+			continue;
+		}
+		first = next+1;
+	}
+	/* not found */
+	return NULL;
+}
+
 /* Table of rename/copy src files */
 static struct diff_rename_src {
 	struct diff_filespec *one;
@@ -409,6 +435,165 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)
 		m[worst] = *o;
 }
 
+struct diff_dir_rename {
+	struct diff_filespec *one;
+	struct diff_filespec *two;
+	int discarded;
+	struct diff_dir_rename* next;
+};
+
+/*
+ * Marks as such file_rename if it is made uninteresting by dir_rename.
+ * Returns -1 if the file_rename is outside of the range in which given
+ * renames concerned by dir_rename are to be found (ie. end of loop),
+ * 0 otherwise.
+ */
+static int maybe_mark_uninteresting(struct diff_rename_dst* file_rename,
+				    struct diff_dir_rename* dir_rename,
+				    int one_len, int two_len)
+{
+	if (!file_rename->pair) /* file add */
+		return 0;
+	if (strncmp(file_rename->two->path,
+		    dir_rename->two->path, two_len))
+		return -1;
+	if (strncmp(file_rename->pair->one->path,
+		    dir_rename->one->path, one_len) ||
+	    !basename_same(file_rename->pair->one, file_rename->two) ||
+	    file_rename->pair->score != MAX_SCORE)
+		return 0;
+
+	file_rename->pair->uninteresting_rename = 1;
+	fprintf (stderr, "[DBG] %s* -> %s* makes %s -> %s uninteresting\n",
+		dir_rename->one->path, dir_rename->two->path,
+		file_rename->pair->one->path, file_rename->two->path);
+	return 0;
+}
+
+// FIXME: prevent possible overflow
+/*
+ * Copy dirname of src into dst, with final "/".
+ * Only handles relative paths since there is no relative path in a git repo.
+ * Writes "./" when there is no "/" in src.
+ * May overwrite more chars than really needed, if src ends with a "/".
+ */
+static const char* copy_dirname(char* dst, const char* src)
+{
+	char* lastslash = strrchr(src, '/');
+	if (!lastslash)
+		return strcpy(dst, "./");
+	strncpy(dst, src, lastslash - src + 1);
+	dst[lastslash - src + 1] = '\0';
+
+	// if src ends with a "/" strip the last component
+	if (lastslash[1] == '\0') {
+		lastslash = strrchr(dst, '/');
+		if (!lastslash)
+			return strcpy(dst, ".");
+		lastslash[1] = '\0';
+	}
+
+	return dst;
+}
+
+/*
+ * FIXME: we could optimize the 100%-rename case by preventing
+ * recursion to unfold what we know we would refold here.
+ * FIXME: do we want to replace linked list with sorted array ?
+ * FIXME: this prototype only handles renaming of dirs without
+ * a subdir.
+ * FIXME: leaks like hell.
+ * FIXME: ideas to evaluate a similarity score, anyone ?
+ *  10% * tree similarity + 90% * moved files similarity ?
+ */
+static struct diff_dir_rename* factorization_candidates = NULL;
+static void diffcore_factorize_renames(void)
+{
+	char one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];
+	int i;
+
+	for (i = 0; i < rename_dst_nr; i++) {
+		// FIXME: what are those ?
+		if (!rename_dst[i].pair)
+			continue;
+		// dummy renames used by copy detection
+		if (!strcmp(rename_dst[i].pair->one->path, rename_dst[i].pair->two->path))
+			continue;
+
+		copy_dirname(one_parent_path, rename_dst[i].pair->one->path);
+
+		struct diff_filespec* one_parent = alloc_filespec(one_parent_path);
+		fill_filespec(one_parent, null_sha1 /*FIXME*/, S_IFDIR);
+
+		if (!locate_rename_dst_dir(one_parent)) {
+			// one_parent_path is empty in result tree
+
+			// already considered ?
+			struct diff_dir_rename* seen;
+			for (seen=factorization_candidates; seen; seen = seen->next)
+				if (!strcmp(seen->one->path, one_parent_path)) break;
+			if (!seen) {
+				// record potential dir rename
+				copy_dirname(two_parent_path, rename_dst[i].pair->two->path);
+
+				seen = xmalloc(sizeof(*seen));
+				seen->one = one_parent;
+				seen->two = alloc_filespec(two_parent_path);
+				fill_filespec(seen->two, null_sha1 /*FIXME*/, S_IFDIR);
+				seen->discarded = 0;
+				seen->next = factorization_candidates;
+				factorization_candidates = seen;
+				fprintf (stderr, "[DBG] %s -> %s suggests possible rename from %s to %s\n",
+				       rename_dst[i].pair->one->path,
+				       rename_dst[i].pair->two->path,
+				       one_parent_path, two_parent_path);
+				fflush(stdout);
+				continue;
+			}
+			if (seen->discarded)
+				continue;
+			// check that seen entry matches this rename
+			copy_dirname(two_parent_path, rename_dst[i].pair->two->path);
+			if (strcmp(two_parent_path, seen->two->path)) {
+				fprintf (stderr, "[DBG] discarding dir split of %s from renames (into %s and %s)\n",
+				       one_parent_path, two_parent_path, seen->two->path);
+				seen->discarded = 1;
+			}
+
+			/* all checks ok, we keep that entry */
+		}
+	}
+
+	// turn candidates into real renames
+	struct diff_dir_rename* candidate;
+	for (candidate=factorization_candidates; candidate; candidate = candidate->next) {
+		int two_idx, i, one_len, two_len;
+		if (candidate->discarded)
+			continue;
+
+		if (!locate_rename_dst_dir(candidate->two)) {
+			fprintf (stderr, "PANIC: %s candidate of rename not in target tree (from %s)\n",
+				candidate->two->path, candidate->one->path);
+		}
+		// bisect to an entry within candidate dst dir
+		two_idx = locate_rename_dst_dir(candidate->two) - rename_dst;
+
+		// now remove extraneous 100% files inside.
+		one_len = strlen(candidate->one->path);
+		two_len = strlen(candidate->two->path);
+		for (i = two_idx; i < rename_dst_nr; i++)
+			if (maybe_mark_uninteresting (rename_dst+i, candidate,
+						      one_len, two_len) < 0)
+				break;
+		for (i = two_idx-1; i >= 0; i--)
+			if (maybe_mark_uninteresting (rename_dst+i, candidate,
+						      one_len, two_len) < 0)
+				break;
+	}
+
+	return;
+}
+
 void diffcore_rename(struct diff_options *options)
 {
 	int detect_rename = options->detect_rename;
@@ -446,13 +631,22 @@ void diffcore_rename(struct diff_options *options)
 				p->one->rename_used++;
 			register_rename_src(p->one, p->score);
 		}
-		else if (detect_rename == DIFF_DETECT_COPY) {
-			/*
-			 * Increment the "rename_used" score by
-			 * one, to indicate ourselves as a user.
-			 */
-			p->one->rename_used++;
-			register_rename_src(p->one, p->score);
+		else {
+			if (detect_rename == DIFF_DETECT_COPY) {
+				/*
+				 * Increment the "rename_used" score by
+				 * one, to indicate ourselves as a user.
+				 */
+				p->one->rename_used++;
+				register_rename_src(p->one, p->score);
+			}
+			if (DIFF_OPT_TST(options, FACTORIZE_RENAMES)) {
+				/* similarly, rename factorization needs to
+				 * see all files from second tree
+				 */
+				//p->two->rename_used++; // FIXME: would we need that ?
+				locate_rename_dst(p->two, 1);
+			}
 		}
 	}
 	if (rename_dst_nr == 0 || rename_src_nr == 0)
@@ -561,8 +755,24 @@ void diffcore_rename(struct diff_options *options)
 	/* At this point, we have found some renames and copies and they
 	 * are recorded in rename_dst.  The original list is still in *q.
 	 */
+
+	/* Now possibly factorize those renames and copies. */
+	if (DIFF_OPT_TST(options, FACTORIZE_RENAMES))
+		diffcore_factorize_renames();
+
 	outq.queue = NULL;
 	outq.nr = outq.alloc = 0;
+
+	// first, turn factorization_candidates into real renames
+	struct diff_dir_rename* candidate;
+	for (candidate=factorization_candidates; candidate; candidate = candidate->next) {
+		struct diff_filepair* pair;
+		if (candidate->discarded) continue;
+		pair = diff_queue(&outq, candidate->one, candidate->two);
+		pair->score = MAX_SCORE;
+		pair->renamed_pair = 1;
+	}
+
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filepair *p = q->queue[i];
 		struct diff_filepair *pair_to_free = NULL;
@@ -577,7 +787,8 @@ void diffcore_rename(struct diff_options *options)
 			struct diff_rename_dst *dst =
 				locate_rename_dst(p->two, 0);
 			if (dst && dst->pair) {
-				diff_q(&outq, dst->pair);
+				if (!dst->pair->uninteresting_rename)
+					diff_q(&outq, dst->pair);
 				pair_to_free = p;
 			}
 			else
diff --git a/diffcore.h b/diffcore.h
index 713cca7..6d2e65b 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -66,6 +66,7 @@ struct diff_filepair {
 	unsigned broken_pair : 1;
 	unsigned renamed_pair : 1;
 	unsigned is_unmerged : 1;
+	unsigned uninteresting_rename : 1;
 };
 #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)
 
diff --git a/tree-diff.c b/tree-diff.c
index 9f67af6..872f757 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -49,7 +49,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 		show_entry(opt, "+", t2, base, baselen);
 		return 1;
 	}
-	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
+	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) &&
+	    !DIFF_OPT_TST(opt, FACTORIZE_RENAMES) &&
+	    !hashcmp(sha1, sha2) && mode1 == mode2)
 		return 0;
 
 	/*

Re: [PATCH 1/2] Introduce rename factorization in diffcore.

[Baz]

2008/10/30 Yann Dirson <ydirson@altern.org>:
> Rename factorization tries to group together files moving from and to
> identical directories - the most common case being directory renames.
> This feature is activated by the new --factorize-renames diffcore
> flag.

Sorry to bikeshed a bit here, but this isn't what 'factorize' means,
and adding a flag with this name unnecessarily adds to the
git-specific terms users have to learn.

Looking back through the archives, there's only a few people who've
used the word 'factorize', and /mostly/ it seems to have been used as
a synonym for 'refactor' in comments; not common usage but
understandable. However in this case, factorize is being used in the
opposite sense from its dictionary definition - to break down into
factors - and instead is being used to mean to /combine/ things; I
don't think that should be in the UI.

Why not just '--group-renames'?

Cheers,
Baz

>
> This is only the first step, adding the basic functionnality and
> adding support to raw diff output (and it breaks unified-diff output
> which does not know how to handle that stuff yet).
>
> Even the output format may not be kept as is.  For now both the result
> of "mv a b" and "mv a/* b/" are displayed as "Rnnn a/ b/", which is
> probably not what we want.  "Rnnn a/* b/" could be a good choice for
> the latter if we want them to be distinguished, and even if we want
> them to look the same.
>
> Other future developements to be made on top of this include:
> * extension of unified-diff format to express this
> * application of such new diffs
> * teach git-svn (and others ?) to make use of that flag
> * merge correctly in case of addition into a moved dir
> * detect "directory splits" so merge can flag a conflict on file adds
> * use inexact dir renames to bump score of below-threshold renames
>  from/to same locations
> * add yours here
> ---
>
>  diff-lib.c        |    6 +
>  diff.c            |    5 +
>  diff.h            |    3 +
>  diffcore-rename.c |  227 +++++++++++++++++++++++++++++++++++++++++++++++++++--
>  diffcore.h        |    1
>  tree-diff.c       |    4 +
>  6 files changed, 235 insertions(+), 11 deletions(-)
>
> diff --git a/diff-lib.c b/diff-lib.c
> index ae96c64..dcc4c2c 100644
> --- a/diff-lib.c
> +++ b/diff-lib.c
> @@ -179,7 +179,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
>                changed = ce_match_stat(ce, &st, ce_option);
>                if (!changed) {
>                        ce_mark_uptodate(ce);
> -                       if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
> +                       if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
> +                           !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))
>                                continue;
>                }
>                oldmode = ce->ce_mode;
> @@ -310,7 +311,8 @@ static int show_modified(struct oneway_unpack_data *cbdata,
>
>        oldmode = old->ce_mode;
>        if (mode == oldmode && !hashcmp(sha1, old->sha1) &&
> -           !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
> +           !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
> +           !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))
>                return 0;
>
>        diff_change(&revs->diffopt, oldmode, mode,
> diff --git a/diff.c b/diff.c
> index e368fef..f91fcf6 100644
> --- a/diff.c
> +++ b/diff.c
> @@ -2437,6 +2437,11 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
>                DIFF_OPT_SET(options, REVERSE_DIFF);
>        else if (!strcmp(arg, "--find-copies-harder"))
>                DIFF_OPT_SET(options, FIND_COPIES_HARDER);
> +       else if (!strcmp(arg, "--factorize-renames")) {
> +               DIFF_OPT_SET(options, FACTORIZE_RENAMES);
> +               if (!options->detect_rename)
> +                       options->detect_rename = DIFF_DETECT_RENAME;
> +       }
>        else if (!strcmp(arg, "--follow"))
>                DIFF_OPT_SET(options, FOLLOW_RENAMES);
>        else if (!strcmp(arg, "--color"))
> diff --git a/diff.h b/diff.h
> index a49d865..db1658b 100644
> --- a/diff.h
> +++ b/diff.h
> @@ -65,6 +65,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
>  #define DIFF_OPT_IGNORE_SUBMODULES   (1 << 18)
>  #define DIFF_OPT_DIRSTAT_CUMULATIVE  (1 << 19)
>  #define DIFF_OPT_DIRSTAT_BY_FILE     (1 << 20)
> +#define DIFF_OPT_FACTORIZE_RENAMES   (1 << 21)
>  #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
>  #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)
>  #define DIFF_OPT_CLR(opts, flag)    ((opts)->flags &= ~DIFF_OPT_##flag)
> @@ -220,6 +221,8 @@ extern void diffcore_std(struct diff_options *);
>  "  -C            detect copies.\n" \
>  "  --find-copies-harder\n" \
>  "                try unchanged files as candidate for copy detection.\n" \
> +"  --factorize-renames\n" \
> +"                factorize renames of all files of a directory.\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" \
> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 1b2ebb4..fc789bc 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -52,6 +52,32 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
>        return &(rename_dst[first]);
>  }
>
> +static struct diff_rename_dst *locate_rename_dst_dir(struct diff_filespec *dir)
> +{
> +       /* code mostly duplicated from locate_rename_dst - not sure we
> +        * could merge them efficiently,though
> +        */
> +       int first, last;
> +       int dirlength = strlen(dir->path);
> +
> +       first = 0;
> +       last = rename_dst_nr;
> +       while (last > first) {
> +               int next = (last + first) >> 1;
> +               struct diff_rename_dst *dst = &(rename_dst[next]);
> +               int cmp = strncmp(dir->path, dst->two->path, dirlength);
> +               if (!cmp)
> +                       return dst;
> +               if (cmp < 0) {
> +                       last = next;
> +                       continue;
> +               }
> +               first = next+1;
> +       }
> +       /* not found */
> +       return NULL;
> +}
> +
>  /* Table of rename/copy src files */
>  static struct diff_rename_src {
>        struct diff_filespec *one;
> @@ -409,6 +435,165 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)
>                m[worst] = *o;
>  }
>
> +struct diff_dir_rename {
> +       struct diff_filespec *one;
> +       struct diff_filespec *two;
> +       int discarded;
> +       struct diff_dir_rename* next;
> +};
> +
> +/*
> + * Marks as such file_rename if it is made uninteresting by dir_rename.
> + * Returns -1 if the file_rename is outside of the range in which given
> + * renames concerned by dir_rename are to be found (ie. end of loop),
> + * 0 otherwise.
> + */
> +static int maybe_mark_uninteresting(struct diff_rename_dst* file_rename,
> +                                   struct diff_dir_rename* dir_rename,
> +                                   int one_len, int two_len)
> +{
> +       if (!file_rename->pair) /* file add */
> +               return 0;
> +       if (strncmp(file_rename->two->path,
> +                   dir_rename->two->path, two_len))
> +               return -1;
> +       if (strncmp(file_rename->pair->one->path,
> +                   dir_rename->one->path, one_len) ||
> +           !basename_same(file_rename->pair->one, file_rename->two) ||
> +           file_rename->pair->score != MAX_SCORE)
> +               return 0;
> +
> +       file_rename->pair->uninteresting_rename = 1;
> +       fprintf (stderr, "[DBG] %s* -> %s* makes %s -> %s uninteresting\n",
> +               dir_rename->one->path, dir_rename->two->path,
> +               file_rename->pair->one->path, file_rename->two->path);
> +       return 0;
> +}
> +
> +// FIXME: prevent possible overflow
> +/*
> + * Copy dirname of src into dst, with final "/".
> + * Only handles relative paths since there is no relative path in a git repo.
> + * Writes "./" when there is no "/" in src.
> + * May overwrite more chars than really needed, if src ends with a "/".
> + */
> +static const char* copy_dirname(char* dst, const char* src)
> +{
> +       char* lastslash = strrchr(src, '/');
> +       if (!lastslash)
> +               return strcpy(dst, "./");
> +       strncpy(dst, src, lastslash - src + 1);
> +       dst[lastslash - src + 1] = '\0';
> +
> +       // if src ends with a "/" strip the last component
> +       if (lastslash[1] == '\0') {
> +               lastslash = strrchr(dst, '/');
> +               if (!lastslash)
> +                       return strcpy(dst, ".");
> +               lastslash[1] = '\0';
> +       }
> +
> +       return dst;
> +}
> +
> +/*
> + * FIXME: we could optimize the 100%-rename case by preventing
> + * recursion to unfold what we know we would refold here.
> + * FIXME: do we want to replace linked list with sorted array ?
> + * FIXME: this prototype only handles renaming of dirs without
> + * a subdir.
> + * FIXME: leaks like hell.
> + * FIXME: ideas to evaluate a similarity score, anyone ?
> + *  10% * tree similarity + 90% * moved files similarity ?
> + */
> +static struct diff_dir_rename* factorization_candidates = NULL;
> +static void diffcore_factorize_renames(void)
> +{
> +       char one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];
> +       int i;
> +
> +       for (i = 0; i < rename_dst_nr; i++) {
> +               // FIXME: what are those ?
> +               if (!rename_dst[i].pair)
> +                       continue;
> +               // dummy renames used by copy detection
> +               if (!strcmp(rename_dst[i].pair->one->path, rename_dst[i].pair->two->path))
> +                       continue;
> +
> +               copy_dirname(one_parent_path, rename_dst[i].pair->one->path);
> +
> +               struct diff_filespec* one_parent = alloc_filespec(one_parent_path);
> +               fill_filespec(one_parent, null_sha1 /*FIXME*/, S_IFDIR);
> +
> +               if (!locate_rename_dst_dir(one_parent)) {
> +                       // one_parent_path is empty in result tree
> +
> +                       // already considered ?
> +                       struct diff_dir_rename* seen;
> +                       for (seen=factorization_candidates; seen; seen = seen->next)
> +                               if (!strcmp(seen->one->path, one_parent_path)) break;
> +                       if (!seen) {
> +                               // record potential dir rename
> +                               copy_dirname(two_parent_path, rename_dst[i].pair->two->path);
> +
> +                               seen = xmalloc(sizeof(*seen));
> +                               seen->one = one_parent;
> +                               seen->two = alloc_filespec(two_parent_path);
> +                               fill_filespec(seen->two, null_sha1 /*FIXME*/, S_IFDIR);
> +                               seen->discarded = 0;
> +                               seen->next = factorization_candidates;
> +                               factorization_candidates = seen;
> +                               fprintf (stderr, "[DBG] %s -> %s suggests possible rename from %s to %s\n",
> +                                      rename_dst[i].pair->one->path,
> +                                      rename_dst[i].pair->two->path,
> +                                      one_parent_path, two_parent_path);
> +                               fflush(stdout);
> +                               continue;
> +                       }
> +                       if (seen->discarded)
> +                               continue;
> +                       // check that seen entry matches this rename
> +                       copy_dirname(two_parent_path, rename_dst[i].pair->two->path);
> +                       if (strcmp(two_parent_path, seen->two->path)) {
> +                               fprintf (stderr, "[DBG] discarding dir split of %s from renames (into %s and %s)\n",
> +                                      one_parent_path, two_parent_path, seen->two->path);
> +                               seen->discarded = 1;
> +                       }
> +
> +                       /* all checks ok, we keep that entry */
> +               }
> +       }
> +
> +       // turn candidates into real renames
> +       struct diff_dir_rename* candidate;
> +       for (candidate=factorization_candidates; candidate; candidate = candidate->next) {
> +               int two_idx, i, one_len, two_len;
> +               if (candidate->discarded)
> +                       continue;
> +
> +               if (!locate_rename_dst_dir(candidate->two)) {
> +                       fprintf (stderr, "PANIC: %s candidate of rename not in target tree (from %s)\n",
> +                               candidate->two->path, candidate->one->path);
> +               }
> +               // bisect to an entry within candidate dst dir
> +               two_idx = locate_rename_dst_dir(candidate->two) - rename_dst;
> +
> +               // now remove extraneous 100% files inside.
> +               one_len = strlen(candidate->one->path);
> +               two_len = strlen(candidate->two->path);
> +               for (i = two_idx; i < rename_dst_nr; i++)
> +                       if (maybe_mark_uninteresting (rename_dst+i, candidate,
> +                                                     one_len, two_len) < 0)
> +                               break;
> +               for (i = two_idx-1; i >= 0; i--)
> +                       if (maybe_mark_uninteresting (rename_dst+i, candidate,
> +                                                     one_len, two_len) < 0)
> +                               break;
> +       }
> +
> +       return;
> +}
> +
>  void diffcore_rename(struct diff_options *options)
>  {
>        int detect_rename = options->detect_rename;
> @@ -446,13 +631,22 @@ void diffcore_rename(struct diff_options *options)
>                                p->one->rename_used++;
>                        register_rename_src(p->one, p->score);
>                }
> -               else if (detect_rename == DIFF_DETECT_COPY) {
> -                       /*
> -                        * Increment the "rename_used" score by
> -                        * one, to indicate ourselves as a user.
> -                        */
> -                       p->one->rename_used++;
> -                       register_rename_src(p->one, p->score);
> +               else {
> +                       if (detect_rename == DIFF_DETECT_COPY) {
> +                               /*
> +                                * Increment the "rename_used" score by
> +                                * one, to indicate ourselves as a user.
> +                                */
> +                               p->one->rename_used++;
> +                               register_rename_src(p->one, p->score);
> +                       }
> +                       if (DIFF_OPT_TST(options, FACTORIZE_RENAMES)) {
> +                               /* similarly, rename factorization needs to
> +                                * see all files from second tree
> +                                */
> +                               //p->two->rename_used++; // FIXME: would we need that ?
> +                               locate_rename_dst(p->two, 1);
> +                       }
>                }
>        }
>        if (rename_dst_nr == 0 || rename_src_nr == 0)
> @@ -561,8 +755,24 @@ void diffcore_rename(struct diff_options *options)
>        /* At this point, we have found some renames and copies and they
>         * are recorded in rename_dst.  The original list is still in *q.
>         */
> +
> +       /* Now possibly factorize those renames and copies. */
> +       if (DIFF_OPT_TST(options, FACTORIZE_RENAMES))
> +               diffcore_factorize_renames();
> +
>        outq.queue = NULL;
>        outq.nr = outq.alloc = 0;
> +
> +       // first, turn factorization_candidates into real renames
> +       struct diff_dir_rename* candidate;
> +       for (candidate=factorization_candidates; candidate; candidate = candidate->next) {
> +               struct diff_filepair* pair;
> +               if (candidate->discarded) continue;
> +               pair = diff_queue(&outq, candidate->one, candidate->two);
> +               pair->score = MAX_SCORE;
> +               pair->renamed_pair = 1;
> +       }
> +
>        for (i = 0; i < q->nr; i++) {
>                struct diff_filepair *p = q->queue[i];
>                struct diff_filepair *pair_to_free = NULL;
> @@ -577,7 +787,8 @@ void diffcore_rename(struct diff_options *options)
>                        struct diff_rename_dst *dst =
>                                locate_rename_dst(p->two, 0);
>                        if (dst && dst->pair) {
> -                               diff_q(&outq, dst->pair);
> +                               if (!dst->pair->uninteresting_rename)
> +                                       diff_q(&outq, dst->pair);
>                                pair_to_free = p;
>                        }
>                        else
> diff --git a/diffcore.h b/diffcore.h
> index 713cca7..6d2e65b 100644
> --- a/diffcore.h
> +++ b/diffcore.h
> @@ -66,6 +66,7 @@ struct diff_filepair {
>        unsigned broken_pair : 1;
>        unsigned renamed_pair : 1;
>        unsigned is_unmerged : 1;
> +       unsigned uninteresting_rename : 1;
>  };
>  #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)
>
> diff --git a/tree-diff.c b/tree-diff.c
> index 9f67af6..872f757 100644
> --- a/tree-diff.c
> +++ b/tree-diff.c
> @@ -49,7 +49,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
>                show_entry(opt, "+", t2, base, baselen);
>                return 1;
>        }
> -       if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
> +       if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) &&
> +           !DIFF_OPT_TST(opt, FACTORIZE_RENAMES) &&
> +           !hashcmp(sha1, sha2) && mode1 == mode2)
>                return 0;
>
>        /*
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [PATCH 1/2] Introduce rename factorization in diffcore.

[Jakub Narebski]

Baz <brian.ewins@gmail.com> writes:
> 2008/10/30 Yann Dirson <ydirson@altern.org>:

> > Rename factorization tries to group together files moving from and to
> > identical directories - the most common case being directory renames.
> > This feature is activated by the new --factorize-renames diffcore
> > flag.
> 
> Sorry to bikeshed a bit here, but this isn't what 'factorize' means,
> and adding a flag with this name unnecessarily adds to the
> git-specific terms users have to learn.

Well, I think from _mathematical_ (arithmetic) point of view it makes
perfect sense.  Before you had:

  (rename-of-sub1-file1 rename-of-sub1-file2 rename-of-sub1-file3)

and after you have

  (rename-of-sub1) * (changes in files)
 
> Looking back through the archives, there's only a few people who've
> used the word 'factorize', and /mostly/ it seems to have been used as
> a synonym for 'refactor' in comments; not common usage but
> understandable. However in this case, factorize is being used in the
> opposite sense from its dictionary definition - to break down into
> factors - and instead is being used to mean to /combine/ things; I
> don't think that should be in the UI.
> 
> Why not just '--group-renames'?

That said, I think that '--group-renames' makes better sense (and is
shorted than '--detect-directory-renames')

+1 for '--group-renames'

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH 1/2] Introduce rename factorization in diffcore.

[Nguyen Thai Ngoc Duy]

On 10/31/08, Yann Dirson <ydirson@altern.org> wrote:
>  -               else if (detect_rename == DIFF_DETECT_COPY) {
>  -                       /*
>  -                        * Increment the "rename_used" score by
>  -                        * one, to indicate ourselves as a user.
>  -                        */
>  -                       p->one->rename_used++;
>  -                       register_rename_src(p->one, p->score);
>  +               else {
>  +                       if (detect_rename == DIFF_DETECT_COPY) {
>  +                               /*
>  +                                * Increment the "rename_used" score by
>  +                                * one, to indicate ourselves as a user.
>  +                                */
>  +                               p->one->rename_used++;
>  +                               register_rename_src(p->one, p->score);
>  +                       }
>  +                       if (DIFF_OPT_TST(options, FACTORIZE_RENAMES)) {
>  +                               /* similarly, rename factorization needs to
>  +                                * see all files from second tree
>  +                                */
>  +                               //p->two->rename_used++; // FIXME: would we need that ?
>  +                               locate_rename_dst(p->two, 1);
>  +                       }
>                 }
>         }

Hmm.. how about turn on a special flag for these rename_dst items?
Otherwise --group-renames and --find-copies-harder combination would
become hell: you have to compare all src with all dst. It could exceed
rename_limit, therefore no rename detection will be done.
-- 
Duy

Re: [PATCH 1/2] Introduce rename factorization in diffcore.

[Nguyen Thai Ngoc Duy]

On 11/8/08, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> Hmm.. how about turn on a special flag for these rename_dst items?
>  Otherwise --group-renames and --find-copies-harder combination would
>  become hell: you have to compare all src with all dst. It could exceed
>  rename_limit, therefore no rename detection will be done.

Nevermind. I read an old version.
-- 
Duy

[PATCH 2/2] Add testcases for the --factorize-renames diffcore flag.

[Yann Dirson]

This notably includes a couple of tests for cases known not to be
working correctly yet.
---

 t/t4030-diff-rename-factorize.sh |  209 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 209 insertions(+), 0 deletions(-)
 create mode 100755 t/t4030-diff-rename-factorize.sh

diff --git a/t/t4030-diff-rename-factorize.sh b/t/t4030-diff-rename-factorize.sh
new file mode 100755
index 0000000..fcf8fb6
--- /dev/null
+++ b/t/t4030-diff-rename-factorize.sh
@@ -0,0 +1,209 @@
+#!/bin/sh
+#
+# Copyright (c) 2008 Yann Dirson
+# Copyright (c) 2005 Junio C Hamano
+#
+
+test_description='Test rename factorization in diff engine.
+
+'
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/diff-lib.sh
+
+test_expect_success \
+    'commit the index.'  \
+    'git update-ref HEAD $(echo "original empty commit" | git commit-tree $(git write-tree))'
+
+mkdir a
+echo >a/path0 'Line 1
+Line 2
+Line 3
+Line 4
+Line 5
+Line 6
+Line 7
+Line 8
+Line 9
+Line 10
+line 11
+Line 12
+Line 13
+Line 14
+Line 15
+'
+sed <a/path0 >a/path1 s/Line/Record/
+sed <a/path0 >a/path2 s/Line/Stuff/
+sed <a/path0 >a/path3 s/Line/Blurb/
+
+test_expect_success \
+    'update-index --add file inside a directory.' \
+    'git update-index --add a/path*'
+
+test_expect_success \
+    'write that tree.' \
+    'tree=$(git write-tree) && test -n "$tree"'
+
+test_expect_success \
+    'commit the index.'  \
+    'git update-ref HEAD $(echo "original set of files" | git commit-tree $tree)'
+
+mv a b
+test_expect_success \
+    'renamed the directory.' \
+    'git update-index --add --remove a/path0 a/path1 a/path2 a/path3 b/path*'
+
+test_expect_success \
+    'git diff-index --factorize-renames after directory move.' \
+    'git diff-index --factorize-renames $tree >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	a/	b/
+EOF
+
+test_expect_success \
+    'validate the output for directory move.' \
+    'compare_diff_patch current.filtered expected'
+
+# now test non-100% renames
+
+echo 'Line 16' >> b/path0
+mv b/path2 b/2path
+rm b/path3
+echo anything > b/path100
+test_expect_success \
+    'edited dir contents.' \
+    'git update-index --add --remove b/* b/path2 b/path3'
+
+test_expect_success \
+    'git diff-index --factorize-renames after directory move and content changes.' \
+    'git diff-index --factorize-renames $tree >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	a/	b/
+:100644 000000 c6971ab9f08a6cd9c89a0f87d94ae347aad6144a 0000000000000000000000000000000000000000 D	a/path3
+:100644 100644 dbde7141d737c8aa0003672c1bc21ded48c6c3b9 dbde7141d737c8aa0003672c1bc21ded48c6c3b9 R100	a/path2	b/2path
+:100644 100644 fdbec444a77953b1bcc899d9fabfa202e5e68f08 4db595d12886f90e36765fc1732c17bccb836663 R093	a/path0	b/path0
+:000000 100644 0000000000000000000000000000000000000000 1ba4650885513e62386fd3e23aeb45beeb67d3bb A	b/path100
+EOF
+
+test_expect_success \
+    'validate the output for directory move and content changes.' \
+    'compare_diff_patch current.filtered expected'
+
+git reset --hard
+
+# now test bulk moves that are not directory moves (get consensus before going further ?)
+
+mkdir c
+for i in 0 1 2; do cp a/path$i c/apath$i; done
+test_expect_success \
+    'add files into a new directory.' \
+    'git update-index --add c/apath*'
+
+test_expect_success \
+    'commit all this.'  \
+    'git commit -m "first set of changes"'
+
+mv c/* a/
+test_expect_success \
+    'move all of the new dir contents into a preexisting dir.' \
+    'git update-index --add --remove a/* c/apath0 c/apath1 c/apath2'
+
+test_expect_success \
+    'git diff-index --factorize-renames without full-dir rename.' \
+    'git diff-index --factorize-renames HEAD >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	c/*	a/
+EOF
+
+test_expect_failure \
+    'validate the output for bulk rename without full-dir rename.' \
+    'compare_diff_patch current.filtered expected'
+
+git reset --hard
+
+# now test moves to toplevel (seriously broken)
+
+mv c/* .
+test_expect_success \
+    'move all of the new dir contents into toplevel.' \
+    'git update-index --add --remove apath* c/apath0 c/apath1 c/apath2'
+
+test_expect_success \
+    'git diff-index --factorize-renames files bulk-moved to toplevel.' \
+    'git diff-index --factorize-renames HEAD >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	c/*	./
+EOF
+
+test_expect_failure \
+    'validate the output for files bulk-moved to toplevel.' \
+    'compare_diff_patch current.filtered expected'
+
+git reset --hard
+
+# now test renaming with subdirs (lacks hiding of renamed subdirs)
+
+mv c a/
+test_expect_success \
+    'move the new dir as subdir of another.' \
+    'git update-index --add --remove a/c/* c/apath0 c/apath1 c/apath2'
+
+test_expect_success \
+    'commit all this.'  \
+    'git commit -m "move as subdir"'
+
+mv a b
+echo foo >> b/c/apath0
+test_expect_success \
+    'rename the directory with some changes.' \
+    'git update-index --add --remove a/path0 a/path1 a/path2 a/path3 a/c/apath0 a/c/apath1 a/c/apath2 b/path* b/c/apath*'
+
+test_expect_success \
+    'git diff-index --factorize-renames on a move including a subdir.' \
+    'git diff-index --factorize-renames HEAD >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	a/	b/
+:100644 100644 fdbec444a77953b1bcc899d9fabfa202e5e68f08 00084e5ea68b5ae339b7c4b429e4a70fe25d069b R096	a/c/apath0	b/c/apath0
+EOF
+
+test_expect_failure \
+    'validate the output for a move including a subdir.' \
+    'compare_diff_patch current.filtered expected'
+
+# now test moving all files from toplevel into subdir (does not hides file moves) (needs consensus on syntax)
+#FIXME: maybe handle this as special case of move of a dir into one of its own subdirs ?
+
+git reset --hard HEAD~2
+
+mv a/* .
+test_expect_success \
+    'rename the directory with some changes.' \
+    'git update-index --add --remove a/path0 a/path1 a/path2 a/path3 path*'
+
+test_expect_success \
+    'commit all this.'  \
+    'git commit -m "move all files to toplevel"'
+
+mkdir z
+mv path* z/
+test_expect_success \
+    'rename the directory with some changes.' \
+    'git update-index --add --remove path0 path1 path2 path3 z/path*'
+
+test_expect_success \
+    'git diff-index --factorize-renames everything from toplevel.' \
+    'git diff-index --factorize-renames HEAD >current'
+grep -v "^\[DBG\] " <current >current.filtered
+cat >expected <<\EOF
+:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100	./*	z/
+EOF
+
+test_expect_failure \
+    'validate the output for a move of everything from toplevel.' \
+    'compare_diff_patch current.filtered expected'
+
+test_done