Skip to content

Latest commit

 

History

History
1034 lines (863 loc) · 22.8 KB

From-Pattern-Matching-Proposal-to-matchit.md

File metadata and controls

1034 lines (863 loc) · 22.8 KB

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

match(it).cpp

In this page, we will give equivalent sample codes for samples from the C++ Pattern Matching Proposal.

For complete samples, please refer to samples directory.

Matching Integrals

In P1371R3:

inspect (x) {
    0 => { std::cout << "got zero"; }
    1 => { std::cout << "got one"; }
    __ => { std::cout << "don't care"; }
};

In match(it):

match(x) ( 
    pattern | 0 = [&]{ std::cout << "got zero"; },
    pattern | 1 = [&]{ std::cout << "got one"; },
    pattern | _ = [&]{ std::cout << "don't care"; }
);

Matching Strings

In P1371R3:

inspect (s) {
    "foo" => { std::cout << "got foo"; }
    "bar" => { std::cout << "got bar"; }
    __ => { std::cout << "don't care"; }
};

In match(it):

match(s)( 
    pattern | "foo" = [&]{ std::cout << "got foo"; },
    pattern | "bar" = [&]{ std::cout << "got bar"; },
    pattern | _     = [&]{ std::cout << "don't care"; }
);

Matching Tuples

In P1371R3:

inspect(p) {
    [0, 0] => { std::cout << "on origin"; }
    [0, y] => { std::cout << "on y-axis"; }
    [x, 0] => { std::cout << "on x-axis"; }
    [x, y] => { std::cout << x << ',' << y; }
};

In match(it):

Id<int32_t> x, y;
match(p) ( 
    pattern | ds(0, 0) = [&]{ std::cout << "on origin"; },
    pattern | ds(0, y) = [&]{ std::cout << "on y-axis"; },
    pattern | ds(x, 0) = [&]{ std::cout << "on x-axis"; },
    pattern | ds(x, y) = [&]{ std::cout << *x << ',' << *y; }
);

Matching Variants

In P1371R3:

inspect (v) {
    <int> i => {
        strm << "got int: " << i;
    }
    <float> f => {
        strm << "got float: " << f;
    }
};

In match(it):

Id<int> i;
Id<float> f;
match(v) ( 
    pattern | as<int>(i) = [&]{  
        strm << "got int: " << *i;
    },
    pattern | as<float>(f) = [&]{  
        strm << "got float: " << *f;
    }
);

Matching Polymorphic Types

struct Shape { virtual ~Shape() = default; };
struct Circle : Shape { int radius; };
struct Rectangle : Shape { int width, height; };

In P1371R3:

int get_area(const Shape& shape)
{
    return inspect (shape) {
        <Circle> [r] => 3.14 * r * r;
        <Rectangle> [w, h] => w * h;
    };
}

In match(it):

int get_area(const Shape& shape)
{
    Id <int> r, w, h;
    return match(shape) ( 
        // need to implement get for the structs.
        pattern | as<Circle>(ds(r))       = 3.14 * r * r,
        pattern | as<Rectangle>(ds(w, h)) = w * h
    );
}

Evaluating Expression Trees

struct Expr;
struct Neg { std::shared_ptr<Expr> expr; };
struct Add { std::shared_ptr<Expr> lhs, rhs; };
struct Mul { std::shared_ptr<Expr> lhs, rhs; };
struct Expr : std::variant<int, Neg, Add, Mul> { using variant::variant; };
namespace std {
template <>
struct variant_size<Expr> : variant_size<Expr::variant> {};
template <std::size_t I>
struct variant_alternative<I, Expr> : variant_alternative<I, Expr::variant> {}; }

In P1371R3:

int eval(const Expr& expr) {
  return inspect (expr) {
    <int> i => i;
    <Neg> [(*?) e] => -eval(e);
    <Add> [(*?) l, (*?) r] => eval(l) + eval(r);
    // Optimize multiplication by 0.
    <Mul> [(*?) <int> 0, __] => 0;
    <Mul> [__, (*?) <int> 0] => 0;
    <Mul> [(*?) l, (*?) r] => eval(l) * eval(r);
}; }

In match(it):

const auto asNegDs = asDsVia<Neg>(&Neg::expr);
const auto asAddDs = asDsVia<Add>(&Add::lhs, &Add::rhs);
const auto asMulDs = asDsVia<Mul>(&Mul::lhs, &Mul::rhs);

