Numbering of non-mainline revisions

[James Westby]

Hi all,

I was having a beer last night, and it bought back
myself and John's discussion on Friday night
over a beer of an efficient way to assign dotted
revision numbers to non-mainline revisions.

He convinced me that his revision numbering scheme
is the best one that we could have, and we also
saw the start of a more efficient algorithm to calculate
them, one that doesn't use the whole of history.

I wrote up some pseudocode for what I thought that
algorithm might be, and attached it to this mail. I
would be grateful if anyone has any comments on it.

A number of points:

  1. It continually follows left hand ancestories
     back to the mainline, when we may have already
     done that for one element in the ancestory. I.e.
     given

        *
        |\
        | a
        |/ \
        c   b
        |  /
        | /
        |/
        d

     it will first follow a's left hand (as it is the right hand
     parent of c) and then b's (as it is the right hand parent of
     d). There could probably be some sort of cache here to avoid
     that.

  2. It doesn't stop when it knows how to number the "other_revision"
     that was passed, it numbers all lines of branches that started
     from the same mainline revision and have been merged back. There
     could be a short circuit added somewhere.

  3. It does require the full mainline, but doesn't use the full history
     of everything on average. This wouldn't play to well with lazy
     history branches.

  4. I have no idea whether it fits in with the existing way that these
     numbers are generated. It may perform very badly with the way
     that it is asked to generate numbers. Also I have no idea if
     is even faster than what we have.

  5. I haven't tested it in the slightest, so I have no idea if it
     even gives the right result in all cases. There's no error
     checking anywhere either.

Sorry for being lazy and not integrating it with what we have,
or even testing and benchmarking it.

I would appreciate any comments that anyone has.

Thanks,

James

-------------- next part --------------
A non-text attachment was scrubbed...
Name: dotted.py
Type: text/x-python
Size: 4683 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080312/4e5592b8/attachment-0001.py