5 patches for repository /home/ben/src/darcs/without-v3:

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 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

patch 3a78254c82d906c54ca487b5b383293804e67255
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Feb 15 17:12:23 CET 2019
  * add more detailed comments for some cases of findConflicts

Attachments

• patch-preview.txt
• separate-class-summary-out-from-class-conflict.dpatch
• unnamed

I think it doesn't make much sense to review the main patch

patch 1a5c552ad9c8192fc3254f3e3dfcdd7c1ee525dd
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Feb 13 20:14:19 CET 2019
  * implement resolveConflicts for RepoPatchV3

because in the meantime I have made some pretty extensive changes to
this part. It would be easier to just review the result after applying
my follow-up patches. Should I attach them here or do you prefer I send
them in a separate bundle?

Reviewing the first three preparatory patches should be fine.

Good timing as I'd just been looking at the first two patches :-)

I think attaching them here makes most sense.

On 15/06/2019 09:22, Ben Franksen wrote:
> 
> New submission from Ben Franksen <ben.franksen@online.de>:
> 
> 5 patches for repository /home/ben/src/darcs/without-v3:
> 
> 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).

Looks good. I was wondering whether we should have some properties
linking 'isConflicted' and 'conflictedEffect', but I see that
'isConflicted' is gone in screened anyway.

> 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.

OK. It's not intuitive to me how it helps with conflicts, but no doubt
all will be revealed later.

It would be nice for it to have some unit tests. In an even more ideal
world we'd be getting this from some standard library.

>>   * add Darcs.Util.Graph
>>   
>>   This contains an efficient algorithm to determine maximal independent sets
>>   of an undirected graph.
> 
> OK. It's not intuitive to me how it helps with conflicts, but no doubt
> all will be revealed later.

It will. If you are interested in a (very) high level rationale you
could re-read what I wrote a year ago on the list:
https://lists.osuosl.org/pipermail/darcs-devel/2018-May/018835.html

> It would be nice for it to have some unit tests.

Yes, definitely.

> In an even more ideal
> world we'd be getting this from some standard library.

I did some research but couldn't find anything suitable on hackage. And
you'll have to admit that the module is nicely small and self-contained.

BTW, the original code in the paper was over 1000 lines of extremely
low-level FORTAN. I first wrote a C version, only occasionally checking
with the FORTAN code when the description of the algorithm was unclear.
Then I tested, bugfixed, refactored, and simplified that version several
times and only then started with Haskell. I was quite pleased to find
that in Haskell I could express this all in a handfull of code lines
with practically no loss of efficiency. I could even add the possibility
to disable or enable the two special optimizations independently.

One thing on my todo list (not at the top though) is to add a good
algorithm to calculate connected components to Darcs.Util.Graph because
we need that, too. I am currently doing this with the simple adjacency
list representation I get out of findConflicts which is not optimal.
This function is also quite easy to get wrong, indeed the one in the
patch I sent is buggy :(

This bundle goes on top of the other patch(es) as they are already in
screened.

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

patch 48278049db03d393b304765615bb65ab3061f6e5
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jul 10 20:23:02 CEST 2019
  * fix the function used internally in v3 to merge FLs
  
  It is used to merge non-conflicting FLs into a single alternative for
  conflict resolution. The bug was that we forgot to call findCommonFL and
  thus mergeNoConflicts could fail.

patch 4d5f45cd18be910226b17636663e17dc34601bd7
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jul 10 23:11:29 CEST 2019
  * v3: remove debug stuff and other minor cleanups

patch 93b5c1f0b9ca14d9e1193d60ca14cd9829f1c168
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jul 10 19:19:14 CEST 2019
  * move v3 helper functions idsFL and idsRL to harness

patch 26a5c2acbd18e96890b17250e51a3a6cba6c77a7
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jul 10 23:17:25 CEST 2019
  * v3: fix and restructure conflict resolution
  
  It probably doesn't make much sense to view the diffs here, since I really
  restructured things a lot, re-wrote the documentation comments, and renamed
  and reordered functions.
  
  The main semantic changes are:
  - fixed the 'components' function which was buggy
  - fixed and cleaned up the history traversal to find vertices
  - throw out the no longer needed 'dropDominated'
  - calculate conflicts between vertices freshly
  
  The last point was crucial. In my original version I made the mistake to
  think that we can read off conflicts between vertices, i.e. contexted prims,
  directly from the conflictor. This is only so in the simplest case of two
  conflicting prims. In general it is false: the contexted patch represented
  by a conflictor need not directly conflict with all of the conflicts stored
  in the conflictor. This cannot be so, since e.g. a prim can conflict with a
  conflictor simply because it conflicts with one of the conflicts stored in
  the conflictor. The side-conditions in the commuteNoConflict cases make that
  pretty clear.

Attachments

• fix-the-function-used-internally-in-v3-to-merge-fls.dpatch
• patch-preview.txt
• unnamed

I forgot to should push the additional patches to screened. Doing that 
now.

Sorry, forgot to add this implicit dependency.

1 patch for repository http://darcs.net/screened:

patch 540cc6b05eae4f6b639e00be6439052871f6c8b8
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jun 18 23:25:02 CEST 2019
  * add LambdaCase to default-extensions for the library
  
  I like to use this simple but useful syntactic extension which exists since
  ghc-7.6.1.

Attachments

• add-lambdacase-to-default_extensions-for-the-library.dpatch
• patch-preview.txt
• unnamed

On 15/06/2019 09:22, Ben Franksen wrote:

> 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.

It took me a little while to understand that this was effectively a
shift in level: where previously we were calling the resolveConflicts
instance for RL RepoPatch now we are calling it for RepoPatch. But the
end result seems reasonable/an improvement.

>   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.

OK. I don't find the name particularly intuitive but the comment is
clear enough.

>   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).

