{"thread":{"id":"49328","subject":"[PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags()","startedAt":"2018-09-12T14:22:57Z","lastAt":"2018-09-25T20:29:11Z","messageCount":25,"participants":["Derrick Stolee via GitGitGadget","Jeff King","Junio C Hamano","Derrick Stolee","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"357965","messageId":"pull.39.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":null,"subject":"[PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-12T14:22:54Z","receivedAt":"2018-09-12T14:22:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As Peff reported [1], the refactored can_all_from_reach_with_flags() method\ndoes not properly peel tags. Since the helper method can_all_from_reach()\nand code in t/helper/test-reach.c all peel tags before getting to this\nmethod, it is not super-simple to create a test that demonstrates this.\n\nI modified t/helper/test-reach.c to allow calling\ncan_all_from_reach_with_flags() directly, and added a test in\nt6600-test-reach.sh that demonstrates the segfault without the fix. The fix\nin commit-reach.c is Peff's fix verbatim.\n\n[1] \nhttps://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u\n\nDerrick Stolee (1):\n commit-reach: properly peel tags\n\n commit-reach.c | 25 ++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 63 insertions(+), 14 deletions(-)\n\n\nbase-commit: 6621c838743812aaba96e55cfec8524ea1144c2d\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/39\n-- \ngitgitgadget\n"},{"id":"357966","messageId":"948e222228d2f2868b85a425142382e63a17773a.1536762173.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.git.gitgitgadget@gmail.com","subject":"[PATCH 1/1] commit-reach: properly peel tags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-12T14:22:56Z","receivedAt":"2018-09-12T14:23:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n\"commit-reach: make can_all_from_reach... linear\" but incorrectly\nassumed that all objects provided were commits. During a fetch\nnegotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\nto the 'from' array. The current code creates a segfault.\n\nAdd a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\nand add a test in t6600-test-reach.sh that demonstrates this segfault.\n\nCorrect the issue by peeling tags when investigating the initial list\nof objects in the 'from' array.\n\nSigned-off-by: Jeff King \nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 25 ++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 63 insertions(+), 14 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 86715c103c..6de72c6e03 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,\n {\n \tstruct commit **list = NULL;\n \tint i;\n+\tint nr_commits;\n \tint result = 1;\n \n \tALLOC_ARRAY(list, from->nr);\n+\tnr_commits = 0;\n \tfor (i = 0; i < from->nr; i++) {\n-\t\tlist[i] = (struct commit *)from->objects[i].item;\n+\t\tstruct object *from_one = from->objects[i].item;\n \n-\t\tif (parse_commit(list[i]) ||\n-\t\t list[i]->generation < min_generation)\n-\t\t\treturn 0;\n+\t\tfrom_one = deref_tag(the_repository, from_one,\n+\t\t\t\t \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n+\t\t\tfrom->objects[i].item->flags |= assign_flag;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tlist[nr_commits] = (struct commit *)from_one;\n+\t\tif (parse_commit(list[nr_commits]) ||\n+\t\t list[nr_commits]->generation < min_generation)\n+\t\t\treturn 0; /* is this a leak? */\n+\t\tnr_commits++;\n \t}\n \n-\tQSORT(list, from->nr, compare_commits_by_gen);\n+\tQSORT(list, nr_commits, compare_commits_by_gen);\n \n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\t/* DFS from list[i] */\n \t\tstruct commit_list *stack = NULL;\n \n@@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t}\n \n cleanup:\n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\tclear_commit_marks(list[i], RESULT);\n \t\tclear_commit_marks(list[i], assign_flag);\n \t}\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex eb21103998..08d2ea68e8 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)\n \tstruct object_id oid_A, oid_B;\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n+\tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n \tstruct commit **X_array;\n \tint X_nr, X_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n-\t\tstruct object *o;\n+\t\tstruct object *orig;\n+\t\tstruct object *peeled;\n \t\tstruct commit *c;\n \t\tif (buf.len < 3)\n \t\t\tcontinue;\n@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)\n \t\tif (get_oid_committish(buf.buf + 2, &oid))\n \t\t\tdie(\"failed to resolve %s\", buf.buf + 2);\n \n-\t\to = parse_object(r, &oid);\n-\t\to = deref_tag_noverify(o);\n+\t\torig = parse_object(r, &oid);\n+\t\tpeeled = deref_tag_noverify(orig);\n \n-\t\tif (!o)\n+\t\tif (!peeled)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n \t\t\t buf.buf, oid_to_hex(&oid));\n \n-\t\tc = object_as_type(r, o, OBJ_COMMIT, 0);\n+\t\tc = object_as_type(r, peeled, OBJ_COMMIT, 0);\n \n \t\tif (!c)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\t\tcommit_list_insert(c, &X);\n \t\t\t\tALLOC_GROW(X_array, X_nr + 1, X_alloc);\n \t\t\t\tX_array[X_nr++] = c;\n+\t\t\t\tadd_object_array(orig, NULL, &X_obj);\n \t\t\t\tbreak;\n \n \t\t\tcase 'Y':\n@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)\n \t\tprint_sorted_commit_ids(list);\n \t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n \t\tprintf(\"%s(X,Y):%d\\n\", av[1], can_all_from_reach(X, Y, 1));\n+\t} else if (!strcmp(av[1], \"can_all_from_reach_with_flag\")) {\n+\t\tstruct commit_list *iter = Y;\n+\n+\t\twhile (iter) {\n+\t\t\titer->item->object.flags |= 2;\n+\t\t\titer = iter->next;\n+\t\t}\n+\n+\t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n \t} else if (!strcmp(av[1], \"commit_contains\")) {\n \t\tstruct ref_filter filter;\n \t\tstruct contains_cache cache;\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex d139a00d1d..f7bf82290b 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -31,7 +31,8 @@ test_expect_success 'setup' '\n \tfor i in $(test_seq 1 10)\n \tdo\n \t\ttest_commit \"1-$i\" &&\n-\t\tgit branch -f commit-1-$i\n+\t\tgit branch -f commit-1-$i &&\n+\t\tgit tag -a -m \"1-$i\" tag-1-$i commit-1-$i\n \tdone &&\n \tfor j in $(test_seq 1 9)\n \tdo\n@@ -39,11 +40,13 @@ test_expect_success 'setup' '\n \t\tx=$(($j + 1)) &&\n \t\ttest_commit \"$x-1\" &&\n \t\tgit branch -f commit-$x-1 &&\n+\t\tgit tag -a -m \"$x-1\" tag-$x-1 commit-$x-1 &&\n \n \t\tfor i in $(test_seq 2 10)\n \t\tdo\n \t\t\tgit merge commit-$j-$i -m \"$x-$i\" &&\n-\t\t\tgit branch -f commit-$x-$i\n+\t\t\tgit branch -f commit-$x-$i &&\n+\t\t\tgit tag -a -m \"$x-$i\" tag-$x-$i commit-$x-$i\n \t\tdone\n \tdone &&\n \tgit commit-graph write --reachable &&\n@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '\n \ttest_three_modes can_all_from_reach\n '\n \n+test_expect_success 'can_all_from_reach_with_flag: tags case' '\n+\tcat >input <<-\\EOF &&\n+\tX:tag-2-10\n+\tX:tag-3-9\n+\tX:tag-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:tag-1-9\n+\tY:tag-2-8\n+\tY:tag-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-7-3\n+\tY:commit-8-1\n+\tEOF\n+\techo \"can_all_from_reach_with_flag(X,_,_,0,0):1\" >expect &&\n+\ttest_three_modes can_all_from_reach_with_flag\n+'\n+\t\n test_expect_success 'commit_contains:hit' '\n \tcat >input <<-\\EOF &&\n \tA:commit-7-7\n-- \ngitgitgadget\n"},{"id":"358002","messageId":"20180912194130.GA22146@sigill.intra.peff.net","threadId":"49328","inReplyTo":"948e222228d2f2868b85a425142382e63a17773a.1536762173.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] commit-reach: properly peel tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-12T19:41:30Z","receivedAt":"2018-09-12T19:41:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 12, 2018 at 07:22:56AM -0700, Derrick Stolee via GitGitGadget wrote:\n\n> From: Derrick Stolee \n> \n> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n> \"commit-reach: make can_all_from_reach... linear\" but incorrectly\n> assumed that all objects provided were commits. During a fetch\n> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\n> to the 'from' array. The current code creates a segfault.\n> \n> Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\n> and add a test in t6600-test-reach.sh that demonstrates this segfault.\n\nThanks, that makes a lot of sense for reproducing. I almost wonder if\nthe whole X_array of commits in test-reach could just go away, and we'd\nfeed whatever list of objects the caller happens to send. That may make\nit simpler to include non-commit objects in a variety of tests.\n\nThat said, I didn't look closely at other fallout in the program from\nthat, so I'll defer to your judgement.\n\n> Correct the issue by peeling tags when investigating the initial list\n> of objects in the 'from' array.\n> \n> Signed-off-by: Jeff King \n\nI'm not sure if this should just be Reported-by, since I don't know that\nI actually contributed any code. ;) But for anything I might have\ncontributed, certainly you have my signoff.\n\n> \tfor (i = 0; i < from->nr; i++) {\n> -\t\tlist[i] = (struct commit *)from->objects[i].item;\n> +\t\tstruct object *from_one = from->objects[i].item;\n> \n> -\t\tif (parse_commit(list[i]) ||\n> -\t\t list[i]->generation < min_generation)\n> -\t\t\treturn 0;\n> +\t\tfrom_one = deref_tag(the_repository, from_one,\n> +\t\t\t\t \"a from object\", 0);\n> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n> +\t\t\tcontinue;\n> +\t\t}\n\nI didn't resurrect the comment from this conditional that was in the\noriginal code (mostly because I wasn't sure if the reasoning was still\nentirely valid, or what setting the flag here actually means). But it's\nprobably worth saying something here to explain why it's OK to punt on\nthis case, and what it means to just set the flag.\n\n> [...]\n\nThe rest of the patch looks sane to me. I didn't go through the trouble\nto reproduce the segfault with the test, but it sounds like you did.\n\n-Peff\n"},{"id":"358009","messageId":"xmqqpnxijtpd.fsf@gitster-ct.c.googlers.com","threadId":"49328","inReplyTo":"948e222228d2f2868b85a425142382e63a17773a.1536762173.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] commit-reach: properly peel tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-12T21:23:42Z","receivedAt":"2018-09-12T21:23:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 86715c103c..6de72c6e03 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> {\n> \tstruct commit **list = NULL;\n> \tint i;\n> +\tint nr_commits;\n> \tint result = 1;\n> \n> \tALLOC_ARRAY(list, from->nr);\n> +\tnr_commits = 0;\n> \tfor (i = 0; i < from->nr; i++) {\n> -\t\tlist[i] = (struct commit *)from->objects[i].item;\n> +\t\tstruct object *from_one = from->objects[i].item;\n> \n> -\t\tif (parse_commit(list[i]) ||\n> -\t\t list[i]->generation < min_generation)\n> -\t\t\treturn 0;\n> +\t\tfrom_one = deref_tag(the_repository, from_one,\n> +\t\t\t\t \"a from object\", 0);\n> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n\nI wondered why this is not futzing with \"from_one->flags\"; by going\nback to the original from->objects[] array, the code is setting the\nflags on the original tag object and not the non-commit object that\nwas pointed at by the tag.\n\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tlist[nr_commits] = (struct commit *)from_one;\n> +\t\tif (parse_commit(list[nr_commits]) ||\n> +\t\t list[nr_commits]->generation < min_generation)\n> +\t\t\treturn 0; /* is this a leak? */\n> +\t\tnr_commits++;\n> \t}\n\nIn the original code, the flags bits were left unchanged if the loop\nterminated by hitting a commit whose generation is too young (or\nparse_commit() returns non-zero). With this updated code, flags bit\ncan be modified before the code notices the situation and leave the\nfunction, bypassing the \"cleanup\" we see below that clears the\n\"assign_flag\" bits.\n\nWould it be a problem that we return early without cleaning up?\n\nEven if we do not call this early return, the assign_flag bits added\nto the original tag in from->objects[i].item won't be cleaned in\nthis new code, as \"cleanup:\" section now loops over the list[] that\nomits the object whose flags was smudged above before the \"continue\".\n\nWould it be a problem that we leave the assign_flags without\ncleaning up?\n\n> -\tQSORT(list, from->nr, compare_commits_by_gen);\n> +\tQSORT(list, nr_commits, compare_commits_by_gen);\n> \n> -\tfor (i = 0; i < from->nr; i++) {\n> +\tfor (i = 0; i < nr_commits; i++) {\n> \t\t/* DFS from list[i] */\n> \t\tstruct commit_list *stack = NULL;\n> \n> @@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> \t}\n> \n> cleanup:\n> -\tfor (i = 0; i < from->nr; i++) {\n> +\tfor (i = 0; i < nr_commits; i++) {\n> \t\tclear_commit_marks(list[i], RESULT);\n> \t\tclear_commit_marks(list[i], assign_flag);\n> \t}\n"},{"id":"358012","messageId":"20180912213407.GA27598@sigill.intra.peff.net","threadId":"49328","inReplyTo":"xmqqpnxijtpd.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/1] commit-reach: properly peel tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-12T21:34:08Z","receivedAt":"2018-09-12T21:34:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 12, 2018 at 02:23:42PM -0700, Junio C Hamano wrote:\n\n> > diff --git a/commit-reach.c b/commit-reach.c\n> > index 86715c103c..6de72c6e03 100644\n> > --- a/commit-reach.c\n> > +++ b/commit-reach.c\n> > @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> > {\n> > \tstruct commit **list = NULL;\n> > \tint i;\n> > +\tint nr_commits;\n> > \tint result = 1;\n> > \n> > \tALLOC_ARRAY(list, from->nr);\n> > +\tnr_commits = 0;\n> > \tfor (i = 0; i < from->nr; i++) {\n> > -\t\tlist[i] = (struct commit *)from->objects[i].item;\n> > +\t\tstruct object *from_one = from->objects[i].item;\n> > \n> > -\t\tif (parse_commit(list[i]) ||\n> > -\t\t list[i]->generation < min_generation)\n> > -\t\t\treturn 0;\n> > +\t\tfrom_one = deref_tag(the_repository, from_one,\n> > +\t\t\t\t \"a from object\", 0);\n> > +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> > +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n> \n> I wondered why this is not futzing with \"from_one->flags\"; by going\n> back to the original from->objects[] array, the code is setting the\n> flags on the original tag object and not the non-commit object that\n> was pointed at by the tag.\n\nNote that from_one may even be NULL.\n\n> > +\t\t\tcontinue;\n> > +\t\t}\n> > +\n> > +\t\tlist[nr_commits] = (struct commit *)from_one;\n> > +\t\tif (parse_commit(list[nr_commits]) ||\n> > +\t\t list[nr_commits]->generation < min_generation)\n> > +\t\t\treturn 0; /* is this a leak? */\n> > +\t\tnr_commits++;\n> > \t}\n> \n> In the original code, the flags bits were left unchanged if the loop\n> terminated by hitting a commit whose generation is too young (or\n> parse_commit() returns non-zero). With this updated code, flags bit\n> can be modified before the code notices the situation and leave the\n> function, bypassing the \"cleanup\" we see below that clears the\n> \"assign_flag\" bits.\n> \n> Would it be a problem that we return early without cleaning up?\n> \n> Even if we do not call this early return, the assign_flag bits added\n> to the original tag in from->objects[i].item won't be cleaned in\n> this new code, as \"cleanup:\" section now loops over the list[] that\n> omits the object whose flags was smudged above before the \"continue\".\n> \n> Would it be a problem that we leave the assign_flags without\n> cleaning up?\n\nYeah, I hadn't thought about the bit cleanup when making my original\nsuggestion. In the original code (before 4fbcca4eff), I think we did set\nflags as we iterated through the loop, and we could still do an early\nreturn when we hit \"!reachable(...)\". But I don't see any cleanup of\nassign_flag there at all.\n\nSo I guess I'm pretty confused about what the semantics are supposed to\nbe.\n\n-Peff\n"},{"id":"358055","messageId":"pull.39.v2.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.git.gitgitgadget@gmail.com","subject":"[PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-13T16:10:34Z","receivedAt":"2018-09-13T16:10:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As Peff reported [1], the refactored can_all_from_reach_with_flags() method\ndoes not properly peel tags. Since the helper method can_all_from_reach()\nand code in t/helper/test-reach.c all peel tags before getting to this\nmethod, it is not super-simple to create a test that demonstrates this.\n\nI modified t/helper/test-reach.c to allow calling\ncan_all_from_reach_with_flags() directly, and added a test in\nt6600-test-reach.sh that demonstrates the segfault without the fix.\n\nFor V2, I compared the loop that inspects the 'from' commits in commit\nba3ca1edce \"commit-reach: move can_all_from_reach_with_flags\" to the version\nhere and got the following diff:\n\n3c3\n< if (from_one->flags & assign_flag)\n---\n> if (!from_one || from_one->flags & assign_flag)\n5c5,7\n< from_one = deref_tag(the_repository, from_one, \"a from object\", 0);\n---\n>\n> from_one = deref_tag(the_repository, from_one,\n> \"a from object\", 0);\n14a17,22\n>\n> list[nr_commits] = (struct commit *)from_one;\n> if (parse_commit(list[nr_commits]) ||\n> list[nr_commits]->generation < min_generation)\n> return 0; /* is this a leak? */\n> nr_commits++;\n\nThis diff includes the early termination we had before 'deref_tag' and the\ncomment for why we can ignore non-commit objects.\n\n[1] \nhttps://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u\n\nDerrick Stolee (1):\n commit-reach: properly peel tags\n\n commit-reach.c | 33 ++++++++++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 71 insertions(+), 14 deletions(-)\n\n\nbase-commit: 6621c838743812aaba96e55cfec8524ea1144c2d\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/39\n\nRange-diff vs v1:\n\n 1: 948e222228 ! 1: 4bf21204dd commit-reach: properly peel tags\n @@ -36,9 +36,17 @@\n -\t\tif (parse_commit(list[i]) ||\n -\t\t list[i]->generation < min_generation)\n -\t\t\treturn 0;\n ++\t\tif (!from_one || from_one->flags & assign_flag)\n ++\t\t\tcontinue;\n ++\n +\t\tfrom_one = deref_tag(the_repository, from_one,\n +\t\t\t\t \"a from object\", 0);\n +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n ++\t\t\t/* no way to tell if this is reachable by\n ++\t\t\t * looking at the ancestry chain alone, so\n ++\t\t\t * leave a note to ourselves not to worry about\n ++\t\t\t * this object anymore.\n ++\t\t\t */\n +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n +\t\t\tcontinue;\n +\t\t}\n @@ -187,7 +195,7 @@\n +\techo \"can_all_from_reach_with_flag(X,_,_,0,0):1\" >expect &&\n +\ttest_three_modes can_all_from_reach_with_flag\n +'\n -+\t\n ++\n test_expect_success 'commit_contains:hit' '\n \tcat >input <<-\\EOF &&\n \tA:commit-7-7\n\n-- \ngitgitgadget\n"},{"id":"358056","messageId":"4bf21204ddf8b9daa823db9954ddde98ab264a1b.1536855032.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 1/1] commit-reach: properly peel tags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-13T16:10:35Z","receivedAt":"2018-09-13T16:10:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n\"commit-reach: make can_all_from_reach... linear\" but incorrectly\nassumed that all objects provided were commits. During a fetch\nnegotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\nto the 'from' array. The current code creates a segfault.\n\nAdd a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\nand add a test in t6600-test-reach.sh that demonstrates this segfault.\n\nCorrect the issue by peeling tags when investigating the initial list\nof objects in the 'from' array.\n\nSigned-off-by: Jeff King \nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 33 ++++++++++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 71 insertions(+), 14 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 86715c103c..4048a2132a 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from,\n {\n \tstruct commit **list = NULL;\n \tint i;\n+\tint nr_commits;\n \tint result = 1;\n \n \tALLOC_ARRAY(list, from->nr);\n+\tnr_commits = 0;\n \tfor (i = 0; i < from->nr; i++) {\n-\t\tlist[i] = (struct commit *)from->objects[i].item;\n+\t\tstruct object *from_one = from->objects[i].item;\n \n-\t\tif (parse_commit(list[i]) ||\n-\t\t list[i]->generation < min_generation)\n-\t\t\treturn 0;\n+\t\tif (!from_one || from_one->flags & assign_flag)\n+\t\t\tcontinue;\n+\n+\t\tfrom_one = deref_tag(the_repository, from_one,\n+\t\t\t\t \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n+\t\t\t/* no way to tell if this is reachable by\n+\t\t\t * looking at the ancestry chain alone, so\n+\t\t\t * leave a note to ourselves not to worry about\n+\t\t\t * this object anymore.\n+\t\t\t */\n+\t\t\tfrom->objects[i].item->flags |= assign_flag;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tlist[nr_commits] = (struct commit *)from_one;\n+\t\tif (parse_commit(list[nr_commits]) ||\n+\t\t list[nr_commits]->generation < min_generation)\n+\t\t\treturn 0; /* is this a leak? */\n+\t\tnr_commits++;\n \t}\n \n-\tQSORT(list, from->nr, compare_commits_by_gen);\n+\tQSORT(list, nr_commits, compare_commits_by_gen);\n \n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\t/* DFS from list[i] */\n \t\tstruct commit_list *stack = NULL;\n \n@@ -600,7 +619,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t}\n \n cleanup:\n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\tclear_commit_marks(list[i], RESULT);\n \t\tclear_commit_marks(list[i], assign_flag);\n \t}\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex eb21103998..08d2ea68e8 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)\n \tstruct object_id oid_A, oid_B;\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n+\tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n \tstruct commit **X_array;\n \tint X_nr, X_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n-\t\tstruct object *o;\n+\t\tstruct object *orig;\n+\t\tstruct object *peeled;\n \t\tstruct commit *c;\n \t\tif (buf.len < 3)\n \t\t\tcontinue;\n@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)\n \t\tif (get_oid_committish(buf.buf + 2, &oid))\n \t\t\tdie(\"failed to resolve %s\", buf.buf + 2);\n \n-\t\to = parse_object(r, &oid);\n-\t\to = deref_tag_noverify(o);\n+\t\torig = parse_object(r, &oid);\n+\t\tpeeled = deref_tag_noverify(orig);\n \n-\t\tif (!o)\n+\t\tif (!peeled)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n \t\t\t buf.buf, oid_to_hex(&oid));\n \n-\t\tc = object_as_type(r, o, OBJ_COMMIT, 0);\n+\t\tc = object_as_type(r, peeled, OBJ_COMMIT, 0);\n \n \t\tif (!c)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\t\tcommit_list_insert(c, &X);\n \t\t\t\tALLOC_GROW(X_array, X_nr + 1, X_alloc);\n \t\t\t\tX_array[X_nr++] = c;\n+\t\t\t\tadd_object_array(orig, NULL, &X_obj);\n \t\t\t\tbreak;\n \n \t\t\tcase 'Y':\n@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)\n \t\tprint_sorted_commit_ids(list);\n \t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n \t\tprintf(\"%s(X,Y):%d\\n\", av[1], can_all_from_reach(X, Y, 1));\n+\t} else if (!strcmp(av[1], \"can_all_from_reach_with_flag\")) {\n+\t\tstruct commit_list *iter = Y;\n+\n+\t\twhile (iter) {\n+\t\t\titer->item->object.flags |= 2;\n+\t\t\titer = iter->next;\n+\t\t}\n+\n+\t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n \t} else if (!strcmp(av[1], \"commit_contains\")) {\n \t\tstruct ref_filter filter;\n \t\tstruct contains_cache cache;\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex d139a00d1d..ae94b27f70 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -31,7 +31,8 @@ test_expect_success 'setup' '\n \tfor i in $(test_seq 1 10)\n \tdo\n \t\ttest_commit \"1-$i\" &&\n-\t\tgit branch -f commit-1-$i\n+\t\tgit branch -f commit-1-$i &&\n+\t\tgit tag -a -m \"1-$i\" tag-1-$i commit-1-$i\n \tdone &&\n \tfor j in $(test_seq 1 9)\n \tdo\n@@ -39,11 +40,13 @@ test_expect_success 'setup' '\n \t\tx=$(($j + 1)) &&\n \t\ttest_commit \"$x-1\" &&\n \t\tgit branch -f commit-$x-1 &&\n+\t\tgit tag -a -m \"$x-1\" tag-$x-1 commit-$x-1 &&\n \n \t\tfor i in $(test_seq 2 10)\n \t\tdo\n \t\t\tgit merge commit-$j-$i -m \"$x-$i\" &&\n-\t\t\tgit branch -f commit-$x-$i\n+\t\t\tgit branch -f commit-$x-$i &&\n+\t\t\tgit tag -a -m \"$x-$i\" tag-$x-$i commit-$x-$i\n \t\tdone\n \tdone &&\n \tgit commit-graph write --reachable &&\n@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '\n \ttest_three_modes can_all_from_reach\n '\n \n+test_expect_success 'can_all_from_reach_with_flag: tags case' '\n+\tcat >input <<-\\EOF &&\n+\tX:tag-2-10\n+\tX:tag-3-9\n+\tX:tag-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:tag-1-9\n+\tY:tag-2-8\n+\tY:tag-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-7-3\n+\tY:commit-8-1\n+\tEOF\n+\techo \"can_all_from_reach_with_flag(X,_,_,0,0):1\" >expect &&\n+\ttest_three_modes can_all_from_reach_with_flag\n+'\n+\n test_expect_success 'commit_contains:hit' '\n \tcat >input <<-\\EOF &&\n \tA:commit-7-7\n-- \ngitgitgadget\n"},{"id":"358058","messageId":"8d6061de-1654-577c-40c6-211dbd03aa36@gmail.com","threadId":"49328","inReplyTo":"4bf21204ddf8b9daa823db9954ddde98ab264a1b.1536855032.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/1] commit-reach: properly peel tags","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-09-13T16:38:16Z","receivedAt":"2018-09-13T16:38:20Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/13/2018 12:10 PM, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n> \"commit-reach: make can_all_from_reach... linear\" but incorrectly\n> assumed that all objects provided were commits. During a fetch\n> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\n> to the 'from' array. The current code creates a segfault.\n>\n> Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\n> and add a test in t6600-test-reach.sh that demonstrates this segfault.\n>\n> Correct the issue by peeling tags when investigating the initial list\n> of objects in the 'from' array.\n>\n> Signed-off-by: Jeff King \n> Signed-off-by: Derrick Stolee \n> ---\n> commit-reach.c | 33 ++++++++++++++++++++++++++-------\n> t/helper/test-reach.c | 22 +++++++++++++++++-----\n> t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n> 3 files changed, 71 insertions(+), 14 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 86715c103c..4048a2132a 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> {\n> \tstruct commit **list = NULL;\n> \tint i;\n> +\tint nr_commits;\n> \tint result = 1;\n> \n> \tALLOC_ARRAY(list, from->nr);\n> +\tnr_commits = 0;\n> \tfor (i = 0; i < from->nr; i++) {\n> -\t\tlist[i] = (struct commit *)from->objects[i].item;\n> +\t\tstruct object *from_one = from->objects[i].item;\n> \n> -\t\tif (parse_commit(list[i]) ||\n> -\t\t list[i]->generation < min_generation)\n> -\t\t\treturn 0;\n> +\t\tif (!from_one || from_one->flags & assign_flag)\n> +\t\t\tcontinue;\n> +\n> +\t\tfrom_one = deref_tag(the_repository, from_one,\n> +\t\t\t\t \"a from object\", 0);\n> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> +\t\t\t/* no way to tell if this is reachable by\n> +\t\t\t * looking at the ancestry chain alone, so\n> +\t\t\t * leave a note to ourselves not to worry about\n> +\t\t\t * this object anymore.\n> +\t\t\t */\n> +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tlist[nr_commits] = (struct commit *)from_one;\n> +\t\tif (parse_commit(list[nr_commits]) ||\n> +\t\t list[nr_commits]->generation < min_generation)\n> +\t\t\treturn 0; /* is this a leak? */\n\nOf course, after sending v2, I see this comment. This is a leak of \n'list' and should be fixed.\n\nNot only is it a leak here, it is also a leak in the 'cleanup' section. \nI'll squash the following into v3, but I'll let v2 simmer for review \nbefore rerolling.\n\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 4048a2132a..c457d8d85f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct \nobject_array *from,\n\n                 list[nr_commits] = (struct commit *)from_one;\n                 if (parse_commit(list[nr_commits]) ||\n-                   list[nr_commits]->generation < min_generation)\n-                       return 0; /* is this a leak? */\n+                   list[nr_commits]->generation < min_generation) {\n+                       result = 0;\n+                       goto cleanup;\n+               }\n+\n                 nr_commits++;\n         }\n\n@@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct object_array \n*from,\n                 clear_commit_marks(list[i], RESULT);\n                 clear_commit_marks(list[i], assign_flag);\n         }\n+       free(list);\n         return result;\n  }\n\n"},{"id":"358092","messageId":"xmqqy3c5ds48.fsf@gitster-ct.c.googlers.com","threadId":"49328","inReplyTo":"8d6061de-1654-577c-40c6-211dbd03aa36@gmail.com","subject":"Re: [PATCH v2 1/1] commit-reach: properly peel tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-13T21:06:47Z","receivedAt":"2018-09-13T21:06:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n>> +\t\t\t/* no way to tell if this is reachable by\n>> +\t\t\t * looking at the ancestry chain alone, so\n>> +\t\t\t * leave a note to ourselves not to worry about\n>> +\t\t\t * this object anymore.\n>> +\t\t\t */\n>> +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n>> +\t\t\tcontinue;\n>> +\t\t}\n>> +\n>> +\t\tlist[nr_commits] = (struct commit *)from_one;\n>> +\t\tif (parse_commit(list[nr_commits]) ||\n>> +\t\t list[nr_commits]->generation < min_generation)\n>> +\t\t\treturn 0; /* is this a leak? */\n>\n> Of course, after sending v2, I see this comment. This is a leak of\n> 'list' and should be fixed.\n>\n> Not only is it a leak here, it is also a leak in the 'cleanup'\n> section. I'll squash the following into v3, but I'll let v2 simmer for\n> review before rerolling.\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 4048a2132a..c457d8d85f 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct\n> object_array *from,\n>\n>                 list[nr_commits] = (struct commit *)from_one;\n>                 if (parse_commit(list[nr_commits]) ||\n> -                   list[nr_commits]->generation < min_generation)\n> -                       return 0; /* is this a leak? */\n> +                   list[nr_commits]->generation < min_generation) {\n> +                       result = 0;\n> +                       goto cleanup;\n> +               }\n> +\n>                 nr_commits++;\n>         }\n>\n> @@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct\n> object_array *from,\n>                 clear_commit_marks(list[i], RESULT);\n>                 clear_commit_marks(list[i], assign_flag);\n>         }\n> +       free(list);\n>         return result;\n>  }\n\nWith this, commit marks are cleared even when we do the \"early\nreturn\", but only for the objects that appear in the resulting\nlist[]. Because the for() loop in the last hunk interates over\nlist[], those non-commit objects that are smudged with assign_flag\nbut never made to list[] will be left smudged when this function\nreturns (this is true when there is no early return). \n\nIs that intended?\n\n\n"},{"id":"358571","messageId":"pull.39.v3.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-21T15:05:24Z","receivedAt":"2018-09-21T15:05:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As Peff reported [1], the refactored can_all_from_reach_with_flags() method\ndoes not properly peel tags. Since the helper method can_all_from_reach()\nand code in t/helper/test-reach.c all peel tags before getting to this\nmethod, it is not super-simple to create a test that demonstrates this.\n\nI modified t/helper/test-reach.c to allow calling\ncan_all_from_reach_with_flags() directly, and added a test in\nt6600-test-reach.sh that demonstrates the segfault without the fix.\n\nFor V2, I compared the loop that inspects the 'from' commits in commit\nba3ca1edce \"commit-reach: move can_all_from_reach_with_flags\" to the version\nhere and got the following diff:\n\n3c3\n< if (from_one->flags & assign_flag)\n---\n> if (!from_one || from_one->flags & assign_flag)\n5c5,7\n< from_one = deref_tag(the_repository, from_one, \"a from object\", 0);\n---\n>\n> from_one = deref_tag(the_repository, from_one,\n> \"a from object\", 0);\n14a17,22\n>\n> list[nr_commits] = (struct commit *)from_one;\n> if (parse_commit(list[nr_commits]) ||\n> list[nr_commits]->generation < min_generation)\n> return 0; /* is this a leak? */\n> nr_commits++;\n\nThis diff includes the early termination we had before 'deref_tag' and the\ncomment for why we can ignore non-commit objects.\n\n[1] \nhttps://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u\n\nDerrick Stolee (2):\n commit-reach: properly peel tags\n commit-reach: fix memory and flag leaks\n\n commit-reach.c | 41 ++++++++++++++++++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 79 insertions(+), 14 deletions(-)\n\n\nbase-commit: 6621c838743812aaba96e55cfec8524ea1144c2d\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/39\n\nRange-diff vs v2:\n\n 1: 4bf21204dd ! 1: 0a1e661271 commit-reach: properly peel tags\n @@ -53,8 +53,11 @@\n +\n +\t\tlist[nr_commits] = (struct commit *)from_one;\n +\t\tif (parse_commit(list[nr_commits]) ||\n -+\t\t list[nr_commits]->generation < min_generation)\n -+\t\t\treturn 0; /* is this a leak? */\n ++\t\t list[nr_commits]->generation < min_generation) {\n ++\t\t\tresult = 0;\n ++\t\t\tgoto cleanup;\n ++\t\t}\n ++\n +\t\tnr_commits++;\n \t}\n \n -: ---------- > 2: b2e0ee4978 commit-reach: fix memory and flag leaks\n\n-- \ngitgitgadget\n"},{"id":"358572","messageId":"0a1e661271660b1fab317aac3997589a94b7c98f.1537542323.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] commit-reach: properly peel tags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-21T15:05:26Z","receivedAt":"2018-09-21T15:05:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n\"commit-reach: make can_all_from_reach... linear\" but incorrectly\nassumed that all objects provided were commits. During a fetch\nnegotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\nto the 'from' array. The current code creates a segfault.\n\nAdd a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\nand add a test in t6600-test-reach.sh that demonstrates this segfault.\n\nCorrect the issue by peeling tags when investigating the initial list\nof objects in the 'from' array.\n\nSigned-off-by: Jeff King \nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 36 +++++++++++++++++++++++++++++-------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--\n 3 files changed, 74 insertions(+), 14 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 86715c103c..e748414d04 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,\n {\n \tstruct commit **list = NULL;\n \tint i;\n+\tint nr_commits;\n \tint result = 1;\n \n \tALLOC_ARRAY(list, from->nr);\n+\tnr_commits = 0;\n \tfor (i = 0; i < from->nr; i++) {\n-\t\tlist[i] = (struct commit *)from->objects[i].item;\n+\t\tstruct object *from_one = from->objects[i].item;\n \n-\t\tif (parse_commit(list[i]) ||\n-\t\t list[i]->generation < min_generation)\n-\t\t\treturn 0;\n+\t\tif (!from_one || from_one->flags & assign_flag)\n+\t\t\tcontinue;\n+\n+\t\tfrom_one = deref_tag(the_repository, from_one,\n+\t\t\t\t \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n+\t\t\t/* no way to tell if this is reachable by\n+\t\t\t * looking at the ancestry chain alone, so\n+\t\t\t * leave a note to ourselves not to worry about\n+\t\t\t * this object anymore.\n+\t\t\t */\n+\t\t\tfrom->objects[i].item->flags |= assign_flag;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tlist[nr_commits] = (struct commit *)from_one;\n+\t\tif (parse_commit(list[nr_commits]) ||\n+\t\t list[nr_commits]->generation < min_generation) {\n+\t\t\tresult = 0;\n+\t\t\tgoto cleanup;\n+\t\t}\n+\n+\t\tnr_commits++;\n \t}\n \n-\tQSORT(list, from->nr, compare_commits_by_gen);\n+\tQSORT(list, nr_commits, compare_commits_by_gen);\n \n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\t/* DFS from list[i] */\n \t\tstruct commit_list *stack = NULL;\n \n@@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t}\n \n cleanup:\n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\tclear_commit_marks(list[i], RESULT);\n \t\tclear_commit_marks(list[i], assign_flag);\n \t}\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex eb21103998..08d2ea68e8 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)\n \tstruct object_id oid_A, oid_B;\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n+\tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n \tstruct commit **X_array;\n \tint X_nr, X_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n-\t\tstruct object *o;\n+\t\tstruct object *orig;\n+\t\tstruct object *peeled;\n \t\tstruct commit *c;\n \t\tif (buf.len < 3)\n \t\t\tcontinue;\n@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)\n \t\tif (get_oid_committish(buf.buf + 2, &oid))\n \t\t\tdie(\"failed to resolve %s\", buf.buf + 2);\n \n-\t\to = parse_object(r, &oid);\n-\t\to = deref_tag_noverify(o);\n+\t\torig = parse_object(r, &oid);\n+\t\tpeeled = deref_tag_noverify(orig);\n \n-\t\tif (!o)\n+\t\tif (!peeled)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n \t\t\t buf.buf, oid_to_hex(&oid));\n \n-\t\tc = object_as_type(r, o, OBJ_COMMIT, 0);\n+\t\tc = object_as_type(r, peeled, OBJ_COMMIT, 0);\n \n \t\tif (!c)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\t\tcommit_list_insert(c, &X);\n \t\t\t\tALLOC_GROW(X_array, X_nr + 1, X_alloc);\n \t\t\t\tX_array[X_nr++] = c;\n+\t\t\t\tadd_object_array(orig, NULL, &X_obj);\n \t\t\t\tbreak;\n \n \t\t\tcase 'Y':\n@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)\n \t\tprint_sorted_commit_ids(list);\n \t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n \t\tprintf(\"%s(X,Y):%d\\n\", av[1], can_all_from_reach(X, Y, 1));\n+\t} else if (!strcmp(av[1], \"can_all_from_reach_with_flag\")) {\n+\t\tstruct commit_list *iter = Y;\n+\n+\t\twhile (iter) {\n+\t\t\titer->item->object.flags |= 2;\n+\t\t\titer = iter->next;\n+\t\t}\n+\n+\t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n \t} else if (!strcmp(av[1], \"commit_contains\")) {\n \t\tstruct ref_filter filter;\n \t\tstruct contains_cache cache;\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex d139a00d1d..ae94b27f70 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -31,7 +31,8 @@ test_expect_success 'setup' '\n \tfor i in $(test_seq 1 10)\n \tdo\n \t\ttest_commit \"1-$i\" &&\n-\t\tgit branch -f commit-1-$i\n+\t\tgit branch -f commit-1-$i &&\n+\t\tgit tag -a -m \"1-$i\" tag-1-$i commit-1-$i\n \tdone &&\n \tfor j in $(test_seq 1 9)\n \tdo\n@@ -39,11 +40,13 @@ test_expect_success 'setup' '\n \t\tx=$(($j + 1)) &&\n \t\ttest_commit \"$x-1\" &&\n \t\tgit branch -f commit-$x-1 &&\n+\t\tgit tag -a -m \"$x-1\" tag-$x-1 commit-$x-1 &&\n \n \t\tfor i in $(test_seq 2 10)\n \t\tdo\n \t\t\tgit merge commit-$j-$i -m \"$x-$i\" &&\n-\t\t\tgit branch -f commit-$x-$i\n+\t\t\tgit branch -f commit-$x-$i &&\n+\t\t\tgit tag -a -m \"$x-$i\" tag-$x-$i commit-$x-$i\n \t\tdone\n \tdone &&\n \tgit commit-graph write --reachable &&\n@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '\n \ttest_three_modes can_all_from_reach\n '\n \n+test_expect_success 'can_all_from_reach_with_flag: tags case' '\n+\tcat >input <<-\\EOF &&\n+\tX:tag-2-10\n+\tX:tag-3-9\n+\tX:tag-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:tag-1-9\n+\tY:tag-2-8\n+\tY:tag-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-7-3\n+\tY:commit-8-1\n+\tEOF\n+\techo \"can_all_from_reach_with_flag(X,_,_,0,0):1\" >expect &&\n+\ttest_three_modes can_all_from_reach_with_flag\n+'\n+\n test_expect_success 'commit_contains:hit' '\n \tcat >input <<-\\EOF &&\n \tA:commit-7-7\n-- \ngitgitgadget\n\n"},{"id":"358573","messageId":"b2e0ee49788bfbf2182df7a93694333568552962.1537542323.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 2/2] commit-reach: fix memory and flag leaks","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-21T15:05:27Z","receivedAt":"2018-09-21T15:05:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe can_all_from_reach_with_flag() method uses 'assign_flag' as a\nvalue we can use to mark objects temporarily during our commit walk.\nThe intent is that these flags are removed from all objects before\nreturning. However, this is not the case.\n\nThe 'from' array could also contain objects that are not commits, and\nwe mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\nsection that removes these markers.\n\nAlso, we forgot to free() the memory for 'list', so add that to the\n'cleanup' section.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex e748414d04..5a845440a9 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -626,6 +626,11 @@ cleanup:\n \t\tclear_commit_marks(list[i], RESULT);\n \t\tclear_commit_marks(list[i], assign_flag);\n \t}\n+\tfree(list);\n+\n+\tfor (i = 0; i < from->nr; i++)\n+\t\tfrom->objects[i].item->flags &= ~assign_flag;\n+\n \treturn result;\n }\n \n-- \ngitgitgadget\n"},{"id":"358689","messageId":"20180921235628.GA3437@sigill.intra.peff.net","threadId":"49328","inReplyTo":"0a1e661271660b1fab317aac3997589a94b7c98f.1537542323.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 1/2] commit-reach: properly peel tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-21T23:56:28Z","receivedAt":"2018-09-21T23:56:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote:\n\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 86715c103c..e748414d04 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> {\n> \tstruct commit **list = NULL;\n> \tint i;\n> +\tint nr_commits;\n> \tint result = 1;\n> \n> \tALLOC_ARRAY(list, from->nr);\n> +\tnr_commits = 0;\n> \tfor (i = 0; i < from->nr; i++) {\n> -\t\tlist[i] = (struct commit *)from->objects[i].item;\n> +\t\tstruct object *from_one = from->objects[i].item;\n> \n> -\t\tif (parse_commit(list[i]) ||\n> -\t\t list[i]->generation < min_generation)\n> -\t\t\treturn 0;\n> +\t\tif (!from_one || from_one->flags & assign_flag)\n> +\t\t\tcontinue;\n> +\n> +\t\tfrom_one = deref_tag(the_repository, from_one,\n> +\t\t\t\t \"a from object\", 0);\n> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> +\t\t\t/* no way to tell if this is reachable by\n> +\t\t\t * looking at the ancestry chain alone, so\n> +\t\t\t * leave a note to ourselves not to worry about\n> +\t\t\t * this object anymore.\n> +\t\t\t */\n\nA minor nit, but the original comment you restored here has a style\nviolation. Might be worth fixing up (but certainly not worth a re-roll\non its own).\n\n> +\t\t\tfrom->objects[i].item->flags |= assign_flag;\n\nOK, so here we mark the original tag with a flag...\n\n> +\n> +\t\tlist[nr_commits] = (struct commit *)from_one;\n> +\t\tif (parse_commit(list[nr_commits]) ||\n> +\t\t list[nr_commits]->generation < min_generation) {\n> +\t\t\tresult = 0;\n> +\t\t\tgoto cleanup;\n> +\t\t}\n\nAnd we jump to the cleanup here, but...\n\n> @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> \t}\n> \n> cleanup:\n> -\tfor (i = 0; i < from->nr; i++) {\n> +\tfor (i = 0; i < nr_commits; i++) {\n> \t\tclear_commit_marks(list[i], RESULT);\n> \t\tclear_commit_marks(list[i], assign_flag);\n\nThis walks over the items in the list array, which don't include the tag\nwe marked. Did we decide that's OK? I think it's actually how the\noriginal code behaved, too, but it seems funny. At the least we might\nwant to call it out in the commit message.\n\nShould we also be walking from->objects and clearing the flags from\nthere (maybe not RESULT, but assign_flag)? It's not clear to me if it's\nunintentional for those to be marked after the function leaves or not.\n\nAlso, a minor aside, but I think it would be slightly more efficient for\nthose final two lines to do:\n\n clear_commit_marks(list[i], RESULT | assign_flag);\n\nOf course, that's totally orthogonal to this patch, but it may make you\nfeel better to offset the other round of clearing I'm suggesting. ;)\n\n> diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\n> index eb21103998..08d2ea68e8 100644\n> --- a/t/helper/test-reach.c\n> +++ b/t/helper/test-reach.c\n\nThese bits all looked good to me.\n\n-Peff\n"},{"id":"358690","messageId":"20180921235803.GB3437@sigill.intra.peff.net","threadId":"49328","inReplyTo":"b2e0ee49788bfbf2182df7a93694333568552962.1537542323.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-21T23:58:03Z","receivedAt":"2018-09-21T23:58:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:\n\n> From: Derrick Stolee \n> \n> The can_all_from_reach_with_flag() method uses 'assign_flag' as a\n> value we can use to mark objects temporarily during our commit walk.\n> The intent is that these flags are removed from all objects before\n> returning. However, this is not the case.\n> \n> The 'from' array could also contain objects that are not commits, and\n> we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\n> section that removes these markers.\n> \n> Also, we forgot to free() the memory for 'list', so add that to the\n> 'cleanup' section.\n\nUrgh, ignore most of my response to patch 1, then. I saw there was a\npatch 2, but thought it was just handling the free().\n\nThe flag-clearing here makes perfect sense.\n\n-Peff\n"},{"id":"358752","messageId":"217bc485-2872-30c4-3344-2b5d0e754ae8@gmail.com","threadId":"49328","inReplyTo":"20180921235628.GA3437@sigill.intra.peff.net","subject":"Re: [PATCH v3 1/2] commit-reach: properly peel tags","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-09-24T11:48:04Z","receivedAt":"2018-09-24T11:48:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/21/2018 7:56 PM, Jeff King wrote:\n> On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote:\n> +\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n> +\t\t\t/* no way to tell if this is reachable by\n> +\t\t\t * looking at the ancestry chain alone, so\n> +\t\t\t * leave a note to ourselves not to worry about\n> +\t\t\t * this object anymore.\n> +\t\t\t */\n> A minor nit, but the original comment you restored here has a style\n> violation. Might be worth fixing up (but certainly not worth a re-roll\n> on its own).\n>\n>> @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n>> \t}\n>> \n>> cleanup:\n>> -\tfor (i = 0; i < from->nr; i++) {\n>> +\tfor (i = 0; i < nr_commits; i++) {\n>> \t\tclear_commit_marks(list[i], RESULT);\n>> \t\tclear_commit_marks(list[i], assign_flag);\n> Also, a minor aside, but I think it would be slightly more efficient for\n> those final two lines to do:\n>\n> clear_commit_marks(list[i], RESULT | assign_flag);\n>\n> Of course, that's totally orthogonal to this patch, but it may make you\n> feel better to offset the other round of clearing I'm suggesting. ;)\n\nThis is definitely a better thing to do, and I'll make the change in v4, \nalong with the comment style cleanup above.\n\nThanks,\n\n-Stolee\n\n\n"},{"id":"358766","messageId":"c8320650-230a-9a17-df79-9555d5214bd2@gmail.com","threadId":"49328","inReplyTo":"20180921235803.GB3437@sigill.intra.peff.net","subject":"Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-09-24T17:25:12Z","receivedAt":"2018-09-24T17:25:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/21/2018 7:58 PM, Jeff King wrote:\n> On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:\n>\n>> From: Derrick Stolee \n>>\n>> The can_all_from_reach_with_flag() method uses 'assign_flag' as a\n>> value we can use to mark objects temporarily during our commit walk.\n>> The intent is that these flags are removed from all objects before\n>> returning. However, this is not the case.\n>>\n>> The 'from' array could also contain objects that are not commits, and\n>> we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\n>> section that removes these markers.\n>>\n>> Also, we forgot to free() the memory for 'list', so add that to the\n>> 'cleanup' section.\n> Urgh, ignore most of my response to patch 1, then. I saw there was a\n> patch 2, but thought it was just handling the free().\n>\n> The flag-clearing here makes perfect sense.\n\nIn my local branch, I ended up squashing this commit into the previous, \nbecause I discovered clear_commit_marks_many() making the cleanup \nsection have this diff:\n\n@@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct \nobject_array *from,\n         }\n\n  cleanup:\n-       for (i = 0; i < from->nr; i++) {\n-               clear_commit_marks(list[i], RESULT);\n-               clear_commit_marks(list[i], assign_flag);\n-       }\n+       clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n+       free(list);\n+\n+       for (i = 0; i < from->nr; i++)\n+               from->objects[i].item->flags &= ~assign_flag;\n+\n         return result;\n  }\n\nWith the bigger change in the larger set, there is less reason to do \nseparate commits. (Plus, it confused you during review.)\n\nThanks,\n\n-Stolee\n\n\n"},{"id":"358773","messageId":"20180924190625.GA27029@sigill.intra.peff.net","threadId":"49328","inReplyTo":"c8320650-230a-9a17-df79-9555d5214bd2@gmail.com","subject":"Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-24T19:06:26Z","receivedAt":"2018-09-24T19:06:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 24, 2018 at 01:25:12PM -0400, Derrick Stolee wrote:\n\n> On 9/21/2018 7:58 PM, Jeff King wrote:\n> > On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:\n> > \n> > > From: Derrick Stolee \n> > > \n> > > The can_all_from_reach_with_flag() method uses 'assign_flag' as a\n> > > value we can use to mark objects temporarily during our commit walk.\n> > > The intent is that these flags are removed from all objects before\n> > > returning. However, this is not the case.\n> > > \n> > > The 'from' array could also contain objects that are not commits, and\n> > > we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\n> > > section that removes these markers.\n> > > \n> > > Also, we forgot to free() the memory for 'list', so add that to the\n> > > 'cleanup' section.\n> > Urgh, ignore most of my response to patch 1, then. I saw there was a\n> > patch 2, but thought it was just handling the free().\n> > \n> > The flag-clearing here makes perfect sense.\n> \n> In my local branch, I ended up squashing this commit into the previous,\n> because I discovered clear_commit_marks_many() making the cleanup section\n> have this diff:\n> \n> @@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array\n> *from,\n>         }\n> \n>  cleanup:\n> -       for (i = 0; i < from->nr; i++) {\n> -               clear_commit_marks(list[i], RESULT);\n> -               clear_commit_marks(list[i], assign_flag);\n> -       }\n> +       clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n> +       free(list);\n> +\n> +       for (i = 0; i < from->nr; i++)\n> +               from->objects[i].item->flags &= ~assign_flag;\n> +\n>         return result;\n>  }\n> \n> With the bigger change in the larger set, there is less reason to do\n> separate commits. (Plus, it confused you during review.)\n\nYeah, that looks better still. Thanks!\n\n-Peff\n"},{"id":"358782","messageId":"pull.39.v4.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-24T20:57:50Z","receivedAt":"2018-09-24T20:57:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As Peff reported [1], the refactored can_all_from_reach_with_flags() method\ndoes not properly peel tags. Since the helper method can_all_from_reach()\nand code in t/helper/test-reach.c all peel tags before getting to this\nmethod, it is not super-simple to create a test that demonstrates this.\n\nI modified t/helper/test-reach.c to allow calling\ncan_all_from_reach_with_flags() directly, and added a test in\nt6600-test-reach.sh that demonstrates the segfault without the fix.\n\nFor V2, I compared the loop that inspects the 'from' commits in commit\nba3ca1edce \"commit-reach: move can_all_from_reach_with_flags\" to the version\nhere and got the following diff:\n\n3c3\n< if (from_one->flags & assign_flag)\n---\n> if (!from_one || from_one->flags & assign_flag)\n5c5,7\n< from_one = deref_tag(the_repository, from_one, \"a from object\", 0);\n---\n>\n> from_one = deref_tag(the_repository, from_one,\n> \"a from object\", 0);\n14a17,22\n>\n> list[nr_commits] = (struct commit *)from_one;\n> if (parse_commit(list[nr_commits]) ||\n> list[nr_commits]->generation < min_generation)\n> return 0; /* is this a leak? */\n> nr_commits++;\n\nThis diff includes the early termination we had before 'deref_tag' and the\ncomment for why we can ignore non-commit objects.\n\n[1] \nhttps://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u\n\nDerrick Stolee (1):\n commit-reach: properly peel tags and clear flags\n\n commit-reach.c | 44 +++++++++++++++++++++++++++++++++----------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++--\n 3 files changed, 79 insertions(+), 17 deletions(-)\n\n\nbase-commit: 6621c838743812aaba96e55cfec8524ea1144c2d\nPublished-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/39\n\nRange-diff vs v3:\n\n 1: 0a1e661271 ! 1: a0a3cf0134 commit-reach: properly peel tags\n @@ -1,6 +1,6 @@\n Author: Derrick Stolee \n \n - commit-reach: properly peel tags\n + commit-reach: properly peel tags and clear flags\n \n The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n \"commit-reach: make can_all_from_reach... linear\" but incorrectly\n @@ -14,6 +14,19 @@\n Correct the issue by peeling tags when investigating the initial list\n of objects in the 'from' array.\n \n + The can_all_from_reach_with_flag() method uses 'assign_flag' as a\n + value we can use to mark objects temporarily during our commit walk.\n + The intent is that these flags are removed from all objects before\n + returning. However, this is not the case.\n +\n + The 'from' array could also contain objects that are not commits, and\n + we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\n + section that removes these markers.\n +\n + Also, we forgot to free() the memory for 'list', so add that to the\n + 'cleanup' section. Also, use a cleaner mechanism for clearing those\n + flags.\n +\n Signed-off-by: Jeff King \n Signed-off-by: Derrick Stolee \n \n @@ -74,10 +87,18 @@\n \n cleanup:\n -\tfor (i = 0; i < from->nr; i++) {\n -+\tfor (i = 0; i < nr_commits; i++) {\n - \t\tclear_commit_marks(list[i], RESULT);\n - \t\tclear_commit_marks(list[i], assign_flag);\n - \t}\n +-\t\tclear_commit_marks(list[i], RESULT);\n +-\t\tclear_commit_marks(list[i], assign_flag);\n +-\t}\n ++\tclear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n ++\tfree(list);\n ++\n ++\tfor (i = 0; i < from->nr; i++)\n ++\t\tfrom->objects[i].item->flags &= ~assign_flag;\n ++\n + \treturn result;\n + }\n + \n \n diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\n --- a/t/helper/test-reach.c\n 2: b2e0ee4978 < -: ---------- commit-reach: fix memory and flag leaks\n\n-- \ngitgitgadget\n"},{"id":"358783","messageId":"a0a3cf01343381281554d0e175b2f4ec5fbe0abb.1537822669.git.gitgitgadget@gmail.com","threadId":"49328","inReplyTo":"pull.39.v4.git.gitgitgadget@gmail.com","subject":"[PATCH v4 1/1] commit-reach: properly peel tags and clear flags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2018-09-24T20:57:52Z","receivedAt":"2018-09-24T20:57:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n\"commit-reach: make can_all_from_reach... linear\" but incorrectly\nassumed that all objects provided were commits. During a fetch\nnegotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\nto the 'from' array. The current code creates a segfault.\n\nAdd a direct call to can_all_from_reach_with_flag() in 'test-tool reach'\nand add a test in t6600-test-reach.sh that demonstrates this segfault.\n\nCorrect the issue by peeling tags when investigating the initial list\nof objects in the 'from' array.\n\nThe can_all_from_reach_with_flag() method uses 'assign_flag' as a\nvalue we can use to mark objects temporarily during our commit walk.\nThe intent is that these flags are removed from all objects before\nreturning. However, this is not the case.\n\nThe 'from' array could also contain objects that are not commits, and\nwe mark those objects with 'assign_flag'. Add a loop to the 'cleanup'\nsection that removes these markers.\n\nAlso, we forgot to free() the memory for 'list', so add that to the\n'cleanup' section. Also, use a cleaner mechanism for clearing those\nflags.\n\nSigned-off-by: Jeff King \nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 44 +++++++++++++++++++++++++++++++++----------\n t/helper/test-reach.c | 22 +++++++++++++++++-----\n t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++--\n 3 files changed, 79 insertions(+), 17 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 86715c103c..db84f85986 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,\n {\n \tstruct commit **list = NULL;\n \tint i;\n+\tint nr_commits;\n \tint result = 1;\n \n \tALLOC_ARRAY(list, from->nr);\n+\tnr_commits = 0;\n \tfor (i = 0; i < from->nr; i++) {\n-\t\tlist[i] = (struct commit *)from->objects[i].item;\n+\t\tstruct object *from_one = from->objects[i].item;\n \n-\t\tif (parse_commit(list[i]) ||\n-\t\t list[i]->generation < min_generation)\n-\t\t\treturn 0;\n+\t\tif (!from_one || from_one->flags & assign_flag)\n+\t\t\tcontinue;\n+\n+\t\tfrom_one = deref_tag(the_repository, from_one,\n+\t\t\t\t \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n+\t\t\t/* no way to tell if this is reachable by\n+\t\t\t * looking at the ancestry chain alone, so\n+\t\t\t * leave a note to ourselves not to worry about\n+\t\t\t * this object anymore.\n+\t\t\t */\n+\t\t\tfrom->objects[i].item->flags |= assign_flag;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tlist[nr_commits] = (struct commit *)from_one;\n+\t\tif (parse_commit(list[nr_commits]) ||\n+\t\t list[nr_commits]->generation < min_generation) {\n+\t\t\tresult = 0;\n+\t\t\tgoto cleanup;\n+\t\t}\n+\n+\t\tnr_commits++;\n \t}\n \n-\tQSORT(list, from->nr, compare_commits_by_gen);\n+\tQSORT(list, nr_commits, compare_commits_by_gen);\n \n-\tfor (i = 0; i < from->nr; i++) {\n+\tfor (i = 0; i < nr_commits; i++) {\n \t\t/* DFS from list[i] */\n \t\tstruct commit_list *stack = NULL;\n \n@@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t}\n \n cleanup:\n-\tfor (i = 0; i < from->nr; i++) {\n-\t\tclear_commit_marks(list[i], RESULT);\n-\t\tclear_commit_marks(list[i], assign_flag);\n-\t}\n+\tclear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n+\tfree(list);\n+\n+\tfor (i = 0; i < from->nr; i++)\n+\t\tfrom->objects[i].item->flags &= ~assign_flag;\n+\n \treturn result;\n }\n \ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex eb21103998..08d2ea68e8 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)\n \tstruct object_id oid_A, oid_B;\n \tstruct commit *A, *B;\n \tstruct commit_list *X, *Y;\n+\tstruct object_array X_obj = OBJECT_ARRAY_INIT;\n \tstruct commit **X_array;\n \tint X_nr, X_alloc;\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)\n \n \twhile (strbuf_getline(&buf, stdin) != EOF) {\n \t\tstruct object_id oid;\n-\t\tstruct object *o;\n+\t\tstruct object *orig;\n+\t\tstruct object *peeled;\n \t\tstruct commit *c;\n \t\tif (buf.len < 3)\n \t\t\tcontinue;\n@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)\n \t\tif (get_oid_committish(buf.buf + 2, &oid))\n \t\t\tdie(\"failed to resolve %s\", buf.buf + 2);\n \n-\t\to = parse_object(r, &oid);\n-\t\to = deref_tag_noverify(o);\n+\t\torig = parse_object(r, &oid);\n+\t\tpeeled = deref_tag_noverify(orig);\n \n-\t\tif (!o)\n+\t\tif (!peeled)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n \t\t\t buf.buf, oid_to_hex(&oid));\n \n-\t\tc = object_as_type(r, o, OBJ_COMMIT, 0);\n+\t\tc = object_as_type(r, peeled, OBJ_COMMIT, 0);\n \n \t\tif (!c)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\t\tcommit_list_insert(c, &X);\n \t\t\t\tALLOC_GROW(X_array, X_nr + 1, X_alloc);\n \t\t\t\tX_array[X_nr++] = c;\n+\t\t\t\tadd_object_array(orig, NULL, &X_obj);\n \t\t\t\tbreak;\n \n \t\t\tcase 'Y':\n@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)\n \t\tprint_sorted_commit_ids(list);\n \t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n \t\tprintf(\"%s(X,Y):%d\\n\", av[1], can_all_from_reach(X, Y, 1));\n+\t} else if (!strcmp(av[1], \"can_all_from_reach_with_flag\")) {\n+\t\tstruct commit_list *iter = Y;\n+\n+\t\twhile (iter) {\n+\t\t\titer->item->object.flags |= 2;\n+\t\t\titer = iter->next;\n+\t\t}\n+\n+\t\tprintf(\"%s(X,_,_,0,0):%d\\n\", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));\n \t} else if (!strcmp(av[1], \"commit_contains\")) {\n \t\tstruct ref_filter filter;\n \t\tstruct contains_cache cache;\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex d139a00d1d..ae94b27f70 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -31,7 +31,8 @@ test_expect_success 'setup' '\n \tfor i in $(test_seq 1 10)\n \tdo\n \t\ttest_commit \"1-$i\" &&\n-\t\tgit branch -f commit-1-$i\n+\t\tgit branch -f commit-1-$i &&\n+\t\tgit tag -a -m \"1-$i\" tag-1-$i commit-1-$i\n \tdone &&\n \tfor j in $(test_seq 1 9)\n \tdo\n@@ -39,11 +40,13 @@ test_expect_success 'setup' '\n \t\tx=$(($j + 1)) &&\n \t\ttest_commit \"$x-1\" &&\n \t\tgit branch -f commit-$x-1 &&\n+\t\tgit tag -a -m \"$x-1\" tag-$x-1 commit-$x-1 &&\n \n \t\tfor i in $(test_seq 2 10)\n \t\tdo\n \t\t\tgit merge commit-$j-$i -m \"$x-$i\" &&\n-\t\t\tgit branch -f commit-$x-$i\n+\t\t\tgit branch -f commit-$x-$i &&\n+\t\t\tgit tag -a -m \"$x-$i\" tag-$x-$i commit-$x-$i\n \t\tdone\n \tdone &&\n \tgit commit-graph write --reachable &&\n@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '\n \ttest_three_modes can_all_from_reach\n '\n \n+test_expect_success 'can_all_from_reach_with_flag: tags case' '\n+\tcat >input <<-\\EOF &&\n+\tX:tag-2-10\n+\tX:tag-3-9\n+\tX:tag-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:tag-1-9\n+\tY:tag-2-8\n+\tY:tag-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-7-3\n+\tY:commit-8-1\n+\tEOF\n+\techo \"can_all_from_reach_with_flag(X,_,_,0,0):1\" >expect &&\n+\ttest_three_modes can_all_from_reach_with_flag\n+'\n+\n test_expect_success 'commit_contains:hit' '\n \tcat >input <<-\\EOF &&\n \tA:commit-7-7\n-- \ngitgitgadget\n"},{"id":"358790","messageId":"20180924210933.GC6255@sigill.intra.peff.net","threadId":"49328","inReplyTo":"a0a3cf01343381281554d0e175b2f4ec5fbe0abb.1537822669.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-09-24T21:09:33Z","receivedAt":"2018-09-24T21:09:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 24, 2018 at 01:57:52PM -0700, Derrick Stolee via GitGitGadget wrote:\n\n> From: Derrick Stolee \n> \n> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e\n> \"commit-reach: make can_all_from_reach... linear\" but incorrectly\n> assumed that all objects provided were commits. During a fetch\n> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags\n> to the 'from' array. The current code creates a segfault.\n> [...]\n\nThanks, this version looks good to me.\n\n-Peff\n"},{"id":"358818","messageId":"CAPig+cTT9cpDPyWugg8WNmCdA7OhEOxVxTxD3FRhpf7Sgdg-zA@mail.gmail.com","threadId":"49328","inReplyTo":"a0a3cf01343381281554d0e175b2f4ec5fbe0abb.1537822669.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-09-25T05:17:12Z","receivedAt":"2018-09-25T05:17:26Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Mon, Sep 24, 2018 at 4:58 PM Derrick Stolee via GitGitGadget\n wrote:\n> diff --git a/commit-reach.c b/commit-reach.c\n> @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> {\n> + from_one = deref_tag(the_repository, from_one,\n> + \"a from object\", 0);\n> + if (!from_one || from_one->type != OBJ_COMMIT) {\n> + /* no way to tell if this is reachable by\n> + * looking at the ancestry chain alone, so\n> + * leave a note to ourselves not to worry about\n> + * this object anymore.\n> + */\n\nStyle nit:\n\n /*\n * Multi-line comment\n * formatting.\n */\n"},{"id":"358832","messageId":"20180925132741.223513-1-dstolee@microsoft.com","threadId":"49328","inReplyTo":"pull.39.v4.git.gitgitgadget@gmail.com","subject":"[PATCH] commit-reach: cleanups in can_all_from_reach...","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-09-25T13:27:41Z","receivedAt":"2018-09-25T13:28:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nDue to a regression introduced by 4fbcca4e \"commit-reach: make\ncan_all_from_reach... linear\" the series including b67f6b26\n\"commit-reach: properly peel tags\" was merged to master quickly.\n\nThere were a few more cleanups left to apply in the series, which\nare included by this change:\n\n1. Clean up a comment that is in the incorrect style.\n\n2. Replace multiple calls to clear_commit_marks() with one call to\n clear_commit_marks_many().\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5a845440a9..66aa41262c 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -558,7 +558,8 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t\tfrom_one = deref_tag(the_repository, from_one,\n \t\t\t\t \"a from object\", 0);\n \t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n-\t\t\t/* no way to tell if this is reachable by\n+\t\t\t/*\n+\t\t\t * no way to tell if this is reachable by\n \t\t\t * looking at the ancestry chain alone, so\n \t\t\t * leave a note to ourselves not to worry about\n \t\t\t * this object anymore.\n@@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \t}\n \n cleanup:\n-\tfor (i = 0; i < nr_commits; i++) {\n-\t\tclear_commit_marks(list[i], RESULT);\n-\t\tclear_commit_marks(list[i], assign_flag);\n-\t}\n+\tclear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n \tfree(list);\n \n \tfor (i = 0; i < from->nr; i++)\n\nbase-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b\n-- \n2.19.0\n\n"},{"id":"358850","messageId":"xmqqwor9pi3i.fsf@gitster-ct.c.googlers.com","threadId":"49328","inReplyTo":"20180925132741.223513-1-dstolee@microsoft.com","subject":"Re: [PATCH] commit-reach: cleanups in can_all_from_reach...","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-25T18:06:25Z","receivedAt":"2018-09-25T18:06:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> \t}\n> \n> cleanup:\n> -\tfor (i = 0; i < nr_commits; i++) {\n> -\t\tclear_commit_marks(list[i], RESULT);\n> -\t\tclear_commit_marks(list[i], assign_flag);\n> -\t}\n> +\tclear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n> \tfree(list);\n> \n> \tfor (i = 0; i < from->nr; i++)\n>\n> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b\n\nThis change looks good to me. \n\nThis is a tangent, but while re-reading clear_commit_marks() and its\nhelpers to refresh my memory, I found that the bottom-most helper in\nthe callchain was written in a very confusing way, but it is not a\nfault of this clean-up. I however suspect that it would not help us\nall that much to use clear_commit_marks_many() with its current\nimplementation. It first clears all commits on the first-parent\nchain from each list[] element, while accumulating the parent\ncommits that are yet to be processed in a commit_list in LIFO order,\nand then consumes these accumulated side parents the same way. We\nprobably would benefit by rewriting clear_commit_marks_many() to\ntraverse from all the tips given in list[] taking advantage of the\ngeneration numbers, using a prio queue to manage the commits\nyet-to-be-cleared, or something.\n"},{"id":"358851","messageId":"08b67726-8af6-34f9-6c4f-6a1be7d81b90@gmail.com","threadId":"49328","inReplyTo":"xmqqwor9pi3i.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] commit-reach: cleanups in can_all_from_reach...","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-09-25T18:13:16Z","receivedAt":"2018-09-25T18:13:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/25/2018 2:06 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n>> \t}\n>> \n>> cleanup:\n>> -\tfor (i = 0; i < nr_commits; i++) {\n>> -\t\tclear_commit_marks(list[i], RESULT);\n>> -\t\tclear_commit_marks(list[i], assign_flag);\n>> -\t}\n>> +\tclear_commit_marks_many(nr_commits, list, RESULT | assign_flag);\n>> \tfree(list);\n>> \n>> \tfor (i = 0; i < from->nr; i++)\n>>\n>> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b\n> This change looks good to me.\n>\n> This is a tangent, but while re-reading clear_commit_marks() and its\n> helpers to refresh my memory, I found that the bottom-most helper in\n> the callchain was written in a very confusing way, but it is not a\n> fault of this clean-up. I however suspect that it would not help us\n> all that much to use clear_commit_marks_many() with its current\n> implementation. It first clears all commits on the first-parent\n> chain from each list[] element, while accumulating the parent\n> commits that are yet to be processed in a commit_list in LIFO order,\n> and then consumes these accumulated side parents the same way. We\n> probably would benefit by rewriting clear_commit_marks_many() to\n> traverse from all the tips given in list[] taking advantage of the\n> generation numbers, using a prio queue to manage the commits\n> yet-to-be-cleared, or something.\n\nAnother commit walk that could be improved by generation numbers? It's \nlike my bat-signal!\n\nThanks for pointing me in that direction. I'll take a look.\n\n-Stolee\n\n"},{"id":"358868","messageId":"xmqqh8idpbho.fsf@gitster-ct.c.googlers.com","threadId":"49328","inReplyTo":"08b67726-8af6-34f9-6c4f-6a1be7d81b90@gmail.com","subject":"Re: [PATCH] commit-reach: cleanups in can_all_from_reach...","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-09-25T20:29:07Z","receivedAt":"2018-09-25T20:29:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Another commit walk that could be improved by generation numbers? It's\n> like my bat-signal!\n\nAh, nevermind. The \"traversal\" done by these helper functions is\nthe most stupid kind (not the algorthim, but the need). It's not\nlike there is an opportunity to optimize by not traversing the\nremainder if we choose the order of traversal intelligently, so any\nalgorithm that does not visit the same node twice and does not do\nthe most naive recursion would work, and what we currently have\nthere is just fine.\n"}]}