Some of the test infrastructure improvements/refactorings
I added while testing unwind, with comments on some
of the key pieces.

Some of the shrinking is now complicated enough it would
almost benefit from tests of its own at some point in
the future.

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

patch 10bcc43af5991b468a15df0ef32948dec94fa1ce
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jan 31 17:18:36 GMT 2020
  * remove obsolete comment

patch 66f3f4db8029b85908991cd4c579e8da9bb02b34
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Feb  1 21:51:22 GMT 2020
  * tests: add fail method to instance Monad Fail
  
  This is needed for now in the MonadFail transition

patch dcb740c4e786947684f1f75480ccba930f5d4958
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Feb  7 22:48:17 GMT 2020
  * tests: add Shrinkable class

patch 117d1ead1a2b3c9ea0e90d4697c6137b9b58babb
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Feb  8 17:25:42 GMT 2020
  * tests: introduce concept of shrinking models

patch a463e7477e459d3cad5dfa32d286ab3efd759952
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb  9 00:22:38 GMT 2020
  * shrinking names and file content

patch ad0998a95bf7c7e09b29f5a1d7397ffb92de5e64
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb  9 19:31:31 GMT 2020
  * tests: introduce an explicit MergeableSequence type

patch 054b211cef28d017955dc69f027a3e8689a07b33
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb  9 19:52:24 GMT 2020
  * tests: add PropagateShrink and Effect for MergeableSequence

patch 9ec8b17389f2244302878945b17e26efdf3e118b
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Feb  9 22:39:23 GMT 2020
  * tests: better shrinking for MergeableSequence.ParMS

Attachments

• patch-preview.txt
• remove-obsolete-comment.dpatch
• unnamed

Whoa, this is a lot of code to take in!

Don't take this wrong, shrinking counter-examples is greatly appreciated.

I have a few preliminary comments/questions:

The Shrinkable class has only trivial implementations for
RepoPatchV1/2/3. It looks as if it is there for sequences of Named
patches only. If this is true, then why use a class at all and not just
plain helper functions?

The PropagateShrink class: reading the docs and studying the types did
not help me understand where the simplifying fixup originally comes
from. I could finally track this down to shrinkModel, and its
implementation for V1Model. What I couldn't find out is how/where
propagateShrink is actually /used/, other than to implement more
instances of PropagateShrink. I have tracked usage up to the shrink
method for WithArbitraryState2 but then I find no uses of that class
anywhere... and withStateShrinking is also nowhere used.

The MergeableSequence type is quite similar to the old Tree type and
clearly subsumes it. Can we get rid of Tree now and perhaps rename
MergeableSequence to MergeableTree? The Arbitrary.Generic module is now
quite large; does it make sense to move your additions to a separate module?

You have two TODO comments in your code. Are you planning to actually do
something about them? The one in Darcs.Test.Patch.Arbitrary.Named looks
a bit scary to me.

One last remark: there are property-based-testing frameworks out there
that don't require shrinking and automatically find smallest counter
examples. I am not sure they are up to the task for us, but if not I
would like to know why.

Attachments

• pEpkey.asc

Patches are already in screened.

On 10/02/2020 10:36, Ben Franksen wrote:

> The Shrinkable class has only trivial implementations for
> RepoPatchV1/2/3. It looks as if it is there for sequences of Named
> patches only. If this is true, then why use a class at all and not just
> plain helper functions?

That's a good point. I started out with a minimal implementation and
didn't go back to it. But I think the class could have non-trivial
implementations of at least shrinkAtStart and shrinkAtEnd for
non-conflicts, by shrinking the underlying prim. So I'd be inclined to
keep it as a class but with TODOs about what could be improved later.

> The PropagateShrink class: reading the docs and studying the types did
> not help me understand where the simplifying fixup originally comes
> from. I could finally track this down to shrinkModel, and its
> implementation for V1Model.

I'd better point to that explicitly in the comment.

> What I couldn't find out is how/where
> propagateShrink is actually /used/, other than to implement more
> instances of PropagateShrink. I have tracked usage up to the shrink
> method for WithArbitraryState2 but then I find no uses of that class
> anywhere... and withStateShrinking is also nowhere used.

Oh, sorry. I should have mentioned when sending in these patches that
they are preparatory, in that the new unwind tests use the new
functionality but I haven't submitted those yet.

I've pushed what's still to be submitted to a new branch:
https://hub.darcs.net/ganesh/darcs-unwind-draft-20200211/changes
in particular you can see it being used here:

https://hub.darcs.net/ganesh/darcs-unwind-draft-20200211/patch/e074079d5f0c5ea3843572bf9d73c76720d7bb71


