blog

C++: Pattern Matching Template Types

How to check if a template type matches a pattern? Something like is_like_v<T, vector<int,_>>.

A previous post considered function overload resolution in the presence of forwarding references, and proposed a design pattern of merging all the overloads of a function into one, using if constexpr to implement the desired overload resolution logic for various argument types. This was restricted to using std::is_same_v and std::decay_t for exact type matches, up to const and ref qualifiers.

A follow up post extended this to checks of whether a given type is an instantiation of a given template, introducing a new type trait is_instance_of_v, used as e.g. is_instance_of_v<T, std::vector>.

In this post we go further again to implement pattern matching on template types. Patterns are written as e.g. A<_,_> for an instantiation of a class template A with two template arguments, or A<int,_> where the first template argument must be int but the second may be anything, or even nested patterns such as B<_, A<int,_>>. We then introduce a new type trait is_like_v to allow matching of types against such patterns, used as e.g. is_like_v<T, A<int,_>> or is_like_v<T, std::vector<_, std::allocator<_>>.

1. Motivation
2. Implementation
3. Demonstration
4. Bonus: one-of-a-set
5. Limitations
6. Conclusion

Motivation

Consider a template type such as std::vector:

template<
    class T,
    class Allocator = std::allocator<T>
  > class vector;

It has two template parameters, T and Allocator, the first giving the element type, the second the allocator type. We may want to query whether some type is an instantiation of std::vector but with a specific element type, say int, while allowing for any allocator type. Effectively we’re looking for a partial match, a bit like a partial specialization of a template. We cannot do this with std::is_same_v or the is_instance_of_v type traits used in previous posts, however.

In this post we develop a new type trait is_like_v that works a bit like std::is_same_v, but with support for partial matches using a wildcard denoted by the underscore _ (using the underscore for fun, mostly—alternatives are possible). It will be used something like this:

if constexpr (is_like_v<T,vector<double,_>>) {
  // ...do something
}

Implementation

We start with a basic declaration of is_like_v<T,P>, where T denotes a type, and P a pattern against which to match it. The pattern is itself a type, but it may include the wildcard _.

The initial definition equates is_like_v<T,P> with std::is_same_v<T,P>, i.e. two types are alike if they are the same:

template<class T, class P>
inline constexpr bool is_like_v = std::is_same_v<T,P>;

Next, we introduce a type to denote wildcards in template patterns. For fun and nice-looking patterns, we’re going to make this the underscore _, although in practice we should be wary of name collisions and reserved words:

struct _ {};

All types match the wildcard:

template<class T>
inline constexpr bool is_like_v<T,_> = true;

The final piece is more complicated: two template types are alike if they are instantiations of the same class template, and their template arguments are alike:

template<template<class...> class T, class... Ts, class... Us>
requires (sizeof...(Ts) == sizeof...(Us))
inline constexpr bool is_like_v<T<Ts...>,T<Us...>> = (is_like_v<Ts,Us> && ...);

Here we use a plentiful mix of modern C++ features: template parameter packs and the sizeof... operator, template template arguments (as we did for is_instance_of_v), constraints and concepts (the requires) to check for the same number of template arguments, and fold expressions (the (is_like<Ts,Us> && ...)).

But those few lines are all we need.

This does pattern matching up to const and ref qualifiers. To ignore const and ref qualifiers, massage in std::decay_t as in the first post.

Demonstration

We can now use is_like_v along the following lines:

is_like_v<std::vector<int>, std::vector<int,_>>;  // true
is_like_v<std::vector<int>, std::vector<_,_>>;  // true
is_like_v<std::vector<int>, std::list<int,_>>;  // false
is_like_v<std::vector<int>, std::list<_,_>>;  // false
is_like_v<std::vector<int>, std::vector<_, std::allocator<_>>>;  // true

We can use such checks in if constexpr statements to implement the body of a function with forwarding reference arguments, as suggested in the first post, but also other circumstances.

Bonus: one-of-a-set

Let’s get beyond single wildcards, and consider sets of patterns as well. Given two or more patterns, we would like is_like_v to give true if the given type matches at least one of those patterns.

By way of motivation, consider a numerical library where expression templates are used to represent mathematical formulae that are lazily evaluated. A linear expression of $x$ such as $ax + c$ may be represented by the type Add<Mul<double,T>,double>, where T is the generic type of $x$ (either a simple arithmetic type such as double or a nested expression template type). But because multiplication and addition are commutative, i.e. $xy = yx$ and $x + y = y + x$, a linear expression of $x$ may emerge with any one of the types Add<Mul<double,T>,double>, Add<Mul<T,double>,double>, Add<double,Mul<double,T>> or Add<double,Mul<T,double>>.

How to match all of these?

Similar to the wildcard type _, we can introduce a set type in that collects together multiple patterns:

template<class... Ps>
struct in {};

Now extend is_like_v with a new specialization to handle the in type:

template<class T, class... Ps>
inline constexpr bool is_like_v<T,in<Ps...>> = (is_like_v<T,Ps> || ...);

