I found a failing test case that I could manually reconstruct, see upcoming 
patch. it has the (simplified) structure A;B;C;D, where

* A and B conflict
* C explicitly depends on A
* D explicitly depends on B and C

Here, darcs reports no conflict i.e. tells us that the conflict A vs. B has 
been resolved. This is correct, since D transitively depends on both A and 
B.

Whereas if we swap B;C to C;B resulting in A;C;B;D, then it does report the 
conflict. Which is incorrect.

Thinking about this test case made me realize that there is a property that 
RepoPatches have but Named patches are missing:

  If we merge A;C with B, where A conflicts with B, and C depends on A,
  then B and C /also/ conflict.

With Named patches this is no longer true, namely if C depends (only) 
explicitly on A. I don't think this is relevant to the bug in question, 
just wanted to mention it here for the record.

The algorithm is indeed subtly broken.

The point is that the generic function findConflicting (Darcs.Patch.Conflict) 
/does/ treat patches that only explicitly depend on those that are in conflict 
with the one in question as belonging to that same conflict. This is obvious 
from the result type, since such a patch could not be part of the LHS of the 
result.

We use this function to calculate the participants in a conflict. The problem is 
that the algorithm accumulates transitive dependencies on the fly during the 
(single) traversal. At the point where we examine B, or more precisely A;C;B, we 
already know that B and C are depended upon by a single patch (D), but not yet 
that the same patch D also (indirectly) depends on A via C. Thus we erroneously 
fail to see that all of the conflict's participants {A,B,C} are transitively 
depended upon.

What we need to do is to include the transitive dependencies for all involved 
patches before checking if they are covered.

It looks as if I have a fix.

The problem I described in the previous message is easy to fix, but this 
is not enough. A second problem is that findConflicting also commutes out 
patches that only explicitly depend on parts of the conflict. These do 
not actually belong to the conflict. Filtering them out makes even more 
test cases succeed but still not all of them.

The remaining problem lies deeper.

To recap the definition: a conflict between a set of conflicting named 
patches is resolved if it is transitively explicitly depended on by a 
single named patch. This marks conflicts as resolved in addition to those 
already regarded resolved by the underlying RepoPatch layer alone.

Now, this is slightly ambiguous because we haven't said whether we are 
talking about direct or transitive conflict sets. The current algorithm 
uses "direct conflict" (this is what findConflicting returns). But for 
conflict resolution we must consider transitive conflicts.

Unfortunately, calculating transitive conflicts is not possible with a 
straight-forward extension of findConflicting. In fact, I doubt that, in 
general, we can commute out all transitively conflicting patches (and 
only those), if the underlying RepoPatch type only knows about direct 
conflicts (as is the case for V3).

So I ended up removing large parts of the existing code and instead 
borrowed and adapted the machinery I developed for RepoPatchV3. 
resolveConflicts for Named patches is now a two-pass algorithm. In a 
first pass we gather two pieces of information: a list of transitive 
explicit dependency sets; and a list of transitive conflict sets. This 
pass is quite similar, but not quite the same as findComponents from 
Darcs.Patch.V3.Resolution.

In a second pass we move patch contents to the "resolved" series, if we 
find that a patch occurs in one of the conflict sets and that conflict 
set is fully covered by one of the dependency sets. All others are 
commuted through it, as far as that is possible. This pass is quite 
similar in structure to the one we used before (and retains the same 
name).

Finally we run the RepoPatch version of resolveConflicts on the resulting 
two series.

This seems to resolve the issue and result in the expected behavior. Will 
send as soon as I have everything cleaned up and properly commented.

For the record: not everything I wrote in my last comment here is 
actually correct. It turned out that when we determine /resolved/ 
conflicts, we actually need to consider direct conflicts (between exactly 
two patches). See the comments in my final (?) fix for this issue.