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;
/*
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
