Automated property based testing for Rust (with shrinking).

Andrew Gallant

Last update: Dec 27, 2022

Related tags

Security tools quickcheck

Overview

quickcheck

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

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

Dual-licensed under MIT or the UNLICENSE.

Documentation

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

Simple example

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

#[cfg(test)]
#[macro_use]
extern crate quickcheck;

fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
    let mut rev = vec!();
    for x in xs.iter() {
        rev.insert(0, x.clone())
    }
    rev
}

#[cfg(test)]
mod tests {
  quickcheck! {
      fn prop(xs: Vec<u32>) -> bool {
          xs == reverse(&reverse(&xs))
      }
  }
}

This example uses the quickcheck! macro, which is backwards compatible with old versions of Rust.

The `#[quickcheck]` attribute

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

To use the #[quickcheck] attribute, you must import the quickcheck macro from the quickcheck_macros crate:

#[cfg(test)]
extern crate quickcheck;
#[cfg(test)]
#[macro_use(quickcheck)]
extern crate quickcheck_macros;

#[cfg(test)]
mod tests {
    fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
        let mut rev = vec!();
        for x in xs {
            rev.insert(0, x.clone())
        }
        rev
    }

    #[quickcheck]
    fn double_reversal_is_identity(xs: Vec<isize>) -> bool {
        xs == reverse(&reverse(&xs))
    }
}

Installation

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

[dependencies]
quickcheck = "1"

If you're only using quickcheck in your test code, then you can add it as a development dependency instead:

[dev-dependencies]
quickcheck = "1"

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

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

N.B. When using quickcheck (either directly or via the attributes), RUST_LOG=quickcheck enables info! so that it shows useful output (like the number of tests passed). This is not needed to show witnesses for failures.

Crate features:

"use_logging": (Enabled by default.) Enables the log messages governed RUST_LOG.
"regex": (Enabled by default.) Enables the use of regexes with env_logger.

Minimum Rust version policy

This crate's minimum supported rustc version is 1.46.0.

The current policy is that the minimum Rust version required to use this crate can be increased in minor version updates. For example, if crate 1.0 requires Rust 1.20.0, then crate 1.0.z for all values of z will also require Rust 1.20.0 or newer. However, crate 1.y for y > 0 may require a newer minimum version of Rust.

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

With all of that said, currently, rand is a public dependency of quickcheck. Therefore, the MSRV policy above only applies when it is more aggressive than rand's MSRV policy. Otherwise, quickcheck will defer to rand's MSRV policy.

Compatibility

In general, this crate considers the Arbitrary implementations provided as implementation details. Strategies may or may not change over time, which may cause new test failures, presumably due to the discovery of new bugs due to a new kind of witness being generated. These sorts of changes may happen in semver compatible releases.

Alternative Rust crates for property testing

The proptest crate is inspired by the Hypothesis framework for Python. You can read a comparison between proptest and quickcheck here and here. In particular, proptest improves on the concept of shrinking. So if you've ever had problems/frustration with shrinking in quickcheck, then proptest might be worth a try!

Alternatives for fuzzing

Please see the Rust Fuzz Book and the arbitrary crate.

Discarding test results (or, properties are polymorphic!)

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

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

pub fn quickcheck<A: Testable>(f: A) {
    // elided
}

So quickcheck can test any value with a type that satisfies the Testable trait. Great, so what is this Testable business?

pub trait Testable {
    fn result(&self, &mut Gen) -> TestResult;
}

This trait states that a type is testable if it can produce a TestResult given a source of randomness. (A TestResult stores information about the results of a test, like whether it passed, failed or has been discarded.)

Sure enough, bool satisfies the Testable trait:

impl Testable for bool {
    fn result(&self, _: &mut Gen) -> TestResult {
        TestResult::from_bool(*self)
    }
}

But in the example, we gave a function to quickcheck. Yes, functions can satisfy Testable too!

