[darcs-devel] Bug in get_extra :)

[Anthony Towns]

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

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)

	-- x might be a Merger itself
	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))

	-- z is definitely not a Merger
	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. :(

I'm not sure that's solvable; and I'm also not sure the above algorithm 
even terminates reliably -- while the unmerger/commute are okay on their 
own, the cM can build up even more complicated patches, potentially ones 
that'll later be reduced... :(

It's completely untested, of course :)

Still, on the offchance it might be useful there it is. :)

> The way this is implemented is that I introduce a "force_commute" which
> always succeeds, and which creates a pair of conflictors (one "forward"
> conflictor, and one "inverse" conflictor) when you use it to commute two
> non-commuting patches.  The result is that when you use force_commute, the
> merge theorem always works (since all the relevant commutations must
> succeed).  This places stronger constraints on the commutation properties
> of conflictors than there were on the commutation properties of mergers.
> What remains to be seen is whether those constraints can be satisfied.

Neat. That might solve my unmerge problem. :-/

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

It's half baked because:
	(a) I still don't grok mergers :)
	(b) I'm not sure how to work out when to merge against a
	    Resolving patch instead of the real history

There are two really nice things about it, though: one is that it lets 
the user tell darcs how to ignore historical mergers that're getting 
annoying to commuter around; and the other is it lets you tell darcs 
explicitly how to merge things, so if you happened to change "foo" to 
"bar" by hand instead of using replace, and then a few weeks later start 
getting patches against the old version, you could add a resolving patch 
R(<oldtag>, "replace foo.txt [A-z0-9] foo bar") and be happy.

Resolving a merge conflict would take the form:

	H, A, M(A,B), {P, R(<H:A>, Pa), R(<H:B>, Pb)}

where Pa ~= diff(H,A ; H,A,M(A,B),P) and Pb likewise.

Cheers,
aj