{"thread":{"id":"3769","subject":"Multi-headed branches (hydra? :)) for basic patch calculus","startedAt":"2006-04-02T04:07:32Z","lastAt":"2006-04-03T04:10:33Z","messageCount":9,"participants":["Sam Vilain","Jakub Narebski","J. Bruce Fields","Martin Langhoff"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18209","messageId":"1143950852.21233.23.camel@localhost.localdomain","threadId":"3769","inReplyTo":null,"subject":"Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2006-04-02T04:07:32Z","receivedAt":"2006-04-02T04:07:32Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":">From a discussion on #git, the idea was raised of \"multi-headed\nbranches\"\n\nSay you've got a sequence of changes like this:\n\n1. add foo.c\n2. add bar.c\n3. modify foo.c\n4. modify bar.c\n\nThe darcs-like operation of this would be to have two sequences of\nordered patches that combine to a final result.  ie:\n\n  1 -> 3\n  2 -> 4\n\nUnless you jump through hoops, git will represent it as:\n\n  1 -> 2 -> 3 -> 4.\n\nHowever, you *could* represent it as:\n\n  1 -> 3  \\\n           >- head\n  2 -> 4  /\n\nWhere \"head\" is a merge commit that just combines the trees of 3 and 4.\n\nIf somebody adds a commit (5) that changes \"foo.c\" again, the darcs\nhistory would change to:\n\n  1 -> 3 -> 5\n  2 -> 4\n\nTo represent this in git you could just roll back the head merge commit,\npush commit 5 on that branch, then make a new head:\n\n  1 -> 3 -> 5 \\\n               >- head\n  2 -> 4 -----/\n\nHowever, if there was support for \"hydra\", or heads that are multiple\ncommit IDs (and necessarily, no blobs in corresponding paths in their\ntrees that are not identical), then you would not need to destroy and\nrecreate this dummy merge head commit to model your patch history in\nthis manner.\n\nIf the plumbing or a porcelain could be smart enough to automatically\ncreate hydra when patches are not dependent, then many of the benefits\nof patch calculus might come for free, without having to create these\ncomplicated sounding entities manually.\n\nOf course this doesn't give you the symbolic labelling of patches that\ncan allow darcs to detect already applied, but \"mutated\" patches, but\nthat might not matter in practice.\n\nSam.\n"},{"id":"18211","messageId":"e0ns59$uq2$1@sea.gmane.org","threadId":"3769","inReplyTo":"1143950852.21233.23.camel@localhost.localdomain","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-02T06:49:22Z","receivedAt":"2006-04-02T06:49:22Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Sam Vilain wrote:\n\n> From a discussion on #git, the idea was raised of \"multi-headed\n> branches\"\n[...] \n> If somebody adds a commit (5) that changes \"foo.c\" again, the darcs\n> history would change to:\n> \n>   1 -> 3 -> 5\n>   2 -> 4\n> \n> To represent this in git you could just roll back the head merge commit,\n> push commit 5 on that branch, then make a new head:\n>\n>   1 -> 3 -> 5 \\\n>                >- head\n>   2 -> 4 -----/\n> \n> However, if there was support for \"hydra\", or heads that are multiple\n> commit IDs (and necessarily, no blobs in corresponding paths in their\n> trees that are not identical), then you would not need to destroy and\n> recreate this dummy merge head commit to model your patch history in\n> this manner.\n[...]\n\nI'm not sure if \"hydras\", i.e. multi-commit 'heads' are what would make\nGIT able to use some of Darcs patches calculus ideas. If I understand\ncorrectly in GIT 'head' (and 'tag') not only identifies commit (commits\nin hydra[1]) but also tree (in hydra it is result of trivial (?) merge).\nWouldn't it be better to somehow represent rather partial ordering between\ncommits in history, to have something from Darcs in GIT? Although I'm not\nsure about efficiency, and if we should do detect commits dependency -- or\nin other words partial ordering of commits/patches -- at commit or at\nmerge. And if we should remember (or cache) partial ordering/dependency\ninfo...\n\n[1] I've detected some confusion in this terminology. \"Hydra\" is\nmulti-headed moster, yet in your ptoposal it is one head that has multiple\nbodies... and \"octopus\" is taken. I guess the terminology should be\nswitched (octopus <-> hydra).\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"18220","messageId":"20060402161121.GB18864@fieldses.org","threadId":"3769","inReplyTo":"1143950852.21233.23.camel@localhost.localdomain","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"J. Bruce Fields","fromEmail":"bfields@fieldses.org","sentAt":"2006-04-02T16:11:21Z","receivedAt":"2006-04-02T16:11:21Z","isPatch":false,"sender":{"key":"bfields@citi.umich.edu","avatar":null},"body":"On Sun, Apr 02, 2006 at 04:07:32PM +1200, Sam Vilain wrote:\n> To represent this in git you could just roll back the head merge commit,\n> push commit 5 on that branch, then make a new head:\n> \n>   1 -> 3 -> 5 \\\n>                >- head\n>   2 -> 4 -----/\n> \n> However, if there was support for \"hydra\", or heads that are multiple\n> commit IDs (and necessarily, no blobs in corresponding paths in their\n> trees that are not identical), then you would not need to destroy and\n> recreate this dummy merge head commit to model your patch history in\n> this manner.\n\nWhat's the advantage to doing this?\n\n> If the plumbing or a porcelain could be smart enough to automatically\n> create hydra when patches are not dependent, then many of the benefits\n> of patch calculus might come for free, without having to create these\n> complicated sounding entities manually.\n\nWhat are the benefits of patch calculus?  (What is it?  The only\nexplanation I've seen is at\nhttp://abridgegame.org/darcs/manual/node8.html, but I don't find it very\nhelpful.)\n\n--b.\n"},{"id":"18222","messageId":"e0ou7b$moa$1@sea.gmane.org","threadId":"3769","inReplyTo":"20060402161121.GB18864@fieldses.org","subject":"Re: Patch calculus","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-02T16:30:46Z","receivedAt":"2006-04-02T16:30:46Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"J. Bruce Fields wrote:\n\n> What are the benefits of patch calculus?  (What is it?  The only\n> explanation I've seen is at\n>   http://abridgegame.org/darcs/manual/node8.html, \n> but I don't find it very helpful.)\n\nSee also http://www.darcs.net/DarcsWiki/PatchTheory\nparticularly http://www.darcs.net/DarcsWiki/WhyYouWantPatchTheory\n\nP.S. I'm not a Darcs advocate.\n-- \nJakub Narebski\nWarsaw, Poland\n"},{"id":"18223","messageId":"e0p04c$svk$1@sea.gmane.org","threadId":"3769","inReplyTo":"e0ou7b$moa$1@sea.gmane.org","subject":"Re: Patch calculus","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-02T17:03:19Z","receivedAt":"2006-04-02T17:03:19Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"J. Bruce Fields wrote:\n \n> What are the benefits of patch calculus?  (What is it?  The only\n> explanation I've seen is at\n>   http://abridgegame.org/darcs/manual/node8.html,\n> but I don't find it very helpful.)\n\nSee also http://www.darcs.net/DarcsWiki/PatchTheory\nparticularly http://www.darcs.net/DarcsWiki/WhyYouWantPatchTheory\n\nand http://en.wikibooks.org/wiki/Understanding_darcs\n\n-- \nJakub Narebski\nWarsaw, Poland\n"},{"id":"18247","messageId":"44305B1F.7030509@vilain.net","threadId":"3769","inReplyTo":"e0ns59$uq2$1@sea.gmane.org","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2006-04-02T23:15:43Z","receivedAt":"2006-04-02T23:15:43Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Jakub Narebski wrote:\n\n>>However, if there was support for \"hydra\", or heads that are multiple\n>>commit IDs (and necessarily, no blobs in corresponding paths in their\n>>trees that are not identical), then you would not need to destroy and\n>>recreate this dummy merge head commit to model your patch history in\n>>this manner.\n>>    \n>>\n>[...]\n>\n>I'm not sure if \"hydras\", i.e. multi-commit 'heads' are what would make\n>GIT able to use some of Darcs patches calculus ideas. If I understand\n>correctly in GIT 'head' (and 'tag') not only identifies commit (commits\n>in hydra[1]) but also tree (in hydra it is result of trivial (?) merge).\n>  \n>\n\nWhether it is stored as a procession of trees or as a sequence of\npatches does not actually make a difference to a mathematician.\n\nThis might not sound right at first, but think that it does not matter\nwhether you have the number \"4\" which came after \"3\" that you store it\nas \"4 (3 was prior)\" or \"1+1+1+1\".  ℕ (the set of natural numbers) is\nitself defined by induction, yet this is not important for functions\nthat deal with natural number elements.\n\n>Wouldn't it be better to somehow represent rather partial ordering between\n>commits in history, to have something from Darcs in GIT?  Although I'm not\n>sure about efficiency, and if we should do detect commits dependency -- or\n>in other words partial ordering of commits/patches -- at commit or at\n>merge.\n>\n\nThat is more or less what I proposed, except that the ordering is built\nat commit time to pick a best head rather than when you try to pull the\npatch, which seems a trivial difference at best.\n\nI think git-commit --hydra is called for.\n\nFirst we define a \"hydra leash\", I can think of two definitions:\n\n - a hydra leash is a specially marked commit\n - a hydra leash is a commit that has multiple parents, and is\n   the result of just an index merge of its parents\n\nWe must also define the concept of a commit being \"against\" the head(s)\nof a hydra.\n\nWith that term in mind, we can make \"--hydra\" do as follows:\n\n a) find the head(s) of the hydra that the commit is against;\n b) apply the commit, and set its parents to those head(s)\n c) put the hydra leash back on.\n\nIdeally the leash should not have the previous leash as one of its\nparents; that leash was always transient and keeping its history is\nperhaps not required, and would break the latter leash detection method\ndescribed above.\n\nInstead, git-pull et al should know what to do.\n\n> And if we should remember (or cache) partial ordering/dependency\n>info...\n>\n>[1] I've detected some confusion in this terminology. \"Hydra\" is\n>multi-headed moster, yet in your ptoposal it is one head that has multiple\n>bodies... and \"octopus\" is taken. I guess the terminology should be\n>switched (octopus <-> hydra).\n>  \n>\n\nA head is a head because there is only one of it, and it's at the top. \nIf the leash is transient then it doesn't really exist, and therefore\ncan't be called a head.  So, you look instead at the heads remaining,\nand where you expected to see an entity with a single head you see many\nheads.\n\nSam.\n"},{"id":"18252","messageId":"46a038f90604021815g453c57c9pf95a0f70a62f2fbc@mail.gmail.com","threadId":"3769","inReplyTo":"1143950852.21233.23.camel@localhost.localdomain","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2006-04-03T01:15:11Z","receivedAt":"2006-04-03T01:15:11Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 4/2/06, Sam Vilain <sam@vilain.net> wrote:\n> If the plumbing or a porcelain could be smart enough to automatically\n> create hydra when patches are not dependent, then many of the benefits\n> of patch calculus might come for free, without having to create these\n> complicated sounding entities manually.\n\nI'm not too excited about the benefits of patch calculus -- it seems\nto break  many general usage scenarios(*) and I haven't seen many\nexamples of those benefits that aren't a bit contrived.\n\n* - For instance: the common practice of having a patch series where\nyou create a new function and later add calls to it breaks quite\nseriously under patch calculus.\n\nAre there common usage scenarios where patch calculus helps more than\nit hurts? Preferrably without involving manual recording of\ndependencies or full language parsers that guess them.\n\ncheers,\n\n\nm\n"},{"id":"18253","messageId":"443083E6.9090204@vilain.net","threadId":"3769","inReplyTo":"46a038f90604021815g453c57c9pf95a0f70a62f2fbc@mail.gmail.com","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2006-04-03T02:09:42Z","receivedAt":"2006-04-03T02:09:42Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Martin Langhoff wrote:\n\n>On 4/2/06, Sam Vilain <sam@vilain.net> wrote:\n>  \n>\n>>If the plumbing or a porcelain could be smart enough to automatically\n>>create hydra when patches are not dependent, then many of the benefits\n>>of patch calculus might come for free, without having to create these\n>>complicated sounding entities manually.\n>>    \n>>\n>\n>I'm not too excited about the benefits of patch calculus -- it seems\n>to break  many general usage scenarios(*) and I haven't seen many\n>examples of those benefits that aren't a bit contrived.\n>\n>* - For instance: the common practice of having a patch series where\n>you create a new function and later add calls to it breaks quite\n>seriously under patch calculus.\n>  \n>\n\nPerhaps.  But forget the darcs implementation for a moment.\n\nWhen you make a commit, you're labelling it with the previous dependent\ncommit for this commit to apply.\n\nSo, git-commit-hydra would do this calculation based on the files\nchanged.  git-commit would assume the prior commit.  You still have both\noptions available.\n\n>Are there common usage scenarios where patch calculus helps more than\n>it hurts? Preferrably without involving manual recording of\n>dependencies or full language parsers that guess them.\n>  \n>\n\nI am in the process of converting a live repository as if it had been\ncommitted to in this manner.  I'll post results shortly.\n\nSam.\n"},{"id":"18257","messageId":"e0q77o$9v5$1@sea.gmane.org","threadId":"3769","inReplyTo":"44305B1F.7030509@vilain.net","subject":"Re: Multi-headed branches (hydra? :)) for basic patch calculus","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-03T04:10:33Z","receivedAt":"2006-04-03T04:10:33Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Sam Vilain wrote:\n\n> Jakub Narebski wrote:\n\n>>Wouldn't it be better to somehow represent rather partial ordering between\n>>commits in history, to have something from Darcs in GIT?  Although I'm not\n>>sure about efficiency, and if we should do detect commits dependency -- or\n>>in other words partial ordering of commits/patches -- at commit or at\n>>merge.\n>>\n> \n> That is more or less what I proposed, except that the ordering is built\n> at commit time to pick a best head rather than when you try to pull the\n> patch, which seems a trivial difference at best.\n> \n> I think git-commit --hydra is called for.\n> \n> First we define a \"hydra leash\", I can think of two definitions:\n> \n>  - a hydra leash is a specially marked commit\n>  - a hydra leash is a commit that has multiple parents, and is\n>    the result of just an index merge of its parents\n> \n> We must also define the concept of a commit being \"against\" the head(s)\n> of a hydra.\n> \n> With that term in mind, we can make \"git commit --hydra\" do as follows:\n> \n>  a) find the head(s) of the hydra that the commit is against;\n>  b) apply the commit, and set its parents to those head(s)\n>  c) put the hydra leash back on.\n\nLet's reiterate to check if I understand that:\n\nYou've got a sequence of changes like this:\n\n1. add foo.c\n2. add bar.c\n3. modify foo.c\n4. modify bar.c\n5. modify foo.c again\n\nYou want patch/commit dependency, which is partial ordering of\npatches/commits/trees:\n\n  1 -> 3 -> 5\n  2 -> 4\n\nbe represented as\n\n  1 -> 3 -> 5 \\\n               >- head\n  2 -> 4 -----/\n\n\nFirst, to clean up my error, head is not a commit. Head is floating pointer\nto the top commit (something like \"last\" pointer in the list, except we\ndon't have list but directed acyclic graph). Getting head means getting the\ntree corresponding to that commit.\n\nYour hydra is a set of pointers to top commit. Getting hydra means getting\nthe tree which is trivial merge of top commits (no conflicts!). Ordinary\nhead is just hydra with one top commit.\n\nDo I understand that hydra is constructed *at commit*?\n\n\nSecond, to repeat my patches vs. trees arguments. In GIT now if one gets\n(4), one would get tree with files foo.c and bar.c added, both modified.\nWith hydra, and with the arrows meaning that one commit is parent of the\nother (unless you modify commit structure too), one would get tree with\nonly file bar.c added, and modified.\n\nBTW, the arrows should be in other direction to show how commits refers to\ntoher commits.\n\n\nThird, let us consider different possible \"git-commit --hydra\" in above\nhydra [head] sitiation:\n\na.) 6. modify bar.c dependent on 4\n\n  1 -> 3 -> 5 \\\n               >- head/hydra\n  2 -> 4 -> 6 /\n\nb.) 6. modify foo.c independently of 5, depends on changes in 3: \nit is getting complicated.\n\n  1 -> 3 -> 5 --\\\n        \\        \\\n         -> 6 ---->- head\n                 /\n  2 -> 4 -------/\n\nc.) 6. moves some content from foo.c to bar.c, thus depending (at least) on\nboth 3 (let's assume that independently 5) and on 4. How to represent that\nwithout modyfying commit structure (and not only head structure)? If we use\nmultiple commits as parents for 6, how do we distinguish between 6 being\nmerge commit of commits 3 and 4, and 6 depending on commits 3 and 4?\n\n  1 -> 3 -> 5 --\\\n        \\        \\\n     (?) -> 6 ---->- head\n        /        /\n  2 -> 4 -------/\n\n\nFourth, the fact that commits do not generate conflicts doesn't mean that\nthey are independent. Let's assume that we are introducing new function for\nexample. If we change first header file foo.h, *commit* that change (not\nthe best practice/workflow, I know) resulting in commit (1), then change\nfile foo.c resulting in commit (2), then commits (1) and (2) are\nindependent in the sense of commits, and so would say the tool which\ndetects dependencies (partial ordering). But actually commits (1) and (2)\ndepends on each other, and commiting both one after another to the same\nbranch says so now.\n\n\nFor more comments I would need to read theory of patches in more detail\nfirst.\n\nI hope that all the above makes sense...\n-- \nJakub Narebski\nWarsaw, Poland\n"}]}