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

[Timothy Brownawell]

On Mon, 2007-05-28 at 07:23 +0200, Markus Schiltknecht wrote:
> Hi,
> 
> Timothy Brownawell wrote:
> > 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....
> 
> I don't understand why you want to do things so complicated. What gain 
> would the hash of the sentinel text data give us? Or the special cert? 

I'm trying to think how we could do it with minimal invasiveness to what
we already have. So instead of adding however many new pseudo-revision
objects and transmitting node-ids over netsync (which makes them a
permanent concept, instead of a local cache), just have the server
generate a new revision from a string of actual revisions and somehow
instruct the client that that revision can be used in place of the
actual most recent revision that was collapsed.

> It's not like we need to verify correctness of the sentinel data - we 
> can't anyhow since we are missing the real revision data.

We can't verify it, so we have to trust it. Which means we need to know
who it comes from, so that that can be an informed decision. Which means
that it either needs to be signed, or we need to track which server it
came from and not allow servers to provide this data unless they
generate it from a full history graph themselves.


> Though I don't quite get your argument about rewriting history. In what 
> way would history-collapsing allow something that's impossible otherwise?

If there are gaps in the history graph, we can't know that it's
well-formed. We can usually verify this because a child contains the
hash of the parents, but if we allow holes in the graph we need some
other means to connect ancestor<->descendant across the hole. And since
we can't *know* that it's correct without having all intermediate
revisions, whoever tells us what that relationship is has the power to
rewrite history.

> >> 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.
> 
> Sure, so what's the problem?  You would simply add sentinels for f and 
> g, while h and i are the first real revisions you have. Both sentinels 
> would have the very same set of ancestors, namely a, b and c.

...But f is not descended from c?

> > 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:
> 
> Nope. G1 and G2 would both have the same node id for the added file. 
> Thus monotone should be able to not add it twice.

This requires that node-ids be transmitted over the network, which is
one of the things I'm trying to find a way to avoid.


-- 
Timothy

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