Dotted revno "algebra"

[Ian Clatworthy]

On 01/05/10 07:27, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I was talking to Ian on the phone yesterday, and he wanted me to post
> about an idea he had.

John,

Thanks for writing this up.

> The idea was to find a way to describe revisions, that looks like a
> dotted revno, but is, in essence, an algebra for how to reach the revision.
>
> The basic idea is to keep a 3-digit number, but to change how those
> digits get assigned. Specifically:
>
> 1) First digit is based on the mainline revision that merged this revision.
>
> 2) Second digit uses an 'algebra' to compute a psuedo-number. More on
> this later.
>
> 3) Third digit defines a distance along the lefthand parent history.

To clarify what I was thinking:

4) The first 2 "digits" would continue to indicate a "development line" 
within the graph.

5) The final digit would increase over time.

> For (2) his idea was to, essentially, append another number for every
> time that you follow a right-hand parent. And this number would
> represent *which* parent was followed.
>
> As an example (time goes up):
>
>   I      5
>   |\
>   G H    4   5.1.1
>   | |\
>   D E F  3   5.1.2   5.11.1
>   | |/
>   B C    2   5.1.3
>   |/
>   A      1

Except that I expected H=5.1.3 and C=5.1.1.

> The really nice thing about this layout is that you can look up the
> revision by walking the ancestry graph, without having to know anything
> ahead of time.

That was the goal, yes.

> Some problems that I see:
>
> 1) This graph:
>
>   G      2
>   |\
>   | F        2.1.1
>   | |\
>   | E \      2.1.2
>   | |\ \
>   | | C D            2.11.1  2.11.1
>   | |/ /
>   | B-'      2.1.3
>   |/
>   A      1
>
> ^- C and D have the same number, because you didn't base the new digit
> on what came before.

FWIW, I was thinking C=2.101.1 and D=2.11.1 here. And it here my scheme 
breaks down ... long sequences of 0s will be ugly.

> 2) To be genuinely useful, I think we would have to number the third
> digit with 1 as the most recent revision, and its LH parent getting 2,
> etc. Otherwise you don't know how far back to go until you get to 1,
> without actually computing the graph difference information.

As explained above, I always expected the 3rd digit to increase over 
time, so that implies that the algorithm must know when the mainline is 
branched from.


> Right now, I actually think my favorite version is (5).
>
>   I      5
>   |\
>   G H    4   5.1
>   | |\
>   D E F  3   5.2   5.1.1
>   | |/
>   B C    2   5.3
>   |/
>   A      1
>
>   G      2
>   |\
>   | F        2.1
>   | |\
>   | E \      2.2
>   | |\ \
>   | | C D        2.2.1 2.1.1
>   | |/ /
>   | B-'      2.3
>   |/
>   A      1
>
>   G      2
>   |\
>   | F        2.1
>   | |\
>   | E \      2.2
>   | | |\
>   | | C D        2.1.1 2.1a1
>   | |/ /
>   | B-'      2.3
>   |/
>   A      1

Interesting.

Ian C.