[darcs-users] [patch273] Haddock merge2FL and fastRemoveFL in Pat... (and 4 more)

Eric Kow kowey at darcs.net
Wed Jun 23 15:24:57 UTC 2010

And here's the last review.

Unfortunately, this is very much a level-1-only review.  I was very focused on
figuring out the basic idea of how this patch works, so with the attention I
put on the story (see below), I may have missed something in the details! (and
I may also be missing some big picture stuff)
This patch is motivated by discoveries we made in patch262.
It addresses the recently filed issue1879.

On Mon, Jun 07, 2010 at 20:06:18 +0000, Petr Ročkai wrote:
> Mon Jun  7 21:59:12 CEST 2010  Petr Rockai <me at mornfall.net>
>   * Make partitionFL do a 3-way split, and detect commutation bugs in Depends.

Maintainability comments, we seems that we should do some subset of

* fix the haddock to tell what middle is for
* change partitionRL for symmetry
* rename this to a special-purpose function, perhaps one which returns
  Left when middle is non-empty

Otherwise, applied, thanks!

Make partitionFL do a 3-way split, and detect commutation bugs in Depends.
The context of this patch is that want to fix a regression where we stopped
noticing the anomalous situation (caused by CVS conversions) where patch that
we think we have in common with the other repo actually depends on patches
specific to that repo.

(Think about that: if we have them in common, why could it possible depend on
some other patch we don't have?)

We used to complain "bug in get_extra"
which was misleading but better than nothing  (the tricky bit is that bug in
get_extra can sometimes be due to a bug, or sometimes be due to a situation
like the above).  Now we just simply fail to notice, and worse, let you have a
bag of patches!

I've created a test case (attached) which I plan to push along with this patch.

>  findCommonWithThem :: RepoPatch p => PatchSet p C(start x) -> PatchSet p C(start y)
>                     -> (PatchSet p C(start) :>> FL (PatchInfoAnd p)) C(x)
>  findCommonWithThem us them =
>      with_partial_intersection us them $
>      \common us' them' ->
>          case partitionFL ((`elem` mapRL info them') . info) $ reverseRL us' of
> -        common2 :> only_ours -> PatchSet (reverseFL common2) common :>> only_ours
> +          _ :> bad@(_:>:_) :> _ -> bug $ "Failed to commute common patches:\n" ++
> +                                   (renderString $ vcat $ mapRL (humanFriendly . info) $ reverseFL
> +bad)
> +          common2 :> _ :> only_ours -> PatchSet (reverseFL common2) common :>> unsafeCoerceP only_ours

[extra context inserted]  This part of the patch is basically the motivation
for the 3-way permute below.  The context is that we're rifling through "our"
patches to see if we have any patches in common with "them".  The way we tell
if patches are in common is if they have the same patchinfo.

I confess I don't understand this function that well, but I know that one thing
we do is to try and partition our list into:
 - patches in common
 - patches not in common (us only)

Now, the thing is that the common patches may be mixed in with some patches
that are only ours (thank-you commutation).  That's perfectly *fine*; all we
have to do is commute them back out, separating the list into common and
only_ours.  And of course, evidently, this commutation should always succeed 
because the patches in question are common (think about it, how would they
have gotten a hold of these patches if they depend on something they don't
have), so problem, right?


It turns out there are cases where commutation can fail, but these are cases
which are triggered by naughty repositories.  Before this patch, we failed to
notice such naughty repositories.  Instead we thought that the common patches
were ours_only and this led to all sorts of weirdness, like patches appearing
more than once in the history.

Phew! Good thing this ways only a regression in HEAD.

> -partitionFL' _ qs NilFL = NilFL :> reverseRL qs
> -partitionFL' keepleft qs (p :>: ps)
> -   | keepleft p,
> -     Just (p' :> qs') <- commuteRL (qs :> p)
> -       = case partitionFL' keepleft qs' ps of
> -         a :> b -> p' :>: a :> b
> -   | otherwise = partitionFL' keepleft (p :<: qs) ps

I think it's useful to begin by showing the initial version of this
helper function.

We want a commute-sensitive partition function: we try to commute all
matching patches to the left side of the list, leaving non-matching
patches (or the matching patches which depend on them behind).  The
mental image I use is of traversing the list while marking out a bubble
of patches that belong on the right side.  If a patch matches, and we
can commute it past the bubble, it is left by definition.  Otherwise it
gets absorbed into the bubble.

So using a lightweight notation, with '(())' for the bubble and patches with
decimals indicate an interesting dependency (in other words, patch 5.3 is a
patch that depends on 3).  To highlight interesting dependencies, an example
traversal might look like this:

(())   l1       l2    r3   r4      l5.3   l6
l1   (())       l2    r3   r4      l5.3   l6
l1     l2     (())    r3   r4      l5.3   l6
l1     l2     ((r3))  r4   l5.3    l6
l1     l2     ((r3    r4   l5.3))  l6
l1     l2       l6  ((r3   r4      l5.3))

LEFT:  l2 l2 l6
RIGHT: r3 r4 l5.3

> +partitionFL' _ middle right NilFL = (NilFL :> reverseRL middle :> reverseRL right)
> +partitionFL' keepleft middle right (p :>: ps)
> +   | keepleft p = case commuteRL (right :> p) of
> +     Just (p' :> right') -> case commuteRL (middle :> p') of
> +       Just (p'' :> middle') -> case partitionFL' keepleft middle' right' ps of
> +         (a :> b :> c) -> (p'' :>: a :> b :> c)
> +       Nothing -> partitionFL' keepleft (p' :<: middle) right' ps
> +     Nothing -> case commuteWhatWeCanRL (right :> p) of
> +       (tomiddle :> p' :> right') -> partitionFL' keepleft (p' :<: tomiddle +<+ middle) right' ps
> +   | otherwise = partitionFL' keepleft middle (p :<: right) ps

The new version now maintains TWO bubbles, a 'middle' bubble and a
'right' bubble.

We now have 4 cases in increasing complexity:

i. The simplest case is if the current patch is non-matching, in which case
   it just gets absorbed into the right bubble.

ii. The next simplest case is if the current patch commutes past both
    bubbles (first the right, then the middle), because then it just goes
    on the left.

iii. Next, if a patch commutes past only the right bubble (stopping at the
     middle), then it gets absorbed into the middle bubble

iv. The interesting case is what happens when the patch does not even commute
    past the right bubble.  Basically we redraw the boundaries between middle
    and right: we do so by pushing p as far down the right bubble as we can.  Where
    we stop becomes the new middle/right boundary.

Following this example (using % to indicate the middle/right bubble boundary)

((%))   l1     l2     r3     r4     l5.3   l6  (case ii)
 l1    ((%))   l2     r3     r4     l5.3   l6  (yawn)
 l1     l2    ((%))   r3     r4     l5.3   l6  (case i, r3 ADDED TO RIGHT)
 l1     l2    ((%     r3))   r4     l5.3   l6  (case i)
 l1     l2    ((%     r3     r4))   l5.3   l6  (case iii!)
 l1     l2   ((r3     l5.3 % r4))   l6         (case ii)
 l1     l2     l6   ((r3     l5.3 % r4))

LEFT:   l1 l2 l6
MIDDLE: r3 l5.3
RIGHT:  r4


PS. to understand commuteWhatWeCanRL, first understand commuteWhatWeCanFL
    commuteWhatWeCanRL is the same exact function (it is not the reverse
    version, but one which accepts reversed lists as arguments)

Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20100623/ae5f68f5/attachment.pgp>

More information about the darcs-users mailing list