match(it): A lightweight header-only pattern-matching library for C++17 with macro-free APIs.

Features

• Easy to get started.

• 

• Single header library.

• Macro-free APIs.
• No heap memory allocation.
• Portability: continuously tested under Ubuntu, MacOS and Windows using GCC/Clang/MSVC.
• No external dependencies.
• Reliability : strict compiler checking option + sanitizers + valgrind.
• Composable patterns.
• Extensible, users can define their own patterns, either via composing existent ones, or create brand new ones.
• Support destructing tuple-like and range-like containers.
• Partial support for constant expression.

Installation

Option 1. Download matchit.h

Simply download the header file matchit.h and put it in your include directory for dependencies.

That's it.

You can download via this bash command

wget https://raw.githubusercontent.com/BowenFu/matchit.cpp/main/include/matchit.h

Option 2. Manage with cmake FetchContent

Include the code snippet in your CMakeLists.txt:

include(FetchContent)

FetchContent_Declare(
    matchit
    GIT_REPOSITORY https://github.com/BowenFu/matchit.cpp.git
    GIT_TAG main)

FetchContent_GetProperties(matchit)
if(NOT matchit_POPULATED)
    FetchContent_Populate(matchit)
    add_subdirectory(${matchit_SOURCE_DIR} ${matchit_BINARY_DIR}
                    EXCLUDE_FROM_ALL)
endif()

message(STATUS "Matchit header are present at ${matchit_SOURCE_DIR}")

And add ${matchit_SOURCE_DIR}/include to your include path.

Option 3. Manage with cmake find_package

Clone the repo via

git clone --depth 1 https://github.com/BowenFu/matchit.cpp

Install the library via

cd matchit.cpp
cmake -B ./build
cd build
make install

Then use find_package in your CMakeLists.txt.

Syntax Design

For syntax design details please refer to REFERENCE.

From Rust to match(it)

The document From Rust to match(it) gives equivalent samples for corresponding Rust samples.

There you may have a picture of what coding with match(it) would be like.

From Pattern Matching Proposal to match(it)

The document From Pattern Matching Proposal to match(it) gives equivalent samples for corresponding samples in the Match Pattern Matching Proposal.

There you will see the pros and cons of the library over the proposal.

Quick start.

Let's start a journey on the library!

(For complete samples, please refer to samples directory.)

Hello World!

The following sample shows to how to implement factorial using match(it) library.

#include "matchit.h"

constexpr int32_t factorial(int32_t n)
{
    using namespace matchit;
    assert(n >= 0);
    return match(n)(
        pattern | 0 = expr(1),
        pattern | _ = [n] { return n * factorial(n - 1); }
    );
}

The basic syntax for pattern matching is

match(VALUE)
(
    pattern | PATTERN1 = HANDLER1,
    pattern | PATTERN2 = HANDLER2,
    ...
)

This is a function call and will return some value returned by handlers. The return type is the common type for all handlers. Return type will be void if all handlers do not return values. Incompatible return types from multiple handlers is a compile error. When handlers return values, the patterns must be exhaustive. A runtime error will happen if all patterns do not get matched. It is not an error if handlers' return types are all void.

expr in the above sample is a helper function that can be used to generate a nullary function that returns a value. expr(1) is equivalent to []{return 1;}. It can be useful for short functions.

The wildcard _ will match any values. It is a common practice to always use it as the last pattern, playing the same role in our library as default case does for switch statements, to avoid case escaping.

We can match multiple values at the same time:

#include "matchit.h"

constexpr int32_t gcd(int32_t a, int32_t b)
{
    using namespace matchit;
    return match(a, b)(
        pattern | ds(_, 0) = [&] { return a >= 0 ? a : -a; },
        pattern | _        = [&] { return gcd(b, a%b); }
    );
}

static_assert(gcd(12, 6) == 6);

Note that some patterns support constexpr match, i.e. you can match them at compile time. From the above code snippets, we can see that gcd(12, 6) can be executed in compile time.

