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 <[email protected]> > * 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
signature.asc
Description: Digital signature
_______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
