{"thread":{"id":"54970","subject":"rev-list with multiple commits sharing same patch-id","startedAt":"2021-01-09T16:25:39Z","lastAt":"2021-01-13T20:34:49Z","messageCount":15,"participants":["Arnaud Morin","Christian Couder","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"413916","messageId":"20210109162440.GM31701@sync","threadId":"54970","inReplyTo":null,"subject":"rev-list with multiple commits sharing same patch-id","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-09T16:24:40Z","receivedAt":"2021-01-09T16:25:39Z","isPatch":false,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"Hey all,\n\nI am struggling with a rev-list command, hope someone can give me a\nclue on what is going on.\n\nI have 2 branches:\n$ git branch\n B\n* master\n\nCurrently on master, there is not diff against B:\n$ git diff\n(empty)\n\nThe commits in B are cherry-picked from master.\nHere is the graph:\n$ git log --graph --oneline --all\n* ae2e3c4 (origin/B, B) remove line2 and add line4 (bis)\n* a7a0339 remove line4\n* caa4aad restore line2\n* d7dc596 remove line2 add line4\n* 44bcfd4 add line3\n* e372641 b\n| * dbf86d8 (HEAD -> master, origin/master) remove line2 and add line4 (bis)\n| * 4017282 remove line4\n| * 0f2a449 restore line2\n| * 8969d3f remove line2 add line4\n| * e73b420 add line3\n| * fe5a75a b\n|/ \n* 6192505 a\n* b4089e1 init\n\n\nHowever, when using git rev-list to perform a symmetric difference, git\nis giving me a commit ID:\n$ git rev-list --left-right --cherry-pick B...master\n>dbf86d8aafc897a25a3093139b4237a62395041e\n\nNote that this commit is not empty\n$ git show dbf86d8aafc897a25a3093139b4237a62395041e --stat\ncommit dbf86d8aafc897a25a3093139b4237a62395041e (origin/master, master)\nAuthor: Arnaud Morin \nDate: Sat Jan 9 10:30:10 2021 +0100\n\n remove line2 and add line4 (bis)\n\n a | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\n\n\nSo, from git rev-list perspective, there is a diff.\n\nAfter digging a little bit, the thing is that this commit is having the\nfollowing patch-id:\n$ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id\n20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n\nWhich is also already existing in an other commit:\n$ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done\n20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n\nSo, is it normal that rev-list is not able to figure out that a commit\nis existing in both branch when 2 commits share the same patch-id?\n\nIs there any way to prevent rev-list from showing this commit?\n\nThanks for your help.\n\n\nPS. I have uploaded my test repo here:\nhttps://gitlab.com/arnaudmorin/git-rev-list\n\n\n-- \nArnaud Morin\n\n"},{"id":"414011","messageId":"20210111075905.GA32482@sync","threadId":"54970","inReplyTo":"20210109162440.GM31701@sync","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-11T07:59:05Z","receivedAt":"2021-01-11T08:00:05Z","isPatch":false,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"Sorry, forgot to mention 2 things:\n- I am using latest stable git version (2.30)\n- I my previous mail, my git diff was against branch B:\n$ git diff B\n(empty)\n\nThanks\n\n-- \nArnaud Morin\n\nOn 09.01.21 - 16:24, Arnaud Morin wrote:\n> Hey all,\n> \n> I am struggling with a rev-list command, hope someone can give me a\n> clue on what is going on.\n> \n> I have 2 branches:\n> $ git branch\n> B\n> * master\n> \n> Currently on master, there is not diff against B:\n> $ git diff\n> (empty)\n> \n> The commits in B are cherry-picked from master.\n> Here is the graph:\n> $ git log --graph --oneline --all\n> * ae2e3c4 (origin/B, B) remove line2 and add line4 (bis)\n> * a7a0339 remove line4\n> * caa4aad restore line2\n> * d7dc596 remove line2 add line4\n> * 44bcfd4 add line3\n> * e372641 b\n> | * dbf86d8 (HEAD -> master, origin/master) remove line2 and add line4 (bis)\n> | * 4017282 remove line4\n> | * 0f2a449 restore line2\n> | * 8969d3f remove line2 add line4\n> | * e73b420 add line3\n> | * fe5a75a b\n> |/ \n> * 6192505 a\n> * b4089e1 init\n> \n> \n> However, when using git rev-list to perform a symmetric difference, git\n> is giving me a commit ID:\n> $ git rev-list --left-right --cherry-pick B...master\n> >dbf86d8aafc897a25a3093139b4237a62395041e\n> \n> Note that this commit is not empty\n> $ git show dbf86d8aafc897a25a3093139b4237a62395041e --stat\n> commit dbf86d8aafc897a25a3093139b4237a62395041e (origin/master, master)\n> Author: Arnaud Morin \n> Date: Sat Jan 9 10:30:10 2021 +0100\n> \n> remove line2 and add line4 (bis)\n> \n> a | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> \n> \n> So, from git rev-list perspective, there is a diff.\n> \n> After digging a little bit, the thing is that this commit is having the\n> following patch-id:\n> $ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> \n> Which is also already existing in an other commit:\n> $ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n> \n> So, is it normal that rev-list is not able to figure out that a commit\n> is existing in both branch when 2 commits share the same patch-id?\n> \n> Is there any way to prevent rev-list from showing this commit?\n> \n> Thanks for your help.\n> \n> \n> PS. I have uploaded my test repo here:\n> https://gitlab.com/arnaudmorin/git-rev-list\n> \n> \n> -- \n> Arnaud Morin\n> \n"},{"id":"414024","messageId":"CAP8UFD3qt4xr4S1BgjPU-vm4qsb=+1JWc=LR_p1CUzTKaAcAoA@mail.gmail.com","threadId":"54970","inReplyTo":"20210109162440.GM31701@sync","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2021-01-11T09:54:18Z","receivedAt":"2021-01-11T09:55:12Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi,\n\nOn Sat, Jan 9, 2021 at 5:29 PM Arnaud Morin wrote:\n\n> I am struggling with a rev-list command, hope someone can give me a\n> clue on what is going on.\n\n[...]\n\n> However, when using git rev-list to perform a symmetric difference, git\n> is giving me a commit ID:\n> $ git rev-list --left-right --cherry-pick B...master\n> >dbf86d8aafc897a25a3093139b4237a62395041e\n\nIt looks like a bug. You might want to check the following test file\nand let us know if a similar case is tested in it, or not:\n\nt6007-rev-list-cherry-pick-file.sh\n\nIf not, it might be a good idea to add one using 'test_expect_failure'\ninstead of 'test_expect_success' to document the failure.\n\nThanks,\nChristian.\n\n\n> Note that this commit is not empty\n> $ git show dbf86d8aafc897a25a3093139b4237a62395041e --stat\n> commit dbf86d8aafc897a25a3093139b4237a62395041e (origin/master, master)\n> Author: Arnaud Morin \n> Date: Sat Jan 9 10:30:10 2021 +0100\n>\n> remove line2 and add line4 (bis)\n>\n> a | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n>\n>\n> So, from git rev-list perspective, there is a diff.\n>\n> After digging a little bit, the thing is that this commit is having the\n> following patch-id:\n> $ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n>\n> Which is also already existing in an other commit:\n> $ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n>\n> So, is it normal that rev-list is not able to figure out that a commit\n> is existing in both branch when 2 commits share the same patch-id?\n>\n> Is there any way to prevent rev-list from showing this commit?\n>\n> Thanks for your help.\n>\n>\n> PS. I have uploaded my test repo here:\n> https://gitlab.com/arnaudmorin/git-rev-list\n>\n>\n> --\n> Arnaud Morin\n>\n"},{"id":"414065","messageId":"20210111182501.GB32482@sync","threadId":"54970","inReplyTo":"CAP8UFD3qt4xr4S1BgjPU-vm4qsb=+1JWc=LR_p1CUzTKaAcAoA@mail.gmail.com","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-11T18:25:01Z","receivedAt":"2021-01-11T18:26:01Z","isPatch":false,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"Hi,\n\nThanks for the link to the test file.\n\nI patched the test file to add this new case (where the same patch-id is\nduplicated in the tree).\nThis patch can be find in [1]\nI had to patch two existing tests to make them work again.\nI also added a new test with this new test-case (two identical patch-id\nin the same tree.)\nNote that I still have one test (outside my new one) which is failing:\n\nnot ok 10 - name-rev --exclude excludes matched patterns\n\nI dont know why yet.\n\nMoreover, I am willing to help fixing the code.\nI have the feeling that a patch needs to be done in revision.c, maybe\nin static void cherry_pick_list?\n\nIf you have any clue to help me?\n\nThanks.\n\n\n[1] https://github.com/arnaudmorin/git/pull/1\n\n\n-- \nArnaud Morin\n\nOn 11.01.21 - 10:54, Christian Couder wrote:\n> Hi,\n> \n> On Sat, Jan 9, 2021 at 5:29 PM Arnaud Morin wrote:\n> \n> > I am struggling with a rev-list command, hope someone can give me a\n> > clue on what is going on.\n> \n> [...]\n> \n> > However, when using git rev-list to perform a symmetric difference, git\n> > is giving me a commit ID:\n> > $ git rev-list --left-right --cherry-pick B...master\n> > >dbf86d8aafc897a25a3093139b4237a62395041e\n> \n> It looks like a bug. You might want to check the following test file\n> and let us know if a similar case is tested in it, or not:\n> \n> t6007-rev-list-cherry-pick-file.sh\n> \n> If not, it might be a good idea to add one using 'test_expect_failure'\n> instead of 'test_expect_success' to document the failure.\n> \n> Thanks,\n> Christian.\n> \n> \n> > Note that this commit is not empty\n> > $ git show dbf86d8aafc897a25a3093139b4237a62395041e --stat\n> > commit dbf86d8aafc897a25a3093139b4237a62395041e (origin/master, master)\n> > Author: Arnaud Morin \n> > Date: Sat Jan 9 10:30:10 2021 +0100\n> >\n> > remove line2 and add line4 (bis)\n> >\n> > a | 2 +-\n> > 1 file changed, 1 insertion(+), 1 deletion(-)\n> >\n> >\n> >\n> > So, from git rev-list perspective, there is a diff.\n> >\n> > After digging a little bit, the thing is that this commit is having the\n> > following patch-id:\n> > $ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id\n> > 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> >\n> > Which is also already existing in an other commit:\n> > $ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done\n> > 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> > 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n> >\n> > So, is it normal that rev-list is not able to figure out that a commit\n> > is existing in both branch when 2 commits share the same patch-id?\n> >\n> > Is there any way to prevent rev-list from showing this commit?\n> >\n> > Thanks for your help.\n> >\n> >\n> > PS. I have uploaded my test repo here:\n> > https://gitlab.com/arnaudmorin/git-rev-list\n> >\n> >\n> > --\n> > Arnaud Morin\n> >\n"},{"id":"414153","messageId":"X/2vgbnxWSmst5yB@coredump.intra.peff.net","threadId":"54970","inReplyTo":"20210109162440.GM31701@sync","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-12T14:17:37Z","receivedAt":"2021-01-12T14:18:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jan 09, 2021 at 04:24:40PM +0000, Arnaud Morin wrote:\n\n> After digging a little bit, the thing is that this commit is having the\n> following patch-id:\n> $ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> \n> Which is also already existing in an other commit:\n> $ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n> 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n\nA slight nit first. Those two commits have the same patch-id, but in\nyour graph they are on the same branch (\"master\", not \"B\"):\n\n> The commits in B are cherry-picked from master.\n> Here is the graph:\n> $ git log --graph --oneline --all\n> * ae2e3c4 (origin/B, B) remove line2 and add line4 (bis)\n> * a7a0339 remove line4\n> * caa4aad restore line2\n> * d7dc596 remove line2 add line4\n> * 44bcfd4 add line3\n> * e372641 b\n> | * dbf86d8 (HEAD -> master, origin/master) remove line2 and add line4 (bis)\n> | * 4017282 remove line4\n> | * 0f2a449 restore line2\n> | * 8969d3f remove line2 add line4\n> | * e73b420 add line3\n> | * fe5a75a b\n> |/ \n> * 6192505 a\n> * b4089e1 init\n\nAnd --cherry-pick is only looking for matches between the two sides of\nthe symmetric difference.\n\nHowever, I think that patch-id does exist on the other side (it appears\nagain twice in fact, which is not surprising):\n\n $ git rev-list --all | git diff-tree --stdin -p | git patch-id | grep 20f4ace68e80\n 20f4ace68e80a751b07d78a27c94e83d6c5314bc ae2e3c4754f53440cc4612d35f80d795a695c862\n 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e\n 20f4ace68e80a751b07d78a27c94e83d6c5314bc d7dc596fcc34662cba35363febc846bfcab1e4be\n 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027\n\nSo the entries should be suppressed from both sides.\n\nIt looks like this was broken in v2.10.0, via dfb7a1b4d0 (patch-ids:\nstop using a hand-rolled hashmap implementation, 2016-07-29).\n\nI think the issue is that it is allowing duplicate entries in the\nhashmap. The algorithm is something like:\n\n - iterate over left-hand commits, inserting patch-id for each into\n hashmap\n\n - iterate over right-hand commits, seeing if any are present in\n hashmap. If so, we exclude the commit _and_ mark the patch-id as\n \"seen\"\n\n - iterate again over left-hand commits, omitting any whose patch-ids\n are marked as \"seen\"\n\nSo if two commits on the left-hand side have the same patch-id, if we\ninsert two entries into the hashmap, then only one of them is going to\nget its \"seen\" flag marked in the middle step.\n\n-Peff\n"},{"id":"414154","messageId":"X/28IXBpse2dNZQH@coredump.intra.peff.net","threadId":"54970","inReplyTo":"X/2vgbnxWSmst5yB@coredump.intra.peff.net","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-12T15:11:29Z","receivedAt":"2021-01-12T15:12:14Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 12, 2021 at 09:17:37AM -0500, Jeff King wrote:\n\n> It looks like this was broken in v2.10.0, via dfb7a1b4d0 (patch-ids:\n> stop using a hand-rolled hashmap implementation, 2016-07-29).\n> \n> I think the issue is that it is allowing duplicate entries in the\n> hashmap. The algorithm is something like:\n> \n> - iterate over left-hand commits, inserting patch-id for each into\n> hashmap\n> \n> - iterate over right-hand commits, seeing if any are present in\n> hashmap. If so, we exclude the commit _and_ mark the patch-id as\n> \"seen\"\n> \n> - iterate again over left-hand commits, omitting any whose patch-ids\n> are marked as \"seen\"\n> \n> So if two commits on the left-hand side have the same patch-id, if we\n> insert two entries into the hashmap, then only one of them is going to\n> get its \"seen\" flag marked in the middle step.\n\nYeah, that's definitely it. Here's what the fix would look like directly\non top of dfb7a1b4d0:\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex db31fa647a..a8ed4f0872 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -66,12 +66,24 @@ struct patch_id *add_commit_patch_id(struct commit *commit,\n \t\t\t\t struct patch_ids *ids)\n {\n \tstruct patch_id *key = xcalloc(1, sizeof(*key));\n+\tstruct patch_id *old;\n \n \tif (init_patch_id_entry(key, commit, ids)) {\n \t\tfree(key);\n \t\treturn NULL;\n \t}\n \n+\t/*\n+\t * Don't allow duplicates. Note that we can't use hashmap_put here; we\n+\t * must retain the _old_ struct, because some commit->util is pointing\n+\t * to it.\n+\t */\n+\told = hashmap_get(&ids->patches, key, ids);\n+\tif (old) {\n+\t\tfree(key);\n+\t\treturn old;\n+\t}\n+\n \thashmap_add(&ids->patches, key);\n \treturn key;\n }\ndiff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\nindex 28d4f6b259..0c5f1dcc54 100755\n--- a/t/t6007-rev-list-cherry-pick-file.sh\n+++ b/t/t6007-rev-list-cherry-pick-file.sh\n@@ -207,4 +207,16 @@ test_expect_success '--count --left-right' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success '--cherry-pick with duplicates on each side' '\n+\tgit checkout -b dup-orig &&\n+\ttest_commit dup-base &&\n+\tgit revert dup-base &&\n+\tgit cherry-pick dup-base &&\n+\tgit checkout -b dup-side HEAD~3 &&\n+\ttest_tick &&\n+\tgit cherry-pick -3 dup-orig &&\n+\tgit rev-list --cherry-pick dup-orig...dup-side >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n test_done\n\n\nUnfortunately we can't do the same thing now. The \"seen\" flag went away\nin 683f17ec44 (patch-ids: replace the seen indicator with a commit\npointer, 2016-07-29), in favor of having each patch_id struct point to a\n\"struct commit\". We could revert that, or turn that pointer into a list,\nbut it gets worse. Later, b3dfeebb92 (rebase: avoid computing\nunnecessary patch IDs, 2016-07-29) built on that by lazily computing the\npatch-ids. So each patch_id struct must point to exactly one commit!\n\nWe'll have to either:\n\n - split them apart into two structs at the time of the lazy computation\n\nor\n\n - accept having duplicate patch_ids, but on lookup make sure we find\n _all_ matches, not just the first one.\n\nHmm, that last one might not be too bad, since we have\nhashmap_get_next() (it does mean iterating over a chained bucket\nlinearly, but that's already the worst-case for a hash lookup).\n\n-Peff\n"},{"id":"414166","messageId":"20210112153438.GC32482@sync","threadId":"54970","inReplyTo":"X/28IXBpse2dNZQH@coredump.intra.peff.net","subject":"Re: rev-list with multiple commits sharing same patch-id","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-12T15:34:38Z","receivedAt":"2021-01-12T15:35:24Z","isPatch":false,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"So instead of:\nid = has_commit_patch_id(commit, &ids);\n\nWe should use some sort of iterator, in order to call:\nid->commit->object.flags |= cherry_flag;\n\nfor all commits which are related to this patch?\n\n\n\n-- \nArnaud Morin\n\nOn 12.01.21 - 10:11, Jeff King wrote:\n> On Tue, Jan 12, 2021 at 09:17:37AM -0500, Jeff King wrote:\n> \n> > It looks like this was broken in v2.10.0, via dfb7a1b4d0 (patch-ids:\n> > stop using a hand-rolled hashmap implementation, 2016-07-29).\n> > \n> > I think the issue is that it is allowing duplicate entries in the\n> > hashmap. The algorithm is something like:\n> > \n> > - iterate over left-hand commits, inserting patch-id for each into\n> > hashmap\n> > \n> > - iterate over right-hand commits, seeing if any are present in\n> > hashmap. If so, we exclude the commit _and_ mark the patch-id as\n> > \"seen\"\n> > \n> > - iterate again over left-hand commits, omitting any whose patch-ids\n> > are marked as \"seen\"\n> > \n> > So if two commits on the left-hand side have the same patch-id, if we\n> > insert two entries into the hashmap, then only one of them is going to\n> > get its \"seen\" flag marked in the middle step.\n> \n> Yeah, that's definitely it. Here's what the fix would look like directly\n> on top of dfb7a1b4d0:\n> \n> diff --git a/patch-ids.c b/patch-ids.c\n> index db31fa647a..a8ed4f0872 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -66,12 +66,24 @@ struct patch_id *add_commit_patch_id(struct commit *commit,\n> \t\t\t\t struct patch_ids *ids)\n> {\n> \tstruct patch_id *key = xcalloc(1, sizeof(*key));\n> +\tstruct patch_id *old;\n> \n> \tif (init_patch_id_entry(key, commit, ids)) {\n> \t\tfree(key);\n> \t\treturn NULL;\n> \t}\n> \n> +\t/*\n> +\t * Don't allow duplicates. Note that we can't use hashmap_put here; we\n> +\t * must retain the _old_ struct, because some commit->util is pointing\n> +\t * to it.\n> +\t */\n> +\told = hashmap_get(&ids->patches, key, ids);\n> +\tif (old) {\n> +\t\tfree(key);\n> +\t\treturn old;\n> +\t}\n> +\n> \thashmap_add(&ids->patches, key);\n> \treturn key;\n> }\n> diff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\n> index 28d4f6b259..0c5f1dcc54 100755\n> --- a/t/t6007-rev-list-cherry-pick-file.sh\n> +++ b/t/t6007-rev-list-cherry-pick-file.sh\n> @@ -207,4 +207,16 @@ test_expect_success '--count --left-right' '\n> \ttest_cmp expect actual\n> '\n> \n> +test_expect_success '--cherry-pick with duplicates on each side' '\n> +\tgit checkout -b dup-orig &&\n> +\ttest_commit dup-base &&\n> +\tgit revert dup-base &&\n> +\tgit cherry-pick dup-base &&\n> +\tgit checkout -b dup-side HEAD~3 &&\n> +\ttest_tick &&\n> +\tgit cherry-pick -3 dup-orig &&\n> +\tgit rev-list --cherry-pick dup-orig...dup-side >actual &&\n> +\ttest_must_be_empty actual\n> +'\n> +\n> test_done\n> \n> \n> Unfortunately we can't do the same thing now. The \"seen\" flag went away\n> in 683f17ec44 (patch-ids: replace the seen indicator with a commit\n> pointer, 2016-07-29), in favor of having each patch_id struct point to a\n> \"struct commit\". We could revert that, or turn that pointer into a list,\n> but it gets worse. Later, b3dfeebb92 (rebase: avoid computing\n> unnecessary patch IDs, 2016-07-29) built on that by lazily computing the\n> patch-ids. So each patch_id struct must point to exactly one commit!\n> \n> We'll have to either:\n> \n> - split them apart into two structs at the time of the lazy computation\n> \n> or\n> \n> - accept having duplicate patch_ids, but on lookup make sure we find\n> _all_ matches, not just the first one.\n> \n> Hmm, that last one might not be too bad, since we have\n> hashmap_get_next() (it does mean iterating over a chained bucket\n> linearly, but that's already the worst-case for a hash lookup).\n> \n> -Peff\n"},{"id":"414167","messageId":"X/3FwNPHqZqY+hv0@coredump.intra.peff.net","threadId":"54970","inReplyTo":"20210112153438.GC32482@sync","subject":"[PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-12T15:52:32Z","receivedAt":"2021-01-12T15:53:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 12, 2021 at 03:34:38PM +0000, Arnaud Morin wrote:\n\n> So instead of:\n> id = has_commit_patch_id(commit, &ids);\n> \n> We should use some sort of iterator, in order to call:\n> id->commit->object.flags |= cherry_flag;\n> \n> for all commits which are related to this patch?\n\nYep, exactly.\n\nHere it is as a patch. :)\n\n-- >8 --\nSubject: [PATCH] patch-ids: handle duplicate hashmap entries\n\nThis fixes a bug introduced in dfb7a1b4d0 (patch-ids: stop using a\nhand-rolled hashmap implementation, 2016-07-29) in which\n\n git rev-list --cherry-pick A...B\n\nwill fail to suppress commits reachable from A even if a commit with\nmatching patch-id appears in B.\n\nAround the time of that commit, the algorithm for \"--cherry-pick\" looked\nsomething like this:\n\n 0. Traverse all of the commits, marking them as being on the left or\n right side of the symmetric difference.\n\n 1. Iterate over the left-hand commits, inserting a patch-id struct for\n each into a hashmap, and pointing commit->util to the patch-id\n struct.\n\n 2. Iterate over the right-hand commits, checking which are present in\n the hashmap. If so, we exclude the commit from the output _and_ we\n mark the patch-id as \"seen\".\n\n 3. Iterate again over the left-hand commits, checking whether\n commit->util->seen is set; if so, exclude them from the output.\n\nAt the end, we'll have eliminated commits from both sides that have a\nmatching patch-id on the other side. But there's a subtle assumption\nhere: for any given patch-id, we must have exactly one struct\nrepresenting it. If two commits from A both have the same patch-id and\nwe allow duplicates in the hashmap, then we run into a problem:\n\n a. In step 1, we insert two patch-id structs into the hashmap.\n\n b. In step 2, our lookups will find only one of these structs, so only\n one \"seen\" flag is marked.\n\n c. In step 3, one of the commits in A will have its commit->util->seen\n set, but the other will not. We'll erroneously output the latter.\n\nPrior to dfb7a1b4d0, our hashmap did not allow duplicates. Afterwards,\nit used hashmap_add(), which explicitly does allow duplicates.\n\nAt that point, the solution would have been easy: when we are about to\nadd a duplicate, skip doing so and return the existing entry which\nmatches. But it gets more complicated.\n\nIn 683f17ec44 (patch-ids: replace the seen indicator with a commit\npointer, 2016-07-29), our step 3 goes away entirely. Instead, in step 2,\nwhen the right-hand side finds a matching patch_id from the left-hand\nside, we can directly mark the left-hand patch_id->commit to be omitted.\nSolving that would be easy, too; there's a one-to-many relationship of\npatch-ids to commits, so we just need to keep a list.\n\nBut there's more. Commit b3dfeebb92 (rebase: avoid computing unnecessary\npatch IDs, 2016-07-29) built on that by lazily computing the full\npatch-ids. So we don't even know when adding to the hashmap whether two\ncommits truly have the same id. We'd have to tentatively assign them a\nlist, and then possibly split them apart (possibly into N new structs)\nat the moment we compute the real patch-ids. This could work, but it's\ncomplicated and error-prone.\n\nInstead, let's accept that we may store duplicates, and teach the lookup\nside to be more clever. Rather than asking for a single matching\npatch-id, it will need to iterate over all matching patch-ids. This does\nmean examining every entry in a single hash bucket, but the worst-case\nfor a hash lookup was already doing that.\n\nWe'll keep the hashmap details out of the caller by providing a simple\niteration interface. We can retain the simple has_commit_patch_id()\ninterface for the other callers, but we'll simplify its return value\ninto an integer, rather than returning the patch_id struct. That way\nthey won't be tempted to look at the \"commit\" field of the return value\nwithout iterating.\n\nReported-by: Arnaud Morin \nSigned-off-by: Jeff King \n---\n patch-ids.c | 14 +++++++++++++-\n patch-ids.h | 20 +++++++++++++++++++-\n revision.c | 6 ++++--\n t/t6007-rev-list-cherry-pick-file.sh | 12 ++++++++++++\n 4 files changed, 48 insertions(+), 4 deletions(-)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex 21973e4933..f51021a0cb 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -89,7 +89,7 @@ static int init_patch_id_entry(struct patch_id *patch,\n \treturn 0;\n }\n \n-struct patch_id *has_commit_patch_id(struct commit *commit,\n+struct patch_id *patch_id_iter_first(struct commit *commit,\n \t\t\t\t struct patch_ids *ids)\n {\n \tstruct patch_id patch;\n@@ -104,6 +104,18 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n \treturn hashmap_get_entry(&ids->patches, &patch, ent, NULL);\n }\n \n+struct patch_id *patch_id_iter_next(struct patch_id *cur,\n+\t\t\t\t struct patch_ids *ids)\n+{\n+\treturn hashmap_get_next_entry(&ids->patches, cur, ent);\n+}\n+\n+int has_commit_patch_id(struct commit *commit,\n+\t\t\tstruct patch_ids *ids)\n+{\n+\treturn !!patch_id_iter_first(commit, ids);\n+}\n+\n struct patch_id *add_commit_patch_id(struct commit *commit,\n \t\t\t\t struct patch_ids *ids)\n {\ndiff --git a/patch-ids.h b/patch-ids.h\nindex 03bb04e707..ab6c6a6804 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -23,7 +23,25 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n \t\t struct object_id *oid, int, int);\n int init_patch_ids(struct repository *, struct patch_ids *);\n int free_patch_ids(struct patch_ids *);\n+\n+/* Add a patch_id for a single commit to the set. */\n struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n-struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\n+\n+/* Returns true if the patch-id of \"commit\" is present in the set. */\n+int has_commit_patch_id(struct commit *commit, struct patch_ids *);\n+\n+/*\n+ * Iterate over all commits in the set whose patch id matches that of\n+ * \"commit\", like:\n+ *\n+ * struct patch_id *cur;\n+ * for (cur = patch_id_iter_first(commit, ids);\n+ * cur;\n+ * cur = patch_id_iter_next(cur, ids) {\n+ * ... look at cur->commit\n+ * }\n+ */\n+struct patch_id *patch_id_iter_first(struct commit *commit, struct patch_ids *);\n+struct patch_id *patch_id_iter_next(struct patch_id *cur, struct patch_ids *);\n \n #endif /* PATCH_IDS_H */\ndiff --git a/revision.c b/revision.c\nindex 9dff845bed..7ec9b634e3 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1241,12 +1241,14 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n \t\t/*\n \t\t * Have we seen the same patch id?\n \t\t */\n-\t\tid = has_commit_patch_id(commit, &ids);\n+\t\tid = patch_id_iter_first(commit, &ids);\n \t\tif (!id)\n \t\t\tcontinue;\n \n \t\tcommit->object.flags |= cherry_flag;\n-\t\tid->commit->object.flags |= cherry_flag;\n+\t\tdo {\n+\t\t\tid->commit->object.flags |= cherry_flag;\n+\t\t} while ((id = patch_id_iter_next(id, &ids)));\n \t}\n \n \tfree_patch_ids(&ids);\ndiff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\nindex f0268372d2..8bf5ae23c2 100755\n--- a/t/t6007-rev-list-cherry-pick-file.sh\n+++ b/t/t6007-rev-list-cherry-pick-file.sh\n@@ -245,6 +245,18 @@ test_expect_success '--count --left-right' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success '--cherry-pick with duplicates on each side' '\n+\tgit checkout -b dup-orig &&\n+\ttest_commit dup-base &&\n+\tgit revert dup-base &&\n+\tgit cherry-pick dup-base &&\n+\tgit checkout -b dup-side HEAD~3 &&\n+\ttest_tick &&\n+\tgit cherry-pick -3 dup-orig &&\n+\tgit rev-list --cherry-pick dup-orig...dup-side >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n # Corrupt the object store deliberately to make sure\n # the object is not even checked for its existence.\n remove_loose_object () {\n-- \n2.30.0.455.gdab6b73766\n\n"},{"id":"414168","messageId":"20210112162425.GD32482@sync","threadId":"54970","inReplyTo":"X/3FwNPHqZqY+hv0@coredump.intra.peff.net","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-12T16:24:25Z","receivedAt":"2021-01-12T16:25:10Z","isPatch":true,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"YAY!\n\nThanks a lot :)\n\n-- \nArnaud Morin\n\nOn 12.01.21 - 10:52, Jeff King wrote:\n> On Tue, Jan 12, 2021 at 03:34:38PM +0000, Arnaud Morin wrote:\n> \n> > So instead of:\n> > id = has_commit_patch_id(commit, &ids);\n> > \n> > We should use some sort of iterator, in order to call:\n> > id->commit->object.flags |= cherry_flag;\n> > \n> > for all commits which are related to this patch?\n> \n> Yep, exactly.\n> \n> Here it is as a patch. :)\n> \n> -- >8 --\n> Subject: [PATCH] patch-ids: handle duplicate hashmap entries\n> \n> This fixes a bug introduced in dfb7a1b4d0 (patch-ids: stop using a\n> hand-rolled hashmap implementation, 2016-07-29) in which\n> \n> git rev-list --cherry-pick A...B\n> \n> will fail to suppress commits reachable from A even if a commit with\n> matching patch-id appears in B.\n> \n> Around the time of that commit, the algorithm for \"--cherry-pick\" looked\n> something like this:\n> \n> 0. Traverse all of the commits, marking them as being on the left or\n> right side of the symmetric difference.\n> \n> 1. Iterate over the left-hand commits, inserting a patch-id struct for\n> each into a hashmap, and pointing commit->util to the patch-id\n> struct.\n> \n> 2. Iterate over the right-hand commits, checking which are present in\n> the hashmap. If so, we exclude the commit from the output _and_ we\n> mark the patch-id as \"seen\".\n> \n> 3. Iterate again over the left-hand commits, checking whether\n> commit->util->seen is set; if so, exclude them from the output.\n> \n> At the end, we'll have eliminated commits from both sides that have a\n> matching patch-id on the other side. But there's a subtle assumption\n> here: for any given patch-id, we must have exactly one struct\n> representing it. If two commits from A both have the same patch-id and\n> we allow duplicates in the hashmap, then we run into a problem:\n> \n> a. In step 1, we insert two patch-id structs into the hashmap.\n> \n> b. In step 2, our lookups will find only one of these structs, so only\n> one \"seen\" flag is marked.\n> \n> c. In step 3, one of the commits in A will have its commit->util->seen\n> set, but the other will not. We'll erroneously output the latter.\n> \n> Prior to dfb7a1b4d0, our hashmap did not allow duplicates. Afterwards,\n> it used hashmap_add(), which explicitly does allow duplicates.\n> \n> At that point, the solution would have been easy: when we are about to\n> add a duplicate, skip doing so and return the existing entry which\n> matches. But it gets more complicated.\n> \n> In 683f17ec44 (patch-ids: replace the seen indicator with a commit\n> pointer, 2016-07-29), our step 3 goes away entirely. Instead, in step 2,\n> when the right-hand side finds a matching patch_id from the left-hand\n> side, we can directly mark the left-hand patch_id->commit to be omitted.\n> Solving that would be easy, too; there's a one-to-many relationship of\n> patch-ids to commits, so we just need to keep a list.\n> \n> But there's more. Commit b3dfeebb92 (rebase: avoid computing unnecessary\n> patch IDs, 2016-07-29) built on that by lazily computing the full\n> patch-ids. So we don't even know when adding to the hashmap whether two\n> commits truly have the same id. We'd have to tentatively assign them a\n> list, and then possibly split them apart (possibly into N new structs)\n> at the moment we compute the real patch-ids. This could work, but it's\n> complicated and error-prone.\n> \n> Instead, let's accept that we may store duplicates, and teach the lookup\n> side to be more clever. Rather than asking for a single matching\n> patch-id, it will need to iterate over all matching patch-ids. This does\n> mean examining every entry in a single hash bucket, but the worst-case\n> for a hash lookup was already doing that.\n> \n> We'll keep the hashmap details out of the caller by providing a simple\n> iteration interface. We can retain the simple has_commit_patch_id()\n> interface for the other callers, but we'll simplify its return value\n> into an integer, rather than returning the patch_id struct. That way\n> they won't be tempted to look at the \"commit\" field of the return value\n> without iterating.\n> \n> Reported-by: Arnaud Morin \n> Signed-off-by: Jeff King \n> ---\n> patch-ids.c | 14 +++++++++++++-\n> patch-ids.h | 20 +++++++++++++++++++-\n> revision.c | 6 ++++--\n> t/t6007-rev-list-cherry-pick-file.sh | 12 ++++++++++++\n> 4 files changed, 48 insertions(+), 4 deletions(-)\n> \n> diff --git a/patch-ids.c b/patch-ids.c\n> index 21973e4933..f51021a0cb 100644\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -89,7 +89,7 @@ static int init_patch_id_entry(struct patch_id *patch,\n> \treturn 0;\n> }\n> \n> -struct patch_id *has_commit_patch_id(struct commit *commit,\n> +struct patch_id *patch_id_iter_first(struct commit *commit,\n> \t\t\t\t struct patch_ids *ids)\n> {\n> \tstruct patch_id patch;\n> @@ -104,6 +104,18 @@ struct patch_id *has_commit_patch_id(struct commit *commit,\n> \treturn hashmap_get_entry(&ids->patches, &patch, ent, NULL);\n> }\n> \n> +struct patch_id *patch_id_iter_next(struct patch_id *cur,\n> +\t\t\t\t struct patch_ids *ids)\n> +{\n> +\treturn hashmap_get_next_entry(&ids->patches, cur, ent);\n> +}\n> +\n> +int has_commit_patch_id(struct commit *commit,\n> +\t\t\tstruct patch_ids *ids)\n> +{\n> +\treturn !!patch_id_iter_first(commit, ids);\n> +}\n> +\n> struct patch_id *add_commit_patch_id(struct commit *commit,\n> \t\t\t\t struct patch_ids *ids)\n> {\n> diff --git a/patch-ids.h b/patch-ids.h\n> index 03bb04e707..ab6c6a6804 100644\n> --- a/patch-ids.h\n> +++ b/patch-ids.h\n> @@ -23,7 +23,25 @@ int commit_patch_id(struct commit *commit, struct diff_options *options,\n> \t\t struct object_id *oid, int, int);\n> int init_patch_ids(struct repository *, struct patch_ids *);\n> int free_patch_ids(struct patch_ids *);\n> +\n> +/* Add a patch_id for a single commit to the set. */\n> struct patch_id *add_commit_patch_id(struct commit *, struct patch_ids *);\n> -struct patch_id *has_commit_patch_id(struct commit *, struct patch_ids *);\n> +\n> +/* Returns true if the patch-id of \"commit\" is present in the set. */\n> +int has_commit_patch_id(struct commit *commit, struct patch_ids *);\n> +\n> +/*\n> + * Iterate over all commits in the set whose patch id matches that of\n> + * \"commit\", like:\n> + *\n> + * struct patch_id *cur;\n> + * for (cur = patch_id_iter_first(commit, ids);\n> + * cur;\n> + * cur = patch_id_iter_next(cur, ids) {\n> + * ... look at cur->commit\n> + * }\n> + */\n> +struct patch_id *patch_id_iter_first(struct commit *commit, struct patch_ids *);\n> +struct patch_id *patch_id_iter_next(struct patch_id *cur, struct patch_ids *);\n> \n> #endif /* PATCH_IDS_H */\n> diff --git a/revision.c b/revision.c\n> index 9dff845bed..7ec9b634e3 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -1241,12 +1241,14 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n> \t\t/*\n> \t\t * Have we seen the same patch id?\n> \t\t */\n> -\t\tid = has_commit_patch_id(commit, &ids);\n> +\t\tid = patch_id_iter_first(commit, &ids);\n> \t\tif (!id)\n> \t\t\tcontinue;\n> \n> \t\tcommit->object.flags |= cherry_flag;\n> -\t\tid->commit->object.flags |= cherry_flag;\n> +\t\tdo {\n> +\t\t\tid->commit->object.flags |= cherry_flag;\n> +\t\t} while ((id = patch_id_iter_next(id, &ids)));\n> \t}\n> \n> \tfree_patch_ids(&ids);\n> diff --git a/t/t6007-rev-list-cherry-pick-file.sh b/t/t6007-rev-list-cherry-pick-file.sh\n> index f0268372d2..8bf5ae23c2 100755\n> --- a/t/t6007-rev-list-cherry-pick-file.sh\n> +++ b/t/t6007-rev-list-cherry-pick-file.sh\n> @@ -245,6 +245,18 @@ test_expect_success '--count --left-right' '\n> \ttest_cmp expect actual\n> '\n> \n> +test_expect_success '--cherry-pick with duplicates on each side' '\n> +\tgit checkout -b dup-orig &&\n> +\ttest_commit dup-base &&\n> +\tgit revert dup-base &&\n> +\tgit cherry-pick dup-base &&\n> +\tgit checkout -b dup-side HEAD~3 &&\n> +\ttest_tick &&\n> +\tgit cherry-pick -3 dup-orig &&\n> +\tgit rev-list --cherry-pick dup-orig...dup-side >actual &&\n> +\ttest_must_be_empty actual\n> +'\n> +\n> # Corrupt the object store deliberately to make sure\n> # the object is not even checked for its existence.\n> remove_loose_object () {\n> -- \n> 2.30.0.455.gdab6b73766\n> \n"},{"id":"414192","messageId":"xmqqy2gy3r5p.fsf@gitster.c.googlers.com","threadId":"54970","inReplyTo":"X/3FwNPHqZqY+hv0@coredump.intra.peff.net","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-12T19:13:06Z","receivedAt":"2021-01-12T19:14:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> At the end, we'll have eliminated commits from both sides that have a\n> matching patch-id on the other side. But there's a subtle assumption\n> here: for any given patch-id, we must have exactly one struct\n> representing it. If two commits from A both have the same patch-id and\n> we allow duplicates in the hashmap, then we run into a problem:\n\nIn practical terms, for one side of the history to have two\nidentical patches, the most likely scenerio for that to happen is to\nhave a patch, its reversion, and its reapplication, intermixed in\nits history with other commits, e.g.\n\n ---o---o---M---o---o---W---o---o---M---o--- ...\n \\\n o---o---o---M---o--- ...\n\nwhere \"M\" are commits that does an identical change, and \"W\"\n(upside-down \"M\") is its reversion. On the top history, \"M\" was\nintroduced, the bottom history cherry-picked, the top history found\nproblems in it and reverted with \"W\", and later (perhaps with the\nhelp of preparatory patches on top of \"W\"), the top history now\nconsiders that \"M\" is safe, so reapplies it.\n\nAnd a \"--cherry-pick\" output that excludes \"identical patches\" that\nappear on both sides on such a history would hide all \"M\"'s, leaving\na history like\n\n ---o---o-------o---o---W---o---o-------o--- ...\n \\\n o---o---o-------o--- ...\n\nBut is this result what the user really wanted to see, I have to\nwonder.\n\nI do not see any problem in the patch itself. We used to hide only\none \"M\" from the history on the top half in the picture, leaving one\n\"M\" and \"W\", while hiding the sole \"M\" from the bottom half. Now if\nwe want to no longer show any \"M\", the updated code would correctly\nhide all of them.\n\nIt just feels to me that the resulting view of the history look\nweird, leaving only the reversion of a patch that has never been\napplied in the first place.\n"},{"id":"414250","messageId":"20210113092448.GE32482@sync","threadId":"54970","inReplyTo":"xmqqy2gy3r5p.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Arnaud Morin","fromEmail":"arnaud.morin@gmail.com","sentAt":"2021-01-13T09:24:48Z","receivedAt":"2021-01-13T09:25:32Z","isPatch":true,"sender":{"key":"arnaud.morin@gmail.com","avatar":"https://gravatar.com/avatar/ce29e2523a928bef59a461d81576d4110beb87ad20bffa2c1a4ae08c137097bf?d=mp&s=160"},"body":"Without this patch, that's even worst, consistency is broken.\nLet me explain.\n\nWith your history example:\n\n ---o---o---M---o---o---W---o---o---M---o--- branch\n \\\n o---o---o---M---o--- master\n\n# WITHOUT PATCH\nIf we imagine that master is having more commits count than branch.\nThe result of rev-list will be like you described:\n$ git rev-list --left-right --cherry-pick branch...master\n Jeff King writes:\n> \n> > At the end, we'll have eliminated commits from both sides that have a\n> > matching patch-id on the other side. But there's a subtle assumption\n> > here: for any given patch-id, we must have exactly one struct\n> > representing it. If two commits from A both have the same patch-id and\n> > we allow duplicates in the hashmap, then we run into a problem:\n> \n> In practical terms, for one side of the history to have two\n> identical patches, the most likely scenerio for that to happen is to\n> have a patch, its reversion, and its reapplication, intermixed in\n> its history with other commits, e.g.\n> \n> ---o---o---M---o---o---W---o---o---M---o--- ...\n> \\\n> o---o---o---M---o--- ...\n> \n> where \"M\" are commits that does an identical change, and \"W\"\n> (upside-down \"M\") is its reversion. On the top history, \"M\" was\n> introduced, the bottom history cherry-picked, the top history found\n> problems in it and reverted with \"W\", and later (perhaps with the\n> help of preparatory patches on top of \"W\"), the top history now\n> considers that \"M\" is safe, so reapplies it.\n> \n> And a \"--cherry-pick\" output that excludes \"identical patches\" that\n> appear on both sides on such a history would hide all \"M\"'s, leaving\n> a history like\n> \n> ---o---o-------o---o---W---o---o-------o--- ...\n> \\\n> o---o---o-------o--- ...\n> \n> But is this result what the user really wanted to see, I have to\n> wonder.\n> \n> I do not see any problem in the patch itself. We used to hide only\n> one \"M\" from the history on the top half in the picture, leaving one\n> \"M\" and \"W\", while hiding the sole \"M\" from the bottom half. Now if\n> we want to no longer show any \"M\", the updated code would correctly\n> hide all of them.\n> \n> It just feels to me that the resulting view of the history look\n> weird, leaving only the reversion of a patch that has never been\n> applied in the first place.\n"},{"id":"414255","messageId":"X/7ur/IcCg1AqTdZ@coredump.intra.peff.net","threadId":"54970","inReplyTo":"20210113092448.GE32482@sync","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-13T12:59:27Z","receivedAt":"2021-01-13T13:00:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 13, 2021 at 09:24:48AM +0000, Arnaud Morin wrote:\n\n> Without this patch, that's even worst, consistency is broken.\n> Let me explain.\n> \n> With your history example:\n> \n> ---o---o---M---o---o---W---o---o---M---o--- branch\n> \\\n> o---o---o---M---o--- master\n> \n> # WITHOUT PATCH\n> If we imagine that master is having more commits count than branch.\n> The result of rev-list will be like you described:\n> $ git rev-list --left-right --cherry-pick branch...master\n> \n> In other words, it's showing both W and M.\n> \n> BUT, if we imagine now that master is having less commits count than branch.\n> $ git rev-list --left-right --cherry-pick branch...master\n> \n> It's only showing W!\n> \n> So the result is not consistent, depending on which branch is having\n> more commits.\n\nRight. There's definitely a question of whether --cherry-pick is the\nmost useful thing in such a situation, but the current behavior was\nsimply broken. It did not behave as advertised, and it treated one side\nof the history different from the other. So whether we want to do\nanything else to help that case, I think this at least makes\n--cherry-pick sane. :)\n\nHere are two related histories to think about.\n\nThis is the same history, but the revert and re-do happens on both\nsides (and this is actually the setup in the new test):\n\n ---o---o---M---o---o---W---o---o---M---o--- branch\n \\\n o---o---M---o---o---W---o---o---M---o--- master\n\nThere we really _do_ want to clear out both M's (really, all four),\nbecause we're doing so _from both sides_. And that is ultimately the\npoint of the cherry-pick option: show commits that were picked from one\nside to the other.\n\nAnother interesting case is when the first \"M\" is actually bundled into\nanother commit, like:\n\n ---o---o---M+X---o---o---W---o---o---M---o--- branch\n \\\n o---o---o--M---o--- master\n\nwhere \"M+X\" has the changes from \"M\" plus some other changes. It will\nget a different patch-id, and --cherry-pick would show both M+X and W,\nbut not M for either side. This is a limitation of the patch-id concept:\nwe are looking at whole commits, not overall changes.\n\nI suspect for most operations we care less about \"remove all\ncherry-picks from both sides\", but rather \"give me one side, omitting\ncommits that are already on the other side\" (because you want to rebase\nor cherry-pick some subset).\n\n-Peff\n"},{"id":"414282","messageId":"xmqqk0sgy6tz.fsf@gitster.c.googlers.com","threadId":"54970","inReplyTo":"20210113092448.GE32482@sync","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-13T19:28:40Z","receivedAt":"2021-01-13T19:29:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Arnaud Morin writes:\n\n> Without this patch, that's even worst, consistency is broken.\n> Let me explain.\n>\n> With your history example:\n>\n> ---o---o---M---o---o---W---o---o---M---o--- branch\n> \\\n> o---o---o---M---o--- master\n>\n> # WITHOUT PATCH\n> If we imagine that master is having more commits count than branch.\n> The result of rev-list will be like you described:\n> $ git rev-list --left-right --cherry-pick branch...master\n> \n> In other words, it's showing both W and M.\n\nSo, at least they cancel out and the reader can tell that the net\neffect was none --- that is \"sort of understandable\" result.\n\n> BUT, if we imagine now that master is having less commits count than branch.\n> $ git rev-list --left-right --cherry-pick branch...master\n> \n> It's only showing W!\n\nWhich is what I felt misleading.\n\n> # WITH PATCH\n> With the patch, everything is consistent, and only W is kept in ouptut,\n> no matter the size of history:\n> $ git.p rev-list --left-right --cherry-pick branch...master\n> writes:\n\n> Right. There's definitely a question of whether --cherry-pick is the\n> most useful thing in such a situation, but the current behavior was\n> simply broken. It did not behave as advertised, and it treated one side\n> of the history different from the other. So whether we want to do\n> anything else to help that case, I think this at least makes\n> --cherry-pick sane. :)\n\nYes; I think \"sane\" does not always equal to \"useful\", though ;-)\n\n> Here are two related histories to think about.\n> ...\n> I suspect for most operations we care less about \"remove all\n> cherry-picks from both sides\", but rather \"give me one side, omitting\n> commits that are already on the other side\" (because you want to rebase\n> or cherry-pick some subset).\n\nYes again. It means \"--cherry-pick\" inherently is not symmetric.\nOne side is the reference side (i.e. mainline), and the goal is to\nremove from the other side what is in the reference side.\n\nWhat we are seeing in this discussion is that \"--cherry-pick\" and\nsymmetric difference do not conceptually play well together.\n\nBut the behaviour with the patch makes the most sense when\ncherry-pick is applied to a symmetric difference (provided that\ndoing so makes sense in the first place, that is).\n"},{"id":"414289","messageId":"X/9ZNM9KxZaQ2it+@coredump.intra.peff.net","threadId":"54970","inReplyTo":"xmqq7dogy4dx.fsf@gitster.c.googlers.com","subject":"Re: [PATCH] patch-ids: handle duplicate hashmap entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-01-13T20:33:56Z","receivedAt":"2021-01-13T20:34:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 13, 2021 at 12:21:30PM -0800, Junio C Hamano wrote:\n\n> > I suspect for most operations we care less about \"remove all\n> > cherry-picks from both sides\", but rather \"give me one side, omitting\n> > commits that are already on the other side\" (because you want to rebase\n> > or cherry-pick some subset).\n> \n> Yes again. It means \"--cherry-pick\" inherently is not symmetric.\n> One side is the reference side (i.e. mainline), and the goal is to\n> remove from the other side what is in the reference side.\n> \n> What we are seeing in this discussion is that \"--cherry-pick\" and\n> symmetric difference do not conceptually play well together.\n> \n> But the behaviour with the patch makes the most sense when\n> cherry-pick is applied to a symmetric difference (provided that\n> doing so makes sense in the first place, that is).\n\nI didn't realize --cherry-pick would work without a symmetric\ndifference. The documentation says:\n\n Omit any commit that introduces the same change as another commit on\n the “other side” when the set of commits are limited with symmetric\n difference.\n\nAnd indeed, I think it silently does nothing with:\n\n git rev-list --cherry-pick A..B\n\n(because there is nothing on the \"other\" side to match).\n\nSo you do need some symmetric difference in order to define the two\nsets, but you might only want to see one of the sides. And that is\nbasically what --cherry does. But having looked at the implementation of\ncherry_pick_list(), it is quite happy to swap the sides internally. I\nguess if we were going to make the output unsymmetric, the first thing\nwould be to stop doing that swap. :)\n\nFor the specifics of reverts and replays, though, I think the weirdness\nhas nothing to do with left/right, or showing one side. It's the\nmismatched count. So if we were to make any change, it would be to keep\na count of how many times each commit appears on the other side, and\ncancel them one for one.\n\nI.e., this:\n\n o--M--W--M--o--\n \\\n o--M--o---\n\nmight plausibly want to show \"M\" once on the upper branch. But:\n\n o--M--W--M--o--\n \\\n o--M--W--M--o--\n\nshould never show M, I wouldn't think.\n\nI'm not sure if that would be violating what existing callers expect\nfrom \"--cherry-pick\", though (i.e., if it would need another name, or an\nextra option to trigger).\n\n-Peff\n"}]}