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

[Timothy Brownawell]

On Fri, 2007-05-25 at 15:17 +0200, Markus Schiltknecht wrote:
> Hi,
> 
> Timothy Brownawell wrote:
> > 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.
> 
> Revision id different from what? Different from the hash of the textual 
> sentinel description, sure. But the revision id of a sentinel should be 
> exactly the revision id it stands for, i.e. the first revision above the 
> horizon - or the newest or whatever you call it. That only blows some 
> sanity checks, but that's easily fixable.

I was thinking that it would be a completely ordinary revision, with the
appropriate revision_id for its text, except that it would be
accompanied by a statement from the server (maybe just a new type of
special cert?) of "This is history-collapsed revision, which can be used
as a replacement for da39....", and then you have a lookup table
somewhere that records this for use by things that walk history and
might need to look at da39....

(You'd also want to disallow committing an immediate child of a
history-collapsed revision, since they're basically a way to allow
rewriting history.)

> > 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.
> 
> Uhm.. I remember Nathaniel saying, that mark merge might be tricky with 
> multiple (>2) ancestors. And as we would have to be able to provide a 
> roster for the gap, we need to provide those markings.

But we already know what value we're going to end up with. ...although
we still have to be able to determine if it should be marked, which I
guess means we would have to upgrade to deterministic *-merge.

> > 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).
> 
> Uhm.. dunno.
> 
> But theoretically, think of replacing all revs in a gap with a single 
> revision. You could have committed it all in one go, no? That's how I'm 
> thinking the sentinel could 'trick' the merge algorithm (and a lot of 
> the rest of the monotone machinery).

What about a wide gap?

a       b   c
 \     /    |
------------------
   \ /      |    ^
    d       e    |
    |\    /      G
    |  \ /       A
    f   g        P
    |   |        |
    :   :        |
    |   |        v
-------------------
    h   i

The gap has two heads, so it needs at least two revisions to replace it.

a       b        c
 \     / \      /
--------------------
  \  /     \  /
   G1       G2
   |        |
--------------------
   |        |
   h        i

But if you added a file in d, then this has it being added twice, as two
separate files. So you need an extra revision:

a       b  c
 \     /   |
------------
  \  /     |
   d       |
   | \     |
   |   \  /
   G1   G2
   |    |
------------
   |    |
   h    i


> How much do we need to preserve? Well, all the files which were added in 
> *any* of the revisions in the gap. But none of the revision texts 
> themselves. That's the goal of partial pull: only pull the files and not 
> care about historical information.

Or I suppose you could just say that if you want to merge, you need
complete history back to all minimal common ancestors.


-- 
Timothy

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