{"thread":{"id":"42515","subject":"[PATCH 0/2] corner cases with \"rev-list --use-bitmap-index -n\"","startedAt":"2016-06-02T23:09:25Z","lastAt":"2016-06-03T07:08:05Z","messageCount":6,"participants":["Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"288176","messageId":"20160602230925.GA11196@sigill.intra.peff.net","threadId":"42515","inReplyTo":null,"subject":"[PATCH 0/2] corner cases with \"rev-list --use-bitmap-index -n\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-02T23:09:25Z","receivedAt":"2016-06-02T23:09:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This series fixes two corner-cases I found when using \"-n\" along with\nbitmaps. The results do make _some_ sense if you interpret them\ncorrectly, but are sufficiently confusing that I think it's worth\ndealing with. See the commit messages for the gory details.\n\nThe good news is that in the first case, we can produce a more sensible\nanswer without spending any extra work.\n\nThe bad news is that the second case cannot, and must fall back to a\nregular traversal. I doubt anybody even cares about this case in\npractice, though, as \"--objects -n\" is somewhat nonsensical already (I\ndidn't run across it in practice; I only noticed while I fixing the\nfirst one, which I did see in practice).\n\n  [1/2]: rev-list: \"adjust\" results of \"--count --use-bitmap-index -n\"\n  [2/2]: rev-list: disable bitmaps when \"-n\" is used with listing objects\n\n-Peff\n"},{"id":"288177","messageId":"20160602231031.GA11247@sigill.intra.peff.net","threadId":"42515","inReplyTo":"20160602230925.GA11196@sigill.intra.peff.net","subject":"[PATCH 1/2] rev-list: \"adjust\" results of \"--count --use-bitmap-index -n\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-02T23:10:31Z","receivedAt":"2016-06-02T23:10:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If you ask rev-list for:\n\n    git rev-list --count --use-bitmap-index HEAD\n\nwe optimize out the actual traversal and just give you the\nnumber of bits set in the commit bitmap. This is faster,\nwhich is good.\n\nBut if you ask to limit the size of the traversal, like:\n\n    git rev-list --count --use-bitmap-index -n 100 HEAD\n\nwe'll still output the full bitmapped number we found. On\nthe surface, that might even seem OK. You explicitly asked\nto use the bitmap index, and it was cheap to compute the\nreal answer, so we gave it to you.\n\nBut there's something much more complicated going on under\nthe hood. If we don't have a bitmap directly for HEAD, then\nwe have to actually traverse backwards, looking for a\nbitmapped commit. And _that_ traversal is bounded by our\n`-n` count.\n\nThis is a good thing, because it bounds the work we have to\ndo, which is probably what the user wanted by asking for\n`-n`. But now it makes the output quite confusing. You might\nget many values:\n\n  - your `-n` value, if we walked back and never found a\n    bitmap (or fewer if there weren't that many commits)\n\n  - the actual full count, if we found a bitmap root for\n    every path of our traversal with in the `-n` limit\n\n  - any number in between! We might have walked back and\n    found _some_ bitmaps, but then cut off the traversal\n    early with some commits not accounted for in the result.\n\nSo you cannot even see a value higher than your `-n` and say\n\"OK, bitmaps kicked in, this must be the real full count\".\nThe only sane thing is for git to just clamp the value to a\nmaximum of the `-n` value, which means we should output the\nexact same results whether bitmaps are in use or not.\n\nThe test in t5310 demonstrates this by using `-n 1`.\nWithout this patch we fail in the full-bitmap case (where we\ndo not have to traverse at all) but _not_ in the\npartial-bitmap case (where we have to walk down to find an\nactual bitmap). With this patch, both cases just work.\n\nI didn't implement the crazy in-between case, just because\nit's complicated to set up, and is really a subset of the\nfull-count case, which we do cover.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/rev-list.c      | 2 ++\n t/t5310-pack-bitmaps.sh | 6 ++++++\n 2 files changed, 8 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 275da0d..aaa79a3 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -360,6 +360,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\tuint32_t commit_count;\n \t\t\tif (!prepare_bitmap_walk(&revs)) {\n \t\t\t\tcount_bitmap_commit_list(&commit_count, NULL, NULL, NULL);\n+\t\t\t\tif (revs.max_count && revs.max_count < commit_count)\n+\t\t\t\t\tcommit_count = revs.max_count;\n \t\t\t\tprintf(\"%d\\n\", commit_count);\n \t\t\t\treturn 0;\n \t\t\t}\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex d446706..3893afd 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -47,6 +47,12 @@ rev_list_tests() {\n \t\ttest_cmp expect actual\n \t'\n \n+\ttest_expect_success \"counting commits with limit ($state)\" '\n+\t\tgit rev-list --count -n 1 HEAD >expect &&\n+\t\tgit rev-list --use-bitmap-index --count -n 1 HEAD >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+\n \ttest_expect_success \"counting non-linear history ($state)\" '\n \t\tgit rev-list --count other...master >expect &&\n \t\tgit rev-list --use-bitmap-index --count other...master >actual &&\n-- \n2.9.0.rc1.132.g33c7f30\n"},{"id":"288178","messageId":"20160602231049.GB11247@sigill.intra.peff.net","threadId":"42515","inReplyTo":"20160602230925.GA11196@sigill.intra.peff.net","subject":"[PATCH 2/2] rev-list: disable bitmaps when \"-n\" is used with listing objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-02T23:10:49Z","receivedAt":"2016-06-02T23:10:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"You can ask rev-list to use bitmaps to speed up an --objects\ntraversal, which should generally give you your answers much\nfaster.\n\nLikewise, you can ask rev-list to limit such a traversal\nwith `-n`, in which case we'll show only a limited set of\ncommits (and only the tree and commit objects directly\nreachable from those commits).\n\nBut if you do both together, the results are nonsensical. We\nend up limiting any fallback traversal we do to _find_ the\nbitmaps, but the actual set of objects we output will be\npicked arbitrarily from the union of any bitmaps we do find,\nand will involve the objects of many more commits.\n\nIt's possible that somebody might want this as a \"show me\nwhat you can, but limit the amount of work you do\" flag.\nBut as with the prior commit clamping \"--count\", the results\nare basically non-deterministic; you'll get the values from\nsome commits between `n` and the total number, and you can't\ntell which.\n\nAnd unlike the `--count` case, we can't easily generate the\n\"real\" value from the bitmap values (you can't just walk\nback `-n` commits and subtract out the reachable objects\nfrom the boundary commits; the bitmaps for `X` record its\ntotal reachability, so you don't know which objects are\ndirectly from `X` itself, which from `X^`, and so on).\n\nSo let's just fallback to the non-bitmap code path in this\ncase, so we always give a sane answer.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/rev-list.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex aaa79a3..9fb6608 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -365,7 +365,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\t\tprintf(\"%d\\n\", commit_count);\n \t\t\t\treturn 0;\n \t\t\t}\n-\t\t} else if (revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n+\t\t} else if (!revs.max_count &&\n+\t\t\t   revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n \t\t\tif (!prepare_bitmap_walk(&revs)) {\n \t\t\t\ttraverse_bitmap_commit_list(&show_object_fast);\n \t\t\t\treturn 0;\n-- \n2.9.0.rc1.132.g33c7f30\n"},{"id":"288193","messageId":"20160603070649.GA24120@sigill.intra.peff.net","threadId":"42515","inReplyTo":"20160602231031.GA11247@sigill.intra.peff.net","subject":"[PATCH v2 0/2] corner cases with \"rev-list --use-bitmap-index -n\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-03T07:06:49Z","receivedAt":"2016-06-03T07:06:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 02, 2016 at 07:10:31PM -0400, Jeff King wrote:\n\n> diff --git a/builtin/rev-list.c b/builtin/rev-list.c\n> index 275da0d..aaa79a3 100644\n> --- a/builtin/rev-list.c\n> +++ b/builtin/rev-list.c\n> @@ -360,6 +360,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n>  \t\t\tuint32_t commit_count;\n>  \t\t\tif (!prepare_bitmap_walk(&revs)) {\n>  \t\t\t\tcount_bitmap_commit_list(&commit_count, NULL, NULL, NULL);\n> +\t\t\t\tif (revs.max_count && revs.max_count < commit_count)\n> +\t\t\t\t\tcommit_count = revs.max_count;\n\n...aaaaand this patch is totally wrong. For one thing, the \"not set\"\nsentinel value for max_count is \"-1\", not \"0\", so it didn't kick in for\n\"-n0\".\n\nAnd for another, any fallback traversal will actually decrement\nrevs.max_count, so we have to save the value before traversing.\n\nAnd as luck would have it, those two bugs cancel each other out in many\ncases (including the ones in the test suite!). If you pass \"-n1\", gets\ndecremented to \"0\".  That would give us a bogus adjustment, but instead\nwe decide that \"0\" means no adjustement is necessary, and return the\nnumber of commits we traversed, which is the right answer as long as we\ndidn't hit any bitmaps on the way down (or we hit one right away, in\nwhich case we didn't decrement at all).\n\nUpdated patches in a moment (the second has the same sentinel problem,\ntoo).\n\n-Peff\n"},{"id":"288194","messageId":"20160603070733.GA29852@sigill.intra.peff.net","threadId":"42515","inReplyTo":"20160603070649.GA24120@sigill.intra.peff.net","subject":"[PATCH v2 1/2] rev-list: \"adjust\" results of \"--count --use-bitmap-index -n\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-03T07:07:34Z","receivedAt":"2016-06-03T07:07:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If you ask rev-list for:\n\n    git rev-list --count --use-bitmap-index HEAD\n\nwe optimize out the actual traversal and just give you the\nnumber of bits set in the commit bitmap. This is faster,\nwhich is good.\n\nBut if you ask to limit the size of the traversal, like:\n\n    git rev-list --count --use-bitmap-index -n 100 HEAD\n\nwe'll still output the full bitmapped number we found. On\nthe surface, that might even seem OK. You explicitly asked\nto use the bitmap index, and it was cheap to compute the\nreal answer, so we gave it to you.\n\nBut there's something much more complicated going on under\nthe hood. If we don't have a bitmap directly for HEAD, then\nwe have to actually traverse backwards, looking for a\nbitmapped commit. And _that_ traversal is bounded by our\n`-n` count.\n\nThis is a good thing, because it bounds the work we have to\ndo, which is probably what the user wanted by asking for\n`-n`. But now it makes the output quite confusing. You might\nget many values:\n\n  - your `-n` value, if we walked back and never found a\n    bitmap (or fewer if there weren't that many commits)\n\n  - the actual full count, if we found a bitmap root for\n    every path of our traversal with in the `-n` limit\n\n  - any number in between! We might have walked back and\n    found _some_ bitmaps, but then cut off the traversal\n    early with some commits not accounted for in the result.\n\nSo you cannot even see a value higher than your `-n` and say\n\"OK, bitmaps kicked in, this must be the real full count\".\nThe only sane thing is for git to just clamp the value to a\nmaximum of the `-n` value, which means we should output the\nexact same results whether bitmaps are in use or not.\n\nThe test in t5310 demonstrates this by using `-n 1`.\nWithout this patch we fail in the full-bitmap case (where we\ndo not have to traverse at all) but _not_ in the\npartial-bitmap case (where we have to walk down to find an\nactual bitmap). With this patch, both cases just work.\n\nI didn't implement the crazy in-between case, just because\nit's complicated to set up, and is really a subset of the\nfull-count case, which we do cover.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/rev-list.c      | 3 +++\n t/t5310-pack-bitmaps.sh | 6 ++++++\n 2 files changed, 9 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 275da0d..b29f8fc 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -358,8 +358,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (use_bitmap_index && !revs.prune) {\n \t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n \t\t\tuint32_t commit_count;\n+\t\t\tint max_count = revs.max_count;\n \t\t\tif (!prepare_bitmap_walk(&revs)) {\n \t\t\t\tcount_bitmap_commit_list(&commit_count, NULL, NULL, NULL);\n+\t\t\t\tif (max_count >= 0 && max_count < commit_count)\n+\t\t\t\t\tcommit_count = max_count;\n \t\t\t\tprintf(\"%d\\n\", commit_count);\n \t\t\t\treturn 0;\n \t\t\t}\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex d446706..3893afd 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -47,6 +47,12 @@ rev_list_tests() {\n \t\ttest_cmp expect actual\n \t'\n \n+\ttest_expect_success \"counting commits with limit ($state)\" '\n+\t\tgit rev-list --count -n 1 HEAD >expect &&\n+\t\tgit rev-list --use-bitmap-index --count -n 1 HEAD >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+\n \ttest_expect_success \"counting non-linear history ($state)\" '\n \t\tgit rev-list --count other...master >expect &&\n \t\tgit rev-list --use-bitmap-index --count other...master >actual &&\n-- \n2.9.0.rc1.132.g33c7f30\n"},{"id":"288195","messageId":"20160603070805.GB29852@sigill.intra.peff.net","threadId":"42515","inReplyTo":"20160603070649.GA24120@sigill.intra.peff.net","subject":"[PATCH v2 2/2] rev-list: disable bitmaps when \"-n\" is used with listing objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-03T07:08:05Z","receivedAt":"2016-06-03T07:08:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"You can ask rev-list to use bitmaps to speed up an --objects\ntraversal, which should generally give you your answers much\nfaster.\n\nLikewise, you can ask rev-list to limit such a traversal\nwith `-n`, in which case we'll show only a limited set of\ncommits (and only the tree and commit objects directly\nreachable from those commits).\n\nBut if you do both together, the results are nonsensical. We\nend up limiting any fallback traversal we do to _find_ the\nbitmaps, but the actual set of objects we output will be\npicked arbitrarily from the union of any bitmaps we do find,\nand will involve the objects of many more commits.\n\nIt's possible that somebody might want this as a \"show me\nwhat you can, but limit the amount of work you do\" flag.\nBut as with the prior commit clamping \"--count\", the results\nare basically non-deterministic; you'll get the values from\nsome commits between `n` and the total number, and you can't\ntell which.\n\nAnd unlike the `--count` case, we can't easily generate the\n\"real\" value from the bitmap values (you can't just walk\nback `-n` commits and subtract out the reachable objects\nfrom the boundary commits; the bitmaps for `X` record its\ntotal reachability, so you don't know which objects are\ndirectly from `X` itself, which from `X^`, and so on).\n\nSo let's just fallback to the non-bitmap code path in this\ncase, so we always give a sane answer.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/rev-list.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex b29f8fc..b82bcc3 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -366,7 +366,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\t\tprintf(\"%d\\n\", commit_count);\n \t\t\t\treturn 0;\n \t\t\t}\n-\t\t} else if (revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n+\t\t} else if (revs.max_count < 0 &&\n+\t\t\t   revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n \t\t\tif (!prepare_bitmap_walk(&revs)) {\n \t\t\t\ttraverse_bitmap_commit_list(&show_object_fast);\n \t\t\t\treturn 0;\n-- \n2.9.0.rc1.132.g33c7f30\n"}]}