{"thread":{"id":"3701","subject":"Fix branch ancestry calculation","startedAt":"2006-03-23T01:29:20Z","lastAt":"2006-03-25T07:54:16Z","messageCount":11,"participants":["Linus Torvalds","Keith Packard","David Mansfield","Chris Shoemaker"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"17795","messageId":"Pine.LNX.4.64.0603221723230.9196@g5.osdl.org","threadId":"3701","inReplyTo":null,"subject":"Fix branch ancestry calculation","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-23T01:29:20Z","receivedAt":"2006-03-23T01:29:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nSome branches don't get any ancestors at all, because their ancestor gets \na \"dotcount\" value of 0, and are thus not considered any better than not \nhaving any ancestor. That's obviously wrong. Even a zero-dot-count \nancestor is better than having none at all.\n\nThis fixes the issue by making not having an ancestor branch have a \ngoodness value of -1, avoiding the problem (because even a zero dot-count \nwill be considered better).\n\nAlternatively, the special-case for the \"1.1.1.1\" revision should be \nremoved (or made to imply a dot-count of 1).\n\nFinally, I suspect that dot-counting in general should ignore any final \n\".1\" counts, ie \"1.2.1.1\" should count the same as \"1.2.1\", which should \ncount the same as \"1.2\", which has a dot-count of 1.\n\nThat would automatically make any \"1.1.1.1.1....\" sequence always count as \nhaving a dot-count of 0.\n\nI'll send suggestion that as a separate patch, but in the meantime, this \nis a separate issue, and obviously a bug-fix.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n----\n\ndiff --git a/cvsps.c b/cvsps.c\n--- a/cvsps.c\n+++ b/cvsps.c\n@@ -2599,7 +2599,7 @@ static void determine_branch_ancestor(Pa\n \t * note: rev is the pre-commit revision, not the post-commit\n \t */\n \tif (!head_ps->ancestor_branch)\n-\t    d1 = 0;\n+\t    d1 = -1;\n \telse if (strcmp(ps->branch, rev->branch) == 0)\n \t    continue;\n \telse if (strcmp(head_ps->ancestor_branch, \"HEAD\") == 0)\n"},{"id":"17798","messageId":"Pine.LNX.4.64.0603221746300.26286@g5.osdl.org","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603221723230.9196@g5.osdl.org","subject":"[RFC] Make dot-counting ignore \".1\" at the end","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-23T01:50:23Z","receivedAt":"2006-03-23T01:50:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nI'm not 100% sure this is appropriate, but in general, I think \"<rev>\" and \n\"<rev>.1\" should be considered the same thing, no? Which implies that \n\"1.1\" and \"1.1.1.1\" are all the same thing, and collapse to just \"1\", ie a \nzero dot-count. They are all the same version, after all, no?\n\nThis gets rid of the insane (?) special case of \"1.1.1.1\" that exists \nthere now, since it's now no longer a special case.\n\nI also wonder if trailing \".1\" revisions should be ignored when comparing \ntwo revisions.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nYeah, I don't know RCS file logic. This may be completely broken.\n\ndiff --git a/cvsps.c b/cvsps.c\nindex 2695a0f..2ad1595 100644\n--- a/cvsps.c\n+++ b/cvsps.c\n@@ -2357,9 +2357,16 @@ static int revision_affects_branch(CvsFi\n static int count_dots(const char * p)\n {\n     int dots = 0;\n+    int len = strlen(p);\n \n-    while (*p)\n-\tif (*p++ == '.')\n+    while (len > 2) {\n+\tif (memcmp(p+len-2, \".1\", 2))\n+\t\tbreak;\n+\tlen -= 2;\n+    }\n+\n+    while (len)\n+\tif (p[--len] == '.')\n \t    dots++;\n \n     return dots;\n@@ -2613,7 +2620,7 @@ static void determine_branch_ancestor(Pa\n \t/* HACK: we sometimes pretend to derive from the import branch.  \n \t * just don't do that.  this is the easiest way to prevent... \n \t */\n-\td2 = (strcmp(rev->rev, \"1.1.1.1\") == 0) ? 0 : count_dots(rev->rev);\n+\td2 = count_dots(rev->rev);\n \t\n \tif (d2 > d1)\n \t    head_ps->ancestor_branch = rev->branch;\n"},{"id":"17808","messageId":"1143095182.6850.23.camel@neko.keithp.com","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603221746300.26286@g5.osdl.org","subject":"Re: [RFC] Make dot-counting ignore \".1\" at the end","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-03-23T06:26:22Z","receivedAt":"2006-03-23T06:26:22Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Wed, 2006-03-22 at 17:50 -0800, Linus Torvalds wrote:\n> I'm not 100% sure this is appropriate, but in general, I think \"<rev>\" and \n> \"<rev>.1\" should be considered the same thing, no? Which implies that \n> \"1.1\" and \"1.1.1.1\" are all the same thing, and collapse to just \"1\", ie a \n> zero dot-count. They are all the same version, after all, no?\n\nNo. 1.1.1.1 is the first import on the first vendor branch; 1.1 is the\nhead of the tree.\n\nvendor branches are total CVS magic and need very special treatment. The\ninitial import sets the 'branch' value in the ,v file to point at the\nvendor branch. Subsequent imports leave the branch value alone, a commit\nto the trunk will reset the branch to point at the trunk. This means\nthat use of the default version of the file just after an import gives\nyou the head of the import tree. It's insane, but that's how it works.\n\nWhat I've been doing is to treat imports to a vendor branch which occur\nsequentially as if they were on the trunk. Imports after an intervening\ncommit to the trunk are placed on a separate branch.\n\nThe best part is that you get the vendor branch named 1.1.1 *even if\nyou've made a million commits to the trunk*. Which means that you must\nignore the numeric relationship between the vendor branch and the trunk\nand merge them together in date order.\n\n> This gets rid of the insane (?) special case of \"1.1.1.1\" that exists \n> there now, since it's now no longer a special case.\n\nOh, it's a seriously special case, one which takes seriously special\nhandling, and a careful disregard for normal version number ordering.\n\n> I also wonder if trailing \".1\" revisions should be ignored when comparing \n> two revisions.\n\nAs 'real' CVS version numbers always have four digits, this doesn't much\nmatter.\n\nbtw -- I've got my parsecvs code doing a pretty good job of discovering\nthe structure of an arbitrary set of ,v files. The last remaining bit of\ncode to write is to correctly construct the tree of branches from the\npartial trees in each ,v file. With simple trees, things are looking\ngood, with the xserver CVS tree, I get a couple of mis-hung branches as\nthe branch tree is wrong. Fixed tomorrow, I think, at which point it\nshould be able to produce more accurate commits than cvsps does.\n\n-- \nkeith.packard@intel.com\n"},{"id":"17809","messageId":"Pine.LNX.4.64.0603222232210.26286@g5.osdl.org","threadId":"3701","inReplyTo":"1143095182.6850.23.camel@neko.keithp.com","subject":"Re: [RFC] Make dot-counting ignore \".1\" at the end","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-23T06:34:16Z","receivedAt":"2006-03-23T06:34:16Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 22 Mar 2006, Keith Packard wrote:\n> \n> No. 1.1.1.1 is the first import on the first vendor branch; 1.1 is the\n> head of the tree.\n\nOk. Discard the second patch. The first one is definitely needed for cvsps \nright now, though.\n\nWith that in place (the \"make sure we have a proper ancestor branch\" \nthing), a \"git cvsimport\" of the binutils tree seems to be working, at \nleast to the point that it seems to have imported 1400+ commits without \nundue complaints. But hey, I'm looking forward to something less \nhacked-together.\n\n\t\tLinus\n"},{"id":"17810","messageId":"1143098270.6850.29.camel@neko.keithp.com","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603222232210.26286@g5.osdl.org","subject":"Re: [RFC] Make dot-counting ignore \".1\" at the end","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-03-23T07:17:50Z","receivedAt":"2006-03-23T07:17:50Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Wed, 2006-03-22 at 22:34 -0800, Linus Torvalds wrote:\n\n> With that in place (the \"make sure we have a proper ancestor branch\" \n> thing), a \"git cvsimport\" of the binutils tree seems to be working, at \n> least to the point that it seems to have imported 1400+ commits without \n> undue complaints. But hey, I'm looking forward to something less \n> hacked-together.\n\nYeah, me too. Attempts at importing some of the X.org trees have\nresulted in 'less than ideal' repositories.\n\nI stuck a couple of hacks in cvsps myself to get it to deal with \nX.org trees; the first was to increase a static buffer to 'large enough'\nto hold X.org-style commit messages (which are enormous).\n\nhttp://gitweb.freedesktop.org/?p=freedesktop-cvsps;a=summary\n\nshows both minor patches. I should have let people know about these\nearlier...\n\n-- \nkeith.packard@intel.com\n"},{"id":"17872","messageId":"442404F0.80609@dm.cobite.com","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603221746300.26286@g5.osdl.org","subject":"Re: [RFC] Make dot-counting ignore \".1\" at the end","fromName":"David Mansfield","fromEmail":"centos@dm.cobite.com","sentAt":"2006-03-24T14:40:48Z","receivedAt":"2006-03-24T14:40:48Z","isPatch":false,"sender":{"key":"centos@dm.cobite.com","avatar":null},"body":"Linus Torvalds wrote:\n> I'm not 100% sure this is appropriate, but in general, I think \"<rev>\" and \n> \"<rev>.1\" should be considered the same thing, no? Which implies that \n> \"1.1\" and \"1.1.1.1\" are all the same thing, and collapse to just \"1\", ie a \n> zero dot-count. They are all the same version, after all, no?\n\n\nHmmm.  I'm not sure about this. Given x.y.z.q... the 'odd' nodes \n(starting from x = position 1) represent branches, not revisions, and \ndon't refer to actual concrete objects (just tags if you will) in the \ncvs world.\n\nSo if <rev> is something like x.y then x.y.z would refer to the 'z' branch.\n\nFurthermore, 'z' better be an even value 2 4 6 etc. because those are \nthe only branch id's cvs will create.  The odd values are for 'imported \nsource' branches.\n\nThe reason 1.1.1.1 exists is some lame-ass crap that CVS delivers to any \ndeveloper who imports his/her initial source code.\n\nIt creates 1.1 as a placeholder, and I think in this special case it has \nthe same contents.  It also creates a .1 'import branch' then puts the\nimported revision onto that 'import' branch.\n\nIn a normal situation, you have rev = x.y\n\nYou branch, it 'registers' a branch x.y.z where z in {2,4,6...} (and \nuses a special 'magic branch' syntax x.y.0.z in the symbolic tags \nsection).\n\nOnly when you commit your first change does it create x.y.z.1.\n\nSo we have:\n\nx.y != x.y.z.1 for sure, in the general case.\n\nAlso x.y.z will never be x.y.1 for a user created branch because z must \nbe even number (except for import branches), in any case x.y.z is never \nan actual file revision.  Now, it COULD be the fact there there needs to \nbe special handling for x.y.z where z == 1 because that is an import \nbranch and something devilish is happening there.\n\nI honestly don't know...\n\nDavid\n"},{"id":"17873","messageId":"44240619.20103@dm.cobite.com","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603221723230.9196@g5.osdl.org","subject":"Re: Fix branch ancestry calculation","fromName":"David Mansfield","fromEmail":"centos@dm.cobite.com","sentAt":"2006-03-24T14:45:45Z","receivedAt":"2006-03-24T14:45:45Z","isPatch":false,"sender":{"key":"centos@dm.cobite.com","avatar":null},"body":"Linus Torvalds wrote:\n> Some branches don't get any ancestors at all, because their ancestor gets \n> a \"dotcount\" value of 0, and are thus not considered any better than not \n> having any ancestor. That's obviously wrong. Even a zero-dot-count \n> ancestor is better than having none at all.\n> \n> This fixes the issue by making not having an ancestor branch have a \n> goodness value of -1, avoiding the problem (because even a zero dot-count \n> will be considered better).\n> \n> Alternatively, the special-case for the \"1.1.1.1\" revision should be \n> removed (or made to imply a dot-count of 1).\n> \n\n\nThanks for this.  I'll look at bundling this and some miscellaneous \nother stuff this weekend (pray to gods for rain so I can stay in all \nweekend ;-).\n\nAnyway, I'd like to nail down some of the other nagging ancestry/branch \npoint problems if possible.\n\nDavid\n"},{"id":"17875","messageId":"Pine.LNX.4.64.0603240739360.26286@g5.osdl.org","threadId":"3701","inReplyTo":"44240619.20103@dm.cobite.com","subject":"Re: Fix branch ancestry calculation","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-24T15:46:28Z","receivedAt":"2006-03-24T15:46:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Mar 2006, David Mansfield wrote:\n> \n> Anyway, I'd like to nail down some of the other nagging ancestry/branch point\n> problems if possible.\n\nWhat I considered doing was to just ignore the branch ancestry that cvsps \ngives us, and instead use whatever branch that is closest (ie generates \nthe minimal diff). That's really wrong too (the data just _has_ to be in \nCVS somehow), but I just don't know how CVS handles branches, and it's how \nwe'd have to do merges if we were to ever support them (since afaik, the \nmerge-back information simply doesn't exists in CVS).\n\nI actually went back to read some of the original CVS papers, and realized \nthat CVS _without_ branches actually makes perfect sense.\n\nSuddenly it was a perfectly reasonable system: the fact that you can only \nmerge once (between working tree and repo) is perfectly reasonable when \nthere is only one branch and checking in requires you to have updated \nfirst. All the things I really hated about CVS just go away if you don't \ndo any branches at all.\n\nOf course, it's a much less powerful thing without branches, but what I'm \ngetting at is that the whole branch support seems to have been a total \ncrock added later on top of something that was never designed for it, and \nwhere the data-structures aren't even set up for it.\n\nLive and learn. (Of course, maybe I'm wrong, and the thing doesn't make \nsense even without branches).\n\n\t\t\tLinus\n"},{"id":"17877","messageId":"1143218338.6850.68.camel@neko.keithp.com","threadId":"3701","inReplyTo":"Pine.LNX.4.64.0603240739360.26286@g5.osdl.org","subject":"Re: Fix branch ancestry calculation","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-03-24T16:38:58Z","receivedAt":"2006-03-24T16:38:58Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Fri, 2006-03-24 at 07:46 -0800, Linus Torvalds wrote:\n> \n> On Fri, 24 Mar 2006, David Mansfield wrote:\n> > \n> > Anyway, I'd like to nail down some of the other nagging ancestry/branch point\n> > problems if possible.\n> \n> What I considered doing was to just ignore the branch ancestry that cvsps \n> gives us, and instead use whatever branch that is closest (ie generates \n> the minimal diff). That's really wrong too (the data just _has_ to be in \n> CVS somehow), but I just don't know how CVS handles branches, and it's how \n> we'd have to do merges if we were to ever support them (since afaik, the \n> merge-back information simply doesn't exists in CVS).\n\ncvsps is more of a problem than cvs itself. Per-file branch information\nis readily available in the ,v files; each version has a list of\nbranches from that version, and there are even tags marking the names of\nthem. One issue that I've discovered is when files have differing branch\nstructure in the same repository. That happens when a branch is created\nwhile files are checked out on different branches.  I'm not quite sure\nwhat to do in this case; I've been trying several approaches and none\nseem optimal. One remaining plan is to just attach such branches by\ndate, but that assumes that the first commit along a branch occurs\nshortly after the branch is created (which isn't required).\n\nOf course, this branch information is only created when a change is made\nto the file along said branch, so most of the repository will lack\nprecise branch information for each branch. When you create a child\nbranch, the files with no commits in the parent branch will never get\nbranch information, so the child branch will be numbered as if it were a\nbranch off of the grandparent. Globally, it is possible to reconstruct\nthe entire branch structure.\n\n> Suddenly it was a perfectly reasonable system: the fact that you can only \n> merge once (between working tree and repo) is perfectly reasonable when \n> there is only one branch and checking in requires you to have updated \n> first. All the things I really hated about CVS just go away if you don't \n> do any branches at all.\n\nIf you look at how deltas are stored in the file you get an even\nstronger argument -- CVS has always advertised that it stores deltas\n'backwards' so that the current version is first in the file. That's\ntrue for the trunk, but for every other branch, you have to seek back\nfrom the tip of the trunk to the branch point and then walk forwards to\nthe desired version along the branch.\n\n-- \nkeith.packard@intel.com\n"},{"id":"17899","messageId":"20060325014532.GB32522@pe.Belkin","threadId":"3701","inReplyTo":"1143218338.6850.68.camel@neko.keithp.com","subject":"Re: Fix branch ancestry calculation","fromName":"Chris Shoemaker","fromEmail":"c.shoemaker@cox.net","sentAt":"2006-03-25T01:45:32Z","receivedAt":"2006-03-25T01:45:32Z","isPatch":false,"sender":{"key":"c.shoemaker@cox.net","avatar":null},"body":"On Fri, Mar 24, 2006 at 08:38:58AM -0800, Keith Packard wrote:\n> On Fri, 2006-03-24 at 07:46 -0800, Linus Torvalds wrote:\n> > \n> > On Fri, 24 Mar 2006, David Mansfield wrote:\n> > > \n> > > Anyway, I'd like to nail down some of the other nagging ancestry/branch point\n> > > problems if possible.\n> > \n> > What I considered doing was to just ignore the branch ancestry that cvsps \n> > gives us, and instead use whatever branch that is closest (ie generates \n> > the minimal diff). That's really wrong too (the data just _has_ to be in \n> > CVS somehow), but I just don't know how CVS handles branches, and it's how \n> > we'd have to do merges if we were to ever support them (since afaik, the \n> > merge-back information simply doesn't exists in CVS).\n> \n> cvsps is more of a problem than cvs itself. Per-file branch information\n> is readily available in the ,v files; each version has a list of\n> branches from that version, and there are even tags marking the names of\n> them. One issue that I've discovered is when files have differing branch\n> structure in the same repository. That happens when a branch is created\n> while files are checked out on different branches.  I'm not quite sure\n> what to do in this case; I've been trying several approaches and none\n> seem optimal. One remaining plan is to just attach such branches by\n> date, but that assumes that the first commit along a branch occurs\n> shortly after the branch is created (which isn't required).\n> \n> Of course, this branch information is only created when a change is made\n> to the file along said branch, so most of the repository will lack\n> precise branch information for each branch. When you create a child\n> branch, the files with no commits in the parent branch will never get\n> branch information, so the child branch will be numbered as if it were a\n> branch off of the grandparent. Globally, it is possible to reconstruct\n> the entire branch structure.\n\nIf that last sentence was a typo then you already know this, but\notherwise you may be disappointed to learn that it's not _always_\npossible to discern the correct ancestry tree.\n\nThe simplest counter-example is two branches where each adds one file\nand no files in common are modified.  If A and B both branched off of\nHEAD and each adds one file, then they should each only have one file.\nBut if B branched from A which branched from HEAD, then B should also\nhave the file that was added to A. (*)  However, the information to\ndistinguish these two cases isn't recorded in CVS.  \n\nI seem to have described this example more fully in the notes I took\nwhile writing the patch to cvsps that does the global inferrence\nyou're describing.  You _usually_ can make a very good guess, and the\nmore files that are modified, the better you can do.\n\nBTW, those notes are still available here:\nhttp://www.codesifter.com/cvsps-notes.txt \n\nIf you end up comparing the ancestry tree discovered by your tool and\nthe tree output by a patched cvsps, I would be very interested in the\nresults.\n\n-chris\n\n(*) You can distinguish between A->B->head and B->A->head simply by\ndate.\n"},{"id":"17914","messageId":"1143273256.6850.86.camel@neko.keithp.com","threadId":"3701","inReplyTo":"20060325014532.GB32522@pe.Belkin","subject":"Re: Fix branch ancestry calculation","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-03-25T07:54:16Z","receivedAt":"2006-03-25T07:54:16Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Fri, 2006-03-24 at 20:45 -0500, Chris Shoemaker wrote:\n\n> If that last sentence was a typo then you already know this, but\n> otherwise you may be disappointed to learn that it's not _always_\n> possible to discern the correct ancestry tree.\n\nSure, it's possible to generate trees which can't be figured out. So\nfar, I haven't found any which can't be pieced back together, except in\ncases where the tree was accidentally damaged (child branches created on\ntwo separate parent branches)\n\n> If you end up comparing the ancestry tree discovered by your tool and\n> the tree output by a patched cvsps, I would be very interested in the\n> results.\n\nSo far, I've found several concrete trees where cvsps (in any form)\nassigns branch points many versions too early compared to the 'true'\nhistory. My tool is getting better answers, but still can't compute the\ntree for the X.org X server tree yet. That one has a wide variety of\ndamage, including the direct copying of ,v files between repositories\nwhich had divered, and the accidental branching of files from different\nparent branches. I keep poking at it...\n\n> -chris\n> \n> (*) You can distinguish between A->B->head and B->A->head simply by\n> date.\n\nI'm doing a lot more date-based identification than I'm really\ncomfortable with; the bad thing here is that branch points can occur\nlong before any commits to that branch, when doing date-based\noperations, you have a range of possible matching branch points and it's\nhard to disambiguate.\n\n-- \nkeith.packard@intel.com\n"}]}