For discussion only. As I wrote this message I have become
convinced something better is needed.

This makes a start on rolling out the new shrinking infrastructure
to some of the existing tests, as discussed in patch1979.

Part of the work is replacing specialised instances and code with
modular ones that compose cleanly. For example the Arbitrary
instances for Pair (Sealed2 (p :> p)) and
Triple (Sealed2 (p :> p :> p)) can come from an ArbitraryState
instance for (p :> q).

I think we really have to move in that direction if we want
our testing infrastructure to be reusable in different situations.

But specialised instances often also have specialised generators.
The old instances generated a list of patches via a "merged
sequence" and took an arbitrary element from it. The replacement
will always start from "aSmallRepo", and (I think) will never
contain a conflict.

So firstly I think we need a more sophisticated approach to
setting up the context of test cases. Also, probably we should
actually evaluate the results by looking at the complexity of the
generated patches. I'm not sure how much classification infrastructure
we have already.

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

patch 6972a7598268b914b4a19255485f85f9426b6af7
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Feb 13 18:35:40 GMT 2020
  * tests: replace withSingle with withStateShrinking

patch 808a679176b765c98efe009c187321388a8bb565
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Feb 13 18:46:34 GMT 2020
  * tests: replace withPair/withTriple with withStateShrinking

Attachments

• patch-preview.txt
• tests_-replace-withsingle-with-withstateshrinking.dpatch
• unnamed

The more I think about it the more obvious it becomes that this isn't the 
right approach, because using merged sequences is fundamental to
generating good test cases of RepoPatches. But composability is also
quite important so I will keep thinking about it.

Hmmm, I think I may have an idea what the problem is. My (not quite so)
new generators produce a test sequence, from which we then may pick
one, two, or three consecutive patches to test our patch properties and
invariants. This sequence contains (possibly conflicted) merge results,
as well as new patches that may depend on conflicted ones. To apply your
approach would require that we remember the original state that the
sequence started out with, which seems doable. But then we would also
need to propagate the simplifying fixup through conflictors! I am not
sure you can do that. On the other hand, we can try to propagate the
fixup through the (unconflicted) branches and then re-merge, but that
works only as far as any conflict and cannot include a possible conflict
resolution, since that depends on patches in both branches, or can it?

Attachments

• pEpkey.asc

On 14/02/2020 01:06, Ben Franksen wrote:

> Hmmm, I think I may have an idea what the problem is. My (not quite so)
> new generators produce a test sequence, from which we then may pick
> one, two, or three consecutive patches to test our patch properties and
> invariants. This sequence contains (possibly conflicted) merge results,
> as well as new patches that may depend on conflicted ones. To apply your
> approach would require that we remember the original state that the
> sequence started out with, which seems doable. But then we would also
> need to propagate the simplifying fixup through conflictors! I am not
> sure you can do that. On the other hand, we can try to propagate the
> fixup through the (unconflicted) branches and then re-merge, but that
> works only as far as any conflict and cannot include a possible conflict
> resolution, since that depends on patches in both branches, or can it?

I think that's an orthogonal difficulty. My shrinking always works on
the unconflicted patches and then we merge again afterwards. I also do
make an effort to propagate shrinks through both branches, and then
recalculate the shrinking fixup after the merge by coalescing - see
recalcShrink. If that succeeds the new shrinking fixup can be used to
simplify the conflictor.

However I'm not sure how successful that particular code actually is, in
part because the original version I wrote and actually used on Unwind
turned out to be wrong (it had some unsafeCoerces that were hiding the
mistakes). I discovered that and rewrote it when cleaning up the
shrinking for submission, but haven't actually used it at all, which is
part of the reason for my comment in patch1979 that maybe we should
actually test shrinking. Overall, the new shrinking was moderately
effective at reducing real test cases, but I still ended up doing a lot
of manual reduction too.

The real problem with my new code in this patch is that it's just overly
simplistic. If we want to use the PropagateShrink MergeableSequence
instance, then MergeableSequence has to be kept around! I think my
original description in http://bugs.darcs.net/msg21801 was actually
right, I just got carried away when actually working on it and
oversimplified. I'll have another go at that strategy.

My greatest reservation at the moment is that I am not sure your
arbitraryMergeableSequence is actually able to generate conflict
/resolutions/ i.e. that it generates new patches that possibly depend on
conflicts i.e. /after/ merging. This is of utmost importance because
otherwise we miss out on a whole class of possible scenarios.

Attachments

• pEpkey.asc

On 14/02/2020 09:08, Ben Franksen wrote:

> My greatest reservation at the moment is that I am not sure your
> arbitraryMergeableSequence is actually able to generate conflict
> /resolutions/ i.e. that it generates new patches that possibly depend on
> conflicts i.e. /after/ merging. This is of utmost importance because
> otherwise we miss out on a whole class of possible scenarios.

It should do. I carefully wrote it to preserve the existing behaviour of
arbitraryMergedSequence:

https://hub.darcs.net/darcs/darcs-screened/patch/ad0998a95bf7c7e09b29f5a1d7397ffb92de5e64