int eval(const Expr &ex)
{
    using namespace matchit;
    Id<int> i;
    Id<Expr> e, l, r;
    return match(ex)(
        pattern | as<int>(i)                   = i,
        pattern | asNegDs(some(e))             = [&]{ return -eval(*e); },
        pattern | asAddDs(some(l), some(r))    = [&]{ return eval(*l) + eval(*r); },
        // Optimize multiplication by 0.
        pattern | asMulDs(some(as<int>(0)), _) = 0,
        pattern | asMulDs(_, some(as<int>(0))) = 0,
        pattern | asMulDs(some(l), some(r))    = [&]{ return eval(*l) * eval(*r); },
        pattern | _                            = -1
    );
}

Terminate from Inspect

In P1371R3:

enum class Op { Add, Sub, Mul, Div };
Op parseOp(Parser& parser) {
    return inspect (parser.consumeToken()) {
        '+' => Op::Add;
        '-' => Op::Sub;
        '*' => Op::Mul;
        '/' => Op::Div;
        token => !{
            std::cerr << "Unexpected: " << token;
            std::terminate();
        }
    };
}
enum class Op { Add, Sub, Mul, Div };
Op parseOp(Parser& parser) {
    Id<char> token;
    return match(parser.consumeToken())(
        pattern | '+' = Op::Add,
        pattern | '-' = Op::Sub,
        pattern | '*' = Op::Mul,
        pattern | '/' = Op::Div,
        pattern | token = [&]{
            std::cerr << "Unexpected: " << *token;
            std::terminate();
            return Op::Add;
        }
    );
}

Wildcard Pattern

In P1371R3:

int v = /* ... */;
inspect (v) {
    __ => { std::cout << "ignored"; }
// ˆˆ wildcard pattern
};

In match(it):

int v = /* ... */;
match(v) ( 
    pattern | _ = [&]{ std::cout << "ignored"; }
    //      ˆ wildcard pattern
);

Identifier Pattern

In P1371R3:

int v = /* ... */;
inspect (v) {
    x => { std::cout << x; }
//  ˆ identifier pattern
};

In match(it):

int v = /* ... */;
match(v)( 
    pattern | x = [&]{ std::cout << *x; }
//          ˆ identifier pattern
);

Expression Pattern

In P1371R3:

int v = /* ... */;
inspect (v){
    0 => { std::cout << "got zero"; }
    1 => { std::cout << "got one"; }
//  ˆ expression pattern
};

In match(it):

int v = /* ... */;
match(v)( 
    pattern | 0 = []{ std::cout << "got zero"; },
    pattern | 1 = []{ std::cout << "got one"; }
//          ˆ expression pattern
);

In P1371R3:

int v = /* ... */;
enum class Color { Red, Green, Blue };
Color color = /* ... */;
inspect (color){
    Color::Red => // ...
    Color::Green => // ...
    Color::Blue => // ...
// ˆˆˆˆˆˆˆˆˆˆˆ expression pattern
};

In match(it):

int v = /* ... */;
enum class Color { Red, Green, Blue };
Color color = /* ... */;
match(color)( 
    pattern | Color::Red = // ...
    pattern | Color::Green = // ...
    pattern | Color::Blue = // ...
// ˆˆˆˆˆˆˆˆˆˆˆ expression pattern
);

In P1371R3: By default, an identifier is an Identifier Pattern.

static constexpr int zero = 0, one = 1;
int v = 42;
inspect (v) {
    zero => { std::cout << zero; }
//  ˆˆˆˆ identifier pattern
};
// prints: 42

In match(it): By default, an identifier is an expression pattern. Only Id variables are considered identifier patterns.

static constexpr int zero = 0, one = 1;
int v = 42;
match(v) {
    pattern | zero = [&]{ std::cout << zero; }
//          ˆˆˆˆ expression pattern
};
// prints nothing. no match.

Structured Binding Pattern

In P1371R3:

std::pair<int, int> p = /* ... */;
inspect (p) { 
    [0, 0] => { std::cout << "on origin"; }
    [0, y] => { std::cout << "on y-axis"; }
//      ˆ identifier pattern
    [x, 0] => { std::cout << "on x-axis"; }
//      ˆ expression pattern
    [x, y] => { std::cout << x << ',' << y; }
//  ˆˆˆˆˆˆ structured binding pattern
 };

