Hi,

This is a work-in-progress bundle, sort of. I guess it could be merged, modulo
the "get.sh" extension that currently fails and needs fixing, or renaming to
failing-. Presumably, most of this *should* go into our first 2.5 alpha.

This also restores the original failures that were present with the old
gcau/get_extra code (including duplicate-related ones).

However, the code should be ready to handle issue1014 and friends, all that
needs to be done is relaxing the error conditions. This may involve passing the
"middle" bit of the findCommonAndUncommon result down the chain, probably as
far as tentativelyMergePatches, which can then decide if the nonemptiness of
the "middle" section is legit (duplicate patches) or is a bug (patchinfo
collision or maybe patch corruption).

Yours,
   Petr.

5 patches for repository darcs-unstable@darcs.net:darcs:

Mon Jun  7 20:48:49 CEST 2010  Petr Rockai <me@mornfall.net>
  * Haddock merge2FL and fastRemoveFL in Patch.Depends.

Mon Jun  7 20:49:34 CEST 2010  Petr Rockai <me@mornfall.net>
  * Use merge2FL instead of plain merge in tentativelMergePatches.

Mon Jun  7 20:50:10 CEST 2010  Petr Rockai <me@mornfall.net>
  * Extend the get test to cover --context interaction with tags.

Mon Jun  7 20:50:41 CEST 2010  Petr Rockai <me@mornfall.net>
  * Extend the issue1014 test to check that named patches are not duplicated.

Mon Jun  7 21:59:12 CEST 2010  Petr Rockai <me@mornfall.net>
  * Make partitionFL do a 3-way split, and detect commutation bugs in Depends.

Attachments

• haddock-merge2fl-and-fastremovefl-in-patch_depends_.dpatch
• unnamed

Hey,

It's 11:10 here and I should probably be starting on that Day Job.
I'm going to apply the most obvious bits of this bundle.  Florent,
would you mind having a look at this one, please?

On Mon, Jun 07, 2010 at 20:06:18 +0000, Petr Ročkai wrote:
> This is a work-in-progress bundle, sort of. I guess it could be merged, modulo
> the "get.sh" extension that currently fails and needs fixing, or renaming to
> failing-. Presumably, most of this *should* go into our first 2.5 alpha.

OK

> However, the code should be ready to handle issue1014 and friends, all that
> needs to be done is relaxing the error conditions. This may involve passing the
> "middle" bit of the findCommonAndUncommon result down the chain, probably as
> far as tentativelyMergePatches, which can then decide if the nonemptiness of
> the "middle" section is legit (duplicate patches) or is a bug (patchinfo
> collision or maybe patch corruption).

I think we need to introduce some extra-evil issue1014 friends.
Can QuickCheck help?

> Mon Jun  7 20:48:49 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Haddock merge2FL and fastRemoveFL in Patch.Depends.
>
> Mon Jun  7 20:50:41 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Extend the issue1014 test to check that named patches are not duplicated.

Applied these two!

> Mon Jun  7 20:49:34 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Use merge2FL instead of plain merge in tentativelMergePatches.
> 
> Mon Jun  7 20:50:10 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Extend the get test to cover --context interaction with tags.
> 
> Mon Jun  7 21:59:12 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Make partitionFL do a 3-way split, and detect commutation bugs in Depends.

Eek, grown-up needed!

Haddock merge2FL and fastRemoveFL in Patch.Depends.
---------------------------------------------------
> +-- | Merge two FLs (say L and R), starting in a common context. The result is a
> +-- FL starting in the original end context of L, going to a new context that is
> +-- the result of applying all patches from R on top of patches from L. This
> +-- version also correctly handles duplicate patches.

What would not correctly handling duplicate patches consist of?

>  merge2FL :: RepoPatch p => FL (PatchInfoAnd p) C(x y)
>           -> FL (PatchInfoAnd p) C(x z)
>           -> Sealed (FL (PatchInfoAnd p) C(y))

Reviewing Haddock patches is interesting because you read the Haddock
and you read the code and you try to think about whether the two fit
together (but if you're like me, your reading of the code is most
definitely influenced by the haddock).  Thanks for documenting these.

It does indeed seem to provide the kind of context you can't just get by
looking at the code.

> +-- whenever the patch has been found and removed. If the patch is not present
> +-- in the sequence at all or any commutation fails, we get Nothing. First two
> +-- cases are optimisations for the common cases where the head of the list is
> +-- the patch to remove, or the patch is not there at all.

