Patch 1730 add RepoPatchV3 aka camp conflictors (and 3 more)

Title add RepoPatchV3 aka camp conflictors (and 3 more)
Superseder Nosy List bf
Related Issues
Status followup-in-progress Assigned To

Created on 2018-09-15.10:35:55 by bf, last changed 2019-02-14.08:27:19 by bf.

File name Status Uploaded Type Edit Remove
add-some-functions-we-need-for-v3-to-darcs_patch_ident.dpatch bf, 2019-02-14.08:24:56 application/x-darcs-patch
patch-preview.txt bf, 2019-02-14.08:24:56 text/x-darcs-patch
unnamed bf, 2019-02-14.08:24:56 text/plain
See mailing list archives for discussion on individual patches.
msg20312 (view) Author: bf Date: 2018-09-15.10:35:50
This is my V3 branch, squached to a few (large) patches.

I will not screen it yet but I have uploaded it to
https://hub.darcs.net/bf/darcs-bf-v3, review at your leisure.

The addition of the V3 stuff to the test suite is unfortunately mixed with a
number of refactoring and cleanup changes there. If this hurts review I am
willing to spend some effort to separate them out.

4 patches for repository http://darcs.net/screened:

patch 4d3f3b0d8738657b041fbf49cd84881254a799fd
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Sep 15 10:56:21 CEST 2018
  * add class IdEq2 to Darcs.Patch.Ident
  This allows a faster equality test for FLs of patches with identity.

patch b40a076b8098ae0c6b34748d1c4d0c7ccfaf59ed
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Sep 15 10:53:07 CEST 2018
  * add some functions we need for V3 to Darcs.Patch.Ident

patch f6f36653b6567ef844d231db2b1b134349d5a684
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Sep 15 09:50:19 CEST 2018
  * add RepoPatchV3 aka camp conflictors

patch 802a2f2a075a8c7aeb0d85ad9306c9b3c68e8a71
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Sep 15 10:06:22 CEST 2018
  * add V3 stuff to the test suite (quickcheck tests only)
msg20456 (view) Author: bf Date: 2018-11-12.21:00:21
This patch will most probably no longer apply cleanly. As I have 
explained on the list, I am exploring the possibility of turning this 
into a pure optimization for V1 Mergers, getting rid of prim patch 
identifiers, and obviating the need for a new and incompatible patch 
msg20627 (view) Author: bf Date: 2019-01-23.21:38:52
This is a literal copy of my email to @darcs-devel, posted here for

As mentioned in my comments to http://bugs.darcs.net/issue2614 it is now
clear that we cannot solve the inconsistencies of the existing darcs
patch formats using "merge-by-value" as this leads to a loss of
permutivity. The only solution is to move forward toward
RepoPatchV3/Camp which is based on /named/ prim patches. These are
wrappers around our current prim patch types that add an identifier
which consists of the hash of the meta data of the named patch to which
they belong, together with a counter to distinguish between the several
prims inside a named patch (assigned when it is recorded). The counter
would not be strictly necessary to get the theory right, but adding it
makes many of the operations on V3 patches a lot more efficient:
equality of named prim patches in the same (pre or post) context reduces
to equality of their identifiers; we can also define an Ord instance and
use Data.Set to store e.g. the set of conflicting (contexted) patches in
a Conflictor.

It is important to note, however, that when we work with prim patches
directly, i.e. outside the implementation of RepoPatchVX, we usually
want to handle the underlying unnamed prim patches: unrecorded changes
and rebase fixups are not part of a Named patch, they are anonymous.
Thus I believe it is best to let (PrimOf p) remain the unnamed prim type
underlying a RepoPatch, even for RepoPatchV3.

The major stumbling block to the integration of named prim patches (i.e.
prim patches with identifiers) into the class based patch interfaces is
the class FromPrim with its fromPrim method to construct a patch of type
p out of a prim patch of type (PrimOf p). Named prims cannot have
instances for that class, at least not cleanly, because to construct a
named prim we need the ingredients for the identifier.