This uses a fold expression to give true if the type T matches any of the patterns Ps.... We can now use something like the following:

is_like_v<T, in<
      Add<Mul<double,_>,double>,
      Add<Mul<_,double>,double>,
      Add<double,Mul<double,_>>,
      Add<double,Mul<_,double>>
    >>;

If the pattern is to be reused, or if we just prefer the aesthetic, we can declare the pattern first:

using linear_pattern = in<
      Add<Mul<double,_>,double>,
      Add<Mul<_,double>,double>,
      Add<double,Mul<double,_>>,
      Add<double,Mul<_,double>>
    >;
is_like_v<T, linear_pattern>;

Implementing a function with forwarding reference parameters may then look something like this:

template<class T>
void f(T&& x) {
  if constexpr (is_like_v<std::decay_t<T>, linear_pattern>) {
    // implementation for linear expression
    std::cerr << "f(linear x)" << std::endl;
  } else {
    // implementation for everything else
    std::cerr << "f(T&& x)" << std::endl;
  }
}

This approach may reduce code size compared to separate function overloads for each of the linear expression types.

Limitations

There are some limitations to pattern matching template types in this way.

Because the wildcard _ is defined as a type, it cannot be substituted for non-type template parameters. That precludes its use where value template parameters are involved, as for the second argument of std::array (which gives the static size of the array):

template<
    class T,
    std::size_t N
> struct array;

or where template template parameters are involved, as for the is_instance_of_v introduced previously.

Where duck-typed class templates are involved, we get away with using _ as a template argument in patterns because, while those patterns are types, they are not used in such a way that requires their instantiation. On the other hand, where class templates with concept or SFINAE constraints are involved, _ may be rejected as a template argument prior to instantiation, in which case the approach will not work.

The same applies to the set type in.

A workaround for some of these limitations is to specialize is_like_v for particular types. Consider std::array again; if appropriate for the use case, we could specialize is_like_v to match the value type T, but ignore the length D:

template<class T, size_t M, class U, size_t N>
inline constexpr bool is_like_v<std::array<T,M>,std::array<U,N>> = is_like_v<T,U>;

Where concept or SFINAE constraints are in use, we might also specialize those constraints for the wildcard _ and set in types to satisfy them artificially. How will depend on the specifics of the constraints, but will likely involve the specialization of certain other type traits for these two types.

Mileage will vary, and the implementation of is_like_v may need to be specific to the circumstances.

Conclusion

This is the final of three posts inspired by the idea of establishing a design pattern for overloading functions in the presence of forwarding references, with greater control over overload resolution. Putting them all together, the suggested paradigm is to:

1. Combine all function overloads into one with forwarding reference parameters.
2. Within the body of that one function, use if constexpr to provide implementations for different argument types.
3. Within each if constexpr condition, use type traits such as std::is_same_v, or the new type traits introduced in these posts, is_instance_of_v and is_like_v, to check for types.
4. Within each if constexpr body, provide the appropriate implementation for those types.

Taking this approach can reduce repeated code in situations where multiple function overloads would otherwise be required, especially so where several of those overloads would have essentially the same implementation. It can also provide finer control over behavior where the usual overload resolution rules do not yield the desired precedence, as the body of the one function can be implemented with arbitrary selection logic for the argument types.

Here’s a complete example for further experimentation with is_like_v:

#include <type_traits>
#include <iostream>
#include <vector>
#include <list>
#include <array>

template<class T, class P>
inline constexpr bool is_like_v = std::is_same_v<T,P>;

struct _ {};

template<class T>
inline constexpr bool is_like_v<T,_> = true;

template<template<class...> class T, class... Ts, class... Us>
requires (sizeof...(Ts) == sizeof...(Us))
inline constexpr bool is_like_v<T<Ts...>,T<Us...>> = (is_like_v<Ts,Us> && ...);

template<class T, size_t M, class U, size_t N>
inline constexpr bool is_like_v<std::array<T,M>,std::array<U,N>> = is_like_v<T,U>;

template<class... Ps>
struct in {};

template<class T, class... Ps>
inline constexpr bool is_like_v<T,in<Ps...>> = (is_like_v<T,Ps> || ...);

int main() {
  std::cerr << is_like_v<std::vector<int>, std::vector<int,_>> << std::endl;  // true
  std::cerr << is_like_v<std::vector<int>, std::vector<_,_>> << std::endl;  // true
  std::cerr << is_like_v<std::vector<int>, std::list<int,_>> << std::endl;  // false
  std::cerr << is_like_v<std::vector<int>, std::list<_,_>> << std::endl;  // false
  std::cerr << is_like_v<std::vector<int>, std::vector<_, std::allocator<_>>> << std::endl;  // true
  std::cerr << is_like_v<std::array<int,10>, std::array<_,20>> << std::endl;  // true, due to specialization

  using pattern = in<
        std::vector<_,std::allocator<_>>,
        std::list<_,std::allocator<_>>
      >;
  std::cerr << is_like_v<std::vector<int>,pattern> << std::endl;  // true
  return 0;
}