I am not screening this one yet, please take a look and tell me if you think
this is a bad idea. With this patch I can successfully push and pull between
the two repos that lemming attached to the ticket (after reverting
unrecorded changes).

This patch breaks the test for issue1879 which is to be expected. Detecting
inconsistencies between repos (this includes malicious patch manipulation)
is a valid goal but I think we should aim for something more reliable. That
is, commute all (supposedly) common remote patches into the same context as
the version in our repo and then compare contents; which would not interfere
with the proposed mitigation for issue2738.

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

patch 3bba990fe96e421f81bb2cf45ece9994d075ce35
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jan 29 13:13:20 CET 2025
  * mitigate issue2738: make merging more robust in the face of V1/V2 commute bugs

  We add a new method robustMerge that is able to handle identical patches by
  returning "null patches" (represented as Nothing2 :: Maybe2), and base the
  generic instance Merge for FLs on that, instead of the plain merge. This
  allows us to keep common patches that cannot be commuted to the tail in the
  "uncommon" branches (in functions like findCommonFL) instead of calling
  error.

Attachments

• mitigate-issue2738_-make-merging-more-robust-in-the-face-of-v1_v2-commute-bugs.dpatch
• patch-preview.txt

I'm still thinking this over (along with your separate email about
commute consistency) but some initial thoughts:

There's no robustMerge instance for `FL` which means that I think
now merge on `FL (FL (Named p))` won't behave the same as merge
on `FL (Named p)`.

I wonder if the implementation could instead be via a merge
instance for `Maybe2 p` or even some special wrapper
`AllowDuplicates p` which behaves the same but whose intended
behavior is clearer. Then just the code that handles "repo merges"
would use the wrapper so the effect would be more tightly scoped.

Also if V1/V2 are the only things to have these bugs maybe we only
need to use this there?

Sorry, I was wrong about merge on FL (FL p) not being the same
as merge on FL p - I now see that once you get to FL you
don't need robustMerge any more because you can just collapse the
list.

Yes, exactly! For sequences we identify Nothing2:>:NilFL with NilFL, which 
is how catMaybes2 gets rid of the Maybe2s.

Following up with an optimized version.

1 patch for repository /home/franksen/src/darcs/screened-with-mitigation-of-issue2738:

patch 697ac0eee2d3606c18fc2081bbf97ceee3945c0e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Jan 31 09:14:57 CET 2025
  * minimize the amount of Maybe2 wrapping and unwrapping in merge for FLs

  This replaces the implementation in terms of the generic mergerFLFL with a
  direct one, at the cost of some (minor) code duplication. The implementation
  uses monadic style with the Identity functor in order to avoid nested case
  expressions.

Attachments

• minimize-the-amount-of-maybe2-wrapping-and-unwrapping-in-merge-for-fls.dpatch
• patch-preview.txt

BTW even though I was wrong about the FL FL thing, I still would
argue for a wrapper type over the new class method approach. It
seems less scary in terms of potential impact.

Could you illustrate (or explain a bit more) what you mean with the 
wrapper type approach? Which patch types do you want to wrap and what 
difference does that make?

Instead of having robustMerge, introduce

newtype AllowDuplicates p wX wY = AllowDuplicates (Maybe2 p wX wY)

with a merge that does what robustMerge does now

Then when we are about to do an operation that requires it, wrap
all our Named/PatchInfoAnds in AllowDuplicates, do the merge,
and unwrap (dropping the Nothing2s).

I see. So, basically, we move the decision whether to do the 
wrapping/unwrapping or not to the call site.

This has a number of drawbacks:

This a much more invasive change. It means we have to find every place where 
we use merge and make a decision. What if we miss one? Or forget about it 
and use the wrong function when making a change in the future?

Also, what about generic functions that are built on merge but also require, 
say, commute or, let's say, displayPatch? Should they now all come in two 
varieties? Or do we also define instances of all these classes for 
AllowDuplicates?

Considering these costs, what exactly are the benefits?

OK - so my idea was based on the mistaken premise that there are only
a few places in the code that actually merge repos via "findCommon"
style logic and therefore we'd just need to change those. However
having dug for myself I realise that's not the case, lots of commands
do it.

My main concern with this change is it's not clear whether it's a
workaround for a bug or a fundamental decision to change merge
semantics.

If it's a workaround for a bug, it feels like it has quite a big
impact on core logic for merging patches. Should it really be
used for V3 for example? Is there some way we could help people
repair repositories instead? (though I suspect not)

If it's a fundamental decision to change merge semantics then
(a) I'd like to think about the other thread some more and
(b) maybe we should do without the forceMerge/merge distinction?

> If it's a workaround for a bug

