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

Eric Kow kowey at darcs.net
Sun Feb 1 18:21:43 UTC 2009


Hi,

I've had a chance to sit down and read this.  Here are some superficial
comments, followed by some questions.

I do like the idea of separating an 'internal' representation of state
from the 'external' one.  It seems like the darcs pristine cache,
especially in its hashed form, is an approximation of the internal
state.  For what it's worth, I also get the impression also that this
distinction is something that the darcs user manual (and the
Understanding Darcs wikibook) attempt to make, at least informally.

Unless I am mistaken, the unrecord command in the appear appears to be
akin to the darcs obliterate/unpull command than to darcs unrecord.  Is
that intentional?  (Unrecord only changes the internal state, leaving
the external state untouched; see also revert which does the opposite).

I'm afraid I didn't understand the idea of "weights", nor did I fully
understand the use of a tree structure to represent the lines in a
file.  I am dimly aware that representing the file as a list of lines
will not suffice if we want to have an internal representation that
allows us to simultaneously represent conflicting states.  But in
what is the representation tree shaped?  For example, are conflicting
modifications to a line just different sublines?  Perhaps an example?

On Wed, Jan 07, 2009 at 15:17:06 +0100, Jean-Philippe Bernardy wrote:
> > First (of two) questions: what, in a nutshell, does it mean not to have any
> > conflicts?  Clearly, there can be conflicting situations (i.e. two people edit
> > different parts of a file).  How roughly does your idea cope with them?  As you
> > can see, I haven't yet had the chance to read the paper, but was hoping for a
> > little bit more of a taster (now that I've had the teaser)
 
> In our representation of files, each line is given a unique identity.
> Let's imagine for a moment that two people replace the same part of a
> file with another. It means that some portion of the file was removed
> twice. Therefore, there will be a "minus one" zone in that portion of
> the file that indicate the problem. (This is very similar to two
> people withdrawing the same money concurrently on the bank account.)

How would a user perceive this?
 
> > Second question.  The paper says:
> > | Darcs will flag this scenario as a conflict, i.e. it cannot represent such a
> > | merge. The result of a merge in Darcs is dependent on the order that the
> > | changes are applied, Darcs will try all possible "non conflicting" permutations
> > | of the changes which will result, in the worst case, in exponential complexity.
> >
> > What does this mean, please?  I thought the whole point of the darcs approach
> > to conflicts is that it be completely independent of order (i.e. we cancel out
> > both patches).
 
> Surely you know more about darcs than us, so we can clear it up
> together. Note that we refer to darcs 1.0. Isn't it true that the
> patch representation (potentially) changes after a reordering?

Well, I must warn you that I'm really a patch theory novice and very
easily in over my head.

I had the understanding that the exponential nature of darcs 1.0 was due
to a use of nested structures.  That is, if there is a conflict, the
representation of one of the combatants must be modified to include a
copy of the patch it is conflicting with.  That means that each conflict
doubles the size of a patch.  If there are conflicts of conflicts, we
get yet more doubling and the rest is history.

Darcs 2, if I understand correctly, still uses some amount of nesting,
but it helps by including enough information to avoid the nesting in the
most common cases, i.e. with spurious conflicts of conflicts (I don't
have a precise definition of this, but rather a vague understanding that
a lot of things that darcs 1.0 would consider a nested conflict are
actually just by-products of its conflicts resolution, and can be
avoided).  As a result, the conflict explosion is avoided, except in
cases of conflict fights, where we have case of a genuinely nested
conflict.

This is all very vague because my understanding is very limited.
Perhaps others can step in to clarify.  The point is that I remain a bit
suspicious of this particular version of the story from the paper:

| Darcs will try all possible "non conflicting" permutations of the
| changes which will result, in the worst case, in exponential
| complexity.

Is that right?  What does it mean?

Thanks very much!

(Now, I hope to have a chance to sit down and play with focal a bit)

-- 
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: 194 bytes
Desc: not available
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20090201/cced9e91/attachment.pgp 


More information about the darcs-users mailing list