aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJeff Vander Stoep <jeffv@google.com>2021-10-19 10:09:02 +0200
committerJeff Vander Stoep <jeffv@google.com>2021-10-27 10:18:18 +0200
commitaa840b6535a14b55bb68eaa4d8b2661ac2b3f091 (patch)
tree652dec8e6682fb4336bf4357803cbb9aaaae2278
parent8bcbd0917c958f2e4e5a10c1b643537b31968efb (diff)
downloadquickcheck-aa840b6535a14b55bb68eaa4d8b2661ac2b3f091.tar.gz
Import quickcheck 1.0.3
This is a test dependency for at least 10 other crates. Test: cargo2android.py --device --run --dependencies; m Change-Id: I67de6452192310b59fd1f972663c697da3fcd439
Diffstat
-rw-r--r--.cargo_vcs_info.json5
-rw-r--r--.github/workflows/ci.yml76
-rw-r--r--.gitignore7
-rw-r--r--COPYING3
-rw-r--r--Cargo.toml47
-rw-r--r--Cargo.toml.orig30
l---------LICENSE1
-rw-r--r--LICENSE-MIT21
-rw-r--r--METADATA19
-rw-r--r--MODULE_LICENSE_MIT0
-rw-r--r--OWNERS1
-rw-r--r--README.md583
-rw-r--r--UNLICENSE24
-rw-r--r--examples/btree_set_range.rs55
-rw-r--r--examples/out_of_bounds.rs13
-rw-r--r--examples/reverse.rs16
-rw-r--r--examples/reverse_single.rs19
-rw-r--r--examples/sieve.rs39
-rw-r--r--examples/sort.rs46
-rw-r--r--rustfmt.toml2
-rw-r--r--src/arbitrary.rs1586
-rw-r--r--src/lib.rs93
-rw-r--r--src/tester.rs451
-rw-r--r--src/tests.rs288
24 files changed, 3425 insertions, 0 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..3668676
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+ "git": {
+ "sha1": "defde6fb0ce20b0c8c4e672aa9ae821f7d1f5b38"
+ }
+}
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
new file mode 100644
index 0000000..b41f2bc
--- /dev/null
+++ b/.github/workflows/ci.yml
@@ -0,0 +1,76 @@
+name: ci
+on:
+ pull_request:
+ push:
+ branches:
+ - master
+ schedule:
+ - cron: '00 01 * * *'
+jobs:
+ test:
+ name: test
+ runs-on: ${{ matrix.os }}
+ strategy:
+ matrix:
+ build:
+ - pinned
+ - stable
+ - beta
+ - nightly
+ - macos
+ - win-msvc
+ - win-gnu
+ include:
+ - build: pinned
+ os: ubuntu-18.04
+ rust: 1.46.0
+ - build: stable
+ os: ubuntu-18.04
+ rust: stable
+ - build: beta
+ os: ubuntu-18.04
+ rust: beta
+ - build: nightly
+ os: ubuntu-18.04
+ rust: nightly
+ - build: macos
+ os: macos-latest
+ rust: stable
+ - build: win-msvc
+ os: windows-2019
+ rust: stable
+ - build: win-gnu
+ os: windows-2019
+ rust: stable-x86_64-gnu
+ steps:
+ - name: Checkout repository
+ uses: actions/checkout@v1
+ with:
+ fetch-depth: 1
+ - name: Install Rust
+ uses: hecrj/setup-rust-action@v1
+ with:
+ rust-version: ${{ matrix.rust }}
+ - run: cargo build --verbose
+ - run: cargo doc --verbose
+ - run: cargo test --verbose
+ - run: cargo build --verbose --manifest-path quickcheck_macros/Cargo.toml
+ - run: cargo test --verbose --manifest-path quickcheck_macros/Cargo.toml
+
+ rustfmt:
+ name: rustfmt
+ runs-on: ubuntu-18.04
+ steps:
+ - name: Checkout repository
+ uses: actions/checkout@v1
+ with:
+ fetch-depth: 1
+ - name: Install Rust
+ uses: hecrj/setup-rust-action@v1
+ with:
+ rust-version: stable
+ - name: Install rustfmt
+ run: rustup component add rustfmt
+ - name: Check formatting
+ run: |
+ cargo fmt --all -- --check
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..002549c
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+doc
+.*.swp
+tags
+target
+build
+Cargo.lock
+*~
diff --git a/COPYING b/COPYING
new file mode 100644
index 0000000..bb9c20a
--- /dev/null
+++ b/COPYING
@@ -0,0 +1,3 @@
+This project is dual-licensed under the Unlicense and MIT licenses.
+
+You may use this code under the terms of either license.
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..aa4ad58
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,47 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+edition = "2018"
+name = "quickcheck"
+version = "1.0.3"
+authors = ["Andrew Gallant <jamslam@gmail.com>"]
+exclude = ["/.travis.yml", "/Makefile", "/ctags.rust", "/session.vim"]
+description = "Automatic property based testing with shrinking."
+homepage = "https://github.com/BurntSushi/quickcheck"
+documentation = "https://docs.rs/quickcheck"
+readme = "README.md"
+keywords = ["testing", "quickcheck", "property", "shrinking", "fuzz"]
+categories = ["development-tools::testing"]
+license = "Unlicense/MIT"
+repository = "https://github.com/BurntSushi/quickcheck"
+
+[lib]
+name = "quickcheck"
+[dependencies.env_logger]
+version = "0.8.2"
+optional = true
+default-features = false
+
+[dependencies.log]
+version = "0.4"
+optional = true
+
+[dependencies.rand]
+version = "0.8"
+features = ["getrandom", "small_rng"]
+default-features = false
+
+[features]
+default = ["regex", "use_logging"]
+regex = ["env_logger/regex"]
+use_logging = ["log", "env_logger"]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..17cc17a
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,30 @@
+[package]
+name = "quickcheck"
+version = "1.0.3" #:version
+authors = ["Andrew Gallant <jamslam@gmail.com>"]
+description = "Automatic property based testing with shrinking."
+documentation = "https://docs.rs/quickcheck"
+homepage = "https://github.com/BurntSushi/quickcheck"
+repository = "https://github.com/BurntSushi/quickcheck"
+readme = "README.md"
+keywords = ["testing", "quickcheck", "property", "shrinking", "fuzz"]
+categories = ["development-tools::testing"]
+license = "Unlicense/MIT"
+exclude = ["/.travis.yml", "/Makefile", "/ctags.rust", "/session.vim"]
+edition = "2018"
+
+[workspace]
+members = ["quickcheck_macros"]
+
+[features]
+default = ["regex", "use_logging"]
+use_logging = ["log", "env_logger"]
+regex = ["env_logger/regex"]
+
+[lib]
+name = "quickcheck"
+
+[dependencies]
+env_logger = { version = "0.8.2", default-features = false, optional = true }
+log = { version = "0.4", optional = true }
+rand = { version = "0.8", default-features = false, features = ["getrandom", "small_rng"] }
diff --git a/LICENSE b/LICENSE
new file mode 120000
index 0000000..7f9a88e
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1 @@
+LICENSE-MIT \ No newline at end of file
diff --git a/LICENSE-MIT b/LICENSE-MIT
new file mode 100644
index 0000000..3b0a5dc
--- /dev/null
+++ b/LICENSE-MIT
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Andrew Gallant
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/METADATA b/METADATA
new file mode 100644
index 0000000..b67fcbf
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,19 @@
+name: "quickcheck"
+description: "Automatic property based testing with shrinking."
+third_party {
+ url {
+ type: HOMEPAGE
+ value: "https://crates.io/crates/quickcheck"
+ }
+ url {
+ type: ARCHIVE
+ value: "https://static.crates.io/crates/quickcheck/quickcheck-1.0.3.crate"
+ }
+ version: "1.0.3"
+ license_type: NOTICE
+ last_upgrade_date {
+ year: 2021
+ month: 10
+ day: 19
+ }
+}
diff --git a/MODULE_LICENSE_MIT b/MODULE_LICENSE_MIT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_MIT
diff --git a/OWNERS b/OWNERS
new file mode 100644
index 0000000..45dc4dd
--- /dev/null
+++ b/OWNERS
@@ -0,0 +1 @@
+include platform/prebuilts/rust:master:/OWNERS
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..2546a63
--- /dev/null
+++ b/README.md
@@ -0,0 +1,583 @@
+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](https://hackage.haskell.org/package/QuickCheck).)
+
+[![Build status](https://github.com/BurntSushi/quickcheck/workflows/ci/badge.svg)](https://github.com/BurntSushi/quickcheck/actions)
+[![](https://meritbadge.herokuapp.com/quickcheck)](https://crates.io/crates/quickcheck)
+
+Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org).
+
+
+### Documentation
+
+The API is fully documented:
+[https://docs.rs/quickcheck](https://docs.rs/quickcheck).
+
+
+### Simple example
+
+Here's an example that tests a function that reverses a vector:
+
+```rust
+#[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:
+
+```rust
+#[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:
+
+```toml
+[dependencies]
+quickcheck = "1"
+```
+
+If you're only using `quickcheck` in your test code, then you can add it as a
+development dependency instead:
+
+```toml
+[dev-dependencies]
+quickcheck = "1"
+```
+
+If you want to use the `#[quickcheck]` attribute, then add `quickcheck_macros`
+
+```toml
+[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`](https://docs.rs/proptest) crate is inspired by the
+[Hypothesis](https://hypothesis.works) framework for Python.
+You can read a comparison between `proptest` and `quickcheck`
+[here](https://github.com/AltSysrq/proptest/blob/master/proptest/README.md#differences-between-quickcheck-and-proptest)
+and
+[here](https://github.com/AltSysrq/proptest/issues/15#issuecomment-348382287).
+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](https://rust-fuzz.github.io/book/introduction.html)
+and the
+[`arbitrary`](https://crates.io/crates/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:
+
+```rust
+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?
+
+```rust
+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:
+
+```rust
+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!
+
+```rust
+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`:
+
+```rust
+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.
+
+```rust
+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`](https://github.com/BurntSushi/quickcheck/blob/master/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](https://docs.rs/quickcheck/*/quickcheck/struct.TestResult.html).
+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`](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.tests)
+and [`QuickCheck::max_tests`](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.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)
+
+```rust
+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))`:
+
+```rust
+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`](https://github.com/rust-fuzz/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.
+
+```bash
+#!/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()](https://docs.rs/quickcheck/*/quickcheck/struct.QuickCheck.html#method.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:
+
+```rust
+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`:
+
+```rust
+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](https://en.wikipedia.org/wiki/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:
+
+```rust
+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:
+
+```rust
+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:
+
+```rust
+fn prop_all_prime(n: usize) -> bool {
+ sieve(n).into_iter().all(is_prime)
+}
+```
+
+And finally, we need to invoke `quickcheck` with our property:
+
+```rust
+fn main() {
+ quickcheck(prop_all_prime as fn(usize) -> bool);
+}
+```
+
+A fully working source file with this code is in
+[`examples/sieve.rs`](https://github.com/BurntSushi/quickcheck/blob/master/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:
+
+```rust
+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:
+
+```rust
+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:
+
+```rust
+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](https://github.com/BurntSushi/quickcheck/issues/56)
+for more details on why.
diff --git a/UNLICENSE b/UNLICENSE
new file mode 100644
index 0000000..68a49da
--- /dev/null
+++ b/UNLICENSE
@@ -0,0 +1,24 @@
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.
+
+For more information, please refer to <http://unlicense.org/>
diff --git a/examples/btree_set_range.rs b/examples/btree_set_range.rs
new file mode 100644
index 0000000..0e7418b
--- /dev/null
+++ b/examples/btree_set_range.rs
@@ -0,0 +1,55 @@
+use std::collections::BTreeSet;
+use std::ops::Bound::{self, *};
+
+use quickcheck::{quickcheck, TestResult};
+
+/// Covers every `std::ops::Range*` plus variants with exclusive start.
+type RangeAny<T> = (Bound<T>, Bound<T>);
+
+/// Mimic `RangeBounds::contains`, stabilized in Rust 1.35.
+trait RangeBounds<T> {
+ fn contains(&self, _: &T) -> bool;
+}
+
+impl<T: PartialOrd> RangeBounds<T> for RangeAny<T> {
+ fn contains(&self, item: &T) -> bool {
+ (match &self.0 {
+ Included(start) => start <= item,
+ Excluded(start) => start < item,
+ Unbounded => true,
+ }) && (match &self.1 {
+ Included(end) => item <= end,
+ Excluded(end) => item < end,
+ Unbounded => true,
+ })
+ }
+}
+
+/// Checks conditions where `BTreeSet::range` panics:
+/// - Panics if range start > end.
+/// - Panics if range start == end and both bounds are Excluded.
+fn panics<T: PartialOrd>(range: RangeAny<T>) -> bool {
+ match (&range.0, &range.1) {
+ (Excluded(start), Excluded(end)) => start >= end,
+ (Included(start), Excluded(end))
+ | (Excluded(start), Included(end))
+ | (Included(start), Included(end)) => start > end,
+ (Unbounded, _) | (_, Unbounded) => false,
+ }
+}
+
+/// Checks that `BTreeSet::range` returns all items contained in the given `range`.
+fn check_range(set: BTreeSet<i32>, range: RangeAny<i32>) -> TestResult {
+ if panics(range) {
+ TestResult::discard()
+ } else {
+ let xs: BTreeSet<_> = set.range(range).cloned().collect();
+ TestResult::from_bool(
+ set.iter().all(|x| range.contains(x) == xs.contains(x)),
+ )
+ }
+}
+
+fn main() {
+ quickcheck(check_range as fn(_, _) -> TestResult);
+}
diff --git a/examples/out_of_bounds.rs b/examples/out_of_bounds.rs
new file mode 100644
index 0000000..10da938
--- /dev/null
+++ b/examples/out_of_bounds.rs
@@ -0,0 +1,13 @@
+use quickcheck::{quickcheck, TestResult};
+
+fn main() {
+ fn prop(length: usize, index: usize) -> TestResult {
+ let v: Vec<_> = (0..length).collect();
+ if index < length {
+ TestResult::discard()
+ } else {
+ TestResult::must_fail(move || v[index])
+ }
+ }
+ quickcheck(prop as fn(usize, usize) -> TestResult);
+}
diff --git a/examples/reverse.rs b/examples/reverse.rs
new file mode 100644
index 0000000..fff6e71
--- /dev/null
+++ b/examples/reverse.rs
@@ -0,0 +1,16 @@
+use quickcheck::quickcheck;
+
+fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
+ let mut rev = vec![];
+ for x in xs {
+ rev.insert(0, x.clone())
+ }
+ rev
+}
+
+fn main() {
+ fn equality_after_applying_twice(xs: Vec<isize>) -> bool {
+ xs == reverse(&reverse(&xs))
+ }
+ quickcheck(equality_after_applying_twice as fn(Vec<isize>) -> bool);
+}
diff --git a/examples/reverse_single.rs b/examples/reverse_single.rs
new file mode 100644
index 0000000..6112509
--- /dev/null
+++ b/examples/reverse_single.rs
@@ -0,0 +1,19 @@
+use quickcheck::{quickcheck, TestResult};
+
+fn reverse<T: Clone>(xs: &[T]) -> Vec<T> {
+ let mut rev = vec![];
+ for x in xs {
+ rev.insert(0, x.clone())
+ }
+ rev
+}
+
+fn main() {
+ 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);
+}
diff --git a/examples/sieve.rs b/examples/sieve.rs
new file mode 100644
index 0000000..f05b8e3
--- /dev/null
+++ b/examples/sieve.rs
@@ -0,0 +1,39 @@
+use quickcheck::quickcheck;
+
+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()
+}
+
+fn is_prime(n: usize) -> bool {
+ n != 0 && n != 1 && (2..).take_while(|i| i * i <= n).all(|i| n % i != 0)
+}
+
+fn main() {
+ fn prop_all_prime(n: usize) -> bool {
+ sieve(n).into_iter().all(is_prime)
+ }
+
+ fn prop_prime_iff_in_the_sieve(n: usize) -> bool {
+ sieve(n) == (0..(n + 1)).filter(|&i| is_prime(i)).collect::<Vec<_>>()
+ }
+
+ quickcheck(prop_all_prime as fn(usize) -> bool);
+ quickcheck(prop_prime_iff_in_the_sieve as fn(usize) -> bool);
+}
diff --git a/examples/sort.rs b/examples/sort.rs
new file mode 100644
index 0000000..0f495a0
--- /dev/null
+++ b/examples/sort.rs
@@ -0,0 +1,46 @@
+// This is a buggy quick sort implementation, QuickCheck will find the bug for
+// you.
+
+use quickcheck::quickcheck;
+
+fn smaller_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T> {
+ xs.iter().filter(|&x| *x < *pivot).map(|x| x.clone()).collect()
+}
+
+fn larger_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T> {
+ xs.iter().filter(|&x| *x > *pivot).map(|x| x.clone()).collect()
+}
+
+fn sortk<T: Clone + Ord>(x: &T, xs: &[T]) -> Vec<T> {
+ let mut result: Vec<T> = sort(&*smaller_than(xs, x));
+ let last_part = sort(&*larger_than(xs, x));
+ result.push(x.clone());
+ result.extend(last_part.iter().map(|x| x.clone()));
+ result
+}
+
+fn sort<T: Clone + Ord>(list: &[T]) -> Vec<T> {
+ if list.is_empty() {
+ vec![]
+ } else {
+ sortk(&list[0], &list[1..])
+ }
+}
+
+fn main() {
+ fn is_sorted(xs: Vec<isize>) -> bool {
+ for win in xs.windows(2) {
+ if win[0] > win[1] {
+ return false;
+ }
+ }
+ true
+ }
+
+ fn keeps_length(xs: Vec<isize>) -> bool {
+ xs.len() == sort(&*xs).len()
+ }
+ quickcheck(keeps_length as fn(Vec<isize>) -> bool);
+
+ quickcheck(is_sorted as fn(Vec<isize>) -> bool)
+}
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..aa37a21
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1,2 @@
+max_width = 79
+use_small_heuristics = "max"
diff --git a/src/arbitrary.rs b/src/arbitrary.rs
new file mode 100644
index 0000000..92f893b
--- /dev/null
+++ b/src/arbitrary.rs
@@ -0,0 +1,1586 @@
+use std::char;
+use std::collections::{
+ BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque,
+};
+use std::env;
+use std::ffi::{CString, OsString};
+use std::hash::{BuildHasher, Hash};
+use std::iter::{empty, once};
+use std::net::{
+ IpAddr, Ipv4Addr, Ipv6Addr, SocketAddr, SocketAddrV4, SocketAddrV6,
+};
+use std::num::Wrapping;
+use std::num::{
+ NonZeroU128, NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize,
+};
+use std::ops::{
+ Bound, Range, RangeFrom, RangeFull, RangeInclusive, RangeTo,
+ RangeToInclusive,
+};
+use std::path::PathBuf;
+use std::sync::Arc;
+use std::time::{Duration, SystemTime, UNIX_EPOCH};
+
+use rand::seq::SliceRandom;
+use rand::{self, Rng, SeedableRng};
+
+/// Gen represents a PRNG.
+///
+/// It is the source of randomness from which QuickCheck will generate
+/// values. An instance of `Gen` is passed to every invocation of
+/// `Arbitrary::arbitrary`, which permits callers to use lower level RNG
+/// routines to generate values.
+///
+/// It is unspecified whether this is a secure RNG or not. Therefore, callers
+/// should assume it is insecure.
+pub struct Gen {
+ rng: rand::rngs::SmallRng,
+ size: usize,
+}
+
+impl Gen {
+ /// Returns a `Gen` with the given size configuration.
+ ///
+ /// The `size` parameter controls the size of random values generated.
+ /// For example, it specifies the maximum length of a randomly generated
+ /// vector, but is and should not be used to control the range of a
+ /// randomly generated number. (Unless that number is used to control the
+ /// size of a data structure.)
+ pub fn new(size: usize) -> Gen {
+ Gen { rng: rand::rngs::SmallRng::from_entropy(), size: size }
+ }
+
+ /// Returns the size configured with this generator.
+ pub fn size(&self) -> usize {
+ self.size
+ }
+
+ /// Choose among the possible alternatives in the slice given. If the slice
+ /// is empty, then `None` is returned. Otherwise, a non-`None` value is
+ /// guaranteed to be returned.
+ pub fn choose<'a, T>(&mut self, slice: &'a [T]) -> Option<&'a T> {
+ slice.choose(&mut self.rng)
+ }
+
+ fn gen<T>(&mut self) -> T
+ where
+ rand::distributions::Standard: rand::distributions::Distribution<T>,
+ {
+ self.rng.gen()
+ }
+
+ fn gen_range<T, R>(&mut self, range: R) -> T
+ where
+ T: rand::distributions::uniform::SampleUniform,
+ R: rand::distributions::uniform::SampleRange<T>,
+ {
+ self.rng.gen_range(range)
+ }
+}
+
+/// Creates a shrinker with zero elements.
+pub fn empty_shrinker<A: 'static>() -> Box<dyn Iterator<Item = A>> {
+ Box::new(empty())
+}
+
+/// Creates a shrinker with a single element.
+pub fn single_shrinker<A: 'static>(value: A) -> Box<dyn Iterator<Item = A>> {
+ Box::new(once(value))
+}
+
+/// `Arbitrary` describes types whose values can be randomly generated and
+/// shrunk.
+///
+/// Aside from shrinking, `Arbitrary` is different from typical RNGs in that
+/// it respects `Gen::size()` for controlling how much memory a particular
+/// value uses, for practical purposes. For example, `Vec::arbitrary()`
+/// respects `Gen::size()` to decide the maximum `len()` of the vector.
+/// This behavior is necessary due to practical speed and size limitations.
+/// Conversely, `i32::arbitrary()` ignores `size()` since all `i32` values
+/// require `O(1)` memory and operations between `i32`s require `O(1)` time
+/// (with the exception of exponentiation).
+///
+/// Additionally, all types that implement `Arbitrary` must also implement
+/// `Clone`.
+pub trait Arbitrary: Clone + 'static {
+ /// Return an arbitrary value.
+ ///
+ /// Implementations should respect `Gen::size()` when decisions about how
+ /// big a particular value should be. Implementations should generally
+ /// defer to other `Arbitrary` implementations to generate other random
+ /// values when necessary. The `Gen` type also offers a few RNG helper
+ /// routines.
+ fn arbitrary(g: &mut Gen) -> Self;
+
+ /// Return an iterator of values that are smaller than itself.
+ ///
+ /// The way in which a value is "smaller" is implementation defined. In
+ /// some cases, the interpretation is obvious: shrinking an integer should
+ /// produce integers smaller than itself. Others are more complex, for
+ /// example, shrinking a `Vec` should both shrink its size and shrink its
+ /// component values.
+ ///
+ /// The iterator returned should be bounded to some reasonable size.
+ ///
+ /// It is always correct to return an empty iterator, and indeed, this
+ /// is the default implementation. The downside of this approach is that
+ /// witnesses to failures in properties will be more inscrutable.
+ fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+ empty_shrinker()
+ }
+}
+
+impl Arbitrary for () {
+ fn arbitrary(_: &mut Gen) -> () {
+ ()
+ }
+}
+
+impl Arbitrary for bool {
+ fn arbitrary(g: &mut Gen) -> bool {
+ g.gen()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = bool>> {
+ if *self {
+ single_shrinker(false)
+ } else {
+ empty_shrinker()
+ }
+ }
+}
+
+impl<A: Arbitrary> Arbitrary for Option<A> {
+ fn arbitrary(g: &mut Gen) -> Option<A> {
+ if g.gen() {
+ None
+ } else {
+ Some(Arbitrary::arbitrary(g))
+ }
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Option<A>>> {
+ match *self {
+ None => empty_shrinker(),
+ Some(ref x) => {
+ let chain = single_shrinker(None).chain(x.shrink().map(Some));
+ Box::new(chain)
+ }
+ }
+ }
+}
+
+impl<A: Arbitrary, B: Arbitrary> Arbitrary for Result<A, B> {
+ fn arbitrary(g: &mut Gen) -> Result<A, B> {
+ if g.gen() {
+ Ok(Arbitrary::arbitrary(g))
+ } else {
+ Err(Arbitrary::arbitrary(g))
+ }
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Result<A, B>>> {
+ match *self {
+ Ok(ref x) => {
+ let xs = x.shrink();
+ let tagged = xs.map(Ok);
+ Box::new(tagged)
+ }
+ Err(ref x) => {
+ let xs = x.shrink();
+ let tagged = xs.map(Err);
+ Box::new(tagged)
+ }
+ }
+ }
+}
+
+macro_rules! impl_arb_for_single_tuple {
+ ($(($type_param:ident, $tuple_index:tt),)*) => {
+ impl<$($type_param),*> Arbitrary for ($($type_param,)*)
+ where $($type_param: Arbitrary,)*
+ {
+ fn arbitrary(g: &mut Gen) -> ($($type_param,)*) {
+ (
+ $(
+ $type_param::arbitrary(g),
+ )*
+ )
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item=($($type_param,)*)>> {
+ let iter = ::std::iter::empty();
+ $(
+ let cloned = self.clone();
+ let iter = iter.chain(
+ self.$tuple_index.shrink().map(move |shr_value| {
+ let mut result = cloned.clone();
+ result.$tuple_index = shr_value;
+ result
+ })
+ );
+ )*
+ Box::new(iter)
+ }
+ }
+ };
+}
+
+macro_rules! impl_arb_for_tuples {
+ (@internal [$($acc:tt,)*]) => { };
+ (@internal [$($acc:tt,)*] ($type_param:ident, $tuple_index:tt), $($rest:tt,)*) => {
+ impl_arb_for_single_tuple!($($acc,)* ($type_param, $tuple_index),);
+ impl_arb_for_tuples!(@internal [$($acc,)* ($type_param, $tuple_index),] $($rest,)*);
+ };
+ ($(($type_param:ident, $tuple_index:tt),)*) => {
+ impl_arb_for_tuples!(@internal [] $(($type_param, $tuple_index),)*);
+ };
+}
+
+impl_arb_for_tuples! {
+ (A, 0),
+ (B, 1),
+ (C, 2),
+ (D, 3),
+ (E, 4),
+ (F, 5),
+ (G, 6),
+ (H, 7),
+}
+
+impl<A: Arbitrary> Arbitrary for Vec<A> {
+ fn arbitrary(g: &mut Gen) -> Vec<A> {
+ let size = {
+ let s = g.size();
+ g.gen_range(0..s)
+ };
+ (0..size).map(|_| A::arbitrary(g)).collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Vec<A>>> {
+ VecShrinker::new(self.clone())
+ }
+}
+
+///Iterator which returns successive attempts to shrink the vector `seed`
+struct VecShrinker<A> {
+ seed: Vec<A>,
+ /// How much which is removed when trying with smaller vectors
+ size: usize,
+ /// The end of the removed elements
+ offset: usize,
+ /// The shrinker for the element at `offset` once shrinking of individual
+ /// elements are attempted
+ element_shrinker: Box<dyn Iterator<Item = A>>,
+}
+
+impl<A: Arbitrary> VecShrinker<A> {
+ fn new(seed: Vec<A>) -> Box<dyn Iterator<Item = Vec<A>>> {
+ let es = match seed.get(0) {
+ Some(e) => e.shrink(),
+ None => return empty_shrinker(),
+ };
+ let size = seed.len();
+ Box::new(VecShrinker {
+ seed: seed,
+ size: size,
+ offset: size,
+ element_shrinker: es,
+ })
+ }
+
+ /// Returns the next shrunk element if any, `offset` points to the index
+ /// after the returned element after the function returns
+ fn next_element(&mut self) -> Option<A> {
+ loop {
+ match self.element_shrinker.next() {
+ Some(e) => return Some(e),
+ None => match self.seed.get(self.offset) {
+ Some(e) => {
+ self.element_shrinker = e.shrink();
+ self.offset += 1;
+ }
+ None => return None,
+ },
+ }
+ }
+ }
+}
+
+impl<A> Iterator for VecShrinker<A>
+where
+ A: Arbitrary,
+{
+ type Item = Vec<A>;
+ fn next(&mut self) -> Option<Vec<A>> {
+ // Try with an empty vector first
+ if self.size == self.seed.len() {
+ self.size /= 2;
+ self.offset = self.size;
+ return Some(vec![]);
+ }
+ if self.size != 0 {
+ // Generate a smaller vector by removing the elements between
+ // (offset - size) and offset
+ let xs1 = self.seed[..(self.offset - self.size)]
+ .iter()
+ .chain(&self.seed[self.offset..])
+ .cloned()
+ .collect();
+ self.offset += self.size;
+ // Try to reduce the amount removed from the vector once all
+ // previous sizes tried
+ if self.offset > self.seed.len() {
+ self.size /= 2;
+ self.offset = self.size;
+ }
+ Some(xs1)
+ } else {
+ // A smaller vector did not work so try to shrink each element of
+ // the vector instead Reuse `offset` as the index determining which
+ // element to shrink
+
+ // The first element shrinker is already created so skip the first
+ // offset (self.offset == 0 only on first entry to this part of the
+ // iterator)
+ if self.offset == 0 {
+ self.offset = 1
+ }
+
+ match self.next_element() {
+ Some(e) => Some(
+ self.seed[..self.offset - 1]
+ .iter()
+ .cloned()
+ .chain(Some(e).into_iter())
+ .chain(self.seed[self.offset..].iter().cloned())
+ .collect(),
+ ),
+ None => None,
+ }
+ }
+ }
+}
+
+impl<K: Arbitrary + Ord, V: Arbitrary> Arbitrary for BTreeMap<K, V> {
+ fn arbitrary(g: &mut Gen) -> BTreeMap<K, V> {
+ let vec: Vec<(K, V)> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = BTreeMap<K, V>>> {
+ let vec: Vec<(K, V)> = self.clone().into_iter().collect();
+ Box::new(
+ vec.shrink().map(|v| v.into_iter().collect::<BTreeMap<K, V>>()),
+ )
+ }
+}
+
+impl<
+ K: Arbitrary + Eq + Hash,
+ V: Arbitrary,
+ S: BuildHasher + Default + Clone + 'static,
+ > Arbitrary for HashMap<K, V, S>
+{
+ fn arbitrary(g: &mut Gen) -> Self {
+ let vec: Vec<(K, V)> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+ let vec: Vec<(K, V)> = self.clone().into_iter().collect();
+ Box::new(vec.shrink().map(|v| v.into_iter().collect::<Self>()))
+ }
+}
+
+impl<T: Arbitrary + Ord> Arbitrary for BTreeSet<T> {
+ fn arbitrary(g: &mut Gen) -> BTreeSet<T> {
+ let vec: Vec<T> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = BTreeSet<T>>> {
+ let vec: Vec<T> = self.clone().into_iter().collect();
+ Box::new(vec.shrink().map(|v| v.into_iter().collect::<BTreeSet<T>>()))
+ }
+}
+
+impl<T: Arbitrary + Ord> Arbitrary for BinaryHeap<T> {
+ fn arbitrary(g: &mut Gen) -> BinaryHeap<T> {
+ let vec: Vec<T> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = BinaryHeap<T>>> {
+ let vec: Vec<T> = self.clone().into_iter().collect();
+ Box::new(
+ vec.shrink().map(|v| v.into_iter().collect::<BinaryHeap<T>>()),
+ )
+ }
+}
+
+impl<T: Arbitrary + Eq + Hash, S: BuildHasher + Default + Clone + 'static>
+ Arbitrary for HashSet<T, S>
+{
+ fn arbitrary(g: &mut Gen) -> Self {
+ let vec: Vec<T> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+ let vec: Vec<T> = self.clone().into_iter().collect();
+ Box::new(vec.shrink().map(|v| v.into_iter().collect::<Self>()))
+ }
+}
+
+impl<T: Arbitrary> Arbitrary for LinkedList<T> {
+ fn arbitrary(g: &mut Gen) -> LinkedList<T> {
+ let vec: Vec<T> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = LinkedList<T>>> {
+ let vec: Vec<T> = self.clone().into_iter().collect();
+ Box::new(
+ vec.shrink().map(|v| v.into_iter().collect::<LinkedList<T>>()),
+ )
+ }
+}
+
+impl<T: Arbitrary> Arbitrary for VecDeque<T> {
+ fn arbitrary(g: &mut Gen) -> VecDeque<T> {
+ let vec: Vec<T> = Arbitrary::arbitrary(g);
+ vec.into_iter().collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = VecDeque<T>>> {
+ let vec: Vec<T> = self.clone().into_iter().collect();
+ Box::new(vec.shrink().map(|v| v.into_iter().collect::<VecDeque<T>>()))
+ }
+}
+
+impl Arbitrary for IpAddr {
+ fn arbitrary(g: &mut Gen) -> IpAddr {
+ let ipv4: bool = g.gen();
+ if ipv4 {
+ IpAddr::V4(Arbitrary::arbitrary(g))
+ } else {
+ IpAddr::V6(Arbitrary::arbitrary(g))
+ }
+ }
+}
+
+impl Arbitrary for Ipv4Addr {
+ fn arbitrary(g: &mut Gen) -> Ipv4Addr {
+ Ipv4Addr::new(g.gen(), g.gen(), g.gen(), g.gen())
+ }
+}
+
+impl Arbitrary for Ipv6Addr {
+ fn arbitrary(g: &mut Gen) -> Ipv6Addr {
+ Ipv6Addr::new(
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ g.gen(),
+ )
+ }
+}
+
+impl Arbitrary for SocketAddr {
+ fn arbitrary(g: &mut Gen) -> SocketAddr {
+ SocketAddr::new(Arbitrary::arbitrary(g), g.gen())
+ }
+}
+
+impl Arbitrary for SocketAddrV4 {
+ fn arbitrary(g: &mut Gen) -> SocketAddrV4 {
+ SocketAddrV4::new(Arbitrary::arbitrary(g), g.gen())
+ }
+}
+
+impl Arbitrary for SocketAddrV6 {
+ fn arbitrary(g: &mut Gen) -> SocketAddrV6 {
+ SocketAddrV6::new(Arbitrary::arbitrary(g), g.gen(), g.gen(), g.gen())
+ }
+}
+
+impl Arbitrary for PathBuf {
+ fn arbitrary(g: &mut Gen) -> PathBuf {
+ // use some real directories as guesses, so we may end up with
+ // actual working directories in case that is relevant.
+ let here =
+ env::current_dir().unwrap_or(PathBuf::from("/test/directory"));
+ let temp = env::temp_dir();
+ #[allow(deprecated)]
+ let home = env::home_dir().unwrap_or(PathBuf::from("/home/user"));
+ let mut p = g
+ .choose(&[
+ here,
+ temp,
+ home,
+ PathBuf::from("."),
+ PathBuf::from(".."),
+ PathBuf::from("../../.."),
+ PathBuf::new(),
+ ])
+ .unwrap()
+ .to_owned();
+ p.extend(Vec::<OsString>::arbitrary(g).iter());
+ p
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = PathBuf>> {
+ let mut shrunk = vec![];
+ let mut popped = self.clone();
+ if popped.pop() {
+ shrunk.push(popped);
+ }
+
+ // Iterating over a Path performs a small amount of normalization.
+ let normalized = self.iter().collect::<PathBuf>();
+ if normalized.as_os_str() != self.as_os_str() {
+ shrunk.push(normalized);
+ }
+
+ // Add the canonicalized variant only if canonicalizing the path
+ // actually does something, making it (hopefully) smaller. Also, ignore
+ // canonicalization if canonicalization errors.
+ if let Ok(canonicalized) = self.canonicalize() {
+ if canonicalized.as_os_str() != self.as_os_str() {
+ shrunk.push(canonicalized);
+ }
+ }
+
+ Box::new(shrunk.into_iter())
+ }
+}
+
+impl Arbitrary for OsString {
+ fn arbitrary(g: &mut Gen) -> OsString {
+ OsString::from(String::arbitrary(g))
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = OsString>> {
+ let mystring: String = self.clone().into_string().unwrap();
+ Box::new(mystring.shrink().map(|s| OsString::from(s)))
+ }
+}
+
+impl Arbitrary for String {
+ fn arbitrary(g: &mut Gen) -> String {
+ let size = {
+ let s = g.size();
+ g.gen_range(0..s)
+ };
+ (0..size).map(|_| char::arbitrary(g)).collect()
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = String>> {
+ // Shrink a string by shrinking a vector of its characters.
+ let chars: Vec<char> = self.chars().collect();
+ Box::new(chars.shrink().map(|x| x.into_iter().collect::<String>()))
+ }
+}
+
+impl Arbitrary for CString {
+ fn arbitrary(g: &mut Gen) -> Self {
+ let size = {
+ let s = g.size();
+ g.gen_range(0..s)
+ };
+ // Use either random bytes or random UTF-8 encoded codepoints.
+ let utf8: bool = g.gen();
+ if utf8 {
+ CString::new(
+ (0..)
+ .map(|_| char::arbitrary(g))
+ .filter(|&c| c != '\0')
+ .take(size)
+ .collect::<String>(),
+ )
+ } else {
+ CString::new(
+ (0..)
+ .map(|_| u8::arbitrary(g))
+ .filter(|&c| c != b'\0')
+ .take(size)
+ .collect::<Vec<u8>>(),
+ )
+ }
+ .expect("null characters should have been filtered out")
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = CString>> {
+ // Use the implementation for a vec here, but make sure null characters
+ // are filtered out.
+ Box::new(VecShrinker::new(self.as_bytes().to_vec()).map(|bytes| {
+ CString::new(
+ bytes.into_iter().filter(|&c| c != 0).collect::<Vec<u8>>(),
+ )
+ .expect("null characters should have been filtered out")
+ }))
+ }
+}
+
+impl Arbitrary for char {
+ fn arbitrary(g: &mut Gen) -> char {
+ let mode = g.gen_range(0..100);
+ match mode {
+ 0..=49 => {
+ // ASCII + some control characters
+ g.gen_range(0..0xB0) as u8 as char
+ }
+ 50..=59 => {
+ // Unicode BMP characters
+ loop {
+ if let Some(x) = char::from_u32(g.gen_range(0..0x10000)) {
+ return x;
+ }
+ // ignore surrogate pairs
+ }
+ }
+ 60..=84 => {
+ // Characters often used in programming languages
+ g.choose(&[
+ ' ', ' ', ' ', '\t', '\n', '~', '`', '!', '@', '#', '$',
+ '%', '^', '&', '*', '(', ')', '_', '-', '=', '+', '[',
+ ']', '{', '}', ':', ';', '\'', '"', '\\', '|', ',', '<',
+ '>', '.', '/', '?', '0', '1', '2', '3', '4', '5', '6',
+ '7', '8', '9',
+ ])
+ .unwrap()
+ .to_owned()
+ }
+ 85..=89 => {
+ // Tricky Unicode, part 1
+ g.choose(&[
+ '\u{0149}', // a deprecated character
+ '\u{fff0}', // some of "Other, format" category:
+ '\u{fff1}',
+ '\u{fff2}',
+ '\u{fff3}',
+ '\u{fff4}',
+ '\u{fff5}',
+ '\u{fff6}',
+ '\u{fff7}',
+ '\u{fff8}',
+ '\u{fff9}',
+ '\u{fffA}',
+ '\u{fffB}',
+ '\u{fffC}',
+ '\u{fffD}',
+ '\u{fffE}',
+ '\u{fffF}',
+ '\u{0600}',
+ '\u{0601}',
+ '\u{0602}',
+ '\u{0603}',
+ '\u{0604}',
+ '\u{0605}',
+ '\u{061C}',
+ '\u{06DD}',
+ '\u{070F}',
+ '\u{180E}',
+ '\u{110BD}',
+ '\u{1D173}',
+ '\u{e0001}', // tag
+ '\u{e0020}', // tag space
+ '\u{e000}',
+ '\u{e001}',
+ '\u{ef8ff}', // private use
+ '\u{f0000}',
+ '\u{ffffd}',
+ '\u{ffffe}',
+ '\u{fffff}',
+ '\u{100000}',
+ '\u{10FFFD}',
+ '\u{10FFFE}',
+ '\u{10FFFF}',
+ // "Other, surrogate" characters are so that very special
+ // that they are not even allowed in safe Rust,
+ //so omitted here
+ '\u{3000}', // ideographic space
+ '\u{1680}',
+ // other space characters are already covered by two next
+ // branches
+ ])
+ .unwrap()
+ .to_owned()
+ }
+ 90..=94 => {
+ // Tricky unicode, part 2
+ char::from_u32(g.gen_range(0x2000..0x2070)).unwrap()
+ }
+ 95..=99 => {
+ // Completely arbitrary characters
+ g.gen()
+ }
+ _ => unreachable!(),
+ }
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = char>> {
+ Box::new((*self as u32).shrink().filter_map(char::from_u32))
+ }
+}
+
+macro_rules! unsigned_shrinker {
+ ($ty:ty) => {
+ mod shrinker {
+ pub struct UnsignedShrinker {
+ x: $ty,
+ i: $ty,
+ }
+
+ impl UnsignedShrinker {
+ pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> {
+ if x == 0 {
+ super::empty_shrinker()
+ } else {
+ Box::new(
+ vec![0]
+ .into_iter()
+ .chain(UnsignedShrinker { x: x, i: x / 2 }),
+ )
+ }
+ }
+ }
+
+ impl Iterator for UnsignedShrinker {
+ type Item = $ty;
+ fn next(&mut self) -> Option<$ty> {
+ if self.x - self.i < self.x {
+ let result = Some(self.x - self.i);
+ self.i = self.i / 2;
+ result
+ } else {
+ None
+ }
+ }
+ }
+ }
+ };
+}
+
+macro_rules! unsigned_problem_values {
+ ($t:ty) => {
+ &[<$t>::min_value(), 1, <$t>::max_value()]
+ };
+}
+
+macro_rules! unsigned_arbitrary {
+ ($($ty:tt),*) => {
+ $(
+ impl Arbitrary for $ty {
+ fn arbitrary(g: &mut Gen) -> $ty {
+ match g.gen_range(0..10) {
+ 0 => {
+ *g.choose(unsigned_problem_values!($ty)).unwrap()
+ },
+ _ => g.gen()
+ }
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item=$ty>> {
+ unsigned_shrinker!($ty);
+ shrinker::UnsignedShrinker::new(*self)
+ }
+ }
+ )*
+ }
+}
+
+unsigned_arbitrary! {
+ usize, u8, u16, u32, u64, u128
+}
+
+macro_rules! signed_shrinker {
+ ($ty:ty) => {
+ mod shrinker {
+ pub struct SignedShrinker {
+ x: $ty,
+ i: $ty,
+ }
+
+ impl SignedShrinker {
+ pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> {
+ if x == 0 {
+ super::empty_shrinker()
+ } else {
+ let shrinker = SignedShrinker { x: x, i: x / 2 };
+ let mut items = vec![0];
+ if shrinker.i < 0 && shrinker.x != <$ty>::MIN {
+ items.push(shrinker.x.abs());
+ }
+ Box::new(items.into_iter().chain(shrinker))
+ }
+ }
+ }
+
+ impl Iterator for SignedShrinker {
+ type Item = $ty;
+ fn next(&mut self) -> Option<$ty> {
+ if self.x == <$ty>::MIN
+ || (self.x - self.i).abs() < self.x.abs()
+ {
+ let result = Some(self.x - self.i);
+ self.i = self.i / 2;
+ result
+ } else {
+ None
+ }
+ }
+ }
+ }
+ };
+}
+
+macro_rules! signed_problem_values {
+ ($t:ty) => {
+ &[<$t>::min_value(), 0, <$t>::max_value()]
+ };
+}
+
+macro_rules! signed_arbitrary {
+ ($($ty:tt),*) => {
+ $(
+ impl Arbitrary for $ty {
+ fn arbitrary(g: &mut Gen) -> $ty {
+ match g.gen_range(0..10) {
+ 0 => {
+ *g.choose(signed_problem_values!($ty)).unwrap()
+ },
+ _ => g.gen()
+ }
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item=$ty>> {
+ signed_shrinker!($ty);
+ shrinker::SignedShrinker::new(*self)
+ }
+ }
+ )*
+ }
+}
+
+signed_arbitrary! {
+ isize, i8, i16, i32, i64, i128
+}
+
+macro_rules! float_problem_values {
+ ($path:path) => {{
+ // hack. see: https://github.com/rust-lang/rust/issues/48067
+ use $path as p;
+ &[p::NAN, p::NEG_INFINITY, p::MIN, -0., 0., p::MAX, p::INFINITY]
+ }};
+}
+
+macro_rules! float_arbitrary {
+ ($($t:ty, $path:path, $shrinkable:ty),+) => {$(
+ impl Arbitrary for $t {
+ fn arbitrary(g: &mut Gen) -> $t {
+ match g.gen_range(0..10) {
+ 0 => *g.choose(float_problem_values!($path)).unwrap(),
+ _ => {
+ use $path as p;
+ let exp = g.gen_range((0.)..p::MAX_EXP as i16 as $t);
+ let mantissa = g.gen_range((1.)..2.);
+ let sign = *g.choose(&[-1., 1.]).unwrap();
+ sign * mantissa * exp.exp2()
+ }
+ }
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = $t>> {
+ signed_shrinker!($shrinkable);
+ let it = shrinker::SignedShrinker::new(*self as $shrinkable);
+ Box::new(it.map(|x| x as $t))
+ }
+ }
+ )*};
+}
+
+float_arbitrary!(f32, std::f32, i32, f64, std::f64, i64);
+
+macro_rules! unsigned_non_zero_shrinker {
+ ($ty:tt) => {
+ mod shrinker {
+ pub struct UnsignedNonZeroShrinker {
+ x: $ty,
+ i: $ty,
+ }
+
+ impl UnsignedNonZeroShrinker {
+ pub fn new(x: $ty) -> Box<dyn Iterator<Item = $ty>> {
+ debug_assert!(x > 0);
+
+ if x == 1 {
+ super::empty_shrinker()
+ } else {
+ Box::new(
+ std::iter::once(1).chain(
+ UnsignedNonZeroShrinker { x: x, i: x / 2 },
+ ),
+ )
+ }
+ }
+ }
+
+ impl Iterator for UnsignedNonZeroShrinker {
+ type Item = $ty;
+
+ fn next(&mut self) -> Option<$ty> {
+ if self.x - self.i < self.x {
+ let result = Some(self.x - self.i);
+ self.i = self.i / 2;
+ result
+ } else {
+ None
+ }
+ }
+ }
+ }
+ };
+}
+
+macro_rules! unsigned_non_zero_arbitrary {
+ ($($ty:tt => $inner:tt),*) => {
+ $(
+ impl Arbitrary for $ty {
+ fn arbitrary(g: &mut Gen) -> $ty {
+ let mut v: $inner = g.gen();
+ if v == 0 {
+ v += 1;
+ }
+ $ty::new(v).expect("non-zero value contsturction failed")
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = $ty>> {
+ unsigned_non_zero_shrinker!($inner);
+ Box::new(shrinker::UnsignedNonZeroShrinker::new(self.get())
+ .map($ty::new)
+ .map(Option::unwrap))
+ }
+ }
+ )*
+ }
+}
+
+unsigned_non_zero_arbitrary! {
+ NonZeroUsize => usize,
+ NonZeroU8 => u8,
+ NonZeroU16 => u16,
+ NonZeroU32 => u32,
+ NonZeroU64 => u64,
+ NonZeroU128 => u128
+}
+
+impl<T: Arbitrary> Arbitrary for Wrapping<T> {
+ fn arbitrary(g: &mut Gen) -> Wrapping<T> {
+ Wrapping(T::arbitrary(g))
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = Wrapping<T>>> {
+ Box::new(self.0.shrink().map(|inner| Wrapping(inner)))
+ }
+}
+
+impl<T: Arbitrary> Arbitrary for Bound<T> {
+ fn arbitrary(g: &mut Gen) -> Bound<T> {
+ match g.gen_range(0..3) {
+ 0 => Bound::Included(T::arbitrary(g)),
+ 1 => Bound::Excluded(T::arbitrary(g)),
+ _ => Bound::Unbounded,
+ }
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = Bound<T>>> {
+ match *self {
+ Bound::Included(ref x) => {
+ Box::new(x.shrink().map(Bound::Included))
+ }
+ Bound::Excluded(ref x) => {
+ Box::new(x.shrink().map(Bound::Excluded))
+ }
+ Bound::Unbounded => empty_shrinker(),
+ }
+ }
+}
+
+impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for Range<T> {
+ fn arbitrary(g: &mut Gen) -> Range<T> {
+ Arbitrary::arbitrary(g)..Arbitrary::arbitrary(g)
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = Range<T>>> {
+ Box::new(
+ (self.start.clone(), self.end.clone()).shrink().map(|(s, e)| s..e),
+ )
+ }
+}
+
+impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeInclusive<T> {
+ fn arbitrary(g: &mut Gen) -> RangeInclusive<T> {
+ Arbitrary::arbitrary(g)..=Arbitrary::arbitrary(g)
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = RangeInclusive<T>>> {
+ Box::new(
+ (self.start().clone(), self.end().clone())
+ .shrink()
+ .map(|(s, e)| s..=e),
+ )
+ }
+}
+
+impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeFrom<T> {
+ fn arbitrary(g: &mut Gen) -> RangeFrom<T> {
+ Arbitrary::arbitrary(g)..
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = RangeFrom<T>>> {
+ Box::new(self.start.clone().shrink().map(|start| start..))
+ }
+}
+
+impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeTo<T> {
+ fn arbitrary(g: &mut Gen) -> RangeTo<T> {
+ ..Arbitrary::arbitrary(g)
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = RangeTo<T>>> {
+ Box::new(self.end.clone().shrink().map(|end| ..end))
+ }
+}
+
+impl<T: Arbitrary + Clone + PartialOrd> Arbitrary for RangeToInclusive<T> {
+ fn arbitrary(g: &mut Gen) -> RangeToInclusive<T> {
+ ..=Arbitrary::arbitrary(g)
+ }
+ fn shrink(&self) -> Box<dyn Iterator<Item = RangeToInclusive<T>>> {
+ Box::new(self.end.clone().shrink().map(|end| ..=end))
+ }
+}
+
+impl Arbitrary for RangeFull {
+ fn arbitrary(_: &mut Gen) -> RangeFull {
+ ..
+ }
+}
+
+impl Arbitrary for Duration {
+ fn arbitrary(gen: &mut Gen) -> Self {
+ let seconds = gen.gen_range(0..gen.size() as u64);
+ let nanoseconds = gen.gen_range(0..1_000_000);
+ Duration::new(seconds, nanoseconds)
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+ Box::new(
+ (self.as_secs(), self.subsec_nanos())
+ .shrink()
+ .map(|(secs, nanos)| Duration::new(secs, nanos % 1_000_000)),
+ )
+ }
+}
+
+impl<A: Arbitrary> Arbitrary for Box<A> {
+ fn arbitrary(g: &mut Gen) -> Box<A> {
+ Box::new(A::arbitrary(g))
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Box<A>>> {
+ Box::new((**self).shrink().map(Box::new))
+ }
+}
+
+impl<A: Arbitrary + Sync> Arbitrary for Arc<A> {
+ fn arbitrary(g: &mut Gen) -> Arc<A> {
+ Arc::new(A::arbitrary(g))
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Arc<A>>> {
+ Box::new((**self).shrink().map(Arc::new))
+ }
+}
+
+impl Arbitrary for SystemTime {
+ fn arbitrary(gen: &mut Gen) -> Self {
+ let after_epoch = bool::arbitrary(gen);
+ let duration = Duration::arbitrary(gen);
+ if after_epoch {
+ UNIX_EPOCH + duration
+ } else {
+ UNIX_EPOCH - duration
+ }
+ }
+
+ fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+ let duration = match self.duration_since(UNIX_EPOCH) {
+ Ok(duration) => duration,
+ Err(e) => e.duration(),
+ };
+ Box::new(
+ duration
+ .shrink()
+ .flat_map(|d| vec![UNIX_EPOCH + d, UNIX_EPOCH - d]),
+ )
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use std::collections::{
+ BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque,
+ };
+ use std::fmt::Debug;
+ use std::hash::Hash;
+ use std::num::Wrapping;
+ use std::path::PathBuf;
+
+ use super::{Arbitrary, Gen};
+
+ #[test]
+ fn arby_unit() {
+ assert_eq!(arby::<()>(), ());
+ }
+
+ macro_rules! arby_int {
+ ( $signed:expr, $($t:ty),+) => {$(
+ let mut arbys = (0..1_000_000).map(|_| arby::<$t>());
+ let mut problems = if $signed {
+ signed_problem_values!($t).iter()
+ } else {
+ unsigned_problem_values!($t).iter()
+ };
+ assert!(problems.all(|p| arbys.any(|arby| arby == *p)),
+ "Arbitrary does not generate all problematic values");
+ let max = <$t>::max_value();
+ let mid = (max + <$t>::min_value()) / 2;
+ // split full range of $t into chunks
+ // Arbitrary must return some value in each chunk
+ let double_chunks: $t = 9;
+ let chunks = double_chunks * 2; // chunks must be even
+ let lim: Box<dyn Iterator<Item=$t>> = if $signed {
+ Box::new((0..=chunks)
+ .map(|idx| idx - chunks / 2)
+ .map(|x| mid + max / (chunks / 2) * x))
+ } else {
+ Box::new((0..=chunks).map(|idx| max / chunks * idx))
+ };
+ let mut lim = lim.peekable();
+ while let (Some(low), Some(&high)) = (lim.next(), lim.peek()) {
+ assert!(arbys.any(|arby| low <= arby && arby <= high),
+ "Arbitrary doesn't generate numbers in {}..={}", low, high)
+ }
+ )*};
+ }
+
+ #[test]
+ fn arby_int() {
+ arby_int!(true, i8, i16, i32, i64, isize, i128);
+ }
+
+ #[test]
+ fn arby_uint() {
+ arby_int!(false, u8, u16, u32, u64, usize, u128);
+ }
+
+ macro_rules! arby_float {
+ ($($t:ty, $path:path),+) => {$({
+ use $path as p;
+ let mut arbys = (0..1_000_000).map(|_| arby::<$t>());
+ //NaN != NaN
+ assert!(arbys.any(|f| f.is_nan()),
+ "Arbitrary does not generate the problematic value NaN"
+ );
+ for p in float_problem_values!($path).iter().filter(|f| !f.is_nan()) {
+ assert!(arbys.any(|arby| arby == *p),
+ "Arbitrary does not generate the problematic value {}",
+ p
+ );
+ }
+ // split full range of $t into chunks
+ // Arbitrary must return some value in each chunk
+ let double_chunks: i8 = 9;
+ let chunks = double_chunks * 2; // chunks must be even
+ let lim = (-double_chunks..=double_chunks)
+ .map(|idx| <$t>::from(idx))
+ .map(|idx| p::MAX/(<$t>::from(chunks/2)) * idx);
+ let mut lim = lim.peekable();
+ while let (Some(low), Some(&high)) = (lim.next(), lim.peek()) {
+ assert!(
+ arbys.any(|arby| low <= arby && arby <= high),
+ "Arbitrary doesn't generate numbers in {:e}..={:e}",
+ low,
+ high,
+ )
+ }
+ })*};
+ }
+
+ #[test]
+ fn arby_float() {
+ arby_float!(f32, std::f32, f64, std::f64);
+ }
+
+ fn arby<A: Arbitrary>() -> A {
+ Arbitrary::arbitrary(&mut Gen::new(5))
+ }
+
+ // Shrink testing.
+ #[test]
+ fn unit() {
+ eq((), vec![]);
+ }
+
+ #[test]
+ fn bools() {
+ eq(false, vec![]);
+ eq(true, vec![false]);
+ }
+
+ #[test]
+ fn options() {
+ eq(None::<()>, vec![]);
+ eq(Some(false), vec![None]);
+ eq(Some(true), vec![None, Some(false)]);
+ }
+
+ #[test]
+ fn results() {
+ // Result<A, B> doesn't implement the Hash trait, so these tests
+ // depends on the order of shrunk results. Ug.
+ // TODO: Fix this.
+ ordered_eq(Ok::<bool, ()>(true), vec![Ok(false)]);
+ ordered_eq(Err::<(), bool>(true), vec![Err(false)]);
+ }
+
+ #[test]
+ fn tuples() {
+ eq((false, false), vec![]);
+ eq((true, false), vec![(false, false)]);
+ eq((true, true), vec![(false, true), (true, false)]);
+ }
+
+ #[test]
+ fn triples() {
+ eq((false, false, false), vec![]);
+ eq((true, false, false), vec![(false, false, false)]);
+ eq(
+ (true, true, false),
+ vec![(false, true, false), (true, false, false)],
+ );
+ }
+
+ #[test]
+ fn quads() {
+ eq((false, false, false, false), vec![]);
+ eq((true, false, false, false), vec![(false, false, false, false)]);
+ eq(
+ (true, true, false, false),
+ vec![(false, true, false, false), (true, false, false, false)],
+ );
+ }
+
+ #[test]
+ fn ints() {
+ // TODO: Test overflow?
+ eq(5isize, vec![0, 3, 4]);
+ eq(-5isize, vec![5, 0, -3, -4]);
+ eq(0isize, vec![]);
+ }
+
+ #[test]
+ fn ints8() {
+ eq(5i8, vec![0, 3, 4]);
+ eq(-5i8, vec![5, 0, -3, -4]);
+ eq(0i8, vec![]);
+ }
+
+ #[test]
+ fn ints16() {
+ eq(5i16, vec![0, 3, 4]);
+ eq(-5i16, vec![5, 0, -3, -4]);
+ eq(0i16, vec![]);
+ }
+
+ #[test]
+ fn ints32() {
+ eq(5i32, vec![0, 3, 4]);
+ eq(-5i32, vec![5, 0, -3, -4]);
+ eq(0i32, vec![]);
+ }
+
+ #[test]
+ fn ints64() {
+ eq(5i64, vec![0, 3, 4]);
+ eq(-5i64, vec![5, 0, -3, -4]);
+ eq(0i64, vec![]);
+ }
+
+ #[test]
+ fn ints128() {
+ eq(5i128, vec![0, 3, 4]);
+ eq(-5i128, vec![5, 0, -3, -4]);
+ eq(0i128, vec![]);
+ }
+
+ #[test]
+ fn uints() {
+ eq(5usize, vec![0, 3, 4]);
+ eq(0usize, vec![]);
+ }
+
+ #[test]
+ fn uints8() {
+ eq(5u8, vec![0, 3, 4]);
+ eq(0u8, vec![]);
+ }
+
+ #[test]
+ fn uints16() {
+ eq(5u16, vec![0, 3, 4]);
+ eq(0u16, vec![]);
+ }
+
+ #[test]
+ fn uints32() {
+ eq(5u32, vec![0, 3, 4]);
+ eq(0u32, vec![]);
+ }
+
+ #[test]
+ fn uints64() {
+ eq(5u64, vec![0, 3, 4]);
+ eq(0u64, vec![]);
+ }
+
+ #[test]
+ fn uints128() {
+ eq(5u128, vec![0, 3, 4]);
+ eq(0u128, vec![]);
+ }
+
+ macro_rules! define_float_eq {
+ ($ty:ty) => {
+ fn eq(s: $ty, v: Vec<$ty>) {
+ let shrunk: Vec<$ty> = s.shrink().collect();
+ for n in v {
+ let found = shrunk.iter().any(|&i| i == n);
+ if !found {
+ panic!(format!(
+ "Element {:?} was not found \
+ in shrink results {:?}",
+ n, shrunk
+ ));
+ }
+ }
+ }
+ };
+ }
+
+ #[test]
+ fn floats32() {
+ define_float_eq!(f32);
+
+ eq(0.0, vec![]);
+ eq(-0.0, vec![]);
+ eq(1.0, vec![0.0]);
+ eq(2.0, vec![0.0, 1.0]);
+ eq(-2.0, vec![0.0, 2.0, -1.0]);
+ eq(1.5, vec![0.0]);
+ }
+
+ #[test]
+ fn floats64() {
+ define_float_eq!(f64);
+
+ eq(0.0, vec![]);
+ eq(-0.0, vec![]);
+ eq(1.0, vec![0.0]);
+ eq(2.0, vec![0.0, 1.0]);
+ eq(-2.0, vec![0.0, 2.0, -1.0]);
+ eq(1.5, vec![0.0]);
+ }
+
+ #[test]
+ fn wrapping_ints32() {
+ eq(Wrapping(5i32), vec![Wrapping(0), Wrapping(3), Wrapping(4)]);
+ eq(
+ Wrapping(-5i32),
+ vec![Wrapping(5), Wrapping(0), Wrapping(-3), Wrapping(-4)],
+ );
+ eq(Wrapping(0i32), vec![]);
+ }
+
+ #[test]
+ fn vecs() {
+ eq(
+ {
+ let it: Vec<isize> = vec![];
+ it
+ },
+ vec![],
+ );
+ eq(
+ {
+ let it: Vec<Vec<isize>> = vec![vec![]];
+ it
+ },
+ vec![vec![]],
+ );
+ eq(vec![1isize], vec![vec![], vec![0]]);
+ eq(vec![11isize], vec![vec![], vec![0], vec![6], vec![9], vec![10]]);
+ eq(
+ vec![3isize, 5],
+ vec![
+ vec![],
+ vec![5],
+ vec![3],
+ vec![0, 5],
+ vec![2, 5],
+ vec![3, 0],
+ vec![3, 3],
+ vec![3, 4],
+ ],
+ );
+ }
+
+ macro_rules! map_tests {
+ ($name:ident, $ctor:expr) => {
+ #[test]
+ fn $name() {
+ ordered_eq($ctor, vec![]);
+
+ {
+ let mut map = $ctor;
+ map.insert(1usize, 1isize);
+
+ let shrinks = vec![
+ $ctor,
+ {
+ let mut m = $ctor;
+ m.insert(0, 1);
+ m
+ },
+ {
+ let mut m = $ctor;
+ m.insert(1, 0);
+ m
+ },
+ ];
+
+ ordered_eq(map, shrinks);
+ }
+ }
+ };
+ }
+
+ map_tests!(btreemap, BTreeMap::<usize, isize>::new());
+ map_tests!(hashmap, HashMap::<usize, isize>::new());
+
+ macro_rules! list_tests {
+ ($name:ident, $ctor:expr, $push:ident) => {
+ #[test]
+ fn $name() {
+ ordered_eq($ctor, vec![]);
+
+ {
+ let mut list = $ctor;
+ list.$push(2usize);
+
+ let shrinks = vec![
+ $ctor,
+ {
+ let mut m = $ctor;
+ m.$push(0);
+ m
+ },
+ {
+ let mut m = $ctor;
+ m.$push(1);
+ m
+ },
+ ];
+
+ ordered_eq(list, shrinks);
+ }
+ }
+ };
+ }
+
+ list_tests!(btreesets, BTreeSet::<usize>::new(), insert);
+ list_tests!(hashsets, HashSet::<usize>::new(), insert);
+ list_tests!(linkedlists, LinkedList::<usize>::new(), push_back);
+ list_tests!(vecdeques, VecDeque::<usize>::new(), push_back);
+
+ #[test]
+ fn binaryheaps() {
+ ordered_eq(
+ BinaryHeap::<usize>::new().into_iter().collect::<Vec<_>>(),
+ vec![],
+ );
+
+ {
+ let mut heap = BinaryHeap::<usize>::new();
+ heap.push(2usize);
+
+ let shrinks = vec![vec![], vec![0], vec![1]];
+
+ ordered_eq(heap.into_iter().collect::<Vec<_>>(), shrinks);
+ }
+ }
+
+ #[test]
+ fn chars() {
+ eq('\x00', vec![]);
+ }
+
+ // All this jazz is for testing set equality on the results of a shrinker.
+ fn eq<A: Arbitrary + Eq + Debug + Hash>(s: A, v: Vec<A>) {
+ let (left, right) = (shrunk(s), set(v));
+ assert_eq!(left, right);
+ }
+ fn shrunk<A: Arbitrary + Eq + Hash>(s: A) -> HashSet<A> {
+ set(s.shrink())
+ }
+ fn set<A: Hash + Eq, I: IntoIterator<Item = A>>(xs: I) -> HashSet<A> {
+ xs.into_iter().collect()
+ }
+
+ fn ordered_eq<A: Arbitrary + Eq + Debug>(s: A, v: Vec<A>) {
+ let (left, right) = (s.shrink().collect::<Vec<A>>(), v);
+ assert_eq!(left, right);
+ }
+
+ #[test]
+ fn bounds() {
+ use std::ops::Bound::*;
+ for i in -5..=5 {
+ ordered_eq(Included(i), i.shrink().map(Included).collect());
+ ordered_eq(Excluded(i), i.shrink().map(Excluded).collect());
+ }
+ eq(Unbounded::<i32>, vec![]);
+ }
+
+ #[test]
+ fn ranges() {
+ ordered_eq(0..0, vec![]);
+ ordered_eq(1..1, vec![0..1, 1..0]);
+ ordered_eq(3..5, vec![0..5, 2..5, 3..0, 3..3, 3..4]);
+ ordered_eq(5..3, vec![0..3, 3..3, 4..3, 5..0, 5..2]);
+ ordered_eq(3.., vec![0.., 2..]);
+ ordered_eq(..3, vec![..0, ..2]);
+ ordered_eq(.., vec![]);
+ ordered_eq(3..=5, vec![0..=5, 2..=5, 3..=0, 3..=3, 3..=4]);
+ ordered_eq(..=3, vec![..=0, ..=2]);
+ }
+
+ #[test]
+ fn pathbuf() {
+ ordered_eq(
+ PathBuf::from("/home/foo//.././bar"),
+ vec![
+ PathBuf::from("/home/foo//.."),
+ PathBuf::from("/home/foo/../bar"),
+ ],
+ );
+ }
+}
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..58dc99d
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,93 @@
+/*!
+This crate is a port of
+[Haskell's QuickCheck](https://hackage.haskell.org/package/QuickCheck).
+
+For detailed examples, please see the
+[README](https://github.com/BurntSushi/quickcheck).
+
+# 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.
+*/
+
+pub use crate::arbitrary::{empty_shrinker, single_shrinker, Arbitrary, Gen};
+pub use crate::tester::{quickcheck, QuickCheck, TestResult, Testable};
+
+/// A macro for writing quickcheck tests.
+///
+/// This macro takes as input one or more property functions to test, and
+/// produces a proper `#[test]` function for each property. If the property
+/// fails, the behavior is as if `quickcheck` were called on the property
+/// (i.e., it panics and fails the test).
+///
+/// Note that this macro doesn't support `mut` or patterns in parameters.
+///
+/// # Example
+///
+/// ```rust
+/// # #[macro_use] extern crate quickcheck; fn main() {
+/// quickcheck! {
+/// fn prop_reverse_reverse(xs: Vec<usize>) -> bool {
+/// let rev: Vec<_> = xs.clone().into_iter().rev().collect();
+/// let revrev: Vec<_> = rev.into_iter().rev().collect();
+/// xs == revrev
+/// }
+/// };
+/// # }
+/// ```
+#[macro_export]
+macro_rules! quickcheck {
+ (@as_items $($i:item)*) => ($($i)*);
+ {
+ $(
+ $(#[$m:meta])*
+ fn $fn_name:ident($($arg_name:ident : $arg_ty:ty),*) -> $ret:ty {
+ $($code:tt)*
+ }
+ )*
+ } => (
+ $crate::quickcheck! {
+ @as_items
+ $(
+ #[test]
+ $(#[$m])*
+ fn $fn_name() {
+ fn prop($($arg_name: $arg_ty),*) -> $ret {
+ $($code)*
+ }
+ $crate::quickcheck(prop as fn($($arg_ty),*) -> $ret);
+ }
+ )*
+ }
+ )
+}
+
+#[cfg(feature = "use_logging")]
+fn env_logger_init() -> Result<(), log::SetLoggerError> {
+ env_logger::try_init()
+}
+#[cfg(feature = "use_logging")]
+macro_rules! info {
+ ($($tt:tt)*) => {
+ log::info!($($tt)*)
+ };
+}
+
+#[cfg(not(feature = "use_logging"))]
+fn env_logger_init() {}
+#[cfg(not(feature = "use_logging"))]
+macro_rules! info {
+ ($($_ignore:tt)*) => {
+ ()
+ };
+}
+
+mod arbitrary;
+mod tester;
+
+#[cfg(test)]
+mod tests;
diff --git a/src/tester.rs b/src/tester.rs
new file mode 100644
index 0000000..e2eaa20
--- /dev/null
+++ b/src/tester.rs
@@ -0,0 +1,451 @@
+use std::cmp;
+use std::env;
+use std::fmt::Debug;
+use std::panic;
+
+use crate::{
+ tester::Status::{Discard, Fail, Pass},
+ Arbitrary, Gen,
+};
+
+/// The main QuickCheck type for setting configuration and running QuickCheck.
+pub struct QuickCheck {
+ tests: u64,
+ max_tests: u64,
+ min_tests_passed: u64,
+ gen: Gen,
+}
+
+fn qc_tests() -> u64 {
+ let default = 100;
+ match env::var("QUICKCHECK_TESTS") {
+ Ok(val) => val.parse().unwrap_or(default),
+ Err(_) => default,
+ }
+}
+
+fn qc_max_tests() -> u64 {
+ let default = 10_000;
+ match env::var("QUICKCHECK_MAX_TESTS") {
+ Ok(val) => val.parse().unwrap_or(default),
+ Err(_) => default,
+ }
+}
+
+fn qc_gen_size() -> usize {
+ let default = 100;
+ match env::var("QUICKCHECK_GENERATOR_SIZE") {
+ Ok(val) => val.parse().unwrap_or(default),
+ Err(_) => default,
+ }
+}
+
+fn qc_min_tests_passed() -> u64 {
+ let default = 0;
+ match env::var("QUICKCHECK_MIN_TESTS_PASSED") {
+ Ok(val) => val.parse().unwrap_or(default),
+ Err(_) => default,
+ }
+}
+
+impl QuickCheck {
+ /// Creates a new QuickCheck value.
+ ///
+ /// This can be used to run QuickCheck on things that implement `Testable`.
+ /// You may also adjust the configuration, such as the number of tests to
+ /// run.
+ ///
+ /// By default, the maximum number of passed tests is set to `100`, the max
+ /// number of overall tests is set to `10000` and the generator is created
+ /// with a size of `100`.
+ pub fn new() -> QuickCheck {
+ let gen = Gen::new(qc_gen_size());
+ let tests = qc_tests();
+ let max_tests = cmp::max(tests, qc_max_tests());
+ let min_tests_passed = qc_min_tests_passed();
+
+ QuickCheck { tests, max_tests, min_tests_passed, gen }
+ }
+
+ /// Set the random number generator to be used by QuickCheck.
+ pub fn gen(self, gen: Gen) -> QuickCheck {
+ QuickCheck { gen, ..self }
+ }
+
+ /// Set the number of tests to run.
+ ///
+ /// This actually refers to the maximum number of *passed* tests that
+ /// can occur. Namely, if a test causes a failure, future testing on that
+ /// property stops. Additionally, if tests are discarded, there may be
+ /// fewer than `tests` passed.
+ pub fn tests(mut self, tests: u64) -> QuickCheck {
+ self.tests = tests;
+ self
+ }
+
+ /// Set the maximum number of tests to run.
+ ///
+ /// The number of invocations of a property will never exceed this number.
+ /// This is necessary to cap the number of tests because QuickCheck
+ /// properties can discard tests.
+ pub fn max_tests(mut self, max_tests: u64) -> QuickCheck {
+ self.max_tests = max_tests;
+ self
+ }
+
+ /// Set the minimum number of tests that needs to pass.
+ ///
+ /// This actually refers to the minimum number of *valid* *passed* tests
+ /// that needs to pass for the property to be considered successful.
+ pub fn min_tests_passed(mut self, min_tests_passed: u64) -> QuickCheck {
+ self.min_tests_passed = min_tests_passed;
+ self
+ }
+
+ /// Tests a property and returns the result.
+ ///
+ /// The result returned is either the number of tests passed or a witness
+ /// of failure.
+ ///
+ /// (If you're using Rust's unit testing infrastructure, then you'll
+ /// want to use the `quickcheck` method, which will `panic!` on failure.)
+ pub fn quicktest<A>(&mut self, f: A) -> Result<u64, TestResult>
+ where
+ A: Testable,
+ {
+ let mut n_tests_passed = 0;
+ for _ in 0..self.max_tests {
+ if n_tests_passed >= self.tests {
+ break;
+ }
+ match f.result(&mut self.gen) {
+ TestResult { status: Pass, .. } => n_tests_passed += 1,
+ TestResult { status: Discard, .. } => continue,
+ r @ TestResult { status: Fail, .. } => return Err(r),
+ }
+ }
+ Ok(n_tests_passed)
+ }
+
+ /// Tests a property and calls `panic!` on failure.
+ ///
+ /// The `panic!` message will include a (hopefully) minimal witness of
+ /// failure.
+ ///
+ /// It is appropriate to use this method with Rust's unit testing
+ /// infrastructure.
+ ///
+ /// Note that if the environment variable `RUST_LOG` is set to enable
+ /// `info` level log messages for the `quickcheck` crate, then this will
+ /// include output on how many QuickCheck tests were passed.
+ ///
+ /// # Example
+ ///
+ /// ```rust
+ /// use quickcheck::QuickCheck;
+ ///
+ /// fn prop_reverse_reverse() {
+ /// fn revrev(xs: Vec<usize>) -> bool {
+ /// let rev: Vec<_> = xs.clone().into_iter().rev().collect();
+ /// let revrev: Vec<_> = rev.into_iter().rev().collect();
+ /// xs == revrev
+ /// }
+ /// QuickCheck::new().quickcheck(revrev as fn(Vec<usize>) -> bool);
+ /// }
+ /// ```
+ pub fn quickcheck<A>(&mut self, f: A)
+ where
+ A: Testable,
+ {
+ // Ignore log init failures, implying it has already been done.
+ let _ = crate::env_logger_init();
+
+ let n_tests_passed = match self.quicktest(f) {
+ Ok(n_tests_passed) => n_tests_passed,
+ Err(result) => panic!(result.failed_msg()),
+ };
+
+ if n_tests_passed >= self.min_tests_passed {
+ info!("(Passed {} QuickCheck tests.)", n_tests_passed)
+ } else {
+ panic!(
+ "(Unable to generate enough tests, {} not discarded.)",
+ n_tests_passed
+ )
+ }
+ }
+}
+
+/// Convenience function for running QuickCheck.
+///
+/// This is an alias for `QuickCheck::new().quickcheck(f)`.
+pub fn quickcheck<A: Testable>(f: A) {
+ QuickCheck::new().quickcheck(f)
+}
+
+/// Describes the status of a single instance of a test.
+///
+/// All testable things must be capable of producing a `TestResult`.
+#[derive(Clone, Debug)]
+pub struct TestResult {
+ status: Status,
+ arguments: Vec<String>,
+ err: Option<String>,
+}
+
+/// Whether a test has passed, failed or been discarded.
+#[derive(Clone, Debug)]
+enum Status {
+ Pass,
+ Fail,
+ Discard,
+}
+
+impl TestResult {
+ /// Produces a test result that indicates the current test has passed.
+ pub fn passed() -> TestResult {
+ TestResult::from_bool(true)
+ }
+
+ /// Produces a test result that indicates the current test has failed.
+ pub fn failed() -> TestResult {
+ TestResult::from_bool(false)
+ }
+
+ /// Produces a test result that indicates failure from a runtime error.
+ pub fn error<S: Into<String>>(msg: S) -> TestResult {
+ let mut r = TestResult::from_bool(false);
+ r.err = Some(msg.into());
+ r
+ }
+
+ /// Produces a test result that instructs `quickcheck` to ignore it.
+ /// This is useful for restricting the domain of your properties.
+ /// When a test is discarded, `quickcheck` will replace it with a
+ /// fresh one (up to a certain limit).
+ pub fn discard() -> TestResult {
+ TestResult { status: Discard, arguments: vec![], err: None }
+ }
+
+ /// Converts a `bool` to a `TestResult`. A `true` value indicates that
+ /// the test has passed and a `false` value indicates that the test
+ /// has failed.
+ pub fn from_bool(b: bool) -> TestResult {
+ TestResult {
+ status: if b { Pass } else { Fail },
+ arguments: vec![],
+ err: None,
+ }
+ }
+
+ /// Tests if a "procedure" fails when executed. The test passes only if
+ /// `f` generates a task failure during its execution.
+ pub fn must_fail<T, F>(f: F) -> TestResult
+ where
+ F: FnOnce() -> T,
+ F: 'static,
+ T: 'static,
+ {
+ let f = panic::AssertUnwindSafe(f);
+ TestResult::from_bool(panic::catch_unwind(f).is_err())
+ }
+
+ /// Returns `true` if and only if this test result describes a failing
+ /// test.
+ pub fn is_failure(&self) -> bool {
+ match self.status {
+ Fail => true,
+ Pass | Discard => false,
+ }
+ }
+
+ /// Returns `true` if and only if this test result describes a failing
+ /// test as a result of a run time error.
+ pub fn is_error(&self) -> bool {
+ self.is_failure() && self.err.is_some()
+ }
+
+ fn failed_msg(&self) -> String {
+ match self.err {
+ None => format!(
+ "[quickcheck] TEST FAILED. Arguments: ({})",
+ self.arguments.join(", ")
+ ),
+ Some(ref err) => format!(
+ "[quickcheck] TEST FAILED (runtime error). \
+ Arguments: ({})\nError: {}",
+ self.arguments.join(", "),
+ err
+ ),
+ }
+ }
+}
+
+/// `Testable` describes types (e.g., a function) whose values can be
+/// tested.
+///
+/// Anything that can be tested must be capable of producing a `TestResult`
+/// given a random number generator. This is trivial for types like `bool`,
+/// which are just converted to either a passing or failing test result.
+///
+/// For functions, an implementation must generate random arguments
+/// and potentially shrink those arguments if they produce a failure.
+///
+/// It's unlikely that you'll have to implement this trait yourself.
+pub trait Testable: 'static {
+ fn result(&self, _: &mut Gen) -> TestResult;
+}
+
+impl Testable for bool {
+ fn result(&self, _: &mut Gen) -> TestResult {
+ TestResult::from_bool(*self)
+ }
+}
+
+impl Testable for () {
+ fn result(&self, _: &mut Gen) -> TestResult {
+ TestResult::passed()
+ }
+}
+
+impl Testable for TestResult {
+ fn result(&self, _: &mut Gen) -> TestResult {
+ self.clone()
+ }
+}
+
+impl<A, E> Testable for Result<A, E>
+where
+ A: Testable,
+ E: Debug + 'static,
+{
+ fn result(&self, g: &mut Gen) -> TestResult {
+ match *self {
+ Ok(ref r) => r.result(g),
+ Err(ref err) => TestResult::error(format!("{:?}", err)),
+ }
+ }
+}
+
+/// Return a vector of the debug formatting of each item in `args`
+fn debug_reprs(args: &[&dyn Debug]) -> Vec<String> {
+ args.iter().map(|x| format!("{:?}", x)).collect()
+}
+
+macro_rules! testable_fn {
+ ($($name: ident),*) => {
+
+impl<T: Testable,
+ $($name: Arbitrary + Debug),*> Testable for fn($($name),*) -> T {
+ #[allow(non_snake_case)]
+ fn result(&self, g: &mut Gen) -> TestResult {
+ fn shrink_failure<T: Testable, $($name: Arbitrary + Debug),*>(
+ g: &mut Gen,
+ self_: fn($($name),*) -> T,
+ a: ($($name,)*),
+ ) -> Option<TestResult> {
+ for t in a.shrink() {
+ let ($($name,)*) = t.clone();
+ let mut r_new = safe(move || {self_($($name),*)}).result(g);
+ if r_new.is_failure() {
+ {
+ let ($(ref $name,)*) : ($($name,)*) = t;
+ r_new.arguments = debug_reprs(&[$($name),*]);
+ }
+
+ // The shrunk value *does* witness a failure, so keep
+ // trying to shrink it.
+ let shrunk = shrink_failure(g, self_, t);
+
+ // If we couldn't witness a failure on any shrunk value,
+ // then return the failure we already have.
+ return Some(shrunk.unwrap_or(r_new))
+ }
+ }
+ None
+ }
+
+ let self_ = *self;
+ let a: ($($name,)*) = Arbitrary::arbitrary(g);
+ let ( $($name,)* ) = a.clone();
+ let mut r = safe(move || {self_($($name),*)}).result(g);
+
+ {
+ let ( $(ref $name,)* ) = a;
+ r.arguments = debug_reprs(&[$($name),*]);
+ }
+ match r.status {
+ Pass|Discard => r,
+ Fail => {
+ shrink_failure(g, self_, a).unwrap_or(r)
+ }
+ }
+ }
+}}}
+
+testable_fn!();
+testable_fn!(A);
+testable_fn!(A, B);
+testable_fn!(A, B, C);
+testable_fn!(A, B, C, D);
+testable_fn!(A, B, C, D, E);
+testable_fn!(A, B, C, D, E, F);
+testable_fn!(A, B, C, D, E, F, G);
+testable_fn!(A, B, C, D, E, F, G, H);
+
+fn safe<T, F>(fun: F) -> Result<T, String>
+where
+ F: FnOnce() -> T,
+ F: 'static,
+ T: 'static,
+{
+ panic::catch_unwind(panic::AssertUnwindSafe(fun)).map_err(|any_err| {
+ // Extract common types of panic payload:
+ // panic and assert produce &str or String
+ if let Some(&s) = any_err.downcast_ref::<&str>() {
+ s.to_owned()
+ } else if let Some(s) = any_err.downcast_ref::<String>() {
+ s.to_owned()
+ } else {
+ "UNABLE TO SHOW RESULT OF PANIC.".to_owned()
+ }
+ })
+}
+
+/// Convenient aliases.
+trait AShow: Arbitrary + Debug {}
+impl<A: Arbitrary + Debug> AShow for A {}
+
+#[cfg(test)]
+mod test {
+ use crate::{Gen, QuickCheck};
+
+ #[test]
+ fn shrinking_regression_issue_126() {
+ fn thetest(vals: Vec<bool>) -> bool {
+ vals.iter().filter(|&v| *v).count() < 2
+ }
+ let failing_case = QuickCheck::new()
+ .quicktest(thetest as fn(vals: Vec<bool>) -> bool)
+ .unwrap_err();
+ let expected_argument = format!("{:?}", [true, true]);
+ assert_eq!(failing_case.arguments, vec![expected_argument]);
+ }
+
+ #[test]
+ fn size_for_small_types_issue_143() {
+ fn t(_: i8) -> bool {
+ true
+ }
+ QuickCheck::new().gen(Gen::new(129)).quickcheck(t as fn(i8) -> bool);
+ }
+
+ #[test]
+ fn regression_signed_shrinker_panic() {
+ fn foo_can_shrink(v: i8) -> bool {
+ let _ = crate::Arbitrary::shrink(&v).take(100).count();
+ true
+ }
+ crate::quickcheck(foo_can_shrink as fn(i8) -> bool);
+ }
+}
diff --git a/src/tests.rs b/src/tests.rs
new file mode 100644
index 0000000..465ef15
--- /dev/null
+++ b/src/tests.rs
@@ -0,0 +1,288 @@
+use std::cmp::Ord;
+use std::collections::hash_map::DefaultHasher;
+use std::collections::{HashMap, HashSet};
+use std::ffi::CString;
+use std::hash::BuildHasherDefault;
+use std::path::PathBuf;
+
+use super::{quickcheck, Gen, QuickCheck, TestResult};
+
+#[test]
+fn prop_oob() {
+ fn prop() -> bool {
+ let zero: Vec<bool> = vec![];
+ zero[0]
+ }
+ match QuickCheck::new().quicktest(prop as fn() -> bool) {
+ Ok(n) => panic!(
+ "prop_oob should fail with a runtime error \
+ but instead it passed {} tests.",
+ n
+ ),
+ _ => return,
+ }
+}
+
+#[test]
+fn prop_reverse_reverse() {
+ fn prop(xs: Vec<usize>) -> bool {
+ let rev: Vec<_> = xs.clone().into_iter().rev().collect();
+ let revrev: Vec<_> = rev.into_iter().rev().collect();
+ xs == revrev
+ }
+ quickcheck(prop as fn(Vec<usize>) -> bool);
+}
+
+quickcheck! {
+ fn prop_reverse_reverse_macro(xs: Vec<usize>) -> bool {
+ let rev: Vec<_> = xs.clone().into_iter().rev().collect();
+ let revrev: Vec<_> = rev.into_iter().rev().collect();
+ xs == revrev
+ }
+
+ #[should_panic]
+ fn prop_macro_panic(_x: u32) -> bool {
+ assert!(false);
+ false
+ }
+}
+
+#[test]
+fn reverse_single() {
+ fn prop(xs: Vec<usize>) -> TestResult {
+ if xs.len() != 1 {
+ TestResult::discard()
+ } else {
+ TestResult::from_bool(
+ xs == xs.clone().into_iter().rev().collect::<Vec<_>>(),
+ )
+ }
+ }
+ quickcheck(prop as fn(Vec<usize>) -> TestResult);
+}
+
+#[test]
+fn reverse_app() {
+ fn prop(xs: Vec<usize>, ys: Vec<usize>) -> bool {
+ let mut app = xs.clone();
+ app.extend(ys.iter().cloned());
+ let app_rev: Vec<usize> = app.into_iter().rev().collect();
+
+ let rxs: Vec<usize> = xs.into_iter().rev().collect();
+ let mut rev_app = ys.into_iter().rev().collect::<Vec<usize>>();
+ rev_app.extend(rxs.into_iter());
+
+ app_rev == rev_app
+ }
+ quickcheck(prop as fn(Vec<usize>, Vec<usize>) -> bool);
+}
+
+#[test]
+fn max() {
+ fn prop(x: isize, y: isize) -> TestResult {
+ if x > y {
+ TestResult::discard()
+ } else {
+ TestResult::from_bool(::std::cmp::max(x, y) == y)
+ }
+ }
+ quickcheck(prop as fn(isize, isize) -> TestResult);
+}
+
+#[test]
+fn sort() {
+ fn prop(mut xs: Vec<isize>) -> bool {
+ xs.sort_by(|x, y| x.cmp(y));
+ for i in xs.windows(2) {
+ if i[0] > i[1] {
+ return false;
+ }
+ }
+ true
+ }
+ quickcheck(prop as fn(Vec<isize>) -> bool);
+}
+
+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()
+}
+
+fn is_prime(n: usize) -> bool {
+ n != 0 && n != 1 && (2..).take_while(|i| i * i <= n).all(|i| n % i != 0)
+}
+
+#[test]
+#[should_panic]
+fn sieve_not_prime() {
+ fn prop_all_prime(n: u8) -> bool {
+ sieve(n as usize).into_iter().all(is_prime)
+ }
+ quickcheck(prop_all_prime as fn(u8) -> bool);
+}
+
+#[test]
+#[should_panic]
+fn sieve_not_all_primes() {
+ fn prop_prime_iff_in_the_sieve(n: u8) -> bool {
+ let n = n as usize;
+ sieve(n) == (0..(n + 1)).filter(|&i| is_prime(i)).collect::<Vec<_>>()
+ }
+ quickcheck(prop_prime_iff_in_the_sieve as fn(u8) -> bool);
+}
+
+#[test]
+fn testable_result() {
+ fn result() -> Result<bool, String> {
+ Ok(true)
+ }
+ quickcheck(result as fn() -> Result<bool, String>);
+}
+
+#[test]
+#[should_panic]
+fn testable_result_err() {
+ quickcheck(Err::<bool, i32> as fn(i32) -> Result<bool, i32>);
+}
+
+#[test]
+fn testable_unit() {
+ fn do_nothing() {}
+ quickcheck(do_nothing as fn());
+}
+
+#[test]
+fn testable_unit_panic() {
+ fn panic() {
+ panic!()
+ }
+ assert!(QuickCheck::new().quicktest(panic as fn()).is_err());
+}
+
+#[test]
+fn regression_issue_83() {
+ fn prop(_: u8) -> bool {
+ true
+ }
+ QuickCheck::new().gen(Gen::new(1024)).quickcheck(prop as fn(u8) -> bool)
+}
+
+#[test]
+fn regression_issue_83_signed() {
+ fn prop(_: i8) -> bool {
+ true
+ }
+ QuickCheck::new().gen(Gen::new(1024)).quickcheck(prop as fn(i8) -> bool)
+}
+
+// Test that we can show the message after panic
+#[test]
+#[should_panic(expected = "foo")]
+fn panic_msg_1() {
+ fn prop() -> bool {
+ panic!("foo");
+ }
+ quickcheck(prop as fn() -> bool);
+}
+
+#[test]
+#[should_panic(expected = "foo")]
+fn panic_msg_2() {
+ fn prop() -> bool {
+ assert!("foo" == "bar");
+ true
+ }
+ quickcheck(prop as fn() -> bool);
+}
+
+#[test]
+#[should_panic(expected = "foo")]
+fn panic_msg_3() {
+ fn prop() -> bool {
+ assert_eq!("foo", "bar");
+ true
+ }
+ quickcheck(prop as fn() -> bool);
+}
+
+#[test]
+#[should_panic]
+fn regression_issue_107_hang() {
+ fn prop(a: Vec<u8>) -> bool {
+ a.contains(&1)
+ }
+ quickcheck(prop as fn(_) -> bool);
+}
+
+#[test]
+#[should_panic(
+ expected = "(Unable to generate enough tests, 0 not discarded.)"
+)]
+fn all_tests_discarded_min_tests_passed_set() {
+ fn prop_discarded(_: u8) -> TestResult {
+ TestResult::discard()
+ }
+
+ QuickCheck::new()
+ .tests(16)
+ .min_tests_passed(8)
+ .quickcheck(prop_discarded as fn(u8) -> TestResult)
+}
+
+#[test]
+fn all_tests_discarded_min_tests_passed_missing() {
+ fn prop_discarded(_: u8) -> TestResult {
+ TestResult::discard()
+ }
+
+ QuickCheck::new().quickcheck(prop_discarded as fn(u8) -> TestResult)
+}
+
+quickcheck! {
+ /// The following is a very simplistic test, which only verifies
+ /// that our PathBuf::arbitrary does not panic. Still, that's
+ /// something! :)
+ fn pathbuf(_p: PathBuf) -> bool {
+ true
+ }
+
+ fn basic_hashset(_set: HashSet<u8>) -> bool {
+ true
+ }
+
+ fn basic_hashmap(_map: HashMap<u8, u8>) -> bool {
+ true
+ }
+
+ fn substitute_hashset(
+ _set: HashSet<u8, BuildHasherDefault<DefaultHasher>>
+ ) -> bool {
+ true
+ }
+
+ fn substitute_hashmap(
+ _map: HashMap<u8, u8, BuildHasherDefault<DefaultHasher>>
+ ) -> bool {
+ true
+ }
+
+ fn cstring(_p: CString) -> bool {
+ true
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-27 17:03:44 +0000