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

Overview

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

match(it).cpp

Standard Type Type

Platform Platform Platform

CMake CMake GitHub license codecov

Features

  • Easy to get started.

    • godbolt
  • 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.

Option 2. Manage with cmake

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.

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.

= 0); return match(n)( pattern | 0 = expr(1), pattern | _ = [n] { return n * factorial(n - 1); } ); } ">
#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:

= 0 ? a : -a; }, pattern | _ = [&] { return gcd(b, a%b); } ); } static_assert(gcd(12, 6) == 6); ">
#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:

template 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) ); } ">
#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:

1000) = expr(true), pattern | _ = expr(false) ); } // app with projection returning scalar types is supported by constexpr match. static_assert(isLarge(100)); ">
#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

s; return match(value)( pattern | app(_ * _, s.at(_ > 1000)) = [&] { std::cout << value << "^2 = " << *s << " > 1000!" << std::endl; return true; }, pattern | _ = expr(false)); } ">
#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 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:

const& arr) { using namespace matchit; Id i, j; return match(arr)( pattern | ds(i, j, _, j, i) = expr(true), pattern | _ = expr(false) ); } static_assert(symmetric(std::array{5, 0, 3, 7, 10}) == false); static_assert(symmetric(std::array{5, 0, 3, 0, 5}) == true); static_assert(symmetric(std::array{5, 1, 3, 0, 5}) == false); ">
#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.

constexpr auto eval(std::tuple const& expr) { using namespace matchit; Id i; Id 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; }); } ">
#include "matchit.h"

template<typename T1, typename T2>
constexpr auto eval(std::tuple<char, T1, T2> const& expr)
{
    using namespace matchit;
    Id i;
    Id 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

const& arr, int32_t s) { using namespace matchit; Id i, j; return match(arr)( pattern | ds(i, j) | when(i + j == s) = expr(true), pattern | _ = expr(false)); } static_assert(sumIs(std::array{5, 6}, 11)); ">
#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.

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); ">
#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;
    Idconst>> 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 range size is zero, the last pattern gets matched, we return true.

Hello Sun!

We've done with our core patterns. Now let's start the journey of composing patterns.

You should be familiar with Some Pattern and None Pattern if you have used the pattern matching feature in Rust.

Some / None Patterns can be used to match raw pointers, std::optional, std::unique_ptr, std::shared_ptr and other types that can be converted to bool and dereferenced. A typical sample can be

constexpr auto square(std::optional const& t) { using namespace matchit; Id id; return match(t)( pattern | some(id) = id * id, pattern | none = expr(0)); } constexpr auto x = std::make_optional(5); static_assert(square(x) == 25); ">
#include "matchit.h"

template <typename T>
constexpr auto square(std::optional const& t)
{
    using namespace matchit;
    Id id;
    return match(t)(
        pattern | some(id) = id * id,
        pattern | none     = expr(0));
}
constexpr auto x = std::make_optional(5);
static_assert(square(x) == 25);

Some pattern accepts a subpattern. In the sample the subpattern is an identifier and we bind the dereferenced result to it. None pattern is alone.

Some and none patterns are not atomic patterns in match(it), they are composed via

template <typename T>
constexpr auto cast = [](auto && input) {
    return static_cast(input);
}; 

constexpr auto deref = [](auto &&x) { return *x; };

constexpr auto some = [](auto const pat) {
    return and_(app(cast<bool>, true), app(deref, pat));
};

constexpr auto none = app(cast<bool>, false);

For Some pattern, first we cast the value to a boolean value, if the boolean value is true, we can further dereference it. Otherwise, the match fails. For None pattern we simply check if the converted boolean value is false.

As pattern is very useful for handling sum type, including class hierarchies, std::variant, and std::any. std::variant and std::any can be visited as

constexpr auto getClassName(T const& v) { using namespace matchit; return match(v)( pattern | as(_) = expr("chars"), pattern | as(_) = expr("int32_t") ); } constexpr std::variant v = 123; static_assert(getClassName(v) == std::string_view{"int32_t"}); ">
#include "matchit.h"
template <typename T>
constexpr auto getClassName(T const& v)
{
    using namespace matchit;
    return match(v)(
        pattern | as<char const*>(_) = expr("chars"),
        pattern | as<int32_t>(_)     = expr("int32_t")
    );
}