This feels like a significant complication (e.g. how does it interact
with lazy repos), but if it's necessary for V3 then I guess we have to
live with it.

> {-
> Keep this code as a reminder that we want to QC test conflict resolution.
> It doesn't work like this anymore, though, we need a full repo. Also should
> do it generically for all patch types i.e. in Darcs.Test.Patch.Properties.Gewneric.

I guess this should at least have a TODO/V3INTEGRATION comment. I'm also
generally in favour of leaving code disabled rather than commented out
so it keeps compiling, but that's not very important in this case as the
code is just an indication of how a future test might look.

The change in the signature of tentativelyMergePatches might be
helpfully accompanied by an update to the comment that describes the
patches and their relationships.

>>   * 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.
> 
> It took me a little while to understand that this was effectively a
> shift in level: where previously we were calling the resolveConflicts
> instance for RL RepoPatch now we are calling it for RepoPatch.

Exactly. It was awfully hard and took lots of experimental changes I had
to throw away before I got to this point. A bit like re-discovering
surgery: you gotta cut exactly this way and then that way and then you
can fit together the pieces without killing the patient...

> But the
> end result seems reasonable/an improvement.

And I think with your refactor of the result data type (which in my
rebased version I took over mostly unchanged) and my further refactors
on top of that the whole interface slowly approaches "understandable for
mere humans".

>>   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.
> 
> OK. I don't find the name particularly intuitive but the comment is
> clear enough.

Which name? combineConflicts? That was just the first thing I could
think of, sorry. Please fix if you have a better one.

>>   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).
> 
> This feels like a significant complication (e.g. how does it interact
> with lazy repos), but if it's necessary for V3 then I guess we have to
> live with it.

Yes, passing the common part around is a bit of complication and it is
unfortunate that we cannot avoid that. I tried to mitigate by passing a
Fork instead of adding yet another parameter.

There is no loss of lazyness, fortunately. Calculating the outermost
layer of the common PatchSet doesn't access patch contents at all and
thus works for lazy repos just as before. We don't even have to read all
inventories, only those after the latest common clean tag. Oh, and
PatchSet2RL is also fully lazy, evaluating nothing until you access its
patches and then only the outermost inventory etc.

I am also convinced that findUncommon and findCommonWithThem could both
be redefined as specializations of findCommonAndUncommon without any
loss of efficiency or laziness.