> The MergeableSequence type is quite similar to the old Tree type and
> clearly subsumes it. Can we get rid of Tree now and perhaps rename
> MergeableSequence to MergeableTree? The Arbitrary.Generic module is now
> quite large; does it make sense to move your additions to a separate module?

Those both sound plausible.

> You have two TODO comments in your code. Are you planning to actually do
> something about them? The one in Darcs.Test.Patch.Arbitrary.Named looks
> a bit scary to me.

Thanks for the nudge, I'd sort of forgotten about them as I went.

In D.T.P.Arbitrary.Named, the comment is on 'shrinkInternally' for Named.

    -- TODO this isn't quite right because other patches might
    -- explicitly depend on this one

It's not great for shrinking to produce a bad test case, because it will
obscure the real error and make the debugging experience worse. On the
other hand it's not as bad as actually breaking darcs, and I'm not sure
if it's that likely to matter in practice.

Fixing it might mean reworking it using something like shrinkModel to
push a "name fixup" forwards to any patch that might depend on it. Or I
could perhaps just remove the "shrink pi" case, though it was very handy
in practice for simplifying test cases.

    -- TODO: Possibly @WithStartState (Sealed p)@ could be replaced with
       @Sealed (WithStartState2 p)@.

This one would need some investigation.

I'm happy in principle to look at all of the above items as part of this
review, but obviously it'd take a while so let me know which ones are
most important and which (if any) are ok to leave as "future work".

> One last remark: there are property-based-testing frameworks out there
> that don't require shrinking and automatically find smallest counter
> examples. I am not sure they are up to the task for us, but if not I
> would like to know why.

I think it'd be useful to try a mix of strategies in property-based
testing. The obvious alternative is something exhaustive like lazy
smallcheck, with the obvious possibility that it might be too slow. We
should check if there are libraries that help with overloading over the
different approaches.

I've added some comments. I'll leave it a little while before pushing
to screened to avoid unnecessary churn if there are any immediate comments
on how they can be improved further.

1 patch for repository darcs-unstable@darcs.net:screened:

patch 2c4ba63f5a588168fa52facc3301318fb9365bee
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Feb 12 13:01:52 GMT 2020
  * tests: add some more comments about ShrinkModel/PropagateShrink

Attachments

• patch-preview.txt
• tests_-add-some-more-comments-about-shrinkmodel_propagateshrink.dpatch
• unnamed

>> The Shrinkable class [...]
> [...] could have non-trivial
> implementations of at least shrinkAtStart and shrinkAtEnd for
> non-conflicts, by shrinking the underlying prim. So I'd be inclined to
> keep it as a class but with TODOs about what could be improved later.

Okay.

>> What I couldn't find out is how/where
>> propagateShrink is actually /used/,
> [..] they are preparatory, in that the new unwind tests use the new
> functionality but I haven't submitted those yet.

So the existing tests don't profit from the cool new shrinker? That's
quite disappointing! Is there a fundamental reason for that?

> It's not great for shrinking to produce a bad test case, because it will
> obscure the real error and make the debugging experience worse. On the
> other hand it's not as bad as actually breaking darcs, and I'm not sure
> if it's that likely to matter in practice.
>
> Fixing it might mean reworking it using something like shrinkModel to
> push a "name fixup" forwards to any patch that might depend on it. Or I
> could perhaps just remove the "shrink pi" case, though it was very handy
> in practice for simplifying test cases.

Sounds like a lot of complication for questionable gain. I'd vote for a
better explanation in the comment and leave it at that, for the moment.

>     -- TODO: Possibly @WithStartState (Sealed p)@ could be replaced with
>        @Sealed (WithStartState2 p)@.
>
> This one would need some investigation.

Unless there is an easy way to try this and quickly see if the idea
works out, I wouldn't bother.

> I'm happy in principle to look at all of the above items as part of this
> review, but obviously it'd take a while so let me know which ones are
> most important and which (if any) are ok to leave as "future work".

Making the existing tests (for RepoPatches, of course, not prims) profit
from the new shrinker would certainly be my top priority.

> I think it'd be useful to try a mix of strategies in property-based
> testing. The obvious alternative is something exhaustive like lazy
> smallcheck, with the obvious possibility that it might be too slow. We
> should check if there are libraries that help with overloading over the
> different approaches.

A while ago I added a dependency on leancheck for a specific use case
(harness/Darcs/Test/Misc/Graph.hs). I think the way to go is to just
start working on a leancheck generator for V1Model and see if we can get
a grip on the state space explosion. We could, for instance, limit file
and directory names to a single alphabetic character. (Writing leancheck
generators is much easier than writing QC generators.)

