[darcs-devel] Bug in get_extra :)

David Roundy droundy at abridgegame.org
Sat Jan 8 10:18:18 PST 2005


On Mon, Jan 03, 2005 at 03:16:01AM +1000, Anthony Towns wrote:
> David Roundy wrote:
> >Alas, it does seem that for all its complexity, the merger code is broken.
> >:(
> 
> :(
> 
> I'm not actually trying to find bugs in darcs, I'm actually just trying 
> to work out how mergers are supposed to work. At least when darcs is 
> confused about it too, I don't feel so bad about not getting it :)

I've just fixed a bug in the merger code (a problem Zooko had turned out to
be relatively straightforward, which helped me find the problem), and in
the process ended up simplifying the merger commutation code a bit.

You could try taking a look at the new code, if you're curious.

> Anyway, the reason I'm trying to find out the tricky bits is so I can 
> fill in the bits of the patch theory that don't make sense to me. I did 
> come up with something that almost works as an algorithm for commuting 
> mergers that doesn't need all the unwinds and glumping; but 
> unfortunately there's a catch. The algorithm's current draft is 
> something like:
> 
> 	commute :: Patch -> Patch -> Maybe(Patch, Patch)
> 
> 	commute x (Merger True y z) =
> 		do (x', y') <- unmerge x y
> 		   (_, z')  <- commute x' z
>                    let newZ = cM y' z'
> 		   in return (newZ, (cM newZ x))
> 
> 	commute (Merger True x y) z =
> 		do (x',z') = merge x z
> 		   return (z', cM x' (cM z y))
> 
> 	cM x y :: Patch -> Patch -> Patch
> 	cM x y = case merge x y in
> 		       Just(_, y') -> y'
> 		       Nothing     -> Merger(x,y)
> 
> But the catch is that while "commute" and "merge" can fail instead of 
> introducing mergers (I think), unmerge has to be able to deal with 
> things like unmerging (M(A,B), M(B,A)) to (B,A), which regular commute 
> can't do. :(

Actually, merge can't fail.  Its type signature is a relic of days past.
What you mean by merge here is actually elegant_merge (apart from minor
differences).

Unmerge can't fail on two patches that were created by a merge.  If the two
patches weren't merged in the first place, then unmerge can in fact fail
(which is where your commute using unmerge falls down).

> >[discussion of conflictor code]
> 
> Neat. That might solve my unmerge problem. :-/

If you want to play with the new code, it's in darcs-unstable, and you just
need to change the line

elegant_merge = old_elegant_merge

to

elegant_merge = new_elegant_merge

in order to enable the new conflictor code.  It should work in the simplest
cases, where you've just got two conflicting sequences of patches.
Branched conflicts and higher-order conflicts aren't yet working.

Since "merger" methods (i.e. anything like M(A,B)) inherently have
exponential costs, even if they are done right (since they have exponential
space usage), I definitely want to focus on the conflictor code, but would
love to discuss the algorithms, since that's where the fun (and hard) part
is.

In the conflictor code, the "merge" code is all implemented in the
"commute" code via force_commute, which makes some things easier and other
things harder.

> >In case you didn't make the connection, once I get the new code up and
> >running, I'll definitely appreciate testing of the sort you're now doing on
> >the old code.  I'm afraid, however, that the old code may be fundamentally
> >flawed here, so fixing these bugs in the old code may not be possible.  :(
> 
> So, the other half-baked thought I had was related to resolving 
> conflicts. I think it'd work really well to introduce a new "resolution" 
> patch type, R(<history>,patch), such that:
> 
> 	applying R(<history>,patch) doesn't change the repository
> 	applying patch to <history> gives the same contents as the
> 		current repository
> 
> 	commute R(<h>, p), NamedP(n,q) =
> 		do (_, p') = commute p q
>                    return (NamedP(n,q), R(<h,n>, p'))
> 
> 	commute NamedP(n,p) R(<h>,q)
> 		| n `elem` h = do (q', _) = commute p q
>                                   return (R(<h'>,q'), NamedP(n,p))
> 		| otherwise = Nothing
>
> and applying a patch to a repo with ...,R(<h>,p) is reduced to applying 
> a patch to <h>,p.

I see (after a minute or so of staring...).  It's an interesting idea, but
there are issues that would need to be worked out.  As implemented, it
violates the rule that commute is its own inverse,
i.e. prop_commute_either_way from PatchTest.

What this comes down to when it comes to applying the R patch is that it
had better be *able* to modify the repository, otherwise when someone else
pulls the R patch from you and merges it with their patches, the R patch
had better end up modifying their repository.  I'm not sure how this would
work out, or that it could be worked out at all.
-- 
David Roundy
http://www.darcs.net




More information about the darcs-devel mailing list