In match(it):

std::pair<int, int> p = /* ... */;
Id<int> x, y;
match(p) (  
    pattern | ds(0, 0) = []{ std::cout << "on origin"; },
    pattern | ds(0, y) = []{ std::cout << "on y-axis"; },
//                ˆ identifier pattern
    pattern | ds(x, 0) = []{ std::cout << "on x-axis"; },
//                ˆ expression pattern
    pattern | ds(x, y) = [&]{ std::cout << *x << ',' << *y; },
//            ˆˆˆˆˆˆ structured binding pattern
);

In P1371R3:

struct Player { std::string name; int hitpoints; int coins; };
void get_hint(const Player& p){
    inspect (p) {
        [.hitpoints: 1] => { std::cout << "You're almost destroyed. Give up!\n"; }
        [.hitpoints: 10, .coins: 10] => { std::cout << "I need the hints from you!\n"; }
        [.coins: 10] => { std::cout << "Get more hitpoints!\n"; }
        [.hitpoints: 10] => { std::cout << "Get more ammo!\n"; }
        [.name: n] => {
            if (n != "The Bruce Dickenson") {
                std::cout << "Get more hitpoints and ammo!\n";
            } else {
                std::cout << "More cowbell!\n";
            }
        }
    };
}

In match(it):

struct Player { std::string name; int hitpoints; int coins; };
void get_hint(const Player& p){
    using P = Player;
    Id<std::string> n;
    match (p) ( 
        pattern | app(&P::hitpoints, 1) =
            [&]{ std::cout << "You're almost destroyed. Give up!\n"; },
        pattern | and_(app(&P::hitpoints, 10), app(&P::coins, 10)) =
            [&]{ std::cout << "I need the hints from you!\n"; },
        pattern | app(&P::coins, 10) =
            [&]{ std::cout << "Get more hitpoints!\n"; },
        pattern | app(&P::hitpoints, 10) =
            [&]{ std::cout << "Get more ammo!\n"; },
        pattern | app(&P::name, n) =
            [&]{
                if (*n != "The Bruce Dickenson") {
                    std::cout << "Get more hitpoints and ammo!\n";
                } else {
                    std::cout << "More cowbell!\n";
                }
            }
    );
}

Case Pattern

In P1371R3:

enum Color { Red, Green, Blue };
Color color = /* ... */;
inspect (color) {
    case Red => // ...
    case Green => // ...
//       ˆˆˆˆˆ id-expression
    case Blue => // ...
//  ˆˆˆˆˆˆˆˆˆ case pattern
};

In match(it):

enum Color { Red, Green, Blue };
Color color = /* ... */;
match(color) ( 
    pattern | Red = // ...
    pattern | Green = // ...
//          ˆˆˆˆˆ id-expression
    pattern | Blue => // ...
//  ˆˆˆˆˆˆˆˆˆ^^^^ case pattern
);

In P1371R3:

static constexpr int zero = 0;
int v = /* ... */;
inspect (v) {
    case zero => { std::cout << "got zero"; }
//       ˆˆˆˆ id-expression
    case 1 => { std::cout << "got one"; }
//       ˆ expression pattern
    case 2 => { std::cout << "got two"; }
//  ˆˆˆˆˆˆ case pattern
};

In match(it):

static constexpr int zero = 0;
int v = /* ... */;
match (v) ( 
    pattern | zero = [&] { std::cout << "got zero"; },
//          ˆˆˆˆ id-expression
    pattern | 1 = [&] { std::cout << "got one"; },
//          ˆ expression pattern or called case pattern
    pattern | 2 = [&] { std::cout << "got two"; }
//          ˆ expression pattern or called case pattern
);

In P1371R3:

static constexpr int zero = 0, one = 1;
std::pair<int, int> p = /* ... */

inspect (p) {
    [case zero, case one] => {
//        ˆˆˆˆ       ˆˆˆ id-expression
        std::cout << zero << ' ' << one;
//      Note that    ˆˆˆˆ and       ˆˆˆ are id-expressions
//      that refer to the `static constexpr` variables.
    }
};

In match(it):

static constexpr int zero = 0, one = 1;
std::pair<int, int> p = /* ... */

