Subject: Re: Consistency question

From: David Kastrup <[email-masked]>
Date: Wed, 15 Jan 2014 14:00:30 +0100

Andreas Krey <[email-masked]> writes:

> On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:
> ...
>> With a single root, "depth" helps a lot.  When looking for a common
>> parent of a number of commits, you first shorten all ancestries to the
>> same size and then you can look for the point of convergence in
>> lockstep.
>
> Hmm, how about traversing from all the start commits downwards
> simultaneously, noting which start you say each commit from, and stopping
> when you have a commit carrying all start labels?

It means that when the start commits are at considerably different
depth, you'll traverse much more material than necessary.

Also you need labels.

> I don't quite see how the same size plus lockstep works out (but the
> 'same size' part is possibly the same as my 'concurrent traversal').

It just equalizes the depth before starting, so you don't need labels:
any common ancestor is reached at the same time by its descendants.

Of course, I conveniently forgot merge commits.  This scheme works out
of the box only with single parenting.  And it works fine without a
common ancestor, too: you just run into a NULL pointer at the same time
when there isn't one.

So, uh, this solution does not really seem to match the problem...

-- 
David Kastrup