[darcs-devel] darcs patch: Add first cut at conflictors. (and 6 more)

Eric Y. Kow eric.kow at gmail.com
Tue Oct 16 04:49:30 UTC 2007


The rest of the review/annotations (although I sort of gave up towards
the end)

======================================================================
Second conflictor code, passes a few more test cases.
======================================================================

Implements some of the fancier merge cases.

> -force_commute z = unPerhaps $ commute_simple z `mplus` (commute_simple_conflict |||
> -                                                        commute_another) z
> +force_commute z = unPerhaps $ force_commute' z

Just a refactor, nothing to see.

> -          Just (x' :> _) -> undefined x' xs' -- Succeeded (Conflictor xs' x' :> P p1')
> +          Just (x' :> Normal p1'') ->
> +              case p1' =/\= p1'' of
> +                IsEq -> Succeeded (Conflictor xs' x' :> P p1')
> +                NotEq -> impossible
> +          Just _ -> impossible

I don't really understand this function (commute_another), but this is
largely because I still have not looked into what remerge does.
Roughly, the idea is that when commuting a patch p1 against a conflictor
{ xs ; x }, you first commute p1 past xs and then past x.  p1' =/\= p1''
seems to be a sensible sanity check.  I'm guessing we could also check
p1 =/\= p1'.  Perhaps this going wrong is a less likely possibility.

> +          case commute (Normal p1' :> x) of
> +          Just (x' :> Normal p1'') ->
> +              case p1' =/\= p1'' of
> +                IsEq -> Succeeded (InvConflictor (reverseRL xs') x' :> P (invert ip1))
> +                NotEq -> impossible

This handles the case of commuting a patch p1 against an *inverse*
conflictor {^ xs ; x }.  We first commute p1^ against xs, and then
against x

======================================================================
add another unit test.
======================================================================

I never really pay attention to these.  Maybe one day.

======================================================================
make a few more test cases work
======================================================================

> +subcommutes :: [(String,
> +                 (FORALL(x y) ConflictorPatch :> ConflictorPatch) C(x y)
> +                     -> Maybe ((ConflictorPatch :> ConflictorPatch) C(x y)))]
> +subcommutes = [("simplest", toMaybe . commute_simple),
> +               ("simple", toMaybe . clever_commute commute_simple_conflict),
> +               ("cleanly", toMaybe . clever_commute commute_cleanly),
> +               ("unconflicting conflictors", toMaybe . clever_commute commute_conflictors),
> +               ("total", commute)]

Not sure what this is for

>  commute_conflictors :: CommuteFunction
> +commute_conflictors (InvConflictor xs x :> Conflictor ys y)
> +    | Just (ys' :> ixs') <- commute (invert xs :> ys),
> +      Just (y' :> rixs') <- commuteRL (reverseFL ixs' :> y),
> +      IsEq <- rixs' =/\= reverseFL ixs', -- guaranteed to be true
> +      Just (ys'' :> ix') <- commuteFL (invert x :> ys'),
> +      IsEq <- ys'' =\/= ys', -- guaranteed to be true
> +      Sealed (Normal _ :>: _) <- remerge (x :>: ys' +>+ y' :>: NilFL)
> +                     = Succeeded (Conflictor ys' y' :> InvConflictor (invert ixs') (invert ix'))

to commute {^ xs ; x }  :> { ys ; y },
 commute xs^  :> ys  to ys'  :>  xs^'
 commute xs^' :> y   to y'   :>  xs^'' (with reversal of xs^)
 commute x^   :> ys' to ys'' :>  x^'
return
  { ys' ; y' } :> {^ xs' ; x' } (assuming that xs^'^ = xs')

David: did you really want ys' here and not ys''?

> +commute_conflictors (Conflictor xs x :> Conflictor ys' y')
> +    | Just (ys :> xs') <- commute (xs :> ys'),
> +      Just (y :> rxs') <- commuteRL (reverseFL xs' :> y'),
> +      IsEq <- rxs' =/\= reverseFL xs', -- guaranteed to be true
> +      Just (ys'' :> ix') <- commuteFL (invert x :> ys'),
> +      IsEq <- ys'' =\/= ys', -- guaranteed to be true
> +      Sealed (Normal _ :>: _) <- remerge (x :>: ys' +>+ y' :>: NilFL)
> +                       = Succeeded (Conflictor ys y :> Conflictor xs' (invert ix'))

Interesting that you chose to write the primes in this way (y' going to
y).  Any particular reason why?

I'm also not sure why it makes sense to invert x here, but then again,
I don't really understand conflictors anyway.

> +commute_conflictors (Conflictor ys' y' :> InvConflictor xs' x')

Would this particular case be captured by clever_commute?

======================================================================
fix detection of conflicts between conflictors.
======================================================================

> +doesnt_conflict :: ConflictedPatch C(x x) -> FL ConflictedPatch C(x y) -> Bool
> +doesnt_conflict x ysy = isnormalfor (lengthFL xs) remerged
> +    where xs = blowup x
> +          Sealed remerged = remerge (xs +>+ ysy)
> +          isnormalfor n _ | n <= 0 = True
> +          isnormalfor n (Normal _ :>: zs) = isnormalfor (n-1) zs
> +          isnormalfor _ _ = False

David: can (remerged xs +>+ ysy) be shorter than xs, and if so, is it
expected for isnormalforn to return False in that case?

> +blowup :: ConflictedPatch C(x x) -> FL ConflictedPatch C(x x)
> +blowup c@(Conflicted xs _) = reverseRL $ c :<: bu (reverseFL xs)
> +    where bu (z:<:zs) = Conflicted (reverseRL zs) z :<: bu zs
> +          bu NilRL = NilRL
> +blowup (Normal x) = Normal x :>: NilFL

Not really sure what this is for, but using an ad-hoc notation for
Conflicted patches

blowup (a :> b :> c / x) gives us
     [ (a           / b)
     , (a :> b      / c)
     , (a :> b :> c / x)
     ]
           
======================================================================
define "Shy" patch type, which preserves dependencies on commute.
======================================================================

shy patches just being a way to make conflicted patches commute in
a different way

> +    commute (cx@(SC xs x) :> cy@(SC ys y)) =
> +        do commute (invert (xs +>+ x :>: NilFL) :> ys +>+ y :>: NilFL)
> +           return (cy :> cx)

Given cy :> cx, return cy :> cx (unmodified as these are conflicted
patches), but only if cx and cy actually commute.

> +    commute (SC xs x :> SN y) = do xs' :> iy' <- commuteFL (invert y :> xs)
> +                                   x' :> _ <- commute (iy' :> x)
> +                                   return (SN y :> SC xs' x')

Why does y get inverted here?

> +    commute (SN y :> SC xs x) = do xs' :> y' <- commuteFL (y :> xs)
> +                                   x' :> _ <- commute (y' :> x)
> +                                   return (SC xs' x' :> SN y)

Interestingly, in this and the SC :> SN case above, we return the normal
patch unmodified, but the conflicted patch modified by commutation with
the normal patch.  I guess this makes sense.  The conflicted patch has
no effect, so it shouldn't do anything to whatever it commutes with.
Above, if you have two conflicted patches, neither should have an effect
on the other.  Just ships passing by.

> +    merge (x :\/: y) = impossible x y

Really?

======================================================================
various refactorings and work on conflictors.
======================================================================

Ok, I'm reaching point of being too tired to review properly.  In
this goes.

Big addition here seems to be commute_conflicting_conflictors.

Also, now the :> operator is right-associative so that
  a :>  b :>  c :> d
should be thought of as
  a :> (b :> (c :> d))

-- 
Eric Kow                     http://www.loria.fr/~kow
PGP Key ID: 08AC04F9         Merci de corriger mon français.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 186 bytes
Desc: not available
Url : http://lists.osuosl.org/pipermail/darcs-devel/attachments/20071016/d40f34e7/attachment.pgp 


More information about the darcs-devel mailing list