Match

Why an algebra

A predicate is easy: a function returning bool. The reason match exists is everything that comes after. When predicates are types that know how to negate themselves and when one entails another, the compiler can do the reasoning: fold a contradiction to never, drop a redundant term, rewrite an expression into the cheaper equivalent form, or flatten it into the normal form a dispatch table needs.

The whole library is 13 small headers, and its only consumer in the repo is msg — where every callback’s matcher is simplified, indexed, and printed in log messages when a message doesn’t match.

Writing a matcher

template <int N> struct is_n_t {
    using is_matcher = void;                        // opt in

    constexpr auto operator()(int i) const -> bool { return i == N; }

    constexpr static auto describe() {              // compile-time text
        return stdx::ct_format<"x == {}">(stdx::ct<N>());
    }
    constexpr auto describe_match(int i) const {    // what happened this time
        return stdx::ct_format<"{} == {}">(i, stdx::ct<N>());
    }
};
template <int N> constexpr auto is_n = is_n_t<N>{};

No base class, no registration. match::matcher<T> checks only for the is_matcher type; match::matcher_for<T, Event> additionally checks that the three members work for that event type.

For one-off conditions there’s match::predicate:

constexpr auto even = match::predicate<"even">([](int i) { return i % 2 == 0; });
even.describe();   // "even"

constexpr auto anon = match::predicate([](int i) { return i > 0; });
anon.describe();   // "<predicate>"

The lambda must be captureless — the predicate is held as a constexpr static member. A capturing one fails with no matching constructor for initialization of '(lambda …)'.

Composing

Simplification

Every one of these is verified, and all of them happen in the type system before main runs:

That last one is a choice, not a rule. Each matcher has a cost: 1 for a leaf, plus 1 per operator. The library builds both forms and keeps the cheaper:

cost(not (X or Y))        == 4      ← chosen
cost(not X and not Y)     == 5

Simplification recurses: X and (X and always) collapses to X, and a contradiction buried in a longer chain still folds the whole expression to never.

Simplifier bench

Build an expression from two operands and an operator. The bench applies the same rules the library does — implication-driven absorption, complementation, and the cost comparison for de Morgan — and shows what the type would collapse to, plus which values match before and after.

Teaching the library

Out of the box the library knows one implication: a matcher implies itself. Two tag_invoke overloads teach it the rest.

template <int N> struct below_t {
    // … the four members …
  private:
    // how to invert
    friend constexpr auto tag_invoke(match::negate_t, below_t const &)
        -> at_least_t<N> { return {}; }

    // x < N implies x < M when N <= M
    template <int M>
    friend constexpr auto tag_invoke(match::implies_t, below_t, below_t<M>)
        -> bool { return N <= M; }
};

With only those, all of this follows (verified):

Implications also chain through the operators: (X and Y) => X, and X => (X or Y), both verified. If your matcher has no natural opposite, skip negate: not then wraps it in not_t, which still works.

Ordering

Because implication is defined, matchers form a partial order: one matcher is “less” than another when it matches fewer things. a <=> b gives a std::partial_ordering (verified):

never and always are the bottom and top of that order. There is no operator== between matchers — m1{} == m1{} is invalid operands to binary expression. Compare with <=>, or compare types.

Sum of products

Disjunctive normal form is an or of ands with negations pushed down to the leaves. It matters because each top-level or term can be indexed independently, which is exactly what msg’s dispatch needs.

X and (Y or Z)   ->  (X and Y) or (X and Z)
(X or Y) and Z   ->  (X and Z) or (Y and Z)
not (X and Y)    ->  not X or not Y
not (X or Y)     ->  not X and not Y

and and or on their own do not produce this form; the conversion is a separate, explicit call. Distribution multiplies terms — (A or B) and (X or Y) becomes four — so convert deliberately, not by habit.

Rest of cib

If you’re writing field matchers for a protocol, start from include/msg/field_matchers.hpp: it is a complete worked example of relational matchers with negation, implication and index hooks.

Use cases

Conditions that explain themselves

Any place you’d write a bare lambda guard but want the log to say why it didn’t fire, a matcher pays for itself: describe_match gives the reason with the actual values, formatted only if logged.

Range and threshold checks

Give your relational matchers negate and implies, and impossible ranges become never at compile time instead of dead runtime branches.

Sets of accepted values

match::any(eq<1>, eq<2>, eq<3>) — which is precisely how msg’s in<F, Vs...> is built.

Feature flags in a matcher expression

match::predicate<"feature">([] { return flag; }) composes with everything else and prints its name. cib’s runtime conditions on msg callbacks work exactly this way.

Testing matchers

// decltype(expression) is unqualified; decltype(constexpr variable) is const
template <typename A, typename B>
constexpr bool same_type =
    std::is_same_v<std::remove_const_t<A>, std::remove_const_t<B>>;

static_assert(same_type<decltype(below<3> and below<5>), below_t<3>>);
static_assert((below<3> and below<5>)(2));
static_assert(e.describe().str == "(x == 1) and (x == 2)"_ctst);

Pitfalls