The setup:

mkdir repo1
cd repo1
darcs init
echo fileA version 1 > fileA
echo fileB version 1 > fileB
darcs add fileA fileB
darcs record --all -m "Add fileA and fileB"
echo fileA version 2 > fileA
sleep 2
darcs record --all -m "Modify fileA"
cd ..
darcs get repo1 repo2
cd repo2
darcs obliterate -p "Modify fileA" --all
darcs unrecord -p "Add fileA and fileB" --all
darcs record --all fileA -m "Add just fileA"
cd ../repo1
darcs pull --all ../repo2

Now the last command I couldn't figure out how to specify non-interactively, so
here's the transcript:

me> darcs obliterate -p "Add fileA and fileB"
Fri Jan 23 15:41:06 CET 2009  foo@bar
  * Modify fileA
Shall I obliterate this patch? (1/2)  [ynWsfvplxdaqjk], or ? for help: n
Fri Jan 23 15:40:04 CET 2009  foo@bar
  * Add fileA and fileB
Shall I obliterate this patch? (2/2)  [ynWvplxdaqjk], or ? for help: y
darcs: bug in darcs!
patches to commute_to_end does not commutex (1) at
src/Darcs/Patch/Depends.hs:452 compiled Jan 23 2009 11:19:30

me> darcs --exact-version
darcs compiled on Jan 23 2009, at 11:22:33
# configured Thu Jan 15 14:31:24 PST 2009
./configure /usr/local/share/config.site /usr/local/etc/config.site

Context:

[TAG 2.2.0
Petr Rockai <me@mornfall.net>**20090115150916] 



Note that if I run the setup from a script rather than typing the commands by
hand in a terminal, and I omit the "sleep" after "echo fileA version 2 > fileA",
the subsequent record says "No changes!" even though there really are some.  Is
this a known problem or should I open a separate bug for that?

BTW I constructed this case because I was trying to see whether the new darcs2
semantics, where identical changes are no longer considered to conflict, makes
it possible to break up a previously-recorded patch into multiple patches
without discarding subsequent patches that depended on the original one.  Is
this supposed to work or not?

Ok, actually the sleep doesn't solve the problem.  Sometimes when I run this
script it works, and sometimes it says "No changes!"  I have no idea what's
going on.

The rest of this bug report sounds pretty serious, so I'll leave the
triage in Thorkil's hands

On Fri, Jan 23, 2009 at 15:12:53 -0000, Aaron Kaplan wrote:
> Note that if I run the setup from a script rather than typing the commands by
> hand in a terminal, and I omit the "sleep" after "echo fileA version 2 > fileA",
> the subsequent record says "No changes!" even though there really are some.  Is
> this a known problem or should I open a separate bug for that?

Just a comment on this unrelated bit: you probably want --ignore-times

I'm going to bump this to urgent.

Hi Aaron,

It sounds like we have a very nice reproducible regression test on our hands
here.  Might I ask what made this tricky to do non-interactively?  Would
obliterate -p "Add fileA and fileB" have helped?  How about your recent findings
working with Lyle, do they give any insight into how to turn this into a test case?

This seems self-contained enough that it could be a good way for any darcs
hacker to get acquainted with some of the deeper stuff... may be a good topic
for hacking sprint 2009-04

Is there a typo or something missing in your suggestion?  obliterate -p "Add
fileA and fileB" is exactly what I said in the script above.  It interactively
asks me if I want to obliterate "Modify fileA", and I don't know how to do the
same thing non-interactively.

I tried making the last line

darcs obliterate --no-deps -p "Add fileA and fileB"

but this says "No patches selected!".  I don't understand why.

Here's a new version of the script with the --ignore-times added, and with the
last line included.  The last line is interactive--you just have to hit y once.
 So this should be easily reproducible, just hard to automate.