We can still get a conflict resolution by generating a parallel sequence
followed by a single patch. It would be expressed by something like
SeqMS (ParMS ps1 ps2) p; if ps1 and ps2 conflict then p can be a
resolution if it touches the right thing.

The difference is that after generating the merged patch and using it to
determine the returned repo state, we store the unmerged patch in the
data structure, and reconstruct the merged one on-demand.

BTW working on this I may have reconstructed a bit more of the
motivation for 'TreeWithFlattenPos', which we discussed last year:

https://lists.osuosl.org/pipermail/darcs-devel/2019-June/019705.html

The existing Arbitrary instance for Single, Pair, etc generates a list
of patches and then chooses an arbitrary element from it.

If we want to remember the source structure instead of the result,
then we need to remember which element we chose. That's the "flatten
position".

On the other hand, just picking the last element seems reasonable
enough so I'll probably do that instead of adding the extra 
complication.

Another issue is the need to generate MergeableSequences of
a minimum length (1, 2 or 3).

With things like TreeWithFlattenPos, there's a bunch of infrastructure 
(TestGenerator, properties, testConditional) to propagate the 
conditions all the way to the QuickCheck property. I guess we should
just reuse that, although it does feel a bit heavyweight.

All this discussion shows why we may need to test our tests somehow :-)

Ah, good. Yes you can do that now with the WithState2 thing, I forgot
about that. Cool. Then it's merely an engineering matter... and I'll
leave that to you ;-)

Attachments

• pEpkey.asc

> BTW working on this I may have reconstructed a bit more of the
> motivation for 'TreeWithFlattenPos', [...]
> With things like TreeWithFlattenPos, there's a bunch of infrastructure 
> (TestGenerator, properties, testConditional) to propagate the 
> conditions all the way to the QuickCheck property. I guess we should
> just reuse that, although it does feel a bit heavyweight.

I think what we should do here is not to take an arbitrary subsequence
of length 1/2/3, but -as you suggested previously- just take the last
1/2/3 elements from an arbitrary sequence. Given how we construct a
MergableSequence recursively this should be just as general.

I always hated TestGenerator, please let that thing die!

The machinery in Darcs.Test.Patch.Arbitrary.RepoPatch is, I think, quite
easy to understand and use. You just need to adapt it to make use of the
added information we now have in the MergeableSequence type. It also
shouldn't be too hard to generalize it so that we can use it for named
patches.

Attachments

• pEpkey.asc

I _think_ this variant should preserve the existing coverage.
The bSized that was on arbitrarySizedSequence was already replicated
in instance ArbitraryState MergeableSequence.

But without coverage tests it's hard to be sure. Maybe we could use
checkCoverage from QuickCheck to be sure of that.

This also replaces the existing shrinking for Fork and WithStartModel.
I'm not sure the WithState2-based shrinking is a perfect replacement,
but I think it's better overall. Also reducing the different ways
we handle shrinking will make it easier to make general improvements.

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

patch b7b03658ee2260354916d101b169e6fd84998c56
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Feb 14 06:51:31 GMT 2020
  * specialise the types of withSingle etc
  
  The new types reflect their actual usage and will make it
  easier to move logic around.

patch 2f1631f5733447e28a0c529ecd47523d4edafff7
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Feb 15 09:29:21 GMT 2020
  * use the shrinking for MergeableSequence on existing tests

Attachments

• patch-preview.txt
• specialise-the-types-of-withsingle-etc.dpatch
• unnamed

After looking a bit closer at what this does e.g. in
Arbitrary.RepoPatch, I think this doesn't yet take advantage of the new
shrinker for many of the tests. For instance,

withSingle
  :: Merge p
  => (forall wX wY. p wX wY -> r)
  -> Sealed2 (WithStartState2 (MergeableSequence p)) -> Maybe r
withSingle prop (Sealed2 (WithStartState2 _ ms))
  = case mergeableSequenceToRL ms of
      _ :<: pp -> Just (prop pp)
      _ -> Nothing

I may be wrong but I see the property gets applied to a plain patch w/o
any state. So if that test fails, QC calls the shrink method for the
plain @p@, not for any @WithStartState2 p@.

Attachments

• pEpkey.asc

What matters is what QuickCheck sees, not what happens in our own code.
We pass QuickCheck a function of type

  Sealed2 (WithStartState2 (MergeableSequence p)) -> Maybe TestResult

so that's the Arbitrary instance it uses both for shrinking and 
generation.

You can also see a type error if you comment out a key instance, for 
example instance Abitrary (Sealed2 (WithStartState2 p)) in 
D.T.P.A.WithState.

That said, I haven't actually tested it :-)

> What matters is what QuickCheck sees, not what happens in our own code.
> We pass QuickCheck a function of type
> 
>   Sealed2 (WithStartState2 (MergeableSequence p)) -> Maybe TestResult
> 
> so that's the Arbitrary instance it uses both for shrinking and 
> generation.

*slapping myself*. Of course. I wasn't thinking clearly.

Attachments

• pEpkey.asc

I already reviewed this one in detail.