________________________________

Helmholtz-Zentrum Berlin für Materialien und Energie GmbH

Mitglied der Hermann von Helmholtz-Gemeinschaft Deutscher Forschungszentren e.V.

Aufsichtsrat: Vorsitzender Dr. Volkmar Dietz, stv. Vorsitzende Dr. Jutta Koch-Unterseher
Geschäftsführung: Prof. Dr. Bernd Rech (Sprecher), Prof. Dr. Jan Lüning, Thomas Frederking

Sitz Berlin, AG Charlottenburg, 89 HRB 5583

Postadresse:
Hahn-Meitner-Platz 1
D-14109 Berlin

On 12/02/2020 17:01, Ben Franksen wrote:

>>> What I couldn't find out is how/where
>>> propagateShrink is actually /used/,
>> [..] they are preparatory, in that the new unwind tests use the new
>> functionality but I haven't submitted those yet.
> 
> So the existing tests don't profit from the cool new shrinker? That's
> quite disappointing! Is there a fundamental reason for that?

No, just that I was focused on my shiny new code (unwind); writing tests
for unwind was one level into that, writing better shrinking for the
unwind failures was two levels into that, and there I stopped.

But talking about the shrinking in isolation is a good time to focus on
that. A good starting point would be to get rid of
arbitraryMergedSequence. Following where it goes, it's used by
arbitrary[Sized]Sequence/arbitraryRL which in turn are used by the
Arbitrary instances for Single, Pair, Triple, Fork and Sequence.

To get the better shrinking, we need to carry around the raw test cases
(WithState2 MergeableSequence) all the way up to the test cases that
ultimately use them. I think that the route to doing this is probably
via refactoring withSingle/withPair etc.

A rough outline would be first to specialise their types to be only as
general as the corresponding Arbitrary instances, and then rework them
to look like withStateShrinking, or to use it. I think that's actually
roughly how my development process went for the new code, I first
introduced a 'withMergedSequence' that looked like that existing
pattern, then refactored it into what I have now.

The concern with changing around QuickCheck code is accidentally
breaking the coverage of the existing tests without realising it. I'm
not sure how to guard against that cheaply.

On 12/02/2020 20:12, Ganesh Sittampalam wrote:

> To get the better shrinking, we need to carry around the raw test cases
> (WithState2 MergeableSequence) all the way up to the test cases that
> ultimately use them. I think that the route to doing this is probably
> via refactoring withSingle/withPair etc.
> 
> A rough outline would be first to specialise their types to be only as
> general as the corresponding Arbitrary instances, and then rework them
> to look like withStateShrinking, or to use it. I think that's actually
> roughly how my development process went for the new code, I first
> introduced a 'withMergedSequence' that looked like that existing
> pattern, then refactored it into what I have now.

Actually I think this is just a question of replacing withSingle etc
with withStateShrinking, but I'm having a bit of trouble with the
instances for reasons I don't understand yet (since the same instances
ought to work in both cases). I'll keep chasing that down.

> I've added some comments. I'll leave it a little while before pushing
Thanks! The comments are perfect. Much easier now to understand how the
pieces fit together.

Attachments

• pEpkey.asc

I had a go at this TODO and decided against it.

1 patch for repository darcs-unstable@darcs.net:screened:

patch f689ef5149917e8951938c1b25e29a7c5dec0e7f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Feb 15 14:21:25 GMT 2020
  * tests: remove invalid TODO
  
  many of the uses of WithStartState are with single-parameter patches
  like Tree so can't be easily replaced by WithStartState2.

Attachments

• patch-preview.txt
• tests_-remove-invalid-todo.dpatch
• unnamed

Trying to implement sorting of Nons (see patch1971), I stumbled over the
fact that you have implemented PropagateShrink for each RepoPatch type
separately. This is because you are accessing their internals. Looking
closer at these implementations I see that you try to commute the prim
past the RepoPatch if the latter is not just a prim, except for
RepoPatchV3.

I investigated and found out that this is indeed hard to do because of
the NamedPrim wrapper. We actually have to use fromAnonymousPrim to lift
the prim to a RepoPatchV3. I /think/ this should be fine, though, since
when a prim commutes past a V3 conflictor, then it should commute past
the effect, all conflicts (including their context) and the patch
itself, so we don't keep a reference to the anonymous prim inside the
commuted conflictor.