----------------------------------
mkdir repo1
cd repo1
darcs init
echo fileA version 1 > fileA
echo fileB version 1 > fileB
darcs add fileA fileB
darcs record --author foo@bar --ignore-times --all -m "Add fileA and fileB"
echo fileA version 2 > fileA
darcs record --author foo@bar --ignore-times --all -m "Modify fileA"
cd ..
darcs get repo1 repo2
cd repo2
darcs obliterate -p "Modify fileA" --all
darcs unrecord -p "Add fileA and fileB" --all
darcs record --author foo@bar --ignore-times --all fileA -m "Add just fileA"
cd ../repo1
darcs pull --all ../repo2
darcs obliterate --dont-prompt-for-dependencies -p "Add fileA and fileB"
-------------------------------------

Lyle's situation was similar, but the error message was different.  I'll try to
write up a minimal test case for it.  Should I post it here or open a new bug?

On Sun, Mar 22, 2009 at 22:23:35 -0000, Aaron Kaplan wrote:
> Is there a typo or something missing in your suggestion?  obliterate -p "Add
> fileA and fileB" is exactly what I said in the script above.

No, that would just be me tripping over myself again.

How about this trick?
  echo n/y | tr / \\012 | darcs obliterate -p ...

> I tried making the last line
> 
> darcs obliterate --no-deps -p "Add fileA and fileB"
> 
> but this says "No patches selected!".  I don't understand why.

That's because the --no-deps switch means "if you're going to have to
use some dependencies not mentioned in the matcher, then don't bother
with the patch in question" 

> Here's a new version of the script with the --ignore-times added, and with the
> last line included.  The last line is interactive--you just have to hit y once.
>  So this should be easily reproducible, just hard to automate.

Thanks!

> Lyle's situation was similar, but the error message was different.  I'll try to
> write up a minimal test case for it.  Should I post it here or open a new bug?

If it's a different error message, I think a new bug would be sensible.

OK got it, here's a version that works completely non-interactively.

mkdir repo1
cd repo1
darcs init
echo fileA version 1 > fileA
echo fileB version 1 > fileB
darcs add fileA fileB
darcs record --author foo@bar --ignore-times --all -m "Add fileA and fileB"
echo fileA version 2 > fileA
darcs record --author foo@bar --ignore-times --all -m "Modify fileA"
cd ..
darcs get repo1 repo2
cd repo2
darcs obliterate -p "Modify fileA" --all
darcs unrecord -p "Add fileA and fileB" --all
darcs record --author foo@bar --ignore-times --all fileA -m "Add just fileA"
cd ../repo1
darcs pull --all ../repo2
echo y | darcs obliterate --dont-prompt-for-dependencies -p "Add fileA and fileB"

I've filed the other, related bug at Issue1401.

On Sun, Mar 22, 2009 at 22:38:38 -0000, Aaron Kaplan wrote:
> OK got it, here's a version that works completely non-interactively.

Thanks!  Now just one more thing :-D

Could you add this to the darcs darcs repository under the bugs/
directory and submit a patch?  I'm making this request in the hopes that
in the future you could do a similar thing for any other bugs you may
find.

Here's a patch.

Attachments

• issue1327-patch

OK we have a minimal regression test for this in the darcs repo, thanks to
Aaron.  All we need now is somebody to study the code and figure out what went
wrong.

Here is my analysis so far. This is the state of the repo before the
failing obliterate:

1: patch 340c6545ae2ec95a2cb5c634964cd38ce94d571c
Author: foo@bar
Date:   Fri Feb  6 02:42:37 CET 2015
  * Add just fileA
    duplicate
    |hunk ./fileA 1
    |-fileA version 2
    |+fileA version 1
    |hunk ./fileA 1
    |-fileA version 1
    |rmfile ./fileA
    |:
    addfile ./fileA
    duplicate
    |hunk ./fileA 1
    |-fileA version 2
    |+fileA version 1
    |hunk ./fileA 1
    |-fileA version 1
    |:
    hunk ./fileA 1
    +fileA version 1

2: patch 1a248554cc51353eeaf23feaa5f818fef3c13e19
Author: foo@bar
Date:   Fri Feb  6 02:42:36 CET 2015
  * Modify fileA
    hunk ./fileA 1
    -fileA version 1
    +fileA version 2

