{"thread":{"id":"3317","subject":"Fake linear history in a deterministic manner.","startedAt":"2006-02-13T01:46:38Z","lastAt":"2006-02-16T23:54:30Z","messageCount":7,"participants":["Martin Langhoff","Junio C Hamano","Linus Torvalds","Eric Wong"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"16010","messageId":"46a038f90602121746v5adb448ej73cc2be6dd3745ce@mail.gmail.com","threadId":"3317","inReplyTo":null,"subject":"Fake linear history in a deterministic manner.","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-02-13T01:46:38Z","receivedAt":"2006-02-13T01:46:38Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"To emulate `cvs log somepath` I need to munge history to look linear.\nI am working on the theory that I will tell the cvs client about *one*\nlinear history, and show merges from parallel histories as a merge\ncommit, \"flattened\" so to speak, and with a commit message where I'll\nlist the hash and first line of each commit that it involves.\n\nNow, we are keeping a sqlite db (bad dependency, I know) with a list\nof the lies we tell to the clients, so we can at least be consistent\n(and fast). The fact that true git clients will be able to commit to\nthe repo means that actual parallel development will happen in the\nrepo.\n\nNow, I can't think of an approach to drawing the linearized history\nthat is deterministic. I can't chose any branch with any confidence,\nbecause the repo always has a very limited view. A client could come\nin any time and push onto the repo a series of commits based on an\nancient commit, with ancient dates, and a merge to todays head.\n\nWe've been talking about updating the sqlite db with a post update\nhook, which means that in that context we never have to choose, the\ncommits that get to the repo first win because they now drive the\nlinearized history.\n\nBut when creating a new lies database, we have no\n\"pushed-to-this-repo\" timestamp in the commits so we'll have to pick.\nAt the moment, I suspect I'll pick the one with the earliest\n\"following\" commit.\n\nI thought briefly about delaying the decision until I see the merge,\nand pick the leftmost, or rightmost, if there is some bias in\ngit-merge or cg-merge on putting whatever origin has on a particular\nside. It'd mean running backwards through history and that the very\nlast merge can flip the decision entirely. Hmmm... any strategy I can\ncome up with means that each new merge throws the dice again entirely.\n\nIdeas?\n\n(As a result of this, the git-cvsserver we're drafting is of limited\nusefulness to projects that really do use git to do what it does best:\nDSCM. Projects with a mostly linearized history -- using git-rebase\nliberally to avoid uninteresting merges -- do get a reasonable cvs\nhistory. Or will get. Sometime. Soon.)\n\n\n\nmartin\n"},{"id":"16021","messageId":"7vk6bz3k7e.fsf@assigned-by-dhcp.cox.net","threadId":"3317","inReplyTo":"46a038f90602121746v5adb448ej73cc2be6dd3745ce@mail.gmail.com","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-13T05:24:05Z","receivedAt":"2006-02-13T05:24:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Langhoff <martin.langhoff@gmail.com> writes:\n\n> I thought briefly about delaying the decision until I see the merge,\n> and pick the leftmost, or rightmost, if there is some bias in\n> git-merge or cg-merge on putting whatever origin has on a particular\n> side. It'd mean running backwards through history and that the very\n> last merge can flip the decision entirely. Hmmm... any strategy I can\n> come up with means that each new merge throws the dice again entirely.\n>\n> Ideas?\n\nWhen somebody pushes a ref to your existing commit ancestry\ngraph, you can easily identify which commits are the new ones\nyou see for the first time.\n\n                A\n           o---o\n          /\n     o---o---o---o---o B\n\nSuppose you started from two branch repo A and B.  Your sqlite\ndatabase knows about all of these commits, and say you earlier\nhave decided to treat A as a side branch, B as trunk.\n\nThen somebody pushed a new B, making the ancestry graph like\nthis:\n\n                A\n           o---o-------*---*---* B-new\n          /           /     \n     o---o---o---o---o B-old\n\nWhen the update-hook runs, as you read in receive-pack.c, \nyour refs have not been updated yet, so you can identify the\ncommits marked with * with:\n\n\tgit rev-list B-new $(git rev-parse --not --all)\n\nI think you have to do this enumeration of new commits anyway,\nif you are keeping tabs on all commits in your database.  And\nyou check the chain * commits form, and work backwards.  The\ntopologically oldest ones determine what branch others belong\nto.\n\nWith CVS you cannot express a merge very well, so you now face a\nchoice.  Which parent to drop from the leftmost * commit in the\nabove picture?\n\nIt has commits known to your sqlite database as its parents, and\none of them, B (old), is on trunk; the other one is a side\nbranch, so in this case the decision is clear.  You leave the\nlink from B-old and cut link from A.  But this heuristics would\nnot work very well if both are branches.  Which one to prefer?\n\nOne approach would be to see the world with eyes of the person\nwho did such a merge.  Both git and cogito place the current\nbranch as the first parent, so you can tell which one the person\nwho did the merge had before that merge that way.  Also in\npractice, in a normal branch, you would build sequence of small\ncommits and occasionally merge from elsewhere, so the side with\nmore difference tends to be a side branch from the point of view\nof the person who performs the merge.\n\nHowever, this would not help much.  There is no inherent\ndistinction between trunk and branch in the distributed\ndevelopment.  Although I treat my \"next\" branch as a side branch\nand \"master\" branch as the trunk, \"next\" sometimes needs to\nmerge from \"master\", and by looking at only that merge, you\ncannot tell which one is the trunk.  My merging \"master\" into\n\"next\" does not make my \"next\" the trunk.\n\nSince the ordering is completely arbitrary, I think you can give\npreference to the ones you have found out about earlier.  That\nis, suppose you already had this, and for some reason track B is\nthe trunk and track A is a branch (say commits on B have 1.XX,\nthe ones on A have 1.XX.1.YY where XX depends on which commits\non B the branch was forked from).  At this point, if you see a\npush to C:\n\n                A\n           o---o\n          /\n     o---o---o---o---o B\n              \\\n               *---* C\n\nyou give 1.XX.2.YY to commits on C.\n\nThis may or may not match reality, and C may collect a lot of\ncommits while B might stay dormant -- and you may regret that\nyou picked B as the trunk.  But the thing is, there is no\ninherent trunk or branch in the distributed world, so the cvs\nclients of your server needs to live with it.  To you, you saw B\nfirst and people who track the project through your server also\nsaw B first.  Then you can have total ordering to side\nbranches.  When you see a merge, you arbitrarily but\nconsistently pick which side to pick.  The one that has smaller\nnumber at the third place (which I am using as \"the branch\nnumber\").\n\nJust thinking out aloud again...\n"},{"id":"16023","messageId":"46a038f90602122158n51fc94a8h2ff2631c16cd28b5@mail.gmail.com","threadId":"3317","inReplyTo":"7vk6bz3k7e.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-02-13T05:58:40Z","receivedAt":"2006-02-13T05:58:40Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 2/13/06, Junio C Hamano <junkio@cox.net> wrote:\n\nYep, I had roughly this exact scenario in my mind, thanks for the\ngraphs -- help make sense of what's happening.\n\n> When somebody pushes a ref to your existing commit ancestry\n> graph, you can easily identify which commits are the new ones\n> you see for the first time.\n>\n>                 A\n>            o---o\n>           /\n>      o---o---o---o---o B\n>\n> Suppose you started from two branch repo A and B.  Your sqlite\n> database knows about all of these commits, and say you earlier\n> have decided to treat A as a side branch, B as trunk.\n\nWell, from the point of view of B being a head we know about, either A\nis another head, and we don't care about it, or A is someone's repo\nand we haven't seen it and thus cannot care about it either.\n\nA bit of background... git-cvsserver at the moment has the following\nsemantics: what cvs considers a top-level \"module\" we use to identify\nthe head. So\n\n    cvs -d :ext:me@server:/var/frob.git checkout  master\n\nwill get you frob.git#master. I thought long and hard about this, and\nit is horribly hard to mimic CVS's idea of branches. So clients see a\nstrictly linear history. Any user in this scenario wanting to do\nbranching and merging is kindly invited to use real tools. There';s\nonly so much magic Perl can do ;-)\n\n> Then somebody pushed a new B, making the ancestry graph like\n> this:\n>\n>                 A\n>            o---o-------*---*---* B-new\n>           /           /\n>      o---o---o---o---o B-old\n>\n> When the update-hook runs, as you read in receive-pack.c,\n> your refs have not been updated yet, so you can identify the\n> commits marked with * with:\n>\n>         git rev-list B-new $(git rev-parse --not --all)\n\nThat's a nifty trick, though I'm not sure I'll be able to use it.\n\nRight now I'm doing something stupid-er just using `git-log\n--parents`, skipping commits that don't move the ball forward on the\nlinear head I know about, and then processing those \"other tracks\"\nwhen I see a merge commit. I'll probably find the merge base and see\nwhat commits were brought in from the other side.\n\nThe problem is that the situation running from post update hook is\nvery different from the scenario of running the very same script on a\nrepo where you see all the history.\n\nIn any case, I'm undecided whether to use --topo-order or\n--merge-order. Does it really matter?\n\n(...)\n> With CVS you cannot express a merge very well, so you now face a\n> choice.  Which parent to drop from the leftmost * commit in the\n> above picture?\n\nWell, we've already lied about having B to clients that won't know\nwhat to do if we tell them about parallel histories, so our pick is B.\n\n(...)\n> One approach would be to see the world with eyes of the person\n> who did such a merge.  Both git and cogito place the current\n> branch as the first parent,\n\nYes, I thought about that, but that order is ambiguous in the two most\ninteresting cases:\n\n - project maintainer pulls from mature feature branches from other\ndevelopers - her side is first, show the \"pulled\" stuff as merges\n(flattened with a merge summary in the commit msg). Still, you can\nargue the feature development is more interesting.\n\n - team-shared-git-repo user does cg-update and merges updates from\norigin - her side is first, we don't know which side is the\ninteresting one. At all. Hmmm.\n\n> But the thing is, there is no\n> inherent trunk or branch in the distributed world, so the cvs\n> clients of your server needs to live with it.\n\nThat's the mantra so far, and we'll talk to cvs clients about\nperfectly linearized history. Anything else won't be useful as far as\nI can tell -- or in any case,until this is going well for basic usage.\nIf someone's crazy enough to try I won't get in the way.\n\ncheers.\n\n\nmartin\n"},{"id":"16049","messageId":"Pine.LNX.4.64.0602130819490.3691@g5.osdl.org","threadId":"3317","inReplyTo":"46a038f90602122158n51fc94a8h2ff2631c16cd28b5@mail.gmail.com","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-13T16:34:19Z","receivedAt":"2006-02-13T16:34:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 13 Feb 2006, Martin Langhoff wrote:\n> \n> In any case, I'm undecided whether to use --topo-order or\n> --merge-order. Does it really matter?\n\nUse topo-order.\n\nmerge-order is much more expensive to calculate, and doesn't even exist if \nNO_OPENSSL is set.\n\nAnyway, while linearization in general is impossible, I'd suggest a few \nheuristics:\n\n - you obviously must remember the head of the previous linearization. Any \n   tree choices you made in the past are not something you can change any \n   more for cvs export.\n\n   This may sound obvious, but the fact is, especially if you do the cvs \n   export frequently, and the main maintainer updates the tree in a timely \n   manner, it will limit your choices a LOT. In fact, most of the time \n   you'll have no choice at all: you will have an unambiguous \"TRUNK\" that \n   is defined by the fact that there is only one linear path from the \n   previous export-head to the current HEAD.\n\nIn short, most of the time you won't have any issues in a stable system. \nYou'll see a true \"fork in the road\" choice only when the maintainer \nhasn't pushed his tree to the thing you export in a while, long enough \nthat no CVS exporting has taken place over a whole parallel cycle. It's \nprobably rare.\n\nSo the main issue of \"which child to choose\" becomes one of the initial \nexport, and then just occasionally thereafter. And in that case, there's \nreally just one obvious algorithm:\n\n - simply enumerate the possible paths (not that hard - it's just \n   enumerating a tree once you've generated the graph in memory with child \n   and parent pointers), and just selecting the one with the \"longest \n   weighted path\".\n\nI say \"weighted path\", because you might want to consider different \ncommits to have different weights. For example, you might want to consider \nmerge commits to be less interesting (so weight them as 0.5 commits) in \norder to get as many \"real\" commits as possible. And you might consider \ncommits made by a certain person to be \"more TRUNKish\", and give them a \nweight of 2, so that you'll be more likely to follow the \"maintainer view\" \nover any other linearized history.\n\nNo other algorithm seems very sane. \n\n\t\tLinus\n"},{"id":"16289","messageId":"20060216222956.GA5818@Muzzle","threadId":"3317","inReplyTo":"46a038f90602121746v5adb448ej73cc2be6dd3745ce@mail.gmail.com","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Eric Wong","fromEmail":"normalperson@yhbt.net","sentAt":"2006-02-16T22:29:57Z","receivedAt":"2006-02-16T22:29:57Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Martin Langhoff <martin.langhoff@gmail.com> wrote:\n> To emulate `cvs log somepath` I need to munge history to look linear.\n> I am working on the theory that I will tell the cvs client about *one*\n> linear history, and show merges from parallel histories as a merge\n> commit, \"flattened\" so to speak, and with a commit message where I'll\n> list the hash and first line of each commit that it involves.\n\nI'd be interested in exporting from git to SVN with something like this.\n\n> I thought briefly about delaying the decision until I see the merge,\n> and pick the leftmost, or rightmost, if there is some bias in\n> git-merge or cg-merge on putting whatever origin has on a particular\n> side. It'd mean running backwards through history and that the very\n> last merge can flip the decision entirely. Hmmm... any strategy I can\n> come up with means that each new merge throws the dice again entirely.\n> \n> Ideas?\n\nI'd actually like to do this interactively in gitk.  Just browse history\nvisually and pick the path you want to choose each time there's a merge,\nand then having it output the revisions to stdout or saved to a file\nafter you're done picking.  Ideally you'd be able to use saved output\ninteractively, as well.\n\n-- \nEric Wong\n"},{"id":"16290","messageId":"46a038f90602161529r6e1855a5l41a2dbfdea7ee2a0@mail.gmail.com","threadId":"3317","inReplyTo":"20060216222956.GA5818@Muzzle","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-02-16T23:29:13Z","receivedAt":"2006-02-16T23:29:13Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 2/17/06, Eric Wong <normalperson@yhbt.net> wrote:\n> Martin Langhoff <martin.langhoff@gmail.com> wrote:\n> > To emulate `cvs log somepath` I need to munge history to look linear.\n> > I am working on the theory that I will tell the cvs client about *one*\n> > linear history, and show merges from parallel histories as a merge\n> > commit, \"flattened\" so to speak, and with a commit message where I'll\n> > list the hash and first line of each commit that it involves.\n>\n> I'd be interested in exporting from git to SVN with something like this.\n\nWe're hoping to release the code soon, but the truth is that it's\nreally trivial. It was more agonizing over the fact that there's no\n\"good\" (aka \"stable\") algorithm for this.\n\n> > I thought briefly about delaying the decision until I see the merge,\n> > and pick the leftmost, or rightmost, if there is some bias in\n> > git-merge or cg-merge on putting whatever origin has on a particular\n> > side. It'd mean running backwards through history and that the very\n> > last merge can flip the decision entirely. Hmmm... any strategy I can\n> > come up with means that each new merge throws the dice again entirely.\n> >\n> > Ideas?\n>\n> I'd actually like to do this interactively in gitk.  Just browse history\n> visually and pick the path you want to choose each time there's a merge,\n> and then having it output the revisions to stdout or saved to a file\n> after you're done picking.  Ideally you'd be able to use saved output\n> interactively, as well.\n\nIt's cool to be able to pick, but if it's for a git-svnserver\nimplementation, you can't change your (fake) history you tell after\nclients have seen. So a merge that gets pushed to the repo later may\ncontain more interesting paths, but you're bound to the lies you've\ntold.\n\ncheers,\n\n\nmartin\n"},{"id":"16292","messageId":"7v7j7uamh5.fsf@assigned-by-dhcp.cox.net","threadId":"3317","inReplyTo":"46a038f90602121746v5adb448ej73cc2be6dd3745ce@mail.gmail.com","subject":"Re: Fake linear history in a deterministic manner.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T23:54:30Z","receivedAt":"2006-02-16T23:54:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin, (and Martyn),\n\nI just cloned the gitcvs via git locally, exported it via\ngitcvs, and ran \"cvs log\" and \"cvs annotate README\" there.  \n\nGood job.  I really had a good laugh looking at the generated\noutput.  It just looks like .... CVS! ;-)\n\nI haven't read the code in detail (I tend to start nitpicking\nthe details without looking at a bigger picture, once I start\nreading the code, so I try to only give superficial look until I\nknow I'll have tons of time to spend on it).\n\nBut it looks like a fun project.\n"}]}