{"thread":{"id":"25584","subject":"[PATCH v8] Detection of directory renames","startedAt":"2010-10-28T22:08:27Z","lastAt":"2010-11-25T17:19:36Z","messageCount":15,"participants":["Yann Dirson","Jonathan Nieder","Ævar Arnfjörð Bjarmason"],"isPatch":true,"patchVersion":8,"patchTotal":null},"messages":[{"id":"154684","messageId":"1288303712-14662-1-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":null,"subject":"[PATCH v8] Detection of directory renames","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:27Z","receivedAt":"2010-10-28T22:08:27Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Changes since v7:\n\n* turned debug traces off but allow them to be easily turned on\n* corrected example in gitdiffcore.txt (Junio)\n* unidiff output changes:\n * don't use \"diff --git\" to avoid confusing git-apply, use\n --git-detect-bulk-moves instead (Junio, 2008)\n * use \"bulk move with similarity index NNN%\"\n * don't use trailing asterisk, useless there\n* added missing &&'s in testsuite\n* improved short help messages\n* documented the unidiff output format and --hide-bulk-move-details\n* splitted raw output format, under discussion, into its own patch\n* improved commit messages, including current rationale for using \"/*\"\n* listed bulk-removal/copy/add as possible future related works\n* renamed test script for consistency\n\nI'll experiment next with bulk-removal detection, with bulk-move\nrerolled on top of it.\n"},{"id":"154685","messageId":"1288303712-14662-2-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"[PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:28Z","receivedAt":"2010-10-28T22:08:28Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"This feature tries to group together files moving from and to\nidentical directories - a common case being directory renames.\n\nThis only adds the detection logic. The output of raw diff is displayed\nas \"Rnnn a/ b/\", and unified diff does not display them at all. Output\nformats will be refined later in the series.\n\nIt is implemented as a new pass in diffcore-rename, occuring after the\nfile renames get detected, grouping those renames looking like a move\nof a full directory into some other place. It is activated by the new\n--detect-bulk-moves diffcore flag.\n\nPossible optimisations to this code include:\n* avoid use of i_am_not_single by using a separate list\n* use a more informative prefixcmp to avoid strcmp calls\n eg. in discard_if_outside()\n* optimize for bulk insertions (avoid useless successive memmove's)\n\nOther future developements to be made on top of this include:\n* detect bulk removals (well, that one is rather a subset than a layer above),\n and possibly bulk additions\n* detect bulk copies\n* detect inexact bulk-moves/copies (where some files were not moved, or were\n moved to a different place) - problem of computing a similarity score\n* display as such the special case of directory move/rename\n* application of such new diffs: issue a conflict, or just a warning ?\n* teach git-svn (and others ?) to make use of that flag\n* handle new conflict type \"bulk-move/add\"\n* detect \"directory splits\" as well\n* use inexact dir renames to bump score of below-threshold renames\n from/to same locations\n* support other types of bluk-grouping, like prefixes (see eg. kernel\n 5d1e859c), and maybe config-specified patterns\n* add yours here\n\nThis patch has been improved by the following contributions:\n- Jonathan Nieder: better implementation of copy_dirname()\n- Jonathan Nieder: portable implementation of memrchr() in another patch\n- Junio C Hamano: split individual renames hiding under control of another flag\n- Junio C Hamano: coding style issues\n- Junio C Hamano: better examples\n- Ævar Arnfjörð Bjarmason: Don't use C99 comments.\n- Jonathan Nieder: just too many other helpful suggestions to list them all\n\nThanks-to: Jonathan Nieder \nThanks-to: Junio C Hamano \nThanks-to: Ævar Arnfjörð Bjarmason \nSigned-off-by: Yann Dirson \n---\n Documentation/diff-options.txt | 4 +\n Documentation/gitdiffcore.txt | 12 ++\n diff-lib.c | 6 +-\n diff.c | 5 +\n diff.h | 3 +\n diffcore-rename.c | 370 ++++++++++++++++++++++++++++++++++++++--\n diffcore.h | 1 +\n tree-diff.c | 4 +-\n 8 files changed, 391 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex bfd0b57..887df4b 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -245,6 +245,10 @@ endif::git-log[]\n \tdelete/add pair to be a rename if more than 90% of the file\n \thasn't changed.\n \n+--detect-bulk-moves::\n+\tDetect bulk move of all files of a directory into a\n+\tdifferent one.\n+\n -C[]::\n --detect-copies[=]::\n \tDetect copies as well as renames. See also `--find-copies-harder`.\ndiff --git a/Documentation/gitdiffcore.txt b/Documentation/gitdiffcore.txt\nindex 6af29a4..93111ac 100644\n--- a/Documentation/gitdiffcore.txt\n+++ b/Documentation/gitdiffcore.txt\n@@ -175,6 +175,18 @@ the expense of making it slower. Without `\\--find-copies-harder`,\n 'git diff-{asterisk}' commands can detect copies only if the file that was\n copied happened to have been modified in the same changeset.\n \n+Bulk move of all files of a directory into a different one can get\n+detected using the `\\--detect-bulk-moves` option. This adds an\n+additional pass on top of the results of per-file rename detection.\n+They are reported with NULL SHA1 id, in addition to the file renames:\n+\n+------------------------------------------------\n+:040000 040000 0000000... 0000000... R100 foo/ bar/\n+:100644 100644 0123456... 1234567... R090 foo/file0 bar/file3\n+:100644 100644 2345678... 2345678... R100 foo/file1 bar/file1\n+:100644 100644 3456789... 3456789... R100 foo/file2 bar/file2\n+------------------------------------------------\n+\n \n diffcore-merge-broken: For Putting \"Complete Rewrites\" Back Together\n --------------------------------------------------------------------\ndiff --git a/diff-lib.c b/diff-lib.c\nindex 392ce2b..5ec3ddc 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -208,7 +208,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)\n \t\t\t\t\t\t ce_option, &dirty_submodule);\n \t\tif (!changed && !dirty_submodule) {\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, DETECT_BULK_MOVES))\n \t\t\t\tcontinue;\n \t\t}\n \t\toldmode = ce->ce_mode;\n@@ -338,7 +339,8 @@ static int show_modified(struct rev_info *revs,\n \n \toldmode = old->ce_mode;\n \tif (mode == oldmode && !hashcmp(sha1, old->sha1) && !dirty_submodule &&\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, DETECT_BULK_MOVES))\n \t\treturn 0;\n \n \tdiff_change(&revs->diffopt, oldmode, mode,\ndiff --git a/diff.c b/diff.c\nindex d1c6b91..2eba335 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3191,6 +3191,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, \"--detect-bulk-moves\")) {\n+\t\tDIFF_OPT_SET(options, DETECT_BULK_MOVES);\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 0083d92..1e2506c 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -78,6 +78,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)\n #define DIFF_OPT_IGNORE_UNTRACKED_IN_SUBMODULES (1 << 25)\n #define DIFF_OPT_IGNORE_DIRTY_SUBMODULES (1 << 26)\n #define DIFF_OPT_OVERRIDE_SUBMODULE_CONFIG (1 << 27)\n+#define DIFF_OPT_DETECT_BULK_MOVES (1 << 28)\n \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@@ -265,6 +266,8 @@ extern void diffcore_fix_diff_index(struct diff_options *);\n \" -C detect copies.\\n\" \\\n \" --find-copies-harder\\n\" \\\n \" try unchanged files as candidate for copy detection.\\n\" \\\n+\" --detect-bulk-moves\\n\" \\\n+\" detect moves of all files of a single directory.\\n\" \\\n \" -l limit rename attempts up to paths.\\n\" \\\n \" -O reorder diffs according to the .\\n\" \\\n \" -S find filepair whose only one side contains the string.\\n\" \\\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..6afc662 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,14 +6,34 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n \n+#define DEBUG_BULKMOVE 0\n+\n+#if DEBUG_BULKMOVE\n+#define debug_bulkmove(args) __debug_bulkmove args\n+void __debug_bulkmove(const char *fmt, ...)\n+{\n+\tva_list ap;\n+\tva_start(ap, fmt);\n+\tfprintf(stderr, \"[DBG] \");\n+\tvfprintf(stderr, fmt, ap);\n+\tva_end(ap);\n+}\n+#else\n+#define debug_bulkmove(args) do { /*nothing */ } while (0)\n+#endif\n+\n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n+\tunsigned i_am_not_single:1; /* does not look for a match, only here to be looked at */\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n \n+/*\n+ * Do a binary search of \"two\" in \"rename_dst\", inserting it if not found.\n+ */\n static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \t\t\t\t\t\t int insert_ok)\n {\n@@ -49,9 +69,36 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \trename_dst[first].two = alloc_filespec(two->path);\n \tfill_filespec(rename_dst[first].two, two->sha1, two->mode);\n \trename_dst[first].pair = NULL;\n+\trename_dst[first].i_am_not_single = 0;\n \treturn &(rename_dst[first]);\n }\n \n+/*\n+ * Do a binary search in \"rename_dst\" of any entry under \"dirname\".\n+ */\n+static struct diff_rename_dst *locate_rename_dst_dir(const char *dirname)\n+{\n+\tint first, last;\n+\tint prefixlength = strlen(dirname);\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(dirname, dst->two->path, prefixlength);\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@@ -386,8 +433,11 @@ static int find_exact_renames(void)\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, -1, i, rename_src[i].one);\n \n-\tfor (i = 0; i < rename_dst_nr; i++)\n+\tfor (i = 0; i < rename_dst_nr; i++) {\n+\t\tif (rename_dst[i].i_am_not_single)\n+\t\t\tcontinue;\n \t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n+\t}\n \n \t/* Find the renames */\n \ti = for_each_hash(&file_table, find_same_files);\n@@ -414,6 +464,270 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+static struct diff_bulk_rename {\n+\tstruct diff_filespec *one;\n+\tstruct diff_filespec *two;\n+\tint discarded;\n+} *bulkmove_candidates;\n+static int bulkmove_candidates_nr, bulkmove_candidates_alloc;\n+\n+/*\n+ * Do a binary search of \"one\" in \"bulkmove_candidate\", inserting it if not\n+ * found.\n+ * A good part was copy-pasted from locate_rename_dst().\n+ */\n+static struct diff_bulk_rename *locate_bulkmove_candidate(const char *one_path,\n+\t\t\t\t\t\t\t const char *two_path)\n+{\n+\tint first, last;\n+\n+\tfirst = 0;\n+\tlast = bulkmove_candidates_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct diff_bulk_rename *candidate = &(bulkmove_candidates[next]);\n+\t\t/* primary sort key on one_path, secondary on two_path */\n+\t\tint cmp = strcmp(one_path, candidate->one->path);\n+\t\tif (!cmp)\n+\t\t\tcmp = strcmp(two_path, candidate->two->path);\n+\t\tif (!cmp)\n+\t\t\treturn candidate;\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+\t/* insert to make it at \"first\" */\n+\tif (bulkmove_candidates_alloc <= bulkmove_candidates_nr) {\n+\t\tbulkmove_candidates_alloc = alloc_nr(bulkmove_candidates_alloc);\n+\t\tbulkmove_candidates = xrealloc(bulkmove_candidates,\n+\t\t\t\t bulkmove_candidates_alloc * sizeof(*bulkmove_candidates));\n+\t}\n+\tbulkmove_candidates_nr++;\n+\tif (first < bulkmove_candidates_nr)\n+\t\tmemmove(bulkmove_candidates + first + 1, bulkmove_candidates + first,\n+\t\t\t(bulkmove_candidates_nr - first - 1) * sizeof(*bulkmove_candidates));\n+\n+\tbulkmove_candidates[first].one = alloc_filespec(one_path);\n+\tfill_filespec(bulkmove_candidates[first].one, null_sha1, S_IFDIR);\n+\tbulkmove_candidates[first].two = alloc_filespec(two_path);\n+\tfill_filespec(bulkmove_candidates[first].two, null_sha1, S_IFDIR);\n+\tbulkmove_candidates[first].discarded = 0;\n+\treturn &(bulkmove_candidates[first]);\n+}\n+\n+/*\n+ * Copy dirname of src into dst, suitable to append a filename without\n+ * an additional \"/\".\n+ * Only handles relative paths since there is no absolute path in a git repo.\n+ * Writes \"\" when there is no \"/\" in src.\n+ * May overwrite more chars than really needed, if src ends with a \"/\".\n+ * Supports in-place modification of src by passing dst == src.\n+ */\n+static const char *copy_dirname(char *dst, const char *src)\n+{\n+\tsize_t len = strlen(src);\n+\tconst char *slash;\n+\tchar *end;\n+\n+\tif (len > 0 && src[len - 1] == '/')\n+\t\t/* Trailing slash. Ignore it. */\n+\t\tlen--;\n+\n+\tslash = memrchr(src, '/', len);\n+\tif (!slash) {\n+\t\t*dst = '\\0';\n+\t\treturn dst;\n+\t}\n+\n+\tend = mempcpy(dst, src, slash - src + 1);\n+\t*end = '\\0';\n+\treturn dst;\n+}\n+\n+// FIXME: leaks like hell.\n+/* See if the fact that one_leftover exists under one_parent_path in\n+ * dst tree should disqualify one_parent_path from bulkmove eligibility.\n+ * Return 1 if it disqualifies, 0 if it is OK.\n+ */\n+static int dispatched_to_different_dirs(const char *one_parent_path)\n+{\n+\t/* this might be a dir split, or files added\n+\t * after the bulk move, or just an isolated\n+\t * rename */\n+\tint two_idx, j, onep_len, maybe_dir_rename;\n+\tstruct diff_rename_dst *one_leftover =\n+\t\tone_leftover = locate_rename_dst_dir(one_parent_path);\n+\n+\tif (!one_leftover)\n+\t\treturn 0;\n+\n+\t/* try to see if it is a file added after the bulk move */\n+\ttwo_idx = one_leftover - rename_dst;\n+\tonep_len = strlen(one_parent_path);\n+\tmaybe_dir_rename = 1;\n+\n+\t/* check no leftover file was already here before */\n+\tfor (j = two_idx; j < rename_dst_nr; j++) {\n+\t\tif (strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))\n+\t\t\tbreak; /* exhausted directory in this direction */\n+\t\tdebug_bulkmove((\"leftover file %s in %s\\n\",\n+\t\t\t\trename_dst[j].two->path, one_parent_path));\n+\t\tif (rename_dst[j].i_am_not_single || /* those were already here */\n+\t\t (rename_dst[j].pair &&\n+\t\t !strncmp(rename_dst[j].pair->one->path,\n+\t\t\t one_parent_path, onep_len) && /* renamed from here */\n+\t\t strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))) { /* not to a subdir */\n+\t\t\tmaybe_dir_rename = 0;\n+\t\t\tdebug_bulkmove((\"... tells not a bulk move\\n\"));\n+\t\t\tbreak;\n+\t\t}\n+\t\tdebug_bulkmove((\"... not believed to prevent bulk move\\n\"));\n+\t}\n+\tif (!maybe_dir_rename)\n+\t\treturn 1;\n+\t/* try the other direction (dup code) */\n+\tfor (j = two_idx-1; j >= 0; j--) {\n+\t\tif (strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))\n+\t\t\tbreak; /* exhausted directory in this direction */\n+\t\tdebug_bulkmove((\"leftover file %s in '%s'\\n\",\n+\t\t\t\trename_dst[j].two->path, one_parent_path));\n+\t\tif (rename_dst[j].i_am_not_single || /* those were already here */\n+\t\t (rename_dst[j].pair &&\n+\t\t !strncmp(rename_dst[j].pair->one->path,\n+\t\t\t one_parent_path, onep_len) && /* renamed from here */\n+\t\t strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))) { /* not to a subdir */\n+\t\t\tmaybe_dir_rename = 0;\n+\t\t\tdebug_bulkmove((\"... tells not a bulk move\\n\"));\n+\t\t\tbreak;\n+\t\t}\n+\t\tdebug_bulkmove((\"... not believed to prevent bulk move\\n\"));\n+\t}\n+\tif (!maybe_dir_rename)\n+\t\treturn 1;\n+\n+\t/* Here we are in the case where a directory\n+\t * content was completely moved, but files\n+\t * were added to it afterwards. Proceed as\n+\t * for a simple bulk move. */\n+\treturn 0;\n+}\n+\n+/*\n+ * Assumes candidate->one is a subdir of seen->one, mark 'seen' as\n+ * discarded if candidate->two is outside seen->two. Also mark\n+ * 'candidate' itself as discarded if the conflict implies so.\n+ *\n+ * Return 1 if 'seen' was discarded\n+ */\n+static int discard_if_outside(struct diff_bulk_rename *candidate,\n+\t\t\t struct diff_bulk_rename *seen) {\n+\tif (!prefixcmp(candidate->two->path, seen->two->path)) {\n+\t\tdebug_bulkmove((\" 'dstpair' conforts 'seen'\\n\"));\n+\t\treturn 0;\n+\t} else {\n+\t\tdebug_bulkmove((\"discarding %s -> %s from bulk moves (split into %s and %s)\\n\",\n+\t\t\t\tseen->one->path, seen->two->path,\n+\t\t\t\tcandidate->two->path, seen->two->path));\n+\t\tseen->discarded = 1;\n+\t\t/* Need to discard dstpair as well, unless moving from\n+\t\t * a strict subdir of seen->one or to a strict subdir\n+\t\t * of seen->two */\n+\t\tif (!strcmp(seen->one->path, candidate->one->path) &&\n+\t\t prefixcmp(seen->two->path, candidate->two->path)) {\n+\t\t\tdebug_bulkmove((\"... and not adding self\\n\"));\n+\t\t\tcandidate->discarded = 1;\n+\t\t}\n+\t\treturn 1;\n+\t}\n+}\n+\n+/*\n+ * Check if the rename specified by \"dstpair\" could cause a\n+ * bulk move to be detected, record it in bulkmove_candidates if yes.\n+ */\n+static void check_one_bulk_move(struct diff_filepair *dstpair)\n+{\n+\tchar one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];\n+\n+\t/* genuine new files (or believed to be so) */\n+\tif (!dstpair)\n+\t\treturn;\n+\t/* dummy renames used by copy detection */\n+\tif (!strcmp(dstpair->one->path, dstpair->two->path))\n+\t\treturn;\n+\n+\tcopy_dirname(one_parent_path, dstpair->one->path);\n+\tcopy_dirname(two_parent_path, dstpair->two->path);\n+\n+\t/* simple rename with no directory change */\n+\tif (!strcmp(one_parent_path, two_parent_path))\n+\t\treturn;\n+\n+\tdebug_bulkmove((\"[] %s -> %s ?\\n\", dstpair->one->path, dstpair->two->path));\n+\n+\t/* loop up one_parent_path over successive parents */\n+\t// FIXME: also loop over two_parent_path prefixes\n+\tdo {\n+\t\tstruct diff_bulk_rename *seen;\n+\t\tint old_nr = bulkmove_candidates_nr;\n+\t\tstruct diff_bulk_rename *candidate =\n+\t\t\tlocate_bulkmove_candidate(one_parent_path, two_parent_path);\n+\t\tdebug_bulkmove((\"[[]] %s ...\\n\", one_parent_path));\n+\t\tif (old_nr == bulkmove_candidates_nr) {\n+\t\t\tdebug_bulkmove((\" already seen\\n\"));\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* After this commit, are there any files still under one_parent_path ?\n+\t\t * Any file left would disqualifies this dir for bulk move.\n+\t\t */\n+\t\tif (dispatched_to_different_dirs(one_parent_path)) {\n+\t\t\t// FIXME: check overlap with discard_if_outside()\n+\t\t\tcandidate->discarded = 1;\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* walk up for one_parent_path prefixes */\n+\t\tfor (seen = candidate-1; (seen >= bulkmove_candidates) &&\n+\t\t\t !prefixcmp(one_parent_path, seen->one->path); seen--) {\n+\t\t\tdebug_bulkmove((\" ? %s -> %s\\n\", seen->one->path, seen->two->path));\n+\t\t\t/* subdir of \"seen\" dest dir ? */\n+\t\t\tif (discard_if_outside(candidate, seen))\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\t/* look down for other moves from one_parent_path */\n+\t\tseen = candidate + 1;\n+\t\tif (seen != bulkmove_candidates + bulkmove_candidates_nr &&\n+\t\t !strcmp(one_parent_path, seen->one->path)) {\n+\t\t\tdebug_bulkmove((\" ? %s -> %s (2)\\n\", seen->one->path, seen->two->path));\n+\t\t\t/* subdir of \"seen\" dest dir ? */\n+\t\t\tif (discard_if_outside(candidate, seen))\n+\t\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/* next parent if any */\n+\t\tcopy_dirname(one_parent_path, one_parent_path);\n+\t} while (*one_parent_path);\n+}\n+\n+/*\n+ * Take all file renames recorded so far and check if they could cause\n+ * a bulk move to be detected.\n+ */\n+static void diffcore_bulk_moves(void)\n+{\n+\tint i;\n+\tfor (i = 0; i < rename_dst_nr; i++)\n+\t\tcheck_one_bulk_move(rename_dst[i].pair);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -424,6 +738,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count;\n \tint num_create, num_src, dst_cnt;\n+\tstruct diff_bulk_rename *candidate;\n \n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n@@ -438,8 +753,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tcontinue; /* not interested */\n \t\t\telse\n \t\t\t\tlocate_rename_dst(p->two, 1);\n-\t\t}\n-\t\telse if (!DIFF_FILE_VALID(p->two)) {\n+\t\t} else if (!DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n \t\t\t * If the source is a broken \"delete\", and\n \t\t\t * they did not really want to get broken,\n@@ -450,14 +764,23 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tif (p->broken_pair && !p->score)\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\t} else {\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, DETECT_BULK_MOVES)) {\n+\t\t\t\t/* similarly, bulk move detection needs to\n+\t\t\t\t * see all files from second tree, but we don't\n+\t\t\t\t * want them to be matched against single sources.\n+\t\t\t\t */\n+\t\t\t\t// FIXME: check interaction with --find-copies-harder\n+\t\t\t\tlocate_rename_dst(p->two, 1)->i_am_not_single = 1;\n+\t\t\t}\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n@@ -509,6 +832,8 @@ void diffcore_rename(struct diff_options *options)\n \n \t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n+\t\tif (rename_dst[i].i_am_not_single)\n+\t\t\tcontinue; /* not looking for a match. */\n \n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n@@ -569,7 +894,30 @@ 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, DETECT_BULK_MOVES))\n+\t\tdiffcore_bulk_moves();\n+\n \tDIFF_QUEUE_CLEAR(&outq);\n+\n+\t/* Now turn non-discarded bulkmove_candidates into real renames */\n+\tfor (candidate = bulkmove_candidates;\n+\t candidate < bulkmove_candidates + bulkmove_candidates_nr; candidate++) {\n+\t\tstruct diff_filepair* pair;\n+\t\tif (candidate->discarded)\n+\t\t\tcontinue;\n+\t\t/* visualize toplevel dir if needed */\n+\t\tif (!*candidate->one->path)\n+\t\t\tcandidate->one->path = \"./\";\n+\t\tif (!*candidate->two->path)\n+\t\t\tcandidate->two->path = \"./\";\n+\t\tpair = diff_queue(&outq, candidate->one, candidate->two);\n+\t\tpair->score = MAX_SCORE;\n+\t\tpair->renamed_pair = 1;\n+\t\tpair->is_bulkmove = 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;\ndiff --git a/diffcore.h b/diffcore.h\nindex b8f1fde..6dab95b 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -69,6 +69,7 @@ struct diff_filepair {\n \tunsigned broken_pair : 1;\n \tunsigned renamed_pair : 1;\n \tunsigned is_unmerged : 1;\n+\tunsigned is_bulkmove : 1;\n };\n #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)\n \ndiff --git a/tree-diff.c b/tree-diff.c\nindex 12c9a88..89cedd4 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, DETECT_BULK_MOVES) &&\n+\t !hashcmp(sha1, sha2) && mode1 == mode2)\n \t\treturn 0;\n \n \t/*\n-- \n1.7.2.3\n"},{"id":"154690","messageId":"1288303712-14662-3-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"[PATCH v8 2/5] Raw diff output format for bulk moves.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:29Z","receivedAt":"2010-10-28T22:08:29Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"To distinguish the general bulk-move case (where the destination\ndirectory was pre-existing) from the directory-rename case (where it\nwas not), the output of raw diff is displayed as \"Rnnn a/* b/\". Those\ncannot be confused with renames of files named \"whatever/*\" with a\nliteral star character, from the full-zero SHA1's.\n\nSigned-off-by: Yann Dirson \n---\n Documentation/gitdiffcore.txt | 2 +-\n diff.c | 9 ++++++++-\n 2 files changed, 9 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/gitdiffcore.txt b/Documentation/gitdiffcore.txt\nindex 93111ac..2538dc0 100644\n--- a/Documentation/gitdiffcore.txt\n+++ b/Documentation/gitdiffcore.txt\n@@ -181,7 +181,7 @@ additional pass on top of the results of per-file rename detection.\n They are reported with NULL SHA1 id, in addition to the file renames:\n \n ------------------------------------------------\n-:040000 040000 0000000... 0000000... R100 foo/ bar/\n+:040000 040000 0000000... 0000000... R100 foo/* bar/\n :100644 100644 0123456... 1234567... R090 foo/file0 bar/file3\n :100644 100644 2345678... 2345678... R100 foo/file1 bar/file1\n :100644 100644 3456789... 3456789... R100 foo/file2 bar/file2\ndiff --git a/diff.c b/diff.c\nindex 2eba335..948eb76 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3490,7 +3490,14 @@ static void diff_flush_raw(struct diff_filepair *p, struct diff_options *opt)\n \tif (p->status == DIFF_STATUS_COPIED ||\n \t p->status == DIFF_STATUS_RENAMED) {\n \t\tconst char *name_a, *name_b;\n-\t\tname_a = p->one->path;\n+\t\tif (p->is_bulkmove) {\n+\t\t\t/* append \"*\" to the first dirname */\n+\t\t\tchar buf[PATH_MAX];\n+\t\t\tchar *next = memccpy(buf, p->one->path, '\\0', PATH_MAX);\n+\t\t\tnext[-1] = '*'; *next = '\\0';\n+\t\t\tname_a = buf;\n+\t\t} else\n+\t\t\tname_a = p->one->path;\n \t\tname_b = p->two->path;\n \t\tstrip_prefix(opt->prefix_length, &name_a, &name_b);\n \t\twrite_name_quoted(name_a, opt->file, inter_name_termination);\n-- \n1.7.2.3\n"},{"id":"154688","messageId":"1288303712-14662-4-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"[PATCH v8 3/5] Add testcases for the --detect-bulk-moves diffcore flag.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:30Z","receivedAt":"2010-10-28T22:08:30Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"This notably includes a couple of tests for cases known not to be\nworking correctly yet.\n\nThis patch has been improved by the following contributions:\n- Jonathan Nieder: reworked style of test script\n- Jonathan Nieder: use \"git commit\" in test instead of only plumbing,\n and use test_tick\n- Sverre Rabbelier: anonymize hashes\n\nThanks-to: Jonathan Nieder \nThanks-to: Sverre Rabbelier \nSigned-off-by: Yann Dirson \n---\n t/t4046-diff-bulk-move.sh | 296 +++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 296 insertions(+), 0 deletions(-)\n create mode 100755 t/t4046-diff-bulk-move.sh\n\ndiff --git a/t/t4046-diff-bulk-move.sh b/t/t4046-diff-bulk-move.sh\nnew file mode 100755\nindex 0000000..4b1c78e\n--- /dev/null\n+++ b/t/t4046-diff-bulk-move.sh\n@@ -0,0 +1,296 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2008,2010 Yann Dirson\n+# Copyright (c) 2005 Junio C Hamano\n+#\n+\n+# TODO for dir renames:\n+# * two dirs or more moving all their files to a single dir\n+# * simultaneous bulkmove and rename\n+\n+test_description='Test rename factorization in diff engine.\n+\n+'\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/diff-lib.sh\n+\n+test_expect_success 'setup' '\n+\tgit commit --allow-empty -m \"original empty commit\"\n+\n+\tmkdir a &&\n+\tprintf \"Line %s\\n\" 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 >a/path0 &&\n+\tsed a/path1 s/Line/Record/ &&\n+\tsed a/path2 s/Line/Stuff/ &&\n+\tsed a/path3 s/Line/Blurb/ &&\n+\n+\tgit update-index --add a/path* &&\n+\ttest_tick &&\n+\tgit commit -m \"original set of files\" &&\n+\n+\t: rename the directory &&\n+\tgit mv a b\n+'\n+test_expect_success 'diff-index --detect-bulk-moves after directory move.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/*\tb/\n+\t:100644 100644 X X R#\ta/path0\tb/path0\n+\t:100644 100644 X X R#\ta/path1\tb/path1\n+\t:100644 100644 X X R#\ta/path2\tb/path2\n+\t:100644 100644 X X R#\ta/path3\tb/path3\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup non-100% rename' '\n+\techo \"Line 16\" >>b/path0 &&\n+\tgit mv b/path2 b/2path &&\n+\tgit rm -f b/path3 &&\n+\techo anything >b/path100 &&\n+\tgit add b/path100\n+'\n+test_expect_success 'diff-index --detect-bulk-moves after content changes.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/*\tb/\n+\t:100644 000000 X X D#\ta/path3\n+\t:100644 100644 X X R#\ta/path2\tb/2path\n+\t:100644 100644 X X R#\ta/path0\tb/path0\n+\t:100644 100644 X X R#\ta/path1\tb/path1\n+\t:000000 100644 X X A#\tb/path100\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup bulk move that is not directory move' '\n+\tgit reset -q --hard &&\n+\n+\tmkdir c &&\n+\t(\n+\t\tfor i in 0 1 2; do\n+\t\t\tcp a/path$i c/apath$i || exit\n+\t\tdone\n+\t) &&\n+\tgit update-index --add c/apath* &&\n+\ttest_tick &&\n+\tgit commit -m \"first set of changes\" &&\n+\n+\tgit mv c/* a/\n+'\n+test_expect_success 'diff-index --detect-bulk-moves without full-dir rename.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\tc/*\ta/\n+\t:100644 100644 X X R#\tc/apath0\ta/apath0\n+\t:100644 100644 X X R#\tc/apath1\ta/apath1\n+\t:100644 100644 X X R#\tc/apath2\ta/apath2\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup bulk move with new file in source dir' '\n+\techo > c/anotherpath \"How much wood?\" &&\n+\tgit update-index --add c/another*\n+'\n+test_expect_success 'diff-index --detect-bulk-moves with new file in source dir.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\tc/*\ta/\n+\t:100644 100644 X X R#\tc/apath0\ta/apath0\n+\t:100644 100644 X X R#\tc/apath1\ta/apath1\n+\t:100644 100644 X X R#\tc/apath2\ta/apath2\n+\t:000000 100644 X X A#\tc/anotherpath\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup bulk move with interfering copy' '\n+\trm c/anotherpath &&\n+\tgit update-index --remove c/anotherpath &&\n+\tmkdir b &&\n+\tcp a/apath0 b/apath9 &&\n+\techo >> a/apath0 \"more\" &&\n+\tgit update-index --add a/apath0 b/apath9\n+'\n+# scores select the \"wrong\" one as \"moved\" (only a suboptimal detection)\n+test_expect_failure 'diff-index --detect-bulk-moves with interfering copy.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\tc/*\ta/\n+\t:100644 100644 X X R#\tc/apath0\ta/apath0\n+\t:100644 100644 X X R#\tc/apath1\ta/apath1\n+\t:100644 100644 X X R#\tc/apath2\ta/apath2\n+\t:100644 100644 X X C#\tc/apath0\tb/apath9\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup bulk move to toplevel' '\n+\tgit reset -q --hard &&\n+\tgit mv c/* .\n+'\n+test_expect_success 'diff-index --detect-bulk-moves bulk move to toplevel.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\tc/*\t./\n+\t:100644 100644 X X R#\tc/apath0\tapath0\n+\t:100644 100644 X X R#\tc/apath1\tapath1\n+\t:100644 100644 X X R#\tc/apath2\tapath2\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup move including a subdir, with some content changes' '\n+\tgit reset -q --hard &&\n+\tmv c a/ &&\n+\tgit update-index --add --remove a/c/* c/apath0 c/apath1 c/apath2 &&\n+\ttest_tick &&\n+\tgit commit -m \"move as subdir\" &&\n+\n+\tgit mv a b &&\n+\techo foo >>b/c/apath0 &&\n+\tgit update-index --add b/c/apath*\n+'\n+test_expect_success 'diff-index --detect-bulk-moves on a move including a subdir.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/*\tb/\n+\t:040000 040000 X X R#\ta/c/*\tb/c/\n+\t:100644 100644 X X R#\ta/c/apath0\tb/c/apath0\n+\t:100644 100644 X X R#\ta/c/apath1\tb/c/apath1\n+\t:100644 100644 X X R#\ta/c/apath2\tb/c/apath2\n+\t:100644 100644 X X R#\ta/path0\tb/path0\n+\t:100644 100644 X X R#\ta/path1\tb/path1\n+\t:100644 100644 X X R#\ta/path2\tb/path2\n+\t:100644 100644 X X R#\ta/path3\tb/path3\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup move of only a subdir' '\n+\tgit reset -q --hard &&\n+\t: rename a subdirectory of a/. &&\n+\tgit mv a/c a/d\n+'\n+test_expect_success 'moving a subdir only' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/c/*\ta/d/\n+\t:100644 100644 X X R#\ta/c/apath0\ta/d/apath0\n+\t:100644 100644 X X R#\ta/c/apath1\ta/d/apath1\n+\t:100644 100644 X X R#\ta/c/apath2\ta/d/apath2\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup move without a subdir' '\n+\tgit reset -q --hard &&\n+\tmkdir b &&\n+\t: rename files in the directory but not subdir. &&\n+\tgit mv a/path* b/\n+'\n+test_expect_success 'moving files but not subdirs is not mistaken for dir move' '\n+\tcat >expected <<-EOF &&\n+\t:100644 100644 X X R#\ta/path0\tb/path0\n+\t:100644 100644 X X R#\ta/path1\tb/path1\n+\t:100644 100644 X X R#\ta/path2\tb/path2\n+\t:100644 100644 X X R#\ta/path3\tb/path3\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup move of files and subdirs to different places' '\n+\tgit reset -q --hard &&\n+\tgit mv a/c b &&\n+\tgit mv a d\n+'\n+test_expect_success 'moving subdirs into one dir and files into another is not mistaken for dir move' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/c/*\tb/\n+\t:100644 100644 X X R#\ta/c/apath0\tb/apath0\n+\t:100644 100644 X X R#\ta/c/apath1\tb/apath1\n+\t:100644 100644 X X R#\ta/c/apath2\tb/apath2\n+\t:100644 100644 X X R#\ta/path0\td/path0\n+\t:100644 100644 X X R#\ta/path1\td/path1\n+\t:100644 100644 X X R#\ta/path2\td/path2\n+\t:100644 100644 X X R#\ta/path3\td/path3\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+# the same with different ordering\n+test_expect_success 'setup move of files and subdirs to different places' '\n+\tgit mv d 0\n+'\n+test_expect_success 'moving subdirs into one dir and files into another is not mistaken for dir move' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/c/*\tb/\n+\t:100644 100644 X X R#\ta/path0\t0/path0\n+\t:100644 100644 X X R#\ta/path1\t0/path1\n+\t:100644 100644 X X R#\ta/path2\t0/path2\n+\t:100644 100644 X X R#\ta/path3\t0/path3\n+\t:100644 100644 X X R#\ta/c/apath0\tb/apath0\n+\t:100644 100644 X X R#\ta/c/apath1\tb/apath1\n+\t:100644 100644 X X R#\ta/c/apath2\tb/apath2\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_expect_success 'setup move of dir with only subdirs' '\n+\tgit reset -q --hard &&\n+\tmkdir a/b &&\n+\tmv a/path* a/b/ &&\n+\tgit update-index --add --remove a/path0 a/path1 a/path2 a/path3 a/b/path* &&\n+\ttest_tick &&\n+\tgit commit -m \"move all toplevel files down one level\" &&\n+\n+\tgit mv a z\n+'\n+# TODO: only a suboptimal non-detection\n+test_expect_failure 'moving a dir with no direct children files' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\ta/*\tz/\n+\t:040000 040000 X X R#\ta/b/*\tz/b/\n+\t:040000 040000 X X R#\ta/c/*\tz/c/\n+\t:100644 100644 X X R#\ta/b/path0\tz/b/path0\n+\t:100644 100644 X X R#\ta/b/path1\tz/b/path1\n+\t:100644 100644 X X R#\ta/b/path2\tz/b/path2\n+\t:100644 100644 X X R#\ta/b/path3\tz/b/path3\n+\t:100644 100644 X X R#\ta/c/apath0\tz/c/apath0\n+\t:100644 100644 X X R#\ta/c/apath1\tz/c/apath1\n+\t:100644 100644 X X R#\ta/c/apath2\tz/c/apath2\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+# now test moving all files from toplevel into subdir (does not hides file moves) (needs consensus on syntax)\n+# Note: this is a special case of move of a dir into one of its own subdirs, which in\n+# turn is a variant of new files/dirs being added into a dir after all its contents\n+# are moved away\n+\n+test_expect_success 'setup move from toplevel to subdir' '\n+\tgit reset -q --hard HEAD~3 &&\n+\tmv a/* . &&\n+\tgit update-index --add --remove a/path0 a/path1 a/path2 a/path3 path* &&\n+\ttest_tick &&\n+\tgit commit -m \"move all files to toplevel\" &&\n+\n+\tmkdir z &&\n+\tgit mv path* z/\n+'\n+test_expect_success '--detect-bulk-moves everything from toplevel.' '\n+\tcat >expected <<-EOF &&\n+\t:040000 040000 X X R#\t./*\tz/\n+\t:100644 100644 X X R#\tpath0\tz/path0\n+\t:100644 100644 X X R#\tpath1\tz/path1\n+\t:100644 100644 X X R#\tpath2\tz/path2\n+\t:100644 100644 X X R#\tpath3\tz/path3\n+\tEOF\n+\tgit diff-index --detect-bulk-moves HEAD >current &&\n+\tcompare_diff_raw expected current\n+'\n+\n+test_done\n-- \n1.7.2.3\n"},{"id":"154689","messageId":"1288303712-14662-5-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"[PATCH v8 4/5] Unified diff output format for bulk moves.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:31Z","receivedAt":"2010-10-28T22:08:31Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"The output produced is as shown below.\n\ndiff --git-detect-bulk-moves mips/nxp/pnx833x/common/ mips/pnx833x/common/\nbulk move with similarity index 100%\nbulk move from mips/nxp/pnx833x/common/\nbulk move to mips/pnx833x/common/\n\nSigned-off-by: Yann Dirson \n---\n Documentation/diff-generate-patch.txt | 19 +++++++++++++\n diff.c | 48 +++++++++++++++++++++++++-------\n 2 files changed, 56 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/diff-generate-patch.txt b/Documentation/diff-generate-patch.txt\nindex 3ac2bea..367e859 100644\n--- a/Documentation/diff-generate-patch.txt\n+++ b/Documentation/diff-generate-patch.txt\n@@ -71,6 +71,25 @@ separate lines indicate the old and the new mode.\n rename to a\n \n \n+bulk move entries\n+-----------------\n+\n+When a bulk move is detected, a special block is output in addition to\n+the renames that constitute the bulk move, looking like this:\n+\n+ diff --git-detect-bulk-moves a/dir1/ b/dir2/\n+\n+It is essentially similar to the standard diff header, with a special\n+syntax showing we are describing a difference between two directories,\n+and not a change to be applied as-is to a file.\n+\n+It is followed by three specific extended header lines:\n+\n+ bulk move with similarity index \n+ bulk move from /\n+ bulk move to /\n+\n+\n combined diff format\n --------------------\n \ndiff --git a/diff.c b/diff.c\nindex 948eb76..ab2e201 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2659,6 +2659,7 @@ static void run_diff_cmd(const char *pgm,\n \tconst char *xfrm_msg = NULL;\n \tint complete_rewrite = (p->status == DIFF_STATUS_MODIFIED) && p->score;\n \tint must_show_header = 0;\n+\tint use_color;\n \n \tif (!DIFF_OPT_TST(o, ALLOW_EXTERNAL))\n \t\tpgm = NULL;\n@@ -2668,14 +2669,36 @@ static void run_diff_cmd(const char *pgm,\n \t\t\tpgm = drv->external;\n \t}\n \n+\t/*\n+\t * don't use colors when the header is intended for an\n+\t * external diff driver\n+\t */\n+\tuse_color = DIFF_OPT_TST(o, COLOR_DIFF) && !pgm;\n+\n+\tif (p->is_bulkmove) {\n+\t\tconst char *set = diff_get_color(use_color, DIFF_METAINFO);\n+\t\tconst char *reset = diff_get_color(use_color, DIFF_RESET);\n+\t\tstruct strbuf *msgbuf;\n+\t\tchar *line_prefix = \"\";\n+\n+\t\tif (o->output_prefix) {\n+\t\t\tmsgbuf = o->output_prefix(o, o->output_prefix_data);\n+\t\t\tline_prefix = msgbuf->buf;\n+\t\t}\n+\t\tfprintf(o->file, \"%s%sdiff --git-detect-bulk-moves %s %s%s\\n\",\n+\t\t\tline_prefix, set, one->path, two->path, reset);\n+\t\tfprintf(o->file, \"%s%sbulk move with similarity index %d%%%s\\n\",\n+\t\t\tline_prefix, set, similarity_index(p), reset);\n+\t\tfprintf(o->file, \"%s%sbulk move from %s%s\\n\",\n+\t\t\tline_prefix, set, one->path, reset);\n+\t\tfprintf(o->file, \"%s%sbulk move to %s%s\\n\",\n+\t\t\tline_prefix, set, two->path, reset);\n+\t\treturn;\n+\t}\n+\n \tif (msg) {\n-\t\t/*\n-\t\t * don't use colors when the header is intended for an\n-\t\t * external diff driver\n-\t\t */\n \t\tfill_metainfo(msg, name, other, one, two, o, p,\n-\t\t\t &must_show_header,\n-\t\t\t DIFF_OPT_TST(o, COLOR_DIFF) && !pgm);\n+\t\t\t &must_show_header, use_color);\n \t\txfrm_msg = msg->len ? msg->buf : NULL;\n \t}\n \n@@ -2748,8 +2771,10 @@ static void run_diff(struct diff_filepair *p, struct diff_options *o)\n \t\treturn;\n \t}\n \n-\tdiff_fill_sha1_info(one);\n-\tdiff_fill_sha1_info(two);\n+\tif (!p->is_bulkmove) {\n+\t\tdiff_fill_sha1_info(one);\n+\t\tdiff_fill_sha1_info(two);\n+\t}\n \n \tif (!pgm &&\n \t DIFF_FILE_VALID(one) && DIFF_FILE_VALID(two) &&\n@@ -3548,9 +3573,10 @@ static void diff_flush_patch(struct diff_filepair *p, struct diff_options *o)\n \tif (diff_unmodified_pair(p))\n \t\treturn;\n \n-\tif ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||\n-\t (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode)))\n-\t\treturn; /* no tree diffs in patch format */\n+\tif (!p->is_bulkmove &&\n+\t ((DIFF_FILE_VALID(p->one) && S_ISDIR(p->one->mode)) ||\n+\t (DIFF_FILE_VALID(p->two) && S_ISDIR(p->two->mode))))\n+\t\treturn; /* no tree diffs in patch format, except for bulk moves */\n \n \trun_diff(p, o);\n }\n-- \n1.7.2.3\n"},{"id":"154686","messageId":"1288303712-14662-6-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"[PATCH v8 5/5] [WIP] Allow hiding renames of individual files involved in a directory rename.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-10-28T22:08:32Z","receivedAt":"2010-10-28T22:08:32Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Once has identified groups of bulk-moved files, and then\nthe --hide-bulk-move-details flag hides those of the individual renames\nwhich carry no other information (further name change, or content changes).\n\nThis makes it much easier to a human reader to spot content changes\nin a commit that also moves a whole subtree.\n\nSigned-off-by: Yann Dirson \n---\n Documentation/diff-options.txt | 5 +++\n diff.c | 7 ++++\n diff.h | 3 ++\n diffcore-rename.c | 68 ++++++++++++++++++++++++++++++++++++++--\n diffcore.h | 1 +\n 5 files changed, 81 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 887df4b..f9a2f4e 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -249,6 +249,11 @@ endif::git-log[]\n \tDetect bulk move of all files of a directory into a\n \tdifferent one.\n \n+--hide-bulk-move-details::\n+\tHide the individual files moves that make up a bulk move,\n+\twithout hinding other changes to the involved files (contents\n+\tchange, name change relative to the bulk move's destination).\n+\n -C[]::\n --detect-copies[=]::\n \tDetect copies as well as renames. See also `--find-copies-harder`.\ndiff --git a/diff.c b/diff.c\nindex ab2e201..b920f2e 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3221,6 +3221,13 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tif (!options->detect_rename)\n \t\t\toptions->detect_rename = DIFF_DETECT_RENAME;\n \t}\n+\telse if (!strcmp(arg, \"--hide-bulk-move-details\")) {\n+\t\tDIFF_OPT_SET(options, HIDE_DIR_RENAME_DETAILS);\n+\t\tif (!DIFF_OPT_TST(options, DETECT_BULK_MOVES))\n+\t\t\tDIFF_OPT_SET(options, DETECT_BULK_MOVES);\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 1e2506c..f28fed5 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -79,6 +79,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)\n #define DIFF_OPT_IGNORE_DIRTY_SUBMODULES (1 << 26)\n #define DIFF_OPT_OVERRIDE_SUBMODULE_CONFIG (1 << 27)\n #define DIFF_OPT_DETECT_BULK_MOVES (1 << 28)\n+#define DIFF_OPT_HIDE_DIR_RENAME_DETAILS (1 << 29)\n \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@@ -268,6 +269,8 @@ extern void diffcore_fix_diff_index(struct diff_options *);\n \" try unchanged files as candidate for copy detection.\\n\" \\\n \" --detect-bulk-moves\\n\" \\\n \" detect moves of all files of a single directory.\\n\" \\\n+\" --hide-bulk-move-details\\n\" \\\n+\" hide individual files moves in a bulk move.\\n\" \\\n \" -l limit rename attempts up to paths.\\n\" \\\n \" -O reorder diffs according to the .\\n\" \\\n \" -S find filepair whose only one side contains the string.\\n\" \\\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6afc662..940cb7d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -519,6 +519,34 @@ static struct diff_bulk_rename *locate_bulkmove_candidate(const char *one_path,\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_bulk_rename *dir_rename,\n+\t\t\t\t int one_len, int two_len)\n+{\n+\tif (!file_rename->pair) /* file add */\n+\t\treturn 0;\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+\tdebug_bulkmove((\"%s* -> %s* makes %s -> %s uninteresting\\n\",\n+\t\t\tdir_rename->one->path, dir_rename->two->path,\n+\t\t\tfile_rename->pair->one->path, file_rename->two->path));\n+\treturn 0;\n+}\n+\n+/*\n * Copy dirname of src into dst, suitable to append a filename without\n * an additional \"/\".\n * Only handles relative paths since there is no absolute path in a git repo.\n@@ -721,11 +749,44 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)\n * Take all file renames recorded so far and check if they could cause\n * a bulk move to be detected.\n */\n-static void diffcore_bulk_moves(void)\n+static void diffcore_bulk_moves(int opt_hide_renames)\n {\n \tint i;\n \tfor (i = 0; i < rename_dst_nr; i++)\n \t\tcheck_one_bulk_move(rename_dst[i].pair);\n+\n+\tif (opt_hide_renames) {\n+\t\t/* flag as \"uninteresting\" those candidates hidden by dir move */\n+\t\tstruct diff_bulk_rename *candidate;\n+\t\tfor (candidate = bulkmove_candidates;\n+\t\t candidate < bulkmove_candidates + bulkmove_candidates_nr;\n+\t\t candidate++) {\n+\t\t\tint two_idx, i, one_len, two_len;\n+\t\t\tstruct diff_rename_dst *two_sample;\n+\t\t\tif (candidate->discarded)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* bisect to any entry within candidate dst dir */\n+\t\t\ttwo_sample = locate_rename_dst_dir(candidate->two->path);\n+\t\t\tif (!two_sample) {\n+\t\t\t\tdie(\"PANIC: %s candidate of rename not in target tree (from %s)\\n\",\n+\t\t\t\t candidate->two->path, candidate->one->path);\n+\t\t\t}\n+\t\t\ttwo_idx = two_sample - rename_dst;\n+\n+\t\t\t/* now remove extraneous 100% files inside. */\n+\t\t\tone_len = strlen(candidate->one->path);\n+\t\t\ttwo_len = strlen(candidate->two->path);\n+\t\t\tfor (i = two_idx; i < rename_dst_nr; i++)\n+\t\t\t\tif (maybe_mark_uninteresting(rename_dst+i, candidate,\n+\t\t\t\t\t\t\t one_len, two_len) < 0)\n+\t\t\t\t\tbreak;\n+\t\t\tfor (i = two_idx-1; i >= 0; i--)\n+\t\t\t\tif (maybe_mark_uninteresting(rename_dst+i, candidate,\n+\t\t\t\t\t\t\t one_len, two_len) < 0)\n+\t\t\t\t\tbreak;\n+\t\t}\n+\t}\n }\n \n void diffcore_rename(struct diff_options *options)\n@@ -897,7 +958,7 @@ void diffcore_rename(struct diff_options *options)\n \n \t/* Now possibly factorize those renames and copies. */\n \tif (DIFF_OPT_TST(options, DETECT_BULK_MOVES))\n-\t\tdiffcore_bulk_moves();\n+\t\tdiffcore_bulk_moves(DIFF_OPT_TST(options, HIDE_DIR_RENAME_DETAILS));\n \n \tDIFF_QUEUE_CLEAR(&outq);\n \n@@ -932,7 +993,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 6dab95b..a4eb8e1 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -69,6 +69,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 \tunsigned is_bulkmove : 1;\n };\n #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)\n-- \n1.7.2.3\n"},{"id":"154709","messageId":"20101029010504.GA28984@burratino","threadId":"25584","inReplyTo":"1288303712-14662-1-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v8] Detection of directory renames","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-29T01:05:04Z","receivedAt":"2010-10-29T01:05:04Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> Changes since v7:\n\nMore history for new readers:\n\n - v7: http://thread.gmane.org/gmane.comp.version-control.git/159825\n - v6: http://thread.gmane.org/gmane.comp.version-control.git/159081\n - v5: http://thread.gmane.org/gmane.comp.version-control.git/158623\n - v1-4: http://thread.gmane.org/gmane.comp.version-control.git/157917/focus=157981\n"},{"id":"154711","messageId":"20101029014540.GB28984@burratino","threadId":"25584","inReplyTo":"1288303712-14662-2-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-29T01:45:40Z","receivedAt":"2010-10-29T01:45:40Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> Possible optimisations to this code include:\n> * avoid use of i_am_not_single by using a separate list\n\nI think that would help code clarity, too. It is tempting to try to\nsplit this patch into micropatches:\n\n1. introduce DETECT_DIRECTORY_RENAMES flag and hidden UI for it.\n\n2. if detecting bulk relocations, do not simplify input for\n diffcore by omitting unchanged files (just like when\n finding copies harder).\n\n3. introduce \"rename target candidate\" flag in rename_dsts.\n - if detecting copies, all diff targets are potential rename\n targets\n\n - if detecting bulk relocations but not copies, all diff\n targets are rename_dsts, but only file creation diff\n targets are potential rename targets\n\n - if detecting neither bulk reloc nor copies, only file\n creation diff targets are rename_dsts (and all are\n potential rename targets).\n\n Alternatively, rename_dsts that are not potential rename targets\n could be put in a different list (which is simpler and probably\n faster, while using a little more memory).\n\n4. honor rename_target_candidate flag (not needed if the\n non-candidates get their own list).\n\n5. introduce a list of potential directory relocations and functions\n to manipulate it.\n\n6. pass the (empty) list of relocated directories back to diffcore.\n\n7. populate the list of directory relocation candidates. If a file\n has been renamed to go from directory a/ to directory b/, we have a\n directory rename candidate.\n\n8. disqualify directories with stragglers left behind.\n\n9. disqualify directories for which the contents are not unanimous\n about where to go.\n\n10. add documentation and stop hiding the UI.\n\nTrivial comments on the patch:\n\n[...]\n> +++ b/diffcore-rename.c\n> @@ -6,14 +6,34 @@\n> #include \"diffcore.h\"\n> #include \"hash.h\"\n> \n> +#define DEBUG_BULKMOVE 0\n> +\n> +#if DEBUG_BULKMOVE\n> +#define debug_bulkmove(args) __debug_bulkmove args\n> +void __debug_bulkmove(const char *fmt, ...)\n> +{\n> +\tva_list ap;\n> +\tva_start(ap, fmt);\n> +\tfprintf(stderr, \"[DBG] \");\n> +\tvfprintf(stderr, fmt, ap);\n> +\tva_end(ap);\n> +}\n> +#else\n> +#define debug_bulkmove(args) do { /*nothing */ } while (0)\n> +#endif\n\nIs the debugging output infrequent enough to just use a function\nunconditionally?\n\n[...]\n> + * Supports in-place modification of src by passing dst == src.\n> + */\n> +static const char *copy_dirname(char *dst, const char *src)\n[...]\n> +\tend = mempcpy(dst, src, slash - src + 1);\n\nI suppose this should read:\n\n\tif (dst != src)\n\t\tmemcpy(dst, src, slash - src + 1);\n\tdst[slash - src + 1] = '\\0';\n\treturn dst;\n\n[...]\n> +static int discard_if_outside(struct diff_bulk_rename *candidate,\n> +\t\t\t struct diff_bulk_rename *seen) {\n\nStyle: '{' for functions goes in column 0.\n\n> +\tif (!prefixcmp(candidate->two->path, seen->two->path)) {\n> +\t\tdebug_bulkmove((\" 'dstpair' conforts 'seen'\\n\"));\n> +\t\treturn 0;\n> +\t} else {\n\nCan get some depth reduction by dropping the else here (since in\nthe trivial case we have already returned).\n\n> +static void diffcore_bulk_moves(void)\n> +{\n> +\tint i;\n> +\tfor (i = 0; i < rename_dst_nr; i++)\n> +\t\tcheck_one_bulk_move(rename_dst[i].pair);\n> +}\n\nYay. :)\n"},{"id":"154815","messageId":"20101029211852.GB5695@home.lan","threadId":"25584","inReplyTo":"20101029014540.GB28984@burratino","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-10-29T21:18:52Z","receivedAt":"2010-10-29T21:18:52Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Thu, Oct 28, 2010 at 08:45:40PM -0500, Jonathan Nieder wrote:\n> Yann Dirson wrote:\n> \n> > Possible optimisations to this code include:\n> > * avoid use of i_am_not_single by using a separate list\n> \n> I think that would help code clarity, too. It is tempting to try to\n> split this patch into micropatches:\n\nHm, I fear too much granularity would become meaningless :)\n\nA number of the steps you suggest (notably 8 and 9) would cause the\ncode to be plain wrong at some points, since those are part of what\nmakes the algorithm (appear to be) correct. This would not be a\nproblem only because that code would not be reachable throught any\nmeans, right ? If the code needs to be easier to understand, I'd\nrather add some more doc, than added commits that are basically\n\"useless for bisect\".\n\nI'm much more tempted to split into fully-functionnal patches that do\nadds reachable code paths (eg. bulk removal - although it's much more\nthan just a split of the patch).\n\n> 1. introduce DETECT_DIRECTORY_RENAMES flag and hidden UI for it.\n\nWhat do you mean by \"hidden UI\" ?\n\n[...]\n> 8. disqualify directories with stragglers left behind.\n> \n> 9. disqualify directories for which the contents are not unanimous\n> about where to go.\n\n[...]\n\n> Trivial comments on the patch:\n> \n> [...]\n> > +++ b/diffcore-rename.c\n> > @@ -6,14 +6,34 @@\n> > #include \"diffcore.h\"\n> > #include \"hash.h\"\n> > \n> > +#define DEBUG_BULKMOVE 0\n> > +\n> > +#if DEBUG_BULKMOVE\n> > +#define debug_bulkmove(args) __debug_bulkmove args\n> > +void __debug_bulkmove(const char *fmt, ...)\n> > +{\n> > +\tva_list ap;\n> > +\tva_start(ap, fmt);\n> > +\tfprintf(stderr, \"[DBG] \");\n> > +\tvfprintf(stderr, fmt, ap);\n> > +\tva_end(ap);\n> > +}\n> > +#else\n> > +#define debug_bulkmove(args) do { /*nothing */ } while (0)\n> > +#endif\n> \n> Is the debugging output infrequent enough to just use a function\n> unconditionally?\n\nYou mean, keep funccalls even with DEBUG_BULKMOVE is not set ? No,\nthere are too many traces for that.\n\n> [...]\n> > + * Supports in-place modification of src by passing dst == src.\n> > + */\n> > +static const char *copy_dirname(char *dst, const char *src)\n> [...]\n> > +\tend = mempcpy(dst, src, slash - src + 1);\n> \n> I suppose this should read:\n> \n> \tif (dst != src)\n> \t\tmemcpy(dst, src, slash - src + 1);\n> \tdst[slash - src + 1] = '\\0';\n> \treturn dst;\n\nAh, sure the dst==src case can be improved. But I'm not sure\nfactorizing writing NUL is worth the cost of re-computing where to put\nit when using mempcpy would avoid. Wouldn't the following be more\nadequate ?\n\n\tif (dst != src) {\n\t\tend = mempcpy(dst, src, slash - src + 1);\n\t\t*end = '\\0';\n\t} else\n\t\tdst[slash - src + 1] = '\\0';\n\treturn dst;\n\n> Style: '{' for functions goes in column 0.\n\n> Can get some depth reduction by dropping the else here (since in\n> the trivial case we have already returned).\n\nRight, thanks.\n\n> > +static void diffcore_bulk_moves(void)\n> > +{\n> > +\tint i;\n> > +\tfor (i = 0; i < rename_dst_nr; i++)\n> > +\t\tcheck_one_bulk_move(rename_dst[i].pair);\n> > +}\n> \n> Yay. :)\n\nIsn't that nice and pretty :)\n"},{"id":"154819","messageId":"20101030002600.GC21410@burratino","threadId":"25584","inReplyTo":"20101029211852.GB5695@home.lan","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-30T00:26:00Z","receivedAt":"2010-10-30T00:26:00Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> Hm, I fear too much granularity would become meaningless :)\n[...]\n> If the code needs to be easier to understand, I'd\n> rather add some more doc, than added commits that are basically\n> \"useless for bisect\".\n\nYes, the example list was probably a little overboard. Even so, the\nidea was to maintain bisectability by introducing a few tests at a\ntime. That way, the fallout of a subfeature can easily be found with\n\"git bisect\", among other benefits[1].\n\nI might try it out some time soon; don't worry about it if you don't\nlike the idea. :)\n\n> On Thu, Oct 28, 2010 at 08:45:40PM -0500, Jonathan Nieder wrote:\n\n>> 1. introduce DETECT_DIRECTORY_RENAMES flag and hidden UI for it.\n>\n> What do you mean by \"hidden UI\" ?\n\nPARSE_OPT_HIDDEN (i.e., a commandline option not tempting readers by\nlisting in -h).\n\n>> Is the debugging output infrequent enough to just use a function\n>> unconditionally?\n>\n> You mean, keep funccalls even with DEBUG_BULKMOVE is not set ? No,\n> there are too many traces for that.\n\nYep, that's what I meant. Alas.\n\nWill the debugging output still be useful once the code is known\nto work reliably? If not, I guess we can remove it at that point\n(avoiding the need to worry about patches that may introduce\n\n\tdebug_bulkmove(expression that does not even\n\t\t typecheck);\n\ndown the line).\n\n> Ah, sure the dst==src case can be improved. But I'm not sure\n> factorizing writing NUL is worth the cost of re-computing where to put\n> it when using mempcpy would avoid. Wouldn't the following be more\n> adequate ?\n> \n> \tif (dst != src) {\n> \t\tend = mempcpy(dst, src, slash - src + 1);\n> \t\t*end = '\\0';\n> \t} else\n> \t\tdst[slash - src + 1] = '\\0';\n> \treturn dst;\n\nI doubt the difference is measurable. But that looks fine (micronit:\nI suppose one should put the dst == src case first in that case).\n\nJonathan\n\n[1] The example that set me on this path to madness:\nhttp://thread.gmane.org/gmane.comp.version-control.git/151086/focus=158913\n"},{"id":"155225","messageId":"20101104215625.GB3167@home.lan","threadId":"25584","inReplyTo":"20101030002600.GC21410@burratino","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-11-04T21:56:25Z","receivedAt":"2010-11-04T21:56:25Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Fri, Oct 29, 2010 at 07:26:00PM -0500, Jonathan Nieder wrote:\n> Yann Dirson wrote:\n> \n> > Hm, I fear too much granularity would become meaningless :)\n> [...]\n> > If the code needs to be easier to understand, I'd\n> > rather add some more doc, than added commits that are basically\n> > \"useless for bisect\".\n> \n> Yes, the example list was probably a little overboard. Even so, the\n> idea was to maintain bisectability by introducing a few tests at a\n> time. That way, the fallout of a subfeature can easily be found with\n> \"git bisect\", among other benefits[1].\n\nI like the idea when successive commits get new functionality, but we\nhave to avoid introducing known-broken functionality and fixing them\nin later patches - and I fear the list as you described it was going\nthat latter way.\n\n> >> Is the debugging output infrequent enough to just use a function\n> >> unconditionally?\n> >\n> > You mean, keep funccalls even with DEBUG_BULKMOVE is not set ? No,\n> > there are too many traces for that.\n> \n> Yep, that's what I meant. Alas.\n\nWell, thinking twice, calls to empty function would be optimized out,\nso yes, we don't need cpp magic at all.\n\n-- \nYann\n"},{"id":"155226","messageId":"1288907957-9191-1-git-send-email-ydirson@altern.org","threadId":"25584","inReplyTo":"20101030002600.GC21410@burratino","subject":"[PATCH] Introduce bulk-move detection in diffcore.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T21:59:17Z","receivedAt":"2010-11-04T21:59:17Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"This feature tries to group together files moving from and to\nidentical directories - a common case being directory renames.\n\nThis only adds the detection logic. The output of raw diff is displayed\nas \"Rnnn a/ b/\", and unified diff does not display them at all. Output\nformats will be refined later in the series.\n\nIt is implemented as a new pass in diffcore-rename, occuring after the\nfile renames get detected, grouping those renames looking like a move\nof a full directory into some other place. It is activated by the new\n--detect-bulk-moves diffcore flag.\n\nPossible optimisations to this code include:\n* avoid use of i_am_not_single by using a separate list\n* use a more informative prefixcmp to avoid strcmp calls\n eg. in discard_if_outside()\n* optimize for bulk insertions (avoid useless successive memmove's)\n\nOther future developements to be made on top of this include:\n* detect bulk removals (well, that one is rather a subset than a layer above),\n and possibly bulk additions\n* detect bulk copies\n* detect inexact bulk-moves/copies (where some files were not moved, or were\n moved to a different place) - problem of computing a similarity score\n* display as such the special case of directory move/rename\n* application of such new diffs: issue a conflict, or just a warning ?\n* teach git-svn (and others ?) to make use of that flag\n* handle new conflict type \"bulk-move/add\"\n* detect \"directory splits\" as well\n* use inexact dir renames to bump score of below-threshold renames\n from/to same locations\n* support other types of bluk-grouping, like prefixes (see eg. kernel\n 5d1e859c), and maybe config-specified patterns\n* add yours here\n\nThis patch has been improved by the following contributions:\n- Jonathan Nieder: better implementation of copy_dirname()\n- Jonathan Nieder: portable implementation of memrchr() in another patch\n- Junio C Hamano: split individual renames hiding under control of another flag\n- Junio C Hamano: coding style issues\n- Junio C Hamano: better examples\n- Ævar Arnfjörð Bjarmason: Don't use C99 comments.\n- Jonathan Nieder: just too many other helpful suggestions to list them all\n\nThanks-to: Jonathan Nieder \nThanks-to: Junio C Hamano \nThanks-to: Ævar Arnfjörð Bjarmason \nSigned-off-by: Yann Dirson \n---\n\nThis version answers to most of Jonathan's remarks, except for the\ndebug_bulkmove() improvement. Should notably make valgrind more happy.\n\n Documentation/diff-options.txt | 4 +\n Documentation/gitdiffcore.txt | 12 ++\n diff-lib.c | 6 +-\n diff.c | 5 +\n diff.h | 3 +\n diffcore-rename.c | 375 ++++++++++++++++++++++++++++++++++++++--\n diffcore.h | 1 +\n tree-diff.c | 4 +-\n 8 files changed, 396 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex bfd0b57..887df4b 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -245,6 +245,10 @@ endif::git-log[]\n \tdelete/add pair to be a rename if more than 90% of the file\n \thasn't changed.\n \n+--detect-bulk-moves::\n+\tDetect bulk move of all files of a directory into a\n+\tdifferent one.\n+\n -C[]::\n --detect-copies[=]::\n \tDetect copies as well as renames. See also `--find-copies-harder`.\ndiff --git a/Documentation/gitdiffcore.txt b/Documentation/gitdiffcore.txt\nindex 6af29a4..93111ac 100644\n--- a/Documentation/gitdiffcore.txt\n+++ b/Documentation/gitdiffcore.txt\n@@ -175,6 +175,18 @@ the expense of making it slower. Without `\\--find-copies-harder`,\n 'git diff-{asterisk}' commands can detect copies only if the file that was\n copied happened to have been modified in the same changeset.\n \n+Bulk move of all files of a directory into a different one can get\n+detected using the `\\--detect-bulk-moves` option. This adds an\n+additional pass on top of the results of per-file rename detection.\n+They are reported with NULL SHA1 id, in addition to the file renames:\n+\n+------------------------------------------------\n+:040000 040000 0000000... 0000000... R100 foo/ bar/\n+:100644 100644 0123456... 1234567... R090 foo/file0 bar/file3\n+:100644 100644 2345678... 2345678... R100 foo/file1 bar/file1\n+:100644 100644 3456789... 3456789... R100 foo/file2 bar/file2\n+------------------------------------------------\n+\n \n diffcore-merge-broken: For Putting \"Complete Rewrites\" Back Together\n --------------------------------------------------------------------\ndiff --git a/diff-lib.c b/diff-lib.c\nindex 392ce2b..5ec3ddc 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -208,7 +208,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)\n \t\t\t\t\t\t ce_option, &dirty_submodule);\n \t\tif (!changed && !dirty_submodule) {\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, DETECT_BULK_MOVES))\n \t\t\t\tcontinue;\n \t\t}\n \t\toldmode = ce->ce_mode;\n@@ -338,7 +339,8 @@ static int show_modified(struct rev_info *revs,\n \n \toldmode = old->ce_mode;\n \tif (mode == oldmode && !hashcmp(sha1, old->sha1) && !dirty_submodule &&\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, DETECT_BULK_MOVES))\n \t\treturn 0;\n \n \tdiff_change(&revs->diffopt, oldmode, mode,\ndiff --git a/diff.c b/diff.c\nindex d1c6b91..2eba335 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3191,6 +3191,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, \"--detect-bulk-moves\")) {\n+\t\tDIFF_OPT_SET(options, DETECT_BULK_MOVES);\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 0083d92..1e2506c 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -78,6 +78,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)\n #define DIFF_OPT_IGNORE_UNTRACKED_IN_SUBMODULES (1 << 25)\n #define DIFF_OPT_IGNORE_DIRTY_SUBMODULES (1 << 26)\n #define DIFF_OPT_OVERRIDE_SUBMODULE_CONFIG (1 << 27)\n+#define DIFF_OPT_DETECT_BULK_MOVES (1 << 28)\n \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@@ -265,6 +266,8 @@ extern void diffcore_fix_diff_index(struct diff_options *);\n \" -C detect copies.\\n\" \\\n \" --find-copies-harder\\n\" \\\n \" try unchanged files as candidate for copy detection.\\n\" \\\n+\" --detect-bulk-moves\\n\" \\\n+\" detect moves of all files of a single directory.\\n\" \\\n \" -l limit rename attempts up to paths.\\n\" \\\n \" -O reorder diffs according to the .\\n\" \\\n \" -S find filepair whose only one side contains the string.\\n\" \\\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..52f3083 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,14 +6,34 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n \n+#define DEBUG_BULKMOVE 0\n+\n+#if DEBUG_BULKMOVE\n+#define debug_bulkmove(args) __debug_bulkmove args\n+void __debug_bulkmove(const char *fmt, ...)\n+{\n+\tva_list ap;\n+\tva_start(ap, fmt);\n+\tfprintf(stderr, \"[DBG] \");\n+\tvfprintf(stderr, fmt, ap);\n+\tva_end(ap);\n+}\n+#else\n+#define debug_bulkmove(args) do { /*nothing */ } while (0)\n+#endif\n+\n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n+\tunsigned i_am_not_single:1; /* does not look for a match, only here to be looked at */\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n \n+/*\n+ * Do a binary search of \"two\" in \"rename_dst\", inserting it if not found.\n+ */\n static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \t\t\t\t\t\t int insert_ok)\n {\n@@ -49,9 +69,36 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \trename_dst[first].two = alloc_filespec(two->path);\n \tfill_filespec(rename_dst[first].two, two->sha1, two->mode);\n \trename_dst[first].pair = NULL;\n+\trename_dst[first].i_am_not_single = 0;\n \treturn &(rename_dst[first]);\n }\n \n+/*\n+ * Do a binary search in \"rename_dst\" of any entry under \"dirname\".\n+ */\n+static struct diff_rename_dst *locate_rename_dst_dir(const char *dirname)\n+{\n+\tint first, last;\n+\tint prefixlength = strlen(dirname);\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(dirname, dst->two->path, prefixlength);\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@@ -386,8 +433,11 @@ static int find_exact_renames(void)\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, -1, i, rename_src[i].one);\n \n-\tfor (i = 0; i < rename_dst_nr; i++)\n+\tfor (i = 0; i < rename_dst_nr; i++) {\n+\t\tif (rename_dst[i].i_am_not_single)\n+\t\t\tcontinue;\n \t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n+\t}\n \n \t/* Find the renames */\n \ti = for_each_hash(&file_table, find_same_files);\n@@ -414,6 +464,275 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+static struct diff_bulk_rename {\n+\tstruct diff_filespec *one;\n+\tstruct diff_filespec *two;\n+\tint discarded;\n+} *bulkmove_candidates;\n+static int bulkmove_candidates_nr, bulkmove_candidates_alloc;\n+\n+/*\n+ * Do a binary search of \"one\" in \"bulkmove_candidate\", inserting it if not\n+ * found.\n+ * A good part was copy-pasted from locate_rename_dst().\n+ */\n+static struct diff_bulk_rename *locate_bulkmove_candidate(const char *one_path,\n+\t\t\t\t\t\t\t const char *two_path)\n+{\n+\tint first, last;\n+\n+\tfirst = 0;\n+\tlast = bulkmove_candidates_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct diff_bulk_rename *candidate = &(bulkmove_candidates[next]);\n+\t\t/* primary sort key on one_path, secondary on two_path */\n+\t\tint cmp = strcmp(one_path, candidate->one->path);\n+\t\tif (!cmp)\n+\t\t\tcmp = strcmp(two_path, candidate->two->path);\n+\t\tif (!cmp)\n+\t\t\treturn candidate;\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+\t/* insert to make it at \"first\" */\n+\tif (bulkmove_candidates_alloc <= bulkmove_candidates_nr) {\n+\t\tbulkmove_candidates_alloc = alloc_nr(bulkmove_candidates_alloc);\n+\t\tbulkmove_candidates = xrealloc(bulkmove_candidates,\n+\t\t\t\t bulkmove_candidates_alloc * sizeof(*bulkmove_candidates));\n+\t}\n+\tbulkmove_candidates_nr++;\n+\tif (first < bulkmove_candidates_nr)\n+\t\tmemmove(bulkmove_candidates + first + 1, bulkmove_candidates + first,\n+\t\t\t(bulkmove_candidates_nr - first - 1) * sizeof(*bulkmove_candidates));\n+\n+\tbulkmove_candidates[first].one = alloc_filespec(one_path);\n+\tfill_filespec(bulkmove_candidates[first].one, null_sha1, S_IFDIR);\n+\tbulkmove_candidates[first].two = alloc_filespec(two_path);\n+\tfill_filespec(bulkmove_candidates[first].two, null_sha1, S_IFDIR);\n+\tbulkmove_candidates[first].discarded = 0;\n+\treturn &(bulkmove_candidates[first]);\n+}\n+\n+/*\n+ * Copy dirname of src into dst, suitable to append a filename without\n+ * an additional \"/\".\n+ * Only handles relative paths since there is no absolute path in a git repo.\n+ * Writes \"\" when there is no \"/\" in src.\n+ * May overwrite more chars than really needed, if src ends with a \"/\".\n+ * Supports in-place modification of src by passing dst == src.\n+ */\n+static const char *copy_dirname(char *dst, const char *src)\n+{\n+\tsize_t len = strlen(src);\n+\tconst char *slash;\n+\tchar *end;\n+\n+\tif (len > 0 && src[len - 1] == '/')\n+\t\t/* Trailing slash. Ignore it. */\n+\t\tlen--;\n+\n+\tslash = memrchr(src, '/', len);\n+\tif (!slash) {\n+\t\t*dst = '\\0';\n+\t\treturn dst;\n+\t}\n+\n+\tif (dst == src)\n+\t\tdst[slash - src + 1] = '\\0';\n+\telse {\n+\t\tend = mempcpy(dst, src, slash - src + 1);\n+\t\t*end = '\\0';\n+\t}\n+\treturn dst;\n+}\n+\n+// FIXME: leaks like hell.\n+/* See if the fact that one_leftover exists under one_parent_path in\n+ * dst tree should disqualify one_parent_path from bulkmove eligibility.\n+ * Return 1 if it disqualifies, 0 if it is OK.\n+ */\n+static int dispatched_to_different_dirs(const char *one_parent_path)\n+{\n+\t/* this might be a dir split, or files added\n+\t * after the bulk move, or just an isolated\n+\t * rename */\n+\tint two_idx, j, onep_len, maybe_dir_rename;\n+\tstruct diff_rename_dst *one_leftover =\n+\t\tone_leftover = locate_rename_dst_dir(one_parent_path);\n+\n+\tif (!one_leftover)\n+\t\treturn 0;\n+\n+\t/* try to see if it is a file added after the bulk move */\n+\ttwo_idx = one_leftover - rename_dst;\n+\tonep_len = strlen(one_parent_path);\n+\tmaybe_dir_rename = 1;\n+\n+\t/* check no leftover file was already here before */\n+\tfor (j = two_idx; j < rename_dst_nr; j++) {\n+\t\tif (strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))\n+\t\t\tbreak; /* exhausted directory in this direction */\n+\t\tdebug_bulkmove((\"leftover file %s in %s\\n\",\n+\t\t\t\trename_dst[j].two->path, one_parent_path));\n+\t\tif (rename_dst[j].i_am_not_single || /* those were already here */\n+\t\t (rename_dst[j].pair &&\n+\t\t !strncmp(rename_dst[j].pair->one->path,\n+\t\t\t one_parent_path, onep_len) && /* renamed from here */\n+\t\t strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))) { /* not to a subdir */\n+\t\t\tmaybe_dir_rename = 0;\n+\t\t\tdebug_bulkmove((\"... tells not a bulk move\\n\"));\n+\t\t\tbreak;\n+\t\t}\n+\t\tdebug_bulkmove((\"... not believed to prevent bulk move\\n\"));\n+\t}\n+\tif (!maybe_dir_rename)\n+\t\treturn 1;\n+\t/* try the other direction (dup code) */\n+\tfor (j = two_idx-1; j >= 0; j--) {\n+\t\tif (strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))\n+\t\t\tbreak; /* exhausted directory in this direction */\n+\t\tdebug_bulkmove((\"leftover file %s in '%s'\\n\",\n+\t\t\t\trename_dst[j].two->path, one_parent_path));\n+\t\tif (rename_dst[j].i_am_not_single || /* those were already here */\n+\t\t (rename_dst[j].pair &&\n+\t\t !strncmp(rename_dst[j].pair->one->path,\n+\t\t\t one_parent_path, onep_len) && /* renamed from here */\n+\t\t strncmp(rename_dst[j].two->path,\n+\t\t\t one_parent_path, onep_len))) { /* not to a subdir */\n+\t\t\tmaybe_dir_rename = 0;\n+\t\t\tdebug_bulkmove((\"... tells not a bulk move\\n\"));\n+\t\t\tbreak;\n+\t\t}\n+\t\tdebug_bulkmove((\"... not believed to prevent bulk move\\n\"));\n+\t}\n+\tif (!maybe_dir_rename)\n+\t\treturn 1;\n+\n+\t/* Here we are in the case where a directory\n+\t * content was completely moved, but files\n+\t * were added to it afterwards. Proceed as\n+\t * for a simple bulk move. */\n+\treturn 0;\n+}\n+\n+/*\n+ * Assumes candidate->one is a subdir of seen->one, mark 'seen' as\n+ * discarded if candidate->two is outside seen->two. Also mark\n+ * 'candidate' itself as discarded if the conflict implies so.\n+ *\n+ * Return 1 if 'seen' was discarded\n+ */\n+static int discard_if_outside(struct diff_bulk_rename *candidate,\n+\t\t\t struct diff_bulk_rename *seen)\n+{\n+\tif (!prefixcmp(candidate->two->path, seen->two->path)) {\n+\t\tdebug_bulkmove((\" 'dstpair' conforts 'seen'\\n\"));\n+\t\treturn 0;\n+\t}\n+\n+\tdebug_bulkmove((\"discarding %s -> %s from bulk moves (split into %s and %s)\\n\",\n+\t\t\tseen->one->path, seen->two->path,\n+\t\t\tcandidate->two->path, seen->two->path));\n+\tseen->discarded = 1;\n+\t/* Need to discard dstpair as well, unless moving from\n+\t * a strict subdir of seen->one or to a strict subdir\n+\t * of seen->two */\n+\tif (!strcmp(seen->one->path, candidate->one->path) &&\n+\t prefixcmp(seen->two->path, candidate->two->path)) {\n+\t\tdebug_bulkmove((\"... and not adding self\\n\"));\n+\t\tcandidate->discarded = 1;\n+\t}\n+\treturn 1;\n+}\n+\n+/*\n+ * Check if the rename specified by \"dstpair\" could cause a\n+ * bulk move to be detected, record it in bulkmove_candidates if yes.\n+ */\n+static void check_one_bulk_move(struct diff_filepair *dstpair)\n+{\n+\tchar one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];\n+\n+\t/* genuine new files (or believed to be so) */\n+\tif (!dstpair)\n+\t\treturn;\n+\t/* dummy renames used by copy detection */\n+\tif (!strcmp(dstpair->one->path, dstpair->two->path))\n+\t\treturn;\n+\n+\tcopy_dirname(one_parent_path, dstpair->one->path);\n+\tcopy_dirname(two_parent_path, dstpair->two->path);\n+\n+\t/* simple rename with no directory change */\n+\tif (!strcmp(one_parent_path, two_parent_path))\n+\t\treturn;\n+\n+\tdebug_bulkmove((\"[] %s -> %s ?\\n\", dstpair->one->path, dstpair->two->path));\n+\n+\t/* loop up one_parent_path over successive parents */\n+\t// FIXME: also loop over two_parent_path prefixes\n+\tdo {\n+\t\tstruct diff_bulk_rename *seen;\n+\t\tint old_nr = bulkmove_candidates_nr;\n+\t\tstruct diff_bulk_rename *candidate =\n+\t\t\tlocate_bulkmove_candidate(one_parent_path, two_parent_path);\n+\t\tdebug_bulkmove((\"[[]] %s ...\\n\", one_parent_path));\n+\t\tif (old_nr == bulkmove_candidates_nr) {\n+\t\t\tdebug_bulkmove((\" already seen\\n\"));\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* After this commit, are there any files still under one_parent_path ?\n+\t\t * Any file left would disqualifies this dir for bulk move.\n+\t\t */\n+\t\tif (dispatched_to_different_dirs(one_parent_path)) {\n+\t\t\t// FIXME: check overlap with discard_if_outside()\n+\t\t\tcandidate->discarded = 1;\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* walk up for one_parent_path prefixes */\n+\t\tfor (seen = candidate-1; (seen >= bulkmove_candidates) &&\n+\t\t\t !prefixcmp(one_parent_path, seen->one->path); seen--) {\n+\t\t\tdebug_bulkmove((\" ? %s -> %s\\n\", seen->one->path, seen->two->path));\n+\t\t\t/* subdir of \"seen\" dest dir ? */\n+\t\t\tif (discard_if_outside(candidate, seen))\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\t/* look down for other moves from one_parent_path */\n+\t\tseen = candidate + 1;\n+\t\tif (seen != bulkmove_candidates + bulkmove_candidates_nr &&\n+\t\t !strcmp(one_parent_path, seen->one->path)) {\n+\t\t\tdebug_bulkmove((\" ? %s -> %s (2)\\n\", seen->one->path, seen->two->path));\n+\t\t\t/* subdir of \"seen\" dest dir ? */\n+\t\t\tif (discard_if_outside(candidate, seen))\n+\t\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/* next parent if any */\n+\t\tcopy_dirname(one_parent_path, one_parent_path);\n+\t} while (*one_parent_path);\n+}\n+\n+/*\n+ * Take all file renames recorded so far and check if they could cause\n+ * a bulk move to be detected.\n+ */\n+static void diffcore_bulk_moves(void)\n+{\n+\tint i;\n+\tfor (i = 0; i < rename_dst_nr; i++)\n+\t\tcheck_one_bulk_move(rename_dst[i].pair);\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -424,6 +743,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count;\n \tint num_create, num_src, dst_cnt;\n+\tstruct diff_bulk_rename *candidate;\n \n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n@@ -438,8 +758,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tcontinue; /* not interested */\n \t\t\telse\n \t\t\t\tlocate_rename_dst(p->two, 1);\n-\t\t}\n-\t\telse if (!DIFF_FILE_VALID(p->two)) {\n+\t\t} else if (!DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n \t\t\t * If the source is a broken \"delete\", and\n \t\t\t * they did not really want to get broken,\n@@ -450,14 +769,23 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tif (p->broken_pair && !p->score)\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\t} else {\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, DETECT_BULK_MOVES)) {\n+\t\t\t\t/* similarly, bulk move detection needs to\n+\t\t\t\t * see all files from second tree, but we don't\n+\t\t\t\t * want them to be matched against single sources.\n+\t\t\t\t */\n+\t\t\t\t// FIXME: check interaction with --find-copies-harder\n+\t\t\t\tlocate_rename_dst(p->two, 1)->i_am_not_single = 1;\n+\t\t\t}\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n@@ -509,6 +837,8 @@ void diffcore_rename(struct diff_options *options)\n \n \t\tif (rename_dst[i].pair)\n \t\t\tcontinue; /* dealt with exact match already. */\n+\t\tif (rename_dst[i].i_am_not_single)\n+\t\t\tcontinue; /* not looking for a match. */\n \n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n@@ -569,7 +899,30 @@ 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, DETECT_BULK_MOVES))\n+\t\tdiffcore_bulk_moves();\n+\n \tDIFF_QUEUE_CLEAR(&outq);\n+\n+\t/* Now turn non-discarded bulkmove_candidates into real renames */\n+\tfor (candidate = bulkmove_candidates;\n+\t candidate < bulkmove_candidates + bulkmove_candidates_nr; candidate++) {\n+\t\tstruct diff_filepair* pair;\n+\t\tif (candidate->discarded)\n+\t\t\tcontinue;\n+\t\t/* visualize toplevel dir if needed */\n+\t\tif (!*candidate->one->path)\n+\t\t\tcandidate->one->path = \"./\";\n+\t\tif (!*candidate->two->path)\n+\t\t\tcandidate->two->path = \"./\";\n+\t\tpair = diff_queue(&outq, candidate->one, candidate->two);\n+\t\tpair->score = MAX_SCORE;\n+\t\tpair->renamed_pair = 1;\n+\t\tpair->is_bulkmove = 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;\ndiff --git a/diffcore.h b/diffcore.h\nindex b8f1fde..6dab95b 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -69,6 +69,7 @@ struct diff_filepair {\n \tunsigned broken_pair : 1;\n \tunsigned renamed_pair : 1;\n \tunsigned is_unmerged : 1;\n+\tunsigned is_bulkmove : 1;\n };\n #define DIFF_PAIR_UNMERGED(p) ((p)->is_unmerged)\n \ndiff --git a/tree-diff.c b/tree-diff.c\nindex 12c9a88..89cedd4 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, DETECT_BULK_MOVES) &&\n+\t !hashcmp(sha1, sha2) && mode1 == mode2)\n \t\treturn 0;\n \n \t/*\n-- \n1.7.2.3\n"},{"id":"156539","messageId":"AANLkTi=Ekoe+RSrRFj63S___Vsa5kTsDKJVPamFsz0c2@mail.gmail.com","threadId":"25584","inReplyTo":"1288303712-14662-2-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2010-11-25T10:08:07Z","receivedAt":"2010-11-25T10:08:07Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Fri, Oct 29, 2010 at 00:08, Yann Dirson wrote:\n\n> +       slash = memrchr(src, '/', len);\n\nI can't compile pu now on Solaris due to this bit. Are you planning on\npicking up the patch / configure / Makefile detection discussed in the\n\"[PATCH] compat: add memrchr()\" thread? Just wondering what the\nprogress was on that.\n\nThanks.\n"},{"id":"156551","messageId":"20101125150218.GA16049@burratino","threadId":"25584","inReplyTo":"AANLkTi=Ekoe+RSrRFj63S___Vsa5kTsDKJVPamFsz0c2@mail.gmail.com","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-25T15:02:18Z","receivedAt":"2010-11-25T15:02:18Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ævar Arnfjörð Bjarmason wrote:\n> On Fri, Oct 29, 2010 at 00:08, Yann Dirson wrote:\n\n>> +       slash = memrchr(src, '/', len);\n>\n> I can't compile pu now on Solaris due to this bit. Are you planning on\n> picking up the patch / configure / Makefile detection discussed in the\n> \"[PATCH] compat: add memrchr()\" thread? Just wondering what the\n> progress was on that.\n\nBTW, remember that the configure / Makefile detection is only an extra\nnicety. [1] teaches git to rely on the system memrchr on glibc\nsystems only; on other systems (unless they define memrchr as a macro,\nwhich would be a strange thing to do), gitmemrchr is used.\n\nUpshot: it should be safe to use [1] without the configure / Makefile\nsupport. Later, an interested person can write a patch for improved\nmemrchr[2] on *BSD and Plan 9.\n\nJonathan\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/159081/focus=159121\n[2] Lower code size. Maybe faster.\n"},{"id":"156563","messageId":"AANLkTimGOkv7db2YW_+-V_oJEheuwBiUW-3fFpHBOt4v@mail.gmail.com","threadId":"25584","inReplyTo":"20101125150218.GA16049@burratino","subject":"Re: [PATCH v8 1/5] Introduce bulk-move detection in diffcore.","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2010-11-25T17:19:36Z","receivedAt":"2010-11-25T17:19:36Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, Nov 25, 2010 at 16:02, Jonathan Nieder wrote:\n> Ævar Arnfjörð Bjarmason wrote:\n>> On Fri, Oct 29, 2010 at 00:08, Yann Dirson wrote:\n>\n>>> +       slash = memrchr(src, '/', len);\n>>\n>> I can't compile pu now on Solaris due to this bit. Are you planning on\n>> picking up the patch / configure / Makefile detection discussed in the\n>> \"[PATCH] compat: add memrchr()\" thread? Just wondering what the\n>> progress was on that.\n>\n> BTW, remember that the configure / Makefile detection is only an extra\n> nicety.  [1] teaches git to rely on the system memrchr on glibc\n> systems only; on other systems (unless they define memrchr as a macro,\n> which would be a strange thing to do), gitmemrchr is used.\n>\n> Upshot: it should be safe to use [1] without the configure / Makefile\n> support.  Later, an interested person can write a patch for improved\n> memrchr[2] on *BSD and Plan 9.\n\nSure. It's just a bit of a hack since we already have a standard-ish\nway of doing this. Which is to optionally have configure.ac support,\nthen add platform-specific stuff to the Makefile & drop something in\ncompat/memrchr.c.\n\nDoing it that way and actually detecting it means we use e.g. the\nnative memrchr on FreeBSD. I just don't see a reason to do it like the\n[1] patch when it's just as easy to do it the \"proper way\", where it's\nmore extendable.\n\nAnyway, it's a very minor issue. I'll probably do a patch for this\nseries like I did for that other thing that needed autoconf detection\nrecently. Thanks everyone.\n"}]}