3: patch 53d93d85157f2ad0721172db162b2c813ab79763
Author: foo@bar
Date:   Fri Feb  6 02:42:36 CET 2015
  * Add fileA and fileB
    addfile ./fileA
    hunk ./fileA 1
    +fileA version 1
    addfile ./fileB
    hunk ./fileB 1
    +fileB version 1

We try to obliterate patch 3. Darcs tells us that we can because it
decides that patches 1 and 2 do not depend on 3. This can be easily
verified by issuing the obliterate command interactively and in the last
question hitting 'l', which gives us the single patch we selected:

---- Already selected patches ----
patch 53d93d85157f2ad0721172db162b2c813ab79763
Author: foo@bar
Date:   Fri Feb  6 02:42:36 CET 2015
  * Add fileA and fileB
---- end of already selected patches ----

The bug happens when we actually try to remove patch 3 past the other
two in removeFromTentativeInventory which calls commuteToEnd, because
the latter is a partial function: the (undocumented) pre-condition is
that the commute is actually possible. BTW, I tried to re-implement
removeFromTentativeInventory along the lines suggested in the FIXME
comment, which was easily done by calling removeFromPatchSet; however,
that makes no difference because removeFromPatchSet returns Nothing for
the same reason: the commute failed.

The upshot is that selectChanges is inconsistent with both commuteToEnd
and removeFromPatchSet: The former tells us that patches 1 and 2 do not
depend on 3, but the latter fail when actually trying to commute 3 past
1 and 2.

I am not sure yet who of the two is wrong. Maybe neither is, and
selectChanges just makes an honest effort to guess whether commutation
is possible? If this is the case the implementation of
removeFromTentativeInventory should allow for failure. But I suspect
this was not the intention because typically selectChanges is very
strict as to which selections it allows.

Note the duplicates in patch 1: they are my main suspect as to where an
inconsistency might arise from.

Closing in... The culprit is definitely selectChanges. Everything works
as expected without the -p "Add fileA and fileB": patch 2 gets included
in the final list if we say 'w' when asked about it and 'y' to patch 3.
If we instead say 'n' to patch 2 then patch 3 is skipped.

It is only with -p "Add fileA and fileB" that we get a final selection
that includes 3 but not 2 and this subsequently fails.

Patch selection in Darcs is of astounding complexity. It took me almost
two full days to arrive at the point where I think I have nailed things
down to Darcs performing a commutation (during patch selection) that
should not suceed but fail:

Here is the relevant part of the output I get from my instrumented darcs:

patch 7bfc09f36b93d052d3ed5dd88aeae7ad421ee919
Author: foo@bar
Date:   Fri Feb  6 23:12:31 CET 2015
  * Add fileA and fileB
---- Already selected patches ----
---- end of already selected patches ----
Shall I obliterate this patch? (2/2)  [ynW...], or ? for more options: y

*before forceFirst=
**first=
=first**
**last=
choice = True
Label Nothing 2
patch 890440fa4c70b02c90112aa6f73dde782cf70a6d
Author: foo@bar
Date:   Fri Feb  6 23:12:31 CET 2015
  UNDO: Modify fileA

    M ./fileA -1 +1
choice = False
Label Nothing 3
patch e82a7023ded8e42414adf0dd68beefa625d381de
Author: foo@bar
Date:   Fri Feb  6 23:12:31 CET 2015
  UNDO: Add fileA and fileB

    R ./fileB
=last**

*after forceFirst=
**first=
Label Nothing 3
patch e82a7023ded8e42414adf0dd68beefa625d381de
Author: foo@bar
Date:   Fri Feb  6 23:12:31 CET 2015
  UNDO: Add fileA and fileB

    R ./fileB
=first**
**last=
choice = True
Label Nothing 2
patch 890440fa4c70b02c90112aa6f73dde782cf70a6d
Author: foo@bar
Date:   Fri Feb  6 23:12:31 CET 2015
  UNDO: Modify fileA

    M ./fileA -1 +1
=last**

Here, the "first" and "last" labels refer to the internal representation
of PatchChoices. 