match(p) ( 
    pattern | ds(zero, one) = [&]( 
//             ˆˆˆˆ  ˆˆˆ id-expression
        std::cout << zero << ' ' << one;
//      Note that    ˆˆˆˆ and       ˆˆˆ are id-expressions
//      that refer to the `static constexpr` variables.
    )
);

Dereference Pattern

In P1371R3:

struct Node {
    int value;
    std::unique_ptr<Node> lhs, rhs;
};

void print_leftmost(const Node& node) {
    inspect (node) {
        [.value: v, .lhs: nullptr] => { std::cout << v << '\n'; }
        [.lhs: (*!) l] => { print_leftmost(l); }
//             ˆˆˆˆ dereference pattern
    };
}

In match(it):

struct Node {
    int value;
    std::unique_ptr<Node> lhs, rhs;
};

void print_leftmost(const Node& node) {
    auto deref = [](auto&& e) { return *e; };
    Id<int> v;
    Id<Node> l;

    match(node) ( 
        pattern | and_(app(&Node::value, v), app(&Node::lhs, nullptr)) = [&]{ std::cout << *v << '\n'; },
        // pattern | app(&Node::lhs, *_, l) = [&]{ print_leftmost(*l); },
        pattern | app(&Node::lhs, app(deref, l)) = [&]{ print_leftmost(*l); }
//             ˆˆˆˆ dereference pattern
    );
}

Extractor Pattern

In P1371R3:

template <typename T>
struct Is {
    template <typename Arg>
    Arg&& extract(Arg&& arg) const {
        static_assert(std::is_same_v<T, std::remove_cvref_t<Arg>>);
        return std::forward<Arg>(arg);
    }
};
template <typename T>
inline constexpr Is<T> is;
// P0480: `auto&& [std::string s, int i] = f();`
inspect (f()) {
    [(is<std::string>!) s, (is<int>!) i] => // ...
    // ˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆ ˆˆˆˆˆˆˆˆˆˆˆˆ extractor pattern
};

In match(it):

template <typename T>
struct Is {
    template <typename Arg>
    Arg&& operator()(Arg&& arg) const {
        static_assert(std::is_same_v<T, std::remove_cvref_t<Arg>>);
        return std::forward<Arg>(arg);
    }
};

template <typename T>
inline constexpr Is<T> is;
// P0480: `auto&& [std::string s, int i] = f();`
Id<std::string> s;
Id<int> i;
match (f()) ( 
    pattern | ds(app(is<std::string>, s), app(is<int>, i)) = // ...
);

In P1371R3:

struct Email {
    std::optional<std::array<std::string_view, 2>>
    try_extract(std::string_view sv) const;
};
inline constexpr Email email;
struct PhoneNumber {
    std::optional<std::array<std::string_view, 3>>
    try_extract(std::string_view sv) const;
};
inline constexpr PhoneNumber phone_number;
inspect (s) {
    (email?) [address, domain] => { std::cout << "got an email"; }
    (phone_number?) ["415", __, __] => { std::cout << "got a San Francisco phone number"; }
//  ˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆ extractor pattern
};

In match(it):

struct Email {
    std::optional<std::array<std::string_view, 2>>
    operator()(std::string_view sv) const;
};
inline constexpr Email email;
struct PhoneNumber {
    std::optional<std::array<std::string_view, 3>>
    operator()(std::string_view sv) const;
};
inline constexpr PhoneNumber phone_number;
Id<std::string_view> address, domain;
match (s) ( 
    pattern | app(email, some(ds(address, domain))) = [&]{ std::cout << "got an email"; },
    pattern | app(phone_number, some(ds("415", _, _))) = [&]{ std::cout << "got a San Francisco phone number"; }
//  ˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆ extractor pattern
);

Pattern Guard

In P1371R3:

inspect (p) {
    [x, y] if (test(x, y)) => { std::cout << x << ',' << y << " passed"; }
//         ˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆ pattern guard
};

In match(it):

Id<X> x;
Id<Y> y;
match(p) ( 
    pattern | ds(x, y) | when([&]{test(*x, *y)}) = [&]{ std::cout << *x << ',' << *y << " passed"; }
//                    ˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆˆ pattern guard
);

Predicate-based Discriminator

struct String {
  enum Storage { Local, Remote };

  int size;
  union {
    char local[32];
    struct { char *ptr; int unused_allocated_space; } remote;
  };

  // Predicate-based discriminator derived from `size`.
  Storage index() const { return size > sizeof(local) ? Remote : Local; }