It is. (I'll say a few more words on that at the end.)

> it feels like it has quite a big impact on core logic for merging patches.

I hope I can convince you that the impact of the change is not as big as you 
make it it out to be. Let's first consider the change to robustMerge and merge 
for FLs.

(1) It does not make any semantic change to patch types that use the default 
implementation of robustMerge. The latter never returns Nothing2 and therefore 
the implementation of merge for FLs should behave identical to the previous 
one. I am willing to add unit tests to make sure this is the case.

(2) For those patch types that do have a custom robustMerge (Named, 
PatchInfoAnd), it changes behavior *precisely* in situations where Darcs 
previously would have crashed due to an error call ("cannot merge identical 
patches").

Second, consider the changes to findCommon*. They potentially impact any patch 
type with an identity, which includes RepoPatchV3 and its internals i.e. named 
prims. But again, the changes are limited to cases which previously were 
handled with an immediate error call, namely "cannot commute common patches" 
and "common patches are not identical". (It should be easy to verify this by 
inspection and I urge you to double-check that.) Thus, for patch types which do 
exhibit commutation consistency, the behavior is unchanged.

> Should it really be used for V3 for example?

I am not 100% happy about this either. If it were not for the stated 
difficulties in engineering it, I would prefer not to. An internal consistency 
check can detect problems even if the test suite for some reason fails to cover 
the particular scenario that triggers it. Given that we are likely to be the 
first to actually use darcs-3 seriously, this may help us to find such a bug 
before we cause damage to other people's repositories.

Anyway, I think we can get the same advantage if, instead of crashing with an 
error call, we merely print a loud warning message when we are about to run 
into any of the relevant cases. Would that be an acceptable compromise?

> Is there some way we could help people repair repositories instead?

I think repairing is possible as long as you know how to do better.

In contrast to the limitations that prevent us from detecting such problems 
early i.e. when we create Mergers / Conflictors / Duplicates, such a repair 
procedure could be given simultaneous access to all affected branches of the 
project. It would also be acceptable if it runs for a very long time, say, a 
few days.

Basically, we'd have to roll back everything up to to some known good state, 
and then re-create the history of records and merges / commutes "in a better 
way" i.e. consistently. For V3, we could hope to find and fix the underlying 
bug, so this might be realistic. But for V1/V2 the inconsistency problem is 
fundamental so I can't see how to "re-create a better history". The best we 
could offer is to convert the whole project to V3. (One more reason to finally 
get my act together and seriously start implementing that!)

> If it's a fundamental decision to change merge semantics

Repeat: It is not. What I wrote about in the other thread, while being inspired 
by this mitigation, is still highly speculative. For instance, I haven't 
(despite some efforts) been able to fix the proof for general permutivity yet. 
And even if we manage to solve all the technical problems in a satisfactory 
manner, I would still say this is an experimental feature for some future new 
patch format.

I think we could constrain the behaviour to V1/V2 patches only by 
also introducing a boolean in the Merge class that we only set to
True for V1/V2. It'd be extra cruft but I think that's justified
if we see this a workaround rather than a fundamental behaviour.

Some follow-up patches. The one of most interest here would be 

  * use robustMerge only if hasInconsistentCommutes

which implements your latest suggestion.

Sorry for the delay, I was being side-tracked searching for alternative ways
to fix issue1879. More on that in another message or ticket.

8 patches for repository /home/ben/src/darcs/darcs-mitigate-commute-bugs:

patch 878e82ef2f2e36598554412a9a4a781839f253b8
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  9 10:26:02 CET 2025
  * rename class law commute-symmetry to commute-self-inverse

patch f41fc8344a8b37abd0507bdfac616b704e954431
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  9 10:26:45 CET 2025
  * add class law commute-consistent

patch 1f945a5deced6f3cf3a873d9a305af960f5a8afe
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  9 10:27:45 CET 2025
  * make findCommonFL do the same as findCommonRL if commute consistency fails

patch 2ca3042ea28dafaeb25457ce51681487241e2b98
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  9 11:05:08 CET 2025
  * use robustMerge only if hasInconsistentCommutes

  We set this new boolean class variable for patch types that exhibit
  inconsistent commutes, namely RepoPatchV1/V2. The higher-level patch types
  Named and PatchInfoAnd inherit it from their ingredients. Thus, robustMerge
  is only used for patch types that require it.

patch 2c5a93640699ef6d27fc2d22a4cb5c605c16fb96
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Jan 31 17:42:18 CET 2025
  * harness: separate properties consistency and permutivity

  This is a complete re-write of the two properties. To reduce clutter and
  make everything more concise and understandable, I made some refactors,
  including a new naming scheme for the patch variables, and support for using
  monadic style with TestResult.

patch 398eb61598fa3457c67874e268fcb35725cf8cf6
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 11 10:03:08 CET 2025
  * mark issue1879-same-patchinfo-uncommon as (again) failing

  This particular sort of inconsistency can no longer be detected by Darcs.

patch 8a4005ccd2e68d63f99d285b21fbff882f3a0edc
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 11 10:02:16 CET 2025
  * rename cons2 to maybeCons in instance Merge FL

patch 8edafc97ffa2b2fb87821b8671b7450b92ed018c
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 11 09:45:15 CET 2025
  * make robustMergeFLFL merge in exactly the same order as mergerFLFL

  This change avoids failure of tests/convert-darcs2.sh where we compare patch
  bundles literally. This failure occurs because RepoPatchV2 uses lists for
  its "set of conflicting Nons" member and does not sort them before
  serialization (Nons do not even have an Ord instance), so equal patches
  (according to Eq2) may have different serializations.

Attachments

• patch-preview.txt
• rename-class-law-commute_symmetry-to-commute_self_inverse.dpatch