darcs

Issue 1327 patches to commute_to_end does not commutex (1) at src/Darcs/Patch/Depends.hs:452

Title patches to commute_to_end does not commutex (1) at src/Darcs/Patch/Depends.hs:452
Priority urgent Status needs-diagnosis/design
Milestone Resolved in
Superseder Nosy List Aaron, darcs-devel, dmitry.kurochkin, kowey
Assigned To
Topics Core

Created on 2009-01-23.15:12:52 by Aaron, last changed 2015-02-09.02:13:40 by bf.

Files
File name Uploaded Type Edit Remove
cleanup_-indentation-of-commandcontrollist.dpatch bf, 2015-02-08.15:44:58 application/x-darcs-patch
debug-added-output-option.dpatch bf, 2015-02-09.02:13:39 application/x-darcs-patch
fix_-failing_issue1327_sh-should-fail-for-the-right-reason.dpatch bf, 2015-02-07.15:49:42 application/x-darcs-patch
issue1327-patch Aaron, 2009-03-29.21:41:18 application/octet-stream
Messages
msg7163 (view) Author: Aaron Date: 2009-01-23.15:12:48
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?
msg7164 (view) Author: Aaron Date: 2009-01-23.15:21:08
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?
msg7165 (view) Author: Aaron Date: 2009-01-23.15:42:26
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.
msg7171 (view) Author: kowey Date: 2009-01-24.08:56:22
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
msg7485 (view) Author: kowey Date: 2009-03-22.20:08:52
I'm going to bump this to urgent.
msg7486 (view) Author: kowey Date: 2009-03-22.21:32:45
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
msg7489 (view) Author: Aaron Date: 2009-03-22.22:23:32
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?
msg7490 (view) Author: kowey Date: 2009-03-22.22:33:12
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.
msg7491 (view) Author: Aaron Date: 2009-03-22.22:38:35
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"
msg7493 (view) Author: Aaron Date: 2009-03-22.23:05:51
I've filed the other, related bug at Issue1401.
msg7496 (view) Author: kowey Date: 2009-03-23.08:37:22
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.
msg7561 (view) Author: Aaron Date: 2009-03-29.21:41:18
Here's a patch.
Attachments
msg8147 (view) Author: kowey Date: 2009-08-15.08:51:06
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.
msg18040 (view) Author: bf Date: 2015-02-06.02:42:27
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.
msg18042 (view) Author: bf Date: 2015-02-06.03:26:07
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.
msg18045 (view) Author: bf Date: 2015-02-07.15:49:42
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
msg18046 (view) Author: bf Date: 2015-02-08.15:44:58
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
msg18047 (view) Author: bf Date: 2015-02-08.23:11:40
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.
msg18048 (view) Author: bf Date: 2015-02-09.02:13:39
Attached a patch that adds output option do debug command for saving
successful commutation sequence to a bundle.
Attachments
History
Date User Action Args
2009-01-23 15:12:52Aaroncreate
2009-01-23 15:21:10Aaronsetstatus: unread -> unknown
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7164
2009-01-23 15:21:57Aaronsetstatus: unknown -> unread
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
2009-01-23 15:42:28Aaronsetstatus: unread -> unknown
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7165
2009-01-23 15:42:45Aaronsetstatus: unknown -> unread
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
2009-01-24 08:56:25koweysetstatus: unread -> unknown
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7171
2009-03-22 20:08:55koweysetpriority: bug -> urgent
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7485
2009-03-22 21:32:48koweysetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7486
2009-03-22 22:23:35Aaronsetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7489
2009-03-22 22:33:14koweysetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7490
2009-03-22 22:38:38Aaronsetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7491
2009-03-22 23:05:54Aaronsetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7493
2009-03-23 08:37:24koweysetnosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7496
2009-03-29 21:41:20Aaronsetfiles: + issue1327-patch
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
messages: + msg7561
2009-08-15 08:51:10koweysetstatus: unknown -> needs-reproduction
nosy: kowey, simon, Aaron, thorkilnaur, dmitry.kurochkin
topic: + Core
messages: + msg8147
2009-08-25 17:39:42adminsetnosy: + darcs-devel, - simon
2009-08-27 14:24:16adminsetnosy: kowey, darcs-devel, Aaron, thorkilnaur, dmitry.kurochkin
2010-03-23 23:41:04koweysetnosy: - thorkilnaur
2015-02-06 02:42:29bfsetstatus: needs-reproduction -> needs-diagnosis/design
messages: + msg18040
2015-02-06 03:26:09bfsetmessages: + msg18042
2015-02-07 15:49:44bfsetfiles: + fix_-failing_issue1327_sh-should-fail-for-the-right-reason.dpatch
messages: + msg18045
2015-02-08 15:45:00bfsetfiles: + cleanup_-indentation-of-commandcontrollist.dpatch
messages: + msg18046
2015-02-08 23:11:41bfsetmessages: + msg18047
2015-02-09 02:13:40bfsetfiles: + debug-added-output-option.dpatch
messages: + msg18048
2015-02-09 08:20:10bflinkissue1401 superseder