  // Opt into Variant-Like protocol.
  template <Storage S>
  auto &&get() {
    if constexpr (S == Local) return local;
    else if constexpr (S == Remote) return remote;
  }

  char *data();
};

In P1371R3:

namespace std {
  // Opt into Variant-Like protocol.

  template <>
  struct variant_size<String> : std::integral_constant<std::size_t, 2> {};

  template <>
  struct variant_alternative<String::Local, String> {
    using type = decltype(String::local);
  };

  template <>
  struct variant_alternative<String::Remote, String> {
    using type = decltype(String::remote);
  };
}
char* String::data() {
  return inspect (*this) {
    <Local> l => l;
    <Remote> r => r.ptr;
  };
}

In match(it): We need get_if instead of get.

// Opt into Variant-Like protocol.
template <String::Storage S>
auto String::get_if()
{
  if constexpr (S == Local) return index() == Local ? &local : nullptr;
  else if constexpr (S == Remote) return index() == Remote ? &remote : nullptr;
}

template <String::Storage S>
const auto asEnum = [](auto&& pat)
{
  using namespace matchit;
  return app([](auto&& x) { return x.template get_if<S>(); }, some(pat));
};

char* String::data() {
  using namespace matchit;
  Id<char*> l;
  Id<std::decay_t<decltype(remote)>> r;
  return match(*this) ( 
    pattern | asEnum<Local>(l)  = l,
    pattern | asEnum<Remote>(r) = [&]{ return (*r).ptr; }
  );
}

Alternatively, we can specialize CustomAsPointer and use as directly.

“Closed” Class Hierarchy

struct Shape { enum Kind { Circle, Rectangle } kind; };
struct Circle : Shape {
  Circle(int radius) : Shape{Shape::Kind::Circle}, radius(radius) {}
  int radius;
};

struct Rectangle : Shape {
  Rectangle(int width, int height)
    : Shape{Shape::Kind::Rectangle}, width(width), height(height) {}
  int width, height;
};

namespace std {
template <>
struct variant_size<Shape> : std::integral_constant<std::size_t, 2> {};

template <>
struct variant_alternative<Shape::Circle, Shape> { using type = Circle; };
template <>
struct variant_alternative<Shape::Rectangle, Shape> { using type = Rectangle; }; }

Shape::Kind index(const Shape& shape) { return shape.kind; }

template <Kind K>
auto&& get(const Shape& shape) {
return static_cast<const std::variant_alternative_t<K, Shape>&>(shape); }

In P1371R3:

int get_area(const Shape& shape) {
  return inspect (shape) {
    <Circle> c => 3.14 * c.radius * c.radius;
    <Rectangle> r => r.width * r.height;
  };
}

In match(it):

int get_area(const Shape& shape) {
  Id<Circle> c;
  Id<Rectangle> r;
  return match (shape) ( 
    pattern | as<Circle>(c)    = [&] { return 3.14 * (*c).radius * (*c).radius; },
    pattern | as<Rectangle>(r) = [&] { return r.width * r.height; }
  );
}

Matcher: any_of

In P1371R3:

template <typename... Ts>
struct any_of : std::tuple<Ts...> {
  using tuple::tuple;
  template <typename U>
  bool match(const U& u) const {
    return std::apply([&](const auto&... xs)
    {
      return (... || xs == u);
    },
    *this);
  }
};

int fib(int n) {
  return inspect (n) {
    x if (x < 0) => 0;
    any_of{1,2} => n; //1|2
    x => fib(x - 1) + fib(x - 2);
  };
}

In match(it):

int fib(int n) {
  Id<int> x;
  return match (n) ( 
    pattern | (_ < 0)  = 0,
    pattern | or_(1,2) = n, //1|2
    pattern | x        = [&] { return fib(*x - 1) + fib(*x - 2); }
  );
}

Matcher: within

In P1371R3:

struct within {
  int first, last;
  bool match(int n) const
  {
    return first <= n && n <= last;
  }
};

inspect (n) {
  within{1, 10} => { // 1..10
    std::cout << n << " is in [1, 10].";
  }
  __ => {
    std::cout << n << " is not in [1, 10].";
  }
};

In match(it):

constexpr auto within = [](auto const &first, auto const &last)
{
    // the following one has memory issue since it creates temporary unarys and capture them via reference when constructing new unarys.
    // return first <= _ && _ <= last;
    return meet([&] (auto&& v) { return first <= v && v <= last; });
};

