Re: [Monotone-devel] Merging suspend branch

[Nathaniel Smith]

(BTW, the threading on your messages seems to be broken in my email
reader?)

On Sat, Jul 14, 2007 at 09:03:42PM -0700, William Uther wrote:
> Zack wrote:
> >  SELECT child FROM revision_ancestry WHERE child NOT IN (SELECT
> >parent FROM revision_ancestry)
[snip]
> hrm.  We'll need to be a little trickier.  If a head of a branch has  
> a child in another branch then your query not return it, but it could  
> still be a head.
[snip]
> And even that wont work, because you're not checking the validity of  
> the certs.  We may not be trusting certs by specific individuals, but  
> we will still have removed revisions from the list of heads if an  
> untrusted person has committed a child.

Phylogeny recapitulates ontogeny -- you pretty much went straight
through the history of our attempts to write head-finding functions
there :-).  IIRC there are pretty good tests for this stuff as a
result, though, so it's an easy place to experiment with.

Btw:
> Hrm. If you have a single revision in your DB, does it get entered in  
> the ancestry table?  Or do we need to extend this further.

Yes.

> After the revs in a branch have been gathered, this is the function  
> that does the work finding the heads: erase_ancestors_and_failures()
> 
> And it has this comment:
> 
> // this call is equivalent to running:
> //   remove_if(candidates.begin(), candidates.end(), p);
> //   erase_ancestors(candidates, app);
> // however, by interleaving the two operations, it can in common  
> cases make
> // many fewer calls to the predicate, which can be a significant  
> speed win.
> //
> // FIXME: once we have heights, we should use them here.  The  
> strategy will
> // be, to calculate the minimum height of all the candidates, and teach
> // accumulate_ancestors to stop at a certain height, and teach the  
> code that
> // removes items from the candidate set to occasionally rescan the  
> candidate
> // set to get a new minimum height (perhaps, whenever we remove the  
> minimum
> // height candidate).
> 
> I don't understand heights.  Should I leave things the way they were  
> and wait for that FIXME to be fixed?

You could figure out heights :-).  I don't know how much of a speed
win the described optimization would be -- it would help a lot for
small branches far from the root (like the little side branches we
create all the time), probably not so much for something like nvm.
There may also be cleverer ways to use heights than mentioned there.

The real problem is that so long as cert trust checking is in lua,
we have no way to tell when trust may have changed, and thus we can't
cache head information in the db (because we have no clue whatsoever
when to invalidate that cache, maybe the user's lua hook calls
get_phase_of_moon()).  Maybe it'd be worthwhile to be cleverer in the
special case (pervasive in practice) where the user simply has not
defined a trust hook...

-- Nathaniel

-- 
Damn the Solar System.  Bad light; planets too distant; pestered with
comets; feeble contrivance; could make a better one myself.
  -- Lord Jeffrey