{"thread":{"id":"51154","subject":"standalone library/tool to query commit-graph?","startedAt":"2019-05-22T18:49:28Z","lastAt":"2019-06-25T18:27:36Z","messageCount":12,"participants":["Karl Ostmo","Derrick Stolee","Jakub Narebski","Ævar Arnfjörð Bjarmason","SZEDER Gábor"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"376064","messageId":"CAECbv94KF9MhzZqa8BR-RL93mh0NuD3vA69pAT-sY5O74e_duQ@mail.gmail.com","threadId":"51154","inReplyTo":null,"subject":"standalone library/tool to query commit-graph?","fromName":"Karl Ostmo","fromEmail":"kostmo@gmail.com","sentAt":"2019-05-22T18:49:15Z","receivedAt":"2019-05-22T18:49:28Z","isPatch":false,"sender":{"key":"kostmo@gmail.com","avatar":null},"body":"After producing the file \".git/objects/info/commit-graph\" with the\ncommand \"git commit-graph write\", is there a way to answer queries\nlike \"git merge-base --is-ancestor\" without having a .git directory?\nE.g. is there a library that will operate on the \"commit-graph\" file\nall by itself?\n\nThanks,\nKarl\n"},{"id":"376065","messageId":"be719a37-ffa0-26d3-eb9c-0f5ccde52e7f@gmail.com","threadId":"51154","inReplyTo":"CAECbv94KF9MhzZqa8BR-RL93mh0NuD3vA69pAT-sY5O74e_duQ@mail.gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-22T18:59:33Z","receivedAt":"2019-05-22T18:59:39Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/22/2019 2:49 PM, Karl Ostmo wrote:\n> After producing the file \".git/objects/info/commit-graph\" with the\n> command \"git commit-graph write\", is there a way to answer queries\n> like \"git merge-base --is-ancestor\" without having a .git directory?\n> E.g. is there a library that will operate on the \"commit-graph\" file\n> all by itself?\n\nYou could certainly build such a tool, assuming your merge-base parameters are\nfull-length commit ids. If you try to start at ref names, you'll need the .git\ndirectory.\n\nI would not expect such a tool to ever exist in the Git codebase. Instead, you\nwould need a new project, say \"graph-analyzer --graph= --is-ancestor \"\n\nThanks,\n-Stolee\n"},{"id":"376111","messageId":"86blztq8ap.fsf@gmail.com","threadId":"51154","inReplyTo":"be719a37-ffa0-26d3-eb9c-0f5ccde52e7f@gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-05-23T19:29:02Z","receivedAt":"2019-05-23T19:29:07Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee writes:\n> On 5/22/2019 2:49 PM, Karl Ostmo wrote:\n\n>> After producing the file \".git/objects/info/commit-graph\" with the\n>> command \"git commit-graph write\", is there a way to answer queries\n>> like \"git merge-base --is-ancestor\" without having a .git directory?\n>> E.g. is there a library that will operate on the \"commit-graph\" file\n>> all by itself?\n>\n> You could certainly build such a tool, assuming your merge-base parameters are\n> full-length commit ids. If you try to start at ref names, you'll need the .git\n> directory.\n>\n> I would not expect such a tool to ever exist in the Git codebase. Instead, you\n> would need a new project, say \"graph-analyzer --graph= --is-ancestor \"\n\nIt would be nice if such tool could convert commit-graph into other\ncommonly used augmented graph storage formats, like GEXF (Graph Exchange\nXML Format), GraphML, GML (Graph Modelling Language), Pajek format or\nGraphviz .dot format.\n\nWishfully thinking,\n--\nJakub Narębski\n"},{"id":"376132","messageId":"87tvdkg7ld.fsf@evledraar.gmail.com","threadId":"51154","inReplyTo":"86blztq8ap.fsf@gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-23T21:54:22Z","receivedAt":"2019-05-23T21:54:27Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, May 23 2019, Jakub Narebski wrote:\n\n> Derrick Stolee writes:\n>> On 5/22/2019 2:49 PM, Karl Ostmo wrote:\n>\n>>> After producing the file \".git/objects/info/commit-graph\" with the\n>>> command \"git commit-graph write\", is there a way to answer queries\n>>> like \"git merge-base --is-ancestor\" without having a .git directory?\n>>> E.g. is there a library that will operate on the \"commit-graph\" file\n>>> all by itself?\n>>\n>> You could certainly build such a tool, assuming your merge-base parameters are\n>> full-length commit ids. If you try to start at ref names, you'll need the .git\n>> directory.\n>>\n>> I would not expect such a tool to ever exist in the Git codebase. Instead, you\n>> would need a new project, say \"graph-analyzer --graph= --is-ancestor \"\n>\n> It would be nice if such tool could convert commit-graph into other\n> commonly used augmented graph storage formats, like GEXF (Graph Exchange\n> XML Format), GraphML, GML (Graph Modelling Language), Pajek format or\n> Graphviz .dot format.\n\nWouldn't that make more sense as a hypothetical output format for \"log\n--graph\" rather than something you'd want to emit from the commit-graph?\nPresumably you'd want to export in such a format to see the shape of the\nrepo, and since the commit graph doesn't include any commits outside of\npacks you'd miss any loose commits.\n"},{"id":"376134","messageId":"20190523222031.GC951@szeder.dev","threadId":"51154","inReplyTo":"87tvdkg7ld.fsf@evledraar.gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-23T22:20:31Z","receivedAt":"2019-05-23T22:20:37Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Thu, May 23 2019, Jakub Narebski wrote:\n> \n> > Derrick Stolee writes:\n> >> On 5/22/2019 2:49 PM, Karl Ostmo wrote:\n> >\n> >>> After producing the file \".git/objects/info/commit-graph\" with the\n> >>> command \"git commit-graph write\", is there a way to answer queries\n> >>> like \"git merge-base --is-ancestor\" without having a .git directory?\n> >>> E.g. is there a library that will operate on the \"commit-graph\" file\n> >>> all by itself?\n> >>\n> >> You could certainly build such a tool, assuming your merge-base parameters are\n> >> full-length commit ids. If you try to start at ref names, you'll need the .git\n> >> directory.\n> >>\n> >> I would not expect such a tool to ever exist in the Git codebase. Instead, you\n> >> would need a new project, say \"graph-analyzer --graph= --is-ancestor \"\n> >\n> > It would be nice if such tool could convert commit-graph into other\n> > commonly used augmented graph storage formats, like GEXF (Graph Exchange\n> > XML Format), GraphML, GML (Graph Modelling Language), Pajek format or\n> > Graphviz .dot format.\n> \n> Wouldn't that make more sense as a hypothetical output format for \"log\n> --graph\" rather than something you'd want to emit from the commit-graph?\n> Presumably you'd want to export in such a format to see the shape of the\n> repo, and since the commit graph doesn't include any commits outside of\n> packs you'd miss any loose commits.\n\nNo, the commit-graph includes loose commits as well.\n\n"},{"id":"376136","messageId":"f05405d7-c78d-a0e4-75a1-d623f977400a@gmail.com","threadId":"51154","inReplyTo":"20190523222031.GC951@szeder.dev","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-23T23:48:33Z","receivedAt":"2019-05-23T23:48:39Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n> On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Thu, May 23 2019, Jakub Narebski wrote:\n>>\n>>> Derrick Stolee writes:\n>>>> On 5/22/2019 2:49 PM, Karl Ostmo wrote:\n>>>\n>>>>> After producing the file \".git/objects/info/commit-graph\" with the\n>>>>> command \"git commit-graph write\", is there a way to answer queries\n>>>>> like \"git merge-base --is-ancestor\" without having a .git directory?\n>>>>> E.g. is there a library that will operate on the \"commit-graph\" file\n>>>>> all by itself?\n>>>>\n>>>> You could certainly build such a tool, assuming your merge-base parameters are\n>>>> full-length commit ids. If you try to start at ref names, you'll need the .git\n>>>> directory.\n>>>>\n>>>> I would not expect such a tool to ever exist in the Git codebase. Instead, you\n>>>> would need a new project, say \"graph-analyzer --graph= --is-ancestor \"\n>>>\n>>> It would be nice if such tool could convert commit-graph into other\n>>> commonly used augmented graph storage formats, like GEXF (Graph Exchange\n>>> XML Format), GraphML, GML (Graph Modelling Language), Pajek format or\n>>> Graphviz .dot format.\n>>\n>> Wouldn't that make more sense as a hypothetical output format for \"log\n>> --graph\" rather than something you'd want to emit from the commit-graph?\n>> Presumably you'd want to export in such a format to see the shape of the\n>> repo, and since the commit graph doesn't include any commits outside of\n>> packs you'd miss any loose commits.\n> \n> No, the commit-graph includes loose commits as well.\n\nDepends on how you build the commit-graph.\n\n\tgit commit-graph write\n\tgit commit-graph write --stdin-packs\n\nThese options build based on commits in packs (and closes under reachability).\n\n\tgit commit-graph write --reachable\n\tgit commit-graph write --stdin-commits\n\nThese options build based on a set of starting commits. Either the refs (--reachable)\nor the input commit ids (--stdin-commits).\n\nBut I do like the flexibility of `git log --graph` as you could export the graph\nafter reparenting (with options like `--simplify-merges -- `). You also would \nnot include commits from random topic branches you have sitting around.\n\n-Stolee\n"},{"id":"376166","messageId":"20190524093459.GE951@szeder.dev","threadId":"51154","inReplyTo":"f05405d7-c78d-a0e4-75a1-d623f977400a@gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T09:34:59Z","receivedAt":"2019-05-24T09:35:05Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, May 23, 2019 at 07:48:33PM -0400, Derrick Stolee wrote:\n> On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n> > On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> >> and since the commit graph doesn't include any commits outside of\n> >> packs you'd miss any loose commits.\n> > \n> > No, the commit-graph includes loose commits as well.\n> \n> Depends on how you build the commit-graph.\n\nYeah; I just didn't want to go into details, hoping that this short\nreply will be enough to jog Ævar's memory to recall our earlier\ndiscussion about this :)\n\n"},{"id":"376169","messageId":"87o93sfahj.fsf@evledraar.gmail.com","threadId":"51154","inReplyTo":"20190524093459.GE951@szeder.dev","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T09:49:28Z","receivedAt":"2019-05-24T09:49:32Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, SZEDER Gábor wrote:\n\n> On Thu, May 23, 2019 at 07:48:33PM -0400, Derrick Stolee wrote:\n>> On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n>> > On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> >> and since the commit graph doesn't include any commits outside of\n>> >> packs you'd miss any loose commits.\n>> >\n>> > No, the commit-graph includes loose commits as well.\n>>\n>> Depends on how you build the commit-graph.\n>\n> Yeah; I just didn't want to go into details, hoping that this short\n> reply will be enough to jog Ævar's memory to recall our earlier\n> discussion about this :)\n\nTo clarify (and I should have said) I meant it'll include only packed\ncommits in the mode Karl Ostmo invoked it in, as Derrick points out.\n\nBut yeah, you can of course give it arbitrary starting points, but\nneeding to deal with those sorts of caveats makes it rather useless in\npractice for the sort of use-case Jakub mused about, but more\nimportantly a full XML dump of the graph isn't going to get much of a\nbenefit from the commit graph, it helps with algorithms that want to\navoid those sorts of full walks.\n"},{"id":"376172","messageId":"20190524100653.GF951@szeder.dev","threadId":"51154","inReplyTo":"87o93sfahj.fsf@evledraar.gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T10:06:53Z","receivedAt":"2019-05-24T10:06:58Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, May 24, 2019 at 11:49:28AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, May 24 2019, SZEDER Gábor wrote:\n> \n> > On Thu, May 23, 2019 at 07:48:33PM -0400, Derrick Stolee wrote:\n> >> On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n> >> > On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >\n> >> >> and since the commit graph doesn't include any commits outside of\n> >> >> packs you'd miss any loose commits.\n> >> >\n> >> > No, the commit-graph includes loose commits as well.\n> >>\n> >> Depends on how you build the commit-graph.\n> >\n> > Yeah; I just didn't want to go into details, hoping that this short\n> > reply will be enough to jog Ævar's memory to recall our earlier\n> > discussion about this :)\n> \n> To clarify (and I should have said) I meant it'll include only packed\n> commits in the mode Karl Ostmo invoked it in, as Derrick points out.\n\nNo, even in that mode it will include loose objects as well, if it has\nto; that's what the \"and closes under reachability\" part of Derrick's\nreply means and that's what I showed in our earlier discussion at:\n\n https://public-inbox.org/git/20190322154943.GF22459@szeder.dev/\n\n\n"},{"id":"376176","messageId":"87k1egf7pz.fsf@evledraar.gmail.com","threadId":"51154","inReplyTo":"20190524100653.GF951@szeder.dev","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T10:49:12Z","receivedAt":"2019-05-24T10:49:17Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, SZEDER Gábor wrote:\n\n> On Fri, May 24, 2019 at 11:49:28AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Fri, May 24 2019, SZEDER Gábor wrote:\n>>\n>> > On Thu, May 23, 2019 at 07:48:33PM -0400, Derrick Stolee wrote:\n>> >> On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n>> >> > On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> >\n>> >> >> and since the commit graph doesn't include any commits outside of\n>> >> >> packs you'd miss any loose commits.\n>> >> >\n>> >> > No, the commit-graph includes loose commits as well.\n>> >>\n>> >> Depends on how you build the commit-graph.\n>> >\n>> > Yeah; I just didn't want to go into details, hoping that this short\n>> > reply will be enough to jog Ævar's memory to recall our earlier\n>> > discussion about this :)\n>>\n>> To clarify (and I should have said) I meant it'll include only packed\n>> commits in the mode Karl Ostmo invoked it in, as Derrick points out.\n>\n> No, even in that mode it will include loose objects as well, if it has\n> to; that's what the \"and closes under reachability\" part of Derrick's\n> reply means and that's what I showed in our earlier discussion at:\n>\n> https://public-inbox.org/git/20190322154943.GF22459@szeder.dev/\n\nI should have said \"include any commits outside of packs [to seed the\nrevision walk]\".\n\nAs you correctly point out there *are* caveats to that, e.g. it's\npossible to have packs & loose commits but you include everything\nbecause of reachability.\n\nFor the purposes of the discussion Jakub started upthread the\nnot-quite-correct-but-close-enough mental model that we generally tend\nto accumulate loose objects that later coalesce into packs is close\nenough.\n\nI.e. for that reason for most users a \"git commit-graph write\" won't\nproduce a graph with all reachable commits, e.g. try cloning git.git,\n\"git am\"-ing a patch on top, and generate it again, it'll be the same\n(unless you picked a humongous patch).\n\nSimilarly it'll be incomplete for most users that have\ngc.writeCommitGraph=true on since they use \"gc --auto\", and they're\nlikely in an in-between state where they have a semi-stale graph.\n\nSo building tools directly on top of it shouldn't be anyone's first\nchoice, instead walk the DAG and see if that walking code can as an\noptimization optimistically consult the commit-graph.\n"},{"id":"376179","messageId":"20190524113710.GG951@szeder.dev","threadId":"51154","inReplyTo":"87k1egf7pz.fsf@evledraar.gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T11:37:10Z","receivedAt":"2019-05-24T11:37:16Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, May 24, 2019 at 12:49:12PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >> > On Thu, May 23, 2019 at 07:48:33PM -0400, Derrick Stolee wrote:\n> >> >> On 5/23/2019 6:20 PM, SZEDER Gábor wrote:\n> >> >> > On Thu, May 23, 2019 at 11:54:22PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >> >\n> >> >> >> and since the commit graph doesn't include any commits outside of\n> >> >> >> packs you'd miss any loose commits.\n> >> >> >\n> >> >> > No, the commit-graph includes loose commits as well.\n> >> >>\n> >> >> Depends on how you build the commit-graph.\n> >> >\n> >> > Yeah; I just didn't want to go into details, hoping that this short\n> >> > reply will be enough to jog Ævar's memory to recall our earlier\n> >> > discussion about this :)\n> >>\n> >> To clarify (and I should have said) I meant it'll include only packed\n> >> commits in the mode Karl Ostmo invoked it in, as Derrick points out.\n> >\n> > No, even in that mode it will include loose objects as well, if it has\n> > to; that's what the \"and closes under reachability\" part of Derrick's\n> > reply means and that's what I showed in our earlier discussion at:\n> >\n> > https://public-inbox.org/git/20190322154943.GF22459@szeder.dev/\n> \n> I should have said \"include any commits outside of packs [to seed the\n> revision walk]\".\n> \n> As you correctly point out there *are* caveats to that, e.g. it's\n> possible to have packs & loose commits but you include everything\n> because of reachability.\n> \n> For the purposes of the discussion Jakub started upthread the\n> not-quite-correct-but-close-enough mental model that we generally tend\n> to accumulate loose objects that later coalesce into packs is close\n> enough.\n> \n> I.e. for that reason for most users a \"git commit-graph write\" won't\n> produce a graph with all reachable commits, e.g. try cloning git.git,\n> \"git am\"-ing a patch on top, and generate it again, it'll be the same\n> (unless you picked a humongous patch).\n\nOk, with this I finally understand what you meant.\n\nAnd it just reinforces my long-held belief that '--reachable' should be\nthe default for 'git commit-graph write'...\n\n"},{"id":"378036","messageId":"86ftnx4j1n.fsf@gmail.com","threadId":"51154","inReplyTo":"87o93sfahj.fsf@evledraar.gmail.com","subject":"Re: standalone library/tool to query commit-graph?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2019-06-25T18:27:32Z","receivedAt":"2019-06-25T18:27:36Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n[...]\n\n> To clarify (and I should have said) I meant it'll include only packed\n> commits in the mode Karl Ostmo invoked it in, as Derrick points out.\n>\n> But yeah, you can of course give it arbitrary starting points, but\n> needing to deal with those sorts of caveats makes it rather useless in\n> practice for the sort of use-case Jakub mused about, but more\n> importantly a full XML dump of the graph isn't going to get much of a\n> benefit from the commit graph, it helps with algorithms that want to\n> avoid those sorts of full walks.\n\nActually for an \"XML dump\" of a graph of revisions (assuming that you\ncan give nodes and edges in arbitrary order in this graph output format)\ndoing it using serialized commit-graph should be faster: you only need\nto read one file, and convert it to other format (perhaps even in a\nstreaming manner). No need to delta-unpack, decompress and parse commit\nobjects.\n\nThough on the other hand you are right: if \"git log --graph\" uses\nserialized commit graph, and it is used for XML / JSON dump, it should\nalso be fast. If there is no serialized commit graph, you still can\ngenerate XML dump.\n\nBest,\n--\nJakub Narębski\n"}]}