match (n) ( 
  pattern | within(1, 10) = [&] { // 1..10
    std::cout << n << " is in [1, 10].";
  },
  pattern | _ = [&] {
    std::cout << n << " is not in [1, 10].";
  }
);

Extractor: both

In P1371R3:

struct Both {
  template <typename U>
  std::pair<U&&, U&&> extract(U&& u) const {
    return {std::forward<U>(u), std::forward<U>(u)};
  }
};
inline constexpr Both both;

inspect (v) {
  (both!) [[x, 0], [0, y]] => // ...
};

In match(it):

Id<int> x, y;
match (v) (
  pattern | and_(ds(x, 0), ds(0, y)) = // ...
);

Extractor: at

In P1371R3:

inline constexpr at = both;

inspect (v) {
  <Point> (at!) [p, [x, y]] => // ... // ...
};

In match(it):

Id<Point> p;
Id<int> x, y;
match (v) ( 
  pattern | as<Point>(p.at(ds(x, y))) => // ... // ...
);

Red-black Tree Rebalancing

enum Color { Red, Black };
template <typename T>
struct Node {
  void balance();
  Color color;
  std::shared_ptr<Node> lhs;
  T value;
  std::shared_ptr<Node> rhs;
};

In P1371R3:

template <typename T>
void Node<T>::balance() {
  *this = inspect (*this) {
    // left-left case
    [case Black, (*?) [case Red, (*?) [case Red, a, x, b], y, c], z, d]
      => Node{Red, std::make_shared<Node>(Black, a, x, b),
                   y,
                   std::make_shared<Node>(Black, c, z, d)};
    [case Black, (*?) [case Red, a, x, (*?) [case Red, b, y, c]], z, d] // left-right case
      => Node{Red, std::make_shared<Node>(Black, a, x, b),
                   y,
                   std::make_shared<Node>(Black, c, z, d)};
    [case Black, a, x, (*?) [case Red, (*?) [case Red, b, y, c], z, d]] // right-left case
      => Node{Red, std::make_shared<Node>(Black, a, x, b),
                   y,
                   std::make_shared<Node>(Black, c, z, d)};
    [case Black, a, x, (*?) [case Red, b, y, (*?) [case Red, c, z, d]]] // right-right case
    => Node{Red, std::make_shared<Node>(Black, a, x, b),
                   y,
                   std::make_shared<Node>(Black, c, z, d)};
    self => self; // do nothing
  };
}

In match(it):

template <typename T>
void Node<T>::balance() {
    using namespace matchit;

    constexpr auto dsN = [](auto&&color, auto&& lhs, auto&& value, auto&& rhs)
    {
        return and_(
            app(&Node<T>::color, color),
            app(&Node<T>::lhs, lhs),
            app(&Node<T>::value, value),
            app(&Node<T>::rhs, rhs)
        );
    };

  Id<std::shared_ptr<Node<T>>> a, b, c, d;
  Id<T> x, y, z;
  Id<Node> self;
  *this = match (*this) ( 
    pattern | dsN(Black, some(dsN(Red, some(dsN(Red, a, x, b )), y, c )), z, d) // left-left case
      = [&] { return Node{Red, std::make_shared<Node>(Black, *a, *x, *b),
                   *y,
                   std::make_shared<Node>(Black, *c, *z, *d)}; },
    pattern | dsN(Black, some(dsN(Red, a, x, some(dsN(Red, b, y, c )))), z, d ) // left-right case
      = [&] { return Node{Red, std::make_shared<Node>(Black, *a, *x, *b),
                   *y,
                   std::make_shared<Node>(Black, *c, *z, *d)}; },
    pattern | dsN(Black, a, x, some(dsN(Red, some(dsN(Red, b, y, c )), z, d))) // right-left case
      = [&] { return Node{Red, std::make_shared<Node>(Black, *a, *x, *b),
                   *y,
                   std::make_shared<Node>(Black, *c, *z, *d)}; },
    pattern | dsN(Black, a, x, some(dsN(Red, b, y, some(dsN(Red, c, z, d))))) // right-right case
      = [&] { return Node{Red, std::make_shared<Node>(Black, *a, *x, *b),
                   *y,
                   std::make_shared<Node>(Black, *c, *z, *d)}; },
    pattern | self = self // do nothing
  );
}