{"thread":{"id":"42849","subject":"[PATCH] Use path comparison for patch ids before the file content","startedAt":"2016-07-14T20:19:08Z","lastAt":"2016-07-15T11:59:50Z","messageCount":3,"participants":["Kevin Willford","Junio C Hamano","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"291473","messageId":"20160714201758.13180-1-kcwillford@gmail.com","threadId":"42849","inReplyTo":null,"subject":"[PATCH] Use path comparison for patch ids before the file content","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2016-07-14T20:17:58Z","receivedAt":"2016-07-14T20:19:08Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"When limiting the list in a revision walk using cherry pick, patch ids are\ncalculated by producing the diff of the content of the files.  This would\nbe more efficent by using a patch id looking at the paths that were\nchanged in the commits and only if all the file changed are the same fall\nback to getting the content of the files in the commits to determine if\nthe commits are the same.\n\nThis change uses a hashmap to store entries with a hash of the patch id\ncalculated by just using the file paths.  The entries constist of the\ncommit and the patch id calculated using file contents which is initially\nempty.  If there are commits that are found in the hashmap it means that\nthe same files were changed in the commits and the file contents need to\nbe checked in order to determine if the commits are truly the same.  The\npatch id that is calcuated based on the file contents is then stored in the\nhashmap entry if needed in later comparisons.  If the commits are determined to be\nthe same the cherry_flag is set on the commit being checked as well as the\ncommit in the hashmap entry saving running though the original list of\ncommits checking a seen flag.  This will speed up a rebase where the\nupstream has many changes but none of them have been pulled into the\ncurrent branch.\n---\n diff.c      |  16 +++++----\n diff.h      |   2 +-\n patch-ids.c | 114 +++++++++++++++++++++++++++++-------------------------------\n patch-ids.h |   7 ++--\n revision.c  |  19 ++--------\n 5 files changed, 73 insertions(+), 85 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex fa78fc1..f38b663 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4449,7 +4449,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 use_path_only)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n@@ -4484,9 +4484,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@@ -4521,6 +4518,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 (use_path_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, sha1_to_hex(p->one->sha1), 40);\n@@ -4541,11 +4545,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 use_path_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, use_path_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 a4d0016..f0262ce 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -4,8 +4,9 @@\n #include \"sha1-lookup.h\"\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+\n+static int ll_commit_patch_id(struct commit *commit, struct diff_options *options,\n+\tunsigned char *sha1, int use_path_only)\n {\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.oid.hash,\n@@ -13,93 +14,90 @@ 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-}\n \n-static const unsigned char *patch_id_access(size_t index, void *table)\n-{\n-\tstruct patch_id **id_table = table;\n-\treturn id_table[index]->patch_id;\n+\n+\treturn diff_flush_patch_id(options, sha1, use_path_only);\n }\n \n-static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)\n+int commit_patch_id(struct commit *commit, struct diff_options *options,\n+\t\t    unsigned char *sha1)\n {\n-\treturn sha1_pos(id, table, nr, patch_id_access);\n+\treturn ll_commit_patch_id(commit, options, sha1, 0);\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, NULL, 0);\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+struct patch_id *has_commit_patch_id(struct commit *commit,\n+\t\t\t\t     struct patch_ids *ids)\n {\n-\tstruct patch_id_bucket *bucket;\n-\tstruct patch_id *ent;\n+\tstruct patch_id *entry;\n \tunsigned char sha1[20];\n-\tint pos;\n+\tunsigned char sha1_2[20];\n+\tstruct patch_id key;\n \n-\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n+\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 1))\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+\n+\tmemset(&key, 0, sizeof(key));\n+\thashmap_entry_init(&key, sha1hash(sha1));\n+\tkey.commit = commit;\n+\n+\tentry = hashmap_get(&ids->patches, &key, NULL);\n+\tif (!entry)\n+\t\treturn NULL;\n+\n+\t/*\n+\t * Since we found a match in the hashmap that means the\n+\t * same files where changed in this commit so we need to\n+\t * get the patch id using the contents of the files to\n+\t * compare with each of the commits in the hash bucket\n+\t * to determine if the commits are truely the same\n+\t */\n+\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 0))\n \t\treturn NULL;\n \n-\tpos = -1 - pos;\n+\tfor (; entry; entry = hashmap_get_next(&ids->patches, entry)) {\n+\t\tif (is_null_sha1(entry->patch_id))\n+\t\t{\n+\t\t\tif (ll_commit_patch_id(entry->commit, &ids->diffopts, sha1_2, 0))\n+\t\t\t\treturn NULL;\n+\n+\t\t\thashcpy(entry->patch_id, sha1_2);\n+\t\t}\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\tif (!hashcmp(entry->patch_id, sha1))\n+\t\t\treturn entry;\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-}\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+\treturn 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-}\n+\tunsigned char sha1[20];\n+\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 1))\n+\t\treturn NULL;\n+\n+\tstruct patch_id *key = xmalloc(sizeof(*key));\n+\tmemset(key, 0, sizeof(*key));\n+\thashmap_entry_init(key, sha1hash(sha1));\n+\tkey->commit = commit;\n+\thashmap_add(&ids->patches, key);\n+\n+\treturn key;\n+}\n\\ No newline at end of file\ndiff --git a/patch-ids.h b/patch-ids.h\nindex eeb56b3..58e55ae 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+\tstruct hashmap_entry ent;\n \tunsigned char patch_id[20];\n-\tchar seen;\n+\tstruct commit *commit;\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,\ndiff --git a/revision.c b/revision.c\nindex edba5b7..f715345 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,23 +873,10 @@ 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 }\n \n-- \n2.9.0.windows.1\n\n"},{"id":"291490","messageId":"xmqqy453ookm.fsf@gitster.mtv.corp.google.com","threadId":"42849","inReplyTo":"20160714201758.13180-1-kcwillford@gmail.com","subject":"Re: [PATCH] Use path comparison for patch ids before the file content","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-14T22:13:45Z","receivedAt":"2016-07-14T22:13:53Z","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> When limiting the list in a revision walk using cherry pick, patch ids are\n> calculated by producing the diff of the content of the files.  This would\n> be more efficent by using a patch id looking at the paths that were\n> changed in the commits and only if all the file changed are the same fall\n> back to getting the content of the files in the commits to determine if\n> the commits are the same.\n\nThe basic idea of this change makes sense.  When we have many\ncommits, but if we can tell that no other commit changes the same\nset of paths as this commit does, we can immediately know that this\ncommit cannot have an equivalent other commit among the rest.  By\nfirst computing a lot cheaper \"hash of touched paths\" for commits,\nand throwing them into separate bins keyed by the \"hash of touched\npaths\", you can narrow the commits whose patch IDs must be compared,\nand if a bin happens to be a singleton, you do not even need to\nproduce any patch ID by running a textual diff.  I like it.\n\nExplaining this as \"hash of touched paths\" is somewhat misleading.\nYour \"use_path_only\" mode actually hashes a lot more than just\npaths.  Because the \"use_path_only\" mode actually hashes the entire\nbasic diff header and not just paths, it can differentiate a commit\nthat adds a file and another commit that modifies the same file, for\nexample.\n\n> ...  This will speed up a rebase where the\n> upstream has many changes but none of them have been pulled into the\n> current branch.\n> ---\n\nMissing sign-off.\n\n>  diff.c      |  16 +++++----\n>  diff.h      |   2 +-\n\nThe changes in the above two files looked OK to me.\nI didn't read the changes to the other three files carefully.\n\n>  patch-ids.c | 114 +++++++++++++++++++++++++++++-------------------------------\n>  patch-ids.h |   7 ++--\n>  revision.c  |  19 ++--------\n>  5 files changed, 73 insertions(+), 85 deletions(-)\n\n>\n> diff --git a/patch-ids.c b/patch-ids.c\n> index a4d0016..f0262ce 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -4,8 +4,9 @@\n> ...\n> +}\n> \\ No newline at end of file\n\nNo newline at end of file.\n\n\nThanks.\n"},{"id":"291528","messageId":"alpine.DEB.2.20.1607151320330.6426@virtualbox","threadId":"42849","inReplyTo":"20160714201758.13180-1-kcwillford@gmail.com","subject":"Re: [PATCH] Use path comparison for patch ids before the file content","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-07-15T11:59:38Z","receivedAt":"2016-07-15T11:59:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Kevin,\n\ncongratulations for your first patch on the Git mailing list!\n\nOn Thu, 14 Jul 2016, Kevin Willford wrote:\n\n> When limiting the list in a revision walk using cherry pick, patch ids are\n> calculated by producing the diff of the content of the files.  This would\n> be more efficent by using a patch id looking at the paths that were\n> changed in the commits and only if all the file changed are the same fall\n> back to getting the content of the files in the commits to determine if\n> the commits are the same.\n> \n> This change uses a hashmap to store entries with a hash of the patch id\n> calculated by just using the file paths.  The entries constist of the\n> commit and the patch id calculated using file contents which is initially\n> empty.  If there are commits that are found in the hashmap it means that\n> the same files were changed in the commits and the file contents need to\n> be checked in order to determine if the commits are truly the same.  The\n> patch id that is calcuated based on the file contents is then stored in the\n> hashmap entry if needed in later comparisons.  If the commits are determined to be\n> the same the cherry_flag is set on the commit being checked as well as the\n> commit in the hashmap entry saving running though the original list of\n> commits checking a seen flag.  This will speed up a rebase where the\n> upstream has many changes but none of them have been pulled into the\n> current branch.\n> ---\n\nHow about pulling out the change that replaces patch-id's ad-hoc hashmap\nwith the struct hashmap solution?\n\nIt would become a two-part patch series, then.\n\nBTW I tried my hand at a different commit message, maybe you want to\ncherry-pick parts of it?\n\n-- snip --\nrebase: avoid computing unnecessary patch IDs\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 \"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 \"header-only\"\npatch IDs are prone to collide with one another, as adjacent commits\nfrequently touch the very same files. Hence we now have to be careful to\nallow multiple hash entries with the same hash.\n-- snap --\n\nAnd as Junio pointed out, please add your Signed-off-by: lines (see\nhttps://github.com/git/git/blob/v2.9.1/Documentation/SubmittingPatches#L239-L291\nfor an explanation).\n\nAnd here are a couple of comments on the code (please read all the way to\nthe end, I cut the parts that I do not address):\n\n> diff --git a/diff.c b/diff.c\n> index fa78fc1..f38b663 100644\n> --- a/diff.c\n> +++ b/diff.c\n> @@ -4449,7 +4449,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 use_path_only)\n\nIf we used `diff_header_only`, we could address Junio's concern about the\nnaming of this parameter.\n\n> diff --git a/patch-ids.c b/patch-ids.c\n> index a4d0016..f0262ce 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -4,8 +4,9 @@\n>  #include \"sha1-lookup.h\"\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> +\n> +static int ll_commit_patch_id(struct commit *commit, struct diff_options *options,\n\nHow about simply changing the signature of the commit_patch_id() function?\nIt's not like Git guarantees any kind of stable API of its libgit.a or\nsomething.\n\n> +int commit_patch_id(struct commit *commit, struct diff_options *options,\n> +\t\t    unsigned char *sha1)\n>  {\n> -\treturn sha1_pos(id, table, nr, patch_id_access);\n> +\treturn ll_commit_patch_id(commit, options, sha1, 0);\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\nThe idea of the original code was to get as close to 4kB for the initial\n(and probably final) hashmap. I do not think we can, or have to, achieve\nthe same with struct hashmap. But we should use a larger initial size than\n64 (maybe 128? I would actually go for 256, even if that roughly doubles\nthe initial hashmap size) by passing an explicit value to hashmap_init():\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, NULL, 0);\n\nLike here (just replace the 0 by 128 or 256).\n\nAlso, since the \"header-only\" patch ID makes hash collisions much more\nlikely (I, for one, frequently have patches in the same patch series that\ntouch the very same set of files), we need to provide a hashmap_cmp_fn.\n\nFor the hashmap population, I would suggest a function like this:\n\nstatic int patch_id_cmp(const struct patch_id *a, constr struct patch_id *b,\n\tconst void *keydata)\n{\n\treturn hashcmp(a->commit, b->commit);\n}\n\nThis will guarantee that all the commits will be added to the hash map,\neven if some \"header-only\" patch IDs collide.\n\n(If you go with my suggestion to split out the conversion to the struct\nhashmap in a preparatory patch, then you probably want to use\nhashcmp(a->patch_id, b->patch_id) in the first patch, and then replace it\nwith the version above in the second patch.)\n\nOf course, we will need to change the cmpfn after populating the hashmap.\nSee below for my thoughts on that:\n\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> +struct patch_id *has_commit_patch_id(struct commit *commit,\n> +\t\t\t\t     struct patch_ids *ids)\n>  {\n> -\tstruct patch_id_bucket *bucket;\n> -\tstruct patch_id *ent;\n> +\tstruct patch_id *entry;\n>  \tunsigned char sha1[20];\n> -\tint pos;\n> +\tunsigned char sha1_2[20];\n> +\tstruct patch_id key;\n>  \n> -\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n> +\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 1))\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> +\n> +\tmemset(&key, 0, sizeof(key));\n> +\thashmap_entry_init(&key, sha1hash(sha1));\n> +\tkey.commit = commit;\n> +\n> +\tentry = hashmap_get(&ids->patches, &key, NULL);\n> +\tif (!entry)\n> +\t\treturn NULL;\n> +\n> +\t/*\n> +\t * Since we found a match in the hashmap that means the\n> +\t * same files where changed in this commit so we need to\n> +\t * get the patch id using the contents of the files to\n> +\t * compare with each of the commits in the hash bucket\n> +\t * to determine if the commits are truely the same\n> +\t */\n> +\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 0))\n>  \t\treturn NULL;\n>  \n> -\tpos = -1 - pos;\n> +\tfor (; entry; entry = hashmap_get_next(&ids->patches, entry)) {\n> +\t\tif (is_null_sha1(entry->patch_id))\n> +\t\t{\n> +\t\t\tif (ll_commit_patch_id(entry->commit, &ids->diffopts, sha1_2, 0))\n> +\t\t\t\treturn NULL;\n> +\n> +\t\t\thashcpy(entry->patch_id, sha1_2);\n> +\t\t}\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\tif (!hashcmp(entry->patch_id, sha1))\n> +\t\t\treturn entry;\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> -}\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> +\treturn NULL;\n>  }\n\nIf you go with my suggestion of patch_id_cmp() above, you will have to\nchange the cmpfn after the hashmap-populating phase.\n\nHappily, we know that this phase is over as soon as has_commit_patch_id()\nis called, and it does not hurt to re-set the cmpfn multiple times.\n\nEven better: if you re-set the cmpfn, you can now use something like this:\n\nstatic int full_patch_id_cmp(const struct patch_id *a,\n    const struct patch_id *b, const diff_options *opt)\n{\n    if (is_null_sha1(a->patch_id) &&\n      commit_patch_id(a->commit, opt, a->patch_id, 0))\n        return error(\"Could not get patch ID for %s\",\n            oid_to_hex(&a->commit->object.oid));\n    if (is_null_sha1(b->patch_id) &&\n      commit_patch_id(b->commit, opt, b->patch_id, 0))\n        return error(\"Could not get patch ID for %s\",\n            oid_to_hex(&b->commit->object.oid));\n    return hashcmp(a->patch_id, b->patch_id);\n}\n\nWith this cmpfn, your has_commit_patch_id() would become something like\nthis:\n\nstruct patch_id *has_commit_patch_id(struct commit *commit,\n\t\t\t\t     struct patch_ids *ids)\n{\n\tunsigned char sha1[20];\n\tstruct patch_id key;\n\n\tif (commit_patch_id(commit, &ids->diffopt, sha1, 1))\n\t\treturn NULL;\n\n\tids->patches.cmpfn = full_patch_id_cmp;\n\tmemset(&key, 0, sizeof(key));\n\tkey.hash = sha1hash(sha1);\n\tkey.commit = commit;\n\treturn hashmap_get(&ids->patches, &key, &ids->diffopt);\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> -}\n> +\tunsigned char sha1[20];\n> +\tif (ll_commit_patch_id(commit, &ids->diffopts, sha1, 1))\n> +\t\treturn NULL;\n> +\n> +\tstruct patch_id *key = xmalloc(sizeof(*key));\n\nGit's source code does not allow declarations after statements, therefore\n`struct patch_id *key;` needs to come before the if().\n\n> +\tmemset(key, 0, sizeof(*key));\n\nSince you want to initialize it to zeroes anyway, how about\n\n\tkey = xcalloc(1, sizeof(*key));\n\n> @@ -873,23 +873,10 @@ 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\nI really like this simplification.\n\n>  \t}\n> -\n>  \tfree_patch_ids(&ids);\n\nLet's keep this empty line here; There is no need to change this existing\ncode.\n\nBTW I could imagine splitting out even just the feature to compute\nheader-only patch IDs, and keep the changes to make use of it for a third\npatch in the series.\n\nI also think that this patch series could use a test that verifies that we\nno longer generate unneeded diffs. Maybe by rebasing a commit on top of an\ncommit touching a different file, after corrupting the blob of the latter\none? Let me give it a try.\n\nCiao,\nJohannes\n"}]}