darcs

Patch 1641 document class Merge, add properties, add and use naturalMerge

Title document class Merge, add properties, add and use naturalMerge
Superseder Nosy List bf
Related Issues
Status accepted Assigned To bf
Milestone

Created on 2018-02-08.00:47:04 by bf, last changed 2018-04-03.15:23:57 by gh.

Files
File name Status Uploaded Type Edit Remove
added-naturalmerge-to-darcs_patch_merge.dpatch bf, 2018-02-08.00:47:04 application/x-darcs-patch
See mailing list archives for discussion on individual patches.
Messages
msg19856 (view) Author: bf Date: 2018-02-08.00:47:04
2 patches for repository http://darcs.net/screened:

patch c7d071a3ed21a93aff34a3d80d2d9276150f6081
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Oct 29 16:51:25 CET 2017
  * added naturalMerge to Darcs.Patch.Merge
  
  This is the simple, non-conflicting merge that works by inverting one
side,
  commuting, and then re-inverting. Used in the instances of Merge for
  RepoPatchV1 and RepoPatchV2.

patch 6de79c9e117a6dce4ccdf33255d8cd987d7c0933
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Oct 29 18:50:36 CET 2017
  * documented class Merge and added properties
Attachments
msg19859 (view) Author: gh Date: 2018-02-08.19:05:23
So, what was wrong with elegantMerge, and what is naturalMerge good for?

I see that naturalMerge is the same as elegantMerge, but without the
following line:

 guard $ unsafeCompare p1o p1 -- should be a redundant check


So why the name change?
msg19860 (view) Author: bf Date: 2018-02-09.09:41:04
They are identical. This is a refactor and a rename.

The main point is to factor it into Darcs.Patch.Merge, since it can be
defined on abstract patches (see the class constraints). There is no
point in duplicating it in D.P.V1 and D.P.V2 (where it appeared inlined).

It is an important and very general concept and IIRC this operation is
referred to as "natural merge" in most of the patch theory work.
msg19875 (view) Author: gh Date: 2018-02-10.19:49:35
Alright.

Probably now is the best moment to include the properties
prop_mergeSymmetric and prop_mergeCommute in the testsuite before we
forget about them.
msg19891 (view) Author: gh Date: 2018-02-16.15:51:17
Could you do it Ben? :-D
msg19893 (view) Author: bf Date: 2018-02-16.19:20:57
I should have added that this is a bit of work in progress. I assume
these properties are tested somewhere. I haven't looked yet. Feel free
to disregard the patch or mark it as follow-up-requested or whatever.

Generally speaking, I think it is a bad idea to have all the properties
inside the harness. They belong to the classes and serve more than just
testing, they are an important part of the documentation. OTOH, the test
code is pretty much inscrutable. Nobody in his right mind would look 
there for properties of a class.

It would be a good idea to find the places in the testsuite where these
properties are tested and replace the code there with an import from
D.P.Merge. I'll probably take this up at some time but not right now.
msg20100 (view) Author: gh Date: 2018-04-03.15:23:56
I had another look at that patch and I think it is an improvement. It
basically factorizes a merge case that should not depend on the
particular implementations of RepoPatchV1 or RepoPatchV2.

To summarize, the RepoPatchV1 code goes from:

~~~
actualMerge (p1 :\/: p2) = case elegantMerge (p1:\/:p2) of
 ....

-- from a common starting context @wX@.
elegantMerge :: PrimPatch prim
             => (RepoPatchV1 prim :\/: RepoPatchV1 prim) wX wY
             -> Maybe ((RepoPatchV1 prim :/\: RepoPatchV1 prim) wX wY)
elegantMerge (p1 :\/: p2) = do
  p1' :> ip2' <- commute (invert p2 :> p1)
  p1o :> _    <- commute (p2 :> p1')
  guard $ unsafeCompare p1o p1 -- should be a redundant check
  return $ invert ip2' :/\: p1'
~~~
  
to:

~~~
actualMerge (p1 :\/: p2) = case naturalMerge (p1:\/:p2) of
 ...
 
-- | The natural, non-conflicting merge.
naturalMerge :: (Invert p, Commute p)
             => (p :\/: p) wX wY -> Maybe ((p :/\: p) wX wY)
naturalMerge (p :\/: q) = do
  q' :> ip' <- commute (invert p :> q)
  -- TODO: find a small convincing example that demonstrates why
  -- it is necessary to do this extra check here
  _ <- commute (p :> q')
  return (q' :/\: invert ip')
~~~

And RepoPatchV2 goes from:

~~~
    merge (x :\/: y)
        | Just (y' :> ix') <-
            commute (invert (assertConsistent x) :> assertConsistent y)
        , Just (y'' :> _) <- commute (x :> y')
        , IsEq <- y'' =\/= y =
            assertConsistent y' :/\: invert (assertConsistent ix')
        -- If we detect equal patches, we have a duplicate.
        | IsEq <- x =\/= y
        , n <- commuteOrAddToCtx (invert x) $ non x =
            Duplicate n :/\: Duplicate n
~~~

To:

~~~
    merge (x :\/: y)
        -- First try the natural (non-conflicting) merge.
        | Just (y' :/\: x') <-
            naturalMerge ((assertConsistent x) :\/: (assertConsistent y))
              = assertConsistent y' :/\: assertConsistent x'
        -- If we detect equal patches, we have a duplicate.
        | IsEq <- x =\/= y
        , n <- commuteOrAddToCtx (invert x) $ non x =
            Duplicate n :/\: Duplicate n

-- | The natural, non-conflicting merge.
naturalMerge :: (Invert p, Commute p)
             => (p :\/: p) wX wY -> Maybe ((p :/\: p) wX wY)
naturalMerge (p :\/: q) = do
  q' :> ip' <- commute (invert p :> q)
  -- TODO: find a small convincing example that demonstrates why
  -- it is necessary to do this extra check here
  _ <- commute (p :> q')
  return (q' :/\: invert ip')
~~~

Accepted.
History
Date User Action Args
2018-02-08 00:47:04bfcreate
2018-02-08 19:05:23ghsetmessages: + msg19859
2018-02-09 09:41:04bfsetmessages: + msg19860
2018-02-10 19:49:35ghsetmessages: + msg19875
2018-02-16 15:51:17ghsetmessages: + msg19891
2018-02-16 19:20:57bfsetmessages: + msg19893
2018-02-24 17:41:50bfsetstatus: needs-screening -> followup-requested
assignedto: bf
2018-04-03 15:23:57ghsetstatus: followup-requested -> accepted
messages: + msg20100