Never mind that the user shouldn't even be asked whether to obliterate
the patch, since "Modify fileA" (which depends on it) has been
explicitly deselected (not shown).

The state after forceFirst is clearly wrong: (the inverse of) "Add fileA
and fileB" has been moved before (the inverse of) Modify fileA.

I am more or less ready to give up at this point. The code in
D.P.Choices looks correct to me, assuming that commuteWhatWeCanXX is
correct. I am more and more suspecting that this is all due to a failing
property of patch commutation as implemented in Darcs. The point here is
that whether commuting a patch past a list of other patches fails or
succeeds should not depend on the order in which we do it. But this what
(apparently) happens here: the -p option causes "Add just fileA" to
commuted first over the other two patches and this seems to let
commutation succeed for the remaining ones (which is wrong, AFAICS).
Whereas, when we actually perform the action on the repo, we commute in
a different order and this fails (which is correct!) but subsequently
causes the crash because we violated the precondition (that the commute
is actually possible).

BTW, note that we have several reports of failing properties when
runnign the unit tests; perhaps this is not a coincidence.

A possible work-around for this issue (and others like it) would be to
acknowledge that the underlying patch theory is partially broken and
never assume that commuting certain patches succeeds (even if we know it
suceeded earlier when we made the patch selection). In particular this
would mean functions like tentativelyRemovePatches (but also many
others) need to be re-written to allow for commutation to fail.

I have attached a bundle that adds the debug messages in case anyone
wants to pursue this further.

Attachments

• fix_-failing_issue1327_sh-should-fail-for-the-right-reason.dpatch

I confirmed my suspicion with a small test program. Here is the output:

initial sequence:
  Add fileA and fileB
  Modify fileA
  Add just fileA
trying to commute back to front...
commuted 'Modify fileA' past 'Add just fileA'
sequence is now:
  Add fileA and fileB
  Add just fileA
  Modify fileA
commuted 'Add fileA and fileB' past 'Add just fileA'
sequence is now:
  Add just fileA
  Add fileA and fileB
  Modify fileA
commuted 'Add fileA and fileB' past 'Modify fileA'
sequence is now:
  Add just fileA
  Modify fileA
  Add fileA and fileB
now let's try to commute in a different order...
cannot commute 'Add fileA and fileB' with 'Modify fileA'
done

I have attached a debug patch that adds a new command named "debug" just
to reproduce this particular failure. See the long comment for how to
run it to get the above results.

The test is short and simple: it uses the basic "commute" function to
try to commute the first three patches of the given repo in two
different orders, reporting the results after each commute.

Attachments

• cleanup_-indentation-of-commandcontrollist.dpatch

There is one slight shimmer of hope in the darkness:

It looks as if the succeeding commutation is not actually wrong: it is
possible to save it to a bundle and cleanly replay it. That means this
is still fixable without developing a new patch formalism. More on that
in a separate message.

Attached a patch that adds output option do debug command for saving
successful commutation sequence to a bundle.

Attachments

• debug-added-output-option.dpatch

This is the first time I have been hit by the broken darcs(-2) patch
theory (see e.g. Issue1327) in real life:

franksen@tiber: ...src/seq/branch-2-2 > darcs push ../branch-2-1
--reverse     
darcs: bug at src/Darcs/Patch/Depends.hs:327 compiled Oct  5 2015 15:23:58
Failed to commute common patches:
patch 58a3060639a0cd6b5df72ce1655ddc1ee2dec0d1
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Tue Nov  3 15:58:25 CET 2015
  * snc: simplify the multi-target lemon rule
  
  Instead of generating an intermediate file ("parser_created") we now use a
  pattern rule. This is the more reliable (and recommended) way to make
rules
  with multiple targets work as expected.
patch 4c93ca9ecf6717006ad52008a63ca527c702979e
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Mon Nov  2 14:12:13 CET 2015
  * snc/Makefile: test only for BASE_3_14==YES and a bit of refactoring
patch b30013217ff103e72b36c3d6e4e973de9294d347
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Tue Nov  3 15:46:29 CET 2015
  * RULES_BUILD: make snc build rules atomic
