[RFC] X.Y.Z dotted revnos

[John Arbash Meinel]

Robert Collins wrote:
> If we're changing them, lets ensure that it is easier to generate revnos
> for partial data sets. Specifically, 'log' should not have to load the
> whole graph before it starts.
> 
> Not making it worse is ok but if we're working on it ---
> 
> -Rob

I agree that would be nice, but I think it is out of the scope of this
particular change. This algorithm scales the same as our original
algorithm. So things at least are not worse than before.

The problem as I see it is detecting when a node is not reachable from
an earlier parent. Something like:

:
A
|\
B C
| |\
D E F
| | |
: : |
| | |
|/ /
G /
|/
H

If you do a simple Breadth-first search, H will see C and A long before
they are seen by G.

I think it would be possible with a specialized graph search.
find_differences() is approximately correct if you give it 2 revisions
that you want to graph. It is incorrect in that it tries to find the
differences in both directions, when you only care about the set for one
side.

However, if you were able to get the set of unique nodes on one side,
and the nodes it took to find them, I *think* you would have enough of
the graph to properly generate either notation.

I think doing this as you ask would be a multiple-day job, rather than
the couple hours it took for me to put this together.

John
=:->