I have been working on minimizing the use of fromPrim throughout the
code base. After a few rounds of refactorings I arrived at a situation
where the overloaded fromPrim is really only needed for the rebase
implementation and --for the time being-- the functions anonymous and
infopatch from Darcs.Patch.Named (which now take prims as input). (Not
counted here are uses of fromPrim inside the implementation of
RepoPatchV1 and RepoPatchV2 as these do not affect the general RepoPatch
API.) The Named constructor infopatch will need to be adapted to create
appropriate identifiers for the prims it gets passed.

Problematic are the anonymous constructor and the remaining uses of
fromPrim inside the rebase implementation. The use case here is the
same: to commute/merge prims with Named patches. I have been thinking of
using a really dirty hack here: randomly generate (hopefully) unique
prim patch identifiers and wrap that with unsafePerformIO. This would
allow us to lift an arbitrary prim to a RepoPatchV3. But note that the
implementation of RepoPatchV3 stores prim patches /with/ identifiers
inside conflictors; if a conflictor stores a reference to some anonymous
prim patch this would be very bad!

So we can do that only if we can guarantee that the identifiers we
conjured out of thin air are never stored inside a regular Named patch
of the repository. In particular, we should never use merge with
anonymously created Named patches and then store the resulting patches
in the repo!

I believe that for the rebase patch this will work because the only way
to leave the rebase patch is via unsuspend and that should flatten out
all existing conflictors (using effect) and thus never create a patch
that contains a Conflictor. I have not yet investigated all uses of the
anonymous constructor, so I can't say yet whether these may prove critical.

Update: I have checked all uses of anonymous and I believe they are all
safe. Will send a preparation bundle for screened with the FromPrim
refactors and another one to update the V3 implementation, with the
first steps taken towards full integration.
msg20654 (view) Author: bf Date: 2019-02-14.08:24:56
This bundle superseded the earlier one. It contains full integration of the
new patch format. All tests pass, but one or two minor features are not yet
implemented, see below for details.

I made no change whatsoever to the core algorithms (commute, merge, etc)
relative to the patch bundle I sent previously, only a minor refactor with
regard to the way PrimPatchIds are embedded in the representation.
Particularly, the NamedPrim wrapper is now fully hidden inside the
RepoPatchV3 implementation i.e. PrimOf (RepoPatchV3 prim) ~ prim ~ whatever
the underlying (unnamed) prim patch format is (i.e. usually V1).

The last big hurdle was to implement resolveConflicts. For this to work with
V3 I had to change the type of that method and this required a certain
amount of changes downstream. In particular, we have to pass the whole
history whenever we merge patches because the conflict resolution for V3
requires that. Instead of adding yet another parameter to functions that
already take more parameters than looks healthy, I chose to wrap all passed
patches as a (Fork common us them), where common is a PatchSet starting at
the Origin. This works out nicely due to the laziness of PatchSets, which
are only evaluated (and read from disk) as far as needed. The algorithm for
conflict resolution is documented in detail in the code.

A rather dirty hack makes this algorithm for resolveConflicts work when
unsuspending patches. The function forceCommutePrim (applied to the fixups
of a patch and the suspended patch itself) violated the assumption that a
patch we conflict with must be found somewhere in the context. To fix that
the patches contained in the resulting WDDNamed are now prefixed with @fixup
:>: invert fixup@.

One thing I am planning to do but haven't begun yet is to re-implement the
function that produces the actual conflict markup (mangleUnravelled) for
NamedPrims, taking advantage of the PrimPatchIds to improve the markup so it
includes the hashes of the originating named patches.

Not yet implemented is conversion from earlier formats to darcs-3.

Also not yet implemented is check/repair: I am using the default methods
that are just stubs that don't do anything interesting. The problem here is
that we cannot lift an operation on a list of prims to a list of NamedPrims
if this involves adding or removing prims, which is what the implementation
for Prim.V1 does. This needs to be refactored to handle one prim at a time
which I haven't done yet.

Similarly, showing hunks with surrounding context for v3 patches is
disabled for now. The code that shows a series of hunks with context is a
mess; it bypasses showContextPatch and re-implements showing for V1 prims.
This needs to be cleaned up first.

