Tutorial 1: a binary search tree

In this tutorial, we write a simple data structure and test its API with fuzzcheck. The goal is to learn the basics, that is:

• the requirements for a type or function to be fuzz-testable
• how to create a default Mutator for a custom type through fuzzcheck’s procedural macros
• how to use serde to serialize interesting values and artifacts to the type system
• how to use the cargo-fuzzcheck command line tool
• how to interpret the files generated by fuzzcheck

The data structure we choose to implement is a binary search tree. We create a new tree with Tree::empty(), insert a value into the tree with tree.insert(x), and search for a value in the tree with tree.contains(&x).

We will create a fuzz target that tests whether the tree

1. behaves like a proper set
2. does not crash

And we will see how, even when fuzzcheck does not find any failures, we can analyze its output to gain insight into our code.