darcs

Patch 2002 introduce unwind

Title introduce unwind
Superseder Nosy List ganesh
Related Issues
Status accepted Assigned To
Milestone

Created on 2020-02-23.19:07:38 by ganesh, last changed 2020-06-20.07:18:54 by bf.

Files
File name Status Uploaded Type Edit Remove
pEpkey.asc bf, 2020-02-24.07:57:26 application/pgp-keys
pEpkey.asc bf, 2020-02-24.08:28:07 application/pgp-keys
pEpkey.asc bf, 2020-02-24.13:03:51 application/pgp-keys
patch-preview.txt ganesh, 2020-02-23.19:07:37 text/x-darcs-patch
patch-preview.txt ganesh, 2020-02-25.08:14:11 text/x-darcs-patch
patch-preview.txt ganesh, 2020-02-25.23:02:20 text/x-darcs-patch
tests_-add-a-todo-about-merging-hasprimconstruct_usesv1model.dpatch ganesh, 2020-02-25.08:14:11 application/x-darcs-patch
tests_-always-use-prim-patches-for-generating_shrinking.dpatch ganesh, 2020-02-23.19:07:37 application/x-darcs-patch
unnamed ganesh, 2020-02-23.19:07:37 text/plain
unnamed ganesh, 2020-02-25.08:14:11 text/plain
unnamed ganesh, 2020-02-25.23:02:20 text/plain
unwind_-add-comment-about-invariant.dpatch ganesh, 2020-02-25.23:02:20 application/x-darcs-patch
See mailing list archives for discussion on individual patches.
Messages
msg21890 (view) Author: ganesh Date: 2020-02-23.19:07:37
This builds on as-yet-unscreened patches in
patch1979 and patch2001.

Again I'll wait a little bit before screening this to give
a chance for any significant objections.

As with my previous bundles, this one doesn't actually do
anything visible yet :-) The next step is to add some error
handling so we can handle the rare case of squashing failure
in V1, and integrate it with rebase. I am fairly confident
that won't be a problem given the previous experiments.

9 patches for repository darcs-unstable@darcs.net:screened:

patch b043d8bcbbe106224a90148480f9735ab0bfefc3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 10:58:34 GMT 2020
  * tests: always use prim patches for generating/shrinking
  
  We already didn't try to generate conflicted patches, and
  even shrinking unconflicted patches is actually unsound if
  there might be a conflict later in a sequence.
  
  Instead of needing partial functions on repo patches, it's
  better to express this invariant in the types by only storing
  prim patches, and generating the repo patches on the fly
  when actually using the test cases.
  

patch ba02c674facfc9dfc826adc1eb8509e07fe010c0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 12:06:59 GMT 2020
  * tests: introduce infrastructure for merge checking
  
  Because V1 and V2 patches are known to be buggy, we
  sometimes need to exclude buggy merges when using them
  to test other properties.

patch b55922b9b19e27d3d42cf4c500d2c9e17e24e9d5
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:44:20 GMT 2020
  * tests: export V1Model(..)

patch 3dc6fb02adcabbba69bc02decb322fec09bab80a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:48:06 GMT 2020
  * tests: move patch properties into D.T.P.P.Generic
  
  This means they can be used from D.T.P.RepoPatchV1
  

patch 6f7b4b6bd8785c0f4df3bf587c1ac1df1149d576
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:51:48 GMT 2020
  * tests: remove unused withStateShrinking

patch 4b0e6e70e1c73391b5ad787c88b47cf330ff6a29
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:52:48 GMT 2020
  * tests: generalise hasPrimConstruct, add usesV1Model

patch c26d508c17fc6157325cea574118adace10ba083
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:52:54 GMT 2020
  * tests: introduce method to identify V1 patch type

patch fa5773462abc1d2d4fc79429f43afe62574910e2
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:54:42 GMT 2020
  * tests: add withAllSequenceItems

patch ed48a37300e45d31ff9b98389340e59b20f8d725
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb 23 18:57:30 GMT 2020
  * introduce concept of unwinding a conflict
  
  This provides a generic way to get at the underlying primitive
  patches in the conflict.
Attachments
msg21898 (view) Author: bf Date: 2020-02-24.07:57:26
Preliminary review.

>   * tests: always use prim patches for generating/shrinking
>   * tests: introduce infrastructure for merge checking
>   * tests: export V1Model(..)
>   * tests: move patch properties into D.T.P.P.Generic
>   * tests: remove unused withStateShrinking

These are all fine, consider reviewed.

>   * tests: generalise hasPrimConstruct, add usesV1Model

You may have expected that I won't like this one overmuch ;-)

