{"thread":{"id":"15323","subject":"diffcore and directory renames","startedAt":"2008-09-01T21:39:04Z","lastAt":"2008-10-27T19:13:16Z","messageCount":11,"participants":["Yann Dirson","Junio C Hamano","Andreas Ericsson","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"89444","messageId":"20080901213904.GP4985@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"15323","inReplyTo":null,"subject":"diffcore and directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-01T21:39:04Z","receivedAt":"2008-09-01T21:39:04Z","isPatch":false,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"I often found myself lost when looking at a diff where a couple of\nlarge dirs where renamed, and a handful of files were modified to take\nthe rename into account - not a rare situation, I'd say.  In such a\ncase, the diffs themselves are mostly hidden among numerous rename\nentries.\n\nTo that, I felt that git ought to know better, and could easily\npresent a directory rename as such.  Among the advantages of having\nsuch \"dir rename detection\", aside from readability which we should\nnot neglect, we'd have more accurate \"svn dcommit\" for such renames\nand, and better decisions made when merging a branch with adds a file\ninto a dir, with a branch which renames that dir (ok, maybe not that\nfrequent, but still).\n\n\nLooking closer at the current behaviour, I realized that git-diff-tree\n*is* already able to report such renames in raw mode :\n\n$ ./git-diff-tree 0f1027 -M\n0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3\n:040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved\n\n... but patch output breaks this into file moves, and even other\ncommands which I would have expected to display the same do in fact\nnot (eg. \"git show --raw\").  Is there any reason for this ?  I would\nhave expected git-show to do the same as diff-tree, and it would not\nbe so much of a problem to introduce a special form of the \"rename\"\nchunk to handle dir renames ?\n\n\nSince current diff-tree behaviour is based on comparing tree hashs, it\nonly detects 100%-similarity renames, and naturally diff-index and\ndiff-files cannot even do that much yet.  However, an optional\nfactorization pass following rename detection could quite easily\ndetect if, when a containing directory disappears because of a set of\nrenames - this is what I have started to look at.\n\nSince what I propose is indeed just a factorization of file renames,\nit could be adequate to represent them as such instead of directory\nrenames, so as to read something like:\n\n|diff --git a/ppc/* b/moved/\n|rename from ppc/*\n|rename to moved/\n\nThis would have the additional advantage of also working when the\ntarget destination was pre-existing, and when merging several dirs\ninto a single one - while at the same time to mistaking the reader too\nmuch into thinking that git cares about directories so much ;)\n\nCallers should also be careful about interpreting the output when\nmixing this behaviour with file filtering, obviously, so it is not\nmeant to be activated by default.\n\nDoes any of this sound sensible ?\n\n\nOn the technical side, I figured out that the best way to plug the\nfactorization was inside diffcore_rename to take advantage of the fact\nit has a list of all renames, that's not going to be published out of\nthis function - that only left me the \"cleanup:\" label as insertion\npoint, not that I find it conceptually very comfortable :)\n\nBut if I have understood correctly, diffcore only gets access to\nchanged filepairs, and does not know about the trees it is comparing.\n\nThe most sensible way to go I can think of would be to give to\ndiffcore enough information (src and dst tree-hash|\"INDEX\"|\"WORKING\nCOPY\") to be able to know for directory existence.  I'd rather check\nit does not sound completely wrong to anyone before going into that -\nopinions ?\n\nBest regards,\n-- \nYann\n"},{"id":"89452","messageId":"7vfxojtr9t.fsf@gitster.siamese.dyndns.org","threadId":"15323","inReplyTo":"20080901213904.GP4985@nan92-1-81-57-214-146.fbx.proxad.net","subject":"Re: diffcore and directory renames","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-09-01T22:50:22Z","receivedAt":"2008-09-01T22:50:22Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> I often found myself lost when looking at a diff where a couple of\n> large dirs where renamed, and a handful of files were modified to take\n> the rename into account - not a rare situation, I'd say.  In such a\n> case, the diffs themselves are mostly hidden among numerous rename\n> entries.\n\nYes, I've hinted here number of times that rename detection could notice\nthe fact that neighbouring paths are migrating to the same directory and\nboost similarity scores of leftover paths that did not otherwise made the\nthreshold in such a situation.\n\nI am glad to see finally somebody got interested ;-)\n\n> $ ./git-diff-tree 0f1027 -M\n> 0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3\n> :040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved\n\nYes, diff-tree can show this, and you should be able to teach diff-index\nwith a clean cache-tree to do similar, but this only applies to the\nnon-recursive 100% rename at the toplevel, which is too narrow a special\ncase to be interesting at all.  We perhaps further could run the\nsimilarity comparison on the raw tree objects if we wanted to so that you\ncan find inexact matches, but I think it is going in the wrong direction.\n\nThe thing is, diffcore is designed to be a general mechanism to unify\ncomparisons on two arbitrary sets of files, be they from tree-vs-tree,\ntree-vs-index, tree-vs-worktree, or index-vs-worktree.  The machinery\nshould be able to operate on any two sets of files in the same way and\nproduce more-or-less the same results.  It is Ok for callers to give extra\nhints, when available, to speed up the computation, but the core of the\nalgorithm should not depend on the presense of such hints to deduce the\nrenames.\n\nSo please aim to make the hint-less case, \"diff-files --no-index\", produce\na sensible result.  That should be the first step.\n"},{"id":"89543","messageId":"20080902204802.GS4985@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"15323","inReplyTo":"7vfxojtr9t.fsf@gitster.siamese.dyndns.org","subject":"Re: diffcore and directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-02T20:48:02Z","receivedAt":"2008-09-02T20:48:02Z","isPatch":false,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Mon, Sep 01, 2008 at 03:50:22PM -0700, Junio C Hamano wrote:\n> Yes, I've hinted here number of times that rename detection could notice\n> the fact that neighbouring paths are migrating to the same directory and\n> boost similarity scores of leftover paths that did not otherwise made the\n> threshold in such a situation.\n\nWow, that's a great idea I did not think about :)\n\n> I am glad to see finally somebody got interested ;-)\n\nI am glad we're on the same side :)\n\n> > $ ./git-diff-tree 0f1027 -M\n> > 0f1027e1aceb4bc5fa682776ab9f72935e2cd1b3\n> > :040000 040000 6f6159f0245784352414ff38ffb68bae80f30bd6 6f6159f0245784352414ff38ffb68bae80f30bd6 R100   ppc     moved\n> \n> Yes, diff-tree can show this, and you should be able to teach diff-index\n> with a clean cache-tree to do similar, but this only applies to the\n> non-recursive 100% rename at the toplevel, which is too narrow a special\n> case to be interesting at all.  We perhaps further could run the\n> similarity comparison on the raw tree objects if we wanted to so that you\n> can find inexact matches, but I think it is going in the wrong direction.\n\nAgreed.\n\n> The thing is, diffcore is designed to be a general mechanism to unify\n> comparisons on two arbitrary sets of files, be they from tree-vs-tree,\n> tree-vs-index, tree-vs-worktree, or index-vs-worktree.  The machinery\n> should be able to operate on any two sets of files in the same way and\n> produce more-or-less the same results.  It is Ok for callers to give extra\n> hints, when available, to speed up the computation, but the core of the\n> algorithm should not depend on the presense of such hints to deduce the\n> renames.\n\nMy idea was rather to just see tree/index/worktree as just 3\nspecialized forms of a single \"abstract tree\" of some sort,\neffectively unifying things.\n\nBut anyway afterwards I thought that there may be something for me to\nlearn in how --find-copies-harder gets its information for\nnon-modified sources of copies -- I'll have a look at that.\n\n\n> So please aim to make the hint-less case, \"diff-files --no-index\", produce\n> a sensible result.  That should be the first step.\n\nOK.\n\nBest regards,\n-- \nYann\n"},{"id":"91637","messageId":"20080925213819.27029.47944.stgit@gandelf.nowhere.earth","threadId":"15323","inReplyTo":"7vfxojtr9t.fsf@gitster.siamese.dyndns.org","subject":"[RFC PATCH] detection of directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-25T21:47:01Z","receivedAt":"2008-09-25T21:47:01Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"This is a first very preliminar patch, mostly so people can comment\nearly on the big picture.  It has a number of limitations, many but\nnot all already listed as FIXME's in the patch itself.  If anything in\nthis patch seems so wrong it is not worth polishing it, it's the\nperfect time to say so :)\n\nThe idea is to add a new pass to diffcore-rename, to group file renames\nlooking like a full directory move, and then to hide those file\nrenames which do not carry any additionnal information.\n\nHere is a sample run:\n\n$ ./git-diff-tree ee491 --factorize-renames -r \n[DBG] possible rename from arm/ to bar/\n[DBG] possible rename from ppc/ to moved/\n[DBG] discarding dir rename of arm/, mixing moved/ and bar/\n[DBG] ppc/* -> moved/* makes ppc/sha1ppc.S -> moved/sha1ppc.S uninteresting\n[DBG] ppc/* -> moved/* makes ppc/sha1.c -> moved/sha1.c uninteresting\nee491a42190ec6e716f46a55fa0a7f4e307f1629\n:040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100   ppc/    moved/\n:100644 100644 9e3ae038e818f4e21bc50f864fc5204f6fa44daa 9e3ae038e818f4e21bc50f864fc5204f6fa44daa R100   arm/sha1.c      bar/sha1.c\n:100644 100644 3952646349cf9d033177e69ba9433652a378c0e9 3952646349cf9d033177e69ba9433652a378c0e9 R100   arm/sha1.h      bar/sha1.h\n:100644 100644 c3c51aa4d487f2e85c02b0257c1f0b57d6158d76 c065eeef7d68ea91863431788e20cd814c5ac52c R099   ppc/sha1.h      moved/sha1.h\n:100644 100644 8c1cb99fb403875af85e4d1524d21f7eb818f59b 8c1cb99fb403875af85e4d1524d21f7eb818f59b R100   arm/sha1_arm.S  moved/sha1_arm.S\n\n-- \nYann Dirson    <ydirson@altern.org> |\nDebian-related: <dirson@debian.org> |   Support Debian GNU/Linux:\n                                    |  Freedom, Power, Stability, Gratis\n     http://ydirson.free.fr/        | Check <http://www.debian.org/>\n"},{"id":"91638","messageId":"20080925214707.27029.36260.stgit@gandelf.nowhere.earth","threadId":"15323","inReplyTo":"20080925213819.27029.47944.stgit@gandelf.nowhere.earth","subject":"[PATCH] Introduce patch factorization in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-25T21:47:07Z","receivedAt":"2008-09-25T21:47:07Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"\n---\n\n diff-lib.c        |    6 +-\n diff.c            |    5 +\n diff.h            |    3 +\n diffcore-rename.c |  194 +++++++++++++++++++++++++++++++++++++++++++++++++++--\n diffcore.h        |    1 \n tree-diff.c       |    4 +\n 6 files changed, 202 insertions(+), 11 deletions(-)\n\ndiff --git a/diff-lib.c b/diff-lib.c\nindex ae96c64..dcc4c2c 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -179,7 +179,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)\n \t\tchanged = ce_match_stat(ce, &st, ce_option);\n \t\tif (!changed) {\n \t\t\tce_mark_uptodate(ce);\n-\t\t\tif (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))\n+\t\t\tif (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&\n+\t\t\t    !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))\n \t\t\t\tcontinue;\n \t\t}\n \t\toldmode = ce->ce_mode;\n@@ -310,7 +311,8 @@ static int show_modified(struct oneway_unpack_data *cbdata,\n \n \toldmode = old->ce_mode;\n \tif (mode == oldmode && !hashcmp(sha1, old->sha1) &&\n-\t    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))\n+\t    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&\n+\t    !DIFF_OPT_TST(&revs->diffopt, FACTORIZE_RENAMES))\n \t\treturn 0;\n \n \tdiff_change(&revs->diffopt, oldmode, mode,\ndiff --git a/diff.c b/diff.c\nindex 9053d4d..2315980 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2599,6 +2599,11 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_OPT_SET(options, REVERSE_DIFF);\n \telse if (!strcmp(arg, \"--find-copies-harder\"))\n \t\tDIFF_OPT_SET(options, FIND_COPIES_HARDER);\n+\telse if (!strcmp(arg, \"--factorize-renames\")) {\n+\t\tDIFF_OPT_SET(options, FACTORIZE_RENAMES);\n+\t\tif (!options->detect_rename)\n+\t\t\toptions->detect_rename = DIFF_DETECT_RENAME;\n+\t}\n \telse if (!strcmp(arg, \"--follow\"))\n \t\tDIFF_OPT_SET(options, FOLLOW_RENAMES);\n \telse if (!strcmp(arg, \"--color\"))\ndiff --git a/diff.h b/diff.h\nindex 1ca4f46..7b862c6 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -64,6 +64,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,\n #define DIFF_OPT_RELATIVE_NAME       (1 << 17)\n #define DIFF_OPT_IGNORE_SUBMODULES   (1 << 18)\n #define DIFF_OPT_DIRSTAT_CUMULATIVE  (1 << 19)\n+#define DIFF_OPT_FACTORIZE_RENAMES   (1 << 20)\n #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)\n #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)\n #define DIFF_OPT_CLR(opts, flag)    ((opts)->flags &= ~DIFF_OPT_##flag)\n@@ -219,6 +220,8 @@ extern void diffcore_std(struct diff_options *);\n \"  -C            detect copies.\\n\" \\\n \"  --find-copies-harder\\n\" \\\n \"                try unchanged files as candidate for copy detection.\\n\" \\\n+\"  --factorize_renames\\n\" \\\n+\"                factorize renames of all files of a directory.\\n\" \\\n \"  -l<n>         limit rename attempts up to <n> paths.\\n\" \\\n \"  -O<file>      reorder diffs according to the <file>.\\n\" \\\n \"  -S<string>    find filepair whose only one side contains the string.\\n\" \\\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1b2ebb4..2757204 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,6 +6,8 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n \n+#include <libgen.h>\n+\n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n@@ -52,6 +54,32 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \treturn &(rename_dst[first]);\n }\n \n+static struct diff_rename_dst *locate_rename_dst_dir(struct diff_filespec *dir)\n+{\n+\t/* code mostly duplicated from locate_rename_dst - not sure we\n+\t * could merge them efficiently,though\n+\t */\n+\tint first, last;\n+\tint dirlength = strlen(dir->path);\n+\n+\tfirst = 0;\n+\tlast = rename_dst_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n+\t\tint cmp = strncmp(dir->path, dst->two->path, dirlength);\n+\t\tif (!cmp)\n+\t\t\treturn dst;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\t/* not found */\n+\treturn NULL;\n+}\n+\n /* Table of rename/copy src files */\n static struct diff_rename_src {\n \tstruct diff_filespec *one;\n@@ -409,6 +437,130 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+struct diff_dir_rename {\n+\tstruct diff_filespec *one;\n+\tstruct diff_filespec *two;\n+\tint discarded;\n+\tstruct diff_dir_rename* next;\n+};\n+\n+/*\n+ * Marks as such file_rename if it is made uninteresting by dir_rename.\n+ * Returns -1 if the file_rename is outside of the range in which given\n+ * renames concerned by dir_rename are to be found (ie. end of loop),\n+ * 0 otherwise.\n+ */\n+static int maybe_mark_uninteresting(struct diff_rename_dst* file_rename,\n+\t\t\t\t    struct diff_dir_rename* dir_rename,\n+\t\t\t\t    int one_len, int two_len) {\n+\tif (strncmp(file_rename->two->path,\n+\t\t    dir_rename->two->path, two_len))\n+\t\treturn -1;\n+\tif (strncmp(file_rename->pair->one->path,\n+\t\t    dir_rename->one->path, one_len) ||\n+\t    !basename_same(file_rename->pair->one, file_rename->two) ||\n+\t    file_rename->pair->score != MAX_SCORE)\n+\t\treturn 0;\n+\n+\tfile_rename->pair->uninteresting_rename = 1;\n+\tprintf (\"[DBG] %s* -> %s* makes %s -> %s uninteresting\\n\",\n+\t\tdir_rename->one->path, dir_rename->two->path,\n+\t\tfile_rename->pair->one->path, file_rename->two->path);\n+\treturn 0;\n+}\n+\n+/*\n+ * FIXME: we could optimize the 100%-rename case by preventing\n+ * recursion to unfold what we know we would refold here.\n+ * FIXME: do we want to replace linked list with sorted array ?\n+ * FIXME: this prototype only handles renaming of dirs without\n+ * a subdir.\n+ * FIXME: leaks like hell.\n+ * FIXME: ideas to evaluate a similarity score, anyone ?\n+ *  10% * tree similarity + 90% * moved files similarity ?\n+ */\n+static struct diff_dir_rename* factorization_candidates = NULL;\n+static void diffcore_factorize_renames(void)\n+{\n+\tchar buffer[PATH_MAX], one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];\n+\tint i;\n+\n+\tfor (i = 0; i < rename_dst_nr; i++) {\n+\t\tif (!rename_dst[i].pair)\n+\t\t\tcontinue;\n+\t\tstrcpy(buffer, rename_dst[i].pair->one->path);\n+\t\tstrcpy(one_parent_path, dirname(buffer));\n+\t\tstrcat(one_parent_path, \"/\");\n+\n+\t\tstruct diff_filespec* one_parent = alloc_filespec(one_parent_path);\n+\t\tfill_filespec(one_parent, null_sha1 /*FIXME*/, S_IFDIR);\n+\n+\t\tif (!locate_rename_dst_dir(one_parent)) {\n+\t\t\t// one_parent_path is empty in result tree\n+\n+\t\t\t// already considered ?\n+\t\t\tstruct diff_dir_rename* seen;\n+\t\t\tfor (seen=factorization_candidates; seen; seen = seen->next)\n+\t\t\t\tif (!strcmp(seen->one->path, one_parent_path)) break;\n+\t\t\tif (!seen) {\n+\t\t\t\t// record potential dir rename\n+\t\t\t\tstrcpy(buffer, rename_dst[i].pair->two->path);\n+\t\t\t\tstrcpy(two_parent_path, dirname(buffer));\n+\t\t\t\tstrcat(two_parent_path, \"/\");\n+\n+\t\t\t\tseen = xmalloc(sizeof(*seen));\n+\t\t\t\tseen->one = one_parent;\n+\t\t\t\tseen->two = alloc_filespec(two_parent_path);\n+\t\t\t\tfill_filespec(seen->two, null_sha1 /*FIXME*/, S_IFDIR);\n+\t\t\t\tseen->discarded = 0;\n+\t\t\t\tseen->next = factorization_candidates;\n+\t\t\t\tfactorization_candidates = seen;\n+\t\t\t\tprintf(\"[DBG] possible rename from %s to %s\\n\",\n+\t\t\t\t       one_parent_path, two_parent_path);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (seen->discarded)\n+\t\t\t\tcontinue;\n+\t\t\t// check that seen entry matches this rename\n+\t\t\tstrcpy(buffer, rename_dst[i].pair->two->path);\n+\t\t\tstrcpy(two_parent_path, dirname(buffer));\n+\t\t\tstrcat(two_parent_path, \"/\");\n+\t\t\tif (strcmp(two_parent_path, seen->two->path)) {\n+\t\t\t\tprintf(\"[DBG] discarding dir rename of %s, mixing %s and %s\\n\",\n+\t\t\t\t       one_parent_path, two_parent_path, seen->two->path);\n+\t\t\t\tseen->discarded = 1;\n+\t\t\t}\n+\n+\t\t\t/* all checks ok, we keep that entry */\n+\t\t}\n+\t}\n+\n+\t// turn candidates into real renames\n+\tstruct diff_dir_rename* candidate;\n+\tfor (candidate=factorization_candidates; candidate; candidate = candidate->next) {\n+\t\tint two_idx, i, one_len, two_len;\n+\t\tif (candidate->discarded)\n+\t\t\tcontinue;\n+\n+\t\t// any entry within candidate dst dir\n+\t\ttwo_idx = locate_rename_dst_dir(candidate->two) - rename_dst;\n+\n+\t\t// now remove extraneous 100% files inside.\n+\t\tone_len = strlen(candidate->one->path);\n+\t\ttwo_len = strlen(candidate->two->path);\n+\t\tfor (i = two_idx; i < rename_dst_nr; i++)\n+\t\t\tif (maybe_mark_uninteresting (rename_dst+i, candidate,\n+\t\t\t\t\t\t      one_len, two_len) < 0)\n+\t\t\t\tbreak;\n+\t\tfor (i = two_idx-1; i >= 0; i--)\n+\t\t\tif (maybe_mark_uninteresting (rename_dst+i, candidate,\n+\t\t\t\t\t\t      one_len, two_len) < 0)\n+\t\t\t\tbreak;\n+\t}\n+\n+\treturn;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -446,13 +598,22 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tp->one->rename_used++;\n \t\t\tregister_rename_src(p->one, p->score);\n \t\t}\n-\t\telse if (detect_rename == DIFF_DETECT_COPY) {\n-\t\t\t/*\n-\t\t\t * Increment the \"rename_used\" score by\n-\t\t\t * one, to indicate ourselves as a user.\n-\t\t\t */\n-\t\t\tp->one->rename_used++;\n-\t\t\tregister_rename_src(p->one, p->score);\n+\t\telse {\n+\t\t\tif (detect_rename == DIFF_DETECT_COPY) {\n+\t\t\t\t/*\n+\t\t\t\t * Increment the \"rename_used\" score by\n+\t\t\t\t * one, to indicate ourselves as a user.\n+\t\t\t\t */\n+\t\t\t\tp->one->rename_used++;\n+\t\t\t\tregister_rename_src(p->one, p->score);\n+\t\t\t}\n+\t\t\tif (DIFF_OPT_TST(options, FACTORIZE_RENAMES)) {\n+\t\t\t\t/* similarly, rename factorization needs to\n+\t\t\t\t * see all files from second tree\n+\t\t\t\t */\n+\t\t\t\t//p->two->rename_used++; // FIXME: would we need that ?\n+\t\t\t\tlocate_rename_dst(p->two, 1);\n+\t\t\t}\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n@@ -561,8 +722,24 @@ void diffcore_rename(struct diff_options *options)\n \t/* At this point, we have found some renames and copies and they\n \t * are recorded in rename_dst.  The original list is still in *q.\n \t */\n+\n+\t/* Now possibly factorize those renames and copies. */\n+\tif (DIFF_OPT_TST(options, FACTORIZE_RENAMES))\n+\t\tdiffcore_factorize_renames();\n+\n \toutq.queue = NULL;\n \toutq.nr = outq.alloc = 0;\n+\n+\t// first, turn factorization_candidates into real renames\n+\tstruct diff_dir_rename* candidate;\n+\tfor (candidate=factorization_candidates; candidate; candidate = candidate->next) {\n+\t\tstruct diff_filepair* pair;\n+\t\tif (candidate->discarded) continue;\n+\t\tpair = diff_queue(&outq, candidate->one, candidate->two);\n+\t\tpair->score = MAX_SCORE;\n+\t\tpair->renamed_pair = 1;\n+\t}\n+\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tstruct diff_filepair *pair_to_free = NULL;\n@@ -577,7 +754,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_rename_dst *dst =\n \t\t\t\tlocate_rename_dst(p->two, 0);\n \t\t\tif (dst && dst->pair) {\n-\t\t\t\tdiff_q(&outq, dst->pair);\n+\t\t\t\tif (!dst->pair->uninteresting_rename)\n+\t\t\t\t\tdiff_q(&outq, dst->pair);\n \t\t\t\tpair_to_free = p;\n \t\t\t}\n \t\t\telse\ndiff --git a/diffcore.h b/diffcore.h\nindex 8ae3578..e4aa099 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -62,6 +62,7 @@ struct diff_filepair {\n \tunsigned broken_pair : 1;\n \tunsigned renamed_pair : 1;\n \tunsigned is_unmerged : 1;\n+\tunsigned uninteresting_rename : 1;\n };\n #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)\n \ndiff --git a/tree-diff.c b/tree-diff.c\nindex 9f67af6..872f757 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -49,7 +49,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \t\tshow_entry(opt, \"+\", t2, base, baselen);\n \t\treturn 1;\n \t}\n-\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)\n+\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) &&\n+\t    !DIFF_OPT_TST(opt, FACTORIZE_RENAMES) &&\n+\t    !hashcmp(sha1, sha2) && mode1 == mode2)\n \t\treturn 0;\n \n \t/*\n"},{"id":"91641","messageId":"48DC133A.7010805@op5.se","threadId":"15323","inReplyTo":"20080925214707.27029.36260.stgit@gandelf.nowhere.earth","subject":"Re: [PATCH] Introduce patch factorization in diffcore.","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-09-25T22:39:54Z","receivedAt":"2008-09-25T22:39:54Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Yann Dirson wrote:\n>  \"                try unchanged files as candidate for copy detection.\\n\" \\\n> +\"  --factorize_renames\\n\" \\\n> +\"                factorize renames of all files of a directory.\\n\" \\\n\n\nUse dashes to separate words in arguments, please.\n\n\n>  \n> +#include <libgen.h>\n> +\n\n +#ifdef basename\n +# undef basename\n +#endif\n\nWe might as well use the GNU version of basename() at least. Even if\nyou don't use it, I'd rather not see this bite some unwary programmer\ncoming along after you. Worst case scenario, sha1's won't add up if\nPOSIX basename alters its argument, making for one fiendishly tricky\nbug to find.\n\n> +/*\n> + * FIXME: we could optimize the 100%-rename case by preventing\n> + * recursion to unfold what we know we would refold here.\n> + * FIXME: do we want to replace linked list with sorted array ?\n\nEither that or a hash. Most of the time seems to be spent in lookups.\nWith a hash you get quick lookups and reasonably quick inserts. With\na sorted array you get lower memory footprint than anything else and\ncan bisect your way to the right entry, which performs reasonably\nclose to skiplists. The sort overhead might be a deterrant factor,\nbut insofar as I understand it trees are always sorted in git anyway,\nso perhaps that'd be the best solution.\n\nApart from that, I'd need to apply the patch to review it properly,\nand I'm far too tired for that now.\n\nI like the direction this is going though, so thanks a lot for doing\nit :)\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"91646","messageId":"m3bpyb3jci.fsf@localhost.localdomain","threadId":"15323","inReplyTo":"20080925213819.27029.47944.stgit@gandelf.nowhere.earth","subject":"Re: [RFC PATCH] detection of directory renames","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-09-25T23:19:20Z","receivedAt":"2008-09-25T23:19:20Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> This is a first very preliminar patch, mostly so people can comment\n> early on the big picture.  It has a number of limitations, many but\n> not all already listed as FIXME's in the patch itself.  If anything in\n> this patch seems so wrong it is not worth polishing it, it's the\n> perfect time to say so :)\n> \n> The idea is to add a new pass to diffcore-rename, to group file renames\n> looking like a full directory move, and then to hide those file\n> renames which do not carry any additionnal information.\n> \n> Here is a sample run:\n> \n> $ ./git-diff-tree ee491 --factorize-renames -r \n> [DBG] possible rename from arm/ to bar/\n> [DBG] possible rename from ppc/ to moved/\n> [DBG] discarding dir rename of arm/, mixing moved/ and bar/\n> [DBG] ppc/* -> moved/* makes ppc/sha1ppc.S -> moved/sha1ppc.S uninteresting\n> [DBG] ppc/* -> moved/* makes ppc/sha1.c -> moved/sha1.c uninteresting\n> ee491a42190ec6e716f46a55fa0a7f4e307f1629\n> :040000 040000 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 R100   ppc/    moved/\n> :100644 100644 9e3ae038e818f4e21bc50f864fc5204f6fa44daa 9e3ae038e818f4e21bc50f864fc5204f6fa44daa R100   arm/sha1.c      bar/sha1.c\n> :100644 100644 3952646349cf9d033177e69ba9433652a378c0e9 3952646349cf9d033177e69ba9433652a378c0e9 R100   arm/sha1.h      bar/sha1.h\n> :100644 100644 c3c51aa4d487f2e85c02b0257c1f0b57d6158d76 c065eeef7d68ea91863431788e20cd814c5ac52c R099   ppc/sha1.h      moved/sha1.h\n> :100644 100644 8c1cb99fb403875af85e4d1524d21f7eb818f59b 8c1cb99fb403875af85e4d1524d21f7eb818f59b R100   arm/sha1_arm.S  moved/sha1_arm.S\n\nWonderfull!!!\n\nI like it very much, and hope that it would get improved. And that you\nwould be able to use it in merges too, to allow for example for new\nfiles to be created in renamed directory instead of old one which does\nnot exist any longer (c.f. http://www.markshuttleworth.com/archives/123\nand following articles).\n\nFor the future, could you show examples with --abbrev option in use? TIA.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"91712","messageId":"20080926190614.GA4985@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"15323","inReplyTo":"m3bpyb3jci.fsf@localhost.localdomain","subject":"Re: [RFC PATCH] detection of directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-26T19:06:14Z","receivedAt":"2008-09-26T19:06:14Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Thu, Sep 25, 2008 at 04:19:20PM -0700, Jakub Narebski wrote:\n> Wonderfull!!!\n\nWow, I love this feedback :)\n\n> I like it very much, and hope that it would get improved. And that you\n> would be able to use it in merges too, to allow for example for new\n> files to be created in renamed directory instead of old one which does\n> not exist any longer (c.f. http://www.markshuttleworth.com/archives/123\n> and following articles).\n\nYes, that's one of planned things.  Along the same line (once renames\nare stabilized), I think about extending things so that \"split dirs\"\nare detected as well, so merge can flag a conflict when there is a\ndoubt that a file would really be added in a \"split directory\".  The\nsituation may be obvious in my example (arm/ contents dispatched into\nbar/ and moved/), but may also be useful when we can detect that a\nsignificant number of files have been moved out of a directory.\n\n> For the future, could you show examples with --abbrev option in use? TIA.\n\nGood idea.\n\nBest regards,\n-- \nYann\n"},{"id":"91713","messageId":"20080926192108.GC17458@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"15323","inReplyTo":"48DC133A.7010805@op5.se","subject":"Re: [PATCH] Introduce patch factorization in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-09-26T19:21:08Z","receivedAt":"2008-09-26T19:21:08Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Fri, Sep 26, 2008 at 12:39:54AM +0200, Andreas Ericsson wrote:\n> Yann Dirson wrote:\n>>  \"                try unchanged files as candidate for copy detection.\\n\" \\\n>> +\"  --factorize_renames\\n\" \\\n>> +\"                factorize renames of all files of a directory.\\n\" \\\n>\n>\n> Use dashes to separate words in arguments, please.\n\nFortunately, the typo only made it to the help string, thanks for\ncatching it :)\n\n>>  +#include <libgen.h>\n>> +\n>\n> +#ifdef basename\n> +# undef basename\n> +#endif\n>\n> We might as well use the GNU version of basename() at least. Even if\n> you don't use it, I'd rather not see this bite some unwary programmer\n> coming along after you. Worst case scenario, sha1's won't add up if\n> POSIX basename alters its argument, making for one fiendishly tricky\n> bug to find.\n\nI'll look into that, thanks\n\n>> +/*\n>> + * FIXME: we could optimize the 100%-rename case by preventing\n>> + * recursion to unfold what we know we would refold here.\n>> + * FIXME: do we want to replace linked list with sorted array ?\n>\n> Either that or a hash. Most of the time seems to be spent in lookups.\n> With a hash you get quick lookups and reasonably quick inserts. With\n> a sorted array you get lower memory footprint than anything else and\n> can bisect your way to the right entry, which performs reasonably\n> close to skiplists. The sort overhead might be a deterrant factor,\n> but insofar as I understand it trees are always sorted in git anyway,\n> so perhaps that'd be the best solution.\n\nThanks for this insight - I'll wait before changing the data structure,\nsince the current implementation may need to be able to recurse (consider\nrenamed subdirs as well as renamed files).\n\n> Apart from that, I'd need to apply the patch to review it properly,\n> and I'm far too tired for that now.\n>\n> I like the direction this is going though, so thanks a lot for doing\n> it :)\n\nGreat :)\n\nBest regards,\n-- \nYann\n"},{"id":"94047","messageId":"m3fxmignz3.fsf@localhost.localdomain","threadId":"15323","inReplyTo":"20080925213819.27029.47944.stgit@gandelf.nowhere.earth","subject":"Re: [RFC PATCH] detection of directory renames","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-10-27T13:35:44Z","receivedAt":"2008-10-27T13:35:44Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> This is a first very preliminar patch, mostly so people can comment\n> early on the big picture.  It has a number of limitations, many but\n> not all already listed as FIXME's in the patch itself.  If anything in\n> this patch seems so wrong it is not worth polishing it, it's the\n> perfect time to say so :)\n\nWhat happened to this work? I din't see it mentioned in \"what's\ncooking...\" announcements...\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"94066","messageId":"20081027191316.GC5158@nan92-1-81-57-214-146.fbx.proxad.net","threadId":"15323","inReplyTo":"m3fxmignz3.fsf@localhost.localdomain","subject":"Re: [RFC PATCH] detection of directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2008-10-27T19:13:16Z","receivedAt":"2008-10-27T19:13:16Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"On Mon, Oct 27, 2008 at 06:35:44AM -0700, Jakub Narebski wrote:\n> Yann Dirson <ydirson@altern.org> writes:\n> \n> > This is a first very preliminar patch, mostly so people can comment\n> > early on the big picture.  It has a number of limitations, many but\n> > not all already listed as FIXME's in the patch itself.  If anything in\n> > this patch seems so wrong it is not worth polishing it, it's the\n> > perfect time to say so :)\n> \n> What happened to this work? I din't see it mentioned in \"what's\n> cooking...\" announcements...\n\nI'm slowly bugfixing it, and plan to post a slightly updated version\nsoon.\n"}]}