impl<A: Arbitrary + Debug, B: Testable> Testable for fn(A) -> B {
    fn result(&self, g: &mut Gen) -> TestResult {
        // elided
    }
}

Which says that a function satisfies Testable if and only if it has a single parameter type (whose values can be randomly generated and shrunk) and returns any type (that also satisfies Testable). So a function with type fn(usize) -> bool satisfies Testable since usize satisfies Arbitrary and bool satisfies Testable.

So to discard a test, we need to return something other than bool. What if we just returned a TestResult directly? That should work, but we'll need to make sure TestResult satisfies Testable:

impl Testable for TestResult {
    fn result(&self, _: &mut Gen) -> TestResult { self.clone() }
}

Now we can test functions that return a TestResult directly.

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

fn prop(xs: Vec<isize>) -> TestResult {
    if xs.len() != 1 {
        return TestResult::discard()
    }
    TestResult::from_bool(xs == reverse(&xs))
}
quickcheck(prop as fn(Vec<isize>) -> TestResult);

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

So now our property returns a TestResult, which allows us to encode a bit more information. There are a few more convenience functions defined for the TestResult type. For example, we can't just return a bool, so we convert a bool value to a TestResult.

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

N.B. Since discarding a test means it neither passes nor fails, quickcheck will try to replace the discarded test with a fresh one. However, if your condition is seldom met, it's possible that quickcheck will have to settle for running fewer tests than usual. By default, if quickcheck can't find 100 valid tests after trying 10,000 times, then it will give up. These parameters may be changed using QuickCheck::tests and QuickCheck::max_tests, or by setting the QUICKCHECK_TESTS and QUICKCHECK_MAX_TESTS environment variables. There is also QUICKCHECK_MIN_TESTS_PASSED which sets the minimum number of valid tests that need pass (defaults to 0) in order for it to be considered a success.

Shrinking

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

fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
    let mut rev = vec![];
    for i in 1..xs.len() {
        rev.insert(0, xs[i].clone())
    }
    rev
}

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

