{"thread":{"id":"42749","subject":"topological index field for commit objects","startedAt":"2016-06-29T18:40:57Z","lastAt":"2017-02-17T09:29:46Z","messageCount":31,"participants":["Marc Strapetz","Junio C Hamano","Stefan Beller","Jeff King","Jakub Narębski","Linus Torvalds","Mike Hommey","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"290520","messageId":"f15a14a5-f39d-9c41-16b9-fe0a48d7450b@syntevo.com","threadId":"42749","inReplyTo":null,"subject":"topological index field for commit objects","fromName":"Marc Strapetz","fromEmail":"marc.strapetz@syntevo.com","sentAt":"2016-06-29T18:31:18Z","receivedAt":"2016-06-29T18:40:57Z","isPatch":false,"sender":{"key":"marc.strapetz@syntevo.com","avatar":"https://avatars.githubusercontent.com/u/3380730?v=4"},"body":"This is no RFE but rather recurring thoughts whenever I'm working with \ncommit graphs: a topological index attribute for commit objects would be \nincredible useful. By \"topological index\" I mean a simple integer for \nwhich following condition holds true:\n\nif commit C is part of the history of commit D,\n then C's topological index is smaller than D's index\n\nThis would allow topological sorting of commits (e.g. in queues) on the \nfly and quickly give a \"no\" answer on the question whether D is part of \nC's history.\n\n-Marc\n\n"},{"id":"290521","messageId":"CAPc5daVC-+0Vr30L_pbcL0GN2OmnGm-+V4tE2WTos_vPRb_S1g@mail.gmail.com","threadId":"42749","inReplyTo":"f15a14a5-f39d-9c41-16b9-fe0a48d7450b@syntevo.com","subject":"Re: topological index field for commit objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-29T18:59:56Z","receivedAt":"2016-06-29T19:00:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n wrote:\n> This is no RFE but rather recurring thoughts whenever I'm working with\n> commit graphs: a topological index attribute for commit objects would be\n> incredible useful. By \"topological index\" I mean a simple integer for which\n> following condition holds true:\n\nLook for \"generation numbers\" in the list archive, perhaps?\n"},{"id":"290528","messageId":"CAGZ79kY6Ry+DfO90wza_RrVbCRAgNB4N=0W6svuJgvGNxeFh5Q@mail.gmail.com","threadId":"42749","inReplyTo":"CAPc5daVC-+0Vr30L_pbcL0GN2OmnGm-+V4tE2WTos_vPRb_S1g@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-29T20:20:37Z","receivedAt":"2016-06-29T20:21:26Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Jun 29, 2016 at 11:59 AM, Junio C Hamano wrote:\n> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n> wrote:\n>> This is no RFE but rather recurring thoughts whenever I'm working with\n>> commit graphs: a topological index attribute for commit objects would be\n>> incredible useful. By \"topological index\" I mean a simple integer for which\n>> following condition holds true:\n>\n> Look for \"generation numbers\" in the list archive, perhaps?\n\nThanks for the pointer to the interesting discussions.\n\nIn http://www.spinics.net/lists/git/msg161363.html\nLinus wrote in a discussion with Jeff:\n\n> Right now, we do *have* a \"generation number\". It's just that it's\n> very easy to corrupt even by mistake. It's called \"committer date\". We\n> could improve on it.\n\nWould it make sense to refuse creating commits that have a commit date\nprior to its parents commit date (except when the user gives a\n`--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n\nWith the proposal to refuse an earlier committer date we would avoid\nthe corruption by mistake and only allow for corruption by actual\nusers intention. And then going forward we could rely more on the\ncommitter date than we do today (i.e. some algorithms can go faster)?\nFor that we'd\n * need to document, what stuff actually breaks if the user overwrites\n the committer date to be earlier\n * and add a switch `--go-slow-because-dates-are-broken`\n\nThis seems to be the easiest fix in 2016 to me as that would require\nto make just a very small change in commit creation, and we can postpone\nthe second part (relying even more on dates) until someone wants to fix it?\n\nThanks,\nStefan\n\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"290532","messageId":"xmqqk2h73f2i.fsf@gitster.mtv.corp.google.com","threadId":"42749","inReplyTo":"CAGZ79kY6Ry+DfO90wza_RrVbCRAgNB4N=0W6svuJgvGNxeFh5Q@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-29T20:39:17Z","receivedAt":"2016-06-29T20:45:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> On Wed, Jun 29, 2016 at 11:59 AM, Junio C Hamano wrote:\n>> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n>> wrote:\n>>> This is no RFE but rather recurring thoughts whenever I'm working with\n>>> commit graphs: a topological index attribute for commit objects would be\n>>> incredible useful. By \"topological index\" I mean a simple integer for which\n>>> following condition holds true:\n>>\n>> Look for \"generation numbers\" in the list archive, perhaps?\n>\n> Thanks for the pointer to the interesting discussions.\n>\n> In http://www.spinics.net/lists/git/msg161363.html\n> Linus wrote in a discussion with Jeff:\n>\n>> Right now, we do *have* a \"generation number\". It's just that it's\n>> very easy to corrupt even by mistake. It's called \"committer date\". We\n>> could improve on it.\n>\n> Would it make sense to refuse creating commits that have a commit date\n> prior to its parents commit date (except when the user gives a\n> `--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n\nI think that has also been discussed in the past. I do not think it\nwould help very much in practice, as projects already have up to 10\nyears (and the ones migrated from CVS, even more) worth of commits\nthey cannot rewrite that may record incorrect committer dates.\nYou'd need something like \"you can trust committer dates that are\nnewer that this date\" per project to switch between slow path and\nfast path, with an updated fsck that knows how to compute that\nnumber after you pulled from somebody who used that overriding\noption.\n\nIf the use of generation number can somehow be limited narrowly, we\nmay be able to incrementally introduce it only for new commits, but\nI haven't thought things through, so let me do so aloud here ;-)\n\nSuppose we use it only for this purpose:\n\n * When we have two commits, C1 and C2, with generation numbers G1\n and G2, we can say \"C1 cannot possibly be an ancestor of C2\" if\n G1 > G2. We cannot say anything else based on generation\n numbers (or lack thereof).\n\nthen I think we could just say \"A newly created commit must record\ngeneration number G that is larger than generation numbers of its\nparent commits; ignore parents that lack generation number for the\npurpose of this sentence\".\n\nI am not sure if that limited use is all that useful, though.\n"},{"id":"290534","messageId":"20160629205647.GA25987@sigill.intra.peff.net","threadId":"42749","inReplyTo":"xmqqk2h73f2i.fsf@gitster.mtv.corp.google.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-29T20:56:48Z","receivedAt":"2016-06-29T20:58:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 29, 2016 at 01:39:17PM -0700, Junio C Hamano wrote:\n\n> > Would it make sense to refuse creating commits that have a commit date\n> > prior to its parents commit date (except when the user gives a\n> > `--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n> \n> I think that has also been discussed in the past. I do not think it\n> would help very much in practice, as projects already have up to 10\n> years (and the ones migrated from CVS, even more) worth of commits\n> they cannot rewrite that may record incorrect committer dates.\n\nYep, it has been discussed and I agree it runs into a lot of corner\ncases.\n\n> If the use of generation number can somehow be limited narrowly, we\n> may be able to incrementally introduce it only for new commits, but\n> I haven't thought things through, so let me do so aloud here ;-)\n\nI think the problem is that you really _do_ want generation numbers for\nold commits. One of the most obvious cases is something like \"tag\n--contains HEAD\", because it has to examine older tags.\n\nSo your history looks something like:\n\n A -- B -- ... Z\n \\ \\\n\t v1.0 HEAD\n\nWithout generation numbers (or some proxy), you have to walk the history\nbetween B..Z to find the answer. With generation numbers, it is\nimmediately obvious.\n\nSo this is the ideal case for generation numbers (the worst cases are\nwhen the things you are looking for are in branchy, close history where\nthe generation numbers don't tell you much; but in such cases the\nwalking is usually not too bad).\n\nSo I think you really do want to be able to generate and store\ngeneration numbers after the fact. That has an added bonus that you do\nnot have to worry about baking incorrect values into your objects; you\ndo the topological walk once, and you _know_ it is correct (at least as\ncorrect as the parent links, but that is our source of truth).\n\nI have patches that generate and store the numbers at pack time, similar\nto the way we do the reachability bitmaps. They're not production ready,\nbut they could probably be made so without too much effort. You wouldn't\nhave ready-made generation numbers for commits since the last full\nrepack, but you can compute them incrementally based on what you do have\nat a cost linear to the unpacked commits (this is the same for bitmaps).\n\n-Peff\n"},{"id":"290535","messageId":"577436DD.8050708@gmail.com","threadId":"42749","inReplyTo":"CAPc5daVC-+0Vr30L_pbcL0GN2OmnGm-+V4tE2WTos_vPRb_S1g@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-06-29T21:00:13Z","receivedAt":"2016-06-29T21:00:37Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-06-29 o 20:59, Junio C Hamano pisze:\n> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n> wrote:\n>\n>> This is no RFE but rather recurring thoughts whenever I'm working with\n>> commit graphs: a topological index attribute for commit objects would be\n>> incredible useful. By \"topological index\" I mean a simple integer for which\n>> following condition holds true:\n>> \n>> if commit C is part of the history of commit D,\n>> then C's topological index is smaller than D's index\n>> \n>> This would allow topological sorting of commits (e.g. in queues) on the fly\n>> and quickly give a \"no\" answer on the question whether D is part of\n>> C's history. \n> \n> Look for \"generation numbers\" in the list archive, perhaps?\n\nIf I remember correctly the discussion, the problem by adding generation number\nto the commit object format was twofold (at least).\n\nFirst there was a problem of backward compatibility, namely what to do with\nexisting repositories, where commit objects do not have generation number.\nObjects in Git are immutable (and I think replacements mechanism wasn't\ninvented yet - anyway too many replacements would slow down operations\nI guess).\n\nSecond objection was of philosophical nature: generation numbers duplicate\n(cache) information that is stored in the graph of revisions. Also, what\nif they get out of sync?\n\nThat is, if I remember the summary of that discussion correctly.\n\n\nAlso, generation numbers (graph level) only help with topological sorting;\nfor finding of two commits are connected (two nodes are connected) people\nplay with different ideas, for example FELINE index:\n http://openproceedings.org/EDBT/2014/paper_166.pdf\n\nNowadays there is also [compressed] bitmap index (if enabled), though I am\nnot sure if it is yet used to speed-up reachability queries\n http://githubengineering.com/counting-objects/\n https://www.eclipsecon.org/2013/sites/eclipsecon.org.2013/files/Scaling%20Up%20JGit%20-%20EclipseCon%202013.pdf\n\n-- \nJakub Narębski\n"},{"id":"290536","messageId":"CAGZ79kZNnbrKFaKGchZ0r5wKCs7pz4RcyYq=0rnD5qSd8XDKXw@mail.gmail.com","threadId":"42749","inReplyTo":"xmqqk2h73f2i.fsf@gitster.mtv.corp.google.com","subject":"Re: topological index field for commit objects","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-29T20:54:01Z","receivedAt":"2016-06-29T21:01:00Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Jun 29, 2016 at 1:39 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> On Wed, Jun 29, 2016 at 11:59 AM, Junio C Hamano wrote:\n>>> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n>>> wrote:\n>>>> This is no RFE but rather recurring thoughts whenever I'm working with\n>>>> commit graphs: a topological index attribute for commit objects would be\n>>>> incredible useful. By \"topological index\" I mean a simple integer for which\n>>>> following condition holds true:\n>>>\n>>> Look for \"generation numbers\" in the list archive, perhaps?\n>>\n>> Thanks for the pointer to the interesting discussions.\n>>\n>> In http://www.spinics.net/lists/git/msg161363.html\n>> Linus wrote in a discussion with Jeff:\n>>\n>>> Right now, we do *have* a \"generation number\". It's just that it's\n>>> very easy to corrupt even by mistake. It's called \"committer date\". We\n>>> could improve on it.\n>>\n>> Would it make sense to refuse creating commits that have a commit date\n>> prior to its parents commit date (except when the user gives a\n>> `--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n>\n> I think that has also been discussed in the past.\n\nI should have guessed that and tried to find it.\n\n> I do not think it\n> would help very much in practice, as projects already have up to 10\n> years (and the ones migrated from CVS, even more) worth of commits\n> they cannot rewrite that may record incorrect committer dates.\n\nChances are that the 10 years of history may be correct time wise as long\nas people don't introduce a bad date malevolently.\n\n> You'd need something like \"you can trust committer dates that are\n> newer that this date\" per project\n\nand git version as old versions of git can still be used later.\n\n> to switch between slow path and\n> fast path, with an updated fsck that knows how to compute that\n> number after you pulled from somebody who used that overriding\n> option.\n\nWell you could have a project setting (`config.sortedDates`)\nthat is automatically computed once when cloning a project and\ndepending on that setting you can go the fast path.\n\nAdditionally when that setting is set, you'd enforce the correct\ndates in committing and merging (read pulling) to carry it on to\nbe true.\n\n>\n> If the use of generation number can somehow be limited narrowly, we\n> may be able to incrementally introduce it only for new commits, but\n> I haven't thought things through, so let me do so aloud here ;-)\n\nI think of it as \"committer date == generation number\", i.e. just a\nspecial form of noting the generation number with gaps in between.\nThis loses the ability to know how many commits there are at maximum\nbetween 2 given \"numbers\" though, which I think is minor.\n\n>\n> Suppose we use it only for this purpose:\n>\n> * When we have two commits, C1 and C2, with generation numbers G1\n> and G2, we can say \"C1 cannot possibly be an ancestor of C2\" if\n> G1 > G2. We cannot say anything else based on generation\n> numbers (or lack thereof).\n>\n> then I think we could just say \"A newly created commit must record\n> generation number G that is larger than generation numbers of its\n> parent commits; ignore parents that lack generation number for the\n> purpose of this sentence\".\n>\n> I am not sure if that limited use is all that useful, though.\n\nI did *not* propose to introduce the generation number, but\nrather meant:\n* we already have committer date\n* it works pretty well\n* only a tiny patch is required to tighten the heuristic to work even better\n (going forward) by avoiding accidents in the history that have\n a committer date earlier than their parents.\n* we postpone drastic changes (i.e. introduction of generation\n numbers or change of algorithms) for now.\n"},{"id":"290542","messageId":"CAGZ79kbjntaTQPNdw9u07AJX3pTWdyKB1fiPqJZ=DZRzNvnKzg@mail.gmail.com","threadId":"42749","inReplyTo":"CAGZ79kZNnbrKFaKGchZ0r5wKCs7pz4RcyYq=0rnD5qSd8XDKXw@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-06-29T21:37:17Z","receivedAt":"2016-06-29T21:37:24Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Jun 29, 2016 at 1:54 PM, Stefan Beller wrote:\n> Chances are that the 10 years of history may be correct time wise as long\n> as people don't introduce a bad date malevolently.\n>\n\nTo answer my own speculation:\nEven git.git violates the timing property, so there is no hope to find\nmany projects\nto have \"parents committer date < committer date\"\n\n$ git log --format=\"%H %ct %P\" HEAD | {\n> while read sha sha_date parents ; do\n> for p in $parents ; do\n> # echo \"$id, $parents, $p\"\n> pd=$(git show -s --format=\"%ct\" $p)\n> if test $pd -gt $sha_date ; then\n> echo $sha\n> fi\n> done\n> done\n> }\n619a644d6daef56d70aeca85514e2d281eb483a5\n776398709dee4050fc194fec45c5818ba9b01afe\ned19f367220a50e4e2a5c1a00b03c14eafcaba89\n\n(out of curiosity these are:)\n(2009-10-18 12:34:56, \"checkout A...B\" switches to the merge base\nbetween A and B)\n(2007-09-01 23:53:47, Keep last used delta base in the delta window)\n(2006-03-03 23:29:56, Add a Documentation/git-tools.txt)\n"},{"id":"290543","messageId":"20160629214343.GA3682@sigill.intra.peff.net","threadId":"42749","inReplyTo":"CAGZ79kbjntaTQPNdw9u07AJX3pTWdyKB1fiPqJZ=DZRzNvnKzg@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-29T21:43:44Z","receivedAt":"2016-06-29T21:44:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 29, 2016 at 02:37:17PM -0700, Stefan Beller wrote:\n\n> On Wed, Jun 29, 2016 at 1:54 PM, Stefan Beller wrote:\n> > Chances are that the 10 years of history may be correct time wise as long\n> > as people don't introduce a bad date malevolently.\n> >\n> \n> To answer my own speculation:\n> Even git.git violates the timing property, so there is no hope to find\n> many projects\n> to have \"parents committer date < committer date\"\n\nIt's expected and reasonable for there to be some skew. People's clocks\naren't all perfectly synced. The question is one of how _much_ skew\nyou're willing to tolerate (and any algorithms obviously need to allow\nthat much, too).\n\nIn some places we allow 24 hours of skew between any two commits. In\nothers we allow up to 5 skewed commits in a row.\n\nThat may not be enough in general, though. E.g.:\n\n> 619a644d6daef56d70aeca85514e2d281eb483a5\n\nThis one is a 3-day skew.\n\n-Peff\n"},{"id":"290544","messageId":"5774426F.3090000@gmail.com","threadId":"42749","inReplyTo":"20160629205647.GA25987@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-06-29T21:49:35Z","receivedAt":"2016-06-29T21:50:20Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-06-29 o 22:56, Jeff King pisze:\n> On Wed, Jun 29, 2016 at 01:39:17PM -0700, Junio C Hamano wrote:\n> \n>>> Would it make sense to refuse creating commits that have a commit date\n>>> prior to its parents commit date (except when the user gives a\n>>> `--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n>>\n>> I think that has also been discussed in the past. I do not think it\n>> would help very much in practice, as projects already have up to 10\n>> years (and the ones migrated from CVS, even more) worth of commits\n>> they cannot rewrite that may record incorrect committer dates.\n> \n> Yep, it has been discussed and I agree it runs into a lot of corner\n> cases.\n> \n>> If the use of generation number can somehow be limited narrowly, we\n>> may be able to incrementally introduce it only for new commits, but\n>> I haven't thought things through, so let me do so aloud here ;-)\n> \n> I think the problem is that you really _do_ want generation numbers for\n> old commits. One of the most obvious cases is something like \"tag\n> --contains HEAD\", because it has to examine older tags.\n> \n> So your history looks something like:\n> \n> A -- B -- ... Z\n> \\ \\\n> \t v1.0 HEAD\n> \n> Without generation numbers (or some proxy), you have to walk the history\n> between B..Z to find the answer. With generation numbers, it is\n> immediately obvious.\n> \n> So this is the ideal case for generation numbers (the worst cases are\n> when the things you are looking for are in branchy, close history where\n> the generation numbers don't tell you much; but in such cases the\n> walking is usually not too bad).\n\nThere are other approaches (special indices) that help reachability\nqueries beside \"generation number\".\n\n> \n> So I think you really do want to be able to generate and store\n> generation numbers after the fact. That has an added bonus that you do\n> not have to worry about baking incorrect values into your objects; you\n> do the topological walk once, and you _know_ it is correct (at least as\n> correct as the parent links, but that is our source of truth).\n\nBy the way, what should happen if you add a replacement (in the git-replace\nmeaning) that creates a shortcut, therefore invalidating generation numbers,\nat least in strict sense - committerdate as generation number would be still\ngood, I think?\n \n> I have patches that generate and store the numbers at pack time, similar\n> to the way we do the reachability bitmaps. They're not production ready,\n> but they could probably be made so without too much effort. You wouldn't\n> have ready-made generation numbers for commits since the last full\n> repack, but you can compute them incrementally based on what you do have\n> at a cost linear to the unpacked commits (this is the same for bitmaps).\n\nDo Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\nlimited to object counting?\n\n-- \nJakub Narębski\n\n"},{"id":"290545","messageId":"20160629220049.GA4416@sigill.intra.peff.net","threadId":"42749","inReplyTo":"5774426F.3090000@gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-29T22:00:49Z","receivedAt":"2016-06-29T22:01:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:\n\n> > So this is the ideal case for generation numbers (the worst cases are\n> > when the things you are looking for are in branchy, close history where\n> > the generation numbers don't tell you much; but in such cases the\n> > walking is usually not too bad).\n> \n> There are other approaches (special indices) that help reachability\n> queries beside \"generation number\".\n\nYes, though generation numbers can help with more questions (e.g., \"what\nis the merge base\").\n\n> By the way, what should happen if you add a replacement (in the git-replace\n> meaning) that creates a shortcut, therefore invalidating generation numbers,\n> at least in strict sense - committerdate as generation number would be still\n> good, I think?\n\nThis is one of the open questions. My older patches turned them off when\nreplacements and grafts are in effect.\n\n> > I have patches that generate and store the numbers at pack time, similar\n> > to the way we do the reachability bitmaps. They're not production ready,\n> > but they could probably be made so without too much effort. You wouldn't\n> > have ready-made generation numbers for commits since the last full\n> > repack, but you can compute them incrementally based on what you do have\n> > at a cost linear to the unpacked commits (this is the same for bitmaps).\n> \n> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n> limited to object counting?\n\nAt GitHub we are using them for --contains analysis, along with mass\nahead/behind (e.g., as in https://github.com/gitster/git/branches). My\nplan is to send patches upstream, but they need some cleanup first.\n\n-Peff\n"},{"id":"290548","messageId":"xmqqlh1n1w84.fsf@gitster.mtv.corp.google.com","threadId":"42749","inReplyTo":"20160629220049.GA4416@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-29T22:11:39Z","receivedAt":"2016-06-29T22:12:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Yes, though generation numbers can help with more questions (e.g., \"what\n> is the merge base\").\n\nHmm, how? I have two commits, with generation number 38 and 47,\nrespectively. What generation number does the commit that is the\nmerge base of these two commits?\n\nI know we can say that 38 cannot possibly be a descendant of 47, but\ncan we say anything else that is useful?\n\n"},{"id":"290549","messageId":"2fff9bc4-0c40-dc51-1cf6-68b359cb16bf@syntevo.com","threadId":"42749","inReplyTo":"xmqqk2h73f2i.fsf@gitster.mtv.corp.google.com","subject":"Re: topological index field for commit objects","fromName":"Marc Strapetz","fromEmail":"marc.strapetz@syntevo.com","sentAt":"2016-06-29T22:15:36Z","receivedAt":"2016-06-29T22:24:16Z","isPatch":false,"sender":{"key":"marc.strapetz@syntevo.com","avatar":"https://avatars.githubusercontent.com/u/3380730?v=4"},"body":"On 29.06.2016 22:39, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> On Wed, Jun 29, 2016 at 11:59 AM, Junio C Hamano wrote:\n>>> On Wed, Jun 29, 2016 at 11:31 AM, Marc Strapetz\n>>> wrote:\n>>>> This is no RFE but rather recurring thoughts whenever I'm working with\n>>>> commit graphs: a topological index attribute for commit objects would be\n>>>> incredible useful. By \"topological index\" I mean a simple integer for which\n>>>> following condition holds true:\n>>>\n>>> Look for \"generation numbers\" in the list archive, perhaps?\n>>\n>> Thanks for the pointer to the interesting discussions.\n>>\n>> In http://www.spinics.net/lists/git/msg161363.html\n>> Linus wrote in a discussion with Jeff:\n>>\n>>> Right now, we do *have* a \"generation number\". It's just that it's\n>>> very easy to corrupt even by mistake. It's called \"committer date\". We\n>>> could improve on it.\n>>\n>> Would it make sense to refuse creating commits that have a commit date\n>> prior to its parents commit date (except when the user gives a\n>> `--dammit-I-know-I-break-a-wildy-used-heuristic`)?\n>\n> I think that has also been discussed in the past. I do not think it\n> would help very much in practice, as projects already have up to 10\n> years (and the ones migrated from CVS, even more) worth of commits\n> they cannot rewrite that may record incorrect committer dates.\n> You'd need something like \"you can trust committer dates that are\n> newer that this date\" per project to switch between slow path and\n> fast path, with an updated fsck that knows how to compute that\n> number after you pulled from somebody who used that overriding\n> option.\n>\n> If the use of generation number can somehow be limited narrowly, we\n> may be able to incrementally introduce it only for new commits, but\n> I haven't thought things through, so let me do so aloud here ;-)\n>\n> Suppose we use it only for this purpose:\n>\n> * When we have two commits, C1 and C2, with generation numbers G1\n> and G2, we can say \"C1 cannot possibly be an ancestor of C2\" if\n> G1 > G2. We cannot say anything else based on generation\n> numbers (or lack thereof).\n>\n> then I think we could just say \"A newly created commit must record\n> generation number G that is larger than generation numbers of its\n> parent commits; ignore parents that lack generation number for the\n> purpose of this sentence\".\n\n From algorithm perspective, for already existing repositories you would \nstill have to switch from an optimized generation number code to the \ncurrent commit-time based code. That could things make even more complex \nand it's possibly expensive to determine whether a repository has full \ngeneration number support or not.\n\nOn the other hand, for new repositories, you could immediately use \ngeneration number based algorithms. So it could be \"A newly created \ncommit must record generation number G that is larger than generation \nnumbers of its parent commits if all parents commits have a generation \nnumber recorded; otherwise do not record a generation number\". Something \nlike \"git filter-branch\" might already be sufficient to convert \nrepositories.\n\nGit versions released in 2019 may start issuing warnings if HEAD has no \ngeneration number assigned and Git versions released in 2025 may \ncompletely refuse to work with such repositories.\n\nIn the interim period, a local cache as Jeff is proposing could serve as \nsecondary source for generation numbers. This would allow to phase out \ncurrent algorithms immediately.\n\n-Marc\n\n\n\n"},{"id":"290550","messageId":"20160629223007.GA4726@sigill.intra.peff.net","threadId":"42749","inReplyTo":"xmqqlh1n1w84.fsf@gitster.mtv.corp.google.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-29T22:30:07Z","receivedAt":"2016-06-29T22:30:18Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 29, 2016 at 03:11:39PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Yes, though generation numbers can help with more questions (e.g., \"what\n> > is the merge base\").\n> \n> Hmm, how? I have two commits, with generation number 38 and 47,\n> respectively. What generation number does the commit that is the\n> merge base of these two commits?\n> \n> I know we can say that 38 cannot possibly be a descendant of 47, but\n> can we say anything else that is useful?\n\nI don't think it can give you the answer immediately from those values,\nbut in general generation numbers help you bound actual traversals and\navoid walking down unproductive paths. So comparing 38 and 47 is not\nnearly as useful as walking from 47 down to 37 and saying \"I know that I\ncannot possibly reach 38 by walking further\".\n\nI haven't thought hard specifically about merge bases computation, so\nperhaps that is a case that isn't helped at all. It has been a while\nsince I've looked into this, but I recall there were some computations\nthat are hard to improve with bitmaps. I may also simply be\nmis-remembering; in my patches generations were tightly tied to having a\npackv4-style cache of commit properties that can be used rather than\ninflating the commit object itself. That cache helps any time you walk\nby speeding up the parse_commit() process. But it's a per-commit\nspeedup. It doesn't change the algorithmic complexity of what you're\ndoing.\n\n-Peff\n"},{"id":"290586","messageId":"5774F4C7.805@gmail.com","threadId":"42749","inReplyTo":"20160629220049.GA4416@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-06-30T10:30:31Z","receivedAt":"2016-06-30T10:31:38Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-06-30 o 00:00, Jeff King pisze:\n> On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:\n> \n>>> So this is the ideal case for generation numbers (the worst cases are\n>>> when the things you are looking for are in branchy, close history where\n>>> the generation numbers don't tell you much; but in such cases the\n>>> walking is usually not too bad).\n>>\n>> There are other approaches (special indices) that help reachability\n>> queries beside \"generation number\".\n> \n> Yes, though generation numbers can help with more questions (e.g., \"what\n> is the merge base\").\n\nWell, those special indices usually need generation number anyway. For\nexample FELINE indices^1 (from \"Reachability Queries in Very Large Graphs\",\nhttp://openproceedings.org/EDBT/2014/paper_166.pdf, that I found when\ntrying to find more about compressed bitmap indices used by Git) also\nutilize generation numbers to speed up reachability analysis. The idea\nbehind FELINE is to associate every vertex (commit) with a unique ordered\npair of natural integers (i.e. two more numbers, in addition to the level\naka generation number), so that partial order over N^2 is superset of\npartial order of graph (DAG of revisions). It can answer in O(1) that\nnodes are not connected, and cut search space if they are.\n\nBTW. some references in this paper (\"Related work\" section) use PWAH\ncompression scheme - perhaps it would work with EWAH that Git uses?\n\n1. FELINE = Fast rEfined onLINE search ... or fun with acronyms\n\n>> By the way, what should happen if you add a replacement (in the git-replace\n>> meaning) that creates a shortcut, therefore invalidating generation numbers,\n>> at least in strict sense - committerdate as generation number would be still\n>> good, I think?\n> \n> This is one of the open questions. My older patches turned them off when\n> replacements and grafts are in effect.\n\nWell, if you store the cache of generation numbers in the packfile, or in\nthe index of the packfile, or in the bitmap file, or in separate bitmap-like\nfile, generating them on repack, then of course any grafts or replacements\ninvalidate them... though for low level commands (like object counting)\nreplacements are transparent -- or rather they are (and can be) treated as\nany other ref for reachability analysis.\n\nWell, if there are no grafts, you could still use them for doing\n\"git --no-replace-objects log ...\", isn't it?\n\nSIDENOTE: should grafts be deprecated and later removed, now that Git has\nsuperior alternative in the form of git-replace, and a simple way to convert\ngrafts to replacements?\n\nAnyway, if file with mapping from revisions to its generation numbers\nwere stored outside of packfiles, it could simply be updated / rewritten\nwhen adding new replacement. You could use one cache for no-replace,\nand one for replace. Though I do wonder if it would be possible to do\nsuch rewrite fast... well, fast enough assuming that adding replacements\nis rare.\n\nAnswering my own question:\n>> committerdate as generation number would be still good, I think?\nNo, it wouldn't:\n\n pre replace:\n\n 1 <-- 2 <-- 3 <-- 5 <--\n \\\n \\----- 4 <-- 6 <-- 7 <-- 8\n\n post replace\n\n 1 <-- 2 \\-- 3' <-- 5\n \\ \\\n \\------ 4 <-- 6 <-- 7 <-- 8 <--\\\n\nEither the replacement commit would have generation number correct, but\nits child wouldn't, or its child would have correct generation number but\nthe replacement wouldn't.\n \n>>> I have patches that generate and store the numbers at pack time, similar\n>>> to the way we do the reachability bitmaps.\n\nAh, so those cached generation numbers are generated and stored at pack\ntime. Where you store them: is it a separate file? Bitmap file? Packfile?\n\n>>> They're not production ready,\n>>> but they could probably be made so without too much effort. You wouldn't\n>>> have ready-made generation numbers for commits since the last full\n>>> repack, but you can compute them incrementally based on what you do have\n>>> at a cost linear to the unpacked commits (this is the same for bitmaps).\n>>\n>> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n>> limited to object counting?\n> \n> At GitHub we are using them for --contains analysis, along with mass\n> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n> plan is to send patches upstream, but they need some cleanup first.\n\nThat would be nice to have, please.\n\nEr, is mass ahead/behind something that can be plugged into Git\n(e.g. for \"git branch -v -v\"), or is it something GitHub-specific?\n\n\nP.S. Having Git ensure that committerdate (as an epoch) is greater\nthan committerdates of its parents at the commit creation time (with\nproviding warning about time skew, perhaps not doing it if skew is\ntoo large) would be not costly. No need to add anything, and it would\nhelp future queries to be faster, I think.\n\n-- \nJakub Narębski\n\n"},{"id":"290607","messageId":"CA+55aFy2AEe7ew5Px=2Uit6hraGV9zFr=JZ57rSYXWMQ4nMjeg@mail.gmail.com","threadId":"42749","inReplyTo":"5774F4C7.805@gmail.com","subject":"Re: topological index field for commit objects","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2016-06-30T18:12:52Z","receivedAt":"2016-06-30T18:13:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, Jun 30, 2016 at 3:30 AM, Jakub Narębski wrote:\n>\n> P.S. Having Git ensure that committerdate (as an epoch) is greater\n> than committerdates of its parents at the commit creation time (with\n> providing warning about time skew, perhaps not doing it if skew is\n> too large) would be not costly. No need to add anything, and it would\n> help future queries to be faster, I think.\n\nSo I think git should check the committer date (ie verify that the\ncommitetr date of a new commit is always equal to or more recent than\nall the parents).\n\nBut we should probably allow some slop for when machines are out of\nsync (think build farms etc automation that may do automated commits,\nbut the clocks on different machines may be off by a few seconds). We\nalready do things like that in some of the use of committer dates -\nsee for example CUTOFF_DATE_SLOP)\n\nAnd we should probably allow the user to override the refusal to\ncreate new commits with bogus dates - think importing repositories etc\nwhere you may have reasons to just say \"that's just how it was\".\n\nAnd it will take years for that to percolate out to all users, so it's\nnot like it will fix things immediately, but then some time from now,\nwe can consider commit dates to be more reliably generation numbers.\n\nI do think that it's ok to cache generation numbers somewhere if there\nis an algorithm that can make use of them, but every time this comes\nup, it's just not been important enough to make a big deal and a new\nincompatible object format for it. The committer date is preexisting\nand has existing pseudo-generation-number usage, so..improving on the\nquality of it sounds like a good idea.\n\nThe first step should probably be to make fsck warn about the existing\ncases of \"commit has older date than parents\". Something like the\nattached patch, perhaps?\n\n Linus\n\n\n fsck.c | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\ndiff --git a/fsck.c b/fsck.c\nindex 05315451c56f..722b65371d38 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -60,6 +60,7 @@\n \tFUNC(NULL_SHA1, WARN) \\\n \tFUNC(ZERO_PADDED_FILEMODE, WARN) \\\n \tFUNC(NUL_IN_COMMIT, WARN) \\\n+\tFUNC(DATE_ORDERING, WARN) \\\n \t/* infos (reported as warnings, but ignored by default) */ \\\n \tFUNC(BAD_TAG_NAME, INFO) \\\n \tFUNC(MISSING_TAGGER_ENTRY, INFO)\n@@ -604,6 +605,17 @@ static int fsck_ident(const char **ident, struct object *obj, struct fsck_option\n \treturn 0;\n }\n \n+static void fsck_commit_date(struct fsck_options *options, struct commit *commit)\n+{\n+\tstruct commit_list *p;\n+\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tstruct commit *parent = p->item;\n+\t\tif (commit->date < parent->date)\n+\t\t\treport(options, &commit->object, FSCK_MSG_DATE_ORDERING, \"Bad commit date ordering with parent\");\n+\t}\n+}\n+\n static int fsck_commit_buffer(struct commit *commit, const char *buffer,\n \tunsigned long size, struct fsck_options *options)\n {\n@@ -650,6 +662,7 @@ static int fsck_commit_buffer(struct commit *commit, const char *buffer,\n \t\t\t\treturn err;\n \t\t}\n \t}\n+\tfsck_commit_date(options, commit);\n \tauthor_count = 0;\n \twhile (skip_prefix(buffer, \"author \", &buffer)) {\n \t\tauthor_count++;\n"},{"id":"290619","messageId":"5775ADA0.3000906@gmail.com","threadId":"42749","inReplyTo":"CA+55aFy2AEe7ew5Px=2Uit6hraGV9zFr=JZ57rSYXWMQ4nMjeg@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-06-30T23:39:12Z","receivedAt":"2016-06-30T23:41:22Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-06-30 o 20:12, Linus Torvalds pisze:\n> On Thu, Jun 30, 2016 at 3:30 AM, Jakub Narębski wrote:\n>>\n>> P.S. Having Git ensure that committerdate (as an epoch) is greater\n>> than committerdates of its parents at the commit creation time (with\n>> providing warning about time skew, perhaps not doing it if skew is\n>> too large) would be not costly. No need to add anything, and it would\n>> help future queries to be faster, I think.\n> \n> So I think git should check the committer date (ie verify that the\n> committer date of a new commit is always equal to or more recent than\n> all the parents).\n> \n> But we should probably allow some slop for when machines are out of\n> sync (think build farms etc automation that may do automated commits,\n> but the clocks on different machines may be off by a few seconds). We\n> already do things like that in some of the use of committer dates -\n> see for example CUTOFF_DATE_SLOP).\n\nThe problem with this idea is that the clock skew might be in two\ndirections, but it does fix/help only one. If committer's clock\nlags behind true time, the automatic bump to have committerdate of\na new commit be greater than committerdates of all its parent is quite\nhelpful.\n\nHowever, if some developer has his or her clock misconfigured so that\nit gives time in the future, this feature would not help. Commits from\nsuch developer (from such machine) would screw it up for others.\n\nThat's why I think some limit is needed. For example, if for some\nreason commit was created with committer date 3 days in the future,\nwe would probably do not want for other developers to have to lie\nabout when they created their commit.\n\n\nOr did you mean that if the date for new commit is in the past\nof committerdates of its parents, its all right when it is within\nslop?\n\n> \n> And we should probably allow the user to override the refusal to\n> create new commits with bogus dates - think importing repositories etc\n> where you may have reasons to just say \"that's just how it was\".\n\nRight. I was thinking about (ab)using --no-verify flag, or perhaps\nprompting user if the terminal is interactive. But perhaps a separate\nflag / environment variable would be better...\n\n> And it will take years for that to percolate out to all users, so it's\n> not like it will fix things immediately, but then some time from now,\n> we can consider commit dates to be more reliably generation numbers.\n[...]\n\nThat's the idea of the proposal.\n\n-- \nJakub Narębski\n\n"},{"id":"290621","messageId":"20160630235901.GA24593@glandium.org","threadId":"42749","inReplyTo":"CA+55aFy2AEe7ew5Px=2Uit6hraGV9zFr=JZ57rSYXWMQ4nMjeg@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-06-30T23:59:01Z","receivedAt":"2016-07-01T00:00:01Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Thu, Jun 30, 2016 at 11:12:52AM -0700, Linus Torvalds wrote:\n> On Thu, Jun 30, 2016 at 3:30 AM, Jakub Narębski wrote:\n> >\n> > P.S. Having Git ensure that committerdate (as an epoch) is greater\n> > than committerdates of its parents at the commit creation time (with\n> > providing warning about time skew, perhaps not doing it if skew is\n> > too large) would be not costly. No need to add anything, and it would\n> > help future queries to be faster, I think.\n> \n> So I think git should check the committer date (ie verify that the\n> commitetr date of a new commit is always equal to or more recent than\n> all the parents).\n> \n> But we should probably allow some slop for when machines are out of\n> sync (think build farms etc automation that may do automated commits,\n> but the clocks on different machines may be off by a few seconds). We\n> already do things like that in some of the use of committer dates -\n> see for example CUTOFF_DATE_SLOP)\n> \n> And we should probably allow the user to override the refusal to\n> create new commits with bogus dates - think importing repositories etc\n> where you may have reasons to just say \"that's just how it was\".\n> \n> And it will take years for that to percolate out to all users, so it's\n> not like it will fix things immediately, but then some time from now,\n> we can consider commit dates to be more reliably generation numbers.\n\nThis is an assumption that might work for git repositories, but not for\nforeign repositories imported in git (think e.g. mercurial repositories\naccessed with a remote helper)\n\nMike\n"},{"id":"290622","messageId":"20160701031711.GA4832@sigill.intra.peff.net","threadId":"42749","inReplyTo":"CA+55aFy2AEe7ew5Px=2Uit6hraGV9zFr=JZ57rSYXWMQ4nMjeg@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-01T03:17:12Z","receivedAt":"2016-07-01T03:24:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 30, 2016 at 11:12:52AM -0700, Linus Torvalds wrote:\n\n> I do think that it's ok to cache generation numbers somewhere if there\n> is an algorithm that can make use of them, but every time this comes\n> up, it's just not been important enough to make a big deal and a new\n> incompatible object format for it. The committer date is preexisting\n> and has existing pseudo-generation-number usage, so..improving on the\n> quality of it sounds like a good idea.\n\nIf you are OK with a cache, I don't think one needs to change the object\nformat at all. It can be computed on the fly, and is purely a local\noptimization.\n\n> The first step should probably be to make fsck warn about the existing\n> cases of \"commit has older date than parents\". Something like the\n> attached patch, perhaps?\n\nI have mixed feelings on this, because it forces the user to confront\nthe issue at a time that's potentially very far from when it actually\nhappened (and often when it is not their fault).\n\nI expect most people don't run fsck at all under normal circumstances,\nso it is only when they have a problem of some sort that they would see\nthis warning at all. It would kick in and prevent objects being\ntransferred when things like receive.fsckObjects are configured, but\nit's not on by default. GitHub does enable it, so pushing there is often\nthe first notification people get about any kind of problem.\n\nThis is a general problem with all fsck-driven warnings (people may\nfetch without realizing they're getting breakage, and such objects may\nget years of history built on top). But I think it can be even worse\nwith timestamps, because the broken state may not even be recognizable\nwhen you first fetch the troublesome object.\n\nE.g., imagine somebody else has their clock set forward, and you fetch\nfrom them. Their object by itself is not broken. It is only when you\nwant to commit on top of it, with the correct clock, that the broken\nstate is created (and then, we cannot know whether it is your clock or\nthe original committer's clock that is bad).\n\nSo I think it would be more productive to put a check like this in \"git\ncommit\" rather than (or perhaps in addition to) fsck. That prevents\nus creating the broken relationship, but it does still mean the user may\nhave to to go back and tell the original committer that their clock was\nbroken.\n\nYou could also have the fsck check look not only for out-of-order\ncommits, but also commits in the future (from the perspective of the\nreceiver). That would reject such broken commits before they even hit\nyour repository (though again, it is unclear in such a case if the\ncommit is broken or the clock of the checker).\n\n> +static void fsck_commit_date(struct fsck_options *options, struct commit *commit)\n> +{\n> +\tstruct commit_list *p;\n> +\n> +\tfor (p = commit->parents; p; p = p->next) {\n> +\t\tstruct commit *parent = p->item;\n> +\t\tif (commit->date < parent->date)\n> +\t\t\treport(options, &commit->object, FSCK_MSG_DATE_ORDERING, \"Bad commit date ordering with parent\");\n> +\t}\n> +}\n\nI didn't test it, but I suspect this won't work reliably, as we do not\nalways have the parents parsed during an fsck check (e.g., during\n\"index-pack --strict\").\n\n-Peff\n"},{"id":"290635","messageId":"df4f72c0-72fc-a779-3fda-3fbc146419db@syntevo.com","threadId":"42749","inReplyTo":"20160701031711.GA4832@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Marc Strapetz","fromEmail":"marc.strapetz@syntevo.com","sentAt":"2016-07-01T06:45:33Z","receivedAt":"2016-07-01T06:44:32Z","isPatch":false,"sender":{"key":"marc.strapetz@syntevo.com","avatar":"https://avatars.githubusercontent.com/u/3380730?v=4"},"body":"On 01.07.2016 05:17, Jeff King wrote:\n> On Thu, Jun 30, 2016 at 11:12:52AM -0700, Linus Torvalds wrote:\n>\n>> I do think that it's ok to cache generation numbers somewhere if there\n>> is an algorithm that can make use of them, but every time this comes\n>> up, it's just not been important enough to make a big deal and a new\n>> incompatible object format for it. The committer date is preexisting\n>> and has existing pseudo-generation-number usage, so..improving on the\n>> quality of it sounds like a good idea.\n>\n> If you are OK with a cache, I don't think one needs to change the object\n> format at all. It can be computed on the fly, and is purely a local\n> optimization.\n\nWhat I like about the local cache is that it can be fixed easily: if we \nhad generation numbers already, there would certainly be a few \nrepositories now which would violate the parent - child condition \n(however that has happened) and then you have to deal with this scenario \nanyway (or tell the user to rewrite his entire history). It's a lot \neasier to throw away and rebuild the cache.\n\nAlso, the local cache can be improved over time, starting with \ngeneration numbers now and one day supporting a FELINE index or whatever \nwill come.\n\n-Marc\n"},{"id":"290636","messageId":"20160701065452.GE5358@sigill.intra.peff.net","threadId":"42749","inReplyTo":"5774F4C7.805@gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-01T06:54:52Z","receivedAt":"2016-07-01T07:01:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 30, 2016 at 12:30:31PM +0200, Jakub Narębski wrote:\n\n> > This is one of the open questions. My older patches turned them off when\n> > replacements and grafts are in effect.\n> \n> Well, if you store the cache of generation numbers in the packfile, or in\n> the index of the packfile, or in the bitmap file, or in separate bitmap-like\n> file, generating them on repack, then of course any grafts or replacements\n> invalidate them... though for low level commands (like object counting)\n> replacements are transparent -- or rather they are (and can be) treated as\n> any other ref for reachability analysis.\n> \n> Well, if there are no grafts, you could still use them for doing\n> \"git --no-replace-objects log ...\", isn't it?\n\nYes, replace refs don't invalidate the concept of a cache. It just\nmeans that you invalidate the invariants of the cache for a specific\nview, so you need a cache which matches that view.\n\nIt has been several years, but I remember at one point having patches\nthat summarized the graft/replace state as a single hash, and only used\nthe cache if it matched that state. So you could actually keep a cache\nfor some set of replace-refs that you have, as well as a cache for the\ncase that you've turned them off, etc.\n\nI don't think that level of complexity is really worth it, though.\n\n> >>> I have patches that generate and store the numbers at pack time, similar\n> >>> to the way we do the reachability bitmaps.\n> \n> Ah, so those cached generation numbers are generated and stored at pack\n> time. Where you store them: is it a separate file? Bitmap file? Packfile?\n\nThere were a few iterations of the concept over the years, but the\npack-time one uses a separate file with the same name prefix as a pack\n(similar to the way bitmaps are stored). The big advantage there is that\nwe can piggy-back on the pack .idx to avoid having to write each sha1\nagain (20 bytes per commit, whereas the actual data we're caching is\nonly 4 bytes).\n\n> > At GitHub we are using them for --contains analysis, along with mass\n> > ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n> > plan is to send patches upstream, but they need some cleanup first.\n> \n> That would be nice to have, please.\n> \n> Er, is mass ahead/behind something that can be plugged into Git\n> (e.g. for \"git branch -v -v\"), or is it something GitHub-specific?\n\nWe have a custom command, \"git ahead-behind\", where you can specify\narbitrary pairs of commits on stdin. But it's all backed by a function\nwhich, yes, could be plugged into \"branch -v -v\". It caches any bitmaps\nit needs, so if you are doing 100 ahead/behind comparisons against\n\"master\", for example, it only has to find the bitmap for \"master\" once\n(remember that we sometimes have to traverse to complete a bitmap when\na branch has been updated since the last repack).\n\n-Peff\n"},{"id":"290647","messageId":"57763C78.3020509@gmail.com","threadId":"42749","inReplyTo":"20160701031711.GA4832@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-07-01T09:48:40Z","receivedAt":"2016-07-01T09:49:34Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-07-01 o 05:17, Jeff King pisze:\n> On Thu, Jun 30, 2016 at 11:12:52AM -0700, Linus Torvalds wrote:\n> \n>> I do think that it's ok to cache generation numbers somewhere if there\n>> is an algorithm that can make use of them, but every time this comes\n>> up, it's just not been important enough to make a big deal and a new\n>> incompatible object format for it. The committer date is preexisting\n>> and has existing pseudo-generation-number usage, so..improving on the\n>> quality of it sounds like a good idea.\n> \n> If you are OK with a cache, I don't think one needs to change the object\n> format at all. It can be computed on the fly, and is purely a local\n> optimization.\n\nNote that if cache is generated during (re)packing, it could be optimized\nfor reading. If we want a cache that follow replacements, it would need\nto be adjusted after each new or modified replacement; assuming that one\ndoesn't modify replacements by hand (then Git would need to detect changes,\nand modify cache if needed, perhaps on query, e.g. \"git log\").\n\n>> The first step should probably be to make fsck warn about the existing\n>> cases of \"commit has older date than parents\". Something like the\n>> attached patch, perhaps?\n> \n> I have mixed feelings on this, because it forces the user to confront\n> the issue at a time that's potentially very far from when it actually\n> happened (and often when it is not their fault).\n\nIt would be nice to have as an optional check, like e.g. unreachable\nobjects, or use warning instead of error, like e.g. dangling objects\nwarning. This would be the default; it can always be changed using\nthe `fsck.` and `receive.fsck.` configuration variables.\n\nThis way we could use this mode to adjust clock-skew heuristics that\nGit uses to speed up reachability queries (including time slop), be\nit automatically or via a configuration variable.\n\n[...]\n> E.g., imagine somebody else has their clock set forward, and you fetch\n> from them. Their object by itself is not broken. It is only when you\n> want to commit on top of it, with the correct clock, that the broken\n> state is created (and then, we cannot know whether it is your clock or\n> the original committer's clock that is bad).\n> \n> So I think it would be more productive to put a check like this in \"git\n> commit\" rather than (or perhaps in addition to) fsck. That prevents\n> us creating the broken relationship, but it does still mean the user may\n> have to to go back and tell the original committer that their clock was\n> broken.\n\nWell, check at \"git commit\" time (perhaps with automatic fixing to used\ncommitterdate for the commit being created, within specified conditions)\ncannot distinguish between the two cases:\n\n * committerdate in parent commit(s) is correct,\n but the clock is in the past\n\n * committerdate in parent commit(s) is incorrect, and in the future,\n while the clock is correct\n \n> You could also have the fsck check look not only for out-of-order\n> commits, but also commits in the future (from the perspective of the\n> receiver). That would reject such broken commits before they even hit\n> your repository (though again, it is unclear in such a case if the\n> commit is broken or the clock of the checker).\n\nWell, one heuristics is that if commits in the future, and/or commits\nwith committerdate out of order have all the same committer, then\nprobably commits are broken. Another \"heuristics\" would be to assume\nthat if you invoked date-checking functionality, you have ensured that\nyour clock is correct.\n\n-- \nJakub Narębski\n\n\n"},{"id":"290648","messageId":"57763F00.4070409@gmail.com","threadId":"42749","inReplyTo":"20160701065452.GE5358@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-07-01T09:59:28Z","receivedAt":"2016-07-01T10:00:06Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-07-01 o 08:54, Jeff King pisze:\n> On Thu, Jun 30, 2016 at 12:30:31PM +0200, Jakub Narębski wrote:\n> \n>>> This is one of the open questions. My older patches turned them off when\n>>> replacements and grafts are in effect.\n>>\n>> Well, if you store the cache of generation numbers in the packfile, or in\n>> the index of the packfile, or in the bitmap file, or in separate bitmap-like\n>> file, generating them on repack, then of course any grafts or replacements\n>> invalidate them... though for low level commands (like object counting)\n>> replacements are transparent -- or rather they are (and can be) treated as\n>> any other ref for reachability analysis.\n>>\n>> Well, if there are no grafts, you could still use them for doing\n>> \"git --no-replace-objects log ...\", isn't it?\n> \n> Yes, replace refs don't invalidate the concept of a cache. It just\n> means that you invalidate the invariants of the cache for a specific\n> view, so you need a cache which matches that view.\n> \n> It has been several years, but I remember at one point having patches\n> that summarized the graft/replace state as a single hash, and only used\n> the cache if it matched that state. So you could actually keep a cache\n> for some set of replace-refs that you have, as well as a cache for the\n> case that you've turned them off, etc.\n> \n> I don't think that level of complexity is really worth it, though.\n\nWell, you could always update the reachability-helpers cache when running\n`git replace` command, and when fetching into 'refs/replace' namespace...\n\n...but this wouldn't take into account the fact that you can change\nreplace refs \"by hand\", and that grafts file^{1} is only editable by hand.\nSo at query time Git would need to check (e.g. via hash of graft file,\nhash of packed-refs refs/replace namespace, concatenated) that said\ncache is still valid for replace-respecting view. And perhaps update\nsaid cache.\n\nThough if we limit ourself to the replacements mechanism, we could\nhave a configuration variable saying \"I will manipulate replacements\nonly using git-replace, and I want faster reachability\", isn't it?\n\n\n1.) Can we deprecate and remove grafts mechanism now that we have superior\nsolution and migration mechanism? \n \n>>>>> I have patches that generate and store the numbers at pack time, similar\n>>>>> to the way we do the reachability bitmaps.\n>>\n>> Ah, so those cached generation numbers are generated and stored at pack\n>> time. Where you store them: is it a separate file? Bitmap file? Packfile?\n> \n> There were a few iterations of the concept over the years, but the\n> pack-time one uses a separate file with the same name prefix as a pack\n> (similar to the way bitmaps are stored). The big advantage there is that\n> we can piggy-back on the pack .idx to avoid having to write each sha1\n> again (20 bytes per commit, whereas the actual data we're caching is\n> only 4 bytes).\n\nDoes it use any lightweight compression mechanism, or is it not needed?\nHow does the format of this file looks like?\n \n>>> At GitHub we are using them for --contains analysis, along with mass\n>>> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n>>> plan is to send patches upstream, but they need some cleanup first.\n>>\n>> That would be nice to have, please.\n>>\n>> Er, is mass ahead/behind something that can be plugged into Git\n>> (e.g. for \"git branch -v -v\"), or is it something GitHub-specific?\n> \n> We have a custom command, \"git ahead-behind\", where you can specify\n> arbitrary pairs of commits on stdin. But it's all backed by a function\n> which, yes, could be plugged into \"branch -v -v\". It caches any bitmaps\n> it needs, so if you are doing 100 ahead/behind comparisons against\n> \"master\", for example, it only has to find the bitmap for \"master\" once\n> (remember that we sometimes have to traverse to complete a bitmap when\n> a branch has been updated since the last repack).\n\nThat would be nice to have (perhaps invoked only if number of branches\nis high enough; that excludes using it for ahead-behind information that\n`git checkout` prints).\n\n-- \nJakub Narębski\n\n"},{"id":"290679","messageId":"xmqqlh1lz6gj.fsf@gitster.mtv.corp.google.com","threadId":"42749","inReplyTo":"20160701031711.GA4832@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-01T16:08:44Z","receivedAt":"2016-07-01T16:08:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So I think it would be more productive to put a check like this in \"git\n> commit\" rather than (or perhaps in addition to) fsck. That prevents\n> us creating the broken relationship, but it does still mean the user may\n> have to to go back and tell the original committer that their clock was\n> broken.\n>\n> You could also have the fsck check look not only for out-of-order\n> commits, but also commits in the future (from the perspective of the\n> receiver). That would reject such broken commits before they even hit\n> your repository (though again, it is unclear in such a case if the\n> commit is broken or the clock of the checker).\n\nI agree 100% with the above two paragraphs.\n"},{"id":"290835","messageId":"alpine.DEB.2.20.1607051339040.8378@virtualbox","threadId":"42749","inReplyTo":"20160629223007.GA4726@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2016-07-05T11:43:01Z","receivedAt":"2016-07-05T11:43:22Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Wed, 29 Jun 2016, Jeff King wrote:\n\n> I haven't thought hard specifically about merge bases computation, so\n> perhaps that is a case that isn't helped at all.\n\nI guess it is not helped by generation numbers.\n\nBut then, we often ask: \"is commit A an ancestor of commit B\" e.g. to\ncheck whether we can fast-forward. The way we do it now is to compute the\nmerge base (singular: if there are more than one, we stop at the first one\nwe found) and then look whether commit A is identical to the merge base.\n\nIf we had generation numbers available, then we would have to change those\ncomputations in order to benefit from them when determining ancestry.\n\nBut then, reachability would accelerate that even more than generation\nnumbers.\n\nCiao,\nDscho\n"},{"id":"290838","messageId":"577BAF3C.90601@gmail.com","threadId":"42749","inReplyTo":"alpine.DEB.2.20.1607051339040.8378@virtualbox","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-07-05T12:59:40Z","receivedAt":"2016-07-05T13:00:42Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-07-05 o 13:43, Johannes Schindelin pisze:\n> On Wed, 29 Jun 2016, Jeff King wrote:\n> \n>> I haven't thought hard specifically about merge bases computation, so\n>> perhaps that is a case that isn't helped at all.\n> \n> I guess it is not helped by generation numbers.\n> \n> But then, we often ask: \"is commit A an ancestor of commit B\" e.g. to\n> check whether we can fast-forward. The way we do it now is to compute the\n> merge base (singular: if there are more than one, we stop at the first one\n> we found) and then look whether commit A is identical to the merge base.\n\nI wonder if this query can be answered faster than finding the merge base\n(the common ancestor) with Git core, and if it would be worth it to expose\nthis functionality to shell...\n\n> If we had generation numbers available, then we would have to change those\n> computations in order to benefit from them when determining ancestry.\n\nGeneration numbers (node level / topological rank) can help with such\nquery. First, if level of A is greater than level of B, then A cannot\nbe an ancestor of B. Second, when following from B we can prune path\nif we get to node with level lower than A. This is so called \"level\nfilter\" in literature.\n\nFELINE indices cut search space even more... though I don't know if\nthey would help with finding common ancestors. Perhaps some other\ntechnique would be better (taking into account Git use of EWAH bitmaps\nfor reachability of objects).\n\n> \n> But then, reachability would accelerate that even more than generation\n> numbers.\n\nI wonder if Git uses bitmap indices here, if possible -- they are generated\nsparsely. They can help both in reachability queries (is A in reachability\nof B, or in reachability of one of ancestors of B?) and in finding merge\nbases (intersection of reachabilities of A and B, or their ancestors...\nor something like that, I think, probably more complicated).\n\n-- \nJakub Narębski\n\n"},{"id":"291782","messageId":"578EC0CA.8060501@gmail.com","threadId":"42749","inReplyTo":"20160629220049.GA4416@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2016-07-20T00:07:38Z","receivedAt":"2016-07-20T00:07:50Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2016-06-30 o 00:00, Jeff King pisze:\n> On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:\n\n>> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n>> limited to object counting?\n>\n> At GitHub we are using them for --contains analysis, along with mass\n> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n> plan is to send patches upstream, but they need some cleanup first.\n\nPing. have you got time to clean up those patches?\n\n-- \nJakub Narębski\n\n"},{"id":"291802","messageId":"20160720130231.GB17469@sigill.intra.peff.net","threadId":"42749","inReplyTo":"578EC0CA.8060501@gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-20T13:02:32Z","receivedAt":"2016-07-20T13:02:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 20, 2016 at 02:07:38AM +0200, Jakub Narębski wrote:\n\n> W dniu 2016-06-30 o 00:00, Jeff King pisze:\n> > On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:\n> \n> >> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n> >> limited to object counting?\n> >\n> > At GitHub we are using them for --contains analysis, along with mass\n> > ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n> > plan is to send patches upstream, but they need some cleanup first.\n> \n> Ping. have you got time to clean up those patches?\n\nNo, I haven't. Don't hold your breath; it's something I hope to work on\nin the next 6 months, not the next 6 weeks.\n\n-Peff\n"},{"id":"310854","messageId":"CANQwDwfk2k+qGtx-_RqoLKObAgyV+ebE57UAd-VXDv86HDw2vg@mail.gmail.com","threadId":"42749","inReplyTo":"20160720130231.GB17469@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2017-02-04T13:43:01Z","receivedAt":"2017-02-04T13:43:49Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On 20 July 2016 at 15:02, Jeff King wrote:\n> On Wed, Jul 20, 2016 at 02:07:38AM +0200, Jakub Narębski wrote:\n>> W dniu 2016-06-30 o 00:00, Jeff King pisze:\n>>> On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:\n>>\n>>>> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n>>>> limited to object counting?\n>>>\n>>> At GitHub we are using them for --contains analysis, along with mass\n>>> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n>>> plan is to send patches upstream, but they need some cleanup first.\n>>\n>> Ping. have you got time to clean up those patches?\n>\n> No, I haven't. Don't hold your breath; it's something I hope to work on\n> in the next 6 months, not the next 6 weeks.\n\nPing, Was there any progress on this front? It is now almost 6 months\nlater...\n\nCould those patches be made available in a \"dirty\" form?\n\nTIA,\n-- \nJakub Narębski\n\n\n-- \nJakub Narebski\n"},{"id":"311852","messageId":"20170217092616.ulassn3472stbfga@sigill.intra.peff.net","threadId":"42749","inReplyTo":"CANQwDwfk2k+qGtx-_RqoLKObAgyV+ebE57UAd-VXDv86HDw2vg@mail.gmail.com","subject":"Re: topological index field for commit objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-02-17T09:26:17Z","receivedAt":"2017-02-17T09:26:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 04, 2017 at 02:43:01PM +0100, Jakub Narębski wrote:\n\n> >>>> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n> >>>> limited to object counting?\n> >>>\n> >>> At GitHub we are using them for --contains analysis, along with mass\n> >>> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n> >>> plan is to send patches upstream, but they need some cleanup first.\n> >>\n> >> Ping. have you got time to clean up those patches?\n> >\n> > No, I haven't. Don't hold your breath; it's something I hope to work on\n> > in the next 6 months, not the next 6 weeks.\n> \n> Ping, Was there any progress on this front? It is now almost 6 months\n> later...\n> \n> Could those patches be made available in a \"dirty\" form?\n\nI just pushed them up to the \"jk/ahead-behind\" branch of\nhttps://github.com/peff/git.\n\nThey were originally done on top of v1.9.1, but I forward-ported them to\nthe current \"master\" just now. The result compiles, but I haven't really\ntested it extensively. Caveat applier.\n\n-Peff\n"},{"id":"311853","messageId":"CANQwDwe258tbv0cfPs5YQwu_KOt275X-c4-oMQLDqYVTVHqd=g@mail.gmail.com","threadId":"42749","inReplyTo":"20170217092616.ulassn3472stbfga@sigill.intra.peff.net","subject":"Re: topological index field for commit objects","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2017-02-17T09:28:59Z","receivedAt":"2017-02-17T09:29:46Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On 17 February 2017 at 10:26, Jeff King wrote:\n> On Sat, Feb 04, 2017 at 02:43:01PM +0100, Jakub Narębski wrote:\n>\n>> >>>> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still\n>> >>>> limited to object counting?\n>> >>>\n>> >>> At GitHub we are using them for --contains analysis, along with mass\n>> >>> ahead/behind (e.g., as in https://github.com/gitster/git/branches). My\n>> >>> plan is to send patches upstream, but they need some cleanup first.\n>> >>\n>> >> Ping. have you got time to clean up those patches?\n>> >\n>> > No, I haven't. Don't hold your breath; it's something I hope to work on\n>> > in the next 6 months, not the next 6 weeks.\n>>\n>> Ping, Was there any progress on this front? It is now almost 6 months\n>> later...\n>>\n>> Could those patches be made available in a \"dirty\" form?\n>\n> I just pushed them up to the \"jk/ahead-behind\" branch of\n> https://github.com/peff/git.\n>\n> They were originally done on top of v1.9.1, but I forward-ported them to\n> the current \"master\" just now. The result compiles, but I haven't really\n> tested it extensively. Caveat applier.\n\nThanks a lot! I'll check this out.\n\n-- \nJakub Narebski\n"}]}