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.