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

Eric Y. Kow eric.kow at gmail.com
Sun Oct 7 21:04:24 UTC 2007

On Wed, Sep 26, 2007 at 11:59:22 -0700, David Roundy wrote:
> Here's the latest state of the conflictors work.  Unfortunately,
> the last patch is rather large, as one change led to a cascade of
> others, including some refactorings that I didn't have the patience
> to factor out.  Work continues...

This is just a running annotation of your first patch in the series.
Review for the latter patches will follow.

David: Comments are not particularly directed at you (I do have one
minor question marked Q1) ; they are basically just me reading the
code aloud.

And sorry for the huge delays, especially since I have no legitimate
excuse.  Just being lazy while home in Jacksonville.

Add first cut at conflictors.

> appendRL :: (MyEq p, Patchy p) => (RL p :> p) C(x y) -> RL p C(x y)

Sticks a patch onto the end of a sequence unless it is already present
or can be commuted there.  See my description of head_permutationsFL in
my 2007-08-26 message to darcs-devel [[ darcs patch: Partial remerge
(and 8 more) ]].

conflicted vs conflictors

The names Conflictor and Conflicted are pretty easy to get confused.
I'm not entirely sure I understand the difference between the two
except that conflictors are implemented on top of conflicteds.

In the darcs source code:
> data ConflictedPatch C(x y) where
>     Normal :: Prim C(x y) -> ConflictedPatch C(x y)
>     Conflicted :: FL Prim C(c b) -> Prim C(b a)
>                -> ConflictedPatch C(c c)

A conflicted patch is either just a primitive patch (no conflict) or
what I call a "truly conflicted sequence".  A truly conflicted sequence
is a forward sequence of primitive patches, followed by a single
primitive patch which they conflict with.  We can think of these two
(the sequence of primitive patches and the one primitive patch) as being
two branches in a conflicts tree.

> +data ConflictorPatch C(x y) where
> +    P :: Prim C(x y) -> ConflictorPatch C(x y)
> +    Conflictor :: FL ConflictedPatch C(a b) -> ConflictedPatch C(b b)
> +               -> ConflictorPatch C(a b)
> +    InvConflictor :: FL ConflictedPatch C(a b) -> ConflictedPatch C(b b)
> +                  -> ConflictorPatch C(b a)

A conflictor is either a primitive patch; or what I call a "true
conflictor", which is a forward sequence of ConflictedPatches followed
by a single ConflictedPatch.  Note that true conflictors may be marked
as inverted.

Note also that the single ConflictedPatch in a true conflictor has no
effect.  This does not necessarily mean that it is a 'truly conflicted
sequence'; it could be an identity patch, for instance.

instance ReadPatch ConflictorPatch

> +instance ReadPatch ConflictorPatch where
> + readPatch' want_eof =
> +     do s <- peek_input
> +        case fmap (sal_to_string . fst) $ my_lex s of
> +          Just "conflictor" ->
> +              do work my_lex
> +                 lex_string "["
> +                 Just (Sealed ps) <- readPatch' want_eof
> +                 lex_string "]"
> +                 Just (Sealed p) <- readPatch' want_eof
> +                 return $ Just $ Sealed $ Conflictor ps (unsafeCoerceP p)

Just pointing out the possible refactor between conflictor and inverse
conflictor parsing, and similarly output.  I kinda wish we could just
infer the parsing code from the output code :-)

> +instance Apply ConflictorPatch where
> +    apply opts (P p) = apply opts p
> +    apply opts (Conflictor x _) = apply opts $ invert x
> +    apply opts (InvConflictor x _) = apply opts x

I assume this is intentional: that applying a conflictor consists in
applying its inverse and vice versa.

commute_simple :: CommuteFunction

> +-- Efficiently handles the case of commuting two conflicted patches.  This
> +-- case is a simple swap because conflicted patches do not modify each other.
> +commute_simple (P p1 :> P p2) = toPerhapsUnknown $ do p2' :> p1' <- commute (p1 :> p2)
> +                                                      return (P p2' :> P p1')
> +commute_simple _ = Unknown

I might just be misunderstanding, but I get the impression that the
comment above does not correspond to this block of code.  Here you
aren't just swapping; you are actually commuting the two primitive
patches.  Did you perhaps mean to associate it with
commute_simple_conflict, or maybe some other function like easy_commute?

commute_simple_conflict :: CommuteFunction