Different from matching patterns in other programming languages, variables can be used normally inside patterns in match(it), this is shown in the following sample:

#include "matchit.h"
#include <map>

template <typename Map, typename Key>
constexpr bool contains(Map const& map, Key const& key)
{
    using namespace matchit;
    return match(map.find(key))(
        pattern | map.end() = expr(false),
        pattern | _         = expr(true)
    );
}

Hello Moon!

We can use Predicate Pattern to put some restrictions on the value to be matched.

constexpr double relu(double value)
{
    return match(value)(
        pattern | (_ >= 0) = expr(value),
        pattern | _        = expr(0));
}

static_assert(relu(5) == 5);
static_assert(relu(-5) == 0);

We overload some operators for wildcard symbol _ to facilitate usage of basic predicates.

Sometimes we want to share one handler for multiple patterns, Or Pattern is the rescue:

#include "matchit.h"

constexpr bool isValid(int32_t n)
{
    using namespace matchit;
    return match(n)(
        pattern | or_(1, 3, 5) = expr(true),
        pattern | _            = expr(false)
    );
}

static_assert(isValid(5));
static_assert(!isValid(6));

And Pattern is for combining multiple Predicate patterns.

App Pattern is powerful when you want to extract some information from the subject. Its syntax is

app(PROJECTION, PATTERN)

A simple sample to check whether a num is large can be:

#include "matchit.h"

constexpr bool isLarge(double value)
{
    using namespace matchit;
    return match(value)(
        pattern | app(_ * _, _ > 1000) = expr(true),
        pattern | _                    = expr(false)
    );
}

// app with projection returning scalar types is supported by constexpr match.
static_assert(isLarge(100));

Note that _ * _ generates a function object that computes the square of the input, can be considered the short version of [](auto&& x){ return x*x;}.

Can we bind the value if we have already extract them? Sure, Identifier Pattern is for you.

Let's log the square result, with Identifier Pattern the codes would be

#include <iostream>
#include "matchit.h"

bool checkAndlogLarge(double value)
{
    using namespace matchit;
    Id<double> s;
    return match(value)(
        pattern | app(_ * _, s.at(_ > 1000)) = [&] {
                std::cout << value << "^2 = " << *s << " > 1000!" << std::endl;
                return true; },
        pattern | _ = expr(false));
}

To use Identifier Patterns, we need to define/declare the identifiers (Id<double> s) first. (Do not mark it as const.) This can be a little strange if you've use Identifier Patterns in other programming language. This is due to the language restriction. But don't be upset. This added verbosity makes it possible for us to use variables inside patterns. You may never be able to do this in other programming language.

Here * operator is used to dereference the value inside identifiers. One thing to note is that identifiers are only valid inside match scope. Do not try to dereference it outside.

Id::at is similar to the @ pattern in Rust, i.e., bind the value when the subpattern gets matched.

Also note when the same identifier is bound multiple times, the bound values must equal to each other via operator==. An sample to check if an array is symmetric:

#include "matchit.h"
constexpr bool symmetric(std::array<int32_t, 5> const& arr)
{
    using namespace matchit;
    Id<int32_t> i, j; 
    return match(arr)(
        pattern | ds(i, j, _, j, i) = expr(true),
        pattern | _                 = expr(false)
    );
}

static_assert(symmetric(std::array<int32_t, 5>{5, 0, 3, 7, 10}) == false);
static_assert(symmetric(std::array<int32_t, 5>{5, 0, 3, 0, 5}) == true);
static_assert(symmetric(std::array<int32_t, 5>{5, 1, 3, 0, 5}) == false);

Hello Mars!

Now we come to the most powerful parts: Destructure Pattern. Destructure Pattern can be used for std::tuple, std::pair, std::array (fixed-sized containers), and dynamic containers or sized ranges(std::vector, std::list, std::set, and so on) with std::begin and std::end supports.

