darcs

Patch 2276 coalescing and the pending patch

Title coalescing and the pending patch
Superseder Nosy List bfrk
Related Issues
Status accepted Assigned To
Milestone

Created on 2023-02-19.09:23:46 by bfrk, last changed 2023-07-16.15:07:44 by bfrk.

Files
File name Status Uploaded Type Edit Remove
OpenPGP_0xD36E45316E58CC97.asc bfrk, 2023-07-13.19:48:06 application/pgp-keys
extend-tests_issue2072_coalesce_move_sh.dpatch bfrk, 2023-02-19.09:23:44 application/x-darcs-patch
patch-preview.txt bfrk, 2023-02-19.09:23:43 text/x-darcs-patch
See mailing list archives for discussion on individual patches.
Messages
msg23111 (view) Author: bfrk Date: 2023-02-19.09:23:44
In case this gets reviewed, please don't waste effort on the changes to the
decoalesce implementation, since the third last patch removes it alltogether
anyway.

15 patches for repository http://darcs.net/screened:

patch cb53c6dee9f835b465b499f6c5a932d9568fe8d7
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jul 19 17:45:59 CEST 2022
  * extend tests/issue2072-coalesce-move.sh

patch 338a25cef56046d8fc2a5280d2a78f62c9bb0cc8
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jul 19 17:25:12 CEST 2022
  * add two more test cases to tests/decoalesce-move.sh

patch 4225d17e3c2de3de28e23e18ee01ffb033775e67
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Jul 21 09:20:08 CEST 2022
  * yet another test for decoalescing

patch aacf7df07580fc2fd82f170d0d14a346284bdc23
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Jul 21 10:19:08 CEST 2022
  * fix: replace sortCoalesceFL with canonizeFL in unrecordedChanges

  If we only coalesce, then a hunk in pending together with some change
  detected via the working tree may result in a non-canonical hunk, which we
  don't want to present to the user for e.g. whatsnew. For record and amend we
  have to make this change in the command implementation, since they do not
  use unrecordedChanges. For completeness, I also made the same change in the
  implementation of convert import: even though the hunks originally come from
  a treeDiff, we cannot be sure that coalescing won't produce non-canonical
  hunks.

patch ad80b14e1c3a68aca914a0c10b5a8af83ec64fd4
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Jul 23 19:03:28 CEST 2022
  * further extend test for issue2072-coalesce-move

  It adds a similar test case where we record only one of the coalesced
  changes and check that the pending part of other half is unmodified.

patch 43e61b50dc594a2fc9c73be8f8665a8b8d442525
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Oct 26 09:50:24 CEST 2021
  * remove lots of redundant constraints

patch 862dbb694aa29ec4f9391cf62513a90d0ad6f121
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jul 12 08:42:06 CEST 2022
  * cleanup: disentangle PrimCoalesce

  This adds isIdentity and comparePrims as methods to class PrimCoalesce,
  turns method coalesce into a generic function, and moves all the generic
  functionality that does not depend on Prim.V1 to the new module
  Darcs.Patch.Prim.Coalesce. Default implementations for sortCoalesceFL and
  tryToShrink are provided, too, and Commute, Eq2, and Invert are now super
  class constraints for PrimCoalesce.

patch 5739abe2714af24154eaa008e3817bd7dd4647dc
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 21 12:18:18 CEST 2022
  * move header comment from D.P.Prim.V1.Coalesce to D.P.Prim.Coalesce

patch bf36302caf4c20e6d9fceb38d54b615838d55fd3
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Jul 20 21:31:33 CEST 2022
  * fix a corner case when we remove recorded changes from pending

  We previously cancelled residual changes in pending with inverse changes
  detected from the working tree. This is wrong, as it can e.g. negate an
  explicit 'darcs add' by the user as a side effect of recording some
  unrelated change. See the test script for an example scenario.

patch 47fefe70cbb32e346e2259abc0e6fbc50703d97d
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Jul 12 10:35:46 CEST 2022
  * cleanup prim sifting as proposed in a TODO comment

  This adds primIsSiftable as a method to class PrimSift, turns siftForPending
  into a generic function and moves it back to Darcs.Repository.Pending. The
  Prim.V1 instance is now trivial and moved to Darcs.Patch.Prim.V1.Core,
  eliminating module Darcs.Patch.Prim.V1.Sift.

patch 2aacbed0e07435e7514e622da3d63db9475a894e
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Jul 24 11:18:21 CEST 2022
  * simplify and inline tentativelyRemoveFromPending

  The only place where we used this function is when we automatically updated
  pending after adding a patch to the repository with UpdatePending set to
  YesUpdatePending. The complicated updatePending procedure is not needed in
  this case, since we don't use it for record and amend, so we can simply
  prepend the inverse of the effect of the added patch, similar to what we do
  when removing a patch from the repo.

