match.cpp

struct I {
  virtual ~I() = default;
};
struct A : public I { int value = 1; };
struct B : public I { int value = 2; };
struct C : public I { int value = 3; };

template <template <int...> class _Tp, class>
struct instance_of : std::false_type { };

template <template <int...> class _Tp, int... _Args>
struct instance_of<_Tp, _Tp<_Args...>> : std::true_type { };

template<class T, bool R, class L = char>
struct InfoBlock {
  typedef L pred_t;
  typedef T type;
  static constexpr inline bool value = R;
  
  L lambda;
  
  InfoBlock(L lambda = 0) : lambda(lambda) { }
};

template<class T, bool R, class L = char>
static InfoBlock<T, R, L> make_info_block(L lambda = 0) {
  return InfoBlock<T, R, L>(lambda);
}

struct Dummy { };

template<int Begin = 0, int End = std::numeric_limits<int>::max()>
struct Range {
  static constexpr inline bool value = false;
  static constexpr inline bool begin = Begin;
  static constexpr inline bool end = End;
  
  typedef char pred_t;
  typedef Dummy type;
};

using AnyRange = Range<>;

template <typename, typename> struct OutPtr;

template <typename  T, typename ...Args>
struct OutPtr<T, std::tuple<Args...>>
{
    using type = std::tuple<typename T::type*, Args...>;
};

template <typename...> struct filter;

template <> struct filter<> { using type = std::tuple<>; };

template <typename Head, typename ...Tail>
struct filter<Head, Tail...>
{
    using type = typename std::conditional<Head::value,
                               typename OutPtr<Head, typename filter<Tail...>::type>::type,
                               typename filter<Tail...>::type
                          >::type;
};

template<class T, class B1, class...Blocks>
std::optional<typename filter<B1, Blocks...>::type>
match(T first, T last, B1 block, Blocks... blocks)
{
  if (first == last) return std::nullopt;
  
  if constexpr (instance_of<Range, B1>::value) {
    for (size_t i = B1::begin; first != last && i != B1::end; ++first, ++i) {
      if (auto others = match(first, last, blocks...)) {
        return { others.value() };
      }
    }
  }
  
  if constexpr (sizeof...(Blocks) > 0) {
    auto *element = dynamic_cast<typename B1::type*>(first);
    
    if (auto others = match(++first, last, blocks...)) {
      if constexpr (B1::value) {
        if (element == nullptr) return std::nullopt;
        if constexpr (!std::is_same<typename B1::pred_t, char>::value) {
          if (!block.lambda(element)) return std::nullopt;
        }
        
        return { std::tuple_cat(std::make_tuple(element), others.value()) };
      } else {
        return { others.value() };
      }
    }
  } else {
    if (auto *element = dynamic_cast<typename B1::type*>(first)) {
      if constexpr (!std::is_same<typename B1::pred_t, char>::value) {
        if (!block.lambda(element)) return std::nullopt;
      }
      
      if constexpr (!B1::value) {
        return { };
      }
      
      return { std::make_tuple(element) };
    }
  }
  
  return std::nullopt;
}

int main(int, char**)
{
  // ...
  auto [a, b, c, a] = match(begin, end,
                         InfoBlock<A, true>(),
                         InfoBlock<B, true>(),
                         InfoBlock<A, false>(),
                         AnyRange(),
                         InfoBlock<C, true>(),
                         Range<1, 2>(),
                         make_info_block<A, true>([](A *a) -> bool {
                           return a->value == 2;
                         }));
  
  return 0;
}