Crate pbt

Useful traits for exhaustive and/or stochastic search over a type, and for applying this search to high-throughput testing.

Specifically, the main trait gives you the following:

• The AST size of an arbitrary term (via a fn size(&self) -> usize)
• The maximum AST size of this type, or a statement that it’s infinite, or a statement that the type is uninstantiable;
• The smallest possible term of this type (or None, iff uninstantiable);
• An iterator over all edge cases/corner cases of this type, computed structurally;
• An iterator over all terms of a given AST size;
• An iterator that uses the above with (0..).flat_map(|size| ..) to perform breadth-first search over all possible values of this type.

In the future, stochastic search may be added, but it is currently not implemented. This is not because doing so would be particularly difficult; instead, iterating first over edge cases and then over an exhaustive breadth-first search works incredibly well in practice, kicks ass in throughput (meaning more cases tested), and solves the shrinking problem by immediately returning the first failing case, which is guaranteed to be the smallest, since it was found during breadth-first search.

The #[pbt] attribute takes a fn prop(args: ..) -> Result<(), _> (or -> bool or -> () or similar) and produces a #[test] that runs the above iterator (edge cases then breadth-first) to produce a staggering throughput of cases in the blink of an eye, effectively guaranteeing correct behavior on all but large or parasitic inputs. Note that this is no substitute for formal verification, but it is incredibly good at finding minimal counterexamples when they do exist, in all but large or specific cases (e.g. if you write assert(x != 42_000_000)). If you might encounter large or specific odd cases, do not rely on this library alone! Instead, use this to find simple logic errors, and use other tests to find these cases.

Modules

collections

Pbt implementations for Vec, BTreeSet, etc.

prelude

Macros

impl_tests

Test correct functionality for this type’s Pbt implementation.

Enums

MaxSize

Outcome

Traits

Pbt

Functions

best_first

First, generate all edge cases of this type, then generate all values of this type sorted by increasing size.

exhaust

Generate all values of this type sorted by increasing size.

exhaust_size

See exhaust_size (without the underscore). This function is for internal use only: it ensures that time is not wasted by calling this function on sizes that are statically known to be unreachable.