These patches all concern the PrimSift, PrimClassify, and PrimCanonize
classes and their Prim.V1 implementation. Most are only refactors without
changing functionality but one or two also chage behavior. This is why I am
not screening them for now.

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

patch ea9c110154b5453a642ceef1c2f7c2ee372a61b9
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Aug  2 22:36:43 CEST 2019
  * cleanup and simplify Darcs.Patch.Prim.V1.Coalesce.mapPrimFL
  
  This eliminates the data type Simple. It is easier and more efficient (wrt
  memory as well as cpu) to put the original patches into the Map, rather than
  take them apart and afterwards put them together again.

patch 818d56d27f76c710a940819c1c7e16e206bfd714
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug  3 01:36:23 CEST 2019
  * use (Bool,a) instead of Either a a in pushCoalescePatch
  
  This is less verbose and more directly captures our intent.

patch 25075b59cf2e6da61af42fd01ed0404e88e20314
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 17:45:08 CEST 2019
  * eliminate class PrimClassify
  
  There were only three use cases left:
  
  (1) The whatsnew command used primIsHunk, which can be easily replaced with
      isJust . isHunk.
  (2) The implementation of RepoPatchV1 used is_filepatch for speedyCommute.
      This is now replaced with calls to listTouchedFiles. To account for
      directory changes, we now check that neither file path is a prefix of
      the other.
  (3) In the instance PrimSift for Prim.V1. Since this is specific to Prim.V1,
      we implement the necessary functions directly.

patch 68e102bdf2dda50041507df1f20dd75403a53553
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 17:45:08 CEST 2019
  * move instance PrimSift for Prim.V1 to its own module

patch 45acbf41ed9714dd8cfe01423daf29640b14f02a
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 19:19:30 CEST 2019
  * drastically simplify implementation of siftForPending for Prim.V1
  
  All the low-level optimisations have been eliminated. What remains is quite
  simple and easy to understand. Theoretically this change may cause
  performance regressions; but the optimizations only covered some simple
  cases like "pending consists only of hunks, binaries, and setpref" or
  "pending consists only of addfile and adddir patches". These special cases
  are handled just fine and without much overhead by the standard algorithm.
  Besides, the bottleneck in handling the pending patch is not sifting, but
  the complicated algorithm for eliminating recorded changes from pending.

patch 2516f1873b74d50c1bcff49e96a62b08ff201007
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:23:30 CEST 2019
  * move canonizeFL out of class PrimCanonize
  
  The definition of this function is independent of Prim.V1, it only uses
  methods from PrimCanonize.

patch b6545d980d7865d5a83dee944cb3b99b5f8ce2f5
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:47:56 CEST 2019
  * define canonize outside of instance PrimCanonize

patch 4f8d783290555868872896d68488ed29458bd0f0
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug  3 01:38:01 CEST 2019
  * refactor and extend tryToShrink and sortCoalesceFL
  
  This is a complicated patch that slightly changes the semantics of both
  functions. If one looks very carefully at the previous implementation of
  tryToShrink, it becomes clear that it is very similar to sortCoalesceFL. The
  difference is that tryToShrink doesn't bother to preserve the order
  established by its call to sortCoalesceFL. Whereas sortCoalesceFL takes care
  not to destroy the order it has already established. Both functions
  internally track whether shrinking has made progress, but hide that from the
  API.
  
  The new methods now both share the same core: sortCoalesceFL2. Similar to
  the old tryHarderToShrink, this function now tries harder to shrink the
  sequence than sortCoalesceFL2 did before. However, if this destroys the
  order, it takes care that it gets restored. It is thus able to find as many
  opportunities to shrink the sequence, while still maintaining the ordering.
  
  Internally, keeping track of whether shrinking has made progress is now
  structured as an effect of type (Any,), where Any is the Bool wrapper from
  the base library. This is a Monad due to the Monoid a => Monad (a,) instance
  defined in base, see the doc comments for details. mapPrimFL now takes and
  returns a function with a monadic effect, which allows us to map
  sortCoalesceFL2 directly. Which in turn allows us to change the return type
  of tryToShrink to Maybe, exposing to calling code whether we could shrink
  the sequence. This is used to avoid lengthFL calls when sifting.
  
  This patch comments out some code instead of deleting it. This was done in
  order to produce better diffs. They will be removed in a separate patch.