I'm going to annotate this function with a more compact ad-hoc notation
I just made up.  Nobody should take this notation to be official.
 * write patch sequences p1 :> p2 :> p3,
   so p1 :>: NilFL would be just written p1
 * write Conflicted NilFL pX as cpX,
   (conflicted = Conflicted NilFL)
 * surround conflictors with {} and use ; to delimit the sequence from
   the single conflicted patch

> +commute_simple_conflict (P p1 :> P p2)
> +    = Succeeded (Conflictor (Normal p1:>:NilFL) (conflicted p2) :>
> +                 InvConflictor (Normal (invert p2):>:NilFL) (conflicted (invert p1)))

If we fail to commute two (primitive) patches
     p1 :> p2
we return two conflictors
     {  p1  ; cp2  }
  :> {^ p2^ ; cp1^ }

> +commute_simple_conflict (Conflictor (Normal p1:>:NilFL) (Conflicted NilFL p2) :>
> +                         InvConflictor (Normal ip2:>:NilFL) (Conflicted NilFL ip1))
> +    | IsEq <- invert ip2 =\/= p2 , IsEq <- invert ip1 =/\= p1 = Succeeded (P p1 :> P p2)

The conflictors
     {   p1  ; cp2  }
  :> {^  p2^ ; cp1^ }
trivially commute as
     p1 :> p2

This is just the reverse of the above, which might make some intuitive

> +commute_simple_conflict (P ip1 :> Conflictor (Normal p1:>:NilFL) (Conflicted NilFL p2))
> +    | IsEq <- invert ip1 =\/= p1 = Succeeded (P p2 :>
> +                                              Conflictor (Normal (invert p2):>:NilFL) (conflicted $ invert p1))

The commutation of
   p1^ :> { p1 ; cp2 }
is also trivial:
   p2  :> { p2^ ; cp1^ }

[Q1] Could the (conflicted $ invert p1) also be written (conflicted ip1)?

> +commute_simple_conflict _ = Unknown

To sum up, we know how to handle the following commutations
     p1 :> p2
     { p1  ; cp2 } :> {^ p2^ ; cp1^ }
     p1^ :> { p1 ; cp2 }

The symmetrical counterparts to these cases are handled by
clever_commute.  Fancier cases such as conflictors with more than a
singleton sequence are handled by commute_another.

commute_another :: CommuteFunction

This handles all the cases that neither commute_simple nor
commute_simple_conflict could handle.