constexpr std::variant<int32_t, char const*> v = 123;
static_assert(getClassName(v) == std::string_view{"int32_t"});

Class hierarchies can be matched as

(_) = expr("Square") ); } ">
struct Shape
{
    virtual ~Shape() = default;
};
struct Circle : Shape {};
struct Square : Shape {};

auto getClassName(Shape const &s)
{
    return match(s)(
        pattern | as(_) = expr("Circle"),
        pattern | as(_) = expr("Square")
    );
}

As pattern is not an atomic pattern, either. It is composed via

template <typename T>
constexpr AsPointer asPointer;

template <typename T>
constexpr auto as = [](auto const pat) {
    return app(asPointer, some(pat));
};

For classes, dynamic_cast is used by default for As pattern, but we can change the behavior through the Customization Point. Users can customize the down casting via defining a get_if function for their classes, similar to std::get_if for std::variant:

constexpr auto kind = app(&Num::kind, k); template auto get_if(Num const* num) { return static_cast(num->kind() == T::k ? num : nullptr); } int32_t staticCastAs(Num const& input) { using namespace matchit; return match(input)( pattern | as(_) = expr(1), pattern | kind = expr(2), pattern | _ = expr(3)); } int32_t main() { std::cout << staticCastAs(One{}) << std::endl; return 0; } ">
#include <iostream>
#include "matchit.h"

enum class Kind { kONE, kTWO };

class Num
{
public:
    virtual ~Num() = default;
    virtual Kind kind() const = 0;
};

class One : public Num
{
public:
    constexpr static auto k = Kind::kONE;
    Kind kind() const override { return k; }
};

class Two : public Num
{
public:
    constexpr static auto k = Kind::kTWO;
    Kind kind() const override
    {
        return k;
    }
};

template 
constexpr auto kind = app(&Num::kind, k);

template <typename T>
auto get_if(Num const* num) {
  return static_castconst *>(num->kind() == T::k ? num : nullptr);
}


int32_t staticCastAs(Num const& input)
{
    using namespace matchit;
    return match(input)(
        pattern | as(_)       = expr(1),
        pattern | kindkTWO> = expr(2),
        pattern | _                = expr(3));
}

int32_t main()
{
    std::cout << staticCastAs(One{}) << std::endl;
    return 0;
}

Hello Milky Way!

There is additional Customziation Point.

Users can specialize PatternTraits if they want to add a brand new pattern.

Real world use case

mathiu is a simple computer algebra system built upon match(it).

A simple sample of mathiu:

auto const x = symbol("x");
auto const e = x ^ fraction(2, 3);
auto const d = diff(e, x);
// prints (* 2/3 (^ x -1/3))
std::cout << toString(d) << std::endl;

Contact

If you have questions regarding the library, I would like to invite you to open an issue at GitHub.

Related Work

match(it)'s syntax / pattern designs have been heavily influenced by these related work

Issues
  • lambda parameters instead of id variables

    lambda parameters instead of id variables

    Could having to use id variables be replaced with lambda parameters? eg: instead of this

    Id<string> text;
    match(variant)(
    pattern | as<string>(text) = [&] {
                std::cout << "Text message: " << *text << std::endl;
            })
    

    this

    match(variant)(
    pattern | as<string> = [](const string& text) {
                std::cout << "Text message: " << text << std::endl;
            })
    
    good first issue 
    opened by GunpowderGuy 3
Releases(v0.1.3)
Owner
Bowen Fu
Bowen Fu
Anime browser built with AniList APIs, showcasing clean Flutter BLoC architecture

Anime browser built with AniList APIs. The purpose of this project is to showcase clean Flutter application architecture with BLoC design pattern.

Peter A. Bizjak 21 Jun 22, 2022
Hybrid Detect demonstrates CPU topology detection using multiple intrinsic and OS level APIs.

Hybrid Detect Hybrid Detect demonstrates CPU topology detection using multiple intrinsic and OS level APIs. First, we demonstrate usage of CPUID intri

