[RFC] Cherry-picking, reordering revisions and 2D versioning

[John A Meinel]

David Allouche wrote:
> On Fri, 2006-01-13 at 11:13 +0100, Jan Hudec wrote:

...

>> Yes, that's clear and makes sense. And should probably work, though the
>> details of weave-merge (3-way merge won't be able to deal with this)
>> will still be a bit tricky.
> 
> I have been repeatedly assured by some of the few that really understand
> weave merging (Martin and Aaron) that weaves support cherry-picking by
> design. From what I can tell, weave-merge support for cherry-picks, is
> kind of just a matter of actually coding it.

I am not 100% sure of this. The problem is that you need a way to
declare that specific lines were generated from a given revision. In the
current weave format, that means you declare that revision to be an
ancestor of the current revision, and don't mark them as deleted. With
the current weaves, only lines from your ancestors can be inside your
current text, and there is no way to include non-continuation ancestry.
(To say that FOO is an ancestor, but the ancestors of FOO are not).

I'll try to give an example to make it clear. We have revisions 1, 2, 3,
and 2b, which is a cherry pick of 3.
The text of 1 is:
A
And 2:
A
B
And 3:
A
B
C
Ignore for now that by context, we would probably get a conflict, but if
we cherry pick just 3, then 2b should be:
A
C

How is this represented in the weave...

Revision 1
1 - no parents
{ 1
. A
}


Revision 2
1 - no parents
2 - parents = 1
{ 1
. A
}
{ 2
. B
}

Revision 3
1 - no parents
2 - parents = 1
3 - parents = 2
{ 1
. A
}
{ 2
. B
}
{ 3
. C
}

Revision 2b
1 - no parents
2 - parents = 1
3 - parents = 2
2b - parents = 1,3
{ 1
. A
}
[ 2b
{ 2
. B
] 2b
}
{ 3
. C
}

The problem lies in how we mark lines as originating from a revision.
Basically, we only have {3 } to say that these lines were added in 3.
And the only way the code will include those in another revision, is if
3 is in the ancestry of 2b. But if 3 is 2b's ancestor, then 2 is also
3's ancestor. And the above looks like just a plain merge, where we
deleted the line B, not a cherrypick where we just added C.

Alternatively, you could record 2b as:
1 - no parents
2 - parents = 1
3 - parents = 2
2b - parents = 1
{ 1
. A
}
{ 2
. B
}
{ 3
. C
}
{ 2b
. C
}

But now you don't know that C actually came from 3.

The concept of line-wise annotated storage, with annotated merging
*does* support cherry picking. If you had some way to store this:

Text 1:
1 A
Text 2: parent 1
1 A
2 B
Text 3: parent 2
1 A
2 B
3 C
Text 2b: parent 1
1 A
3 C

Then you have all the cherry picking you could want. Because 2b now
declares that one of the lines came from 3, but that it hasn't merged
all of 3's ancestry.

I think there was some discussion about adding parents which don't
include ancestry. Some way of saying '3 is an ancestor, but 3's
ancestors are not'.

Knits are a little bit more flexible about how things are annotated,
since they are a diff with per-line annotations. But right now weaves in
memory are in the same format as the on-disk representation. So we would
need a different internal representation as well. (ie this is a Weave
issue, not a disk representation issue)

John
=:->

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060116/e385824e/attachment.pgp