However, I wonder whether this kind of shrinking is sound at all for V3.
Suppose we shrink an unconflicted V3 patch by commuting a prim past it,
but then it gets stuck in the next patch. Now what if after that we have
a conflictor with a reference to the first patch. Isn't this reference
now invalid?

More generally speaking, I wonder if commuting a prim past a p1, such
that it gets stuck later on p2, could change whether p1 and p2 commute.
Wouldn't this invalidate the whole sequence?

Attachments

• pEpkey.asc

[this is one of those patches that started out with a bad title and is
now suffering from ping pong as we reply to mails :-)]

On 22/02/2020 13:03, Ben Franksen wrote:

> However, I wonder whether this kind of shrinking is sound at all for V3.
> Suppose we shrink an unconflicted V3 patch by commuting a prim past it,
> but then it gets stuck in the next patch. Now what if after that we have
> a conflictor with a reference to the first patch. Isn't this reference
> now invalid?

Can you give an example?

> More generally speaking, I wonder if commuting a prim past a p1, such
> that it gets stuck later on p2, could change whether p1 and p2 commute.
> Wouldn't this invalidate the whole sequence?

I'm not quite sure without thinking more deeply, but I have a couple of
thoughts.

Firstly, if shrinking produces a technically legal patch sequence but
the test doesn't fail any more because there's some fundamental change,
that's absolutely normal. On the other hand if shrinking produces an
invalid patch sequence it can cause some confusion and wasted time for
the developer, so we'd certainly like to avoid that.

Secondly, I am not actually sure that this case is worth having in the
first place, and I suspect I only wrote it that way because I could. The
premise of MergeableSequence is that we keep and shrink only
unconflicted patches. So if we use that consistently we shouldn't
actually care about this case at all. Maybe it would be better to change
MergeableSequence p to store (PrimOf p), and to drop the PropagateShrink
instance for RepoPatches entirely.

> [this is one of those patches that started out with a bad title and is
> now suffering from ping pong as we reply to mails :-)]

Oops ;-) I replied to the first email in the thread, my bad.

>> However, I wonder whether this kind of shrinking is sound at all for V3.
>> Suppose we shrink an unconflicted V3 patch by commuting a prim past it,
>> but then it gets stuck in the next patch. Now what if after that we have
>> a conflictor with a reference to the first patch. Isn't this reference
>> now invalid?
> 
> Can you give an example?

See below.

>> More generally speaking, I wonder if commuting a prim past a p1, such
>> that it gets stuck later on p2, could change whether p1 and p2 commute.
>> Wouldn't this invalidate the whole sequence?
> 
> I'm not quite sure without thinking more deeply, but I have a couple of
> thoughts.

Without looking at the code for propagateShrink for prims, I assumed
that it uses, among other things, coalescing to simplify a given patch.
I just verified that's the case. But we know that coalescing does not
preserve commutation behavior.

Now, if a later patch in the sequence is in conflict with the one that
has absorbed the fixup, then it could become invalid by e.g. no longer
conflicting with it. (It should be easy to construct a concrete
example.) A problem could occur even if p2 is unconflicted, but a later
p3 is in conflict with p1. For example, suppose that absorbing the fixup
makes p1 :> p2 commute when they didn't before. This means p2 should no
longer be in the context of the Contexted patch stored in p3. Etc.

This means that even doing this for an unconflicted RepoPatch is wrong,
unless we can be sure that the whole sequence is unconflicted. More
precisely, we must not modify a patch that is part of a conflict
anywhere in the sequence.

> Firstly, if shrinking produces a technically legal patch sequence but
> the test doesn't fail any more because there's some fundamental change,
> that's absolutely normal.

Agreed.

> On the other hand if shrinking produces an
> invalid patch sequence it can cause some confusion and wasted time for
> the developer, so we'd certainly like to avoid that.

Yes.

> Secondly, I am not actually sure that this case is worth having in the
> first place, and I suspect I only wrote it that way because I could.

I suspected that, since you left out the case (returning Nothing) for
V3, which is not as straight forward as for V1 and V2 because of the
NamedPrim wrappers.

> The
> premise of MergeableSequence is that we keep and shrink only
> unconflicted patches. So if we use that consistently we shouldn't
> actually care about this case at all.

I also understood the premise as such. So the immediate "fix" here is
simply to make it an error to apply propagateShrink to a conflicted
patch. Or rather, throw an error if /any/ element of the sequence is
conflicted, since in case our fixup gets absorbed, we never try to
propagate it further up the chain.

Note this is just to be on the safe side and eliminate dead code. I do
believe that we actually apply shrinking only to the unmerged and thus
unconflicted sequence.