patch 18bb76a72a80b54649677a343d3bc758dfd75954
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 12:13:44 CEST 2019
  * separate canonizing from coalescing
  
  This moves the implementation of 'canonize' and 'canonizeFL' to a separate
  module, eliminates the export of canonize, and renames class PrimCanonize to
  PrimCoalesce.
  
  The rationale for this refactor is that 'canonize' for single prims was the
  only remaining method from class PrimCanonize that actually had anything to
  do with canonizing. Its implementation does not depend on coalescing and is
  almost independent from PrimV1, with the exception that it removed patches
  with no effect, using isIdentity. This is, however, also done by
  sortCoalesceFL. Investigating the call sites of the canonize method revealed
  that some of them actually re-implement canonizeFL. The remaining two call
  sites (in Prim.Patch.Split and Darcs.Repository.Diff) now call canonizeFL
  with a singleton FL.

patch a680caba30615c0712be9e77bbfd49fe1e2075dd
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:07:21 CEST 2019
  * remove out-commented functions from D.P.Prim.V1.Coalesce
  
  This is recorded as a separate patch for easier review.

patch 455447e0131a65226296450340273b7da75e640b
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:43:51 CEST 2019
  * slightly extend docs for class PrimCoalesce

Attachments

• cleanup-and-simplify-darcs_patch_prim_v1_coalesce_mapprimfl.dpatch
• patch-preview.txt
• unnamed

Sorry for taking a while to comment on this bundle.

> (2) The implementation of RepoPatchV1 used is_filepatch for speedyCommute.
>     This is now replaced with calls to listTouchedFiles. To account for
>     directory changes, we now check that neither file path is a prefix of
>     the other.

As with all changes to the commute behaviour of patches, this makes me
slightly nervous. Also, moving from is_filepatch to listTouchedFiles seems
like a complication, and I think that listTouchedFiles was previously only
important for the UI.

But we can't never make changes to the commute code for patches, so we
should do something. How about we just get rid of speedyCommute (and review
that change very carefully)? It should just be an optimisation and this is
just V1 patches, which are probably not very widely used.

Also, I'm fine with the general idea of the rest of the changes, though
I haven't looked in detail. If the tests pass then simplifications
to coalescing etc are very likely to be a good thing.

> Sorry for taking a while to comment on this bundle.

No problem.

>> (2) The implementation of RepoPatchV1 used is_filepatch for speedyCommute.
>>     This is now replaced with calls to listTouchedFiles. To account for
>>     directory changes, we now check that neither file path is a prefix of
>>     the other.
> 
> As with all changes to the commute behaviour of patches, this makes me
> slightly nervous.

There is no change to behavior, or at least I didn't intend there to be
one. As you noted below, this is all just an optimization. I slightly
extended its scope: we not only consider files but also directories. I
can't see what could go wrong with that: if both patches touch exactly
one file or directory and none is a prefix of the other, then the
patches are obviously completely unrelated and must commute trivially.

It would be perfectly fine to apply this optimization to the other
RepoPatch types, too. The only thing I don't like is that this ties
commutation to Prim.V1, even if only indirectly.

(Digression: One possible fix for that is to generalize PatchInspect in
such a way that we return some "name/identifier for a file system
object" instead of AnchoredPath. And I think the way to do that is to
define a class for ApplyStates with an associated type synonym, which
for Tree would be AnchoredPath. But this needs more thought and should
be postponed until we make a serious effort to integrate some variant of
FileUUID as an alternative prim patch type.)

BTW, believe we have separate unit tests for speedyCommute. I am not
sure they cover conflicted patches, but I would be willing to extend
them so they do.

If that doesn't satisfy you I could try and limit the optimization to
un-conflicted patches.

> Also, moving from is_filepatch to listTouchedFiles seems
> like a complication, and I think that listTouchedFiles was previously only
> important for the UI.

It is true that until now it was probably used for the UI only. But all
the RepoPatch implementations of listTouchedFiles take care to list all
files touched by any of their ingredients, even if they aren't active
because of conflicts. This behavior should be documented as required.

As to complication: it is a trade-off, as usual. Overall things become
simpler, but of course listTouchedFiles itself is more powerful and
complex than is_filepatch.

