Pattern matching with predicates support

Question

TL;DR

https://godbolt.org/z/TMfb8z99h

static std::string match(const std::variant<int, double, std::string, std::vector<int>> &v) {
    return
      v >>= m
      // matches `int`
      | [](int i) { return std::to_string(i); }
      // matches `std::string`
      | [](const std::string &s) { return s; }
      // only matches `double`, since `int` has been matched above
      | m_if<std::is_fundamental>([](double d) { return std::to_string(d); })
      // matches `std::vector<int, Allocator>`, can also be 
      // m_is<std::vector, int, traits::_ph>
      | m_is<std::vector, int>([](const auto& v) {
            int sum = 0; 
            for (int i: v) sum += i; 
            return std::to_string(sum); });
}

int main() {
    std::cout 
      << match("oceanic")
      << '\n' << match(815) 
      << '\n' << match(23.42)
      << '\n' << match(std::vector{4, 8, 15, 16, 23, 42});

In detail

I wanted a nice and neat interface for pattern matching an std::variant-like structure that can be used (initially) as part of my library's API utilities.

• Why not just std::visit?
  It's invocation in itself is overly verbose.
• Why not just use a set of if constexpr in the labmda-visitor?
  It works only starting from C++17, whilst I am aiming for a public API usable as early as at least C++11 (if possible).
  ... And it also adds to boilerplate (need to write using T = std::decay_t<decltype(v)>; every time) and if constexpr itself is rather long.
• Why not just go with overloaded{...} lambda set?
  The main reason you can guess from the example usage I have provided above: using template predicates is not possible. Matching templates "ignoring" allocators also requires some additional work (before C++20, where template lambdas become available).
  ... And it is impossible to use with callable types declared as final. Not a deal breaker though.

Interface and design decisions

For the simplest implementation possible I decided to construct the matching object in-place and invoke it in a single expression.

• For matching: m, global inline constant used for overloading.
• For general predicates: m_if<predicate_template, templ_args...>. For example: m_if<is_fundamental> or m_if<is_same, int>.
• For direct type and template matching: m_is.
  For example:
  • m_is<int> matches int,
  • m_is<std::basic_string> matches all the specializations
  • m_is<std::vector, int> matches all the specializatioins of std::vector<int, AllocatorT>
  • m_is<std::array, int> matches all the std::array<int, N>. Possible, because function templates support overloads, unlike class templates.
  • [](const std::string&) {} matches fully specialized std::string. Only non-template lambdas and callable types with a single operator() overload are acceptable, because the argument is used for m_is<Arg>.
• For collecting matches: operator|, I believe that no explanation is needed.
• For invocation: operator>>= and operator<<= just because of the precedence. And operator(), it is less confusing for functional folks, but invocation is not that clean.
• constexpr invocation should be possible.

Can it blow up in your face?

All the types must be matched, otherwise a compile-time error. For example, if I uncomment m_if<std::is_fundamental> case, I get:

• Clang: the very first line allows to understand which type (double) was not handled

<source>:123:20: error: static assertion failed due to requirement '(double *)nullptr , false': unmatched Type
  123 |     static_assert(((T*)nullptr, Matched), "unmatched Type");

• GCC: ugly as always, but T = double can be seen from the first line

<source>: In instantiation of 'constexpr std::size_t traits::{anonymous}::_find_match(std::bool_constant<Matched>) [with T = double; long unsigned int I = 2; bool Matched = false; std::size_t = long unsigned int; std::bool_constant<Matched> = std::bool_constant<false>]':
<source>:132:45:   required from 'constexpr std::size_t traits::{anonymous}::_find_match(std::false_type) [with T = double; long unsigned int I = 0; Match = _match<traits::_bind<traits::is_same_type, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::pred, match(const std::variant<int, double, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> > >&)::<lambda(const std::string&)> >; Matches = {_match<traits::_bind<traits::is_template_bind<std::vector, int>::pred>::pred, match(const std::variant<int, double, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> > >&)::<lambda(const auto:30&)> >}; std::size_t = long unsigned int; std::false_type = std::false_type]'
  132 |     return _find_match<T, I + 1, Matches...>(Match::template value<T>);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Redundant matches are not supported at this point

Limitations

It is practically impossible to compare 2 templates of different signatures, so the cases like m_is<std::array> are ad hoc'ed.

Implementation

#include <variant>
#include <type_traits>
#include <tuple>

namespace traits {

template <typename T, typename = decltype(&T::operator())>
struct callable_arg;

template <typename T, typename Arg, typename Ret>
struct callable_arg<T, Ret(T::*)(Arg)> {
    using type = Arg;
};

template <typename T, typename Arg, typename Ret>
struct callable_arg<T, Ret(T::*)(Arg) const> {
    using type = Arg;
};

template <typename T>
using callable_arg_t = typename callable_arg<T>::type;

template <template <typename, typename...> class Pred, typename ... Args>
struct _bind {
    template <typename T>
    using pred = Pred<T, Args...>;
};

/// placeholder to ignore types
struct _ph {};

template <typename L, typename R>
struct is_same : std::is_same<L, R> {};

template <typename L>
struct is_same<L, _ph> : std::true_type {};

template <typename R>
struct is_same<_ph, R> : std::true_type {};

template <typename ... List>
struct list_t;

template <typename, typename ...>
struct _is_subset_of;

template <typename ... Of>
struct _is_subset_of<list_t<>, Of...> : std::true_type {};

// gcc will not compile without it
template <>
struct _is_subset_of<list_t<>> : std::true_type {};

template <typename ... T>
struct _is_subset_of<list_t<T...>> : std::false_type {};

template <typename T, typename ... Ts, typename Of, typename ... Ofs>
struct _is_subset_of<list_t<T, Ts...>, Of, Ofs...> : 
    std::conditional<is_same<T, Of>::value, 
        _is_subset_of<list_t<Ts...>, Ofs...>, 
        std::false_type>::type {};

template <typename ... T>
struct list_t {
    template <typename ... Of>
    struct is_subset_of : _is_subset_of<list_t<T...>, Of...> {};
};

// example/check
static_assert(list_t<>::is_subset_of<>::value == std::true_type::value);
static_assert(list_t<>::is_subset_of<int>::value == std::true_type::value);
static_assert(list_t<int>::is_subset_of<int>::value == std::true_type::value);
static_assert(list_t<int>::is_subset_of<int, double>::value == std::true_type::value);
static_assert(list_t<>::is_subset_of<int, double>::value == std::true_type::value);
static_assert(list_t<int>::is_subset_of<>::value != std::true_type::value);
static_assert(list_t<_ph>::is_subset_of<int, double>::value == std::true_type::value);

template <typename Arg, typename T>
struct is_same_type : is_same<std::remove_const_t<std::remove_reference_t<Arg>>, T> {};

template <typename, template <typename...> class, typename ...>
struct is_template : std::false_type {};

template <template <typename...> class Templ, typename ... Args, typename ... SpecArgs>
struct is_template<Templ<Args...>, Templ, SpecArgs...> 
    : list_t<SpecArgs...>::template is_subset_of<Args...> {};

template <template <typename, typename...> class Templ, typename ... SpecArgs>
struct is_template_bind {
    template <typename T>
    using pred = is_template<T, Templ, SpecArgs...>;
};

template <typename T, template <typename> class...>
struct foldl;

template <typename T, template <typename> class Pred>
struct foldl<T, Pred> {
    using type = typename Pred<T>::type;
};

template <typename T, template <typename> class Left,
    template <typename> class ... Right>
struct foldl<T, Left, Right...> : foldl<typename Left<T>::type, Right...> {};

template <typename T, template <typename> class ... List>
using foldl_t = typename foldl<T, List...>::type;

// example/check
static_assert(
    std::is_same_v<
        int,
        foldl_t<int const&, 
            std::remove_reference,
            std::remove_const
            >>);

namespace {
template <typename T, std::size_t I, bool Matched>
constexpr static std::size_t _find_match(std::bool_constant<Matched>) noexcept {
    static_assert(((T*)nullptr, Matched), "unmatched Type");
    return I;
}

template <typename T, std::size_t I, typename ...>
constexpr static std::size_t _find_match(std::true_type) noexcept { return I; }

template <typename T, std::size_t I, typename Match, typename ... Matches>
constexpr static std::size_t _find_match(std::false_type) noexcept {
    return _find_match<T, I + 1, Matches...>(Match::template value<T>);
}

template <typename T, typename Match, typename ... Matches>
constexpr static std::size_t find_match() noexcept {
    return _find_match<T, 0, Matches...>(Match::template value<T>);
}
} // namespace
} // namespace traits

template <template <typename> class Pred, typename Callable>
struct _match {
    template <typename T>
    constexpr static auto value = std::bool_constant<Pred<T>{}>();

    Callable _callable;
};

template <template <typename, typename...> class Pred, typename ... Args, typename Callable>
constexpr auto m_if(Callable c) noexcept
-> _match<traits::_bind<Pred, Args...>::template pred, Callable> {
    return {c};
}

template <typename T, typename Callable>
constexpr auto m_is(Callable c) noexcept {
    return m_if<traits::is_same_type, T>(c);
}

template <template <typename, typename...> class Templ, typename ... SpecArgs, 
    typename Callable>
constexpr auto m_is(Callable c) {
    return m_if<traits::is_template_bind<Templ, SpecArgs...>::template pred>(c);
}

template <typename ... Matches>
struct _m {
    std::tuple<Matches...> _matches;

    template <template <typename...> class Variant, typename ... T>
    constexpr decltype(auto) operator()(const Variant<T...> &var) { return _visit(var); }

    template <template <typename...> class Variant, typename ... T>
    constexpr decltype(auto) operator()(Variant<T...> &var) { return _visit(var); }

    template <template <typename...> class Variant, typename ... T>
    constexpr decltype(auto) operator()(Variant<T...> &&var) { return _visit(std::move(var)); }

private:
    template <typename Variant>
    constexpr decltype(auto) _visit(Variant &&var) {
        // todo: remove dependency on `std::visit`
        return std::visit(
            [&](auto && v) -> decltype(auto) {
                return std::get<
                    traits::find_match<std::decay_t<decltype(v)>, Matches...>()
                >(_matches)._callable(std::forward<decltype(v)>(v));
            }, std::forward<Variant>(var));
    }
};

template <typename ... Matches, template <typename> class Pred, typename Callable>
constexpr auto operator|(_m<Matches...> lhs, _match<Pred, Callable> rhs) noexcept 
    -> _m<Matches..., _match<Pred, Callable>> {
        return {std::tuple_cat(lhs._matches, std::make_tuple(rhs))};
}

template <typename ... Matches, typename Callable, 
    typename = std::void_t<decltype(&Callable::operator())>>
constexpr auto operator|(_m<Matches...> ms, Callable non_template_c) noexcept {
    return ms | 
        m_is<traits::foldl_t<traits::callable_arg_t<Callable>,
            std::remove_reference, 
            std::remove_const>>(non_template_c);
}

template <typename ... Matches, typename Variant>
constexpr decltype(auto) operator<<=(_m<Matches...> m, Variant &&var) {
    return m(std::forward<Variant>(var));
}

template <typename ... Matches, typename Variant>
constexpr decltype(auto) operator>>=(Variant &&var, _m<Matches...> m) {
    return m(std::forward<Variant>(var));
}

const inline _m<> m{};

Examples:

auto dummy() {
    constexpr auto _1 = 
    m
    | [](int i){ return i; }
    | [](double i){ return int(i); }
    <<= std::variant<int, double>{815};
    static_assert(815 == _1);

    constexpr auto _2 = 
    std::variant<int, double>{108.0} 
    >>= m
    | [](int i){ return i; }
    | [](double i){ return int(i); };
    static_assert(108 == _2);

    return _1;
}

#include <string>
#include <vector>
#include <iostream>

static std::string match(const std::variant<int, double, std::string, std::vector<int>> &v) {
    return
      v >>= m
      // matches `int`
      | [](int i) { return std::to_string(i); }
      // matches `std::string`
      | [](const std::string &s) { return s; }
      // only matches `double`, since `int` has been matched above
      | m_if<std::is_fundamental>([](double d) { return std::to_string(d); })
      // matches `std::vector<int, Allocator>`, can also be 
      // m_is<std::vector, int, traits::_ph>
      | m_is<std::vector, int>([](const auto& v) {
            int sum = 0; 
            for (int i: v) sum += i; 
            return std::to_string(sum); });
}

int main() {
    std::cout 
      << match("oceanic")
      << '\n' << match(815) 
      << '\n' << match(23.42)
      << '\n' << match(std::vector{4, 8, 15, 16, 23, 42});
}
```

Answer 1

Improve the API

When I read v >>= m, I see that v was the function parameter, but what is m? This is a very bad name for a global variable of something with a very specific function. I also don't see why you want to use the >>= operator here; it looks like a shift-assignment, which it definitely is not. I suggest changing the syntax so you'd write something like:

return pattern_matcher(v)
       | [](int i){ return std::to_string(i); }
       | …;

By using operator| you also had to introduce other types in the global namespace, such as m_if and m_is. Consider instead creating member functions of the matcher object, so you'd write something like this:

return pattern_matcher(v)
       .match([](int i){ … })
       .match([](const std::string& s){ … })
       .match_if<std::is_fundamental>([](double d){ … })
       .match_type<std::vector, int>([](const auto& v) {…});

Another option would be to do it in the style of std::optional:

return match(v, [](int i){ … })
       .or_else([](const std::string& s){ … })
       .or_else_if<std::is_fundamental>([](double d){ … })
       …;

To summarize, these changes would avoid magic incantations (v >>= m) and avoid adding things to the global namespace unnecessarily.

How to do it in C++17 and later

I agree with indi that I don't think it's worth writing this functionality when it's 2024, and you should be using at least C++17 already. Once you can use a newer version of C++, you get most of what you need from the standard library. The only issue might be that you want the behavior of trying each pattern in sequence and use the first matching one, which is something you can't do with an overloaded{…}. However, you can try to make a class that acts like an overload set, but instead stores a tuple of functions, and which has an operator() that tries them all in sequence. This way, you'd be able to write something like:

return std::visit(match_sequence{
                      [](int){…},
                      [](const std::string& s){…},
                      …
                      match_type<std::vector, int>([](const auto& v){…})
                  }, v);

What about functions taking multiple parameters?

You'll notice that std::visit() can take more than two parameters; the first is a function, the rest of the parameters are variants. The function is called with the value of each of the variants. This is something that is very hard to support with your current syntax, but if you use the style I recommend above, you can write something like:

using MyVariant = std::variant<int, double, std::string, std::vector<int>>;

static std::string match(const MyVariant& v1, const MyVariant& v2) {
    pattern_matcher(v1, v2)
    .match([](int i, int j){…})
    …;
}
```