patch ce9708288ef89817c8fce04e71705ca985ab736d
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Tue Nov  3 15:46:18 CET 2015
  * RULES_BUILD: test only for BASE_3_14==YES and some refactoring
patch 5dad798923ea5940ef520ea5f8f0f93ac10a7428
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Wed May 27 14:23:57 CEST 2015
  * avoid deprecation warnings for use of PATH_FILTER with base 3.15
patch 3b055a70401a8fb0fbc8a7c9047388584a07c2d8
Author: benjamin.franksen@helmholtz-berlin.de
Date:   Sun Jun 30 20:17:55 CEST 2013
  * adapt build rules to take generated header into account
See http://wiki.darcs.net/BugTracker/Reporting for help on bug reporting.

I have made a tar ball of the two repos and uploaded them for reference:

http://www-csr.bessy.de/control/SoftDist/sequencer/repo/seq-branches-21-and-22.tar.gz

I get the same error when I try to pull (--reverse or not doesn't make a
difference), and also when I do push or pull in the other repo.

I have not yet found a way to work around this problem.

I have call Darcs' patch theory as "broken", since it does not have a
property which is desirable to have, namely that whether a sequence of
commutations succeeds does only depend on the final permutation of
patches, not on the order in which we arrive at this permutation by a
sequence of commutations ("consistency of failure"). I am no longer
convinced that this means that Darcs patch theory is broken.

While this property is desirable it is by no means essential. Indeed, it
appears that the Darcs-2 patch theory trades this property for one which
is arguably even more desirable, namely that duplicate patches do not
conflict. The failing test for this issue can be simplified to make this
obvious (the order is patch application order):

(1) add file f
(2) modify f
(3) add file f

Darcs allows commutations that result in a sequence where at least one
of the two 'add file f' patches (i.e. 1 or 3) come before 'modify f'
(2). So it is obvious that commuting (1) with (2) fails for the patches
in the order above. However, if we first commute (3) before (2) and then
before (1), then (afterwards) commuting (1) with (2) succeeds!

This behavior is logically consistent even though it does not have the
property of consistency of failure.

We *do* want to have (n-fold) permutivity, that is: if two sequences of
commutations both succeed *and* result in the same permutation, then the
effect should be the same. That is, the final effect should not depend
the sequence(s) of commutations.

I am still convinced that a proof of n-permutivity from 3-permutivity is
possible without assuming consistency of failure.

Anyway: It seems clear to me now that it is simply a *bug* that we
assume consistency of failure inside the Darcs sources. If patch
selection finds a sequence of commutations that suceeds, then we must
not simply assume that any other sequence that results in the same
permutation suceeds, too. Instead the sequence determined by patch
selection must be remembered and passed to the code that actually
performs the changes to the repository.

There might be another way to fix this bug. We could try to restore
consistency of failure by introducing a "relaxed" form of commutation,
where we drop the condition that modifications to a file depend on the
change that adds the file. If we take care to perform these "relaxed"
commutations only if we previously (e.g. during patch selection) proved
that the finally resulting permutation is reachable via a sequence of
"strict" commutations, then this should be safe (in the sense that the
resulting patch sequence can actually be applied to a tree).

It could be that such a change would be less invasive then the
previously proposed one (i.e. to drop all assumptions of consistency of
failure in the code). The main caveat is that I am not sure whether
"duplicate add-file plus modify-file" is the only scenario where
consistency of failure breaks down. For other cases the solution
indicated above might not work (without changing the patch format).
Also, I have no idea yet how to actually implement this effectively (the
naive copy-paste-modify method would, I fear, involve enormous amounts
of code duplication). If anyone has a good idea... (Ganesh?)

A few thoughts:

- The most obvious technical difficulty that this bug causes is that it makes tags 
effectively mutable, in that you can replace the patches a tag depends on without changing 
its identity.

That in turn defeats assumptions darcs makes about tags throughout. In the code this can 
be seen from the structure of a PatchSet and lots of code that depends on it like 
findCommonAndUncommon. The key point is that when merging you can stop comparing two 
repositories at the first common "clean" tag.