> But we can't never make changes to the commute code for patches, so we
> should do something. How about we just get rid of speedyCommute (and review
> that change very carefully)? It should just be an optimisation and this is
> just V1 patches, which are probably not very widely used.

I doubt that. Remember that conversion from darcs-1 to darcs-2 format
means you must either merge all your branches into one repo and then
pull them apart afterwards or else say goodbye to those branches. Also
note that the former may be impossible in practice due to exponential
conflict blow-up. My guess is that many users never bothered to upgrade
to darcs-2. I know for sure that I didn't, mostly, and that we still
have many darcs-1 repos at work and we regularly use them. We just take
care not to create conflicts in upstream, quite similar to the way we
work with darcs itself.

Updated and rebased. Now contains a test for issue2072 that was resolved by
this bundle, plus a patch to remove the speedyCommute optimization for
RepoPatchV1.

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

patch 29b26f78edb68431c0f94a1162a55120a8c664a9
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  7 16:02:13 CET 2021
  * normalize code layout for pushCoalescePatch

patch a26e99aaa63c1c3fb1cb61ca4a3a49d96de9d104
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug  3 01:36:23 CEST 2019
  * use (Bool,a) instead of Either a a in pushCoalescePatch

  This is less verbose and more directly captures our intent.

patch 823562e22affc95b39b8fa2f251ef2be65915be1
Author: Ben Franksen <ben.franksen@online.de>
Date:   Fri Aug  2 22:36:43 CEST 2019
  * cleanup and simplify Darcs.Patch.Prim.V1.Coalesce.mapPrimFL

  This eliminates the data type Simple. It is easier and more efficient (wrt
  memory as well as cpu) to put the original patches into the Map, rather than
  take them apart and afterwards put them together again.

patch 885f06049afb7b2f99fd29dbea133f31a19db63c
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Feb  7 16:26:19 CET 2021
  * fix haddocks for pushCoalescePatch

  Itemized lists require the points to be numeric.

patch 565cdb2202675d777cfe9e80e7056da1773344cb
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 17:45:08 CEST 2019
  * eliminate class PrimClassify

  There were only three use cases left:

  (1) The whatsnew command used primIsHunk, which can be easily replaced with
      isJust . isHunk.
  (2) The implementation of RepoPatchV1 used is_filepatch for speedyCommute.
      This is now replaced with calls to listTouchedFiles. To account for
      directory changes, we now check that neither file path is a prefix of
      the other.
  (3) In the instance PrimSift for Prim.V1. Since this is specific to Prim.V1,
      we implement the necessary functions directly.

patch faca1827e69c26e671a52f273f57086c59cdc095
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 17:45:08 CEST 2019
  * move instance PrimSift for Prim.V1 to its own module

patch 5ba102034f4a95587465afa70800422e31789a48
Author: Ben Franksen <ben.franksen@online.de>
Date:   Thu Aug  1 19:19:30 CEST 2019
  * drastically simplify implementation of siftForPending for Prim.V1

  All the low-level optimisations have been eliminated. What remains is quite
  simple and easy to understand. Theoretically this change may cause
  performance regressions; but the optimizations only covered some simple
  cases like "pending consists only of hunks, binaries, and setpref" or
  "pending consists only of addfile and adddir patches". These special cases
  are handled just fine and without much overhead by the standard algorithm.
  Besides, the bottleneck in handling the pending patch is not sifting, but
  the complicated algorithm for eliminating recorded changes from pending.

patch bb222eb5b29ca4d5996a1e74b5e54f9b5d68c3de
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 16 20:37:51 CET 2021
  * derive the Show instances for Prim.V1

patch 0c4d6fb2c48d5b72a05b2bc73eb427131519397a
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 16 20:47:55 CET 2021
  * remove evalargs in Darcs.Patch.Prim.V1.Core

  All the interesting fields are already declared as strict in the data type.

patch c2730e96cc887077b422e4534aaadd8f5465d2ef
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Feb 16 21:21:20 CET 2021
  * layout fixes in Darcs.Patch.Prim.V1.Core

patch 8d5f7b0ac24d4f3ff3cc499f814de550623d11df
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:23:30 CEST 2019
  * move canonizeFL out of class PrimCanonize

  The definition of this function is independent of Prim.V1, it only uses
  methods from PrimCanonize.