25 patches for repository http://darcs.net/screened:

patch 201588ce705f87b17bcb800c113b91d75d3a450e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 16:50:41 CET 2019
  * add some functions we need for V3 to Darcs.Patch.Ident

patch 2ab2d6ea7d3b4299dee37bc81e36fa35bc9c035d
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:45:13 CET 2019
  * add RepoPatchV3 aka camp conflictors

patch 41d9f81cb0bb0c89d3589440cd2959d0b5df7361
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:45:38 CET 2019
  * add V3 stuff to the test suite (quickcheck tests only)

patch 39e45329fa32f4a682ba1e557ee756a7a1d74327
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * renamed fromPrim to fromAnonymousPrim

patch 9e6f89e0479a740cf4b7ff28150f5f9d284cb400
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * add prim patch identifier when constructing Named patches
  This re-adds method fromPrim to class FromPrim, this time with additional
  parameters to construct the identifier. This is then used in function
  infopatch instead of fromAnonymousPrim.

patch d0bbd4aa6e41c41459f09e64239d74f2e64d5850
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * move Darcs.Patch.V3.Prim to Darcs.Patch.Prim.Named
  This is actually a fully generic wrapper for any PrimPatch type and
  technically not tied to V3.

patch 3a797b9fc225df6dbb031b29307f4e30c891fa6c
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * add new Darcs3 format option

patch f6b41d01a4487e2d5004f5175113d9dfd90ecc98
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * trivial refactor in D.R.Create

patch 0107cb750c63795b3cd1fb17f94478102ab7dc5d
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * allow runnign the test scripts with darcs-3 format

patch 47609c8e55be5be81dfed655514762c51140f343
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb  8 17:46:49 CET 2019
  * adapt test skip based on repo format
  Now that we have three formats, we can no longer assume that skip-formats
  darcs-1 implies test is run only for darcs-2.

patch 4e79a8698e04ff031c1f3697114777357ce26ac8
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Feb  9 14:43:32 CET 2019
  * fix in the QC generator for prim patch IDs

patch 2c68e35e4a324ece160ff5e50bdfdaa21c3491ec
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Feb  9 14:51:59 CET 2019
  * fix instance MightBeEmptyHunk for NamedPrim
  Property effectPreserving fails for Prim.V1 empty hunks, and so it does for
  its NamedPrim wrapper.

patch 1b723556f68d6ea9fcc71b9348c74a2c2163a4d5
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Feb  9 13:27:16 CET 2019
  * separate class Summary out from class Conflict
  This prepares a change in the type and meaning of resolveConflicts but makes
  sense independently. The method conflictedEffect is used only to generate a
  summary for potentially conflicted patches and thus has been moved to the
  new class Summary. The class Conflict gets a new method isConflicted which
  just returns whether a patch is conflicted or not.
  Incidentally this gets rid of a number of unneeded instances for Conflict
  with nonsense/dummy implementations for resolveConflicts (such as for Named,
  PatchInfoAnd, RebaseChange, and RebaseSelect).

patch 160164bb4f50312093ab83c721488caea21ffe8e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Feb  9 17:10:00 CET 2019
  * add Darcs.Util.Graph
  This contains an efficient algorithm to determine maximal independent sets
  of an undirected graph.

patch d61e91e261ee659ff98225948038258dc7df0a34
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb 10 13:43:32 CET 2019
  * fix a typo in a comment

patch fffd7cd29873f3c9f5529c79bb859ac86e51887a
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb 10 19:28:06 CET 2019
  * fix cloning of darcs-3 format repos

patch 7cd237bf9a779540fe19c332e759e359a1b4cb0d
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb 10 21:48:03 CET 2019
  * bugfix in instance ShowContextPatch for NamedPrim

