diffcore and directory renames

diffcore and directory renames

[Yann Dirson]

I often found myself lost when looking at a diff where a couple of
large dirs where renamed, and a handful of files were modified to take
the rename into account - not a rare situation, I'd say.  In such a
case, the diffs themselves are mostly hidden among numerous rename
entries.

To that, I felt that git ought to know better, and could easily
present a directory rename as such.  Among the advantages of having
such "dir rename detection", aside from readability which we should
not neglect, we'd have more accurate "svn dcommit" for such renames
and, and better decisions made when merging a branch with adds a file
into a dir, with a branch which renames that dir (ok, maybe not that
frequent, but still).


Looking closer at the current behaviour, I realized that git-diff-tree
*is* already able to report such renames in raw mode :

$ ./git-diff-tree 0f1027 -M
0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3
:040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved

... but patch output breaks this into file moves, and even other
commands which I would have expected to display the same do in fact
not (eg. "git show --raw").  Is there any reason for this ?  I would
have expected git-show to do the same as diff-tree, and it would not
be so much of a problem to introduce a special form of the "rename"
chunk to handle dir renames ?


Since current diff-tree behaviour is based on comparing tree hashs, it
only detects 100%-similarity renames, and naturally diff-index and
diff-files cannot even do that much yet.  However, an optional
factorization pass following rename detection could quite easily
detect if, when a containing directory disappears because of a set of
renames - this is what I have started to look at.

Since what I propose is indeed just a factorization of file renames,
it could be adequate to represent them as such instead of directory
renames, so as to read something like:

