{"thread":{"id":"42963","subject":"[[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content","startedAt":"2016-07-29T16:19:58Z","lastAt":"2016-08-04T14:21:49Z","messageCount":25,"participants":["Kevin Willford","Junio C Hamano","Johannes Schindelin","Eric Wong","Jakub Narębski"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"292521","messageId":"20160729161920.3792-1-kcwillford@gmail.com","threadId":"42963","inReplyTo":null,"subject":"[[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-29T16:19:16Z","receivedAt":"2016-07-29T16:19:58Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"This patch series is to remove the hand rolled hashmap in the patch_ids\nand use the hashmap.h implementation.  It also introduces the idea of having\na header only patch id so that the contents of the files do not have to be\nloaded in order to determine if two commits are different.\n\n\nKevin Willford (4):\n  patch-ids: stop using a hand-rolled hashmap implementation\n  patch-ids: replace the seen indicator with a commit pointer\n  patch-ids: add flag to create the diff patch id using header only data\n  rebase: avoid computing unnecessary patch IDs\n\n builtin/log.c                        |  2 +-\n diff.c                               | 16 +++---\n diff.h                               |  2 +-\n patch-ids.c                          | 99 +++++++++++++++---------------------\n patch-ids.h                          | 11 ++--\n revision.c                           | 18 ++-----\n t/perf/p3400-rebase.sh               | 36 +++++++++++++\n t/t6007-rev-list-cherry-pick-file.sh | 17 +++++++\n 8 files changed, 114 insertions(+), 87 deletions(-)\n create mode 100644 t/perf/p3400-rebase.sh\n\n-- \n2.9.2.windows.1\n\n"},{"id":"292522","messageId":"20160729161920.3792-2-kcwillford@gmail.com","threadId":"42963","inReplyTo":"20160729161920.3792-1-kcwillford@gmail.com","subject":"[[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-29T16:19:17Z","receivedAt":"2016-07-29T16:20:09Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"From: Kevin Willford <kewillf@microsoft.com>\n\nThis change will use the hashmap from the hashmap.h to keep track of the\npatch_ids that have been encountered instead of using an internal\nimplementation.  This simplifies the implementation of the patch ids.\n\nSigned-off-by: Kevin Willford <kcwillford@gmail.com>\n---\n patch-ids.c | 86 +++++++++++++++++++++----------------------------------------\n patch-ids.h |  7 +++--\n 2 files changed, 32 insertions(+), 61 deletions(-)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex a4d0016..db31fa6 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -16,90 +16,62 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n \treturn diff_flush_patch_id(options, sha1);\n }\n \n-static const unsigned char *patch_id_access(size_t index, void *table)\n+static int patch_id_cmp(struct patch_id *a,\n+\t\t\tstruct patch_id *b,\n+\t\t\tvoid *keydata)\n {\n-\tstruct patch_id **id_table = table;\n-\treturn id_table[index]->patch_id;\n+\treturn hashcmp(a->patch_id, b->patch_id);\n }\n \n-static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)\n-{\n-\treturn sha1_pos(id, table, nr, patch_id_access);\n-}\n-\n-#define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */\n-struct patch_id_bucket {\n-\tstruct patch_id_bucket *next;\n-\tint nr;\n-\tstruct patch_id bucket[BUCKET_SIZE];\n-};\n-\n int init_patch_ids(struct patch_ids *ids)\n {\n \tmemset(ids, 0, sizeof(*ids));\n \tdiff_setup(&ids->diffopts);\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n+\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n \treturn 0;\n }\n \n int free_patch_ids(struct patch_ids *ids)\n {\n-\tstruct patch_id_bucket *next, *patches;\n-\n-\tfree(ids->table);\n-\tfor (patches = ids->patches; patches; patches = next) {\n-\t\tnext = patches->next;\n-\t\tfree(patches);\n-\t}\n+\thashmap_free(&ids->patches, 1);\n \treturn 0;\n }\n \n-static struct patch_id *add_commit(struct commit *commit,\n-\t\t\t\t   struct patch_ids *ids,\n-\t\t\t\t   int no_add)\n+static int init_patch_id_entry(struct patch_id *patch,\n+\t\t\t       struct commit *commit,\n+\t\t\t       struct patch_ids *ids)\n {\n-\tstruct patch_id_bucket *bucket;\n-\tstruct patch_id *ent;\n-\tunsigned char sha1[20];\n-\tint pos;\n-\n-\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n-\t\treturn NULL;\n-\tpos = patch_pos(ids->table, ids->nr, sha1);\n-\tif (0 <= pos)\n-\t\treturn ids->table[pos];\n-\tif (no_add)\n-\t\treturn NULL;\n-\n-\tpos = -1 - pos;\n+\tif (commit_patch_id(commit, &ids->diffopts, patch->patch_id))\n+\t\treturn -1;\n \n-\tbucket = ids->patches;\n-\tif (!bucket || (BUCKET_SIZE <= bucket->nr)) {\n-\t\tbucket = xcalloc(1, sizeof(*bucket));\n-\t\tbucket->next = ids->patches;\n-\t\tids->patches = bucket;\n-\t}\n-\tent = &bucket->bucket[bucket->nr++];\n-\thashcpy(ent->patch_id, sha1);\n-\n-\tALLOC_GROW(ids->table, ids->nr + 1, ids->alloc);\n-\tif (pos < ids->nr)\n-\t\tmemmove(ids->table + pos + 1, ids->table + pos,\n-\t\t\tsizeof(ent) * (ids->nr - pos));\n-\tids->nr++;\n-\tids->table[pos] = ent;\n-\treturn ids->table[pos];\n+\thashmap_entry_init(patch, sha1hash(patch->patch_id));\n+\treturn 0;\n }\n \n struct patch_id *has_commit_patch_id(struct commit *commit,\n \t\t\t\t     struct patch_ids *ids)\n {\n-\treturn add_commit(commit, ids, 1);\n+\tstruct patch_id patch;\n+\n+\tmemset(&patch, 0, sizeof(patch));\n+\tif (init_patch_id_entry(&patch, commit, ids))\n+\t\treturn NULL;\n+\n+\treturn hashmap_get(&ids->patches, &patch, NULL);\n }\n \n struct patch_id *add_commit_patch_id(struct commit *commit,\n \t\t\t\t     struct patch_ids *ids)\n {\n-\treturn add_commit(commit, ids, 0);\n+\tstruct patch_id *key = xcalloc(1, sizeof(*key));\n+\n+\tif (init_patch_id_entry(key, commit, ids)) {\n+\t\tfree(key);\n+\t\treturn NULL;\n+\t}\n+\n+\thashmap_add(&ids->patches, key);\n+\treturn key;\n }\ndiff --git a/patch-ids.h b/patch-ids.h\nindex eeb56b3..9569ee0 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -2,15 +2,14 @@\n #define PATCH_IDS_H\n \n struct patch_id {\n-\tunsigned char patch_id[20];\n+\tstruct hashmap_entry ent;\n+\tunsigned char patch_id[GIT_SHA1_RAWSZ];\n \tchar seen;\n };\n \n struct patch_ids {\n+\tstruct hashmap patches;\n \tstruct diff_options diffopts;\n-\tint nr, alloc;\n-\tstruct patch_id **table;\n-\tstruct patch_id_bucket *patches;\n };\n \n int commit_patch_id(struct commit *commit, struct diff_options *options,\n-- \n2.9.2.gvfs.2.42.gb7633a3\n\n"},{"id":"292523","messageId":"20160729161920.3792-3-kcwillford@gmail.com","threadId":"42963","inReplyTo":"20160729161920.3792-1-kcwillford@gmail.com","subject":"[[PATCH v2] 2/4] patch-ids: replace the seen indicator with a commit pointer","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-29T16:19:18Z","receivedAt":"2016-07-29T16:20:28Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"From: Kevin Willford <kewillf@microsoft.com>\n\nThe cherry_pick_list was looping through the original side checking the\nseen indicator and setting the cherry_flag on the commit.  If we save\noff the commit in the patch_id we can set the cherry_flag on the correct\ncommit when running through the other side when a patch_id match is found.\n\nSigned-off-by: Kevin Willford <kcwillford@gmail.com>\n---\n patch-ids.c |  1 +\n patch-ids.h |  2 +-\n revision.c  | 18 +++---------------\n 3 files changed, 5 insertions(+), 16 deletions(-)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex db31fa6..bafaae2 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -43,6 +43,7 @@ static int init_patch_id_entry(struct patch_id *patch,\n \t\t\t       struct commit *commit,\n \t\t\t       struct patch_ids *ids)\n {\n+\tpatch->commit = commit;\n \tif (commit_patch_id(commit, &ids->diffopts, patch->patch_id))\n \t\treturn -1;\n \ndiff --git a/patch-ids.h b/patch-ids.h\nindex 9569ee0..dea1ecd 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -4,7 +4,7 @@\n struct patch_id {\n \tstruct hashmap_entry ent;\n \tunsigned char patch_id[GIT_SHA1_RAWSZ];\n-\tchar seen;\n+\tstruct commit *commit;\n };\n \n struct patch_ids {\ndiff --git a/revision.c b/revision.c\nindex edba5b7..19cc067 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -846,7 +846,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \t\t */\n \t\tif (left_first != !!(flags & SYMMETRIC_LEFT))\n \t\t\tcontinue;\n-\t\tcommit->util = add_commit_patch_id(commit, &ids);\n+\t\tadd_commit_patch_id(commit, &ids);\n \t}\n \n \t/* either cherry_mark or cherry_pick are true */\n@@ -873,21 +873,9 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \t\tid = has_commit_patch_id(commit, &ids);\n \t\tif (!id)\n \t\t\tcontinue;\n-\t\tid->seen = 1;\n-\t\tcommit->object.flags |= cherry_flag;\n-\t}\n \n-\t/* Now check the original side for seen ones */\n-\tfor (p = list; p; p = p->next) {\n-\t\tstruct commit *commit = p->item;\n-\t\tstruct patch_id *ent;\n-\n-\t\tent = commit->util;\n-\t\tif (!ent)\n-\t\t\tcontinue;\n-\t\tif (ent->seen)\n-\t\t\tcommit->object.flags |= cherry_flag;\n-\t\tcommit->util = NULL;\n+\t\tcommit->object.flags |= cherry_flag;\n+\t\tid->commit->object.flags |= cherry_flag;\n \t}\n \n \tfree_patch_ids(&ids);\n-- \n2.9.2.gvfs.2.42.gb7633a3\n\n"},{"id":"292524","messageId":"20160729161920.3792-5-kcwillford@gmail.com","threadId":"42963","inReplyTo":"20160729161920.3792-1-kcwillford@gmail.com","subject":"[[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-29T16:19:20Z","receivedAt":"2016-07-29T16:20:34Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"From: Kevin Willford <kewillf@microsoft.com>\n\nThe `rebase` family of Git commands avoid applying patches that were\nalready integrated upstream. They do that by using the revision walking\noption that computes the patch IDs of the two sides of the rebase\n(local-only patches vs upstream-only ones) and skipping those local\npatches whose patch ID matches one of the upstream ones.\n\nIn many cases, this causes unnecessary churn, as already the set of\npaths touched by a given commit would suffice to determine that an\nupstream patch has no local equivalent.\n\nThis hurts performance in particular when there are a lot of upstream\npatches, and/or large ones.\n\nTherefore, let's introduce the concept of a \"diff-header-only\" patch ID,\ncompare those first, and only evaluate the \"full\" patch ID lazily.\n\nPlease note that in contrast to the \"full\" patch IDs, those\n\"diff-header-only\" patch IDs are prone to collide with one another, as\nadjacent commits frequently touch the very same files. Hence we now\nhave to be careful to allow multiple hash entries with the same hash.\nWe accomplish that by using the hashmap_add() function that does not even\ntest for hash collisions.  This also allows us to evaluate the full patch ID\nlazily, i.e. only when we found commits with matching diff-header-only\npatch IDs.\n\nWe add a performance test that demonstrates ~1-6% improvement.  In\npractice this will depend on various factors such as how many upstream\nchanges and how big those changes are along with whether file system\ncaches are cold or warm.  As Git's test suite has no way of catching\nperformance regressions, we also add a regression test that verifies\nthat the full patch ID computation is skipped when the diff-header-only\ncomputation suffices.\n\nSigned-off-by: Kevin Willford <kcwillford@gmail.com>\n---\n builtin/log.c                        |  2 +-\n patch-ids.c                          | 22 ++++++++++++++++------\n patch-ids.h                          |  2 +-\n t/perf/p3400-rebase.sh               | 36 ++++++++++++++++++++++++++++++++++++\n t/t6007-rev-list-cherry-pick-file.sh | 17 +++++++++++++++++\n 5 files changed, 71 insertions(+), 8 deletions(-)\n create mode 100644 t/perf/p3400-rebase.sh\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex fd1652f..b076993 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1331,7 +1331,7 @@ static void prepare_bases(struct base_tree_info *bases,\n \t\tstruct object_id *patch_id;\n \t\tif (commit->util)\n \t\t\tcontinue;\n-\t\tif (commit_patch_id(commit, &diffopt, sha1))\n+\t\tif (commit_patch_id(commit, &diffopt, sha1, 0))\n \t\t\tdie(_(\"cannot get patch id\"));\n \t\tALLOC_GROW(bases->patch_id, bases->nr_patch_id + 1, bases->alloc_patch_id);\n \t\tpatch_id = bases->patch_id + bases->nr_patch_id;\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 69a14a3..0a4828a 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -5,7 +5,7 @@\n #include \"patch-ids.h\"\n \n int commit_patch_id(struct commit *commit, struct diff_options *options,\n-\t\t    unsigned char *sha1)\n+\t\t    unsigned char *sha1, int diff_header_only)\n {\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.oid.hash,\n@@ -13,13 +13,21 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n \telse\n \t\tdiff_root_tree_sha1(commit->object.oid.hash, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1, 0);\n+\treturn diff_flush_patch_id(options, sha1, diff_header_only);\n }\n \n static int patch_id_cmp(struct patch_id *a,\n \t\t\tstruct patch_id *b,\n-\t\t\tvoid *keydata)\n+\t\t\tstruct diff_options *opt)\n {\n+\tif (is_null_sha1(a->patch_id) &&\n+\t    commit_patch_id(a->commit, opt, a->patch_id, 0))\n+\t\treturn error(\"Could not get patch ID for %s\",\n+\t\t\toid_to_hex(&a->commit->object.oid));\n+\tif (is_null_sha1(b->patch_id) &&\n+\t    commit_patch_id(b->commit, opt, b->patch_id, 0))\n+\t\treturn error(\"Could not get patch ID for %s\",\n+\t\t\toid_to_hex(&b->commit->object.oid));\n \treturn hashcmp(a->patch_id, b->patch_id);\n }\n \n@@ -43,11 +51,13 @@ static int init_patch_id_entry(struct patch_id *patch,\n \t\t\t       struct commit *commit,\n \t\t\t       struct patch_ids *ids)\n {\n+\tunsigned char header_only_patch_id[GIT_SHA1_RAWSZ];\n+\n \tpatch->commit = commit;\n-\tif (commit_patch_id(commit, &ids->diffopts, patch->patch_id))\n+\tif (commit_patch_id(commit, &ids->diffopts, header_only_patch_id, 1))\n \t\treturn -1;\n \n-\thashmap_entry_init(patch, sha1hash(patch->patch_id));\n+\thashmap_entry_init(patch, sha1hash(header_only_patch_id));\n \treturn 0;\n }\n \n@@ -60,7 +70,7 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n \tif (init_patch_id_entry(&patch, commit, ids))\n \t\treturn NULL;\n \n-\treturn hashmap_get(&ids->patches, &patch, NULL);\n+\treturn hashmap_get(&ids->patches, &patch, &ids->diffopts);\n }\n \n struct patch_id *add_commit_patch_id(struct commit *commit,\ndiff --git a/patch-ids.h b/patch-ids.h\nindex dea1ecd..0f34ea1 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -13,7 +13,7 @@ struct patch_ids {\n };\n \n int commit_patch_id(struct commit *commit, struct diff_options *options,\n-\t\t    unsigned char *sha1);\n+\t\t    unsigned char *sha1, int);\n int init_patch_ids(struct patch_ids *);\n int free_patch_ids(struct patch_ids *);\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\ndiff --git a/t/perf/p3400-rebase.sh b/t/perf/p3400-rebase.sh\nnew file mode 100644\nindex 0000000..b3e7d52\n--- /dev/null\n+++ b/t/perf/p3400-rebase.sh\n@@ -0,0 +1,36 @@\n+#!/bin/sh\n+\n+test_description='Tests rebase performance'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'setup' '\n+\tgit checkout -f -b base &&\n+\tgit checkout -b to-rebase &&\n+\tgit checkout -b upstream &&\n+\tfor i in $(seq 100)\n+\tdo\n+\t\t# simulate huge diffs\n+\t\techo change$i >unrelated-file$i &&\n+\t\tseq 1000 >>unrelated-file$i &&\n+\t\tgit add unrelated-file$i &&\n+\t\ttest_tick &&\n+\t\tgit commit -m commit$i unrelated-file$i &&\n+\t\techo change$i >unrelated-file$i &&\n+\t\tseq 1000 | tac >>unrelated-file$i &&\n+\t\tgit add unrelated-file$i &&\n+\t\ttest_tick &&\n+\t\tgit commit -m commit$i-reverse unrelated-file$i ||\n+\t\tbreak\n+\tdone &&\n+\tgit checkout to-rebase &&\n+\ttest_commit our-patch interesting-file\n+'\n+\n+test_perf 'rebase on top of a lot of unrelated changes' '\n+\tgit rebase --onto upstream HEAD^ &&\n+\tgit rebase --onto base HEAD^\n+'\n+\n+test_done\ndiff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\nindex 28d4f6b..fff3322 100755\n--- a/t/t6007-rev-list-cherry-pick-file.sh\n+++ b/t/t6007-rev-list-cherry-pick-file.sh\n@@ -206,5 +206,22 @@ test_expect_success '--count --left-right' '\n \tgit rev-list --count --left-right C...D > actual &&\n \ttest_cmp expect actual\n '\n+remove_loose_object () {\n+\tsha1=\"$(git rev-parse \"$1\")\" &&\n+\tremainder=${sha1#??} &&\n+\tfirsttwo=${sha1%$remainder} &&\n+\trm .git/objects/$firsttwo/$remainder\n+}\n+test_expect_success '--cherry-pick avoids looking at full diffs' '\n+\tgit checkout -b shy-diff &&\n+\ttest_commit dont-look-at-me &&\n+\techo Hello >dont-look-at-me.t &&\n+\ttest_tick &&\n+\tgit commit -m tip dont-look-at-me.t &&\n+\tgit checkout -b mainline HEAD^ &&\n+\ttest_commit to-cherry-pick &&\n+\tremove_loose_object shy-diff^:dont-look-at-me.t &&\n+\tgit rev-list --cherry-pick ...shy-diff\n+'\n \n test_done\n-- \n2.9.2.gvfs.2.42.gb7633a3\n\n"},{"id":"292525","messageId":"20160729161920.3792-4-kcwillford@gmail.com","threadId":"42963","inReplyTo":"20160729161920.3792-1-kcwillford@gmail.com","subject":"[[PATCH v2] 3/4] patch-ids: add flag to create the diff patch id using header only data","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-29T16:19:19Z","receivedAt":"2016-07-29T16:20:37Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"From: Kevin Willford <kewillf@microsoft.com>\n\nThis will allow a diff patch id to be created using only the header data\nso that the contents of the file will not have to be loaded.\n\nSigned-off-by: Kevin Willford <kcwillford@gmail.com>\n---\n diff.c      | 16 ++++++++++------\n diff.h      |  2 +-\n patch-ids.c |  2 +-\n 3 files changed, 12 insertions(+), 8 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 7d03419..28a4190 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4455,7 +4455,7 @@ static void patch_id_consume(void *priv, char *line, unsigned long len)\n }\n \n /* returns 0 upon success, and writes result into sha1 */\n-static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n+static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1, int diff_header_only)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n@@ -4490,9 +4490,6 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \n \t\tdiff_fill_sha1_info(p->one);\n \t\tdiff_fill_sha1_info(p->two);\n-\t\tif (fill_mmfile(&mf1, p->one) < 0 ||\n-\t\t\t\tfill_mmfile(&mf2, p->two) < 0)\n-\t\t\treturn error(\"unable to read files to diff\");\n \n \t\tlen1 = remove_space(p->one->path, strlen(p->one->path));\n \t\tlen2 = remove_space(p->two->path, strlen(p->two->path));\n@@ -4527,6 +4524,13 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \t\t\t\t\tlen2, p->two->path);\n \t\tgit_SHA1_Update(&ctx, buffer, len1);\n \n+\t\tif (diff_header_only)\n+\t\t\tcontinue;\n+\n+\t\tif (fill_mmfile(&mf1, p->one) < 0 ||\n+\t\t\tfill_mmfile(&mf2, p->two) < 0)\n+\t\t\treturn error(\"unable to read files to diff\");\n+\n \t\tif (diff_filespec_is_binary(p->one) ||\n \t\t    diff_filespec_is_binary(p->two)) {\n \t\t\tgit_SHA1_Update(&ctx, oid_to_hex(&p->one->oid),\n@@ -4549,11 +4553,11 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \treturn 0;\n }\n \n-int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1)\n+int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1, int diff_header_only)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n-\tint result = diff_get_patch_id(options, sha1);\n+\tint result = diff_get_patch_id(options, sha1, diff_header_only);\n \n \tfor (i = 0; i < q->nr; i++)\n \t\tdiff_free_filepair(q->queue[i]);\ndiff --git a/diff.h b/diff.h\nindex 125447b..7883729 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -342,7 +342,7 @@ extern int run_diff_files(struct rev_info *revs, unsigned int option);\n extern int run_diff_index(struct rev_info *revs, int cached);\n \n extern int do_diff_cache(const unsigned char *, struct diff_options *);\n-extern int diff_flush_patch_id(struct diff_options *, unsigned char *);\n+extern int diff_flush_patch_id(struct diff_options *, unsigned char *, int);\n \n extern int diff_result_code(struct diff_options *, int);\n \ndiff --git a/patch-ids.c b/patch-ids.c\nindex bafaae2..69a14a3 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -13,7 +13,7 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n \telse\n \t\tdiff_root_tree_sha1(commit->object.oid.hash, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\treturn diff_flush_patch_id(options, sha1, 0);\n }\n \n static int patch_id_cmp(struct patch_id *a,\n-- \n2.9.2.gvfs.2.42.gb7633a3\n\n"},{"id":"292557","messageId":"xmqqshusmby9.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"20160729161920.3792-1-kcwillford@gmail.com","subject":"Re: [[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T20:22:22Z","receivedAt":"2016-07-29T20:22:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kcwillford@gmail.com> writes:\n\n> This patch series is to remove the hand rolled hashmap in the patch_ids\n> and use the hashmap.h implementation.  It also introduces the idea of having\n> a header only patch id so that the contents of the files do not have to be\n> loaded in order to determine if two commits are different.\n\n> Subject: Re: [[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content\n\nDid you do \"format-patch --subject-prefix='[PATCH v2]'\" or something\nlike that?  When applied, that would result in a commit title like\nthis:\n\n\t1/4] patch-ids: stop using a ...\n\nbecause we stop at the first ']', and we do not bother to count up\nto \"matching bracket\".\n\n    git format-patch --subject-prefix='PATCH v2'\n\nor even better\n\n    git format-patch -v2\n\nwould have been more appropriate.\n"},{"id":"292558","messageId":"xmqqoa5gmas6.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"20160729161920.3792-2-kcwillford@gmail.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T20:47:37Z","receivedAt":"2016-07-29T20:47:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kcwillford@gmail.com> writes:\n\n> From: Kevin Willford <kewillf@microsoft.com>\n>\n> This change will use the hashmap from the hashmap.h to keep track of the\n> patch_ids that have been encountered instead of using an internal\n> implementation.  This simplifies the implementation of the patch ids.\n>\n> Signed-off-by: Kevin Willford <kcwillford@gmail.com>\n> ---\n>  patch-ids.c | 86 +++++++++++++++++++++----------------------------------------\n>  patch-ids.h |  7 +++--\n>  2 files changed, 32 insertions(+), 61 deletions(-)\n\nThe patch text itself is almost unreadble because of a lot of\nverbose code it had to carry before this change, and the removal of\nthat unreadable code of course is the point of this very welcome\nclean-up ;-).  The resulting code is very readable.\n\n>  struct patch_id *has_commit_patch_id(struct commit *commit,\n>  \t\t\t\t     struct patch_ids *ids)\n>  {\n> -\treturn add_commit(commit, ids, 1);\n> +\tstruct patch_id patch;\n> +\n> +\tmemset(&patch, 0, sizeof(patch));\n> +\tif (init_patch_id_entry(&patch, commit, ids))\n> +\t\treturn NULL;\n> +\treturn hashmap_get(&ids->patches, &patch, NULL);\n>  }\n>  \n>  struct patch_id *add_commit_patch_id(struct commit *commit,\n>  \t\t\t\t     struct patch_ids *ids)\n>  {\n> -\treturn add_commit(commit, ids, 0);\n> +\tstruct patch_id *key = xcalloc(1, sizeof(*key));\n> +\n> +\tif (init_patch_id_entry(key, commit, ids)) {\n> +\t\tfree(key);\n> +\t\treturn NULL;\n> +\t}\n\nThis is a tangent, but this made me wonder if it is safe to simply\nfree(3) the result of calling hashmap_entry_init() which is called\nin init_patch_id_entry().  It would obviously become a resource\nleak, if a hashmap_entry (which the api documentation says is \"an\nopaque structure\") holds any allocated resource.\n\nThe fact that hashmap_entry_init() is there but there is no\ncorresponding hashmap_entry_clear() hints that there is nothing to\nbe worried about and I can see from the implementation of\nhashmap_entry_init() that no extra resource is held inside, but an\nAPI user should not have to guess.  We may want to do one of the two\nthings:\n\n * document that an embedded hashmap_entry does not hold any\n   resource that need to be released and it is safe to free the user\n   structure that embeds one; or\n\n * implement hashmap_entry_clear() that currently is a no-op.\n\nIf we anticipate that the hashmap implementation may gain more\nfields in this \"opaque\" structure, the latter might be a more\nfuture-proof approach, as all the callers of hashmap_entry_init()\nwould already be calling hashmap_entry_clear() to clean it up when\nsuch a change to the hashmap implementation happens.  On the other\nhand, a caller that does not call hashmap_entry_clear() would not be\nnoticed by anybody as leaking resources until such a change happens,\nso the future-proofing may not have much practical value (iow, the\nexisting callers of _init() would need to be audited anyway to make\nsure they also call _clear()).\n"},{"id":"292559","messageId":"xmqqk2g4ma1o.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"20160729161920.3792-3-kcwillford@gmail.com","subject":"Re: [[PATCH v2] 2/4] patch-ids: replace the seen indicator with a commit pointer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T21:03:31Z","receivedAt":"2016-07-29T21:03:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kcwillford@gmail.com> writes:\n\n> From: Kevin Willford <kewillf@microsoft.com>\n>\n> The cherry_pick_list was looping through the original side checking the\n> seen indicator and setting the cherry_flag on the commit.  If we save\n> off the commit in the patch_id we can set the cherry_flag on the correct\n> commit when running through the other side when a patch_id match is found.\n>\n> Signed-off-by: Kevin Willford <kcwillford@gmail.com>\n> ---\n>  patch-ids.c |  1 +\n>  patch-ids.h |  2 +-\n>  revision.c  | 18 +++---------------\n>  3 files changed, 5 insertions(+), 16 deletions(-)\n\nWe lose the final loop to fix up the shorter side, because the\nsecond loop now marks both sides.\n\nAnd as a side effect, we do not use commit->util which is a scarce\nshared resource (aka historical API wart).\n\nMakes sense.  Thanks.\n"},{"id":"292563","messageId":"xmqqeg6cm8tr.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"20160729161920.3792-2-kcwillford@gmail.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T21:29:52Z","receivedAt":"2016-07-29T21:30:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kcwillford@gmail.com> writes:\n\n> +static int patch_id_cmp(struct patch_id *a,\n> +\t\t\tstruct patch_id *b,\n> +\t\t\tvoid *keydata)\n>  {\n> +\treturn hashcmp(a->patch_id, b->patch_id);\n>  }\n>  \n>  int init_patch_ids(struct patch_ids *ids)\n>  {\n>  \tmemset(ids, 0, sizeof(*ids));\n>  \tdiff_setup(&ids->diffopts);\n>  \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n>  \tdiff_setup_done(&ids->diffopts);\n> +\thashmap_init(&ids->patches, (hashmap_cmp_fn)patch_id_cmp, 256);\n>  \treturn 0;\n>  }\n\nThis is a tangent, and I do not suggest to change patch 1/4 to flip\nthe style, but I am not sure if this is a good style, or casting it\nthe other way around is better from the type-checking point of view,\ni.e.\n\n    static int cmp_fn(const void *a_, const void *b_, const void *keydata)\n    {\n\tstruct patch_id *a = a_;\n        struct patch_id *b = b_;\n\treturn hashcmp(a->patch_id, b->patch_id);\n    }\n\n    ...\n    \thashmap_init(..., cmp_fn, ...);\n    ...\n\nI see many existing calls to hashmap_init() follow this pattern, so\nas I said, patch 1/4 is fine as-is.\n\nThanks.\n"},{"id":"292564","messageId":"xmqqa8h0m82f.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"20160729161920.3792-5-kcwillford@gmail.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T21:46:16Z","receivedAt":"2016-07-29T21:46:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kcwillford@gmail.com> writes:\n\n>  static int patch_id_cmp(struct patch_id *a,\n>  \t\t\tstruct patch_id *b,\n> -\t\t\tvoid *keydata)\n> +\t\t\tstruct diff_options *opt)\n>  {\n> +\tif (is_null_sha1(a->patch_id) &&\n> +\t    commit_patch_id(a->commit, opt, a->patch_id, 0))\n> +\t\treturn error(\"Could not get patch ID for %s\",\n> +\t\t\toid_to_hex(&a->commit->object.oid));\n> +\tif (is_null_sha1(b->patch_id) &&\n> +\t    commit_patch_id(b->commit, opt, b->patch_id, 0))\n> +\t\treturn error(\"Could not get patch ID for %s\",\n> +\t\t\toid_to_hex(&b->commit->object.oid));\n>  \treturn hashcmp(a->patch_id, b->patch_id);\n>  }\n\nThese error returns initially looks slightly iffy in that in general\nthe caller of any_cmp_fn() wants to know how a/b compares, but by\nreturning error(), it always says \"a is smaller than b\".  This\nhowever may be OK because the callers in hashmap_get* implementation\nonly wants to know \"are they equal?\", and we are saying \"no they\ncannot possibly be equal\" here.  The original that ran a full\ncommit_patch_id() in now-removed add_commit() helper function didn't\neven diagnose this error and silently omitted the commit from the\ncandidate list, so this may be even seen as an improvement.\n\nThe idea of using the two level hash, computing the more expensive\none only when the hashmap hashes of the result of the cheaper hash\nfunction collide, is excellent.  Thanks.\n\n\n"},{"id":"292704","messageId":"alpine.DEB.2.20.1607301056120.11824@virtualbox","threadId":"42963","inReplyTo":"xmqqoa5gmas6.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-01T08:54:48Z","receivedAt":"2016-08-01T08:55:13Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nfirst of all: Kevin & I are colleagues and I helped prepare this patch\nseries. I had the idea to have a two-level patch ID to help e.g. when an\nalternate object store is hosted on a (slow) network drive.\n\nOn Fri, 29 Jul 2016, Junio C Hamano wrote:\n\n> Kevin Willford <kcwillford@gmail.com> writes:\n> \n> >  struct patch_id *add_commit_patch_id(struct commit *commit,\n> >  \t\t\t\t     struct patch_ids *ids)\n> >  {\n> > -\treturn add_commit(commit, ids, 0);\n> > +\tstruct patch_id *key = xcalloc(1, sizeof(*key));\n> > +\n> > +\tif (init_patch_id_entry(key, commit, ids)) {\n> > +\t\tfree(key);\n> > +\t\treturn NULL;\n> > +\t}\n> \n> This is a tangent, but this made me wonder if it is safe to simply\n> free(3) the result of calling hashmap_entry_init() which is called\n> in init_patch_id_entry().  It would obviously become a resource\n> leak, if a hashmap_entry (which the api documentation says is \"an\n> opaque structure\") holds any allocated resource.\n\nIt would be a serious bug if hashmap_entry_init() played games with\nreferences, given its signature (that this function does not have any\naccess to the hashmap structure, only to the entry itself):\n\n\tvoid hashmap_entry_init(void *entry, unsigned int hash)\n\nPlease note that the `void *entry` really needs to point to a struct whose\nfirst field is of type `struct hashmap_entry`. This is not type-safe, of\ncourse, but C does not allow a strong sub-typing of the kind we want to\nuse here.\n\n> The fact that hashmap_entry_init() is there but there is no\n> corresponding hashmap_entry_clear() hints that there is nothing to\n> be worried about and I can see from the implementation of\n> hashmap_entry_init() that no extra resource is held inside, but an\n> API user should not have to guess.  We may want to do one of the two\n> things:\n> \n>  * document that an embedded hashmap_entry does not hold any\n>    resource that need to be released and it is safe to free the user\n>    structure that embeds one; or\n> \n>  * implement hashmap_entry_clear() that currently is a no-op.\n\nUrgh. The only reason we have hashmap_entry_init() is that we *may* want\nto extend `struct hashmap_entry` at some point. That is *already*\nover-engineered because that point in time seems quite unlikely to arrive,\nlike, ever.\n\nIn that light, as you said, why would we overengineer things even further\nby introducing a hashmap_entry_clear(), especially given that we won't\ncatch any forgotten _clear() calls, given that it is a no-op anyway?\n\nLet's just not.\n\nCiao,\nDscho\n"},{"id":"292706","messageId":"alpine.DEB.2.20.1608011055180.149069@virtualbox","threadId":"42963","inReplyTo":"xmqqa8h0m82f.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-01T08:58:54Z","receivedAt":"2016-08-01T08:59:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Fri, 29 Jul 2016, Junio C Hamano wrote:\n\n> Kevin Willford <kcwillford@gmail.com> writes:\n> \n> >  static int patch_id_cmp(struct patch_id *a,\n> >  \t\t\tstruct patch_id *b,\n> > -\t\t\tvoid *keydata)\n> > +\t\t\tstruct diff_options *opt)\n> >  {\n> > +\tif (is_null_sha1(a->patch_id) &&\n> > +\t    commit_patch_id(a->commit, opt, a->patch_id, 0))\n> > +\t\treturn error(\"Could not get patch ID for %s\",\n> > +\t\t\toid_to_hex(&a->commit->object.oid));\n> > +\tif (is_null_sha1(b->patch_id) &&\n> > +\t    commit_patch_id(b->commit, opt, b->patch_id, 0))\n> > +\t\treturn error(\"Could not get patch ID for %s\",\n> > +\t\t\toid_to_hex(&b->commit->object.oid));\n> >  \treturn hashcmp(a->patch_id, b->patch_id);\n> >  }\n> \n> These error returns initially looks slightly iffy in that in general\n> the caller of any_cmp_fn() wants to know how a/b compares, but by\n> returning error(), it always says \"a is smaller than b\".\n\nI am to blame, as this is my design.\n\nAnd yes, it is kind of funny that we require a cmpfn that returns <0, ==0\nand >0 for comparisons, when hashmaps try to avoid any order.\n\nDo you want a note in the commit message about this \"abuse\" of a negative\nreturn value, or a code comment?\n\n> The idea of using the two level hash, computing the more expensive\n> one only when the hashmap hashes of the result of the cheaper hash\n> function collide, is excellent.\n\nThanks :-)\n\nCiao,\nDscho\n"},{"id":"292708","messageId":"alpine.DEB.2.20.1608011059040.149069@virtualbox","threadId":"42963","inReplyTo":"xmqqshusmby9.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-01T09:01:01Z","receivedAt":"2016-08-01T09:01:40Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Fri, 29 Jul 2016, Junio C Hamano wrote:\n\n> Kevin Willford <kcwillford@gmail.com> writes:\n> \n> > This patch series is to remove the hand rolled hashmap in the patch_ids\n> > and use the hashmap.h implementation.  It also introduces the idea of having\n> > a header only patch id so that the contents of the files do not have to be\n> > loaded in order to determine if two commits are different.\n> \n> > Subject: Re: [[PATCH v2] 0/4] Use header data patch ids for rebase to avoid loading file content\n> \n> Did you do \"format-patch --subject-prefix='[PATCH v2]'\" or something\n> like that?\n\nThis is my fault, sorry, I suggested this usage (misremembering the\nsemantics because I only use my mail-patch-series.sh helper and never use\nformat-patch manually anymore).\n\n>     git format-patch --subject-prefix='PATCH v2'\n> \n> or even better\n> \n>     git format-patch -v2\n> \n> would have been more appropriate.\n\nOooh, I did not know about the latter form. Nice.\n\nThanks,\nDscho\n"},{"id":"292783","messageId":"xmqqy44gi7bp.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"alpine.DEB.2.20.1607301056120.11824@virtualbox","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-01T20:04:58Z","receivedAt":"2016-08-01T20:20:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> It would be a serious bug if hashmap_entry_init() played games with\n> references, given its signature (that this function does not have any\n> access to the hashmap structure, only to the entry itself):\n>\n> \tvoid hashmap_entry_init(void *entry, unsigned int hash)\n\nI do not think we are on the same page.  The \"reference to other\nresource\" I wondered was inside the hashmap_entry structure, IOW,\n\"the entry itself\".\n\nWhich is declared to be opaque to the API users, so whoever defined\nthat API cannot blame me for not checking its definition to see that\nit only has \"unsigned int hash\" and no allocated memory or open file\ndescriptor in it that needs freeing.\n\nBy the way, the first parameter of the function being \"void *\" is\nmerely to help lazy API users, who have their own structure that\nembeds the hashmap_entry as its first element, as API documentation\ntells them to do, e.g.\n\n\tstruct foo {\n        \tstruct hashmap_entry e;\n                ... other \"foo\" specific fields come here ...\n\t} foo;\n\nand because of the lazy \"void *\", they do not have to do this:\n\n\thashmap_entry_init(&foo->e, ...);\n\nwhich would be required if the first parameter were \"struct\nhashmap_entry *\", but they can just do this:\n\n\thashmap_entry_init(&foo, ...);\n\nI have a slight preference to avoid the lazy \"void *\", but that is\nan unrelated tangent.\n\n>> The fact that hashmap_entry_init() is there but there is no\n>> corresponding hashmap_entry_clear() hints that there is nothing to\n>> be worried about and I can see from the implementation of\n>> hashmap_entry_init() that no extra resource is held inside, but an\n>> API user should not have to guess.  We may want to do one of the two\n>> things:\n>> \n>>  * document that an embedded hashmap_entry does not hold any\n>>    resource that need to be released and it is safe to free the user\n>>    structure that embeds one; or\n>> \n>>  * implement hashmap_entry_clear() that currently is a no-op.\n>\n> Urgh. The only reason we have hashmap_entry_init() is that we *may* want\n> to extend `struct hashmap_entry` at some point. That is *already*\n> over-engineered because that point in time seems quite unlikely to arrive,\n> like, ever.\n\nI am saying that an uneven over-enginnering is bad.\n\nTo be consistent with having _init() and declaring the entry\nstructure to be opaque, you would either need _clear() or document\nyou would never need to worry about the lack of _clear().\n"},{"id":"292784","messageId":"xmqqtwf4i71l.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"alpine.DEB.2.20.1608011055180.149069@virtualbox","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-01T20:11:02Z","receivedAt":"2016-08-01T20:25:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Hi Junio,\n>\n> On Fri, 29 Jul 2016, Junio C Hamano wrote:\n>\n>> Kevin Willford <kcwillford@gmail.com> writes:\n>> \n>> >  static int patch_id_cmp(struct patch_id *a,\n>> >  \t\t\tstruct patch_id *b,\n>> > -\t\t\tvoid *keydata)\n>> > +\t\t\tstruct diff_options *opt)\n>> >  {\n>> > +\tif (is_null_sha1(a->patch_id) &&\n>> > +\t    commit_patch_id(a->commit, opt, a->patch_id, 0))\n>> > +\t\treturn error(\"Could not get patch ID for %s\",\n>> > +\t\t\toid_to_hex(&a->commit->object.oid));\n>> > +\tif (is_null_sha1(b->patch_id) &&\n>> > +\t    commit_patch_id(b->commit, opt, b->patch_id, 0))\n>> > +\t\treturn error(\"Could not get patch ID for %s\",\n>> > +\t\t\toid_to_hex(&b->commit->object.oid));\n>> >  \treturn hashcmp(a->patch_id, b->patch_id);\n>> >  }\n>> \n>> These error returns initially looks slightly iffy in that in general\n>> the caller of any_cmp_fn() wants to know how a/b compares, but by\n>> returning error(), it always says \"a is smaller than b\".\n>\n> I am to blame, as this is my design.\n>\n> And yes, it is kind of funny that we require a cmpfn that returns <0, ==0\n> and >0 for comparisons, when hashmaps try to avoid any order.\n\nPerhaps hashmap API needs fixing in the longer term not to call this\ntype hashmap_cmp_fn; instead it should lose cmp and say something\nlike hashmap_eq_fn or something.\n\n> Do you want a note in the commit message about this \"abuse\" of a negative\n> return value, or a code comment?\n\nI do not think negative (or non-zero) return is an \"abuse\" at all.\nIt is misleading in the context of the function whose name has \"cmp\"\nin it, but that is not the fault of this function, rather, the\nbreakage is more in the API that calls a function that wants to know\nonly equality a \"cmp\".  A in-code comment before the function name\nmay be appropriate:\n\n        /*\n         * hashmap API calls hashmap_cmp_fn, but it only wants\n         * \"does the key match the entry?\" with 0 (matches) and\n         * non-zero (does not match).\n         */\n        static int patch_id_match(const struct patch_id *ent,\n                                  const struct patch_id *key,\n                                  const void *keydata)\n        {\n                ...\n\n"},{"id":"292809","messageId":"20160801223447.GA10924@whir","threadId":"42963","inReplyTo":"xmqqy44gi7bp.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2016-08-01T22:34:47Z","receivedAt":"2016-08-01T22:35:24Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > It would be a serious bug if hashmap_entry_init() played games with\n> > references, given its signature (that this function does not have any\n> > access to the hashmap structure, only to the entry itself):\n> >\n> > \tvoid hashmap_entry_init(void *entry, unsigned int hash)\n\n<snip>\n\n> I have a slight preference to avoid the lazy \"void *\", but that is\n> an unrelated tangent.\n\nMe too.  I noticed this while working on the http-walker\nspeedups and my self-rejected last patch:\n\n  https://public-inbox.org/git/20160711210243.GA1604%40whir/\n\nExtracting list_entry from list.h (currently in next[1]) and\nexposing that generically as \"container_of\" for use with\nhashmap_* would make it safer-to-use and allow structs to belong\nto multiple hashmaps.\n\nlist_entry is also an alias for container_of in the Linux\nkernel, but we don't have enough code using list_* to\nwarrant two names for the same macro.\n\n[1] https://public-inbox.org/git/20160711205131.1291-4-e%4080x24.org/\n"},{"id":"292823","messageId":"8ec80c21-5ab1-d806-d8d6-e7180be00670@gmail.com","threadId":"42963","inReplyTo":"xmqqtwf4i71l.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-08-02T09:50:58Z","receivedAt":"2016-08-02T10:22:16Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 01.08.2016 o 22:11, Junio C Hamano pisze:\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>> On Fri, 29 Jul 2016, Junio C Hamano wrote:\n\n>>> These error returns initially looks slightly iffy in that in general\n>>> the caller of any_cmp_fn() wants to know how a/b compares, but by\n>>> returning error(), it always says \"a is smaller than b\".\n>>\n>> I am to blame, as this is my design.\n>>\n>> And yes, it is kind of funny that we require a cmpfn that returns <0, ==0\n>> and >0 for comparisons, when hashmaps try to avoid any order.\n> \n> Perhaps hashmap API needs fixing in the longer term not to call this\n> type hashmap_cmp_fn; instead it should lose cmp and say something\n> like hashmap_eq_fn or something.\n\nThe problem is that one expects hashmap_cmp_fn() to return ==0 on equality,\nwhile one would expect for hashmap_eq_fn() to return true (==1) on equality.\nSo we would have to rewrite all calling sites.\n\nIt would be nice to have a comment about how hashmap uses cmpfn in\nhashmap.h.  \n\n\nThough... currently our hashmap implementation uses linked\nlist (separate chaining) for handling hash collisions (for collision\nresolution). More sophisticated data structures, such as balanced search\ntrees, or splay trees, are worth considering only if the load factor is\nlarge, or if the hash distribution is likely to be very non-uniform,\nor if one must guarantee good performance even in a worst-case scenario.\nSo almost certainly comparing function (which is needed for trees)\nwon't be needed.\n\nBest,\n-- \nJakub Narębski\n\n"},{"id":"292826","messageId":"alpine.DEB.2.20.1608021244450.79248@virtualbox","threadId":"42963","inReplyTo":"xmqqtwf4i71l.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-02T10:45:17Z","receivedAt":"2016-08-02T10:46:14Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Mon, 1 Aug 2016, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > On Fri, 29 Jul 2016, Junio C Hamano wrote:\n> >\n> >> Kevin Willford <kcwillford@gmail.com> writes:\n> >> \n> >> >  static int patch_id_cmp(struct patch_id *a,\n> >> >  \t\t\tstruct patch_id *b,\n> >> > -\t\t\tvoid *keydata)\n> >> > +\t\t\tstruct diff_options *opt)\n> >> >  {\n> >> > +\tif (is_null_sha1(a->patch_id) &&\n> >> > +\t    commit_patch_id(a->commit, opt, a->patch_id, 0))\n> >> > +\t\treturn error(\"Could not get patch ID for %s\",\n> >> > +\t\t\toid_to_hex(&a->commit->object.oid));\n> >> > +\tif (is_null_sha1(b->patch_id) &&\n> >> > +\t    commit_patch_id(b->commit, opt, b->patch_id, 0))\n> >> > +\t\treturn error(\"Could not get patch ID for %s\",\n> >> > +\t\t\toid_to_hex(&b->commit->object.oid));\n> >> >  \treturn hashcmp(a->patch_id, b->patch_id);\n> >> >  }\n> >> \n> >> These error returns initially looks slightly iffy in that in general\n> >> the caller of any_cmp_fn() wants to know how a/b compares, but by\n> >> returning error(), it always says \"a is smaller than b\".\n> >\n> > I am to blame, as this is my design.\n> >\n> > And yes, it is kind of funny that we require a cmpfn that returns <0, ==0\n> > and >0 for comparisons, when hashmaps try to avoid any order.\n> \n> Perhaps hashmap API needs fixing in the longer term not to call this\n> type hashmap_cmp_fn; instead it should lose cmp and say something\n> like hashmap_eq_fn or something.\n\nMaybe.\n\nBut to make sure: you do not expect Kevin to do that in the context of\nthis here patch series, right?\n\nCiao,\nDscho\n"},{"id":"292828","messageId":"alpine.DEB.2.20.1608021013010.79248@virtualbox","threadId":"42963","inReplyTo":"xmqqy44gi7bp.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-02T10:30:36Z","receivedAt":"2016-08-02T11:02:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Mon, 1 Aug 2016, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > It would be a serious bug if hashmap_entry_init() played games with\n> > references, given its signature (that this function does not have any\n> > access to the hashmap structure, only to the entry itself):\n> >\n> > \tvoid hashmap_entry_init(void *entry, unsigned int hash)\n> \n> I do not think we are on the same page.  The \"reference to other\n> resource\" I wondered was inside the hashmap_entry structure, IOW,\n> \"the entry itself\".\n\nOh, I see now.\n\n> Which is declared to be opaque to the API users,\n\nActually, not really. We cannot do that in C: we need to define the struct\nin hashmap.h so that its size is known to the users.\n\n> so whoever defined that API cannot blame me for not checking its\n> definition to see that it only has \"unsigned int hash\" and no allocated\n> memory or open file descriptor in it that needs freeing.\n\nThat is the reason, I guess, why we have the documentation in\nDocumentation/technical/api-hashmap.txt: it would have to talk about your\nhypothetical hashmap_entry_clear() (which would better be named\n*_release() BTW, unless I misunderstood what you want a hypothetical\nfuture version of that function to do).\n\nAnd quite frankly, unless we *have* to, I would rather try to avoid\nintroducing that function as much as possible, as it would make using the\nhashmap API even more finicky than it already is.\n\n> By the way, the first parameter of the function being \"void *\" is\n> merely to help lazy API users, who have their own structure that\n> embeds the hashmap_entry as its first element, as API documentation\n> tells them to do, e.g.\n> \n> \tstruct foo {\n>         \tstruct hashmap_entry e;\n>                 ... other \"foo\" specific fields come here ...\n> \t} foo;\n> \n> and because of the lazy \"void *\", they do not have to do this:\n> \n> \thashmap_entry_init(&foo->e, ...);\n> \n> which would be required if the first parameter were \"struct\n> hashmap_entry *\", but they can just do this:\n> \n> \thashmap_entry_init(&foo, ...);\n\nYes, I know that. It is the common way to simulate subclassing in C, for\nlack of a more compile-safe construct.\n\n> I have a slight preference to avoid the lazy \"void *\", but that is\n> an unrelated tangent.\n\nOh, we are already safely in Unrelated Tangent Land for a while, I would\nthink. Nothing of what we are discussing in this thread has anything to do\nwith Kevin's patch series, which is about trying to use resources more\nsensibly when using the revision machinery's --cherry-pick option.\n\nAnd since we are already there, I'll offer an opinion in favor of `void\n*`: doing the &foo->e dance could quite possibly suggest that `e` is a\nfield just like any other field (and does not necessarily *need* to be the\nfirst).\n\nBut again, this has nothing to do with the patch series we are discussing\nhere.\n\n> >> The fact that hashmap_entry_init() is there but there is no\n> >> corresponding hashmap_entry_clear() hints that there is nothing to be\n> >> worried about and I can see from the implementation of\n> >> hashmap_entry_init() that no extra resource is held inside, but an\n> >> API user should not have to guess.  We may want to do one of the two\n> >> things:\n> >> \n> >>  * document that an embedded hashmap_entry does not hold any\n> >>    resource that need to be released and it is safe to free the user\n> >>    structure that embeds one; or\n> >> \n> >>  * implement hashmap_entry_clear() that currently is a no-op.\n> >\n> > Urgh. The only reason we have hashmap_entry_init() is that we *may* want\n> > to extend `struct hashmap_entry` at some point. That is *already*\n> > over-engineered because that point in time seems quite unlikely to arrive,\n> > like, ever.\n> \n> I am saying that an uneven over-enginnering is bad.\n\nHmm. I guess that the _init() function could be replaced by an _INIT macro\na la STRBUF_INIT. Not sure it is really worth the effort, though.\n\nCiao,\nDscho\n"},{"id":"292844","messageId":"xmqqshunf6lm.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"alpine.DEB.2.20.1608021013010.79248@virtualbox","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-02T17:01:09Z","receivedAt":"2016-08-02T17:06:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Hi Junio,\n>\n> On Mon, 1 Aug 2016, Junio C Hamano wrote:\n>\n>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>> \n>> > It would be a serious bug if hashmap_entry_init() played games with\n>> > references, given its signature (that this function does not have any\n>> > access to the hashmap structure, only to the entry itself):\n>> >\n>> > \tvoid hashmap_entry_init(void *entry, unsigned int hash)\n>> \n>> I do not think we are on the same page.  The \"reference to other\n>> resource\" I wondered was inside the hashmap_entry structure, IOW,\n>> \"the entry itself\".\n>\n> Oh, I see now.\n>\n>> Which is declared to be opaque to the API users,\n>\n> Actually, not really. We cannot do that in C: we need to define the struct\n> in hashmap.h so that its size is known to the users.\n\nWhat I meant was what Documentation/technical/api-hashmap.txt said.\nI know that we cannot embed a true \"opaque\" structure in C just as\nyou do.\n\n> That is the reason, I guess, why we have the documentation in\n> Documentation/technical/api-hashmap.txt: it would have to talk about your\n> hypothetical hashmap_entry_clear() (which would better be named\n> *_release() BTW, unless I misunderstood what you want a hypothetical\n> future version of that function to do).\n\nI think there is no misunderstanding on your part.  I am following\nthe conclusion (as I recall) of a discussion on the list not in so\ndistant past about X_free(x) that frees the resource an instance of\n\"struct X\" holds and also the instance itself, and X_clear(x) that\nonly frees the resources without freeing the instance (the latter of\nwhich allows x to be on stack, you do X_init(&x) and conclude with\nX_clear(&x)).  The name X_clear() is more in line with existing API\nfunctions like string_list_clear(), argv_array_clear().  An oddball\nis strbuf_release(), which I think made you make the above comment.\n\n>> I have a slight preference to avoid the lazy \"void *\", but that is\n>> an unrelated tangent.\n>\n> Oh, we are already safely in Unrelated Tangent Land for a while, I would\n> think. Nothing of what we are discussing in this thread has anything to do\n> with Kevin's patch series,...\n\nOh, no question about that.  Go back to my review, to which your\nmessage I am responding to is a reply to.  What you wrote are all\nabout things after \"This is a tangent, but this made me wonder if it\nis safe to simply free(3) the result...\", which pointed out rough\npoints in the hashmap API from the API user's point of view and\nsuggested a few possible improvement opportunities.\n\n>> I am saying that an uneven over-enginnering is bad.\n>\n> Hmm. I guess that the _init() function could be replaced by an _INIT macro\n> a la STRBUF_INIT. Not sure it is really worth the effort, though.\n\nI do not think so, as X_init() and X_INIT() from the point of view\nof the API user would not make much difference; as long as the\ndocumentation does not say it is safe to make it go out of scope\nwithout \"deinitialize\" it, the reader will be left wondering.\n"},{"id":"292845","messageId":"xmqqoa5bf6d0.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"8ec80c21-5ab1-d806-d8d6-e7180be00670@gmail.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-02T17:06:19Z","receivedAt":"2016-08-02T17:06:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narębski <jnareb@gmail.com> writes:\n\n> The problem is that one expects hashmap_cmp_fn() to return ==0 on equality,\n> while one would expect for hashmap_eq_fn() to return true (==1) on equality.\n> So we would have to rewrite all calling sites.\n\nYes, and I do not think it is a \"problem\".  There only are about a\ndozen callsites of hashmap_init().\n\n> It would be nice to have a comment about how hashmap uses cmpfn in\n> hashmap.h.  \n\nThat is the absolute minimum but I think that is already done in the\nDocumentation/technical/api-hashmap.txt.\n\n> Though... currently our hashmap implementation uses linked\n> list (separate chaining) for handling hash collisions (for collision\n> resolution). More sophisticated data structures, such as balanced search\n> trees,...\n\nBut that requires total ordering of the elements registered in a\nhashmap.  So far, because cmp_fn that was misnamed was only about\nequality, you can safely use a hashmap to store things that do not\nhave inherent order among them.  Besides, if your hashmap has to\noptimize the hash collision resolution part with complex strucure,\nyour hash function is bad or your hash bucket growing strategy is\nsuboptimal, or both, which is the first thing you should look at,\nnot the \"now how would we find it in the bucket with too many\nthings?\"\n\n"},{"id":"292846","messageId":"xmqqk2fzf69w.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"alpine.DEB.2.20.1608021244450.79248@virtualbox","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-02T17:08:11Z","receivedAt":"2016-08-02T17:09:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n>> Perhaps hashmap API needs fixing in the longer term not to call this\n>> type hashmap_cmp_fn; instead it should lose cmp and say something\n>> like hashmap_eq_fn or something.\n>\n> Maybe.\n>\n> But to make sure: you do not expect Kevin to do that in the context of\n> this here patch series, right?\n\nI think I already answered this in the message you are responding\nto.\n\n> Do you want a note in the commit message about this \"abuse\" of a negative\n> return value, or a code comment?\n\nI do not think negative (or non-zero) return is an \"abuse\" at all.\nIt is misleading in the context of the function whose name has \"cmp\"\nin it, but that is not the fault of this function, rather, the\nbreakage is more in the API that calls a function that wants to know\nonly equality a \"cmp\".  A in-code comment before the function name\nmay be appropriate:\n\n        /*\n         * hashmap API calls hashmap_cmp_fn, but it only wants\n         * \"does the key match the entry?\" with 0 (matches) and\n         * non-zero (does not match).\n         */\n        static int patch_id_match(const struct patch_id *ent,\n                                  const struct patch_id *key,\n                                  const void *keydata)\n        {\n                ...\n\n"},{"id":"292852","messageId":"xmqqtwf3dp4a.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"xmqqshunf6lm.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 1/4] patch-ids: stop using a hand-rolled hashmap implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-02T18:04:05Z","receivedAt":"2016-08-02T18:10:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n>\n>> Oh, we are already safely in Unrelated Tangent Land for a while, I would\n>> think. Nothing of what we are discussing in this thread has anything to do\n>> with Kevin's patch series,...\n>\n> Oh, no question about that.  Go back to my review, to which your\n> message I am responding to is a reply to.  What you wrote are all\n> about things after \"This is a tangent, but this made me wonder if it\n> is safe to simply free(3) the result...\", which pointed out rough\n> points in the hashmap API from the API user's point of view and\n> suggested a few possible improvement opportunities.\n\nIn other words, I'd be happy with a patch like this, outside the\nscope of and independent from this series.\n\nWhen the hashmap_entry structure does acquire references to external\nresources (which I wouldn't judge the likelihood of), this paragraph\nwill become stale, but that is exactly the point at which _clear()\nfunction needs to be added to the API and described here, replacing\nthis paragraph.\n\nI do not mind having an empty _clear() before that happens, but I do\nnot think it adds much safety.  A disciplined user of the API may\ncall that empty _clear() to make her code future-proof, but we know\nthere are undisciplined developers and reviewers and there will be\ncodepaths that call _init() without calling the empty _clear(), and\nwe won't notice it.  Whoever is adding the real need for _clear()\nmust audit the codebase at that point _anyway_, and that is why I\nthink having an empty _clear() before would not buy us much.\n\n Documentation/technical/api-hashmap.txt | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex ad7a5bd..1dcec3d 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -104,6 +104,11 @@ If `free_entries` is true, each hashmap_entry in the map is freed as well\n `entry` points to the entry to initialize.\n +\n `hash` is the hash code of the entry.\n++\n+The hashmap_entry structure does not hold references to external resources,\n+and it is safe to just discard it once you are done with it (i.e. if\n+your structure was allocated with xmalloc(), you can just free(3) it,\n+and if it is on stack, you can just let it go out of scope).\n \n `void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`::\n \n"},{"id":"293060","messageId":"xmqqziot5jc3.fsf@gitster.mtv.corp.google.com","threadId":"42963","inReplyTo":"xmqqk2fzf69w.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-04T03:00:44Z","receivedAt":"2016-08-04T03:35:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> I do not think negative (or non-zero) return is an \"abuse\" at all.\n> It is misleading in the context of the function whose name has \"cmp\"\n> in it, but that is not the fault of this function, rather, the\n> breakage is more in the API that calls a function that wants to know\n> only equality a \"cmp\".  A in-code comment before the function name\n> may be appropriate:\n>\n>         /*\n>          * hashmap API calls hashmap_cmp_fn, but it only wants\n>          * \"does the key match the entry?\" with 0 (matches) and\n>          * non-zero (does not match).\n>          */\n>         static int patch_id_match(const struct patch_id *ent,\n>                                   const struct patch_id *key,\n>                                   const void *keydata)\n>         {\n>                 ...\n\nHow about this one instead (to be squashed into 4/4)?\n\nThe updated wording directly addresses the puzzlement I initially\nfelt \"This returns error() which is always negative, so comparing\n(A, B) would say A < B, while comparing (B, A) would say B < A.\nWould it cause a problem in the caller?\" while reading the function\nby being explicit that the sign does not matter.\n\n patch-ids.c | 10 ++++++++++\n 1 file changed, 10 insertions(+)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 0a4828a..082412a 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -16,6 +16,16 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n \treturn diff_flush_patch_id(options, sha1, diff_header_only);\n }\n \n+/*\n+ * When we cannot load the full patch-id for both commits for whatever\n+ * reason, the function returns -1 (i.e. return error(...)). Despite\n+ * the \"cmp\" in the name of this function, the caller only cares about\n+ * the return value being zero (a and b are equivalent) or non-zero (a\n+ * and b are different), and returning non-zero would keep both in the\n+ * result, even if they actually were equivalent, in order to err on\n+ * the side of safety.  The actual value being negative does not have\n+ * any significance; only that it is non-zero matters.\n+ */\n static int patch_id_cmp(struct patch_id *a,\n \t\t\tstruct patch_id *b,\n \t\t\tstruct diff_options *opt)\n"},{"id":"293081","messageId":"alpine.DEB.2.20.1608041620290.5786@virtualbox","threadId":"42963","inReplyTo":"xmqqziot5jc3.fsf@gitster.mtv.corp.google.com","subject":"Re: [[PATCH v2] 4/4] rebase: avoid computing unnecessary patch IDs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-08-04T14:21:11Z","receivedAt":"2016-08-04T14:21:49Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Wed, 3 Aug 2016, Junio C Hamano wrote:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > I do not think negative (or non-zero) return is an \"abuse\" at all.\n> > It is misleading in the context of the function whose name has \"cmp\"\n> > in it, but that is not the fault of this function, rather, the\n> > breakage is more in the API that calls a function that wants to know\n> > only equality a \"cmp\".  A in-code comment before the function name\n> > may be appropriate:\n> >\n> >         /*\n> >          * hashmap API calls hashmap_cmp_fn, but it only wants\n> >          * \"does the key match the entry?\" with 0 (matches) and\n> >          * non-zero (does not match).\n> >          */\n> >         static int patch_id_match(const struct patch_id *ent,\n> >                                   const struct patch_id *key,\n> >                                   const void *keydata)\n> >         {\n> >                 ...\n> \n> How about this one instead (to be squashed into 4/4)?\n> \n> The updated wording directly addresses the puzzlement I initially\n> felt \"This returns error() which is always negative, so comparing\n> (A, B) would say A < B, while comparing (B, A) would say B < A.\n> Would it cause a problem in the caller?\" while reading the function\n> by being explicit that the sign does not matter.\n\nPlease squash it in. Kevin is on vacation and I am sure he is fine with\nthis change.\n\nThanks,\nDscho\n"}]}