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

Jean-Philippe Bernardy bernardy at chalmers.se
Sat Feb 14 17:18:06 UTC 2009


On Sat, Feb 14, 2009 at 3:38 PM, Eric Kow <kowey at darcs.net> wrote:
> (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?

Yes.

> 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?)

No. This is mainly what I mean by "non standard marking of conflicts"

>> 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?

Yes and yes. In fact in my latest version I do a hashing instead of
random picking.

> 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.

Yes, I believe there is lots of room for improving the internal representation.

>> 2. The notation for representing conflicts is non-standard
>
> I'm not sure I understand what you mean exactly

See above.

>> 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?

Yep.

> 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)?

Right; unless you insert at the end or beginning.

Cheers,
JP.


More information about the darcs-users mailing list