I can appreciate the need to move from the Bool to a Dict here and I am
not objecting to that part. However, having both hasPrimConstruct and
hasV1Model smells. Logically these are the same statement i.e. we
require patches based on Prim.V1. Perhaps this is a good time to do
acknowledge that PrimConstruct really cannot be defined usefully for
other prim types... anyway, I don't think this should hold up screening
these patches, just add a TODO marker here so we remember we should
clean this up.

>   * tests: introduce method to identify V1 patch type

Fine.

>   * tests: add withAllSequenceItems

(1) If you recognise that combineTestResults is just mconcat with a
suitable SemiGroup instance I would expect you to replace this function
with mconcat everywhere.
(2) I get a warning about missing implementation of mappend (ghc-8.2). I
think you should define mappend instead of (<>).

>   * introduce concept of unwinding a conflict

For data Unwind you say

-- Note: At the moment we don't require any invariants like minimality
-- for the context.

and further down in consBefore:

    -- Slightly surprisingly, it is possible for a context patch to
commute with the
    -- underlying primitive. If that happens we want to see if we can
eliminate it
    -- by propagating it through the other context ("after" in this case).
    -- "full unwind example 3" fails if this case is omitted, as
(typically) do the standard
    -- 100 iteration QuickCheck tests

I may be wrong, but to me these two statements contradict each other!
Apparently we do have to commute context prims past if that is possible,
which pretty strongly suggests that the context has to be minimal, at
least with respect to commutation.

I am not much surprised that context prims sometimes can be commuted
past for some patch types. For instance, for V2 the context as stored in
the Non inside the conflictor consists of full RepoPatchV2s which could
be conflicted themselves. But we just take their combined effect when we
unwind, so there may well be some parts that commute past.

Can you simplify the examples with a few helper functions? E.g.

mkNamed hash = NamedP (rawPatchInfo "" "" "" ["Ignore-this: "++hash]
path s = AnchoredPath [unsafeMakeName s])

Otherwise: Fine.
Attachments
msg21900 (view) Author: bf Date: 2020-02-24.08:28:07
>>   * introduce concept of unwinding a conflict
> [...]
> 
> Otherwise: Fine.

Almost. This one I guess slipped in accidentally:

hunk ./harness/Darcs/Test/HashedStorage.hs 1
-module Darcs.Test.HashedStorage( tests ) where
+module Darcs.Test.HashedStorage ( tests, unsafeMakeName ) where
Attachments
msg21905 (view) Author: ganesh Date: 2020-02-24.12:14:55
On 24/02/2020 08:28, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
>>>   * introduce concept of unwinding a conflict
>> [...]
>>
>> Otherwise: Fine.
> 
> Almost. This one I guess slipped in accidentally:
> 
> hunk ./harness/Darcs/Test/HashedStorage.hs 1
> -module Darcs.Test.HashedStorage( tests ) where
> +module Darcs.Test.HashedStorage ( tests, unsafeMakeName ) where

It's needed by Darcs.Test.Patch.Examples.Unwind. I hit it at the last
minute when merging with latest screened, there's probably a better way.
msg21908 (view) Author: bf Date: 2020-02-24.13:03:51
>> hunk ./harness/Darcs/Test/HashedStorage.hs 1
>> -module Darcs.Test.HashedStorage( tests ) where
>> +module Darcs.Test.HashedStorage ( tests, unsafeMakeName ) where
> 
> It's needed by Darcs.Test.Patch.Examples.Unwind. I hit it at the last
> minute when merging with latest screened, there's probably a better way.

Okay, no problem, I just wondered.
Attachments
msg21912 (view) Author: ganesh Date: 2020-02-24.18:32:06
I've screened this bundle as there's no major surgery required,
and will followup with further patches to address the comments.
msg21918 (view) Author: ganesh Date: 2020-02-25.08:14:11
Following up on review

3 patches for repository /home/ganesh/darcs/screened:

patch 54bb5860e199e30c8f4ae1e67165032c943586f3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 07:09:02 GMT 2020
  * tests: add a TODO about merging hasPrimConstruct/usesV1Model

patch 9a237fb212d148f7103d0ce5028cc68b600a2bba
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 07:34:38 GMT 2020
  * tests: add mappend TestResult for old GHC compatibility

patch 9ac310184b6f612d6da4946c2e91b3a4f356e967
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 08:04:53 GMT 2020
  * tests: use Semigroup TestResult consistently
