Crate reltester

source ·
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

  1. 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 and proptest. Calling the checkers on static, non-randomized values is possible but is less effective in catching bugs.

  2. Based on the traits that your type implements, call the appropriate checker(s):

    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 of Rhs == 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 Rust std uses to describe a > b iff b < a. Thus the exact mathematical definition of PartialOrd 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 like PartialOrd, the mathematical definition of Ord 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.

  1. https://github.com/rust-lang/rust/issues/41964 ↩

  2. https://github.com/bevyengine/bevy/pull/7469 ↩

  3. https://github.com/bluejekyll/trust-dns/issues/1638 ↩

  4. https://github.com/sparsemat/sprs/issues/261 ↩

  5. Trichotomy is a corollary that follows from the definitions of >, ==, and < based on Ordering. ↩

Modules

  • error
    Crate error types.
  • invariants
    Granular checkers for specific trait invariants. Only use these if you implement PartialEq and PartialOrd with a non-Self type parameter and you can’t satisfy the type bounds of the main helper functions.

Functions