- I think consistency of failure breaks down in any case involving dependency. If you 
replace "add file f" with "add line 10 in f" and "modify f" with "modify line 10 in f", 
exactly the same issues arise.

- I personally don't believe that it's desirable to have duplicates not conflict. While 
it's attractive in a lot of common cases, there are occasional cases where it silently 
does the wrong thing - e.g. consider a file being used as a record of a list of actions or 
events; the same action/event happening twice could be lost. It's also brittle: identical 
changes merge "cleanly", but very similar changes cause a conflict. IMO the real problem 
is that conflicts are so painful in darcs that any opportunity to avoid them is attractive 
:)

My own preferred solution is to get completely away from the way darcs handles conflicts 
at the moment. Instead of just giving up on merging conflicts and effectively undoing 
them, a richer model for repository content allows them to be represented directly. 
http://darcs.net/Ideas/AddAddConflicts is one idea that we've experimented with and Pijul 
is a more ambitious attempt at doing this for file content as well as directory contents.

> The most obvious technical difficulty that this bug causes is that
> it makes tags effectively mutable, in that you can replace the
> patches a tag depends on without changing its identity.

This would be very bad. But I cannot see how inconsistency of failure
(which is what this bug is about) leads to that. Can you give an example?

> I think consistency of failure breaks down in any case involving
> dependency. If you replace "add file f" with "add line 10 in f"
> and "modify f" with "modify line 10 in f", exactly the same issues
> arise.

In principle, perhaps, but not in Darcs as it is, since there is no
separate 'line add' patch (AFAIK), just hunks. I think that for
consistency of failure to break down there must be duplicates involved,
however a similar scenario could perhaps be constructed with duplicate
hunk patches.

I'll reply in a message to the list regarding the other points you
raised. They are related to the problem at hand but do not guide us to a
short or medium term solution...

> > The most obvious technical difficulty that this bug causes is that
> > it makes tags effectively mutable, in that you can replace the
> > patches a tag depends on without changing its identity.

> This would be very bad. But I cannot see how inconsistency of failure
> (which is what this bug is about) leads to that. Can you give an example?

Elaborating your example slightly, suppose you have this:

[patch 1] add file A
[patch 2] modify file A
[tag]

The tag will explicitly depend on patch 2. Since patch 2 implicitly depends on patch 1 there'll be no explicit 
dependency either from the tag or from patch 2. Here "implicitly depends" is exactly a failure to commute.

Now merge in

[patch 1A] add file A

The It merges as a duplicate with [patch 1] and cleanly with [patch 2] and [tag]. Commute it to before [patch 
1]. Now commute out [patch 1] which is allowed because of the presence of [patch 1A]. The tag is still there, 
explicitly depending on [patch 2] and indirectly/implicitly on [patch 1A].

> > I think consistency of failure breaks down in any case involving
> > dependency. If you replace "add file f" with "add line 10 in f"
> > and "modify f" with "modify line 10 in f", exactly the same issues
> > arise.

> In principle, perhaps, but not in Darcs as it is, since there is no
> separate 'line add' patch (AFAIK), just hunks. I think that for
> consistency of failure to break down there must be duplicates involved,
> however a similar scenario could perhaps be constructed with duplicate
> hunk patches.

A hunk patch is just "remove n lines at position k and add m lines at position k". "Add line 10" = "Remove 0 
lines at position 10 and add 1 line at position 10", and "Modify line 10" = "Remove 1 line at position 10 and 
add 1 line at position 10".

I tried to reproduce your example with no success. I can't get the first
file add to commute past the tag, at least not with regular darcs commands.

You're right - it turns out tags actually explicitly depend on 
anything not covered by another explicit dependency (see 
'getUncovered' in Darcs.Patch.Depends). I never realised that about 
tags and had just assumed my example would work.

In contrast, the UI for adding explicit dependencies for (non-tag) 
patches explicitly ignores anything already covered by an implicit 
dependency.

So you can substitute dependencies of normal patches, but not of 
tags (either directly or indirectly). This still feels pretty 
dubious to me, but not as bad as I thought.