patch 0dbc2d98aa6397193411924a6524c7445565d173
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Jul 21 10:03:29 CEST 2022
  * explain optimization case in updatePending and add a test for it

patch 6e1427815800d31bc880c730b6bac5edfeba300b
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Jul 23 22:23:03 CEST 2022
  * drastically simplify updatePending, remove decoalescing

  This replaces the previous algorithm to subtract recorded changes from
  pending with a much simpler one that achieves the same results. The whole
  decoalescing functionality is no longer needed and has been removed.

patch 67a97fe1dd9995718d6658e7b32729eb3c807fb9
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Jul 24 14:15:05 CEST 2022
  * use Maybe2 in the result type of coalesce

patch e7fd2d3ac7c11ff00a81a7121b421234ac42f169
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug  7 21:17:09 CEST 2022
  * add another (de)coalescing test
Attachments
msg23550 (view) Author: ganesh Date: 2023-07-12.23:16:13
Getting started on this review..

>   * extend tests/issue2072-coalesce-move.sh
>   * add two more test cases to tests/decoalesce-move.sh
>   * yet another test for decoalescing
>   * further extend test for issue2072-coalesce-move
>   * add another (de)coalescing test

I didn't read these carefully but I shall assume they are good
things :-)

>  * fix: replace sortCoalesceFL with canonizeFL in unrecordedChanges

> If we only coalesce, then a hunk in pending together with some
> change detected via the working tree [..]

I guess this is very much an edge case given it's relatively hard to get
hunks into pending (maybe when blocked in by a delete or replace patch)?

Looks fine, anyway.

>   * remove lots of redundant constraints

Yay
msg23551 (view) Author: ganesh Date: 2023-07-13.07:21:58
>   * cleanup: disentangle PrimCoalesce

Looks good

>   * move header comment from D.P.Prim.V1.Coalesce to D.P.Prim.Coalesce

Fine

>   * fix a corner case when we remove recorded changes from pending

OK. Hopefully the test suite would have shown it if any other cases
were relying on that logic!
msg23552 (view) Author: ganesh Date: 2023-07-13.07:56:21
>   * cleanup prim sifting as proposed in a TODO comment

Looks good

>  * simplify and inline tentativelyRemoveFromPending
>  * explain optimization case in updatePending and add a test for it
>  * drastically simplify updatePending, remove decoalescing

I want to read through these a few more times to think about it in
detail, but an initial question:

I think the net effect of these three patches is that when
updating pending
 - for apply etc, we just prepend the inverse effect of the new patch
 - for record/amend we use coalescing

Is that right? I'm not immediately seeing why we shouldn't coalesce
during apply if that would pull in something that partially subtracted
from the pending state. Or would that case always be a conflict anyway?
msg23557 (view) Author: bfrk Date: 2023-07-13.11:11:22
>>   * fix: replace sortCoalesceFL with canonizeFL in unrecordedChanges
> 
>> If we only coalesce, then a hunk in pending together with some
>> change detected via the working tree [..]
> 
> I guess this is very much an edge case given it's relatively hard to get
> hunks into pending (maybe when blocked in by a delete or replace patch)?

Quite so. And yes, I believe these are the two conditions under which we can 
have hunks in pending.
msg23558 (view) Author: bfrk Date: 2023-07-13.11:42:22
> I think the net effect of these three patches is that when
> updating pending
>   - for apply etc, we just prepend the inverse effect of the new patch
>   - for record/amend we use coalescing
> 
> Is that right? I'm not immediately seeing why we shouldn't coalesce
> during apply if that would pull in something that partially subtracted
> from the pending state. Or would that case always be a conflict anyway?

That's an interesting question, although not directly related to the /change/ 
in question, since that was always the behavior for apply. I think it would 
indeed be a conflict, except perhaps in some corner cases like commuting 
adjacent hunks.

We may consider treating conflicts with unrecorded changes in a way that is 
different from conflicts with recorded changes. That is a semantic change, 
however, and would require a special version of merge, one that leaves 
inverted prims we cannot commute where they are (i.e. prepend them to 
pending).
msg23559 (view) Author: ganesh Date: 2023-07-13.12:13:53
> That's an interesting question, although not directly related to the
> /change/ in question, since that was always the behavior for apply.

Didn't the removal of the call to updatePending in this patch change
the behaviour of apply from coalescing/decoalescing to just prepending 
inverses? :

>   * simplify and inline tentativelyRemoveFromPending
msg23560 (view) Author: bfrk Date: 2023-07-13.12:57:02
> I like the idea of separating the apply from showContextPatch and instead
> use a generic helper function for the combination of the two. I wonder
> why I didn't think of that myself.

The problem is how do we implement showContextPatch for composite patches (FL, 
RL, Named, etc)? To do this correctly we have to apply each single patch after 
showing it (with context). But then we need to unapply everything afterwards, or 
else have a way to restore the state to what it was before we applied the 
patches. The latter was basically what we did previously and for which we needed 
getApplyState, nestedApply, etc. (More precisely, what we did before was to 
embed the apply as a nested virtualTreeIO action, but the effect was the same 
i.e. no change to the state in our original monad.)