Use merge2FL instead of plain merge in tentativelMergePatches.
--------------------------------------------------------------
> Petr Rockai <me@mornfall.net>**20100607184934
>  Ignore-this: 9fde612f399cab5553e9cf57e0764685
> ] hunk ./src/Darcs/Patch/Depends.hs 33
>                   getPatchesBeyondTag, getPatchesInTag,
>                   splitOnTag,
>                   newsetUnion, newsetIntersection,
> -                 commuteToEnd, findCommonAndUncommon
> +                 commuteToEnd, findCommonAndUncommon, merge2FL
>                 ) where
>  import Data.List ( delete, intersect, (\\) )
>  
> hunk ./src/Darcs/Repository/Merge.hs 37
>  import Darcs.Patch
>      ( RepoPatch, Prim, merge, joinPatches, listTouchedFiles
>      , patchcontents, anonymous, fromPrims, effect )
> +import Darcs.Patch.Depends( merge2FL )
>  import Progress( debugMessage )
>  import Darcs.ProgressPatches( progressFL )
>  import Darcs.Witnesses.Sealed( Sealed(Sealed), seal )
> hunk ./src/Darcs/Repository/Merge.hs 58
>  tentativelyMergePatches_ mc r cmd opts usi themi =
>    do let us = mapFL_FL hopefully usi
>           them = mapFL_FL hopefully themi
> -     _ :/\: pc <- return $ merge (progressFL "Merging them" them :\/: progressFL "Merging us" us)
> +     Sealed pc <- return $ merge2FL (progressFL "Merging them" usi) (progressFL "Merging us" themi)
>       pend <- unrecordedChanges opts r []
> hunk ./src/Darcs/Repository/Merge.hs 60
> -     anonpend <- anonymous (fromPrims pend)
> +     anonpend <- n2pia `fmap` anonymous (fromPrims pend)
>       pend' :/\: pw <- return $ merge (pc :\/: anonpend :>: NilFL)
> hunk ./src/Darcs/Repository/Merge.hs 62
> -     let pwprim = joinPatches $ progressFL "Examining patches for conflicts" $ mapFL_FL patchcontents pw
> +     let pwprim = joinPatches $ progressFL "Examining patches for conflicts" $
> +                                mapFL_FL (patchcontents . hopefully) pw
>       Sealed standard_resolved_pw <- return $ standardResolution pwprim
>       debugMessage "Checking for conflicts..."
>       unless (AllowConflicts `elem` opts || NoAllowConflicts `elem` opts) $
> hunk ./src/Darcs/Repository/Merge.hs 71
>       debugMessage "Announcing conflicts..."
>       have_conflicts <- announceMergeConflicts cmd opts standard_resolved_pw
>       debugMessage "Checking for unrecorded conflicts..."
> -     have_unrecorded_conflicts <- checkUnrecordedConflicts opts pc
> +     have_unrecorded_conflicts <- checkUnrecordedConflicts opts $ mapFL_FL hopefully pc
>       debugMessage "Reading working directory..."
>       working <- readUnrecorded r
>       debugMessage "Working out conflicts in actual working directory..."
> hunk ./src/Darcs/Repository/Merge.hs 88
>       when (mc == MakeChanges) $
>            do let doChanges :: FL (PatchInfoAnd p) C(x t) -> IO ()
>                   doChanges NilFL = applyps r themi
> -                 doChanges _     = applyps r (mapFL_FL n2pia pc)
> +                 doChanges _     = applyps r pc
>               doChanges usi
>               setTentativePending r (effect pend' +>+ pw_resolution)
>       return $ seal (effect pwprim +>+ pw_resolution)


Extend the get test to cover --context interaction with tags.
-------------------------------------------------------------
> -rm -rf temp1 temp2
> +
> +cd temp1
> +darcs tag -m tt
> +echo x > x
> +darcs rec -lam "x" x
> +darcs changes --context > my_context
> +cd ..
> +
> +rm -rf temp2
> +darcs get temp1 --context="${abs_to_context}" temp2
> +darcs changes --context --repo temp2 > repo2_context
> +diff -u ${abs_to_context} repo2_context

Looks good, not applied as requested.

Extend the issue1014 test to check that named patches are not duplicated.
-------------------------------------------------------------------------
> +darcs changes
>  
> hunk ./tests/failing-issue1014_identical_patches.sh 62
> +test `darcs changes | fgrep -c '* C'` -eq 1

OK, that is indeed our issue1868 test sorted

Make partitionFL do a 3-way split, and detect commutation bugs in Depends.
--------------------------------------------------------------------------
> Petr Rockai <me@mornfall.net>**20100607195912
>  Ignore-this: b692fb774356bab221442b938d8b4347
> ] hunk ./src/Darcs/Patch/Depends.hs 49
>  import Darcs.Patch.Set ( PatchSet(..), Tagged(..), SealedPatchSet, newset2RL, Origin )
>  import Darcs.ProgressPatches ( progressRL )
>  import Darcs.Witnesses.Sealed (Sealed(..), FlippedSeal(..), flipSeal, seal )
> -import Printer ( renderString )
> +import Printer ( renderString, vcat )
>  #include "impossible.h"
>  
>  {-|
> hunk ./src/Darcs/Patch/Depends.hs 208
>      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
>  
>  findCommonAndUncommon :: RepoPatch p => PatchSet p C(start x) -> PatchSet p C(start y)
>                           -> (FL (PatchInfoAnd p) :\/: FL (PatchInfoAnd p)) C(x y)
> hunk ./src/Darcs/Patch/Permutations.hs 47
>  partitionFL :: Commute p
>              => (FORALL(u v) p C(u v) -> Bool)       -- ^predicate; if true we would like the patch in the "left" list
>              -> FL p C(x y)                          -- ^input 'FL'
> -            -> (FL p :> FL p) C(x y)                -- ^"left" and "right" results
> +            -> ((FL p :> FL p :> FL p) C(x y))      -- ^"left", "middle" and "right"
>  
>  -- optimise by using an accumulating parameter to track all the "right" patches that we've found so far
>  partitionFL' :: Commute p
> hunk ./src/Darcs/Patch/Permutations.hs 52
>               => (FORALL(u v) p C(u v) -> Bool)
> -             -> RL p C(x z)  -- the "right" patches found so far
> -             -> FL p C(z y)
> -             -> (FL p :> FL p) C(x y)
> +             -> RL p C(a b)  -- the "middle" patches found so far
> +             -> RL p C(b c)  -- the "right" patches found so far
> +             -> FL p C(c d)
> +             -> ((FL p :> FL p :> FL p) C(a d))
>  
> hunk ./src/Darcs/Patch/Permutations.hs 57
> -partitionFL keepleft ps = partitionFL' keepleft NilRL ps
> +partitionFL keepleft ps = partitionFL' keepleft NilRL NilRL ps
> +
> +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
>  
> hunk ./src/Darcs/Patch/Permutations.hs 70
> -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
>  
>  -- |split an 'RL' into "left" and "right" lists according to a predicate, using commutation as necessary.
>  -- If a patch does satisfy the predicate but cannot be commuted past one that does not satisfy
> 

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9

Hi Florent, this patch was marked amend-requested, but it's not clear
what amended was requested.  Any ideas what's up?  Thanks!

Sorry to elbow my way in, but I think we're anxiously waiting on this
one for the Darcs 2.5 alpha so I'm going to try and get it done today.

On Mon, Jun 07, 2010 at 20:06:18 +0000, Petr Ročkai wrote:
> Mon Jun  7 20:48:49 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Haddock merge2FL and fastRemoveFL in Patch.Depends.

> Mon Jun  7 20:50:41 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Extend the issue1014 test to check that named patches are not duplicated.

Pushed in my first review from 2010-06-08

> Mon Jun  7 20:50:10 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Extend the get test to cover --context interaction with tags.

Applied, thanks!

> Mon Jun  7 20:49:34 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Use merge2FL instead of plain merge in tentativelMergePatches.

Applied, thanks!

> Mon Jun  7 21:59:12 CEST 2010  Petr Rockai <me@mornfall.net>
>   * Make partitionFL do a 3-way split, and detect commutation bugs in Depends.

More review later

We also talked about this bundle a little bit on IRC
  http://irclog.perlgeek.de/darcs/2010-06-23#i_2471430

To sum, the context to this patch bundle is that the recent NewSet works
introduces some silent-but-deadly situations:

 (A) We no longer notice the anomalous situation where two different
     patches have the same patchinfo.  This sometimes arises when you
     split a CVS repository into two Darcs repositories and then try
     to merge them back together in Darcs, eg. with nofib and GHC
     (because CVS does not have atomic commits, but it lets you recycle
     the commit message across different files)

 (B) The issue1014 test no longer complains, but now instead of crashing
     it causes your history to have TWO instances of the same patch
     (turning your patchset into an unfortunate patchbag)

The game here is to attempt to resolve (A) and try to prepare for a
future resolution of (B); so two independent patches which can be
applied independently of each other.

Haddock merge2FL and fastRemoveFL in Patch.Depends.
---------------------------------------------------
> +-- | Merge two FLs (say L and R), starting in a common context. The result is a
> +-- FL starting in the original end context of L, going to a new context that is
> +-- the result of applying all patches from R on top of patches from L. This
> +-- version also correctly handles duplicate patches.

While trying to review the patch below, I found myself having lots of
little questions about how merge2FL relates to mergeFL, which Petr
clarified.  I'll be following up with a haddock patch of my own, which
Petr has acked on IRC:

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=26477#a26477

Use merge2FL instead of plain merge in tentativelMergePatches.
--------------------------------------------------------------
As above, this patch does not actually have any effect; it's merely
rearranging the furniture in anticipation for future work on issue1014.

>  Ignore-this: 9fde612f399cab5553e9cf57e0764685
> hunk ./src/Darcs/Repository/Merge.hs 58
>  tentativelyMergePatches_ mc r cmd opts usi themi =
>    do let us = mapFL_FL hopefully usi
>           them = mapFL_FL hopefully themi
> -     _ :/\: pc <- return $ merge (progressFL "Merging them" them :\/: progressFL "Merging us" us)
> +     Sealed pc <- return $ merge2FL (progressFL "Merging them" usi) (progressFL "Merging us" themi)

We switch from merge to merge2FL.

Notes with thanks to Petr:

- this involves flipping the order of arguments simply because the two
  functions have different conventions

- merge2FL should not be confused with mergeFL.  Merge2FL does this
  extra work of knocking out patches that share a patchinfo, which will
  be important in the future when we try to fix issue1014 (did anyone
  else that the new post 2008 Darcs team has been starting to wade into
  the core yet?)
  
- this actually has no effect because the patches with identical
  patchinfo will already been filtered out in findCommonAndUncommon
  But in future work, that may change...

The rest of this patch is just using hopefully because we're now
manipulating PatchInfoAnd (Hopefully captures the business of partial
repositories, if I understand correctly, Kudos to whoever haddocked it!
It made reading things a lot faster.)

> -     anonpend <- anonymous (fromPrims pend)
> +     anonpend <- n2pia `fmap` anonymous (fromPrims pend)
>       pend' :/\: pw <- return $ merge (pc :\/: anonpend :>: NilFL)

> -     let pwprim = joinPatches $ progressFL "Examining patches for conflicts" $ mapFL_FL patchcontents pw
> +     let pwprim = joinPatches $ progressFL "Examining patches for conflicts" $
> +                                mapFL_FL (patchcontents . hopefully) pw

> -     have_unrecorded_conflicts <- checkUnrecordedConflicts opts pc
> +     have_unrecorded_conflicts <- checkUnrecordedConflicts opts $ mapFL_FL hopefully pc

Extend the get test to cover --context interaction with tags.
-------------------------------------------------------------
> +cd temp1
> +darcs tag -m tt
> +echo x > x
> +darcs rec -lam "x" x
> +darcs changes --context > my_context
> +cd ..
> +
> +rm -rf temp2
> +darcs get temp1 --context="${abs_to_context}" temp2
> +darcs changes --context --repo temp2 > repo2_context
> +diff -u ${abs_to_context} repo2_context

Here we test for the case where the context file contains a tag (but not
as its most recent patch).  Seems to make sense.

Make partitionFL do a 3-way split, and detect commutation bugs in Depends.
--------------------------------------------------------------------------
I hope to review this after lunch or failing that, tomorrow.

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9

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@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"
  http://wiki.darcs.net/Troubleshooting#bug%20in%20get_extra%20commuting%20patch
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?

WRONG!

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

Eric

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

Only the 'Extend the get test to cover --context interaction with tags.'
test fails (which makes sense, since it's testing issue1865).  

I've requested that Petr either break it out into a separate test case
or (come to think of it), just throw on another patch marking the get.sh
test as failing.  At his discretion...

Meanwhile, I'm marking this accepted because I don't have the heart to
do otherwise (after the saga).  I hope that doesn't cause confusion in
the long run...

Op woensdag 23 juni 2010 17:24 schreef Eric Kow:
>  l1     l2    ((%     r3     r4))   l5.3   l6  (case iii!)

Isn't that a case iv? l5.3 can't even commute past the right bubble because r3 
is in the right bubble. Just checking if I understand...

Reinier

On Sun, Jun 27, 2010 at 13:29:26 +0200, Reinier Lamers wrote:
> Op woensdag 23 juni 2010 17:24 schreef Eric Kow:
> >  l1     l2    ((%     r3     r4))   l5.3   l6  (case iii!)
> 
> Isn't that a case iv? l5.3 can't even commute past the right bubble because r3 
> is in the right bubble. Just checking if I understand...

Hmm, yes, I think you're right and I hope this was a mere think-o
(circumstantial evidence: case iv is the exciting case, hence the
exclamation mark)

An example of a case iii would be a subsequent l7.3
Bubbles, bubbles, everywhere

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

Note that one confusing notational point is that the (case foo) step means
"what next" and not "how did we get here?"

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9