> Maybe it would be better to change
> MergeableSequence p to store (PrimOf p), and to drop the PropagateShrink
> instance for RepoPatches entirely.

I am not sure we can do that without major disruption. Perhaps it is
worth to try that but I think having a precondition / partial function
here is also fine.

Attachments

• pEpkey.asc

Here is a quick shot at replacing the offending cases with calls to error.
Not screening this yet in case I made a stupid mistake.

1 patch for repository http://darcs.net/screened:

patch 35058bffb6491d81286ee82d42dbf49d6f17dc76
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Feb 22 16:16:39 CET 2020
  * harness: make sure we never try to shrink a seqence with conflicted patches
  
  This replaces the corresponding cases in the PropagateShrink instances for
  RepoPatch types with error calls. In the instance for Named, we explicitly
  check that all contained repopatches are unconflicted.

Attachments

• harness_-make-sure-we-never-try-to-shrink-a-seqence-with-conflicted-patches.dpatch
• patch-preview.txt
• unnamed

Why not just let the error cases for the individual RepoPatches handle
it, rather than doing a second check in Named?

> This means that even doing this for an unconflicted RepoPatch is wrong,
> unless we can be sure that the whole sequence is unconflicted. More
> precisely, we must not modify a patch that is part of a conflict
> anywhere in the sequence.

Yes, you're right. So we should definitely never try to shrink in the
presence of actual conflicts.

It feels a bit messy. Let me have a go at using PrimOf instead first 
before you screen it.

[I meant to send this to the tracker, sorry for duplicates]

> Why not just let the error cases for the individual RepoPatches handle
> it, rather than doing a second check in Named?

Because if a fixup actually gets absorbed, then there is nothing left to
propagate through the rest of the sequence, so we don't call
propagetShrink on them and thus no error. In fact there is still a hole
because we don't check this one level up i.e. before propagating a fixup
through a sequence of Named patches.

Attachments

• pEpkey.asc

Here's a draft of getting rid of various instances for RepoPatches

Unfortunately it needed a bit more type family machinery, principally
because we need to construct MergeableSequence (Named p) as well as
MergeableSequence p - not in current screened, but in my unwind patches.

So if we want to store a "prim only" version inside MergeableSequence,
we need some way of getting both from RepoPatch prim to prim as well
as Named (RepoPatch prim) to Named prim. That's the new OnlyPrim
type family, with a containing class "PrimBased".

It's unfortunate, but overall I feel it's the right thing to do: it
means we can remove several slightly dubious instances for RepoPatches.
Without this we'll be continually writing code where we have to assume
there are no conflicts in a RepoPatch.

1 patch for repository darcs-unstable@darcs.net:screened:

patch 64e383bff658f2d8f7ec44c665482e5b5818df9b
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Feb 22 20:51:22 GMT 2020
  * WIP: PrimBased

Attachments

• patch-preview.txt
• unnamed
• wip_-primbased.dpatch

> Unfortunately it needed a bit more type family machinery, principally
> because we need to construct MergeableSequence (Named p) as well as
> MergeableSequence p - not in current screened, but in my unwind patches.

Hmm, I was wondering why there is no 'instance PrimBased (Named p)'.
Your remark explains that (I looked at your changes before reading it).

I would really like to see all the necessary machinery for Named patches
being added. A lot of that already seems to be there, so why not go all
the way and then actually use it to test properties for Named patches?

> So if we want to store a "prim only" version inside MergeableSequence,
> we need some way of getting both from RepoPatch prim to prim as well
> as Named (RepoPatch prim) to Named prim. That's the new OnlyPrim
> type family, with a containing class "PrimBased".

If one wants to avoid partial functions/methods, this seems to be the
way to go.

> It's unfortunate, but overall I feel it's the right thing to do: it
> means we can remove several slightly dubious instances for RepoPatches.
> Without this we'll be continually writing code where we have to assume
> there are no conflicts in a RepoPatch.

I am fine with PrimBased/OnlyPrim. There is only minimal typing
overhead, no more than I would expect is needed to get rid of the
partial methods, type inference doesn't seem to suffer, and signatures
don't become unreadable. Looks like a clear win.

However, I stumbled over one detail that isn't immediately obvious to
me. You have now added vacuous instances Shrinkable Prim for various
Prim types e.g.

instance Shrinkable V1.Prim where
  shrinkInternally _ = []
  shrinkAtEnd _ = []
  shrinkAtStart _ = []

It is unclear to me why these are needed, and I find them a bit ugly. Is
there a way to get rid of them, and if not, why are they needed?

Attachments

