Expand description
Relation tester is a small testing utility for automatically
checking the correctness of [Partial]Eq
, [Partial]Ord
, Hash
, and
[DoubleEnded|Fused]Iterator
trait implementations. It’s most useful when
used in conjuction with
quickcheck
or some other
property-based testing framework.
Rationale
Imagine a scenario where you have a type Foo
with a custom implementation
of either PartialEq
, Eq
, PartialOrd
, or Ord
. By “custom” we mean
hand-written as opposed to derived. The Rust compiler alone cannot verify
the correctness of these implementations and thus it is up to you, the
programmer, to uphold certain invariants about the specific binary
relation that you’re
implementing. For example, if you implement PartialEq
for Foo
, you must
guarantee that foo1 == foo2
implies foo2 == foo1
(symmetry).
Other traits such as Hash
and Iterator
mandate their own invariants as
well – some of which are very intuitive, and
others
which are not. It’s especially common for less-than-perfect implementations
of the std::iter
family of traits to introduce off-by-one
bugs1 2 3 4 among others.
The idea is, instead of keeping these invariants in your head whenever you go about manually implementing one of these traits in your codebase, you can add a Reltester check to your test suite and have a higher degree of confidence that your implementation is correct.
How to use
-
Write some tests that generate random values of the type you wish to test. You can do this by hand or using crates such as
quickcheck
andproptest
. Calling the checkers on static, non-randomized values is possible but is less effective in catching bugs. -
Based on the traits that your type implements, call the appropriate checker(s):
reltester::eq
forEq
;reltester::ord
forOrd
;reltester::partial_eq
forPartialEq
;reltester::partial_ord
forPartialOrd
;reltester::hash
forHash
;reltester::iterator
forIterator
;reltester::fused_iterator
forFusedIterator
;reltester::double_ended_iterator
forDoubleEndedIterator
;
Some of these functions take multiple (two or three) values of the same type. This is because it takes up to three values to test some invariants.
The reltester::invariants
module is available for more
granular checks if you can’t satisfy the type bounds of the main functions.
Multi-type relations: Foo: PartialEq<Bar>
and Foo: PartialOrd<Bar>
In some cases your PartialEq
and PartialOrd
implementations
may use a non-Self
type parameter. (Note: Eq
and Ord
don’t accept
type parameters and this use case doesn’t apply to them.) Reltester
supports this use case and exposes granular invariant checking functions in
the invariants
module with more lax type constraints.
Examples
f32
(PartialEq
, PartialOrd
)
use reltester;
use quickcheck_macros::quickcheck;
#[quickcheck]
fn test_f32(a: f32, b: f32, c: f32) -> bool {
// Let's check if `f32` implements `PartialEq` and `PartialOrd` correctly
// (spoiler: it does).
reltester::partial_eq(&a, &b, &c).is_ok()
&& reltester::partial_ord(&a, &b, &c).is_ok()
}
u32
(Hash
)
use reltester;
use quickcheck_macros::quickcheck;
#[quickcheck]
fn test_u32(a: u32, b: u32) -> bool {
// Unlike `f32`, `u32` implements both `Eq` and `Hash`, which allows us to
// test `Hash` invariants.
reltester::hash(&a, &b).is_ok()
}
Vec<u32>
(DoubleEndedIterator
, FusedIterator
, Iterator
)
use reltester;
use quickcheck_macros::quickcheck;
#[quickcheck]
fn test_vec_u32(nums: Vec<u32>) -> bool {
// `Iterator` is implied and checked by both `DoubleEndedIterator` and
// `FusedIterator`.
reltester::double_ended_iterator(nums.iter()).is_ok()
&& reltester::fused_iterator(nums.iter()).is_ok()
}
TL;DR invariants of the comparison traits
Chances are you don’t need to concern yourself with the mathematical definitions of
comparison traits; as long as your implementations are sensible and your
reltester
tests pass, you can move on and assume your implementations are
correct. The required invariants are listed here only for the sake of
completeness.
PartialEq
requires symmetry and transitivity of==
whenever applicable (partial equivalence relation in the case ofRhs == Self
).Eq
requires symmetry, transitivity, and reflexivity of==
(equivalence relation).PartialOrd
requires symmetry of==
, transitivity of>
,==
, and<
; and duality of>
and<
. Note that duality is not common mathematical terminology, it’s just what the Ruststd
uses to describea > b iff b < a
. Thus the exact mathematical definition ofPartialOrd
seems open to debate, though it’s generally understood to mean strict partial order.Ord
requires symmetry and reflexivity of==
; transitivity of>
,==
, and<
; and duality of>
and<
.==
; transitivity and duality of>
and<
; and must be trichotomous5. Just likePartialOrd
, the mathematical definition ofOrd
is a bit open to interpretation, though it’s generally understood to mean total order.
In addition to the above, trait method default implementation overrides (for e.g.
PartialOrd::lt
or Ord::max
) must have the same behavior as the
default implementations. reltester
always checks these for you.
Modules
- Crate error types.
- Granular checkers for specific trait invariants. Only use these if you implement
PartialEq
andPartialOrd
with a non-Self
type parameter and you can’t satisfy the type bounds of the main helper functions.
Functions
- Checks the correctness of the
DoubleEndedIterator
trait (andIterator
by extension) for some valueiter
. - Checks the correctness of the
Iterator
trait for some valueiter
. - Checks the correctness of the
PartialEq
trait for some values. - Checks the correctness of the
PartialOrd
trait (andPartialEq
by extension) for some values.