Re: [Monotone-devel] partial pull #2 - gaps instead of a single horizon

[Timothy Brownawell]

On Fri, 2007-05-25 at 10:51 +0200, Markus Schiltknecht wrote:

> I've had a look at implementing those gaps. I think we could simply 
> build rosters for complete gaps and process normally from there on. I 
> would even add the necessary (parent, child) tuples in revision_ancestry 
> for the gaps. So you could still build an ancestry tree. Just one which 
> has revisions in it, which stand for a whole gap, i.e. multiple 
> (missing) revisions. For mtn log or mtn annotate, you wouldn't have to 
> care about bailing out as soon as you hit the horizon, but you'd just 
> get a special revision_t, which stands for a whole set of missing 
> revisions. If you ask me, the issue gets a tad simpler, as soon as you 
> start to think of gaps instead of a (single) horizon.

How special does it have to be? The only differences I see are that (1)
it has a different revision_id, so we need something signed by the
server saying the most recent revision that it replaces, and (2) it can
have >2 parents.

> Of course, gaps also don't come for free. The hardest problem probably 
> is, that a gap can perfectly well have more than two ending revisions, 
> i.e. ancestors. Our current roster and merge code doesn't support that. 
> (Hm, I remember having raised that issue before...) We could either add 
> support for more than two ancestors or work around the issue by letting 
> monotone insert multiple cascaded sentinels, sort of a binary tree. I 
> still prefer the first option, but the second is probably easier to do 
> and doesn't pose problems with the mark merge algorithm.

I think there are really only problems with *generating* revisions with
multiple ancestors; the only reason we can't have them in history is
because we chose to have the sanity checking not allow it.

> While talking about merging: in the presence of gaps, merging is not 
> always possible. Of course, you'd have to have the two revisions you 
> want to merge - we need their rosters. Additionally, we need the common 
> ancestor. 

How much do we need to preserve? We currently either need any revisions
in which files were added or an assertion by the server that certain
apparently different files are really the same, and maybe some
intermediate nodes to preserve some amount of the graph shape (not
*necessary*, but useful for having reasonable common ancestors for text
merge).


-- 
Timothy

Free (experimental) public monotone hosting: http://mtn-host.prjek.net