Great article!
It could benefit from a fleshed out shrinking session in which you explicitly show how the tree is traversed.
Also, some details for people who are curious about the Hypothesis approach:
-
Hypothesis’ approach is very elegant. But you pay for it with more complexity in the core, and making it harder to write generators. As @whatyouhide says, primitive generators must be written in a specific way, and even though the idea is simple, the details are quite involved. EDIT: composing already-built generators is very easy, though.
-
Describing hypothesis as taking a random bytestring and generating examples out of it makes it look way simpler than it is: doing this would require an mapping that can generate an example out of any random byte stream thrown at it. This is not true. Sometimes hypothesis cheats and “generates” the bytes it needs in order to satisfy some data constraints (a list with at least 5 elements, for example; in this case hypothesis might force some bytes to have the value it wants). The corollary is that during shrinking, some byte strrams might generate invalid examples, which must be discarded. These are not major problems, but they must be managed carefully, and that takes more code.
-
Shrinking is not done by only shrinking the byte stream. That would generate invalid data too often, and waste time on impossible shrinks. Hypothesis has a way of tagging some bytes as special, so that they will be shrunk in specific ways. In practice, shrinking has some restrictions. This again makes the core much more complex than just “eat some bytes and generate some objects”.
My undeestanding is that Hypothesis might unlock some shrinks that are hard to unlock when using the Lazy Tree approach, but I don’t know if that’s relevant in practice.
If you ever decide you want to go the byte stream route, I can send you my partial (and probably very buggy - haven’t tested it in ages) port of the Hypothesis core to elixir. The Python code is challenhing to understand in some parts, because it mutates objects like crazy and bends backwards to undo some mutations when it decides to backtrack. An elixir port should definitely return modified “generator state”. That gives you undo for free.
