Numbering of non-mainline revisions
James Westby
jw+debian at jameswestby.net
Wed Mar 12 18:45:43 GMT 2008
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
More information about the bazaar
mailing list