• pEpkey.asc

On 23/02/2020 08:04, Ben Franksen wrote:

> I would really like to see all the necessary machinery for Named patches
> being added. A lot of that already seems to be there, so why not go all
> the way and then actually use it to test properties for Named patches?

I did it, but it's tangled up with my draft unwind changes. I just
uploaded the current state to darcs hub:

https://hub.darcs.net/ganesh/darcs-unwind-draft-20200223/browse/harness/Darcs/Test/Patch/Arbitrary/Named.hs

I could move the extra instances over to this patch but they still
wouldn't be used until I submit the unwind changes. That ought to be
soon as I've worked through most of the necessary cleanups.

> However, I stumbled over one detail that isn't immediately obvious to
> me. You have now added vacuous instances Shrinkable Prim for various
> Prim types e.g.
> 
> instance Shrinkable V1.Prim where
>   shrinkInternally _ = []
>   shrinkAtEnd _ = []
>   shrinkAtStart _ = []
> 
> It is unclear to me why these are needed, and I find them a bit ugly. Is
> there a way to get rid of them, and if not, why are they needed?

This is basically the same explanation as in

http://bugs.darcs.net/msg21791

The vacuous instances for RepoPatch have now moved down a level to Prim.
While I probably could get rid of the instances, I think it's better to
leave them as TODOs to expand on later.

Here's a final version of the PrimBased patch.

I've added the instances for Named (unused for now) and
some comments on the vacuous instances of Shrinkable for
prim types.

I'd like to screen this now so I can move on to finalising
and submitting the last disruptive part of my unwind tests,
before that develops any further conflicts. Let me know
if you object.

1 patch 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.

Attachments

• patch-preview.txt
• tests_-always-use-prim-patches-for-generating_shrinking.dpatch
• unnamed

Ah, okay. So, just to get this straight: we currently do not shrink
patches per se. We merely shrink the start state and try to propagate
the resulting fixup, hopefully shrinking the patches as a result. Correct?

Attachments

• pEpkey.asc

On 23/02/2020 21:42, Ben Franksen wrote:

> Ah, okay. So, just to get this straight: we currently do not shrink
> patches per se. We merely shrink the start state and try to propagate
> the resulting fixup, hopefully shrinking the patches as a result. Correct?

shrinkAtStart and shrinkAtEnd do things on lists of patches (dropping
elements). shrinkInternally doesn't do anything anywhere.

It may be that shrinkInternally will always be useless and should be
removed. I was playing around to some extent when I wrote these new
classes, with a primary goal of making things properly modular.

Ganesh, sorry for aksing these stupid questions. When I looked at the
first bundle where you introduce the Shrinkable class I must have
completely missed its definition in D.T.P.A.Shrink which is well documented.

I have taken a closer look at that now. Yes the implementation for
sequences and pairs is non-trivial. But since it is based on the
instances for the components, it still doesn't do anything. Yet. This is
not crititcism, I just want to understand which part of the code is
actually actively shrinking things and which is mere infrastructure for
future (or pending) improvements.

Regarding the implementations for pairs and FL. I have looked (again) at
the documentation for the shrink method in QC. It says the returned list
should start with the most aggressive shrinks, suggesting that QC stops
at the first element of the list that fails the property under test. For
sequences this suggests to me that we should put (Sealed/FlippedSeal
NilFL) at the head of the result for both shrinkAtStart and shrinkAtEnd.

Attachments

• pEpkey.asc

On 24/02/2020 06:58, Ben Franksen wrote:

> I have taken a closer look at that now. Yes the implementation for
> sequences and pairs is non-trivial. But since it is based on the
> instances for the components, it still doesn't do anything. Yet. This is
> not crititcism, I just want to understand which part of the code is
> actually actively shrinking things and which is mere infrastructure for
> future (or pending) improvements.

The instances for sequences actually drop patches. You don't need to do
any shrinking of the components to get a smaller test case that way.

> Regarding the implementations for pairs and FL. I have looked (again) at
> the documentation for the shrink method in QC. It says the returned list
> should start with the most aggressive shrinks, suggesting that QC stops
> at the first element of the list that fails the property under test. For
> sequences this suggests to me that we should put (Sealed/FlippedSeal
> NilFL) at the head of the result for both shrinkAtStart and shrinkAtEnd.

Yes, probably. I didn't pay too much attention to making shrinking fast,
getting something partially effective has taken long enough :-)

Overall I am not actually entirely sure that Shrinkable in its current
form is that useful. shrinkInternally may not have any useful
implementation, and shrinkAtStart doesn't fit that well with the idea of
propagating a shrinking fixup from the start of the repository. It might
be that it would be better to integrate Shrinkable into the
ShrinkModel/PropagateShrink infrastructure instead.

