darcs

Issue 1868 duplicate patch weirdness: AC + BC = ACBC

Title duplicate patch weirdness: AC + BC = ACBC
Priority bug Status needs-diagnosis/design
Milestone 3.0.0 Resolved in
Superseder Nosy List dmitry.kurochkin, kowey, mornfall
Assigned To
Topics Conflicts

Created on 2010-06-07.18:35:21 by kowey, last changed 2018-04-26.06:24:27 by ganesh.

Messages
msg11302 (view) Author: mornfall Date: 2010-06-07.10:18:03
Eric Kow <kowey@darcs.net> writes:
> On Fri, Jun 04, 2010 at 15:22:17 +0200, Petr Rockai wrote:
>> Well, if this still induced commutation failures, they would still crash
>> darcs. So no, we are not silently ignoring the bug. I don't quite
>> understand how this bug actually came into existence, since I don't
>> think the problem is in any way inherent. It indeed looks like an
>> implementation barf in get_extra. Which no longer exists...
>
> So we've discussed this a bit on IRC with Ian this morning,
>
> http://irclog.perlgeek.de/darcs/2010-06-06#i_2408192
>
> I'm not sure I followed all of the discussion, but I think we've come around to
> thinking that issue1014 needs a closer look (and more aggressive testing).  This
> may be one of those succeeding-for-the-wrong-reason bugs which are way way worse
> than crashing.  If I understand correctly, now we have a situation where
>
> 1. named patches A and B contain only identical primitive patches.
> 2. named patch C depends on A (or B)
> 3. merging AC+BC now leads to a weird repo where we have the named
>    patch C appearing *twice* (not a set of patches anymore, but a
>    bag :-/)
>
> Please correct me if I'm mistaken.  Perhaps we could extend the issue1014
> one by grepping the changes --xml output for the patchinfo and passing it
> to wc -l.

Well, I have so far extended the code to maintain a list of patches that
failed to commute into "common" even though should have. Now at the
point of findCommonAndUncommon and friends, it is too early to tell if
this is really a problem.

So what we probably need is wibbling the merge code to pass this extra
list into the merge function, which can then decide whether this is a
problem. Dup'd named patches that turn out to be merely duplicates can
then be safely discarded during the merge.

In addition, this should allow us to produce much better error messages
in case of PatchInfo collisions: we can clearly say that there was
actually a PatchInfo collision on these two patches, and we can print
them out (in some context, unfortunately we can't guarantee identical,
or even similar context for them).

All in all, this approach should allow us to fix issue1014 safely, while
at the same time improving the situation with corrupt repositories: we
should now be able to tell apart corrupt patches from PatchInfo
collisions, which both previously lead to get_extra failure.

Of course, it is not coming for free -- the code will get a little more
complex, although I think it should still be a lot easier to follow than
the pre-newset gcau.

As for a plan of action wrt. our pending alpha release, I think that I
will restore the original "failing" behaviour for those possibly
dangerous merges. I will then work on a more reasonable implementation
for alpha 2.

[snip text about legit get_extra failures]
> (Sounds like we should have an example of this cooked up, maybe not as a test
>  case but just so we have something to point to as an example of what could go
>  wrong).
We should actually have this a as a test, requiring that darcs fails or
warns or something, if it runs into bogus patch combinations. Even if
they may never arise, theoretically, they do in practice.

[snip]

Yours,
   Petr.
msg11309 (view) Author: kowey Date: 2010-06-07.18:35:19
Marking need-action because we need a formal test for this (note that
the issue1014 test succeeds for the wrong reason).

