[darcs-users] Fwd: Towards a conflict-free revision control system.

[Eric Kow]

(I'm removing the camp list from my CC list because of errors)

On Mon, Feb 02, 2009 at 19:47:22 +0100, Jean-Philippe Bernardy wrote:
> Let's take a simple example. Imagine we index lines by rationals for
> the moment.  The indices are picked randomly by the system as long as
> they preserve the order of the user file. The fact that they are
> rationals ensure that one can always insert something between two
> other things.  We'll see how we can refine this later.

Thanks for your example.

Now I understand that
(a) the weights (Int) are used to detect conflicts
(b) rationals as line indices are used to allow different patches to the
    same place to be applied concurrently (e.g. 2.1 and 2.2 are
    modifications to line 2 made in two different repositories)
(c) a tree-structured file allows for blocks to be inserted between
    lines (and not just lines).
Is that right?

In this particular example, a negative weight tells us we are removing
the same line twice (or N times), which can be marked up as a conflict.
Are there other ways that the weights are used?

> Initial state, each line is a triple (weight, index, contents)
> 
> 1 1 a
> 1 2 b
> 1 3 c

I'm just going put these side by side for the interested
(sorry, fixed-width fonts, only)

> User A changes to: | User B changes the initial state in his own repo to
>                    | 
> 1 1 a              | 1 1 a
> 1 2.1 x            | 1 2.2 y
> 1 3 b              | 1 3 c
>                    | 
> The patch is       | The patch is
>                    | 
> -1 2 b             | -1 2 b
> 1 2.1 x            | 1 2.2 y

> Composing the initial state with both patches yields:
> 
> 1 1 a
> -1 2 b
> 1 2.1 x
> 1 2.2 y
> 1 3 c
> 
> The external representation for this merge can be:
> 
> a
> <<<
> b
> >>>
> x
> y
> c

(Just checking: did you mean to include some kind of marker between y
 and c?)

> Here the "conflict" can be detected because a line has a negative weight.
> 
> There are a few catches with proceeding as such.
> 
> 1. Line indices may clash

By this you mean that the indices (say 2.1 vs 2.2) are handed out
randomly, but it may so happen anyway that the two users get the same
index?  If so, is your solution just to reduce the probability of a
clash to something really small?  I wonder if it would be useful to
have some scheme where one does not rely on randomly assigned indices,
but some kind of automatic index renaming instead.

> 2. The notation for representing conflicts is non-standard

I'm not sure I understand what you mean exactly

> 3. Merging concurrent insertions at the same point may yield
> arbitrary interleavings.

And from your explanation below, this is why files are represented as
trees?  Just to make sure I have the 'shape' of the idea right, this
means that files will only be as wide as their initial version
(everything else is an insertion)?

> 1. Cannot really be fixed with 100% certainty; this is a matter of using the
> appropriate precision when picking new indices.
> 2. To fix this the tool should warn about all potential conflicting
> situations, see below...
> 3. Is fixed by indexing by list of rationals, yielding the tree structure.
> (A new node is created to ensure contiguity of a block)
> 
> e.g. if user C inserts a big block he could have:
> 
> 1 1 a
> 1 2.3;1 u
> 1 2.3;2 v
> 1 2.3;3 w
> 1 3 c

Thanks!

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20090214/cac19848/attachment.pgp>