But as I've said before, good shrinking is complicated enough that it
may well need tests of its own.

> The instances for sequences actually drop patches.

I must be missing something because I don't see that they do.

>> Regarding the implementations for pairs and FL. I have looked (again) at
>> the documentation for the shrink method in QC. It says the returned list
>> should start with the most aggressive shrinks, suggesting that QC stops
>> at the first element of the list that fails the property under test. For
>> sequences this suggests to me that we should put (Sealed/FlippedSeal
>> NilFL) at the head of the result for both shrinkAtStart and shrinkAtEnd.
> 
> Yes, probably. I didn't pay too much attention to making shrinking fast,
> getting something partially effective has taken long enough :-)

My remark was not about performance at all. I think QC assumes that the
shrink list is sorted by "size" (increasing) and /stops/ searching at
the first element that fails the test. In my book this means that not
starting the result list with the smallest possible shrinking means that
shrinking will not give the best possible results.

It is quite possible that I am confused about how shrinking works. If
that is the case please enlighten me.

Attachments

• pEpkey.asc

On 24/02/2020 08:16, Ben Franksen wrote:

>> The instances for sequences actually drop patches.
> 
> I must be missing something because I don't see that they do.

For example:

> instance (Commute p, Shrinkable p) => Shrinkable (FL p) where
[...]
>   shrinkAtStart ps = do
>     q :> qs <- headPermutationsFL ps
>     FlippedSeal qs:map (mapFlipped (:>: qs)) (shrinkAtStart q)

The first shrink result is 'FlippedSeal qs' which omits one of the
patches from 'ps'.

> My remark was not about performance at all. I think QC assumes that the
> shrink list is sorted by "size" (increasing) and /stops/ searching at
> the first element that fails the test. In my book this means that not
> starting the result list with the smallest possible shrinking means that
> shrinking will not give the best possible results.
> 
> It is quite possible that I am confused about how shrinking works. If
> that is the case please enlighten me.

Shrinking is iterative and a shrink function is only expected to produce
"immediate" shrinks. For one iteration, QC will take the first shrink
that fails the test, but then will attempt to further shrink that
result. It will only terminate if there are *no* shrinks that fail the test.

So any final result from shrinking will be locally minimal: there will
be no further shrinks possible to that value. There certainly could be
weird failures where e.g. lists of size 4 and 6 fail, but none of size
5, and so we'd get stuck at 6 if we just shrink by 1 element each time.
But more of the time it's just about performance, i.e. the faster we
find smaller shrinks the less work we do.

> The first shrink result is 'FlippedSeal qs' which omits one of the
> patches from 'ps'.

Sorry for being dense. I just couldn't see that. All clear now.

> Shrinking is iterative and a shrink function is only expected to produce
> "immediate" shrinks. For one iteration, QC will take the first shrink
> that fails the test, but then will attempt to further shrink that
> result. It will only terminate if there are *no* shrinks that fail the test.

Okay... I didn't know about that.

> So any final result from shrinking will be locally minimal: there will
> be no further shrinks possible to that value. There certainly could be
> weird failures where e.g. lists of size 4 and 6 fail, but none of size
> 5, and so we'd get stuck at 6 if we just shrink by 1 element each time.
> But more of the time it's just about performance, i.e. the faster we
> find smaller shrinks the less work we do.

I think I understand now, thanks for the explanation. So we drop one
patch from e.g. the head of the sequence. If that fails the test, QC
will try to further shrink that sequence, etc. If they all fail, then it
will finally try NilFL. But if one doesn't we'll be stuck. If this is
so, then shrinking a sequence with something like 'reverse . tailsFL' in
one go looks like an easy improvement.

Attachments

• pEpkey.asc

Go ahead and screen. The patches look good and we can sort out possible
improvements later.

________________________________

Helmholtz-Zentrum Berlin für Materialien und Energie GmbH

Mitglied der Hermann von Helmholtz-Gemeinschaft Deutscher Forschungszentren e.V.

Aufsichtsrat: Vorsitzender Dr. Volkmar Dietz, stv. Vorsitzende Dr. Jutta Koch-Unterseher
Geschäftsführung: Prof. Dr. Bernd Rech (Sprecher), Prof. Dr. Jan Lüning, Thomas Frederking

Sitz Berlin, AG Charlottenburg, 89 HRB 5583

Postadresse:
Hahn-Meitner-Platz 1
D-14109 Berlin

