bzr-revnocache can now cache the merge graph

[Ian Clatworthy]

The trunk of bzr-revnocache now lets you configure what
gets cached: "just" the rev-id=>revno map or the full
(sorted) merge graph. If you're interested in helping
to test out the latter, grab the latest code and edit
the top of __init__.py. (FWIW, you can also disable
caching altogether if you want as well.)

Note that the trigger for storing the merge graph is
currently still Branch.get_revision_id_to_revno_map().
There is no Branch.iter_merge_revisions() API that
I can override yet. A MERGE/RFC is in the review queue
for this.

As a next step, I'd like to try out caching "mergelines"
in addition to or instead of the full merge graph. I
expect a mergeline record to look something like:

 mergerevno depth length last_rev_id join_rev_id [first_rev_id split_rev_id]

See my comment in https://bugs.launchpad.net/bzr/+bug/125773
for an explanation of these terms. If I'm wasting my time going
down this track, please let me know!

At a minimum, I expect this cache will:

* be a small fraction of the other caches size wise
  and therefore be orders of magnitude faster to load

* speed up lookups of dotted_revno -> rev_id because
  of this.

I also wonder whether we can reconstitute the sorted merge
graph and/or rev_id=>revno map from *just* this information
efficiently? Thoughts? Sample code to help me write

  def iter_merge_lines(branch, merge_graph_iter)?

Perhaps that API together with something like

  def mergeline_revision_info(branch, mergerevno)

would be useful in other parts of bzrlib or plugins?
I suspect knowing where each mergeline got joined into
the graph (i.e. a child pointer) must be useful in
some graph walking algorithms, yes?

In summary, bzr-revnocache continues to grow as a
proof-of-concept. I think it could nicely complement
John's lazy-revno calculation branch which focusses
on efficiently going the other direction, i.e.
rev-id to revno conversion. As branch is extended
with APIs like iter_merge_revisions(), performance
improvements ought to gradually ripple though the
various commands as the code starts using them (and
users install this plugin).

Ian C.