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: Expr, rhs: Expr) -> Expr {
        Expr::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.