patch dc879f6671f4dbff633ebeeb635a83e8d05337ac
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb 10 23:09:51 CET 2019
  * hack: disable showContextSeries for darcs-3 format
  The code (in Darcs.Patch.Viewing) that implements showContextSeries messily
  re-implements showing for FLs of primitive patches (hunks in particular),
  circumventing the ShowPatchBasic instance. This means that it cannot take
  prim patch IDs into account since these are added to prim patches as a
  wrapper. This would not be a big problem for display but it is one when we
  use showContextPatch to create a patch bundle because it means that hunks
  are stored without the prim patch ID and thus cannot be read.
  The temporary "fix" here is to disable showContextSeries by adding a new
  ListFormatV3, until the context showing code is cleaned up to pass the
  correct prim show function down into showContextSeries.

patch dcceaa03b5ae8ce0c7670e056a1f6ef9eec8aa16
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 12 18:17:39 CET 2019
  * show the PrimPatchId only ForStorage, not ForDisplay
  The PrimPatchId is not useful to the user and clutters up the output when
  --verbose is in effect. It also allows more test scripts to pass without
  having to adapt them.

patch f6fa434b182eb283aec29cc5ea8a077cb2c70923
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 12 18:21:32 CET 2019
  * fix expected output in look_for_moves test for darcs-3
  The place where we have to adapt the test is when we test teh output of
  'darcs log --machine-readable' which uses the ForStorage format option, so
  we have to expect the hash line before the content.

patch 1850f72913a5057fb12bbfeeff5b5e93ce278c37
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 12 18:36:09 CET 2019
  * tests/pull.sh: expect the correct behavior for darcs-3, too

patch d22ee446187b4954744092a410530b23d2866aad
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Feb 13 09:23:01 CET 2019
  * disable repair tests when format is darcs-3
  Repairing currently means that we add or drop prims from a sequence, and we
  cannot lift that to NamedPrims. Doing this right requires considerable
  refactors to the Repair interface(s), so this is postponed for now.

patch e46cc62d1d40c0f98d33b7d850efcc172d3b6be6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Feb 13 18:20:58 CET 2019
  * fix rebase unsuspend for v3 with a dirty hack
  See comment in the code for the why and how.

patch dcb2738aa6f37a04a803b5b92e7c000f22ecd32e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Feb 13 18:24:09 CET 2019
  * change the type of resolveConflicts
  It now gets two RLs of patches as input and produces a simple (not nested)
  list of resolutions. The change in the input type(s) has been done because
  otherwise a RepoPatchV3 cannot correctly implement resolveConflicts, which
  requires that we know the transitive set of conflicting patches for each
  conflict. But a V3 conflictor contains only the patches that directly
  conflict. The separation into two input RLs is so that we can still resolve
  only the conflicts inside a (trailing) segment of all patches in a repo,
  which is how we call it when merging patches.
  There are no longer instances of class Conflict for RLs and FLs. Instead, we
  offer the stand-alone function combineConflicts and use that in the
  implementation of resolveConflicts for RepoPatchV1/2.
  The change in the result type is just a cleanup: instead of adding the
  mangled resolutions as a first element and then taking the head (in
  standardResolution) we now replace the inner list with the mangled version.
  Passing the full context to resolveConflicts requires a number changes
  downstream. This is not strictly needed for V1/V2 which ignore the context,
  so we could pass undefined, but we need to make this change for V3 anyway.
  Instead of adding yet another parameter to all functions involved, we now
  pass a (Fork common us them) which cleans up type signatures (and
  incidentally some of the code, too).

patch 1a5c552ad9c8192fc3254f3e3dfcdd7c1ee525dd
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Feb 13 20:14:19 CET 2019
  * implement resolveConflicts for RepoPatchV3
Date User Action Args
2018-09-15 10:35:55bfcreate
2018-11-12 21:00:22bfsetmessages: + msg20456
2018-11-26 22:42:51ganeshsetstatus: needs-screening -> followup-in-progress
2019-01-23 21:38:53bfsetmessages: + msg20627
2019-02-14 08:24:56bfsetfiles: + patch-preview.txt, add-some-functions-we-need-for-v3-to-darcs_patch_ident.dpatch, unnamed
messages: + msg20654
2019-02-14 08:27:00bfsetfiles: - add-class-ideq2-to-darcs_patch_ident.dpatch
2019-02-14 08:27:14bfsetfiles: - patch-preview.txt
2019-02-14 08:27:19bfsetfiles: - unnamed