I recently made a mistake (at work) and pushed duplicated patches and a
duplicate tag to a shared repo. Then I cloned --tag with the duplicate
tag, and got a 'fromJust' exception. I have a test script and will
send/push that. I have also tracked the error down to
Darcs.Patch.Match.splitOnMatchingTag, third clause, where splitOnTag
(info p) (PatchSet ts (ps:<:p)) returns Nothing which shouldn't be
possible. Perhaps a regression introduced by a refactor I made to this
code some time ago. Will further investigate and hopefully send a fix.

I tracked it down to this patch:

patch 47da99770d4be412f7d9baed75eb0573a5b18d54
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Sep 14 09:00:22 CEST 2018
  * clean up partitioning functions and export primed versions

I don't understand this: apparently the old and new versions of
partitionRL have different behavior but I fail to comprehend why.

To find out where exactly the mistake is I would like to instrument the
function with debug (trace) output. But it is polymorphic over all patch
types p with only a Commute p constraint. For display I need at least
Show2 (though ShowPatch would be nicer) but this infects *lots* of code
downstream of partitionRL.

Any idea how to work around this i.e. how can I avoid having to add tons
of Show2 constraints all over the place?

How about (locally) adding Show2/ShowPatch as a superclass of Patchy or 
Commute?

Yep, that worked (with Show2 and a few dummy instances). My results so far:

It looks as if the new partitionRL is not doing anything "wrong" here.
Rather, it does a few more commutations which in turn cause a second
(recursive) invocation to fail. This means permutivity is violated. The
bug appears only if duplicate patches are present, but it happens with
darcs-2 and darcs-1 format. This is not covered by our quickcheck tests
because for RepoPatchV2 we exclude Duplicate patches from the test and
for RepoPatchV1 we do not quickcheck test permutivity at all (because of
performance issues).

This is really depressing. It means that even with merge-by-value our
current patch theories are still inconsistent in the presence of
duplicate patches.

Here is my revised test script:

rm -rf R S T
darcs init R
cd R
echo R > R
darcs record -lam 'R1'
darcs tag R
cd ..

darcs init S
cd S
echo R > R
darcs record -lam 'R2'
darcs tag R
echo S > R
darcs record -lam 'S'
darcs tag S
cd ..

cd R
darcs pull ../S -a --allow-conflicts
cd ..

darcs clone R T --tag S

And here is what happens in the second call to partitionRL, called at
Darcs.Patch.Depends.splitOnTag, the line with

  partitionRL ((`notElem` (t : getdeps (hopefully hp))) . info) hps)

listing only the patch names:

  input:
    "R1"
    "TAG R"
    "S"
    "R2"
    "TAG R"
    "TAG S"
  output:
    "R1"
    "S"
    "R2"
    "TAG R"
    "TAG S"
    :>
    "TAG R"

whereas with the old version of partitionRL it is

  before:
    "R1"
    "TAG R"
    "R2"
    "TAG R"
    "S"
    "TAG S"
  after:
    "R2"
    "TAG R"
    "S"
    "TAG S"
    :>
    "R1"
    "TAG R"

Note the duplicate patches R1/R2. The problem is that patch S depends on
either R1 or R2 and if we first commute R2 and S, then we can no longer
commute R1 with S and thus cannot commute it past the "TAG S".

So here's the thing: "merge by value" is unsound. If duplicate prim patches 
do not have an identity, then permutivity goes down the drains.

I wonder how I wasn't able to see this before; it's really simple.

Here is the basic example: we have two repos, in one we have a patch p1, in 
the other we have p2:>q (which do not commute) and p1 and p2 are duplicates 
i.e. they make the same primitive change. We merge them one way and get 
p1:>p2:>q, where the names here are supposed to identify patch identity, not 
content, so they are invariant under merging and commutation. So now q 
depends on either p1 or p2. That means we can commute

(1)   p1:>p2:>q <-> p1:>q:>p2

because the conflicting patches always commute. But we cannot commute p1:>q 
here because q depends on one of p1 or p2. On the other hand we can commute 
p1 and p2 (they directly conflict), so we have

(1)   p1:>p2:>q <-> p2:>p1:>q

But to the q conflictor p1 and p2 look exactly the same, so with the same 
argument as above we can commute

(2)   p2:>p1:>q <-> p2:>q:>p1

(which is also the same as merging the two repos in the other direction).

So p1:>q commutes if preceded by p2, but not if we commute p2 past both, in 
direct contradiction to permutivity.

This has assumed that duplicate patches conflict as they do in darcs-1 
format. In darcs-2 we get a Duplicate patch instead of a conflictor, but 
their commutation behavior is exactly the same as that of conflictors, it is 
just not counted as a conflict. So with darcs-2 we have the same situation.

The patch that broke this has been rolled back.