reaction to "Integrated vs type based shrinking"

[Eh2406]

Hi,

David R. MacIver, the author of Hypothesis, just wrote an interesting article on "Integrated vs type based shrinking". I got in over my head trying to figure out how his suggestions for the haskell quickcheck relate to the rust one.

I'd love to hear your reaction to the article. Are we doing this already?

[BurntSushi]

I've read his work before. I'm not a huge fan of the writing style personally, but if I look past that, then I'd agree with him. I think it would be uncontroversial to state that the most annoying thing about using quickcheck in Rust (and Haskell) is writing shrinkers. For types with few invariants, it's not that bad, but if your type is more complex (like an AST where not all inhabitants are valid, for example), then both generation and shrinking need to maintain those invariants. My impression is that there are actually two solutions to this problem: one is what MacIver mentions (which I think might be doable with autoshrinking, but I haven't given much thought to it). The other solution is to encode more of your invariants into the type system. (e.g., Create an AST where none or fewer inhabitants are invalid.)

If the most natural next question is, "do you plan to solve this problem?", then I'd say my answer is "not any time soon." If it requires fundamental changes, then it might be better starting from scratch, but I'd be willing to entertain proposals!

In general, criticisms of Haskell's QuickCheck probably apply to Rust's QuickCheck. The reverse may not be true however.

[Eh2406]

Ya, his writing style is somewhat... adversarial.

I don't speak Haskell, so I'm not sure what MacIver's suggestion would look like in rust termes. Arbitrary already combines the gen and shrinking. So I am alittle confused.

Your suggestion, is in the family "If it is hard to test, it is hard to use. Refactor it." I.E. if it is hard to make a shrinker that stays in valid types then make it more rusty and use types that match the content.

I did not ask you to change anything; I merely asked for a reaction. I appreciate your willingness to respond to uninformed questions from a random guy on the internet. I try to take advantage of that tendency in this community in the hope that one day I will pull my weight. In the meantime my confusion may spark informed people to have good ideas.

[BurntSushi]

I don't speak Haskell, so I'm not sure what MacIver's suggestion would look like in rust termes. Arbitrary already combines the gen and shrinking. So I am alittle confused.

This example might help: https://github.com/rust-lang-nursery/regex/blob/master/regex-syntax/src/properties.rs#L131 --- It is rather complex, but it's the AST example I had in mind when I mentioned it. It'd be tough to grok all of it, but basically, all of the invariants around the AST are maintained somewhat messily across both generation and shrinking. I managed to bundle some of them up, but you can see all of the filters applied in the shrinker itself that are necessary to maintain those AST invariants.

An example of an invariant in the AST is something like "a Expr::Alternate must contain two or more subexpressions."

If I wanted to fix this, I'd probably look into defining an AST that more faithfully represents the concrete syntax. As it stands, the existing AST is a simplified version of the real AST to make it easier to compile into a finite state machine. So creating a more faithful AST requires more work, but it might wind up making tests easier and some types of analysis easier too. If I could do it all over again, I probably would have tried to define a faithful AST and a separate AST like the one that exists today. It's not clear though whether I could move all invariants into the type system.

Your suggestion, is in the family "If it is hard to test, it is hard to use. Refactor it." I.E. if it is hard to make a shrinker that stays in valid types then make it more rusty and use types that match the content.

That's pretty fair. But I will note that I think moving more invariants into the type system can also make it hard to use. There's a balance to be struck. It's hard.

I did not ask you to change anything; I merely asked for a reaction. I appreciate your willingness to respond to uninformed questions from a random guy on the internet. I try to take advantage of that tendency in this community in the hope that one day I will pull my weight. In the meantime my confusion may spark informed people to have good ideas.

Ah gotya! Ask away!

[Eh2406]

I think I understand the problem. I'm not understanding his proposed solution.

Working thru the example from the article. To test a function that takes even integers:

/// can only be called on even numbers
def thing_to_test(n: u32) -> bool {
    assert_eq!(n % 2, 0)
   // do some real work
}

We need a new new type

struct EvenNumber{n:u32}

So that we can implement Arbitrary on it. Than we need to make the thing_to_test generic so we can test it with EvenNumber but allow are existing code to continue to use it with u32. (This is where your suggestion is to make it only take EvenNumber. Using the type system to enforce the invariant in all the code not just the tests.) Implementing Arbitrary on it, may not be as simple/DRY as it seems because the invariant nades to be encoded in both the fn arbitrary and again in the fn shrink.

This is where I am confused. What is his suggestion?

I think.... he wants to change from

pub trait Arbitrary : Clone + Send + 'static {
    fn arbitrary<G: Gen>(g: &mut G) -> Self;
    fn shrink(&self) -> Box<Iterator<Item=Self>> {empty_shrinker()}
}

to

pub trait Arbitrary<T> : Clone + Send + 'static {
    fn arbitrary<G: Gen>(g: &mut G) -> T;
    fn shrink(&self) -> Box<Iterator<Item=T>> {empty_shrinker()}
}

So now to test thing_to_test we make a new type GenEvenNumber which implements Arbitrary<u32> thus letting us test against the unchanged thing_to_test. But how does that solve the simple/DRY problem?

Oww... we use a factory type,

struct MappedArbitrary<A: Arbitrary<T>, T, U, F: fn(T) -> U>{
core: A
map: F
}

impl Arbitrary<U> for MappedArbitrary<A, T, U, F>{
This is predictable 
}

So we can use MappedArbitrary<ArbitraryU32, u32, u32, |n| 2 * n> The trike being that the factory type is not DRY but it only needs to be written once, then used with any fn.

[Eh2406]

If I understand his suggestions, than this sounds like "fundamental changes," so I'd be happy to close. If I do not understand his suggestion, than I'd love some elucidation.

In general thank you for all the amazing libraries, and documentation. This community where I can learn from all the questions and discussion, and where I am comfortable asking, is a truly wonderful thing. Thank you for your ongoing maintenance of this community!

[BurntSushi]

I honestly haven't digested everything, but I think the crux of the matter is that Arbitrary itself isn't quite sufficient. The problem is that arbitrary and shrink are decoupled. If arbitrary generates something and shrink shrinks something, then where exactly are the runtime invariants of your type enforced? You kind of have to do it in both generation and shrinking, which is where DRY is violated.

I wish I had more time to digest this and explain it better with examples, but that's all I've got for now! Thanks for your kind words by the way. :-)

[Eh2406]

He has written 2 follow up posts. In Compositional shrinking he describes what I had thout he ment. He claims that it is a kind of "halfway house." It improves the ability to compose Arbitrary generators, but still leaves us not very DRY. (As you pointed out.)

In How Hypothesis Works He described his approach. It looks like he has everything be a mapped version of a base Arbitrary<&[u8]> this is very simple in that it is the source of all data and all shrinking. The problem Is it is not clear how to efficiently shrink the &[u8]. He then spent the rest explaining solutions he has for this, but they all seem complicated and finicky.

[BurntSushi]

It's been many moons and I haven't and don't plan on doing anything here. I think they are just different takes on property based testing. proptest might be good for folks interested in the Hypothesis way of doing things.