{"thread":{"id":"26223","subject":"[PATCH 3/3] diffcore-rename: fall back to -C when -C -C busts the rename limit","startedAt":"2011-01-06T21:50:03Z","lastAt":"2011-01-06T22:28:36Z","messageCount":5,"participants":["Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"159075","messageId":"1294350606-19530-1-git-send-email-gitster@pobox.com","threadId":"26223","inReplyTo":"7vhbdlahnp.fsf@alter.siamese.dyndns.org","subject":"[PATCH 0/3] Falling back \"diff -C -C\" to \"diff -C\" more gracefully","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-01-06T21:50:03Z","receivedAt":"2011-01-06T21:50:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In a project with many paths, \"diff -C -C\" may have too many rename source\ncandidates (as it tries to use all existing paths) but the rename source\ncandidates \"diff -C\" would use may still fit under the rename detection\nlimit.  Currently, we punt and disable the inexact rename detection\naltogether even in such a case.\n\nThis weatherballoon series illustrates how diffcore-rename can be tweaked\nto allow \"-C -C\" to fall back to \"-C\".  Somebody should write a test, but\nnot today ;-).\n\nJunio C Hamano (3):\n  diffcore-rename: refactor \"too many candidates\" logic\n  diffcore-rename: record filepair for rename src\n  diffcore-rename: fall back to -C when -C -C busts the rename limit\n\n diffcore-rename.c |   97 ++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 71 insertions(+), 26 deletions(-)\n\n-- \n1.7.4.rc1.214.g2a4f9\n"},{"id":"159074","messageId":"1294350606-19530-2-git-send-email-gitster@pobox.com","threadId":"26223","inReplyTo":"1294350606-19530-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] diffcore-rename: refactor \"too many candidates\" logic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-01-06T21:50:04Z","receivedAt":"2011-01-06T21:50:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Move the logic to a separate function, to be enhanced by later patches in\nthe series.\n\nWhile at it, swap the condition used in the if statement from \"if it is\ntoo big then do this\" to \"if it would fit then do this\".\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-rename.c |   39 +++++++++++++++++++++++++--------------\n 1 files changed, 25 insertions(+), 14 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..6ab050d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -414,11 +414,34 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+static int too_many_rename_candidates(int num_create,\n+\t\t\t\t      struct diff_options *options)\n+{\n+\tint rename_limit = options->rename_limit;\n+\tint num_src = rename_src_nr;\n+\n+\t/*\n+\t * This basically does a test for the rename matrix not\n+\t * growing larger than a \"rename_limit\" square matrix, ie:\n+\t *\n+\t *    num_create * num_src > rename_limit * rename_limit\n+\t *\n+\t * but handles the potential overflow case specially (and we\n+\t * assume at least 32-bit integers)\n+\t */\n+\tif (rename_limit <= 0 || rename_limit > 32767)\n+\t\trename_limit = 32767;\n+\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n+\t    (num_create * num_src <= rename_limit * rename_limit))\n+\t\treturn 0;\n+\n+\treturn 1;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n \tint minimum_score = options->rename_score;\n-\tint rename_limit = options->rename_limit;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n@@ -484,19 +507,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (!num_create)\n \t\tgoto cleanup;\n \n-\t/*\n-\t * This basically does a test for the rename matrix not\n-\t * growing larger than a \"rename_limit\" square matrix, ie:\n-\t *\n-\t *    num_create * num_src > rename_limit * rename_limit\n-\t *\n-\t * but handles the potential overflow case specially (and we\n-\t * assume at least 32-bit integers)\n-\t */\n-\tif (rename_limit <= 0 || rename_limit > 32767)\n-\t\trename_limit = 32767;\n-\tif ((num_create > rename_limit && num_src > rename_limit) ||\n-\t    (num_create * num_src > rename_limit * rename_limit)) {\n+\tif (too_many_rename_candidates(num_create, options)) {\n \t\tif (options->warn_on_too_large_rename)\n \t\t\twarning(\"too many files (created: %d deleted: %d), skipping inexact rename detection\", num_create, num_src);\n \t\tgoto cleanup;\n-- \n1.7.4.rc1.214.g2a4f9\n"},{"id":"159076","messageId":"1294350606-19530-3-git-send-email-gitster@pobox.com","threadId":"26223","inReplyTo":"1294350606-19530-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] diffcore-rename: record filepair for rename src","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-01-06T21:50:05Z","receivedAt":"2011-01-06T21:50:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This will allow us to later skip unmodified entries added due to \"-C -C\".\nWe might also want to do something similar to rename_dst side, but that\nwould only be for the sake of symmetry and not necessary for this series.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-rename.c |   23 ++++++++++++-----------\n 1 files changed, 12 insertions(+), 11 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6ab050d..9ce81b6 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -54,22 +54,23 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \n /* Table of rename/copy src files */\n static struct diff_rename_src {\n-\tstruct diff_filespec *one;\n+\tstruct diff_filepair *p;\n \tunsigned short score; /* to remember the break score */\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n-static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n-\t\t\t\t\t\t   unsigned short score)\n+static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n {\n \tint first, last;\n+\tstruct diff_filespec *one = p->one;\n+\tunsigned short score = p->score;\n \n \tfirst = 0;\n \tlast = rename_src_nr;\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n \t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->one->path);\n+\t\tint cmp = strcmp(one->path, src->p->one->path);\n \t\tif (!cmp)\n \t\t\treturn src;\n \t\tif (cmp < 0) {\n@@ -89,7 +90,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n \tif (first < rename_src_nr)\n \t\tmemmove(rename_src + first + 1, rename_src + first,\n \t\t\t(rename_src_nr - first - 1) * sizeof(*rename_src));\n-\trename_src[first].one = one;\n+\trename_src[first].p = p;\n \trename_src[first].score = score;\n \treturn &(rename_src[first]);\n }\n@@ -204,7 +205,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \tif (rename_dst[dst_index].pair)\n \t\tdie(\"internal error: dst already matched.\");\n \n-\tsrc = rename_src[src_index].one;\n+\tsrc = rename_src[src_index].p->one;\n \tsrc->rename_used++;\n \tsrc->count++;\n \n@@ -384,7 +385,7 @@ static int find_exact_renames(void)\n \n \tinit_hash(&file_table);\n \tfor (i = 0; i < rename_src_nr; i++)\n-\t\tinsert_file_table(&file_table, -1, i, rename_src[i].one);\n+\t\tinsert_file_table(&file_table, -1, i, rename_src[i].p->one);\n \n \tfor (i = 0; i < rename_dst_nr; i++)\n \t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n@@ -472,7 +473,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\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\tregister_rename_src(p);\n \t\t}\n \t\telse if (detect_rename == DIFF_DETECT_COPY) {\n \t\t\t/*\n@@ -480,7 +481,7 @@ void diffcore_rename(struct diff_options *options)\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\tregister_rename_src(p);\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n@@ -526,7 +527,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tm[j].dst = -1;\n \n \t\tfor (j = 0; j < rename_src_nr; j++) {\n-\t\t\tstruct diff_filespec *one = rename_src[j].one;\n+\t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \t\t\tthis_src.score = estimate_similarity(one, two,\n \t\t\t\t\t\t\t     minimum_score);\n@@ -556,7 +557,7 @@ void diffcore_rename(struct diff_options *options)\n \t\tdst = &rename_dst[mx[i].dst];\n \t\tif (dst->pair)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (rename_src[mx[i].src].one->rename_used)\n+\t\tif (rename_src[mx[i].src].p->one->rename_used)\n \t\t\tcontinue;\n \t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n \t\trename_count++;\n-- \n1.7.4.rc1.214.g2a4f9\n"},{"id":"159073","messageId":"1294350606-19530-4-git-send-email-gitster@pobox.com","threadId":"26223","inReplyTo":"1294350606-19530-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] diffcore-rename: fall back to -C when -C -C busts the rename limit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-01-06T21:50:06Z","receivedAt":"2011-01-06T21:50:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When there are too many paths in the project, the number of rename source\ncandidates \"git diff -C -C\" finds will exceed the rename detection limit,\nand no inexact rename detection is performed.  We however could fall back\nto \"git diff -C\" if the number of paths modified are sufficiently small.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-rename.c |   37 +++++++++++++++++++++++++++++++++++--\n 1 files changed, 35 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 9ce81b6..4851af3 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -415,11 +415,18 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+/*\n+ * Returns:\n+ * 0 if we are under the limit;\n+ * 1 if we need to disable inexact rename detection;\n+ * 2 if we would be under the limit if we were given -C instead of -C -C.\n+ */\n static int too_many_rename_candidates(int num_create,\n \t\t\t\t      struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n \tint num_src = rename_src_nr;\n+\tint i;\n \n \t/*\n \t * This basically does a test for the rename matrix not\n@@ -436,6 +443,19 @@ static int too_many_rename_candidates(int num_create,\n \t    (num_create * num_src <= rename_limit * rename_limit))\n \t\treturn 0;\n \n+\t/* Are we running under -C -C? */\n+\tif (!DIFF_OPT_TST(options, FIND_COPIES_HARDER))\n+\t\treturn 1;\n+\n+\t/* Would we bust the limit if we were running under -C? */\n+\tfor (num_src = i = 0; i < rename_src_nr; i++) {\n+\t\tif (diff_unmodified_pair(rename_src[i].p))\n+\t\t\tcontinue;\n+\t\tnum_src++;\n+\t}\n+\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n+\t    (num_create * num_src <= rename_limit * rename_limit))\n+\t\treturn 2;\n \treturn 1;\n }\n \n@@ -446,7 +466,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n-\tint i, j, rename_count;\n+\tint i, j, rename_count, skip_unmodified = 0;\n \tint num_create, num_src, dst_cnt;\n \n \tif (!minimum_score)\n@@ -508,10 +528,18 @@ void diffcore_rename(struct diff_options *options)\n \tif (!num_create)\n \t\tgoto cleanup;\n \n-\tif (too_many_rename_candidates(num_create, options)) {\n+\tswitch (too_many_rename_candidates(num_create, options)) {\n+\tcase 1:\n \t\tif (options->warn_on_too_large_rename)\n \t\t\twarning(\"too many files (created: %d deleted: %d), skipping inexact rename detection\", num_create, num_src);\n \t\tgoto cleanup;\n+\tcase 2:\n+\t\tif (options->warn_on_too_large_rename)\n+\t\t\twarning(\"too many files, falling back to -C\");\n+\t\tskip_unmodified = 1;\n+\t\tbreak;\n+\tdefault:\n+\t\tbreak;\n \t}\n \n \tmx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));\n@@ -529,6 +557,11 @@ void diffcore_rename(struct diff_options *options)\n \t\tfor (j = 0; j < rename_src_nr; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n+\n+\t\t\tif (skip_unmodified &&\n+\t\t\t    diff_unmodified_pair(rename_src[j].p))\n+\t\t\t\tcontinue;\n+\n \t\t\tthis_src.score = estimate_similarity(one, two,\n \t\t\t\t\t\t\t     minimum_score);\n \t\t\tthis_src.name_score = basename_same(one, two);\n-- \n1.7.4.rc1.214.g2a4f9\n"},{"id":"159079","messageId":"20110106222836.GA13727@sigill.intra.peff.net","threadId":"26223","inReplyTo":"1294350606-19530-1-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 0/3] Falling back \"diff -C -C\" to \"diff -C\" more gracefully","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-01-06T22:28:36Z","receivedAt":"2011-01-06T22:28:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 06, 2011 at 01:50:03PM -0800, Junio C Hamano wrote:\n\n> Junio C Hamano (3):\n>   diffcore-rename: refactor \"too many candidates\" logic\n>   diffcore-rename: record filepair for rename src\n>   diffcore-rename: fall back to -C when -C -C busts the rename limit\n\nI read through the series, and it looks good to me. I didn't do any\ntesting, though. :)\n\n-Peff\n"}]}