On 24/02/2020 13:01, Ben Franksen wrote:

> I think I understand now, thanks for the explanation. So we drop one
> patch from e.g. the head of the sequence. If that fails the test, QC
> will try to further shrink that sequence, etc. If they all fail, then it
> will finally try NilFL. But if one doesn't we'll be stuck. If this is
> so, then shrinking a sequence with something like 'reverse . tailsFL' in
> one go looks like an easy improvement.

Note it's only a clear improvement if dropping one element doesn't help
but dropping two does.

It could also slow down shrinking substantially if most shrinks don't
work (i.e. the test succeeds after shrinking). The instance for normal
lists tries dividing the list in 2, 4, 8 etc as well as removing each
individual element:

https://hackage.haskell.org/package/QuickCheck-2.13.2/docs/src/Test.QuickCheck.Arbitrary.html#shrinkList

> Note it's only a clear improvement if dropping one element doesn't help
> but dropping two does.
> 
> It could also slow down shrinking substantially if most shrinks don't
> work (i.e. the test succeeds after shrinking). The instance for normal
> lists tries dividing the list in 2, 4, 8 etc as well as removing each
> individual element:
> 
> https://hackage.haskell.org/package/QuickCheck-2.13.2/docs/src/Test.QuickCheck.Arbitrary.html#shrinkList

Fascinating. Professional shrinking seems to be a black art. I'll
refrain from further comments.

Attachments

• pEpkey.asc

>   * remove obsolete comment

Okay.

>   * tests: add fail method to instance Monad Fail

Okay.

>   * tests: add Shrinkable class

Okay. We already discussed this at length. ATM, only the instance for
sequences does actual shrinking.

>   * tests: introduce concept of shrinking models

Okay. I haven't studied the code in detail but I believe you know what
you did there. And the idea sound quite reasoinable.

>   * shrinking names and file content

Okay. This seems to be the actual shrinking for V1Model.

>   * tests: introduce an explicit MergeableSequence type

Okay. Again, the idea makes sense to me, but I haven't studied the
details. I guess the worst that can happen is that we get no shrinking
or that the shrinker hangs. Can fix such problems when they appear.

>   * tests: add PropagateShrink and Effect for MergeableSequence

Okay.

>   * tests: better shrinking for MergeableSequence.ParMS

Okay.

+      -- Unless the shrinking prim disappears on both branches of the
merge,
+      -- we'll need to try to recalculate it for the result of the
merge - trying
+      -- to use propagateShrink a second time wouldn't guarantee the right
+      -- contexts. (This is a bit complicated to see, hence all the
type signatures
+      -- in this function.)

I must say that all the type signatures here don't make me see it
either. They make me see why a function like recalcShrink is needed, but
not why its implementation works.

Accepted pending review of follow-ups.

Attachments

• pEpkey.asc

>   * tests: remove invalid TODO
>   
>   many of the uses of WithStartState are with single-parameter patches
>   like Tree so can't be easily replaced by WithStartState2.

Yes. Okay.

Attachments

• pEpkey.asc

>   * tests: always use prim patches for generating/shrinking

This one depends on patches in other bundles. It would have been better
if you had sent this follow-up as a separate bundle.

I'll mark as accepted-pending-tests until I reviewed the other stuff.

Attachments

• pEpkey.asc

On 28/02/2020 09:48, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
>>   * tests: always use prim patches for generating/shrinking
> 
> This one depends on patches in other bundles. It would have been better
> if you had sent this follow-up as a separate bundle.
> 
> I'll mark as accepted-pending-tests until I reviewed the other stuff.

I guess this is a question of workflow/logical grouping that it'd be
helpful for us to agree on.

I like to keep a single logical group of patches in a single ticket
(patchXXXX) on the patch tracker, which I think is what you mean by
bundle here.

If there are followups that belong in the same review, I put them in the
same ticket because then the review can be accepted as a single entity
that takes into account both the initial patches and the followups.

If this means we end up with patches/dependencies interleaved with other
patches in screened, I don't see this as a problem. Once something is
reviewed, I just move it to "accepted-pending-tests", but might not push
it to reviewed immediately. Every so often, I sweep up any unblocked
accepted-pending-tests patches, check that they build and the tests
pass, and push them to reviewed. I might also do this with parts of a
review bundle after checking that the intermediate state wouldn't be
fundamentally broken in some subtle way.

I actually found it a bit confusing when you followed up on a review in
another bundle recently because I then had to keep track of the
relationship between the two, though it wasn't much of a big deal. I'm
ok with doing it that way consistently if it works a lot better for you.