|diff --git a/ppc/* b/moved/
|rename from ppc/*
|rename to moved/

This would have the additional advantage of also working when the
target destination was pre-existing, and when merging several dirs
into a single one - while at the same time to mistaking the reader too
much into thinking that git cares about directories so much ;)

Callers should also be careful about interpreting the output when
mixing this behaviour with file filtering, obviously, so it is not
meant to be activated by default.

Does any of this sound sensible ?


On the technical side, I figured out that the best way to plug the
factorization was inside diffcore_rename to take advantage of the fact
it has a list of all renames, that's not going to be published out of
this function - that only left me the "cleanup:" label as insertion
point, not that I find it conceptually very comfortable :)

But if I have understood correctly, diffcore only gets access to
changed filepairs, and does not know about the trees it is comparing.

The most sensible way to go I can think of would be to give to
diffcore enough information (src and dst tree-hash|"INDEX"|"WORKING
COPY") to be able to know for directory existence.  I'd rather check
it does not sound completely wrong to anyone before going into that -
opinions ?

Best regards,
-- 
Yann

Re: diffcore and directory renames

[Junio C Hamano]

Yann Dirson <ydirson@altern.org> writes:

> I often found myself lost when looking at a diff where a couple of
> large dirs where renamed, and a handful of files were modified to take
> the rename into account - not a rare situation, I'd say.  In such a
> case, the diffs themselves are mostly hidden among numerous rename
> entries.

Yes, I've hinted here number of times that rename detection could notice
the fact that neighbouring paths are migrating to the same directory and
boost similarity scores of leftover paths that did not otherwise made the
threshold in such a situation.

I am glad to see finally somebody got interested ;-)

> $ ./git-diff-tree 0f1027 -M
> 0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3
> :040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved

Yes, diff-tree can show this, and you should be able to teach diff-index
with a clean cache-tree to do similar, but this only applies to the
non-recursive 100% rename at the toplevel, which is too narrow a special
case to be interesting at all.  We perhaps further could run the
similarity comparison on the raw tree objects if we wanted to so that you
can find inexact matches, but I think it is going in the wrong direction.

The thing is, diffcore is designed to be a general mechanism to unify
comparisons on two arbitrary sets of files, be they from tree-vs-tree,
tree-vs-index, tree-vs-worktree, or index-vs-worktree.  The machinery
should be able to operate on any two sets of files in the same way and
produce more-or-less the same results.  It is Ok for callers to give extra
hints, when available, to speed up the computation, but the core of the
algorithm should not depend on the presense of such hints to deduce the
renames.

So please aim to make the hint-less case, "diff-files --no-index", produce
a sensible result.  That should be the first step.

Re: diffcore and directory renames

[Yann Dirson]

On Mon, Sep 01, 2008 at 03:50:22PM -0700, Junio C Hamano wrote:
> Yes, I've hinted here number of times that rename detection could notice
> the fact that neighbouring paths are migrating to the same directory and
> boost similarity scores of leftover paths that did not otherwise made the
> threshold in such a situation.

Wow, that's a great idea I did not think about :)

> I am glad to see finally somebody got interested ;-)

I am glad we're on the same side :)

> > $ ./git-diff-tree 0f1027 -M
> > 0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3
> > :040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved
> 
> Yes, diff-tree can show this, and you should be able to teach diff-index
> with a clean cache-tree to do similar, but this only applies to the
> non-recursive 100% rename at the toplevel, which is too narrow a special
> case to be interesting at all.  We perhaps further could run the
> similarity comparison on the raw tree objects if we wanted to so that you
> can find inexact matches, but I think it is going in the wrong direction.

Agreed.

> The thing is, diffcore is designed to be a general mechanism to unify
> comparisons on two arbitrary sets of files, be they from tree-vs-tree,
> tree-vs-index, tree-vs-worktree, or index-vs-worktree.  The machinery
> should be able to operate on any two sets of files in the same way and
> produce more-or-less the same results.  It is Ok for callers to give extra
> hints, when available, to speed up the computation, but the core of the
> algorithm should not depend on the presense of such hints to deduce the
> renames.

My idea was rather to just see tree/index/worktree as just 3
specialized forms of a single "abstract tree" of some sort,
effectively unifying things.

But anyway afterwards I thought that there may be something for me to
learn in how --find-copies-harder gets its information for
non-modified sources of copies -- I'll have a look at that.


> So please aim to make the hint-less case, "diff-files --no-index", produce
> a sensible result.  That should be the first step.

OK.

Best regards,
-- 
Yann

[RFC PATCH] detection of directory renames

[Yann Dirson]

This is a first very preliminar patch, mostly so people can comment
early on the big picture.  It has a number of limitations, many but
not all already listed as FIXME's in the patch itself.  If anything in
this patch seems so wrong it is not worth polishing it, it's the
perfect time to say so :)

The idea is to add a new pass to diffcore-rename, to group file renames
looking like a full directory move, and then to hide those file
renames which do not carry any additionnal information.

Here is a sample run:

$ ./git-diff-tree ee491 --factorize-renames -r 
[DBG] possible rename from arm/ to bar/
[DBG] possible rename from ppc/ to moved/
[DBG] discarding dir rename of arm/, mixing moved/ and bar/
[DBG] ppc/* -> moved/* makes ppc/sha1ppc.S -> moved/sha1ppc.S uninteresting
[DBG] ppc/* -> moved/* makes ppc/sha1.c -> moved/sha1.c uninteresting
ee491a42190ec6e716f46a55fa0a7f4e307f1629
:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100   ppc/    moved/
:100644 100644 9e3ae038e818f4e21bc50f864fc5204f6fa44daa 9e3ae038e818f4e21bc50f864fc5204f6fa44daa R100   arm/sha1.c      bar/sha1.c
:100644 100644 3952646349cf9d033177e69ba9433652a378c0e9 3952646349cf9d033177e69ba9433652a378c0e9 R100   arm/sha1.h      bar/sha1.h
:100644 100644 c3c51aa4d487f2e85c02b0257c1f0b57d6158d76 c065eeef7d68ea91863431788e20cd814c5ac52c R099   ppc/sha1.h      moved/sha1.h
:100644 100644 8c1cb99fb403875af85e4d1524d21f7eb818f59b 8c1cb99fb403875af85e4d1524d21f7eb818f59b R100   arm/sha1_arm.S  moved/sha1_arm.S

-- 
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] Introduce patch factorization in diffcore.

[Yann Dirson]

---

 diff-lib.c        |    6 +-
 diff.c            |    5 +
 diff.h            |    3 +
 diffcore-rename.c |  194 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 diffcore.h        |    1 
 tree-diff.c       |    4 +
 6 files changed, 202 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 9053d4d..2315980 100644
--- a/diff.c
+++ b/diff.c
@@ -2599,6 +2599,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 1ca4f46..7b862c6 100644
--- a/diff.h
+++ b/diff.h
@@ -64,6 +64,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_OPT_RELATIVE_NAME       (1 << 17)
 #define DIFF_OPT_IGNORE_SUBMODULES   (1 << 18)
 #define DIFF_OPT_DIRSTAT_CUMULATIVE  (1 << 19)
+#define DIFF_OPT_FACTORIZE_RENAMES   (1 << 20)
 #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)
@@ -219,6 +220,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..2757204 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -6,6 +6,8 @@
 #include "diffcore.h"
 #include "hash.h"
 
+#include <libgen.h>
+
 /* Table of rename/copy destinations */
 
 static struct diff_rename_dst {
@@ -52,6 +54,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 +437,130 @@ 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 (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;
+	printf ("[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: 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 buffer[PATH_MAX], one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];
+	int i;
+
+	for (i = 0; i < rename_dst_nr; i++) {
+		if (!rename_dst[i].pair)
+			continue;
+		strcpy(buffer, rename_dst[i].pair->one->path);
+		strcpy(one_parent_path, dirname(buffer));
+		strcat(one_parent_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
+				strcpy(buffer, rename_dst[i].pair->two->path);
+				strcpy(two_parent_path, dirname(buffer));
+				strcat(two_parent_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;
+				printf("[DBG] possible rename from %s to %s\n",
+				       one_parent_path, two_parent_path);
+				continue;
+			}
+			if (seen->discarded)
+				continue;
+			// check that seen entry matches this rename
+			strcpy(buffer, rename_dst[i].pair->two->path);
+			strcpy(two_parent_path, dirname(buffer));
+			strcat(two_parent_path, "/");
+			if (strcmp(two_parent_path, seen->two->path)) {
+				printf("[DBG] discarding dir rename of %s, mixing %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;
+
+		// any 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 +598,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 +722,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 +754,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 8ae3578..e4aa099 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -62,6 +62,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] Introduce patch factorization in diffcore.

[Andreas Ericsson]

Yann Dirson wrote:
>  "                try unchanged files as candidate for copy detection.\n" \
> +"  --factorize_renames\n" \
> +"                factorize renames of all files of a directory.\n" \


Use dashes to separate words in arguments, please.


>  
> +#include <libgen.h>
> +

 +#ifdef basename
 +# undef basename
 +#endif

We might as well use the GNU version of basename() at least. Even if
you don't use it, I'd rather not see this bite some unwary programmer
coming along after you. Worst case scenario, sha1's won't add up if
POSIX basename alters its argument, making for one fiendishly tricky
bug to find.

> +/*
> + * 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 ?

Either that or a hash. Most of the time seems to be spent in lookups.
With a hash you get quick lookups and reasonably quick inserts. With
a sorted array you get lower memory footprint than anything else and
can bisect your way to the right entry, which performs reasonably
close to skiplists. The sort overhead might be a deterrant factor,
but insofar as I understand it trees are always sorted in git anyway,
so perhaps that'd be the best solution.

Apart from that, I'd need to apply the patch to review it properly,
and I'm far too tired for that now.

I like the direction this is going though, so thanks a lot for doing
it :)

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

Re: [RFC PATCH] detection of directory renames

[Jakub Narebski]

Yann Dirson <ydirson@altern.org> writes:

> This is a first very preliminar patch, mostly so people can comment
> early on the big picture.  It has a number of limitations, many but
> not all already listed as FIXME's in the patch itself.  If anything in
> this patch seems so wrong it is not worth polishing it, it's the
> perfect time to say so :)
> 
> The idea is to add a new pass to diffcore-rename, to group file renames
> looking like a full directory move, and then to hide those file
> renames which do not carry any additionnal information.
> 
> Here is a sample run:
> 
> $ ./git-diff-tree ee491 --factorize-renames -r 
> [DBG] possible rename from arm/ to bar/
> [DBG] possible rename from ppc/ to moved/
> [DBG] discarding dir rename of arm/, mixing moved/ and bar/
> [DBG] ppc/* -> moved/* makes ppc/sha1ppc.S -> moved/sha1ppc.S uninteresting
> [DBG] ppc/* -> moved/* makes ppc/sha1.c -> moved/sha1.c uninteresting
> ee491a42190ec6e716f46a55fa0a7f4e307f1629
> :040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100   ppc/    moved/
> :100644 100644 9e3ae038e818f4e21bc50f864fc5204f6fa44daa 9e3ae038e818f4e21bc50f864fc5204f6fa44daa R100   arm/sha1.c      bar/sha1.c
> :100644 100644 3952646349cf9d033177e69ba9433652a378c0e9 3952646349cf9d033177e69ba9433652a378c0e9 R100   arm/sha1.h      bar/sha1.h
> :100644 100644 c3c51aa4d487f2e85c02b0257c1f0b57d6158d76 c065eeef7d68ea91863431788e20cd814c5ac52c R099   ppc/sha1.h      moved/sha1.h
> :100644 100644 8c1cb99fb403875af85e4d1524d21f7eb818f59b 8c1cb99fb403875af85e4d1524d21f7eb818f59b R100   arm/sha1_arm.S  moved/sha1_arm.S

Wonderfull!!!

I like it very much, and hope that it would get improved. And that you
would be able to use it in merges too, to allow for example for new
files to be created in renamed directory instead of old one which does
not exist any longer (c.f. http://www.markshuttleworth.com/archives/123
and following articles).

For the future, could you show examples with --abbrev option in use? TIA.
-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [RFC PATCH] detection of directory renames

[Yann Dirson]

On Thu, Sep 25, 2008 at 04:19:20PM -0700, Jakub Narebski wrote:
> Wonderfull!!!

Wow, I love this feedback :)

> I like it very much, and hope that it would get improved. And that you
> would be able to use it in merges too, to allow for example for new
> files to be created in renamed directory instead of old one which does
> not exist any longer (c.f. http://www.markshuttleworth.com/archives/123
> and following articles).

Yes, that's one of planned things.  Along the same line (once renames
are stabilized), I think about extending things so that "split dirs"
are detected as well, so merge can flag a conflict when there is a
doubt that a file would really be added in a "split directory".  The
situation may be obvious in my example (arm/ contents dispatched into
bar/ and moved/), but may also be useful when we can detect that a
significant number of files have been moved out of a directory.

> For the future, could you show examples with --abbrev option in use? TIA.

Good idea.

Best regards,
-- 
Yann

Re: [PATCH] Introduce patch factorization in diffcore.

[Yann Dirson]

On Fri, Sep 26, 2008 at 12:39:54AM +0200, Andreas Ericsson wrote:
> Yann Dirson wrote:
>>  "                try unchanged files as candidate for copy detection.\n" \
>> +"  --factorize_renames\n" \
>> +"                factorize renames of all files of a directory.\n" \
>
>
> Use dashes to separate words in arguments, please.

Fortunately, the typo only made it to the help string, thanks for
catching it :)

>>  +#include <libgen.h>
>> +
>
> +#ifdef basename
> +# undef basename
> +#endif
>
> We might as well use the GNU version of basename() at least. Even if
> you don't use it, I'd rather not see this bite some unwary programmer
> coming along after you. Worst case scenario, sha1's won't add up if
> POSIX basename alters its argument, making for one fiendishly tricky
> bug to find.

I'll look into that, thanks

>> +/*
>> + * 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 ?
>
> Either that or a hash. Most of the time seems to be spent in lookups.
> With a hash you get quick lookups and reasonably quick inserts. With
> a sorted array you get lower memory footprint than anything else and
> can bisect your way to the right entry, which performs reasonably
> close to skiplists. The sort overhead might be a deterrant factor,
> but insofar as I understand it trees are always sorted in git anyway,
> so perhaps that'd be the best solution.

Thanks for this insight - I'll wait before changing the data structure,
since the current implementation may need to be able to recurse (consider
renamed subdirs as well as renamed files).

> Apart from that, I'd need to apply the patch to review it properly,
> and I'm far too tired for that now.
>
> I like the direction this is going though, so thanks a lot for doing
> it :)

Great :)

Best regards,
-- 
Yann

Re: [RFC PATCH] detection of directory renames

[Jakub Narebski]

Yann Dirson <ydirson@altern.org> writes:

> This is a first very preliminar patch, mostly so people can comment
> early on the big picture.  It has a number of limitations, many but
> not all already listed as FIXME's in the patch itself.  If anything in
> this patch seems so wrong it is not worth polishing it, it's the
> perfect time to say so :)

What happened to this work? I din't see it mentioned in "what's
cooking..." announcements...

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [RFC PATCH] detection of directory renames

[Yann Dirson]

On Mon, Oct 27, 2008 at 06:35:44AM -0700, Jakub Narebski wrote:
> Yann Dirson <ydirson@altern.org> writes:
> 
> > This is a first very preliminar patch, mostly so people can comment
> > early on the big picture.  It has a number of limitations, many but
> > not all already listed as FIXME's in the patch itself.  If anything in
> > this patch seems so wrong it is not worth polishing it, it's the
> > perfect time to say so :)
> 
> What happened to this work? I din't see it mentioned in "what's
> cooking..." announcements...

I'm slowly bugfixing it, and plan to post a slightly updated version
soon.