[MERGE/RFC] Add dotted-decimal revision numbers to merge_sorted output

[Robert Collins]

On Thu, 2006-09-07 at 02:57 -0400, Aaron Bentley wrote:
> Robert Collins wrote:
> > Then we have the allocation of revision numbers to 4 descendants of A:
> > B, D, E, H.
> > D is the first found during the search and gets allocated sequence
> > number 0
> > B is second - gets 1
> > E is third and H is forth, getting 2 and 3 each.
> 
> What order does the search go in?

The same as merge_sort - its hooked into the same algorithm, to minimise
multiple passes across revisions for log, and because the two searches
have nearly identical requirements for performance and data stability.
Revisions are allocated a sequence number from there parent in pre-order
traversal, and revision numbers are fully known in post-order traversal.

> > So D gets 1.0.1 (1 from A, 0 from A's sequence when D is first examined,
> > the rightmost 1 is a constant). This is transformed into '2' by the
> > special case for the first descendant.
> > 
> > B gets 1.1.1 (1 from A, 1 from A's sequence number when B is first
> > examined, the rightmost 1 is a constant)
> > 
> > E gets 1.2.1 (1 from A, 2 from A's sequence ... you get the idea I
> > hope ;).
> 
> Much clearer.  I did some thinking about this for weavediff, which used
> positional indicators instead of revision-ids for parents, but that case
> was easier because the conditional indicators didn't need to resemble
> revnos.  So they indicated distance from the target revision, rather
> than distance from the origin.
> 
> > And yes, they are stable - as long as ghosts are not filled in. Doing a
> > pull can change them because pull can give you a tip which
> > short-circuits past revisions along its left-most parent compared to the
> > graph before you pulled. But any number of merge and commits will not
> > cause destabilisation.
> 
> I don't see how that's possible.  If I merge Z, that may fetch Q, and Q
> may be descendant of A, and the new sequence might be B, Q, D, E, H
> which would mean that D, E and H would be renumbered.  It isn't just
> pulls and filling in ghosts that can destabilize it, AFAICT.  It's any
> kind of fetch.

When you merge Z, until you commit, there are no revnos for the
ancestors it brings in. 

When you do the commit, (or if we synthesise a graph entry that looks
like the commit would), you get a graph that looks like:

{K: ['J', 'Z'],
 EXISTING_GRAPH_OF_J,
 EXISTING_GRAPH_OF_Z
}

Now, because we assign sequences during the pre-order portion of the
traversal, ALL the nodes that existin in the portion reachable by J are
assigned first - as they would be when K did not exist. So they are
stable.

The nodes for the Z subgraph - which may indeed join with the J subgraph
- are visited later, and thus cannot affect the numbers assigned to the
components of J.


Rob





-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060907/61b76639/attachment.pgp