Repository files navigation

QuickCheck is a way to do property based testing using randomly generatedinput. This crate comes with the ability to randomly generate and shrinkintegers, floats, tuples, booleans, lists, strings, options and results.All QuickCheck needs is a property function—it will then randomly generateinputs to that function and call the property for each set of inputs. If theproperty fails (whether by a runtime error like index out-of-bounds or by notsatisfying your property), the inputs are "shrunk" to find a smallercounter-example.

The shrinking strategies for lists and numbers use a binary search to coverthe input space quickly. (It should be the same strategy used inKoen Claessen's QuickCheck forHaskell.)

Dual-licensed under MIT or theUNLICENSE.

The API is fully documented:https://docs.rs/quickcheck.

Here's an example that tests a function that reverses a vector:

fnreverse<T:Clone>(xs:&[T]) ->Vec<T>{letmut rev =vec![];for xin xs.iter(){        rev.insert(0, x.clone())}    rev}#[cfg(test)]mod tests{use quickcheck::quickcheck;usesuper::reverse;quickcheck!{fn prop(xs:Vec<u32>) ->bool{            xs == reverse(&reverse(&xs))}}}

This example uses thequickcheck! macro, which is backwards compatible withold versions of Rust.

To make it easier to write QuickCheck tests, the#[quickcheck] attributewill convert a property function into a#[test] function.

To use the#[quickcheck] attribute, you must import thequickcheck macrofrom thequickcheck_macros crate:

fnreverse<T:Clone>(xs:&[T]) ->Vec<T>{letmut rev =vec![];for xin xs{        rev.insert(0, x.clone())}    rev}#[cfg(test)]mod tests{use quickcheck_macros::quickcheck;usesuper::reverse;#[quickcheck]fndouble_reversal_is_identity(xs:Vec<isize>) ->bool{        xs ==reverse(&reverse(&xs))}}

quickcheck is oncrates.io, so you can include it in your project like so:

[dependencies]quickcheck ="1"

If you're only usingquickcheck in your test code, then you can add it as adevelopment dependency instead:

[dev-dependencies]quickcheck ="1"

If you want to use the#[quickcheck] attribute, then addquickcheck_macros

[dev-dependencies]quickcheck ="1"quickcheck_macros ="1"

N.B. When usingquickcheck (either directly or via the attributes),RUST_LOG=quickcheck enablesinfo! so that it shows useful output(like the number of tests passed). This isnot needed to showwitnesses for failures.

Crate features:

• "use_logging": (Enabled by default.) Enables the log messages governedRUST_LOG.
• "regex": (Enabled by default.) Enables the use of regexes withenv_logger.

This crate's minimum supportedrustc version is1.71.0.

The current policy is that the minimum Rust version required to use this cratecan be increased in minor version updates. For example, ifcrate 1.0 requiresRust 1.20.0, thencrate 1.0.z for all values ofz will also require Rust1.20.0 or newer. However,crate 1.y fory > 0 may require a newer minimumversion of Rust.

In general, this crate will be conservative with respect to the minimumsupported version of Rust.

With all of that said, currently,rand is a public dependency ofquickcheck. Therefore, the MSRV policy above only applies when it is moreaggressive thanrand's MSRV policy. Otherwise,quickcheck will defer torand's MSRV policy.

In general, this crate considers theArbitrary implementations provided asimplementation details. Strategies may or may not change over time, which maycause new test failures, presumably due to the discovery of new bugs due to anew kind of witness being generated. These sorts of changes may happen insemver compatible releases.

Theproptest crate is inspired by theHypothesis framework for Python.You can read a comparison betweenproptest andquickcheckhereandhere.In particular,proptest improves on the concept of shrinking. So if you'veever had problems/frustration with shrinking inquickcheck, thenproptestmight be worth a try!

Please see theRust Fuzz Bookand thearbitrary crate.

Sometimes you want to test a property that only holds for asubset of thepossible inputs, so that when your property is given an input that is outsideof that subset, you'd discard it. In particular, the property shouldneitherpass nor fail on inputs outside of the subset you want to test. But propertiesreturn boolean values—which either indicate pass or fail.

To fix this, we need to take a step back and look at the type of thequickcheck function:

pubfnquickcheck<A:Testable>(f:A){// elided}

Soquickcheck can test any value with a type that satisfies theTestabletrait. Great, so what is thisTestable business?

pubtraitTestable{fnresult(&self,&mutGen) ->TestResult;}

This trait states that a type is testable if it can produce aTestResultgiven a source of randomness. (ATestResult stores information about theresults of a test, like whether it passed, failed or has been discarded.)

Sure enough,bool satisfies theTestable trait:

implTestableforbool{fnresult(&self, _:&mutGen) ->TestResult{TestResult::from_bool(*self)}}

But in the example, we gave afunction toquickcheck. Yes, functions cansatisfyTestable too!

impl<A:Arbitrary +Debug,B:Testable>Testableforfn(A) ->B{fnresult(&self,g:&mutGen) ->TestResult{// elided}}

Which says that a function satisfiesTestable if and only if it has a singleparameter type (whose values can be randomly generated and shrunk) and returnsany type (that also satisfiesTestable). So a function with typefn(usize) -> bool satisfiesTestable sinceusize satisfiesArbitrary andboolsatisfiesTestable.

So to discard a test, we need to return something other thanbool. What if wejust returned aTestResult directly? That should work, but we'll need tomake sureTestResult satisfiesTestable:

implTestableforTestResult{fnresult(&self, _:&mutGen) ->TestResult{self.clone()}}

Now we can test functions that return aTestResult directly.

As an example, let's test our reverse function to make sure that the reverse ofa vector of length 1 is equal to the vector itself.

fnprop(xs:Vec<isize>) ->TestResult{if xs.len() !=1{returnTestResult::discard()}TestResult::from_bool(xs ==reverse(&xs))}quickcheck(propasfn(Vec<isize>) ->TestResult);

(A full working program for this example is inexamples/reverse_single.rs.)

So now our property returns aTestResult, which allows us to encode a bitmore information. There are a few moreconvenience functions defined for theTestResulttype.For example, we can't just return abool, so we convert abool value to aTestResult.

(The ability to discard tests allows you to get similar functionality asHaskell's==> combinator.)

N.B. Since discarding a test means it neither passes nor fails,quickcheckwill try to replace the discarded test with a fresh one. However, if yourcondition is seldom met, it's possible thatquickcheck will have to settlefor running fewer tests than usual. By default, ifquickcheck can't find100 valid tests after trying10,000 times, then it will give up.These parameters may be changed usingQuickCheck::testsandQuickCheck::max_tests,or by setting theQUICKCHECK_TESTS andQUICKCHECK_MAX_TESTSenvironment variables.There is alsoQUICKCHECK_MIN_TESTS_PASSED which sets the minimum number ofvalid tests that need pass (defaults to0) in order for it to be considered asuccess.

Shrinking is a crucial part of QuickCheck that simplifies counter-examples foryour properties automatically. For example, if you erroneously defined afunction for reversing vectors as: (my apologies for the contrived example)

fnreverse<T:Clone>(xs:&[T]) ->Vec<T>{letmut rev =vec![];for iin1..xs.len(){        rev.insert(0, xs[i].clone())}    rev}

And a property to test thatxs == reverse(reverse(xs)):

fnprop(xs:Vec<isize>) ->bool{    xs ==reverse(&reverse(&xs))}quickcheck(propasfn(Vec<isize>) ->bool);

Then without shrinking, you might get a counter-example like:

[quickcheck] TEST FAILED. Arguments: ([-17, 13, -12, 17, -8, -10, 15, -19,-19, -9, 11, -5, 1, 19, -16, 6])

Which is pretty mysterious. But with shrinking enabled, you're nearlyguaranteed to get this counter-example every time:

[quickcheck] TEST FAILED. Arguments: ([0])

Which is going to be much easier to debug.

Quickcheck uses random input to test, so it won'talways find bugs that could be uncovered with a particularproperty. You can improve your odds of finding these latentbugs by spending more CPU cycles asking quickcheck to findthem for you. There are a few different ways to do this, andwhich one you choose is mostly a matter of taste.

If you are finding yourself doing this sort of thing alot, you might also be interested in trying outcargo fuzz,which runs in a loop by default.

One approach is to run your quickcheck properties in a loop thatjust keeps going until you tell it to stop or it finds a bug.For example, you could use a bash script such as the followingone.

#!/usr/bin/bashwhiletruedo    cargotest qc_if [[ x$?!= x0 ]];thenexit$?fidone

One thing to note is that this script passes theqc_ filter tocargo test. This assumes that you've prefixed all your quickcheckproperties withqc_. You could leave off the filter, but thenyou would be running all your deterministic tests as well, whichwould take time away from quickcheck!

Checking the return code and exiting is also important. Without thattest, you won't ever notice when a failure happens.

Another approach is to just ask quickcheck to run properties moretimes. You can do this either via thetests()method, or via theQUICKCHECK_TESTS environment variable.This will cause quickcheck to run for a much longer time. Unlike,the loop approach this will take a bounded amount of time, whichmakes it more suitable for something like a release cycle thatwants to really hammer your software.

This approach entails spending more time generating interestinginputs in your implementations of Arbitrary. The idea is tofocus on the corner cases. This approach can be tricky becauseprogrammers are not usually great at intuiting corner cases,and the whole idea of property checking is to take that burdenoff the programmer. Despite the theoretical discomfort, thisapproach can turn out to be practical.

It is very simple to generate structs in QuickCheck. Consider the followingexample, where the structPoint is defined:

structPoint{x:i32,y:i32,}

In order to generate a randomPoint instance, you need to implementthe traitArbitrary for the structPoint:

use quickcheck::{Arbitrary,Gen};implArbitraryforPoint{fnarbitrary(g:&mutGen) ->Point{Point{x: i32::arbitrary(g),y: i32::arbitrary(g),}}}

TheSieve of Eratosthenesis a simple and elegant way to find all primes less than or equal toN.Briefly, the algorithm works by allocating an array withN slots containingbooleans. Slots marked withfalse correspond to prime numbers (or numbersnot known to be prime while building the sieve) and slots marked withtrueare known to not be prime. For eachn, all of its multiples in this arrayare marked as true. When alln have been checked, the numbers markedfalseare returned as the primes.

As you might imagine, there's a lot of potential for off-by-one errors, whichmakes it ideal for randomized testing. So let's take a look at myimplementation and see if we can spot the bug:

fnsieve(n:usize) ->Vec<usize>{if n <=1{returnvec![];}letmut marked =vec![false; n+1];    marked[0] =true;    marked[1] =true;    marked[2] =true;for pin2..n{for iin(2*p..n).filter(|&n| n % p ==0){            marked[i] =true;}}    marked.iter().enumerate().filter_map(|(i,&m)|if m{None}else{Some(i)}).collect()}

Let's try it on a few inputs by hand:

sieve(3) => [2, 3]sieve(5) => [2, 3, 5]sieve(8) => [2, 3, 5, 7, 8] # !!!

Something has gone wrong! But where? The bug is rather subtle, but it's aneasy one to make. It's OK if you can't spot it, because we're going to useQuickCheck to help us track it down.

Even before looking at some example outputs, it's good to try and come up withsomeproperties that are always satisfiable by the output of the function. Anobvious one for the prime number sieve is to check if all numbers returned areprime. For that, we'll need anis_prime function:

fnis_prime(n:usize) ->bool{    n !=0 && n !=1 &&(2..).take_while(|i| i*i <= n).all(|i| n % i !=0)}

All this is doing is checking to see if any number in[2, sqrt(n)] dividesn with base cases for0 and1.

Now we can write our QuickCheck property:

fnprop_all_prime(n:usize) ->bool{sieve(n).into_iter().all(is_prime)}

And finally, we need to invokequickcheck with our property:

fnmain(){quickcheck(prop_all_primeasfn(usize) ->bool);}

A fully working source file with this code is inexamples/sieve.rs.

The output of running this program has this message:

[quickcheck] TEST FAILED. Arguments: (4)

Which says thatsieve failed theprop_all_prime test when givenn = 4.Because of shrinking, it was able to find a (hopefully) minimal counter-examplefor our property.

With such a short counter-example, it's hopefully a bit easier to narrow downwhere the bug is. Since4 is returned, it's likely never marked as being notprime. Since4 is a multiple of2, its slot should be marked astrue whenp = 2 on these lines:

for iin(2*p..n).filter(|&n| n % p ==0){    marked[i] =true;}

Ah! But does the.. (range) operator includen? Nope! This particularoperator is a half-open interval.

A2*p..n range will never yield4 whenn = 4. When we change this to2*p..n+1, all tests pass.

In addition, if our bug happened to result in an index out-of-bounds error,thenquickcheck can handle it just like any other failure—includingshrinking on failures caused by runtime errors.

But hold on... we're not done yet. Right now, our property tests that allthe numbers returned bysieve are prime but it doesn't test if the list iscomplete. It does not ensure that all the primes between0 andn are found.

Here's a property that is more comprehensive:

fnprop_prime_iff_in_the_sieve(n:usize) ->bool{sieve(n) ==(0..(n +1)).filter(|&i|is_prime(i)).collect::<Vec<_>>()}

It tests that for each number between 0 and n, inclusive, the naive primality testyields the same result as the sieve.

Now, if we run it:

fnmain(){quickcheck(prop_all_primeasfn(usize) ->bool);quickcheck(prop_prime_iff_in_the_sieveasfn(usize) ->bool);}

we see that it fails immediately for value n = 2.

[quickcheck] TEST FAILED. Arguments: (2)

If we inspectsieve() once again, we see that we mistakenly mark2 asnon-prime. Removing the linemarked[2] = true; results in both propertiespassing.

I think I've captured the key features, but there are still things missing:

• Only functions with 8 or fewer parameters can be quickchecked. Thislimitation can be lifted to someN, but requires an implementation for eachn of theTestable trait.
• Functions that fail because of a stack overflow are not caught by QuickCheck.Therefore, such failures will not have a witness attachedto them. (I'd like to fix this, but I don't know how.)
• Coarbitrary does not exist in any form in this package. It's unlikely thatit ever will.
• Arbitrary is not implemented for closures. Seeissue #56for more details on why.