> +commute_another (P p1 :> Conflictor xs x)
> +    | Sealed (Normal _ :>: _) <- remerge (Normal p1 :>: xs +>+ (x :>: NilFL)) 
> +    = case commuteFL (Normal p1 :> xs) of
> +      Just (xs' :> Normal p1') ->
> +          case commute (Normal p1' :> x) of
> +          Just (x' :> _) -> undefined x' xs' -- Succeeded (Conflictor xs' x' :> P p1')
> +          Nothing -> impossible
> +      Just (_ :> _) -> impossible
> +      Nothing -> errorDoc $ blueText "impossible case 1 in Conflictor.lhs" $$ showPatch (Normal p1 :>: xs)

This code tells us how to commute a primitive patch with a conflictor in
which the sequence is longer 

> +commute_another (P p1' :> InvConflictor xs x)
> +    | Sealed (Normal _ :<: _) <- reverseFL `mapSeal` remerge (xs +>+ (x :>: Normal (invert p1') :>: NilFL)) 
> +    = case commuteRL (reverseFL xs :> Normal (invert p1')) of
> +      Just (Normal ip1 :> xs') ->
> +          case undefined of -- commute (Normal (invert ip1) :> x) of
> +          Just (x' :> _) -> undefined x'  ip1 xs' -- Succeeded (InvConflictor (reverseRL xs') x' :> P (invert ip1))
> +          Nothing -> impossible
> +      Just (_ :> _) -> impossible
> +      Nothing -> impossible remove_active_inverse_from_set remove_conflicted_inverse_from_set initLastFL

> +commute_another _ = Unknown

initLastFL :: FL a C(x y) -> (FL a :> a) C(x y)

> +initLastFL NilFL = bug "incorrect call of initLastFL"
> +initLastFL (x :>: NilFL) = NilFL :> x
> +initLastFL (x :>: xs) = case initLastFL xs of
> +                        xs' :> l -> (x :>: xs') :> l

Given a nonempty list, peels off the last element and returns it

For example:
   [a, b, c]
gives us
   [a, b] :> c
written with pretend list sugar

> +remove_active_inverse_from_set :: Prim C(x y) -> FL ConflictedPatch C(y z)
> +                        -> Maybe (FL ConflictedPatch C(x z))
> +remove_active_inverse_from_set p xs = rifs p $ head_permutationsFL xs
> +    where rifs :: Prim C(x y)
> +               -> [FL ConflictedPatch C(y z)]
> +               -> Maybe (FL ConflictedPatch C(x z))
> +          rifs pp ((Normal p' :>: xs'):_)
> +              | IsEq <- pp =/\= invert p' = Just xs'
> +          rifs pp ((Conflicted NilFL p' :>: _):_)
> +              | IsEq <- pp =/\= invert p' = Nothing
> +          rifs pp (_ : xss) = rifs pp xss
> +          rifs _ [] = Nothing

See if there is any way for p^ to be commuted down to the front of the
list.  If so and it does not result in a conflict, return the resulting
list sans p^.


1. Resulting in a conflict is as good as p^ not being in the list.

2. This is highly sensitive to the order of the list of permutations
   [FL ConflictedPatch C(y z)].  The scenario in my head is that
   there may be two permutations in the list, one where p^' is Normal
   and one where it is Conflicted.  In the case where the former
   comes first, we return Just; in the case where it is the latter
   that comes first, we return Nothing.

   I have three guesses here:
      (a) this is OK because it is inherently impossible for p^ to
          bubble up to the front of the list in such distinct ways,
          i.e. as both Normal and Conflicted.
      (b) this is OK because the head_permutationsFL returns the
          permutations in a guaranteed sensible order which does
          exactly what we want.
      (c) this is not OK, which I doubt

3. Seems like you could factor the recursion out of this, with good
   ol' filter, or a list comprehension.

> +remove_conflicted_inverse_from_set :: Prim C(x y) -> FL ConflictedPatch C(y z)
> +                                   -> Maybe (FL ConflictedPatch C(y z))
> +remove_conflicted_inverse_from_set p xs = rifs p $ head_permutationsFL xs

Same as above, only we return Just if p^ bubbles up to the front of the
list as a Conflicted patch.  It bubbling up as a Normal patch is as good
as it not being there, which is somewhat worrying to me.

combining commutation functions
> +infixl 2 |||
> +(|||) :: CommuteFunction -> CommuteFunction -> CommuteFunction
> +(c1 ||| c2) p = clever_commute c1 p `mplus` clever_commute c2 p
> +
> +clever_commute :: CommuteFunction -> CommuteFunction
> +clever_commute c (p1:>p2) =
> +    case c (p1 :> p2) of
> +    Succeeded x -> Succeeded x
> +    Failed -> Failed
> +    Unknown -> case c (invert p2 :> invert p1) of
> +               Succeeded (p1' :> p2') -> Succeeded (invert p2' :> invert p1')
> +               Failed -> Failed
> +               Unknown -> Unknown

clever_commute tries first to commute
    p1  :> p2   If that returns Unknown it tries to commute
    p2^ :> p1^  into
    p1^':> p2^' which it then inverts into
    p2' :> p1'
Again, this requires that for all possible commutations, p1^' == p1'^.

This function is 'clever' because it saves us the work of writing
symmetrical commutation functions.  We just specify one case and let its
counterpart be automatically derived from clever commute.  For example,
above we have code for handling the commutation of Conflictor :>
InvConflictor, but not the other way around.   clever_commute lets us
recycle that code to take care of the opposite case.  The code is
borrowed from the primitive patch stuff and just has a different type.

In general, one useful trick in reading darcs code is to understand that
we keep the commutation code modular by breaking it down into little
mini-commutation functions that fit together thematically.  We then
cascade them so that if one commutation function fails, we try the next
one on the list.  The alternative would be to have one big function with
a whole mess of guards or case alternatives.

You may be wondering why we use Succeeded, Failed and Unknown in the
cascade instead of the usual Just and Nothing.  As I understand it,
having three cases lets us optimise the code a bit.  If we know that
something simply will not commute no matter how many commutation
functions you shake at it we say so and halt the cascade immediately.

> -#define fromJust (\m_fromJust_funny_name -> case m_fromJust_funny_name of {Nothing -> bug ("fromJust error at "++__FILE__++":"++show (__LINE__ :: Int)++" compiled "++__TIME__++" "++__DATE__); Just x -> x})
> +#define fromJust (\m_fromJust_funny_name -> case m_fromJust_funny_name of {Nothing -> bug ("fromJust error at "++__FILE__++":"++show (__LINE__ :: Int)++" compiled "++__TIME__++" "++__DATE__); Just xyz -> xyz})

I guess stuff like this is what makes Lisp and maybe Liskell nice.
I wouldn't know though.

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/20071007/34ccc4d0/attachment.pgp 

More information about the darcs-devel mailing list