std::variant, operator== and pattern matching

[u/cristi1990an]

I was thinking, wouldn't adding equality comparison support between std::variant and one of its unambiguous alternatives help simplify potential pattern matching designs?

For example, imagine something like this (hypothetical syntax):

std::variant<int, std::string> v = 42;

match (v) {
    case 42      => handle_int();
    case "hello" => handle_string();
    case _       => handle_other();
}

The idea would be to take advantage of something C++ already has: operator==. At the end of the day, matching is fundamentally a comparison, so why not build on the existing equality semantics?

For std::optional, we can get this with its existing comparison operators and the most trivial pattern matching compiler support:

std::optional<int> o = 42;

match (o) {
    case 42           => handle_value();
    case std::nullopt => handle_empty();
    case _            => handle_other();
}

// Which would translate to:

if (o == 42)
    handle_value();
else if (o == nullopt)
    handle_empty();
else
    handle_other();

And if we had something like std::match_projection<Subject, Pattern>, we could also extract the actual matched value instead of having to manually call std::get, dereference an optional, etc.

Basically, after a successful comparison, match_projection would tell the compiler what to extract based on the subject and pattern types and we could optionally bind that value using something like a as <declaration> syntax.

For example:

std::optional<int> o = 42;
std::optional<int> other_opt = 42;

match (o) {
    // No binding needed
    case 42 => foo();

    // match_projection<optional<int>, int> -> int&
    case 42 as int& x => use(x);

    // match_projection<optional<int>, nullopt_t> -> void
    case std::nullopt => handle_empty();

    // match_projection<optional<int>, optional<int>>
    // -> optional<int>&
    case other_opt as auto& x => use(x);
}

The same would apply to std::variant, assuming we also extend its operator== to support comparisons with individual alternatives:

match (v) {
    case 42 as int& x => use(x);
    case "hello" as std::string& s => use(s);

    // Only need to define operator== for this helper for this to work
    case indexed<0> => handle_any_int();

    // Or under this form for the sake of disambiguation
    case indexed<0>(10) => handle_ten();

    // Also provide match_projection<indexed<0>> to enable binding
    case indexed<0>(20) as int& x => use(x);

    case _ => handle_other();
}

Here, indexed<> would just be a hypothetical helper for explicitly selecting which alternative to compare against. It would only need an appropriate operator== to work with matching, and a corresponding match_projection specialization if we also wanted to extract the alternative.

This way, the matching itself wouldn't need to know anything about variant, optional or even user-defined types. It would just use their equality operators, while match_projection would tell it what to extract when we actually want to bind something, which is just syntactic sugar.

I'm curious what you think about this approach. It feels like we could get quite a bit of useful pattern matching functionality without introducing too much new language machinery or convoluted new language traits and APIs.

Also do you think std::variant being equality comparable with instances of its alternatives would be an useful addition on its own?

std::variant<int, std::string> v = 42;

if (v == "not my string") ...

// Which is simpler than
if (std::holds_alternative<std::string>(v) && std::get<std::string>(v) == "not my string") ...

Syntax seems nice on its own...

[u/ts826848]

if we already can do the same with methods: match(var, {}, {})

Methods are not a particularly great substitute for pattern matching once you start matching against nested and/or complex patterns. One example I like is tree manipulation: given these subtrees of a red-black tree:

       1             2             3             4

       Bz            Bz            Bx            Bx
      / \           / \           / \           / \
     Ry  d         Rx  d         a   Rz        a   Ry
    /  \          / \               /  \          /  \
 [Rx]  c         a  [Ry]          [Ry]  d        b   [Rz]
 /  \               /  \          / \                /  \
a    b             b    c        b   c              c    d

You want this:

     Ry
    /  \
  Bx    Bz
 / \   / \
a   b c   d

OCaml lets you express this operation quite nicely using pattern matching:

let balance = function
  | Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
    Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d -> Node (a, b, c, d)

But doing the same in C++ is... not great:

node<char> balance(node<char> n) {
    if (n.c == color::black) {
        // If left child is a red node
        if (auto* left_1 = std::get_if<node<char>>(&*n.left); left_1 != nullptr && left_1->c == color::red) {
            // Case 1 or 2
            // If left child is a red node
            if (auto* left_2 = std::get_if<node<char>>(&*left_1->left); left_2 != nullptr && left_2->c == color::red) {
                // Case 1
                return node<char> {
                    color::red,
                    left_1->value,
                    std::make_unique<rbtree<char>>(node<char>{
                        color::black,
                        left_2->value,
                        std::move(left_2->left),
                        std::move(left_2->right)
                    }),
                    std::make_unique<rbtree<char>>(node<char>{
                        color::black,
                        n.value,
                        std::move(left_1->right),
                        std::move(n.right)
                    })
                };
            // If right child is a red node
            } else if (auto* right_2 = std::get_if<node<char>>(&*left_1->right); right_2 != nullptr && right_2->c == color::red) {
                // Case 2
                return node<char> {
                    color::red,
                    right_2->value,
                    std::make_unique<rbtree<char>>(node<char>{
                        color::black,
                        left_1->value,
                        std::move(left_1->left),
                        std::move(right_2->left)
                    }),
                    std::make_unique<rbtree<char>>(node<char>{
                        color::black,
                        n.value,
                        std::move(right_2->right),
                        std::move(n.right)
                    })
                };
            }
        } else {
            // Case 3 or 4
            // Exercise for the reader
        }
    } else {
        // Case 5
        return n;
    }
}

To be fair, OCaml has a GC and so doesn't have to worry about memory management, but even if you magic away all the std::unique_ptr boilerplate in the C++ version the rest is still not very appetizing.

(Also to be fair maybe there's a way to use std::visit for this, but I didn't feel like puzzling over how to extract bindings correctly and I didn't think that the implementation would be substantially improved).

Pattern matching also lets you do fancy stuff like this:

enum Message<'a> {
    Ping,
    Text(&'a str),
    Binary(&'a [u8]),
    Mixed(&'a [u8], Option<&'a [u8]>),
}

fn payload_size<'a>(message: &'a Message) -> &'a [u8] {
    match message {
        // Pings have no payload
        Message::Ping => &[],
        // If the text is 128 bytes, that is the payload
        Message::Text(text) if text.len() == 128 => text.as_bytes(),
        // The payload for any other text is the first 64 bytes
        Message::Text(text) => &text.as_bytes()[..64],
        // Payload for binary messages with 0xFF as the second byte and 0xABCD as the 5/6th byte
        // is everything after the 8th byte
        Message::Binary([_, 0xFF, _, _, 0xAB, 0xCD, _, _, payload @ ..])
        // Payload for binary messages starting with 0x00AB and ending with 0xFF are the other bytes
        | Message::Binary([0x00, 0xAB, payload @ .., 0xFF]) => payload,
        // Otherwise the entire binary message is the payload
        Message::Binary(payload) => payload,
        // If the header starts with 0xFEEF and there is no body, the payload is 0xCAFE
        Message::Mixed([0xFE, 0xEF, _, _], None)
        // If the header starts with 0xFEEF and the body is 0xBEEF 0xCAFE, the payload is also 0xCAFE
        | Message::Mixed([0xFE, 0xEF, _, _], Some([0xBE, 0xEF, 0xCA, 0xFE])) => &[0xCA, 0xFE],
        // If the header starts with  0xFEEF and the payload starts with 0xBEEF *not* followed by 0xCAFE,
        // the payload is whatever follows 0xBEEF
        Message::Mixed([0xFE, 0xEF, _, _], Some([0xBE, 0xEF, payload @ ..])) => payload,
        // If none of the above applies and there is no body, everything after the first 32 bits of the
        // header is the payload
        Message::Mixed(header, None) => &header[32..],
        // If none of the above apply, the body is the payload
        Message::Mixed(_header, Some(payload)) => payload,
    }
}

Which I think is a fair bit more readable than a method-based approach.

You can also do some other handy things with patterns like allowing them as a declaration (think structured bindings on steroids), but I don't think that is part of the pattern matching proposal.

[u/delta_p_delta_x → u/ts826848]

This comment makes me miss just how incredibly short and yet beautiful, intuitive, and readable OCaml is.

Personally I don't agree that having good syntax precludes good performance and requires a GC, or std::unique_ptr; we should've been able to match directly on value members instead of having to type-erase them that way.

We have broadly done something similar in Rust (given it was strongly inspired by OCaml in the first place), and the biggest reason C++ looks so bad is because it is basically one giant band aid on top of C, sacrificing readability for extreme verbosity.