[darcs-devel] shrinkPatchInfo goes into infinite loop

[Ben Franksen]

Am 01.03.20 um 22:15 schrieb Ganesh Sittampalam:
>> I'll send my patch. If you apply it and roll back the fixes I made to
>> metadataDecodingTest, you tests should loop (use darcs-test -t
>> Darcs.Patch.Info).
>>
>> [...] I guess the problem is related to the way
>> you define shrink via <|> for the member of Patchinfo.
> 
> That approach is just meant to shrink each element of the PatchInfo in
> turn. I don't think it's a problem.

That was just a hunch and probably completely wrong.

> I've spent a while playing with this and I am partially convinced that
> it's your change that triggered the loop.
> 
> I've just sent some new draft patches on top of yours in patch2006. If
> you just take these ones:
> 
>   * introduce empty
>   * tests: bugfix for shrinking log lines
>   * WIP: introduce shrinking tests
> 
> You'll see that the new tests I added to check shrinking pass.
> 
> If you then take the rest, they start failing. My suspicion is that your
> change to the shrinking of names:
> 
>> -      sn <- f1 (piName pi)
>> +      sn <- f1 (justName pi)
> 
> along with the other underlying changes, has made it possible for an
> empty name to be shrunk to an empty name. But I'm not 100% certain so
> I'm happy to keep looking into it if you still think it's a problem with
> the existing shrinking.

I haven't yet look at your changes, but I guess we can verify this by
adding an assertion a la

  if x `elem` shrink x then error "bad shrink" else id

> The general work on shrinking tests is very much provisional. It could
> do with a bit more documentation, and I'm a bit nervous about the extra
> code to maintain.

And I am nervous about the whole shrinking leading to loops instead of
failed tests. If it was indeed my refactor that broke the shrinker, this
means shrinking not very robust against such refactors.

OTOH, the PatchInfo tests are a mess anyway, with their direct access to
the low-level implementation details. Perhaps no wonder it is easy to
break them.

> The basic idea is to firstly check that all shrinks are valid (as the
> PatchInfo ones weren't previously) and secondly that they all make the
> value smaller.
> 
> This was surprisingly tricky to get right for PatchInfo, partly because
> of all the hidden invariants/representation assumptions embedded in the
> type. Your refactoring is of course moving in the right direction to
> normalise the representation.
> 
> The Char instance in particular was a pain, I had to read the source for
> shrink on Char to understand how to write it. And if that changes it'll
> be a maintenance headache.

In the meantime I have succeeded with my attempts at integrating
LeanCheck testing to the point where I can easily run all the PrimV1
tests with 20000 test cases.

Doing this required a few minor refactors to untangle Arbitrary from the
infrastructure, but the amount of code I had to add is minimal: 30 LOC
for V1Model, 100 LOC for PrimV1, 25 LOC to gather the prim tests in the
new function lc_prim in Darcs.Test.Patch.

Part of why supporting LC takes a lot less code to write than QC is that
for QC we have to provide special Arbitrary instances for pairs and FLs
that tweak the distributions, which means we cannot define one fully
generic instance based on ArbitraryState (because the special instances
would overlap). Whereas for LC this is not needed, so we can define a
single instance Listable (Sealed2 p); and for the V1.Prim and V2.Prim
wrappers we can derive /everything/ with two lines of code!

To keep reins on the state space explosion, I have resorted to simple
and drastic measures: File and dir 'Name's (not paths!) are taken from
the finite set {"f","g"} (in particular, this means directories can have
at most two entries); and characters in file contents are limited to
{'x','y',' ','\n'}. This means we get "interesting" repos (i.e. nested
directories and multiple non-empty lines of text in files) pretty early.

I think I will send some patches soon.

I should mention that the LC tests already uncovered a problem: the
tests coalesceEffectPreserving and invertRollback both fail with

      prim coalesce effect preserving: [Failed]
*** Failed! Falsifiable (after 2381 tests):
(Sealed2 (WithState mkV1Model [("f",mkFile ["x"])] (Prim {unPrim = FP
(AnchoredPath [Name {unName = "f"}]) (Hunk 1 [Data.ByteString.Char8.pack
"x"] [])}:>Prim {unPrim = FP (AnchoredPath [Name {unName = "f"}]) (Hunk
1 [] [Data.ByteString.Char8.pack "x"])}) mkV1Model [("f",mkFile ["x"])]))
      invert rollback: [Failed]
*** Failed! Falsifiable (after 37 tests):
(Sealed2 (WithState mkV1Model [("f",mkFile ["x"])] (Prim {unPrim = FP
(AnchoredPath [Name {unName = "f"}]) (Hunk 1 [Data.ByteString.Char8.pack
"x"] [])}) mkV1Model [("f",mkFile [])]))

(I have changed showModel for V1Model so it prints a valid expression I
can paste in ghci. Note how minimal theses cases are despite zero effort
on my part.)

I am almost sure this is a problem in the way these properties are
written and not with PrimV1 per se. When I run the properties with the
failing test case as input they fail, but when I apply the patches
directly and compare the resulting repos, they are identical. Quite strange.

Cheers
Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pEpkey.asc
Type: application/pgp-keys
Size: 4211 bytes
Desc: not available
URL: <http://lists.osuosl.org/pipermail/darcs-devel/attachments/20200302/132545a6/attachment.key>