[darcs-devel] TreeWithFlattenPos

Ganesh Sittampalam ganesh at earth.li
Fri Jun 21 20:20:16 UTC 2019


Hi,

On 21/06/2019 12:50, Ben Franksen wrote:
> See harness/Darcs/Test/Patch/Arbitrary/Generic.hs

I wrote TreeWithFlattenPos:

patch f8c199e6922b986bd65a51015ad09a4ef8a77833
Author: Ganesh Sittampalam <ganesh at earth.li>
Date:   Tue Oct 16 19:37:38 GMT Summer Time 2007
  * shrinking of conflictor pairs

The comment, and the Arbitrary instance, make me think that my
motivation was to get better shrinking of failing cases. But I can't
really remember the full reasoning and the shrink code doesn't look
particularly clever or careful to me.

What I do remember is that I wrote a bunch of test code like this while
David was developing V2 patches, and making them gradually more
sophisticated did help find quite a few issues in his implementation.

> It associates a number with a Tree. The Arbitrary instance tells me that
> this number is supposed to be no greater than the number of pairs in any
> flattened version of the Tree, i.e.  (max 0 (numberOfPatches t - 1)).
> 
> While commutePairFromTree always chooses the last of all pairs,
> commutePairFromTWFP chooses an arbitrary pair by indexing into the list
> of pairs with the number associated with the Tree. Why not use the oneof
> combinator from QuickCheck and dispense with the number?

Having the index in the testing type means it's part of the shrinking
code. I guess being able to change the position while shrinking the tree
might make it more likely that one of the shrinks would preserve the
failure? But I can't reconstruct the full reasoning.

> We test many properties with generators for Tree and for
> TreeWithFlattenPos. Makes no sense to me at all. If the idea was to test
> the pairs at the leaves of the tree more often, why not use frequency
> for that? (But I could see no reason why we would want to do that).
> 
> BTW, numberOfPatches is almost the same as sizeTree, except that
> sizeTree adds 1 for each Par Node, no idea why. Since sizeTree isn't
> used anywhere except for propFail which in turn isn't used anywhere I
> think it could safely be changed to return the actual size.

The comment on prop_fail (as it was named when introduced) is that it
helps with debugging. I really can't remember what that was about. You
might as well just delete both.

> Also, I have the impression that the author of this module didn't
> realize that all tree flattenings necessarily have the same size which
> is exactly the number of patches in the Tree.

I think I would have probably realised that, but that doesn't mean I
didn't write unnecessarily complicated code :-)

> Unless someone chimes in here and comes up with a good explanation for
> this apparently unnecessary complication I will go ahead and simplify
> things by removing TreeWithFlattenPos and modifying the test generators
> for pairs (and triples) such that they pick an arbitrary pair (or
> triple) from any of the tree flattenings. I'll do this before I start
> adding the missing scenarios (i.e. patches recorded on top of conflictors).

I have no objection. The complexity may or may not have been justified
at the time for helping to actually find and cut down bugs, but in a
world where the tests do pass the trade-offs are different anyway.

Ganesh


More information about the darcs-devel mailing list