My idea to simplify this was to say, well, we are in an ApplyMonad anyway, and 
also need to apply each patch, so why not make this part of the contract and 
thus do away with the need to restore the state? It is true that this makes 
showContextPatch harder to use: we must be aware that it will affect the state. 
Perhaps it suffices to just rename the method to showWithContextAndApply?

It should also be noted that there is precedence for this kind of combined 
operation in darcs, namely class Repair with its method applyAndTryToFix. We 
have the same dilemma there: we need the state to fix the patch but then for the 
next patch we also need the (possibly also fixed) state afterwards.
msg23561 (view) Author: ganesh Date: 2023-07-13.13:18:37
OK, I sort of see the problem. I think a good minor improvement 
would be to do this as part of this review:

> Perhaps it suffices to just rename the method to 
> showWithContextAndApply?

And then we can think about something more sophisticated for followups,
if either of us feels like pursuing it further.
msg23562 (view) Author: ganesh Date: 2023-07-13.13:21:09
PS these messages (msg23559 and msg23560) actually belong in patch2275
but never mind, I'll just refer to them from there when I close that
review.
msg23563 (view) Author: ganesh Date: 2023-07-13.13:21:44
Aargh I meant 23560 and 23561!
msg23564 (view) Author: bfrk Date: 2023-07-13.17:00:02
OMG, mixed up tickets again, sorry!
msg23565 (view) Author: bfrk Date: 2023-07-13.19:48:06
>> That's an interesting question, although not directly related to the

>> /change/ in question, since that was always the behavior for apply.

> 

> Didn't the removal of the call to updatePending in this patch change

> the behaviour of apply from coalescing/decoalescing to just prepending

> inverses? :

Yes. But apply/pull go via tentativelyMergePatches which passes

NoUpdatePending to tentativelyAddPatches_, which means that

tentativelyRemoveFromPending is not called. I tried to convey that in

the patch description but the remark came out so cryptic that I didn't

quite understand it myself when I re-read it ;-)

In fact, the only remaining places where we call one of the

tentativelyAddPatch* procedures with YesUpdatePending is in the tag

command (which is stupid, tagging does not need to update pending), and

(depending on whether we have a working tree) in convert darcs-2 (where

it is also not needed: pending should always be empty).
Attachments
msg23566 (view) Author: bfrk Date: 2023-07-13.19:55:09
(sorry for the botched formatting of my last message)

And I shouldn't have started with "Yes" because no, that's not true ;-)
msg23568 (view) Author: ganesh Date: 2023-07-13.21:16:32
>  * simplify and inline tentativelyRemoveFromPending
>  * explain optimization case in updatePending and add a test for it
>  * drastically simplify updatePending, remove decoalescing

OK, I'm fine with these. Or at least I shall trust the tests.

>   * use Maybe2 in the result type of coalesce

Also good.
msg23590 (view) Author: bfrk Date: 2023-07-16.15:07:43
One more remark: Keep in mind that writing the (tentative) pending patch 
always sifts it as the first step, which in turn involves at least one 
application of `tryToShrink`, which in turn is effectively the same thing 
`sortCoalesceFL`. Thus, even if we "just prepend inverses" outside of 
Darcs.Patch.Pending, the overall effect still includes coalescing.
History
Date User Action Args
2023-02-19 09:23:46bfrkcreate
2023-02-19 09:44:41bfrksetstatus: needs-screening -> needs-review
2023-07-12 23:16:14ganeshsetstatus: needs-review -> review-in-progress
messages: + msg23550
2023-07-13 07:21:58ganeshsetmessages: + msg23551
2023-07-13 07:56:21ganeshsetmessages: + msg23552
2023-07-13 11:11:23bfrksetmessages: + msg23557
2023-07-13 11:42:22bfrksetmessages: + msg23558
2023-07-13 12:13:54ganeshsetmessages: + msg23559
2023-07-13 12:57:02bfrksetmessages: + msg23560
2023-07-13 13:18:37ganeshsetmessages: + msg23561
2023-07-13 13:21:10ganeshsetmessages: + msg23562
2023-07-13 13:21:44ganeshsetmessages: + msg23563
2023-07-13 17:00:02bfrksetmessages: + msg23564
2023-07-13 19:48:07bfrksetfiles: + OpenPGP_0xD36E45316E58CC97.asc
messages: + msg23565
2023-07-13 19:55:09bfrksetmessages: + msg23566
2023-07-13 21:16:33ganeshsetstatus: review-in-progress -> accepted-pending-tests
messages: + msg23568
2023-07-15 00:30:17ganeshsetstatus: accepted-pending-tests -> accepted
2023-07-16 15:07:44bfrksetmessages: + msg23590