Crate truth_values

Tiny, zero-dependency, zero-allocation*, no_std library for generating all possible combinations of n bools. Useful for testing boolean functions, verifying logical equivalence, and generating truth tables. *Optional alloc feature for Vec related functions.

Example - each() and each_const()

Consider implementing an interpreter or optimizer, and now you want to assert logical equivalence between expressions, e.g. asserting De Morgan’s laws:

• not (A or B) = (not A) and (not B)
• not (A and B) = (not A) or (not B)

Using const generic variant, i.e. where N is const:

each_const(|[a, b]| {
    assert_eq!(!(a || b), !a && !b);
    assert_eq!(!(a && b), !a || !b);
});
// The closure is called for each combination of 2 `bool`s, i.e.:
// [false, false]
// [true,  false]
// [false, true]
// [true,  true]

Using non-const generic variant, i.e. where n can be dynamic:

each(2, |bools| match bools {
    &[a, b] => {
        assert_eq!(!(a || b), !a && !b);
        assert_eq!(!(a && b), !a || !b);
    }
    _ => unreachable!(),
});
// The closure is called for each combination of 2 `bool`s, i.e.:
// &[false, false]
// &[true,  false]
// &[false, true]
// &[true,  true]

Example - gen() and gen_const()

Alternatively, use gen() functions to obtain an Iterator for generating all combinations. This could be used to e.g. map each combination into an Expr for an AST, to easily generate all Expr combinations to verify their evaluation.

Using const generic variant, i.e. where N is const:

#[derive(PartialEq, Debug)]
enum Expr {
    Bool(bool),
    And(Box<Self>, Box<Self>),
    // ...
}

impl Expr {
    fn and(lhs: Self, rhs: Self) -> Self {
        Self::And(Box::new(lhs), Box::new(rhs))
    }
}

let exprs = truth_values::gen_const()
    .map(|[a, b]| {
        Expr::and(Expr::Bool(a), Expr::Bool(b))
    })
    .collect::<Vec<_>>();

assert_eq!(
    exprs,
    [
        Expr::and(Expr::Bool(false), Expr::Bool(false)),
        Expr::and(Expr::Bool(true),  Expr::Bool(false)),
        Expr::and(Expr::Bool(false), Expr::Bool(true)),
        Expr::and(Expr::Bool(true),  Expr::Bool(true)),
    ]
);

Using non-const generic variant, i.e. where n can be dynamic:

let exprs = truth_values::gen_slice(2, |bools| {
    match bools {
        &[a, b] => {
            Expr::and(Expr::Bool(a), Expr::Bool(b))
        }
        _ => unreachable!(),
    }
})
.collect::<Vec<_>>();

assert_eq!(
    exprs,
    [
        Expr::and(Expr::Bool(false), Expr::Bool(false)),
        Expr::and(Expr::Bool(true),  Expr::Bool(false)),
        Expr::and(Expr::Bool(false), Expr::Bool(true)),
        Expr::and(Expr::Bool(true),  Expr::Bool(true)),
    ]
);

Combinations of 1, 2, 3, 4 bools

gen_const::<1>()	gen_const::<2>()	gen_const::<3>()	gen_const::<4>()
[false] [true]	[false, false] [true, false] [false, true] [true, true]	[false, false, false] [true, false, false] [false, true, false] [true, true, false] [false, false, true] [true, false, true] [false, true, true] [true, true, true]	[false, false, false, false] [true, false, false, false] [false, true, false, false] [true, true, false, false] [false, false, true, false] [true, false, true, false] [false, true, true, false] [true, true, true, false] [false, false, false, true] [true, false, false, true] [false, true, false, true] [true, true, false, true] [false, false, true, true] [true, false, true, true] [false, true, true, true] [true, true, true, true]

Implementation

The gen() functions return an Iterator, which additionally specializes size_hint(), count(), nth(), last().

The Iterator also implements:

• DoubleEndedIterator implementing next_back() and nth_back()
• ExactSizeIterator implementing len()
• FusedIterator

Warning

The amount of combinations is exponential! The number of combinations for N boolean variables is 2N. In short, 10 variables produce 1024 combinations, but 20 variables produce over 1 million combinations.

Just alone exhausting the generator for 30 variables, i.e. over 1 billion combinations, takes a handful of seconds on my machine.

Ideally, if used to test expressions, then there will likely only be a handful of variables. However, if user input is accepted, then it might be worth guarding and limiting the number of variables.

So even though up to MAX (63) variables for 64-bit platforms is supported, it is probably undesirable to even attempt to process that many variables.

Structs

Bools

An Iterator that produces exactly n bools.

Constants

MAX

Maximum number of variables supported by gen() functions.

Functions

count

Returns Some with the number of combinations that n variables produces.

each

Shorthand for gen_slice(n, f).for_each(|_| ()).

each_const

Shorthand for gen_const().for_each(f).

each_vec_slice

Shorthand for gen_vec_slice(n, f).for_each(|_| ()).

each_with_buffer

Shorthand for gen_with_buffer(n, buffer, f).for_each(|_| ()).

gen

Returns an Iterator producing all possible combinations of n bools, in the form of individual Bools iterators.

gen_const

Returns an Iterator producing all possible combinations of [bool; N].

gen_slice

Returns an Iterator producing T for each possible combinations of n bools.

gen_vec

Returns an Iterator producing Vec<bool> for each possible combinations of n bools.

gen_vec_slice

Returns an Iterator producing T for each possible combinations of n bools.

gen_with_buffer

Returns an Iterator producing T for each possible combinations of n bools.

is_supported

Returns true if n variables is supported by gen() functions, i.e. n <= MAX.