Numbering of non-mainline revisions

[John Arbash Meinel]

-----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-----