>> {-
>> Keep this code as a reminder that we want to QC test conflict resolution.
>> It doesn't work like this anymore, though, we need a full repo. Also should
>> do it generically for all patch types i.e. in Darcs.Test.Patch.Properties.Gewneric.
> 
> I guess this should at least have a TODO/V3INTEGRATION comment.

Yes, definitely. I had completely forgotten about this out-commented code.

> I'm also
> generally in favour of leaving code disabled rather than commented out
> so it keeps compiling, but that's not very important in this case as the
> code is just an indication of how a future test might look.

I have written this test a while ago (not yet sent) and it certainly did
uncover some bugs in my conflict resolution code for V3. (So I did not
forget we need the test, just the old code and my comment.) The
commented code can be deleted; I will send that along with the new tests.

BTW, I also added a property that says conflict resolutions are
independent of the ordering of patches; to my astonishment it seemed to
hold up for all 3 RepoPatch types. I investigated and found that indeed
V1 and V2 sort or nubSort the unravelled conflicts. And V3 does that
too, though not by calling nubSort but rather because it gathers them in
a Set to begin with.

> The change in the signature of tentativelyMergePatches might be
> helpfully accompanied by an update to the comment that describes the
> patches and their relationships.

Right, I missed that. Will fix.

Following up on patch review, last point first.

1 patch for repository http://darcs.net/screened:

patch ca145a96c093c5067eed264469241034706d3150
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jul 16 01:23:39 CEST 2019
  * overhaul documentation in Darcs.Repository.Merge
  
  It was slightly out of date after the latest changes to the conflict
  resolution API, which means we now take a complete Fork of both repos as
  argument and pass the common part on to standardResolution. It also did not
  reflect that a while ago we changed the witnesses to make it clear that we
  expect to be in an unmodified repo, that is, we start with the tentative
  state equal to the recorded state.

Attachments

• overhaul-documentation-in-darcs_repository_merge.dpatch
• patch-preview.txt
• unnamed

>>> {-
>>> Keep this code as a reminder that we want to QC test conflict resolution.
>>> It doesn't work like this anymore, though, we need a full repo. Also should
>>> do it generically for all patch types i.e. in Darcs.Test.Patch.Properties.Gewneric.
>>
>> I guess this should at least have a TODO/V3INTEGRATION comment.
> 
> Yes, definitely. I had completely forgotten about this out-commented code.
> 
>> I'm also
>> generally in favour of leaving code disabled rather than commented out
>> so it keeps compiling, but that's not very important in this case as the
>> code is just an indication of how a future test might look.
> 
> I have written this test a while ago (not yet sent) and it certainly did
> uncover some bugs in my conflict resolution code for V3. (So I did not
> forget we need the test, just the old code and my comment.) The
> commented code can be deleted; I will send that along with the new tests.

I think it makes more sense to gather these patches in a separate
bundle, along with other tests I added and one or two that needed fixing.

> patch 93b5c1f0b9ca14d9e1193d60ca14cd9829f1c168
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Wed Jul 10 19:19:14 CEST 2019
>   * move v3 helper functions idsFL and idsRL to harness

> patch 540cc6b05eae4f6b639e00be6439052871f6c8b8
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Tue Jun 18 23:25:02 CEST 2019
>   * add LambdaCase to default-extensions for the library
>   
>   I like to use this simple but useful syntactic extension which 
exists since
>   ghc-7.6.1.



OK (just knocking out easy patches so I have a minimal set
of difficult ones to review in detail)

> patch 1a5c552ad9c8192fc3254f3e3dfcdd7c1ee525dd
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Wed Feb 13 20:14:19 CET 2019
>   * implement resolveConflicts for RepoPatchV3
> 
> patch 3a78254c82d906c54ca487b5b383293804e67255
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Fri Feb 15 17:12:23 CET 2019
>   * add more detailed comments for some cases of findConflicts

OK (mostly obsoleted by following patches)

> patch 48278049db03d393b304765615bb65ab3061f6e5
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Wed Jul 10 20:23:02 CEST 2019
>   * fix the function used internally in v3 to merge FLs

OK

> patch 4d5f45cd18be910226b17636663e17dc34601bd7
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Wed Jul 10 23:11:29 CEST 2019
>   * v3: remove debug stuff and other minor cleanups

OK

> patch 26a5c2acbd18e96890b17250e51a3a6cba6c77a7
> Author: Ben Franksen <ben.franksen@online.de>
> Date:   Wed Jul 10 23:17:25 CEST 2019
>   * v3: fix and restructure conflict resolution

OK - I've read the new code and comments in V3.Core and it makes 
reasonable sense to me, though I haven't thought deeply about all 
the details.

>   go _ _ NilRL NilRL _ = error "autsch, hit the bottom"

This error message may be a bit confusing if anyone hits it :-)

>>   go _ _ NilRL NilRL _ = error "autsch, hit the bottom"
> 
> This error message may be a bit confusing if anyone hits it :-)

:-))

(You are right, of course. OTOH, @error "impossible case"@, of which I
just counted 95 occurrences, isn't any less confusing, just more boring...)