[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-users
Subject:    Re: [darcs-users] Why darcs? What does the 'physicists proof' actually prove?
From:       David Roundy <droundy () abridgegame ! org>
Date:       2003-07-25 11:38:04
Message-ID: 20030725113804.GC31594 () jdj5 ! mit ! edu
[Download RAW message or body]

On Tue, Jul 22, 2003 at 06:01:13PM +1000, William Uther wrote:
> Questions 7 and 8 might be irrelevant if you answer question 9...

I think 8 is obsoleted by the answer to 9.

> Question 7: Where does darcs use unwinding?
> 
> I can see what you are doing.  I'm missing the why.  What is an example
> of the use of unwinding?

It is used internally in interpereting mergers.  In particular, when a
merger is applied, all the conflicting patches in the merger need to be
unapplied, so an unwind is how I figure out what patches involved in the
merger need to be undone.

> Question 8: Where do you use commutation?
> 
> Again, I can see this is used in the theory.  Where is it used in 
> practice?

....

> Question 9: What is the darcs algorithm?
> 
> There is a lot of formalism given, but the algorithm for 'pull' is not
> given.  i.e. Given a current set of patches, particular patch I wish to
> apply, and the context for that patch, how do I apply it to the current
> set of patches?

The reason I don't give the algorithm for actually doing anything is
basically that once you have the theory of patches, you can do it however
you choose, as long as you don't make a mistake.  A mistake being applying
a patch out of context--in fact I think that is really the only mistake.  I
guess the only mistakes would be applying a patch out of context, commuting
two patches that are not sequential, or merging two patches that are not
parallel.  So if you avoid making mistakes and follow the formalism, the
algorithms to use are pretty trivial.  Actually, it's very easy to make
mistakes... but in theory the practical algorithms are trivial!  :)

> I'd expect something like the following (I'm making this up as I go 
> along, so this might be a little wacky):
> 
> Let C be the context in my current working copy.
> Let P be the patch I want to pull from another repository.
> Let C' be the context of the patch P in the remote repository.
> 
> Let D = C - C', and let D' = C' - C.  (using the set theoretic concept 
> of subtraction)
> 
> For each patch Q in D', commute P and Q.  If they fail to commute, then 
> mark Q as a dependancy of P that must be applied first.  If the commute 
> succeeds, then P has been altered so that it no longer has Q in it's 
> context - remove Q from C' and D'.
> If there are any dependancies then ask the user to get them, and apply 
> them first.  If not, then continue.
> 
> D' should now be the empty set.
> 
> For each patch Q in D, there ?should? be at least one which applies in 
> parallel with P, lets call it Q.  Then use the darcs merge to turn P || 
> Q into P'Q.  If this conflicts, then ask the user to resolve the 
> conflict.  Now set P <- P' and D <- D-Q, and keep going.
> 
> D should now be empty, and you can apply the modified patch.
> 
> Is this at all close?

It is essentially correct--practically identical to the algorithm used.
Which is what I meant by saying the algorithm is trivial.  If you really
understand the theory of patches, you can pretty easily see how to do
things.  The only difference between your algorithm and the one I use is in
the case of conflicts.  Because of the "every merge succeeds" property, we
don't need to resolve the conflicts until after the patch has been applied,
and in general don't want to.  For example if we have want to merge:
{
hunk test 1
-A
+B
}
with
{
hunk test 1
-A
+C
hunk test 1
-C
+D
}
we'd rather just tell the user that there is a conflict between
hunk test 1
-A
+B
and
hunk test 1
-A
+D
rather than first asking to resolve the conflict with the chage to D.

The other differences between your algorithm and that used by pull are
simply because pull prompts interactively, so I interleave user interaction
with the commuting, which gets to be tedious, since I start with the oldest
patch (which by definition has no dependencies, since D' is empty), and the
user has three options, Y (pull that patch), N (don't pull that patch) and
W (wait to see if I want a patch that depends on that patch).  But that
just leads to more book keeping.

Another suggestion is that rather than thinking in terms of sets, it is
also useful (intuition-wise) to picture the patches in order.

Say my repo is:

ONMLKJIHGFEDCBA

And I want to pull X from

ZYXWVUTSRQPHGFEDCBA

Here C is ONMLKJIHGFEDCBA, C' is WVUTSRQPHGFEDCBA, D' is WVUTSRQP and D is
ONMLKJI.

The algorithm becomes: (first dropping ZY, which are unimportant to us)

XWVUTSRQPHGFEDCBA <-> W'X'VUTSRQPHGFEDCBA <-> W'V'(X2)UTSRQPHGFEDCBA etc.

Until we reach (unless there are commutation failures, which would have to
be dealt with either by failing or by pulling the dependencies).

W'V'U'T'S'R'Q'P'X8HGFEDCBA

There's no need to describe the whole algorithm again, but this is how I
think of (and visualize) the pull process, which I find helpful.

> My apologies for the long post, and my thanks for any insight you have
> the time to provide.

No problem!
-- 
David Roundy
http://www.abridgegame.org


[prev in list] [next in list] [prev in thread] [next in thread]