{"thread":{"id":"60113","subject":"[Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","startedAt":"2023-08-15T16:45:34Z","lastAt":"2023-08-16T21:00:23Z","messageCount":8,"participants":["Karthik Nayak","Junio C Hamano","Taylor Blau"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"480677","messageId":"CAOLa=ZQmjroDiOcUsu_MHtQ-88QHU9qeZPOPh+KJJ3dFoF2q0A@mail.gmail.com","threadId":"60113","inReplyTo":null,"subject":"[Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2023-08-15T16:44:18Z","receivedAt":"2023-08-15T16:45:34Z","isPatch":false,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Hello!\n\nWhat did you do before the bug happened? (Steps to reproduce your issue)\n\nAssume a repository structure as follows:\n\n- commit1 9f2aa2eb987c2281bb4901dbccd1398ad2c39722\n  - tree: 205f6b799e7d5c2524468ca006a0131aa57ecce7\n    - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n      - content: foo\n- commit2 9e02481f4df3a8997335b0a68882580e3b9b588f (parent:\n9f2aa2eb987c2281bb4901dbccd1398ad2c39722)\n  - tree: 672d0aa883d095369c56416587bc397eee4ac37e\n    - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n      - content: foo\n    - 100644 blob eec8c88a93f6ee1515fb8348f2c122cfda4302cd    moo\n      - content: moo\n- commit3 91fa9611a355db77a07f963c746d57f75af380da (parent:\n9e02481f4df3a8997335b0a68882580e3b9b588f)\n   - tree 0c16a6cc9eef3fdd3034c1ffe2fc5e6d0bba2192\n     - tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n       - 100644 blob 7a67abed5f99fdd3ee203dd137b9818d88b1bafd    goo\n         - content: goo\n     - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n       - content: foo\n     - 100644 blob eec8c88a93f6ee1515fb8348f2c122cfda4302cd    moo\n       - content: moo\n     - 100644 blob 8baef1b4abc478178b004d62031cf7fe6db6f903    abc\n       - content: abc\n- commit4 6b52ed5b176604a0740689b5bb9be7bd79f4bced (parent:\n9f2aa2eb987c2281bb4901dbccd1398ad2c39722)\n  - tree ff05824d2f76436c61d2c971e11a27514aba6948\n    - tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n      - 100644 blob 7a67abed5f99fdd3ee203dd137b9818d88b1bafd    goo\n        - content: goo\n    - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n      - content: foo\n    - 100644 blob 8baef1b4abc478178b004d62031cf7fe6db6f903    abc\n      - content: abc\n\nWhat did you expect to happen? (Expected behavior)\n\nIn such a repository, the output for the command, should have the\noutput provided below\n\n❯ git rev-list --objects 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n--not 91fa9611a355db77a07f963c746d57f75af380da\n6b52ed5b176604a0740689b5bb9be7bd79f4bced\nff05824d2f76436c61d2c971e11a27514aba6948\n\nWhat happened instead? (Actual behavior)\n\nInstead, the output is as follows:\n\n❯ git rev-list --objects 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n--not 91fa9611a355db77a07f963c746d57f75af380da\n6b52ed5b176604a0740689b5bb9be7bd79f4bced\nff05824d2f76436c61d2c971e11a27514aba6948\n8baef1b4abc478178b004d62031cf7fe6db6f903 abc\n086885f71429e3599c8c903b0e9ed491f6522879 bar\n7a67abed5f99fdd3ee203dd137b9818d88b1bafd bar/goo\n\nWhat's different between what you expected and what actually happened?\n\nIf you notice here, the objects\n`8baef1b4abc478178b004d62031cf7fe6db6f903`,\n`086885f71429e3599c8c903b0e9ed491f6522879` and\n`7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,\nthese objects are reachable from\n`91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been\nincluded since we used the `--not` flag.\n\nAnything else you want to add:\n\nI did some preliminary walkthrough of the code to understand why this\nhappens, and my understanding is as follows:\n1. In rev-list.c: we first set up the revisions provided via the\n`setup_revisions()` function. Here, any revision provided under the\n`--not` flag is marked as `UNINTERESTING`.\n2. In rev-list.c: we then call `prepare_revision_walk()`, this\nfunction internally goes through the commits and calls\n`handle_commit()` on each of the commit. In our case\n(6b52ed5b176604a0740689b5bb9be7bd79f4bced,\n91fa9611a355db77a07f963c746d57f75af380da).\n3. In revision.c: In `handle_commit()` we set `revs->limited = 1`\nsince one of our commits is marked as `UNINTERESTING`.\n4. In revision.c: Back in `prepare_revision_walk()`, since\n`revs->limited` is set, we call `limit_list()`.\n5. In revision.c: Not sure what the purpose of `limit_list()` is, but\nseems like it is to optimize the revision walk to reduce the traversal\nlater on. In our case, we can mark all parents of the commit as\nuninteresting and remove the commit from the rev list entirely.\n6. In rev-list.c: Finally, when we call\n`traverse_commit_list_filtered` for the traversal, we recursively show\ncommit/object unless we come across something `UNINTERESTING`. Since\nonly the commits were marked as `UNINTERESTING`, any shared\ntrees/blobs will still be printed to output.\n\nThe diff below fixes the issue:\n\n@@ -3790,11 +3833,12 @@ int prepare_revision_walk(struct rev_info *revs)\n         commit_list_sort_by_date(&revs->commits);\n     if (revs->no_walk)\n         return 0;\n-    if (revs->limited) {\n+    if (revs->limited && !revs->tree_objects) {\n         if (limit_list(revs) < 0)\n             return -1;\n         if (revs->topo_order)\n\nBut this is definitely a very _naive_ fix. Before diving into fixing\nthis, it would be nice to hear some thoughts on this.\n\n[System Info]\ngit version:\ngit version 2.41.0\ncpu: x86_64\nno commit associated with this build\nsizeof-long: 8\nsizeof-size_t: 8\nshell-path: /bin/sh\nuname: Linux 6.4.9-200.fc38.x86_64 #1 SMP PREEMPT_DYNAMIC Tue Aug  8\n21:21:11 UTC 2023 x86_64\ncompiler info: gnuc: 13.1\nlibc info: glibc: 2.37\n$SHELL (typically, interactive shell): /bin/fish\n\n\n[Enabled Hooks]\nnot run from a git repository - no hooks to show\n\n- Karthik\n"},{"id":"480684","messageId":"xmqqttt0hzl2.fsf@gitster.g","threadId":"60113","inReplyTo":"CAOLa=ZQmjroDiOcUsu_MHtQ-88QHU9qeZPOPh+KJJ3dFoF2q0A@mail.gmail.com","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-08-15T19:31:37Z","receivedAt":"2023-08-15T19:32:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karthik Nayak <karthik.188@gmail.com> writes:\n\n> If you notice here, the objects\n> `8baef1b4abc478178b004d62031cf7fe6db6f903`,\n> `086885f71429e3599c8c903b0e9ed491f6522879` and\n> `7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,\n> these objects are reachable from\n> `91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been\n> included since we used the `--not` flag.\n\nFor performance reasons, we cannot afford to enumerate all objects\nthat are reachable from --not objects and exclude them from the\noutput.  So it is a balancing act to decide where to draw the line.\n\nSpending more cycles and heaps for traversing the --not side deeper\nmay make the --objects output smaller and more precise, but there of\ncourse is cost associated with it.  And --objects do not promise\nthat it gives absolute minimum---the reason it exists is to make\nsure the objects listed are sufficient to fill gaps between the\n--not tips and positive ones, which is the primary reason for its\nexistence.\n\n> The diff below fixes the issue:\n>\n> @@ -3790,11 +3833,12 @@ int prepare_revision_walk(struct rev_info *revs)\n>          commit_list_sort_by_date(&revs->commits);\n>      if (revs->no_walk)\n>          return 0;\n> -    if (revs->limited) {\n> +    if (revs->limited && !revs->tree_objects) {\n>          if (limit_list(revs) < 0)\n>              return -1;\n>          if (revs->topo_order)\n\nThis might change the size of the output and \"fix\" the output in\nyour particular small test case, but I am not sure what kind of bugs\nthis will introduce in the more general codepath.\n\nNot calling limit_list() when the .limited bit is on is breaking one\nof the most fundamental assumptions in the revision traversal.  When\na feature is enabled that needs to paint the graph upfront before it\ncan compute its result, the code that enables the feature flips the\n.limited to ask this part of the code to make sure it calls\nlimit_list() to paint the graph with UNINTERESTING bit.\n\nThis area to paint uninteresting trees have changed quite\ndrastically at d5d2e935 (revision: implement sparse algorithm,\n2019-01-16).  Some of what it removed may be contributing the \"over\ncounting\" of trees that are relevant in your example.\n\n\n\n"},{"id":"480685","messageId":"xmqq350khvv2.fsf@gitster.g","threadId":"60113","inReplyTo":"CAOLa=ZQmjroDiOcUsu_MHtQ-88QHU9qeZPOPh+KJJ3dFoF2q0A@mail.gmail.com","subject":"Re: [Bug???] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-08-15T20:52:01Z","receivedAt":"2023-08-15T20:52:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karthik Nayak <karthik.188@gmail.com> writes:\n\n> Hello!\n>\n> What did you do before the bug happened? (Steps to reproduce your issue)\n>\n> Assume a repository structure as follows:\n>\n> - commit1 9f2aa2eb987c2281bb4901dbccd1398ad2c39722\n>   - tree: 205f6b799e7d5c2524468ca006a0131aa57ecce7\n>     - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n>       - content: foo\n> - commit2 9e02481f4df3a8997335b0a68882580e3b9b588f (parent:\n> 9f2aa2eb987c2281bb4901dbccd1398ad2c39722)\n>   - tree: 672d0aa883d095369c56416587bc397eee4ac37e\n>     - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n>       - content: foo\n>     - 100644 blob eec8c88a93f6ee1515fb8348f2c122cfda4302cd    moo\n>       - content: moo\n> - commit3 91fa9611a355db77a07f963c746d57f75af380da (parent:\n> 9e02481f4df3a8997335b0a68882580e3b9b588f)\n>    - tree 0c16a6cc9eef3fdd3034c1ffe2fc5e6d0bba2192\n>      - tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n>        - 100644 blob 7a67abed5f99fdd3ee203dd137b9818d88b1bafd    goo\n>          - content: goo\n>      - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n>        - content: foo\n>      - 100644 blob eec8c88a93f6ee1515fb8348f2c122cfda4302cd    moo\n>        - content: moo\n>      - 100644 blob 8baef1b4abc478178b004d62031cf7fe6db6f903    abc\n>        - content: abc\n> - commit4 6b52ed5b176604a0740689b5bb9be7bd79f4bced (parent:\n> 9f2aa2eb987c2281bb4901dbccd1398ad2c39722)\n>   - tree ff05824d2f76436c61d2c971e11a27514aba6948\n>     - tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n>       - 100644 blob 7a67abed5f99fdd3ee203dd137b9818d88b1bafd    goo\n>         - content: goo\n>     - 100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n>       - content: foo\n>     - 100644 blob 8baef1b4abc478178b004d62031cf7fe6db6f903    abc\n>       - content: abc\n\nThe differences in commit object names become distracting, but I do\nnot think your example depends on them, so a minimum reproduction\nrecipe should be\n\n\t$ rm -fr new ; git init new ; cd new\n\t$ echo foo >foo\n\t$ git add -A; git commit -m one; git rev-parse HEAD:\n\t205f6b799e7d5c2524468ca006a0131aa57ecce7\n\t$ echo moo >moo\n\t$ git add -A; git commit -m two; git rev-parse HEAD:\n\t672d0aa883d095369c56416587bc397eee4ac37e\n\t$ mkdir bar; echo goo >bar/goo; echo abc >abc\n\t$ git add -A; git commit -m three; git rev-parse HEAD:\n\t0c16a6cc9eef3fdd3034c1ffe2fc5e6d0bba2192\n\t$ git rm moo; git commit -m four; git rev-parse HEAD:\n\tff05824d2f76436c61d2c971e11a27514aba6948\n\n\t$ git rev-list --objects HEAD^..HEAD\n\t5a1b93c9c4c0c9e5c969f8e0b92a02184f8f9aab\n\tff05824d2f76436c61d2c971e11a27514aba6948\n\nthat output lists HEAD and HEAD^{tree} in this order, which seems to\nbe what you are expecting.\n\nI am consistently getting the same result with Git 2.42-rc2, 2.41,\n2.21, and 2.20 (I do not have ones older than 2.20 around).\n\n> What did you expect to happen? (Expected behavior)\n>\n> In such a repository, the output for the command, should have the\n> output provided below\n>\n> ❯ git rev-list --objects 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n> --not 91fa9611a355db77a07f963c746d57f75af380da\n> 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n> ff05824d2f76436c61d2c971e11a27514aba6948\n>\n> What happened instead? (Actual behavior)\n>\n> Instead, the output is as follows:\n>\n> ❯ git rev-list --objects 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n> --not 91fa9611a355db77a07f963c746d57f75af380da\n> 6b52ed5b176604a0740689b5bb9be7bd79f4bced\n> ff05824d2f76436c61d2c971e11a27514aba6948\n> 8baef1b4abc478178b004d62031cf7fe6db6f903 abc\n> 086885f71429e3599c8c903b0e9ed491f6522879 bar\n> 7a67abed5f99fdd3ee203dd137b9818d88b1bafd bar/goo\n\nSo, there is something else going on in *your* build of Git, or the\nrepository you prepared for testing, or both.\n\n"},{"id":"480688","messageId":"ZNv3+xOCi920StXO@nand.local","threadId":"60113","inReplyTo":"xmqqttt0hzl2.fsf@gitster.g","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-15T22:11:07Z","receivedAt":"2023-08-15T22:12:14Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Aug 15, 2023 at 12:31:37PM -0700, Junio C Hamano wrote:\n> Karthik Nayak <karthik.188@gmail.com> writes:\n>\n> > If you notice here, the objects\n> > `8baef1b4abc478178b004d62031cf7fe6db6f903`,\n> > `086885f71429e3599c8c903b0e9ed491f6522879` and\n> > `7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,\n> > these objects are reachable from\n> > `91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been\n> > included since we used the `--not` flag.\n>\n> For performance reasons, we cannot afford to enumerate all objects\n> that are reachable from --not objects and exclude them from the\n> output.  So it is a balancing act to decide where to draw the line.\n\nAs a hack, you can exploit the existing bitmap traversal routine to\nbuild up an exact mapping of what is and isn't on either side of your\nreachability query.\n\nIOW, if you run:\n\n    git repack -ad --write-bitmap-index\n\nand then repeat the rev-list query with `--use-bitmap-index`, you should\nget exact results.\n\nNote that this will only work if pack.useBitmapBoundaryTraversal is set\nto false, since the boundary-based traversal that is behind that\nconfiguration option is susceptible to the same one-sided error.\n\nThanks,\nTaylor\n"},{"id":"480693","messageId":"CAOLa=ZQPmtqT9OHxh5uFq0rg+9L02tnmh1UE52em-rXPmFR6yg@mail.gmail.com","threadId":"60113","inReplyTo":"xmqqttt0hzl2.fsf@gitster.g","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2023-08-15T22:56:58Z","receivedAt":"2023-08-15T22:58:31Z","isPatch":false,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"On Tue, Aug 15, 2023 at 9:31 PM Junio C Hamano <gitster@pobox.com> wrote:\n> > If you notice here, the objects\n> > `8baef1b4abc478178b004d62031cf7fe6db6f903`,\n> > `086885f71429e3599c8c903b0e9ed491f6522879` and\n> > `7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,\n> > these objects are reachable from\n> > `91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been\n> > included since we used the `--not` flag.\n>\n> For performance reasons, we cannot afford to enumerate all objects\n> that are reachable from --not objects and exclude them from the\n> output.  So it is a balancing act to decide where to draw the line.\n>\n> Spending more cycles and heaps for traversing the --not side deeper\n> may make the --objects output smaller and more precise, but there of\n> course is cost associated with it.  And --objects do not promise\n> that it gives absolute minimum---the reason it exists is to make\n> sure the objects listed are sufficient to fill gaps between the\n> --not tips and positive ones, which is the primary reason for its\n> existence.\n>\n\nI understand this, this makes sense from how rev-list is internally\nused. But from a user\nfacing command perspective, it's not doing what it says. So either we\nadd to the docs\nsaying that there are quirks using `--not` with `--objects`  or we fix this.\n\nSo I would still consider it a bug in that sense.\n\n> > The diff below fixes the issue:\n> >\n> > @@ -3790,11 +3833,12 @@ int prepare_revision_walk(struct rev_info *revs)\n> >          commit_list_sort_by_date(&revs->commits);\n> >      if (revs->no_walk)\n> >          return 0;\n> > -    if (revs->limited) {\n> > +    if (revs->limited && !revs->tree_objects) {\n> >          if (limit_list(revs) < 0)\n> >              return -1;\n> >          if (revs->topo_order)\n>\n> This might change the size of the output and \"fix\" the output in\n> your particular small test case, but I am not sure what kind of bugs\n> this will introduce in the more general codepath.\n>\n> Not calling limit_list() when the .limited bit is on is breaking one\n> of the most fundamental assumptions in the revision traversal.  When\n> a feature is enabled that needs to paint the graph upfront before it\n> can compute its result, the code that enables the feature flips the\n> .limited to ask this part of the code to make sure it calls\n> limit_list() to paint the graph with UNINTERESTING bit.\n>\n> This area to paint uninteresting trees have changed quite\n> drastically at d5d2e935 (revision: implement sparse algorithm,\n> 2019-01-16).  Some of what it removed may be contributing the \"over\n> counting\" of trees that are relevant in your example.\n>\n\nI never proposed this as the solution, this was merely me trying to understand\nwhy it is working the way it is, hence calling it a _naive_ fix.\n\n> The differences in commit object names become distracting, but I do\n> not think your example depends on them, so a minimum reproduction\n> recipe should be\n>\n>         $ rm -fr new ; git init new ; cd new\n>         $ echo foo >foo\n>         $ git add -A; git commit -m one; git rev-parse HEAD:\n>         205f6b799e7d5c2524468ca006a0131aa57ecce7\n>         $ echo moo >moo\n>         $ git add -A; git commit -m two; git rev-parse HEAD:\n>         672d0aa883d095369c56416587bc397eee4ac37e\n>         $ mkdir bar; echo goo >bar/goo; echo abc >abc\n>         $ git add -A; git commit -m three; git rev-parse HEAD:\n>         0c16a6cc9eef3fdd3034c1ffe2fc5e6d0bba2192\n>         $ git rm moo; git commit -m four; git rev-parse HEAD:\n>         ff05824d2f76436c61d2c971e11a27514aba6948\n>\n>         $ git rev-list --objects HEAD^..HEAD\n>         5a1b93c9c4c0c9e5c969f8e0b92a02184f8f9aab\n>         ff05824d2f76436c61d2c971e11a27514aba6948\n>\n> that output lists HEAD and HEAD^{tree} in this order, which seems to\n> be what you are expecting.\n>\n> I am consistently getting the same result with Git 2.42-rc2, 2.41,\n> 2.21, and 2.20 (I do not have ones older than 2.20 around).\n\nThe provided reproduction recipe unfortunately uses a linear history and\ntherefore, is not the same as the example provided by me. Here is a reproducible\nrecipe following the same commands you used:\n\n$ rm -fr new ; git init new ; cd new\n$ echo foo >foo\n$ git add -A; git commit -m one; git rev-parse HEAD\n26fb965d7439c1760677377bf314d8933de0b716\n$ mkdir bar; echo goo >bar/goo\n$ git add -A; git commit -m two; git rev-parse HEAD\n$ git checkout -B branch\n$ git reset --hard @~1\nHEAD is now at 26fb965 one\n$ git add -A; git commit -m three; git rev-parse HEAD\n91ef508167eb683486c3df6f8d07622b61ed698d\n\n$ git rev-list --objects HEAD ^master\n91ef508167eb683486c3df6f8d07622b61ed698d\nff05824d2f76436c61d2c971e11a27514aba6948\n8baef1b4abc478178b004d62031cf7fe6db6f903 abc\n086885f71429e3599c8c903b0e9ed491f6522879 bar\n7a67abed5f99fdd3ee203dd137b9818d88b1bafd bar/goo\n\n$ git cat-file -p HEAD^{tree}\n100644 blob 8baef1b4abc478178b004d62031cf7fe6db6f903    abc\n040000 tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n\n$ git cat-file -p master^{tree}\n040000 tree 086885f71429e3599c8c903b0e9ed491f6522879    bar\n100644 blob 257cc5642cb1a054f08cc83f2d943e56fd3ebe99    foo\n\n> So, there is something else going on in *your* build of Git, or the\n> repository you prepared for testing, or both.\n>\n\n$ git version\ngit version 2.41.0\n\nSo the issue definitely exists, this is on an unmodified git. You can see that\nthe objects `086885f71429e3599c8c903b0e9ed491f6522879` and\n`7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are still shown (which shouldn't\nhave been shown).\n"},{"id":"480694","messageId":"CAOLa=ZTXjV3abbuLYF8oE3P_P_xSZUtyM4fpPSg55Dd_QXoWXQ@mail.gmail.com","threadId":"60113","inReplyTo":"ZNv3+xOCi920StXO@nand.local","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2023-08-15T22:59:33Z","receivedAt":"2023-08-15T23:00:43Z","isPatch":false,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"On Wed, Aug 16, 2023 at 12:11 AM Taylor Blau <me@ttaylorr.com> wrote:\n>\n> On Tue, Aug 15, 2023 at 12:31:37PM -0700, Junio C Hamano wrote:\n> > Karthik Nayak <karthik.188@gmail.com> writes:\n> >\n> > > If you notice here, the objects\n> > > `8baef1b4abc478178b004d62031cf7fe6db6f903`,\n> > > `086885f71429e3599c8c903b0e9ed491f6522879` and\n> > > `7a67abed5f99fdd3ee203dd137b9818d88b1bafd` are included in the output,\n> > > these objects are reachable from\n> > > `91fa9611a355db77a07f963c746d57f75af380da` and shouldn't have been\n> > > included since we used the `--not` flag.\n> >\n> > For performance reasons, we cannot afford to enumerate all objects\n> > that are reachable from --not objects and exclude them from the\n> > output.  So it is a balancing act to decide where to draw the line.\n>\n> As a hack, you can exploit the existing bitmap traversal routine to\n> build up an exact mapping of what is and isn't on either side of your\n> reachability query.\n>\n> IOW, if you run:\n>\n>     git repack -ad --write-bitmap-index\n>\n> and then repeat the rev-list query with `--use-bitmap-index`, you should\n> get exact results.\n>\n> Note that this will only work if pack.useBitmapBoundaryTraversal is set\n> to false, since the boundary-based traversal that is behind that\n> configuration option is susceptible to the same one-sided error.\n>\n> Thanks,\n> Taylor\n\nThanks! I tried using bitmap traversal and can confirm the issue doesn't\nexist with this option.\n"},{"id":"480722","messageId":"xmqqbkf6g80f.fsf@gitster.g","threadId":"60113","inReplyTo":"CAOLa=ZQPmtqT9OHxh5uFq0rg+9L02tnmh1UE52em-rXPmFR6yg@mail.gmail.com","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-08-16T18:24:48Z","receivedAt":"2023-08-16T18:25:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karthik Nayak <karthik.188@gmail.com> writes:\n\n> The provided reproduction recipe unfortunately uses a linear\n> history and therefore, is not the same as the example provided by\n> me. Here is a reproducible recipe following the same commands you\n> used:\n> $ rm -fr new ; git init new ; cd new\n> $ echo foo >foo\n> $ git add -A; git commit -m one; git rev-parse HEAD\n> 26fb965d7439c1760677377bf314d8933de0b716\n> $ mkdir bar; echo goo >bar/goo\n> $ git add -A; git commit -m two; git rev-parse HEAD\n> $ git checkout -B branch\n> $ git reset --hard @~1\n> HEAD is now at 26fb965 one\n> $ git add -A; git commit -m three; git rev-parse HEAD\n> 91ef508167eb683486c3df6f8d07622b61ed698d\n>\n> $ git rev-list --objects HEAD ^master\n> 91ef508167eb683486c3df6f8d07622b61ed698d\n> ff05824d2f76436c61d2c971e11a27514aba6948\n> 8baef1b4abc478178b004d62031cf7fe6db6f903 abc\n> 086885f71429e3599c8c903b0e9ed491f6522879 bar\n> 7a67abed5f99fdd3ee203dd137b9818d88b1bafd bar/goo\n\nThanks, but the above is not recreating the same as your original\n(where did \"moo\" go???).  Also \"git rev-parse HEAD\" for the sanity\nchecking should be spelled \"git rev-parse HEAD:\" if you want to help\nothers looking into the issue---anybody trying to reproduce will NOT\nhave the same commit object name, but the point of these checks is\nto show the tree object name, which should reproduce for them.\n\n"},{"id":"480727","messageId":"CAOLa=ZR666sDj269SSDa26afqMxUq2Qr6TJnMSKOkVuqoKX43Q@mail.gmail.com","threadId":"60113","inReplyTo":"xmqqbkf6g80f.fsf@gitster.g","subject":"Re: [Bug] In `git-rev-list(1)`, using the `--objects` flag doesn't work well with the `--not` flag, as non-commit objects are not excluded","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2023-08-16T20:58:49Z","receivedAt":"2023-08-16T21:00:23Z","isPatch":false,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"On Wed, Aug 16, 2023 at 8:24 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Karthik Nayak <karthik.188@gmail.com> writes:\n>\n> > The provided reproduction recipe unfortunately uses a linear\n> > history and therefore, is not the same as the example provided by\n> > me. Here is a reproducible recipe following the same commands you\n> > used:\n> > $ rm -fr new ; git init new ; cd new\n> > $ echo foo >foo\n> > $ git add -A; git commit -m one; git rev-parse HEAD\n> > 26fb965d7439c1760677377bf314d8933de0b716\n> > $ mkdir bar; echo goo >bar/goo\n> > $ git add -A; git commit -m two; git rev-parse HEAD\n> > $ git checkout -B branch\n> > $ git reset --hard @~1\n> > HEAD is now at 26fb965 one\n> > $ git add -A; git commit -m three; git rev-parse HEAD\n> > 91ef508167eb683486c3df6f8d07622b61ed698d\n> >\n> > $ git rev-list --objects HEAD ^master\n> > 91ef508167eb683486c3df6f8d07622b61ed698d\n> > ff05824d2f76436c61d2c971e11a27514aba6948\n> > 8baef1b4abc478178b004d62031cf7fe6db6f903 abc\n> > 086885f71429e3599c8c903b0e9ed491f6522879 bar\n> > 7a67abed5f99fdd3ee203dd137b9818d88b1bafd bar/goo\n>\n> Thanks, but the above is not recreating the same as your original\n> (where did \"moo\" go???).  Also \"git rev-parse HEAD\" for the sanity\n> checking should be spelled \"git rev-parse HEAD:\" if you want to help\n> others looking into the issue---anybody trying to reproduce will NOT\n> have the same commit object name, but the point of these checks is\n> to show the tree object name, which should reproduce for them.\n>\n\nIt's not re-creating the exact structure I had in my original post, but it is\na shorter version which demonstrates the issue at hand.\n\nI don't see the importance of \"moo\" here, the original repository structure\nwas something I was playing around with and found the issue.\n\nSorry about the misspelling, was just trying to provide a more deterministic\nmethod of re-creating the issue. And I think that it still holds true.\nIn the newer\nexample you can see that although \"branch\" and \"master\" are TREESAME\nwith regards to the \"bar\" path, the tree for \"bar\" and its children\nare still output\nfrom git-rev-list(1). Even though we specify \"^master\".So ideally only objects\nreachable from \"branch\" and not reachable from \"master\" should have been\noutput.\n"}]}