null 27 Jul 21, 2022
The most powerful and customizable binary pattern scanner written on modern C++

Sig The most powerful and customizable binary pattern scanner written on modern C++ ✔ Capabilities: Support for all common pattern formats: Pattern +

Александр 135 Jul 21, 2022
Edf is an event-driven framework for embedded system (e.g. FreeRTOS) with state machine and subscriber-publisher pattern.

Edf means event-driven framework. Event-driven programming is a common pattern in embedded systems. However, if you develop software directly on top o

Arrow89 6 Aug 3, 2022
Small header-only C++ library that helps to initialize Vulkan instance and device object

Vulkan Extensions & Features Help, or VkExtensionsFeaturesHelp, is a small, header-only, C++ library for developers who use Vulkan API.

Adam Sawicki 10 Apr 13, 2022
C++ header-only library for generic data validation.

C++ header-only library for generic data validation.

Evgeny Sidorov 26 Jul 13, 2022
a compile-time, header-only, dimensional analysis and unit conversion library built on c++14 with no dependencies.

UNITS A compile-time, header-only, dimensional analysis library built on c++14 with no dependencies. Get in touch If you are using units.h in producti

Nic Holthaus 769 Aug 5, 2022
A header only C++ library that provides type safety and user defined literals for physical units

SI - Type safety for physical units A header only c++ library that provides type safety and user defined literals for handling pyhsical values defined

Dominik Berner 379 Jul 21, 2022
Small Header only library to parse argv for flags

Small Header only library to parse argv for flags

Ben Wernicke 2 Dec 8, 2021
Header only roguelike rendering library.

Header only roguelike rendering library. Support for Opengl33 and Raylib. Features Support for custom glyph atlasses with up to 65655 tiles of custom

Journeyman 6 Aug 4, 2022
A Header-Only Engine that tries to use SFML in a deeper level

⚙️ SFML-Low-Level-Engine ⚙️ A header-only library that tries to use SFML at a deeper level ?? Instalation Download the source code and put the GLD fol

!Gustavo! 4 Aug 27, 2021
Header-only C++20 wrapper for MPI 4.0.

MPI Modern C++20 message passing interface wrapper. Examples Initialization: mpi::environment environment; const auto& communicator = mpi::world_c

Ali Can Demiralp 29 Apr 8, 2022
This is a Header-only c++ string implentation which specializes in dealing with small strings. 🧵

string-impl This is a Header-only c++ string implentation which specializes in dealing with small strings. ?? Usage ⌨ Instantiation A string can be in

null 1 Apr 1, 2022
libparser is a small C library that parses input based on a precompiled context-free grammar.

libparser is a small C library that parses input based on a precompiled context-free grammar.

Mattias Andrée 9 Jul 19, 2022
The lightweight and modern Map SDK for Android and iOS

Open Mobile Maps The lightweight and modern Map SDK for Android (6.0+) and iOS (10+) openmobilemaps.io Getting started Readme Android Readme iOS Featu

Open Mobile Maps 89 Jul 6, 2022
Lightweight state machine implemented in C++

Intro This is my second take on C++ state machine implementation. My first attempt can be found here. The main goals of the implementation are: No dyn

Łukasz Gemborowski 20 Jul 14, 2022
MMUit is a lightweight toolkit to explore and modify address translation for ARM64.

Overview MMUit is a lightweight toolkit to explore and modify address translation for ARM64. C/C++ interface detailed information on VA, TTE, TCR etc

Alexander Hude 37 Feb 13, 2022
The goal of arrowvctrs is to wrap the Arrow Data C API and Arrow Stream C API to provide lightweight Arrow support for R packages

The goal of arrowvctrs is to wrap the Arrow Data C API and Arrow Stream C API to provide lightweight Arrow support for R packages to consume and produce streams of data in Arrow format. Right now it’s just a fun way for me to learn about Arrow!

Dewey Dunnington 30 Aug 5, 2022
Simple and lightweight pathname parser for C. This module helps to parse dirname, basename, filename and file extension .

Path Module For C File name and extension parsing functionality are removed because it's difficult to distinguish between a hidden dir (ex: .git) and

Prajwal Chapagain 3 Feb 25, 2022