{"thread":{"id":"26556","subject":"[PATCH 1/3] for_each_hash: allow passing a 'void *data' pointer to callback","startedAt":"2011-02-19T04:25:11Z","lastAt":"2011-02-19T04:30:02Z","messageCount":3,"participants":["Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"161582","messageId":"alpine.LFD.2.02.1102182023120.4165@i5.linux-foundation.org","threadId":"26556","inReplyTo":null,"subject":"[PATCH 1/3] for_each_hash: allow passing a 'void *data' pointer to callback","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-02-19T04:25:11Z","receivedAt":"2011-02-19T04:25:11Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Fri, 18 Feb 2011 19:55:19 -0800\n\nFor the find_exact_renames() function, this allows us to pass the\ndiff_options structure pointer to the low-level routines.  We will use\nthat to distinguish between the \"rename\" and \"copy\" cases.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nSo I changed the \"int flag\" to a \"void *data\". That should be more \nflexible, with the slight downside that there are now two \"void *\" \npointers, and the callback routine obviously has to know that the first \none is the one from the hash chain, and the other one is the \"data\" \nhelper.\n\nThis does NOT change any semantics. It is purely setup code that passes \nthe new pointer around, but doesn't actually use it.\n\n builtin/describe.c |    4 ++--\n diffcore-rename.c  |   14 ++++++++------\n hash.c             |    4 ++--\n hash.h             |    2 +-\n 4 files changed, 13 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 342129f..3ba26dc 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -63,7 +63,7 @@ static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n \treturn n;\n }\n \n-static int set_util(void *chain)\n+static int set_util(void *chain, void *data)\n {\n \tstruct commit_name *n;\n \tfor (n = chain; n; n = n->next) {\n@@ -289,7 +289,7 @@ static void describe(const char *arg, int last_one)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n \tif (!have_util) {\n-\t\tfor_each_hash(&names, set_util);\n+\t\tfor_each_hash(&names, set_util, NULL);\n \t\thave_util = 1;\n \t}\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..e5e88fe 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -247,7 +247,8 @@ struct file_similarity {\n };\n \n static int find_identical_files(struct file_similarity *src,\n-\t\t\t\tstruct file_similarity *dst)\n+\t\t\t\tstruct file_similarity *dst,\n+\t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n \n@@ -306,11 +307,12 @@ static void free_similarity_list(struct file_similarity *p)\n \t}\n }\n \n-static int find_same_files(void *ptr)\n+static int find_same_files(void *ptr, void *data)\n {\n \tint ret;\n \tstruct file_similarity *p = ptr;\n \tstruct file_similarity *src = NULL, *dst = NULL;\n+\tstruct diff_options *options = data;\n \n \t/* Split the hash list up into sources and destinations */\n \tdo {\n@@ -329,7 +331,7 @@ static int find_same_files(void *ptr)\n \t * If we have both sources *and* destinations, see if\n \t * we can match them up\n \t */\n-\tret = (src && dst) ? find_identical_files(src, dst) : 0;\n+\tret = (src && dst) ? find_identical_files(src, dst, options) : 0;\n \n \t/* Free the hashes and return the number of renames found */\n \tfree_similarity_list(src);\n@@ -377,7 +379,7 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index,\n  * and then during the second round we try to match\n  * cache-dirty entries as well.\n  */\n-static int find_exact_renames(void)\n+static int find_exact_renames(struct diff_options *options)\n {\n \tint i;\n \tstruct hash_table file_table;\n@@ -390,7 +392,7 @@ static int find_exact_renames(void)\n \t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n \n \t/* Find the renames */\n-\ti = for_each_hash(&file_table, find_same_files);\n+\ti = for_each_hash(&file_table, find_same_files, options);\n \n \t/* .. and free the hash data structure */\n \tfree_hash(&file_table);\n@@ -467,7 +469,7 @@ void diffcore_rename(struct diff_options *options)\n \t * We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n-\trename_count = find_exact_renames();\n+\trename_count = find_exact_renames(options);\n \n \t/* Did we only want exact renames? */\n \tif (minimum_score == MAX_SCORE)\ndiff --git a/hash.c b/hash.c\nindex 1cd4c9d..749ecfe 100644\n--- a/hash.c\n+++ b/hash.c\n@@ -81,7 +81,7 @@ void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n \treturn insert_hash_entry(hash, ptr, table);\n }\n \n-int for_each_hash(const struct hash_table *table, int (*fn)(void *))\n+int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)\n {\n \tint sum = 0;\n \tunsigned int i;\n@@ -92,7 +92,7 @@ int for_each_hash(const struct hash_table *table, int (*fn)(void *))\n \t\tvoid *ptr = array->ptr;\n \t\tarray++;\n \t\tif (ptr) {\n-\t\t\tint val = fn(ptr);\n+\t\t\tint val = fn(ptr, data);\n \t\t\tif (val < 0)\n \t\t\t\treturn val;\n \t\t\tsum += val;\ndiff --git a/hash.h b/hash.h\nindex 69e33a4..b875ce6 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -30,7 +30,7 @@ struct hash_table {\n \n extern void *lookup_hash(unsigned int hash, const struct hash_table *table);\n extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table);\n-extern int for_each_hash(const struct hash_table *table, int (*fn)(void *));\n+extern int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data);\n extern void free_hash(struct hash_table *table);\n \n static inline void init_hash(struct hash_table *table)\n-- \n1.7.4.1.51.g2bf8a\n"},{"id":"161583","messageId":"alpine.LFD.2.02.1102182025270.4165@i5.linux-foundation.org","threadId":"26556","inReplyTo":"alpine.LFD.2.02.1102182023120.4165@i5.linux-foundation.org","subject":"[PATCH 2/3] diffcore-rename: propler honor the difference between -M and -C","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-02-19T04:28:33Z","receivedAt":"2011-02-19T04:28:33Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Fri, 18 Feb 2011 20:10:32 -0800\n\nWe would allow rename detection to do copy detection even when asked\npurely for renames.  That confuses users, but more importantly it can\nterminally confuse the recursive merge rename logic.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\nHey, it actually deletes one more line than it adds, because I wanted to \navoid having to indent that big for-loop that was largely duplicated, and \ndecided to instead de-duplicate it and make it a helper function that is \ncalled a second time for the \"find copies\" case.\n\nAnd it now uses the new \"options\" pointer in find_identical_files() to \ndecide if it wants to find copies or just renames.\n\nSo this is the patch that actually changes semantics, and makes \"-M\" means \n\"only renames\" and \"-C\" mean \"find copies too\". Like it was always \nintended, but I don't know if we've ever implemented it that way. The \n\"we'll find copies even with -M\" is certainly not some new regression.\n\n diffcore-rename.c              |   53 +++++++++++++++++++--------------------\n t/t4003-diff-rename-1.sh       |    2 +-\n t/t4004-diff-rename-symlink.sh |    2 +-\n t/t4005-diff-rename-2.sh       |    2 +-\n t/t4008-diff-break-rewrite.sh  |    4 +-\n t/t4009-diff-rename-4.sh       |    2 +-\n 6 files changed, 32 insertions(+), 33 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e5e88fe..b9b039d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -278,6 +278,8 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\t}\n \t\t\t/* Give higher scores to sources that haven't been used already */\n \t\t\tscore = !source->rename_used;\n+\t\t\tif (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)\n+\t\t\t\tcontinue;\n \t\t\tscore += basename_same(source, target);\n \t\t\tif (score > best_score) {\n \t\t\t\tbest = p;\n@@ -416,6 +418,27 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n \t\tm[worst] = *o;\n }\n \n+static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, int copies)\n+{\n+\tint count = 0, i;\n+\n+\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n+\t\tstruct diff_rename_dst *dst;\n+\n+\t\tif ((mx[i].dst < 0) ||\n+\t\t    (mx[i].score < minimum_score))\n+\t\t\tbreak; /* there is no more usable pair. */\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 (!copies && rename_src[mx[i].src].one->rename_used)\n+\t\t\tcontinue;\n+\t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n+\t\tcount++;\n+\t}\n+\treturn count;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -538,33 +561,9 @@ void diffcore_rename(struct diff_options *options)\n \t/* cost matrix sorted by most to least similar pair */\n \tqsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);\n \n-\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n-\t\tstruct diff_rename_dst *dst;\n-\n-\t\tif ((mx[i].dst < 0) ||\n-\t\t    (mx[i].score < minimum_score))\n-\t\t\tbreak; /* there is no more usable pair. */\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\t\tcontinue;\n-\t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n-\t\trename_count++;\n-\t}\n-\n-\tfor (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) {\n-\t\tstruct diff_rename_dst *dst;\n-\n-\t\tif ((mx[i].dst < 0) ||\n-\t\t    (mx[i].score < minimum_score))\n-\t\t\tbreak; /* there is no more usable pair. */\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\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n-\t\trename_count++;\n-\t}\n+\trename_count += find_renames(mx, dst_cnt, minimum_score, 0);\n+\tif (detect_rename == DIFF_DETECT_COPY)\n+\t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n \n  cleanup:\ndiff --git a/t/t4003-diff-rename-1.sh b/t/t4003-diff-rename-1.sh\nindex c6130c4..bfa8835 100755\n--- a/t/t4003-diff-rename-1.sh\n+++ b/t/t4003-diff-rename-1.sh\n@@ -29,7 +29,7 @@ test_expect_success \\\n # copy-and-edit one, and rename-and-edit the other.  We do not say\n # anything about rezrov.\n \n-GIT_DIFF_OPTS=--unified=0 git diff-index -M -p $tree >current\n+GIT_DIFF_OPTS=--unified=0 git diff-index -C -p $tree >current\n cat >expected <<\\EOF\n diff --git a/COPYING b/COPYING.1\n copy from COPYING\ndiff --git a/t/t4004-diff-rename-symlink.sh b/t/t4004-diff-rename-symlink.sh\nindex 92a65f4..6e562c8 100755\n--- a/t/t4004-diff-rename-symlink.sh\n+++ b/t/t4004-diff-rename-symlink.sh\n@@ -35,7 +35,7 @@ test_expect_success SYMLINKS \\\n # a new creation.\n \n test_expect_success SYMLINKS 'setup diff output' \"\n-    GIT_DIFF_OPTS=--unified=0 git diff-index -M -p $tree >current &&\n+    GIT_DIFF_OPTS=--unified=0 git diff-index -C -p $tree >current &&\n     cat >expected <<\\EOF\n diff --git a/bozbar b/bozbar\n new file mode 120000\ndiff --git a/t/t4005-diff-rename-2.sh b/t/t4005-diff-rename-2.sh\nindex 1ba359d..77d7f49 100755\n--- a/t/t4005-diff-rename-2.sh\n+++ b/t/t4005-diff-rename-2.sh\n@@ -29,7 +29,7 @@ test_expect_success \\\n # and COPYING.2 are based on COPYING, and do not say anything about\n # rezrov.\n \n-git diff-index -M $tree >current\n+git diff-index -C $tree >current\n \n cat >expected <<\\EOF\n :100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0603b3238a076dc6c8022aedc6648fa523a17178 C1234\tCOPYING\tCOPYING.1\ndiff --git a/t/t4008-diff-break-rewrite.sh b/t/t4008-diff-break-rewrite.sh\nindex d79d9e1e..73b4a24 100755\n--- a/t/t4008-diff-break-rewrite.sh\n+++ b/t/t4008-diff-break-rewrite.sh\n@@ -173,8 +173,8 @@ test_expect_success \\\n     'compare_diff_raw expected current'\n \n test_expect_success \\\n-    'run diff with -B -M' \\\n-    'git diff-index -B -M \"$tree\" >current'\n+    'run diff with -B -C' \\\n+    'git diff-index -B -C \"$tree\" >current'\n \n cat >expected <<\\EOF\n :100644 100644 f5deac7be59e7eeab8657fd9ae706fd6a57daed2 08bb2fb671deff4c03a4d4a0a1315dff98d5732c C095\tfile0\tfile1\ndiff --git a/t/t4009-diff-rename-4.sh b/t/t4009-diff-rename-4.sh\nindex de3f174..f22c8e3 100755\n--- a/t/t4009-diff-rename-4.sh\n+++ b/t/t4009-diff-rename-4.sh\n@@ -29,7 +29,7 @@ test_expect_success \\\n # and COPYING.2 are based on COPYING, and do not say anything about\n # rezrov.\n \n-git diff-index -z -M $tree >current\n+git diff-index -z -C $tree >current\n \n cat >expected <<\\EOF\n :100644 100644 6ff87c4664981e4397625791c8ea3bbb5f2279a3 0603b3238a076dc6c8022aedc6648fa523a17178 C1234\n-- \n1.7.4.1.51.g2bf8a\n"},{"id":"161584","messageId":"alpine.LFD.2.02.1102182028410.4165@i5.linux-foundation.org","threadId":"26556","inReplyTo":"alpine.LFD.2.02.1102182025270.4165@i5.linux-foundation.org","subject":"[PATCH 3/3] diffcore-rename: improve estimate_similarity() heuristics","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-02-19T04:30:02Z","receivedAt":"2011-02-19T04:30:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Fri, 18 Feb 2011 20:12:06 -0800\n\nThe logic to quickly dismiss potential rename pairs was broken.  It\nwould too eagerly dismiss possible renames when all of the difference\nwas due to pure new data (or deleted data).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis is the trivial one-liner, now with a changelog and sign-off. It \nchanges the percentage of the size difference (delta_size) to be compared \nagainst the larger file size rather than the smaller file size.\n\n diffcore-rename.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex b9b039d..0cd4c13 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -170,7 +170,7 @@ static int estimate_similarity(struct diff_filespec *src,\n \t * and the final score computation below would not have a\n \t * divide-by-zero issue.\n \t */\n-\tif (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n+\tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n \tif (!src->cnt_data && diff_populate_filespec(src, 0))\n-- \n1.7.4.1.51.g2bf8a\n"}]}