1quickcheck 2========== 3QuickCheck is a way to do property based testing using randomly generated 4input. This crate comes with the ability to randomly generate and shrink 5integers, floats, tuples, booleans, lists, strings, options and results. 6All QuickCheck needs is a property function—it will then randomly generate 7inputs to that function and call the property for each set of inputs. If the 8property fails (whether by a runtime error like index out-of-bounds or by not 9satisfying your property), the inputs are "shrunk" to find a smaller 10counter-example. 11 12The shrinking strategies for lists and numbers use a binary search to cover 13the input space quickly. (It should be the same strategy used in 14[Koen Claessen's QuickCheck for 15Haskell](https://hackage.haskell.org/package/QuickCheck).) 16 17[![Build status](https://github.com/BurntSushi/quickcheck/workflows/ci/badge.svg)](https://github.com/BurntSushi/quickcheck/actions) 18[![](https://meritbadge.herokuapp.com/quickcheck)](https://crates.io/crates/quickcheck) 19 20Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org). 21 22 23### Documentation 24 25The API is fully documented: 26[https://docs.rs/quickcheck](https://docs.rs/quickcheck). 27 28 29### Simple example 30 31Here's an example that tests a function that reverses a vector: 32 33```rust 34#[cfg(test)] 35#[macro_use] 36extern crate quickcheck; 37 38fn reverse<T: Clone>(xs: &[T]) -> Vec<T> { 39 let mut rev = vec!(); 40 for x in xs.iter() { 41 rev.insert(0, x.clone()) 42 } 43 rev 44} 45 46#[cfg(test)] 47mod tests { 48 quickcheck! { 49 fn prop(xs: Vec<u32>) -> bool { 50 xs == reverse(&reverse(&xs)) 51 } 52 } 53} 54``` 55 56This example uses the `quickcheck!` macro, which is backwards compatible with 57old versions of Rust. 58 59### The `#[quickcheck]` attribute (requires Rust 1.30 or later) 60 61To make it easier to write QuickCheck tests, the `#[quickcheck]` attribute 62will convert a property function into a `#[test]` function. 63 64To use the `#[quickcheck]` attribute, you must import the `quickcheck` macro 65from the `quickcheck_macros` crate: 66 67```rust 68#[cfg(test)] 69extern crate quickcheck; 70#[cfg(test)] 71#[macro_use(quickcheck)] 72extern crate quickcheck_macros; 73 74#[cfg(test)] 75mod tests { 76 fn reverse<T: Clone>(xs: &[T]) -> Vec<T> { 77 let mut rev = vec!(); 78 for x in xs { 79 rev.insert(0, x.clone()) 80 } 81 rev 82 } 83 84 #[quickcheck] 85 fn double_reversal_is_identity(xs: Vec<isize>) -> bool { 86 xs == reverse(&reverse(&xs)) 87 } 88} 89``` 90 91 92### Installation 93 94`quickcheck` is on `crates.io`, so you can include it in your project like so: 95 96```toml 97[dependencies] 98quickcheck = "0.9" 99``` 100 101If you're only using `quickcheck` in your test code, then you can add it as a 102development dependency instead: 103 104```toml 105[dev-dependencies] 106quickcheck = "0.9" 107``` 108 109If you want to use the `#[quickcheck]` attribute, then add `quickcheck_macros` 110 111```toml 112[dev-dependencies] 113quickcheck = "0.9" 114quickcheck_macros = "0.9" 115``` 116 117N.B. When using `quickcheck` (either directly or via the attributes), 118`RUST_LOG=quickcheck` enables `info!` so that it shows useful output 119(like the number of tests passed). This is **not** needed to show 120witnesses for failures. 121 122Crate features: 123 124- `"unstable"`: Enables Arbitrary implementations that require the Rust nightly 125 channel. 126- `"use_logging"`: (Enabled by default.) Enables the log messages governed 127 `RUST_LOG`. 128- `"regex"`: (Enabled by default.) Enables the use of regexes with 129 `env_logger`. 130 131Prior to quickcheck 0.8, this crate had an `i128` feature for enabling support 132for 128-bit integers. As of quickcheck 0.8 this feature is now provided by 133default and thus no longer available. 134 135 136### Minimum Rust version policy 137 138This crate's minimum supported `rustc` version is `1.34.0`. 139 140The current policy is that the minimum Rust version required to use this crate 141can be increased in minor version updates. For example, if `crate 1.0` requires 142Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust 1431.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum 144version of Rust. 145 146In general, this crate will be conservative with respect to the minimum 147supported version of Rust. 148 149With all of that said, currently, `rand` is a public dependency of 150`quickcheck`. Therefore, the MSRV policy above only applies when it is more 151aggressive than `rand`'s MSRV policy. Otherwise, `quickcheck` will defer to 152`rand`'s MSRV policy. 153 154 155### Alternative Rust crates for property testing 156 157The [`proptest`](https://docs.rs/proptest) crate is inspired by the 158[Hypothesis](https://hypothesis.works) framework for Python. 159You can read a comparison between `proptest` and `quickcheck` 160[here](https://github.com/AltSysrq/proptest/blob/master/proptest/README.md#differences-between-quickcheck-and-proptest) 161and 162[here](https://github.com/AltSysrq/proptest/issues/15#issuecomment-348382287). 163In particular, `proptest` improves on the concept of shrinking. So if you've 164ever had problems/frustration with shrinking in `quickcheck`, then `proptest` 165might be worth a try! 166 167 168### Discarding test results (or, properties are polymorphic!) 169 170Sometimes you want to test a property that only holds for a *subset* of the 171possible inputs, so that when your property is given an input that is outside 172of that subset, you'd discard it. In particular, the property should *neither* 173pass nor fail on inputs outside of the subset you want to test. But properties 174return boolean values—which either indicate pass or fail. 175 176To fix this, we need to take a step back and look at the type of the 177`quickcheck` function: 178 179```rust 180pub fn quickcheck<A: Testable>(f: A) { 181 // elided 182} 183``` 184 185So `quickcheck` can test any value with a type that satisfies the `Testable` 186trait. Great, so what is this `Testable` business? 187 188```rust 189pub trait Testable { 190 fn result<G: Gen>(&self, &mut G) -> TestResult; 191} 192``` 193 194This trait states that a type is testable if it can produce a `TestResult` 195given a source of randomness. (A `TestResult` stores information about the 196results of a test, like whether it passed, failed or has been discarded.) 197 198Sure enough, `bool` satisfies the `Testable` trait: 199 200```rust 201impl Testable for bool { 202 fn result<G: Gen>(&self, _: &mut G) -> TestResult { 203 TestResult::from_bool(*self) 204 } 205} 206``` 207 208But in the example, we gave a *function* to `quickcheck`. Yes, functions can 209satisfy `Testable` too! 210 211```rust 212impl<A: Arbitrary + Debug, B: Testable> Testable for fn(A) -> B { 213 fn result<G: Gen>(&self, g: &mut G) -> TestResult { 214 // elided 215 } 216} 217``` 218 219Which says that a function satisfies `Testable` if and only if it has a single 220parameter type (whose values can be randomly generated and shrunk) and returns 221any type (that also satisfies `Testable`). So a function with type `fn(usize) 222-> bool` satisfies `Testable` since `usize` satisfies `Arbitrary` and `bool` 223satisfies `Testable`. 224 225So to discard a test, we need to return something other than `bool`. What if we 226just returned a `TestResult` directly? That should work, but we'll need to 227make sure `TestResult` satisfies `Testable`: 228 229```rust 230impl Testable for TestResult { 231 fn result<G: Gen>(&self, _: &mut G) -> TestResult { self.clone() } 232} 233``` 234 235Now we can test functions that return a `TestResult` directly. 236 237As an example, let's test our reverse function to make sure that the reverse of 238a vector of length 1 is equal to the vector itself. 239 240```rust 241fn prop(xs: Vec<isize>) -> TestResult { 242 if xs.len() != 1 { 243 return TestResult::discard() 244 } 245 TestResult::from_bool(xs == reverse(&xs)) 246} 247quickcheck(prop as fn(Vec<isize>) -> TestResult); 248``` 249 250(A full working program for this example is in 251[`examples/reverse_single.rs`](https://github.com/BurntSushi/quickcheck/blob/master/examples/reverse_single.rs).) 252 253So now our property returns a `TestResult`, which allows us to encode a bit 254more information. There are a few more 255[convenience functions defined for the `TestResult` 256type](https://docs.rs/quickcheck/*/quickcheck/struct.TestResult.html). 257For example, we can't just return a `bool`, so we convert a `bool` value to a 258`TestResult`. 259 260(The ability to discard tests allows you to get similar functionality as 261Haskell's `==>` combinator.) 262 263N.B. Since discarding a test means it neither passes nor fails, `quickcheck` 264will try to replace the discarded test with a fresh one. However, if your 265condition is seldom met, it's possible that `quickcheck` will have to settle 266for running fewer tests than usual. By default, if `quickcheck` can't find 267`100` valid tests after trying `10,000` times, then it will give up. 268These parameters may be changed using 269[`QuickCheck::tests`](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.tests) 270and [`QuickCheck::max_tests`](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.max_tests), 271or by setting the `QUICKCHECK_TESTS` and `QUICKCHECK_MAX_TESTS` 272environment variables. 273There is also `QUICKCHECK_MIN_TESTS_PASSED` which sets the minimum number of 274valid tests that need pass (defaults to `0`) in order for it to be considered a 275success. 276 277 278### Shrinking 279 280Shrinking is a crucial part of QuickCheck that simplifies counter-examples for 281your properties automatically. For example, if you erroneously defined a 282function for reversing vectors as: (my apologies for the contrived example) 283 284```rust 285fn reverse<T: Clone>(xs: &[T]) -> Vec<T> { 286 let mut rev = vec![]; 287 for i in 1..xs.len() { 288 rev.insert(0, xs[i].clone()) 289 } 290 rev 291} 292``` 293 294And a property to test that `xs == reverse(reverse(xs))`: 295 296```rust 297fn prop(xs: Vec<isize>) -> bool { 298 xs == reverse(&reverse(&xs)) 299} 300quickcheck(prop as fn(Vec<isize>) -> bool); 301``` 302 303Then without shrinking, you might get a counter-example like: 304 305``` 306[quickcheck] TEST FAILED. Arguments: ([-17, 13, -12, 17, -8, -10, 15, -19, 307-19, -9, 11, -5, 1, 19, -16, 6]) 308``` 309 310Which is pretty mysterious. But with shrinking enabled, you're nearly 311guaranteed to get this counter-example every time: 312 313``` 314[quickcheck] TEST FAILED. Arguments: ([0]) 315``` 316 317Which is going to be much easier to debug. 318 319### More Thorough Checking 320 321Quickcheck uses random input to test, so it won't 322always find bugs that could be uncovered with a particular 323property. You can improve your odds of finding these latent 324bugs by spending more CPU cycles asking quickcheck to find 325them for you. There are a few different ways to do this, and 326which one you choose is mostly a matter of taste. 327 328If you are finding yourself doing this sort of thing a 329lot, you might also be interested in trying out 330[`cargo fuzz`](https://github.com/rust-fuzz/cargo-fuzz), 331which runs in a loop by default. 332 333##### Running in a Loop 334 335One approach is to run your quickcheck properties in a loop that 336just keeps going until you tell it to stop or it finds a bug. 337For example, you could use a bash script such as the following 338one. 339 340```bash 341#!/usr/bin/bash 342 343while true 344do 345 cargo test qc_ 346 if [[ x$? != x0 ]] ; then 347 exit $? 348 fi 349done 350``` 351 352One thing to note is that this script passes the `qc_` filter to 353`cargo test`. This assumes that you've prefixed all your quickcheck 354properties with `qc_`. You could leave off the filter, but then 355you would be running all your deterministic tests as well, which 356would take time away from quickcheck! 357 358Checking the return code and exiting is also important. Without that 359test, you won't ever notice when a failure happens. 360 361##### Cranking the Number of Tests 362 363Another approach is to just ask quickcheck to run properties more 364times. You can do this either via the 365[tests()](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.tests) 366method, or via the `QUICKCHECK_TESTS` environment variable. 367This will cause quickcheck to run for a much longer time. Unlike, 368the loop approach this will take a bounded amount of time, which 369makes it more suitable for something like a release cycle that 370wants to really hammer your software. 371 372##### Making Arbitrary Smarter 373 374This approach entails spending more time generating interesting 375inputs in your implementations of Arbitrary. The idea is to 376focus on the corner cases. This approach can be tricky because 377programmers are not usually great at intuiting corner cases, 378and the whole idea of property checking is to take that burden 379off the programmer. Despite the theoretical discomfort, this 380approach can turn out to be practical. 381 382### Generating Structs 383 384It is very simple to generate structs in QuickCheck. Consider the following 385example, where the struct `Point` is defined: 386 387```rust 388struct Point { 389 x: i32, 390 y: i32, 391} 392``` 393 394In order to generate a random `Point` instance, you need to implement 395the trait `Arbitrary` for the struct `Point`: 396 397```rust 398use quickcheck::{Arbitrary, Gen}; 399 400impl Arbitrary for Point { 401 fn arbitrary<G: Gen>(g: &mut G) -> Point { 402 Point { 403 x: i32::arbitrary(g), 404 y: i32::arbitrary(g), 405 } 406 } 407} 408``` 409 410 411### Case study: The Sieve of Eratosthenes 412 413The [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 414is a simple and elegant way to find all primes less than or equal to `N`. 415Briefly, the algorithm works by allocating an array with `N` slots containing 416booleans. Slots marked with `false` correspond to prime numbers (or numbers 417not known to be prime while building the sieve) and slots marked with `true` 418are known to not be prime. For each `n`, all of its multiples in this array 419are marked as true. When all `n` have been checked, the numbers marked `false` 420are returned as the primes. 421 422As you might imagine, there's a lot of potential for off-by-one errors, which 423makes it ideal for randomized testing. So let's take a look at my 424implementation and see if we can spot the bug: 425 426```rust 427fn sieve(n: usize) -> Vec<usize> { 428 if n <= 1 { 429 return vec![]; 430 } 431 432 let mut marked = vec![false; n+1]; 433 marked[0] = true; 434 marked[1] = true; 435 marked[2] = true; 436 for p in 2..n { 437 for i in (2*p..n).filter(|&n| n % p == 0) { 438 marked[i] = true; 439 } 440 } 441 marked.iter() 442 .enumerate() 443 .filter_map(|(i, &m)| if m { None } else { Some(i) }) 444 .collect() 445} 446``` 447 448Let's try it on a few inputs by hand: 449 450``` 451sieve(3) => [2, 3] 452sieve(5) => [2, 3, 5] 453sieve(8) => [2, 3, 5, 7, 8] # !!! 454``` 455 456Something has gone wrong! But where? The bug is rather subtle, but it's an 457easy one to make. It's OK if you can't spot it, because we're going to use 458QuickCheck to help us track it down. 459 460Even before looking at some example outputs, it's good to try and come up with 461some *properties* that are always satisfiable by the output of the function. An 462obvious one for the prime number sieve is to check if all numbers returned are 463prime. For that, we'll need an `is_prime` function: 464 465```rust 466fn is_prime(n: usize) -> bool { 467 n != 0 && n != 1 && (2..).take_while(|i| i*i <= n).all(|i| n % i != 0) 468} 469``` 470 471All this is doing is checking to see if any number in `[2, sqrt(n)]` divides 472`n` with base cases for `0` and `1`. 473 474Now we can write our QuickCheck property: 475 476```rust 477fn prop_all_prime(n: usize) -> bool { 478 sieve(n).into_iter().all(is_prime) 479} 480``` 481 482And finally, we need to invoke `quickcheck` with our property: 483 484```rust 485fn main() { 486 quickcheck(prop_all_prime as fn(usize) -> bool); 487} 488``` 489 490A fully working source file with this code is in 491[`examples/sieve.rs`](https://github.com/BurntSushi/quickcheck/blob/master/examples/sieve.rs). 492 493The output of running this program has this message: 494 495``` 496[quickcheck] TEST FAILED. Arguments: (4) 497``` 498 499Which says that `sieve` failed the `prop_all_prime` test when given `n = 4`. 500Because of shrinking, it was able to find a (hopefully) minimal counter-example 501for our property. 502 503With such a short counter-example, it's hopefully a bit easier to narrow down 504where the bug is. Since `4` is returned, it's likely never marked as being not 505prime. Since `4` is a multiple of `2`, its slot should be marked as `true` when 506`p = 2` on these lines: 507 508```rust 509for i in (2*p..n).filter(|&n| n % p == 0) { 510 marked[i] = true; 511} 512``` 513 514Ah! But does the `..` (range) operator include `n`? Nope! This particular 515operator is a half-open interval. 516 517A `2*p..n` range will never yield `4` when `n = 4`. When we change this to 518`2*p..n+1`, all tests pass. 519 520In addition, if our bug happened to result in an index out-of-bounds error, 521then `quickcheck` can handle it just like any other failure—including 522shrinking on failures caused by runtime errors. 523 524But hold on... we're not done yet. Right now, our property tests that all 525the numbers returned by `sieve` are prime but it doesn't test if the list is 526complete. It does not ensure that all the primes between `0` and `n` are found. 527 528Here's a property that is more comprehensive: 529 530```rust 531fn prop_prime_iff_in_the_sieve(n: usize) -> bool { 532 sieve(n) == (0..(n + 1)).filter(|&i| is_prime(i)).collect::<Vec<_>>() 533} 534``` 535 536It tests that for each number between 0 and n, inclusive, the naive primality test 537yields the same result as the sieve. 538 539Now, if we run it: 540 541```rust 542fn main() { 543 quickcheck(prop_all_prime as fn(usize) -> bool); 544 quickcheck(prop_prime_iff_in_the_sieve as fn(usize) -> bool); 545} 546``` 547 548we see that it fails immediately for value n = 2. 549 550``` 551[quickcheck] TEST FAILED. Arguments: (2) 552``` 553 554If we inspect `sieve()` once again, we see that we mistakenly mark `2` as 555non-prime. Removing the line `marked[2] = true;` results in both properties 556passing. 557 558### What's not in this port of QuickCheck? 559 560I think I've captured the key features, but there are still things missing: 561 562* As of now, only functions with 8 or fewer parameters can be quickchecked. 563This limitation can be lifted to some `N`, but requires an implementation 564for each `n` of the `Testable` trait. 565* Functions that fail because of a stack overflow are not caught by QuickCheck. 566Therefore, such failures will not have a witness attached 567to them. (I'd like to fix this, but I don't know how.) 568* `Coarbitrary` does not exist in any form in this package. I think it's 569possible; I just haven't gotten around to it yet. 570