I'll be adding msg11302 (from Petr's patch 262) to this shortly
msg11317 (view) Author: mornfall Date: 2010-06-07.20:11:08
Actually, patch273 should have the required extension of issue1014 test.
msg11328 (view) Author: kowey Date: 2010-06-08.10:05:08
No more tests or investigation needed (Petr really seems to know how to
fix this). So bumping up to need-implementation.
msg14756 (view) Author: markstos Date: 2011-10-13.13:02:03
Is this a regression, or can it be bumped to the 2.10?
msg14944 (view) Author: ganesh Date: 2012-01-01.22:35:28
This isn't a regression from 2.5 - in fact it's sort of fundamental to the 
handling of duplicates in darcs-2 patches.
msg20117 (view) Author: bf Date: 2018-04-19.06:25:20
Standard problem with duplicates. Unsolvable with current patch format.
msg20124 (view) Author: gh Date: 2018-04-22.22:49:08
But mornfall's http://bugs.darcs.net/msg11302 is proposing a fix.

I am not sure how to interpret Ganesh's message, that the bug is
fundamental to darcs-2 patches.
msg20127 (view) Author: gh Date: 2018-04-23.14:50:31
Maybe the problem would be that even if Darcs 2.16 would manage to
handle nicely these cases (eg, by discarding the duplicate C patch in
the example), other versions of Darcs out there would keep on failing at
merging. So in a given project different persons with different Darcs
versions would have different experciences.

But I don't think this is a real problem, this is basically a bug that
can be fixed in a newer version of Darcs.
msg20129 (view) Author: bf Date: 2018-04-24.18:18:38
Okay, if you have an idea how to fix this or know someone who has, let's
re-open this. My personal preference is to concentrate on getting rid of
Duplicates. I am currently updating and polishing the code I wrote to
integrate Camp conflictors as RepoPatchV3; it is near completion and
conflict resolution is the main part that is still missing, apart from
adding it to the test suite.
msg20130 (view) Author: ganesh Date: 2018-04-26.06:24:25
I'm a bit rusty on the details, but I think there are two aspects to 
this problem.

Firstly, duplicate patches allow this bad property that you can 
"substitute" out a depended-on patch: if named patch C depends on 
named patch A because of some primitives in A, you can produce a 
different named patch B that has a duplicate of those primitives 
from A, and then use darcs commands to get the repo BC instead of 
AC. This is fundamentally a problem with having duplicates in the 
underlying patch type (RepoPatchV2) and hard/impossible to fix 
without removing duplicates.

In the case described here things get a step worse because you can 
apparently make a repo with two copies of C. The suggestion of 
making the high-level merging code cleverer so it doesn't do that 
sounds plausible, but at the cost of added complexity. By "high-
level merging code" I mean the code that works with named patches at 
the repository level to handle merges, such as 
findCommonAndUncommon, not the low-level Merge class and its 
instances.

For me getting rid of duplicates as Ben proposes is the best fix, 
but if anyone is motivated to work on the merge code to patch around 
this particular problem, we could discuss whether the increase in 
complexity is worth it at that point.
History
Date User Action Args
2010-06-07 18:35:21koweycreate
2010-06-07 18:35:31koweysettitle: duplicate patch weirdness: AC + BC = ABCC -> duplicate patch weirdness: AC + BC = ACBC
2010-06-07 18:36:12adminsetmessages: + msg11302
2010-06-07 20:11:08mornfallsetmessages: + msg11317
2010-06-08 10:05:08koweysetstatus: needs-reproduction -> needs-implementation
messages: + msg11328
2010-06-15 20:52:20adminsetmilestone: 2.5.0
2010-06-15 21:00:14adminsettopic: - Target-2.5
2010-07-25 14:29:21tux_rockersetmilestone: 2.5.0 -> 2.8.0
2011-10-13 13:02:04markstossetmessages: + msg14756
2012-01-01 22:35:29ganeshsetmessages: + msg14944
milestone: 2.8.0 -> 2.10.0
2014-12-17 18:50:21ghsetmilestone: 2.10.0 -> 3.0.0
2018-04-19 06:25:21bfsetstatus: needs-implementation -> given-up
messages: + msg20117
2018-04-22 22:49:11ghsetmessages: + msg20124
2018-04-23 14:50:33ghsetmessages: + msg20127
2018-04-24 18:18:39bfsetstatus: given-up -> needs-diagnosis/design
messages: + msg20129
2018-04-26 06:24:27ganeshsetassignedto: mornfall ->
messages: + msg20130