Attachments
msg21919 (view) Author: ganesh Date: 2020-02-25.08:25:25
[apologies, another patch with a bad initial subject, which I've fixed]

>>   * tests: generalise hasPrimConstruct, add usesV1Model
> 
> You may have expected that I won't like this one overmuch ;-)
> 
> I can appreciate the need to move from the Bool to a Dict here and I am
> not objecting to that part. However, having both hasPrimConstruct and
> hasV1Model smells. Logically these are the same statement i.e. we
> require patches based on Prim.V1. Perhaps this is a good time to do
> acknowledge that PrimConstruct really cannot be defined usefully for
> other prim types... anyway, I don't think this should hold up screening
> these patches, just add a TODO marker here so we remember we should
> clean this up.

I've added the TODO. I'm not sure we should just explicitly look for
Prim.V1 though. For example there are the newtype wrappers for
(Repo)V1/V2. I also have some old experiments with making Prim.V1 more
general/modular, that I'd expect to be able to implement PrimConstruct
or something like it.

Still, I fully agree that the PrimConstruct class is very specific. I
introduced that and PrimClassify mainly to make it possible to overload
on prim types at all, not with the feeling that they were the one true
design.

>>   * tests: add withAllSequenceItems
> 
> (1) If you recognise that combineTestResults is just mconcat with a
> suitable SemiGroup instance I would expect you to replace this function
> with mconcat everywhere.

Yes, true, sent.

Though I now have slight second thoughts: are we happy that the instance
is canonical enough> I think it probably is but there are probably other
possible instances, such as rejecting if anything is rejected rather
than just if everything is rejected.

> (2) I get a warning about missing implementation of mappend (ghc-8.2). I
> think you should define mappend instead of (<>).

Sorry, fixed. I think we need mappend in Monoid and <> in Semigroup for now.
msg21920 (view) Author: ganesh Date: 2020-02-25.23:02:20
more review followups

3 patches for repository darcs-unstable@darcs.net:screened:

patch 4f8676c04b9f22b5a95ba778e1c640c64c24c544
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 22:33:47 GMT 2020
  * unwind: add comment about invariant

patch 82c590abe3ff78835131daa0c21853fd250220ce
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 22:59:55 GMT 2020
  * tests: reformat example

patch b58383bb4e9b281edd434f58e5aa3355ad844b32
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Feb 25 23:00:03 GMT 2020
  * tests: add some helpers to unwind examples
Attachments
msg21921 (view) Author: ganesh Date: 2020-02-25.23:06:07
On 24/02/2020 07:57, Ben Franksen wrote:

>>   * introduce concept of unwinding a conflict
> 
> I may be wrong, but to me these two statements contradict each other!
> Apparently we do have to commute context prims past if that is possible,
> which pretty strongly suggests that the context has to be minimal, at
> least with respect to commutation.

Yes, good point. I wrote the first comment before updating the code and
forgot about it. I've now rewritten it with a statement about the invariant.

The context isn't actually minimal with respect to commutation because
we can't remove things from it just because they commute: if we commute
them past the underlying they just end up in the other context. So in
the end we have to pick one. I did actually experiment with a structure
that stored the items that commute with the underlying in both contexts
(i.e. essentially caching both sides of the commutation), but it didn't
work out well.

But it is minimal with respect to cancellation of inverses.

> Can you simplify the examples with a few helper functions? E.g.
> 
> mkNamed hash = NamedP (rawPatchInfo "" "" "" ["Ignore-this: "++hash]
> path s = AnchoredPath [unsafeMakeName s])

Good idea, done.
History
Date User Action Args
2020-02-23 19:07:38ganeshcreate
2020-02-24 07:57:28bfsetfiles: + pEpkey.asc
messages: + msg21898
2020-02-24 08:28:07bfsetfiles: + pEpkey.asc
messages: + msg21900
2020-02-24 12:14:55ganeshsetmessages: + msg21905
2020-02-24 13:03:53bfsetfiles: + pEpkey.asc
messages: + msg21908
2020-02-24 18:32:06ganeshsetstatus: needs-screening -> needs-review
messages: + msg21912
2020-02-25 07:02:05ganeshsettitle: tests: always use prim patches for gener... (and 8 more) -> introduce unwind
2020-02-25 08:14:12ganeshsetfiles: + patch-preview.txt, tests_-add-a-todo-about-merging-hasprimconstruct_usesv1model.dpatch, unnamed
messages: + msg21918
2020-02-25 08:25:26ganeshsetmessages: + msg21919
2020-02-25 23:02:22ganeshsetfiles: + patch-preview.txt, unwind_-add-comment-about-invariant.dpatch, unnamed
messages: + msg21920
2020-02-25 23:06:07ganeshsetmessages: + msg21921
title: introduce unwind -> tests: always use prim patches for gener... (and 8 more)
2020-02-25 23:06:22ganeshsettitle: tests: always use prim patches for gener... (and 8 more) -> introduce unwind
2020-06-20 07:18:54bfsetstatus: needs-review -> accepted