fn prop(xs: Vec<isize>) -> bool {
    xs == reverse(&reverse(&xs))
}
quickcheck(prop as fn(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 nearly guaranteed to get this counter-example every time:

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

Which is going to be much easier to debug.

More Thorough Checking

Quickcheck uses random input to test, so it won't always find bugs that could be uncovered with a particular property. You can improve your odds of finding these latent bugs by spending more CPU cycles asking quickcheck to find them for you. There are a few different ways to do this, and which one you choose is mostly a matter of taste.

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

Running in a Loop

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

#!/usr/bin/bash

while true
do
    cargo test qc_
    if [[ x$? != x0 ]] ; then
        exit $?
    fi
done

One thing to note is that this script passes the qc_ filter to cargo test. This assumes that you've prefixed all your quickcheck properties with qc_. You could leave off the filter, but then you would be running all your deterministic tests as well, which would take time away from quickcheck!

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

Cranking the Number of Tests

Another approach is to just ask quickcheck to run properties more times. You can do this either via the tests() method, or via the QUICKCHECK_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, which makes it more suitable for something like a release cycle that wants to really hammer your software.

Making Arbitrary Smarter

This approach entails spending more time generating interesting inputs in your implementations of Arbitrary. The idea is to focus on the corner cases. This approach can be tricky because programmers are not usually great at intuiting corner cases, and the whole idea of property checking is to take that burden off the programmer. Despite the theoretical discomfort, this approach can turn out to be practical.

Generating Structs

It is very simple to generate structs in QuickCheck. Consider the following example, where the struct Point is defined:

struct Point {
    x: i32,
    y: i32,
}

In order to generate a random Point instance, you need to implement the trait Arbitrary for the struct Point:

use quickcheck::{Arbitrary, Gen};

impl Arbitrary for Point {
    fn arbitrary(g: &mut Gen) -> Point {
        Point {
            x: i32::arbitrary(g),
            y: i32::arbitrary(g),
        }
    }
}

Case study: The Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple and elegant way to find all primes less than or equal to N. Briefly, the algorithm works by allocating an array with N slots containing booleans. Slots marked with false correspond to prime numbers (or numbers not known to be prime while building the sieve) and slots marked with true are known to not be prime. For each n, all of its multiples in this array are marked as true. When all n have been checked, the numbers marked false are returned as the primes.

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

fn sieve(n: usize) -> Vec<usize> {
    if n <= 1 {
        return vec![];
    }

    let mut marked = vec![false; n+1];
    marked[0] = true;
    marked[1] = true;
    marked[2] = true;
    for p in 2..n {
        for i in (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 an easy one to make. It's OK if you can't spot it, because we're going to use QuickCheck to help us track it down.

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

fn is_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)] divides n with base cases for 0 and 1.

Now we can write our QuickCheck property:

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

And finally, we need to invoke quickcheck with our property:

fn main() {
    quickcheck(prop_all_prime as fn(usize) -> bool);
}

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

The output of running this program has this message:

[quickcheck] TEST FAILED. Arguments: (4)

Which says that sieve failed the prop_all_prime test when given n = 4. Because of shrinking, it was able to find a (hopefully) minimal counter-example for our property.

With such a short counter-example, it's hopefully a bit easier to narrow down where the bug is. Since 4 is returned, it's likely never marked as being not prime. Since 4 is a multiple of 2, its slot should be marked as true when p = 2 on these lines:

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

Ah! But does the .. (range) operator include n? Nope! This particular operator is a half-open interval.

A 2*p..n range will never yield 4 when n = 4. When we change this to 2*p..n+1, all tests pass.

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

But hold on... we're not done yet. Right now, our property tests that all the numbers returned by sieve are prime but it doesn't test if the list is complete. It does not ensure that all the primes between 0 and n are found.

Here's a property that is more comprehensive:

fn prop_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 test yields the same result as the sieve.

Now, if we run it:

fn main() {
    quickcheck(prop_all_prime as fn(usize) -> bool);
    quickcheck(prop_prime_iff_in_the_sieve as fn(usize) -> bool);
}

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

[quickcheck] TEST FAILED. Arguments: (2)

If we inspect sieve() once again, we see that we mistakenly mark 2 as non-prime. Removing the line marked[2] = true; results in both properties passing.

What's not in this port of QuickCheck?

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

Only functions with 8 or fewer parameters can be quickchecked. This limitation can be lifted to some N, but requires an implementation for each n of the Testable trait.
Functions that fail because of a stack overflow are not caught by QuickCheck. Therefore, such failures will not have a witness attached to 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 that it ever will.
Arbitrary is not implemented for closures. See issue #56 for more details on why.

Comments

RFC: remove dependency on `rand` ecosystem

I am no longer happy about depending on the rand crates. There is too much churn, too many crates, and IMO, worst of all, there is no desire to add a minimal version check to their CI. Which means anything that depends on quickcheck in turn cannot reliably have its own minimal version check.

Because I am tired of depending on rand, I have started removing it completely where possible. For example, in walkdir, I've removed quickcheck as a dependency. In ripgrep, I've removed tempfile as a dependency, because it in turn was the only thing bringing rand into ripgrep's dependency tree.

I don't see any other path forward here. I can either continue to grin and bear rand, drop everything that depends on randomness, or figure out how to generate randomness without rand. Specifically, I'd very much like to add a minimal version check back to the regex crate, which catches bugs that happen in practice. (See here and here.) My sense is that there is some design space in the ecosystem for a simple source of randomness that doesn't need to be cryptographically secure, and an API that does not experience significant churn. Certainly, quickcheck does not need a cryptographic random number generator.

With that said, there is some infrastructure in the rand API that is incredibly useful. For example, quickcheck makes heavy use of the Rng::gen method for generating values based on type.

So it seems like if we have something like the Rng trait with with a non-cryptographic RNG, then we'd be probably good to go.

Are there other avenues here? What have I missed? My experience in building infrastructure for randomness is pretty limited, so am I underestimating the difficulty involved here?

Another side to this question is whether any users of quickcheck are leveraging parts of the rand ecosystem that would be difficult or impossible to do if we broke ties with rand.
question

opened by BurntSushi 37
make arbitrary generate full range of integers
Aims to fix #119, #190 and #233. Changes the implementation of Arbitrary for numbers to ignore the size of gen, and instead pick uniformly from the entire range of the type.

Todo:

[x] change behavior

[X] integer types

[x] floating-point types

[X] add tests

[x] explain new meaning of Gen's size() in documentation
opened by maxbla 22

Strings generated by default should have more usual characters

Strings typically generted look like this:

򒽹򪬛򘌟󥫹񕘼򟶹񍀝󿡥񰫩􂒡𻘒򅇪򍸈򁑙򟪆󴥏􅲴󩇇Ք𡫗󼺆򺩪𾺗𵅟𻎚񦎅񳜿󔈐ᘤ񜾊񺥿򍔛󆬭𙚹񃃣񥊆򇆗򂤇􀑬󨍏󉨫򺌑񽙕񷗮󻐉𿞊񹩵򖬊񣁇󘅛󖛉𼄠󄚷򽕎

񡰎𣒌󹣵

􅘤󀞶񼮳𮕇򀁕񗎰򀇦򹖻񚂫󚾪򃢛ൾ𬫤񘖤􇾷򇍤񮅈弅򥅽񨭴󶈡񫯭𧚼䝠Ᏼ􌷞󻃃񛑓󵎍𯭜􄼧򛷺񚂛񊪧󯱩񩴝𛭑𨀒񡥍󛢘񺐢𵑌眻󖙞񅉊򛻨񆷮󸧖󵔸񎽔򡚥񂼮򆼤񄓭񷬗􂭡򼠀񥉑󓊢򡽍􀟞񮆀񿫇񿌝򒋏񜎀񢝒򋯼񹌈􃔪򈟙󟬠󀧸󀉖𠥤񌡭𧆼񦛼񶰆񂠑𻗛򙄒

򁂺󶼀𰷹𾏉򮘭򈝥󓞤򫚁󙖘󆖙𰻟񇫙𴋅𠈼󹌀凾𖙟𠓕𾭭𗢐񥂡񇫘򫯝󨃖僧󰲺򘳑𛉏񡴶􏹊򔌇ᘼ􎜅󇆯󈤟󷃚􎞎񦖄봄򬩘񎩭򓲜󍥊𰀈􍆔񥝖򅈳𿴛􌆗񍏰񛯚􏡩򵆠񝭆􍘣򅕜򞙄󬍦񜟩󐮐򊽛󘉏񔀊񎇝󞏏񥍇󕎎𑝩񡨭򋡠򪙃󆂵𫟯񩽗𕡫򞠇𤷸򙺛򄎩򍮂򒹣䴒𻉜󸅩􎬙𷆊񲎀񪨌򌀀􄻖񇋒󹜅

񒢩򊟗𥁿򌅞񬕧𞎂񮕄򞿮ҙ󐢉󠢜񭈑󕓴󅸛򕎅𳞇񪉩񞢜򭧘󛦦󎪦󱏚홀񍋧篬󦲫򈧹񍔿񚣪򛍾𡚙󫬴򽉫񈝗񔁯󹕩񦟠󼝹𦼄󹆲񜋑񠇒񇽖􋤋񤔇󐂚񼛍􄼀󮀯𔯀󦃂񵒵򄯎󩎅򓊕򯠎񌬆롇񘺊񵺾𕧨񚾓򍚬󷈮󠢧򦂼𹥞󮾛򼢁􀏜򸬟󮃣򪾂򬁷񯕞񋓝󞭤󰥔񐮃󲏫󻞻򻬒􄑎򉗭򄫛󨶇󔽟򹑹򼹨򨵖񰊅񻣊

񕂍􌥩񵉗񶗖𬉞魊񞦹󙤵𦪀𒮡󄮽𕗠񥽕􂥦􈲹󙁡򞞌𵄐𳎩뚲󄬥򶰂񷷢򝬉񞝟򃹪腎󑍭򒋀򔲙󉺿񲥓𝹯󩬑

񾧍󝫮򎿛窯񕓨􈲶񽶛򩪣򁹡􂏔򛘎򘇀𠷺񎂦񭭸񽎊𐊊𨺿򆊺𗞩􌽂񁸶輬񄃸񅙜񐢳񔧏񈙄𝐳𪉛

𥹠𼞳󾢙𔅿􊭷񾣐򎕊񭳖򕸌󎀛򶃣𜿉􀢛󶄿𲊊񪟛񈘉񲻦񭩂󳄒𾺲𯆊񏸆񌼠񭳒񷞈򁓎􈋖𚜸󿒲򁔀𰤫򫥑򞼲𥐸񥾥󓮿򳖱𗋕󳉋􉠨𖍳󷕝򝘊򏩰󁺱񍰉崳󀁈𒯻򿮥𯙇񥻂󓿭򫙎񄦽񠷎𞸁񵳳󿧻􂯓󹗄򇪾󽘝󉵷򗚫񸐄󘁳񏶌񥵾󧒟򮫰𖪄񞼗􏾢𶕘򊮴𗰼򄌋񺿭򣘸

򵑆򢀍򯪂񏁾𧔥󼖈򬿚󰖓􁯌򁆙񎠤񬴞𝒲󹩝򾜣񰢝󭙯񠵛񹘦󒳼񡫉󺲢񘾥񿔷󾣎埙󊽑򼪐򊰭񠮺禹󾣣𼵝򒹐񓪊󫨬򫄒󦉂񇫄󬆿򻃃񯟶󜚓𷗚𲦂󻔴񮏂򶰎񥊢񰵪񢔀򁻢喒󢷅󟽄񚐚񓼈򭶸􅇆󭏂𜯃𨖉󑶧򪌿𨌽򄔖𱢼򩱼򫮴

𻥻򖿄󎰁𔱷𑒂𼟊􇼅𲂄􈔜󉄘􋫢𖔄񋺆𬎽򛖢򠬔􃸫􀵆𮘜󛥺􂶐򵄤𺐅񀕛񟥠􏽑󹫠򡧄󒸡򰎜򊎰񥑌񇇣𩔒򰅈򵄯񓣏󓢍򑛛򉨸𾓊𷅣𵼤𦌘򓀞𽣟򞴍

񒚞񙶴󫃔񀹮񣍯𵘣󾈣򐜴󄌿𦶞󯛫󄊁񳍮񚶨󡷣𸫂𞳊񏜪󜮶𺾆㮄񆡐󓶭﯈󊎊󿧺􏋔󤍄󁾒򣎦񛦋򯠖􍓙񜠔򇺱𓆦񟣤󝢧򱁕񗽳󶱮󶊼󿓊򾚓򵵆򼫏󄈬򜒕󱦡񘗏򮑏󔼋򂄸󺺘𨛽󚲁񶗜󖿭󣠯򆱩񰊫憎񳥒񼷵𠗆񍻠󽖾𿂆󑓓񎚯򦉠𘊲

𳸈򋸴󂩗񽰋񄨪񏉙򀤵󕳷𚱲򵚑󓶵񀐡󈁡򮖵񜬃񫡵񠬳񬶊𡱭񅼺򝙾񞬁ꈺ𹖉𵌛ロ񒁭􉫒󋟑񔊢򽲓񿨈񑜰񇿴򢣖􍟣򰮍󿘱󄡣󹉚𬥿񋘙𔭦򡎑

󰺿󶄔𬆷󱂌󉬞󾪢񖖖񮊕񝧃򾽼񨤳𸾂𣑌󸕖󹴌𬜄𑼦􌷱򩔤𖌸񥺼񗎱񗱐󲣑𴒨󴹒𹒪󋊌󨴖򙀁򁿵񫘕󐇯򂯲񵕌񁢜󹤨򙢄񨓩򄠑񻨸𻍦󦩒񬪸󻴴񜀛򝇩񼗕򣚉󵏛󣹥򉭞򦚎񀺲񆛜󮟏񟒫𲹇򋼡򷧘񿩬󎭝򪆀𛑛񻉞󝫨𡞱㆒

򼋡󯻭􁤛񎔝󸴭󜈰񱚱픦󎍆𢐻򷟝񞮵蘪󖣢𫭪𲊺󿜚񈅗򿧙󿴞񫌱衯򉕭򊞴қ󴙠𱜯񙐰򍊌񮨬󪾪򮝂𾨆񱘾񡠇팢򗡗򽑶򴸟𙅡򎋎𐠮󶖉򄡏󟛿􏠰򟿢񚨬憲򭫉􉌞񘮝󗕖񡏤𮺀񫐀𔚈񷋭𙪢򇬣򛡡񗚡򓛏򘌶𦷴񶵍򮵔숥𲟪

񘿘𛀦򵊻󠑜󼾐𙈨󹲃𸯕𜆦淅󍵮𰂘񛦑󛫌󝌲󔕇󹙮񧃷񧈵񠶄򙹫󓰆򒈐􃎢邮򣻖񩹖𓋱𥥫񩘆

It fails (or takes long) to find simple case like a when something starts with a space, special character or like this.

I think normal characters should be preferred to deeply Unicode things.

I think by default there should be tiers of characters classes:

Bug-prone characters: whitespace, punctuation, control characters, maybe up to 5 selected Unicode queeries like zero-width space;
[a-zA-Z0-9_];
Unicode characters in the first plane;
Everything else.

And character generator may aim for, for example, 10% of buggy chars, 40% of [a-zA-Z0-9_], 40% of basic Unicode characters, 10% of everything else.

enhancement

opened by vi 20

Feature request: Add auto-derivators for structs and enums

I want quickcheck to have a compiler plugin that automatically generates Arbitrary impl for structs and enums composed of Arbitrary types, like with serialisation.

That should shrink

extern crate quickcheck;

use quickcheck::Arbitrary;

#[derive(Clone,Debug)]
struct Mumu {
    a : u32,
    b : String,
}

#[derive(Clone,Debug)]
enum Qqq {
    Lol,
    Ror,
    Kokoko(Mumu),
    Totot(u32),
}

impl Arbitrary for Mumu {
    fn arbitrary<G : quickcheck::Gen>(g:&mut G) -> Mumu {
        Mumu {a : Arbitrary::arbitrary(g), b : Arbitrary::arbitrary(g) }
    }
    fn shrink(&self) -> Box<Iterator<Item=Self>> {
        Box::new ( (self.a.clone(), self.b.clone()).shrink().map(|(aa,bb)| Mumu { a: aa, b:bb}))
    }
}

impl Arbitrary for Qqq {
    fn arbitrary<G : quickcheck::Gen>(g:&mut G) -> Qqq {
        let y = g.next_u32() % 4;
        match y {
            0 => Qqq::Lol,
            1 => Qqq::Ror,
            2 => Qqq::Kokoko(Arbitrary::arbitrary(g)),
            3 => Qqq::Totot(Arbitrary::arbitrary(g)),
            _ => panic!(),
        }
    }
    fn shrink(&self) -> Box<Iterator<Item=Self>> {
        match self {
            &Qqq::Totot(ref x) => Box::new(x.shrink().map(|s| Qqq::Totot(s))),
            &Qqq::Kokoko(ref x) => Box::new(x.shrink().map(|s| Qqq::Kokoko(s))),
            _ => quickcheck::empty_shrinker(),
        }
    }
}



#[test]
fn it_works() {
    fn qqq(x : Qqq) -> bool {
        if let Qqq::Kokoko(Mumu { a : v, b: _ }) = x {
            return v != 4
        }
        true
    }

    quickcheck::QuickCheck::new().tests(1000_000_000).quickcheck(qqq as fn(Qqq) -> bool);
}

extern crate quickcheck;

use quickcheck::Arbitrary;

#[derive(Clone,Debug,Arbitrary)]
struct Mumu {
    a : u32,
    b : String,
}

#[derive(Clone,Debug,Arbitrary)]
enum Qqq {
    Lol,
    Ror,
    Kokoko(Mumu),
    Totot(u32),
}

#[test]
fn it_works() {
    fn qqq(x : Qqq) -> bool {
        if let Qqq::Kokoko(Mumu { a : v, b: _ }) = x {
            return v != 4
        }
        true
    }

    quickcheck::QuickCheck::new().tests(1000_000_000).quickcheck(qqq as fn(Qqq) -> bool);
}

enhancement help wanted

opened by vi 18

The random selection doesn't appear to be very random
I have a type which wraps an i32, and wrote an Arbitrary impl like so:

trait Arbitrary<PgDate> { fn arbitrary<G: Gen>() -> Self { PgDate(i32::arbitrary()) } }

When I actually output what it's running with, the values are only ranging from 100 to -100, instead of 100 completely random numbers as I'd expect. Additionally, shrink appears to be flawed on these types. My understanding was that quickcheck would test for known problematic values for a given type. For i32 I'd expect that to at minimum be 1, 0, -1, i32::MAX and i32::MIN, but when I add the shrink like so:

fn shrink(&self) -> Box<Iterator<Item=Self>> { Box::new(self.0.shrink().map(PgDate))

I just see the same range of -100 to 100. This caused a critical bug that occurs for any values less than -2451545 to go unnoticed.
opened by sgrif 17
Add autoshrinking.

I appreciate that this is a very large pull request, and I'm open to breaking it up. This change adds automatic shrinking to StdGen, so users no-longer have to implement shrink alongside arbitrary for their types. The output of the random number generator is cached into a vector, and to shrink testcases we replay simplified versions of this random buffer; this allows us to shrink data structures without knowing anything about them.

opened by SeanRBurton 17
Generating arbitrary recursive datastructures can overflow the stack pretty easily

For example, this Arbitrary implementation for a simple tree will overflow the stack more often than when running tests. I'm not sure how to bound the depth of the recursion here.
question

opened by emberian 16

rand 0.6.5 seems to be breaking the build

Not exactly sure if this belongs here or on rust-random/rand. Just tried to run cargo test with quickcheck = "0.8.0" in [dev-dependencies], without using the macros or importing them. This is what I get:

[...]

error[E0277]: the trait bound `rand_xorshift::XorShiftRng: rand_core::SeedableRng` is not satisfied
   --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/rand-0.6.5/src/deprecated.rs:242:5
    |
242 | /     fn from_seed(seed: Self::Seed) -> Self {
243 | |         XorShiftRng(::rand_xorshift::XorShiftRng::from_seed(seed))
244 | |     }
    | |_____^ the trait `rand_core::SeedableRng` is not implemented for `rand_xorshift::XorShiftRng`

error[E0277]: the trait bound `rand_hc::Hc128Rng: rand_core::SeedableRng` is not satisfied
   --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/rand-0.6.5/src/deprecated.rs:280:5
    |
280 |     type Seed = <rngs::StdRng as SeedableRng>::Seed;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `rand_core::SeedableRng` is not implemented for `rand_hc::Hc128Rng`

error[E0277]: the trait bound `rand_hc::Hc128Rng: rand_core::SeedableRng` is not satisfied
   --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/rand-0.6.5/src/deprecated.rs:282:5
    |
282 | /     fn from_seed(seed: Self::Seed) -> Self {
283 | |         StdRng(rngs::StdRng::from_seed(seed))
284 | |     }
    | |_____^ the trait `rand_core::SeedableRng` is not implemented for `rand_hc::Hc128Rng`

error: aborting due to 34 previous errors

For more information about this error, try `rustc --explain E0277`.
error: Could not compile `rand`.

opened by brycx 15

Re-export all of `rand`

Users of quickcheck need to use the same version of rand that quickcheck does if they want to make full use of rand's API, esp when implementing Arbitrary. This allows them to use quickcheck::rand, and still use another version of rand for other purposes if they wish.

opened by jsgf 14

implement Testable for Fn*

Using rustc 1.0.0-nightly (3d0d9bb6f 2015-01-12 22:56:20 +0000):

fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
    let mut rev = vec!();
    for x in xs.iter() {
        rev.insert(0, x.clone())
    }
    rev
}

#[test]
fn reverse_identity() {
  fn prop(xs: Vec<i32>) -> bool {
    xs == reverse(reverse(xs.as_slice()).as_slice())
  }
  quickcheck(prop);
}

produces

error: the trait `quickcheck::tester::Testable` is not implemented for the type `fn(collections::vec::Vec<i32>) -> bool {tests::reverse_identity::prop}`

quickcheck(false) compiles; this appears to be specific to the fn impls, including the zero-arg fn.

enhancement wontfix

opened by abr-egn 13

Examples [WIP]

Ok, next pull request coming up!

I've build a buggy version of a quicksort implementation with a quite common bug (neither the smaller_than nor the larger_than part include the "equal" part). QuickCheck will find this bug.

I also added a more descriptive name to the invariant on your reverse example. I hope you like it :wink:

Work in Progress: I don't know how elegant my implementation is. I tried to keep it to my Haskell implementation, which is only 5 lines. This implementation gets kinda messy with conversions between vectors and ranges. I will ask for feedback in the Rust IRC :+1:

opened by moonglum 11

Fix simple example in README

Maybe I'm doing something wrong, but the example didn't compile for me until I added a use crate::reverse:

PS C:\code\playground> cargo test
   Compiling playground v0.1.0 (C:\code\playground)
  --> src\main.rs:17:19
   |
17 |             xs == reverse(&reverse(&xs))
   |                   ^^^^^^^ not found in this scope
   |
help: consider importing this function
   |
15 |     use crate::reverse;
   |

I also ran rustfmt on it; the vec![] is a suggestion from it.

opened by lynn 0

Explain what the crate does in lib.rs docs

Currently https://docs.rs/quickcheck doesn't say much about what this crate does. I think having most info in the README is OK, but probably there should be some info in the crate docs root as well.

opened by lynn 0
Implement something like choose_weighted for `Gen`
Can we include something like frequency from Haskell's QuickCheck? It will generalize this pattern and make it more convenient to use, for example:

g.choose_weighted(&[ (10, g.gen_range(0..0xB0) as u8 as char), (2, ...), (5, ...), (1, ...), (1, ...), (1, ...), ])

The implementation can be something like this:

impl Gen { pub fn choose_weighted<'a, T>(&mut self, slice: &'a [(u32, T)]) -> Option<&'a T> { slice.choose_weighted(&mut self.rng, |item| item.0).ok().map(|item| &item.1) } }

I know that in this particular example can be problem with eager evaluation which is not problem in Haskell since it is lazy, however, we can solve it by adding another associated function which chooses from closures instead of values. In other words, do it exactly like it is done for Result with and/and_then and or/or_else functions.

What do you think?
opened by DrSplinter 0
Add support for arrays powered by const generics without unsafe or libs

Closes #187

Alternative to #282 that does not use unsafe

This seems to have been a heavily requested feature since 2017 now but the hold back was that implementing array support via macros heavily impacts compile times, is limited to some predefined arbitrary length and bloats the docs with unnecessary clutters. The wait was for const generic stabilization which is finally upon us, so we can utilize that and add array support!

Also lol while I was writing the shrink implementation I was like uff too much cloning there's probably a way to write this better that Sushi will tell me about, then while opening this PR I decided to double check there are no PRs open that already do this, which is when I found #282 and saw the exact same implementation I reached. Now I feel much less bad about the implementation

opened by Mathspy 2