patch 55039de944e3dd99fe89fbb562d9a3cca3d8791a
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:47:56 CEST 2019
  * define canonize outside of instance PrimCanonize

patch 4caf10dd7d378f34d9249518dd02158f6a78346b
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug  3 01:38:01 CEST 2019
  * refactor and extend tryToShrink and sortCoalesceFL

  This is a complicated patch that slightly changes the semantics of both
  functions. If one looks very carefully at the previous implementation of
  tryToShrink, it becomes clear that it is very similar to sortCoalesceFL. The
  difference is that tryToShrink doesn't bother to preserve the order
  established by its call to sortCoalesceFL. Whereas sortCoalesceFL takes care
  not to destroy the order it has already established. Both functions
  internally track whether shrinking has made progress, but hide that from the
  API.

  The new methods now both share the same core: sortCoalesceFL2. Similar to
  the old tryHarderToShrink, this function now tries harder to shrink the
  sequence than sortCoalesceFL2 did before. However, if this destroys the
  order, it takes care that it gets restored. It is thus able to find as many
  opportunities to shrink the sequence, while still maintaining the ordering.

  Internally, keeping track of whether shrinking has made progress is now
  structured as an effect of type (Any,), where Any is the Bool wrapper from
  the base library. This is a Monad due to the Monoid a => Monad (a,) instance
  defined in base, see the doc comments for details. mapPrimFL now takes and
  returns a function with a monadic effect, which allows us to map
  sortCoalesceFL2 directly. Which in turn allows us to change the return type
  of tryToShrink to Maybe, exposing to calling code whether we could shrink
  the sequence. This is used to avoid lengthFL calls when sifting.

  This patch comments out some code instead of deleting it. This was done in
  order to produce better diffs. They will be removed in a separate patch.

patch 76748bb8d9f9b12a9a64214c42c8c1ef0f5e6cfc
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Nov 17 09:36:28 CET 2021
  * extend docs for class PrimSift

patch a2bffdda59fbec2d5135e08c64737ed8b68a7c29
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Nov 17 09:36:28 CET 2021
  * separate canonizing from coalescing

  This moves the implementation of 'canonize' and 'canonizeFL' to a separate
  module, eliminates the export of canonize, and renames class PrimCanonize to
  PrimCoalesce.

  The rationale for this refactor is that 'canonize' for single prims was the
  only remaining method from class PrimCanonize that actually had anything to
  do with canonizing. Its implementation does not depend on coalescing and is
  almost independent from PrimV1, with the exception that it removed patches
  with no effect, using isIdentity. This is, however, also done by
  sortCoalesceFL. Investigating the call sites of the canonize method revealed
  that some of them actually re-implement canonizeFL. The remaining two call
  sites (in Prim.Patch.Split and Darcs.Repository.Diff) now call canonizeFL
  with a singleton FL.

patch adc5bf70a2ac2db29255d2830a8607d719f018d3
Author: Ben Franksen <ben.franksen@online.de>
Date:   Mon Aug  5 10:07:21 CEST 2019
  * remove out-commented functions from D.P.Prim.V1.Coalesce

  This is recorded as a separate patch for easier review.

patch 445cbd3b350cf80060c61558fe77c63ce249ec88
Author: Ben Franksen <ben.franksen@online.de>
Date:   Wed Apr 20 20:58:59 CEST 2022
  * remove RepoPatchV1 speedyCommute

  Note that this was merely used as an optimization for the case where both
  patches touch a single file or directory, neither of which is a prefix of
  the other. It was previously limited to just files, using is_filepatch.
  Extending the optimization to include directories and relying on
  listTouchedFiles was regarded as too risky, which is why here we remove the
  optimization altogether.

patch 79dc9623a91b6ac7ad61e0b785eec61d23dd439f
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Apr 12 17:17:45 CEST 2022
  * add test for (now resolved) issue2072

Attachments

• normalize-code-layout-for-pushcoalescepatch.dpatch
• patch-preview.txt

Screening this one now, since the main point of contention is resolved 
as proposed by Ganesh (remove the speedyCommute optimization for 
RepoPatchV1).

Picking off a couple of easy changes at the start:

>   * normalize code layout for pushCoalescePatch

