Hi, Ganesh Sittampalam <[email protected]> writes:
[snip tool changes, which look OK to me] [snip import/export/copyright] > hunk ./src/Darcs/Patch/Permutations.hs 237 > sloppyIdentity NilRL = IsEq > sloppyIdentity (x:<:xs) | IsEq <- sloppyIdentity x = sloppyIdentity xs > sloppyIdentity _ = NotEq > + > +-- |CommuteFn is the basis of a general framework for building up commutation > +-- operations between different patch types in a generic manner. > Unfortunately > +-- type classes are not well suited to the problem because of the multiple > possible > +-- routes by which the commuter for (FL p1, FL p2) can be built out of the > +-- commuter for (p1, p2) - and more complicated problems when we start > building > +-- multiple constructors on top of each other. The type class resolution > machinery > +-- really can't cope with selecting some route, because it doesn't know that > all > +-- possible routes should be equivalent. > +type CommuteFn p1 p2 = FORALL(x y) (p1 :> p2) C(x y) -> Maybe ((p2 :> p1) > C(x y)) > + > +-- |Build a commuter between a patch and itself using the operation from the > type class. > +selfCommuter :: Commute p => CommuteFn p p > +selfCommuter = commute Ok, clear. > +commuterIdRL :: CommuteFn p1 p2 -> CommuteFn p1 (RL p2) > +commuterIdRL _ (x :> NilRL) = return (NilRL :> x) > +commuterIdRL commuter (x :> (y :<: ys)) > + = do ys' :> x' <- commuterIdRL commuter (x :> ys) > + y' :> x'' <- commuter (x' :> y) > + return ((y' :<: ys') :> x'') I always mix up FL and RL (and more importantly their constructors), but anyway, this should lift a commuter on p1 and p2 to a commuter on p1 (RL p2) (the type signature says so much). I can't be trusted to understand in which order an RL is supposed to apply and on which side the end is written, but as far as I can tell, the function should be correct if the witnesses match up. Maybe monad is used to propagate commutation failures -- any single failure fails the whole operation. > +-- |Partition a list into the patches that commute with the given patch and > those that don't (including dependencies) > +partitionConflictingFL :: (Commute p1, Invert p1) => CommuteFn p1 p2 -> FL > p1 C(x y) -> p2 C(x z) -> (FL p1 :> FL p1) C(x y) > +partitionConflictingFL _ NilFL _ = (NilFL :> NilFL) > +partitionConflictingFL commuter (x :>: xs) ys = > + case commuter (invert x :> ys) of > + Nothing -> case commuteWhatWeCanFL (x :> xs) of > + xs_ok :> x' :> xs_deps -> > + case partitionConflictingFL commuter xs_ok ys of > + xs_clean :> xs_conflicts -> xs_clean :> (xs_conflicts > +>+ (x' :>: xs_deps)) > + Just (ys' :> _) -> > + case partitionConflictingFL commuter xs ys' of > + xs_clean :> xs_conflicts -> (x :>: xs_clean) :> xs_conflicts It should be probably noted that "ys" is actually treated as an atomic entity, although its name suggests it is compound (which in practice it is, but that's probably irrelevant from the POV of this function). We try to commute inversions of patches in "them" (x :>: xs) past "ys" -- if that works out, all is good, we copy the commuted inversion into the "clean" portion of the output and proceed with the rest. If the commute fails (the Nothing branch), we use commuteWhatWeCanFL to get rid of the failing "x" and all its dependencies -- tacking them straight into the "conflicted" part of the output of partitionConflictingFL. We proceed to work on the part of "them" (i.e. x :>: xs) that does not depend on x. Overall, it seems right that the patches are partitioned into two FL's, first for patches whose inverses commute past "ys" and the second for patches that don't. Now I just need to figure the inversions... "ys" is a patch (RL) we have and there are two patches, x :>: y :>: NilFL that the remote repo has. Now the usual merge could say (it should be symmetric, but the above seems to use this variant): common :>: x :>: y :>: invert y :>: invert x :>: ys and then try to commute ys past the two inversions. So it seems right that we try to commute past inversions, and we do it in the order in which the merge would do them (first x then y), so all set and good. [snip import/export business] > hunk ./src/Darcs/SelectChanges.hs 653 > -> (FL p :> FL p) C(x y) > tp_patches (x:>y) = mapFL_FL tpPatch x :> mapFL_FL tpPatch y > > +filterOutConflicts :: RepoPatch p > + => [DarcsFlag] > + -> RL (PatchInfoAnd p) C(x r) > + -> Repository p C(r u t) > + -> FL (PatchInfoAnd p) C(x z) > + -> IO (Bool, Sealed (FL (PatchInfoAnd p) C(x))) > +filterOutConflicts opts us repository them > + | SkipConflicts `elem` opts > + = do let commuter = commuterIdRL selfCommuter > + pend <- fmap n2pia . (anonymous . fromPrims) =<< unrecordedChanges > [] repository [] > + them' :> rest <- return $ partitionConflictingFL commuter them > (pend :<: us) > + return (check rest, Sealed them') > + | otherwise > + = return (False, Sealed them) > + where check :: FL p C(a b) -> Bool > + check NilFL = False > + check _ = True Assuming correctness of partitionConflictingFL, this seems about right. The "them" patches are commuted, one by one (by partitionConflictingFL) through the composition of "us" (which ought to be the patches that we have but the remote repo does not -- in the pull situation) and the unrecorded changes in the working copy. Any failed commutes there would normally translate to conflicts. The (commuterIdRL selfCommuter) is used to "atomically" commute a patch past a the (pend :<: us) sequence -- it's all or nothing, according to commuteIdRL definition above. I think the patch is good to go, I'll just run it through testsuite and witnesses tomorrow out of pure paranoia and then push (bar any objections). (This is a digression, but: I do think that we could benefit from clearer and more idiomatic terminology for the patch sequences -- I *think* it works to imagine an RL as a stack and and FL as a "normal" list... when I was toying around with these things, it also helped me to actually write RLs with their head to the right instead to the left as darcs does -- so that patches always apply from left to right as written in the code, but can be popped/pushed on different ends, depending on orientation of the list... but I guess this is all matter of different intuitions...) Yours, Petr. _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