The outermost ds inside pattern can be omitted. When pattern receives multiple parameters, they are treated as subpatterns of a ds pattern.

#include "matchit.h"

template<typename T1, typename T2>
constexpr auto eval(std::tuple<char, T1, T2> const& expr)
{
    using namespace matchit;
    Id<T1> i;
    Id<T2> j;
    return match(expr)(
        pattern | ds('+', i, j) = i + j,
        pattern | ds('-', i, j) = i - j,
        pattern | ds('*', i, j) = i * j,
        pattern | ds('/', i, j) = i / j,
        pattern | _ = []
        {
            assert(false);
            return -1;
        });
}

Some operators have been overloaded for Id, so i + j will return a nullary function that return the value of *i + *j.

There also ways to destructure your struct / class, make your struct / class tuple-like or adopt App Pattern. The second option looks like

// Another option to destructure your struct / class.
constexpr auto dsByMember(DummyStruct const&v)
{
    using namespace matchit;
    // compose patterns for destructuring struct DummyStruct.
    constexpr auto dsA = dsVia(&DummyStruct::size, &DummyStruct::name);
    Id<char const*> name;
    return match(v)(
        pattern | dsA(2, name) = expr(name),
        pattern | _ = expr("not matched")
    );
};

static_assert(dsByMember(DummyStruct{1, "123"}) == std::string_view{"not matched"});
static_assert(dsByMember(DummyStruct{2, "123"}) == std::string_view{"123"});

Let's continue the journey. Sometimes you have multiple identifiers and you want exert a restriction on the relationship of them. Is that possible? Sure! Here comes the Match Guard. Its syntax is

pattern | PATTERN | when(GUARD) = HANDLER

Say, we want to match only when the sum of two identifiers equal to some value, we can write codes as

#include <array>
#include "matchit.h"

constexpr bool sumIs(std::array<int32_t, 2> const& arr, int32_t s)
{
    using namespace matchit;
    Id<int32_t> i, j;
    return match(arr)(
        pattern | ds(i, j) | when(i + j == s) = expr(true),
        pattern | _                           = expr(false));
}

static_assert(sumIs(std::array<int32_t, 2>{5, 6}, 11));

That is cool, isn't it? Note that i + j == s will return a nullary function that return the result of *i + *j == s.

Now we come to the Ooo Pattern. What is that? You may ask. In some programming language it's called Rest Pattern. You can match arbitrary number of items with it. It can only be used inside ds patterns though and at most one Ooo pattern can appear inside a ds pattern. You can write the code as following when you want to check pattern of a tuple.

#include <array>
#include "matchit.h"

template <typename Tuple>
constexpr int32_t detectTuplePattern(Tuple const& tuple)
{
    using namespace matchit;
    return match(tuple)
    (
        pattern | ds(2, ooo, 2)  = expr(4),
        pattern | ds(2, ooo   )  = expr(3),
        pattern | ds(ooo, 2   )  = expr(2),
        pattern | ds(ooo      )  = expr(1)
    );
}

static_assert(detectTuplePattern(std::make_tuple(2, 3, 5, 7, 2)) == 4);

What is more, we can bind a subrange to the ooo pattern when destructuring a std::array or other containers / ranges. That is quite cool. We can check if an/a array/vector/list/set/map/subrange/... is symmetric with:

template <typename Range>
constexpr bool recursiveSymmetric(Range const &range)
{
    Id<int32_t> i;
    Id<SubrangeT<Range const>> subrange;
    return match(range)(
        pattern | ds(i, subrange.at(ooo), i) = [&] { return recursiveSymmetric(*subrange); },
        pattern | ds(_, ooo, _)              = expr(false),
        pattern | _                          = expr(true)
    );

In the first pattern, we require that the head equals to the end. and if that is the case, we further check the rest parts (bound to subrange) via a recursive call. Once some nested call fails to meet that requirement (fall through to the second pattern), the checking fails. Otherwise when there are only one element left or the ra