OK

>   * use (Bool,a) instead of Either a a in pushCoalescePatch

> --   As an additional optimization, pushCoalescePatch outputs a
> whether

Small language mistake in the change, should be "outputs whether".

I haven't forgotten this patch btw, it just didn't get to the top of my
review list yet.

Continuing to go incrementally

>   * cleanup and simplify Darcs.Patch.Prim.V1.Coalesce.mapPrimFL

Fine

>   * fix haddocks for pushCoalescePatch

fine

>  * eliminate class PrimClassify
>  * remove RepoPatchV1 speedyCommute

Reviewing these together - looks fine.

As an aside I think the original speedyCommute optimisation (now
removed) was wrong in the unlikely event that someone would have
used V1 repo patches with FileUUID prims, as FileUUID just says
`listTouchedFiles _ = []`.

>   * move instance PrimSift for Prim.V1 to its own module

Fine

>  * drastically simplify implementation of siftForPending for Prim.V1

>  -- | Alternately 'sift' and 'tryToShrink' until shrinking no longer reduces

The word "Alternately" in thhis comment on `siftForPending` no
longer makes sense now that the short-cut cases have been removed.
(I've checked it's still there in screened).

Rest looks good.

>  * derive the Show instances for Prim.V1
>  * remove evalargs in Darcs.Patch.Prim.V1.Core
>  * layout fixes in Darcs.Patch.Prim.V1.Core
>  * move canonizeFL out of class PrimCanonize
>  * define canonize outside of instance PrimCanonize

All good

>   * refactor and extend tryToShrink and sortCoalesceFL

Looks good. I haven't double-checked your statements about the old
behaviour in full detail, but they make sense and the new code is fine.

>  * extend docs for class PrimSift
>  * remove out-commented functions from D.P.Prim.V1.Coalesce
>  * add test for (now resolved) issue2072

All good.

>   * separate canonizing from coalescing

regarding this comment:

> +-- Even if the patches are just hunk patches,
> +-- this is not necessarily the same set of results as you would get
> +-- if you applied the sequence to a specific tree and recalculated
> +-- a diff.
> +--
> +-- XXX Why not? How does it differ? The implementation for Prim.V1 does
> +-- sortCoalesceFL and then invokes the diff algorithm for each hunk. How can
> +-- that be any different to applying the sequence and then taking the diff?
> +-- Is this merely because diff does not sort by file path?

For one thing, "diff" can produce many equivalent results. e.g. Myers versus
Patience. Also, given a patch and ignoring its true darcs context, there are
many possible filesystem trees it could apply to, and diffing in each possible
such tree will not necessarily produce the same result.

> +-- Besides, diff and apply /must/ be inverses in the sense that for any two
> +-- states {start, end}, we have
> +--
> +-- prop> diff start (apply (diff start end)) == end

I don't follow this property because I can't figure out the types ;-)

But I do think this is true:

prop> apply (diff start end) start == end

but apply is only a one-sided inverse for diff; it's not always true that

prop> diff start (apply patch start) == patch

Replying to msg23368: If this is about the comment, as far as I can 
see the code still does that i.e. alternately sift and tryToShrink 
until the latter fails i.e. no more shrinking is possible. Or are you 
suggesting that doing this in a loop is no longer necessary because 
the loop will always stop after one iteration?

> Replying to msg23368: If this is about the comment, as far as I can
> see the code still does that i.e. alternately sift and tryToShrink 
> until the latter fails i.e. no more shrinking is possible. Or are
> you suggesting that doing this in a loop is no longer necessary
> because the loop will always stop after one iteration?

Oh, I misread that comment completely! I thought "Alternately" meant
as an alternative to the (supposed) fast path code just above that
you simplified away :-) Now I read your interpretation it makes much
more sense.

>   * separate canonizing from coalescing

Looks good. I'm not sure that avoiding exporting `canonize` is worth it,
as the call sites which construct explicit singletons look a bit
ugly, but it's no big deal.

That's this whole bundle done. In less than 4 years! :-)

Thanks! These are tricky refactors and not easy to review.

Regarding your last remark about not exporting the "single" 
canonize: you are right that this is debatable. The point I wanted 
to drive home with this is that canonizing a sequence is not the 
same as canonizing each patch in the sequence.