Numbering of non-mainline revisions
John Arbash Meinel
john at arbash-meinel.com
Wed Mar 12 22:29:01 GMT 2008
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
James Westby wrote:
| 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
I'm looking into it right now. I can say that as a beginning, if "other_revision
== mainline_revision" it crashes in a branch with only 1 revision.
To give it a bit of a workout, I'm putting together a trivial plugin that I've
uploaded to:
lp:~jameinel/+junk/bzr-test-dotted
I'll experiment with it a bit and let you know.
So far I keep breaking it (I keep getting KeyError exceptions). But I'll see if
I can't get it working and then evaluate its performance, etc. Certainly I could
use it as a starting point.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFH2FktJdeBCYSNAAMRAioUAKDYS1yUf0ubPigCTob75oKV5gE2tQCeMib6
6J4PUiFrM1TGL1jcENyoXmU=
=jgxt
-----END PGP SIGNATURE-----
More information about the bazaar
mailing list