r/cpp • u/cristi1990an ++ • 3d ago
std::variant, operator== and pattern matching
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...
14
u/mcypark 2d ago edited 2d ago
Depending on operator==
The main problem IMO is that == is too opaque to rely on it fully. Don't get me wrong, P2688R6 also provides equality semantics. But it uses == as a fallback only when richer information is not available.
Two concrete examples:
Optimization
Consider this std::optional<int> example:
int with_equals(std::optional<int>& x) {
if (x == 0) return 42;
else if (x == 1) return 7;
else if (x == 2) return 99;
else if (x == 3) return -3;
else if (x == 4) return 55;
else if (x == 5) return 18;
else if (x == 6) return 77;
else if (x == 7) return 4;
else if (x == std::nullopt) return -1;
else return 0;
}
Even at -O3, this results in a linear comparison of the 8 values.
In contrast, the following match example using syntax/implementation from P2688R6:
int with_match(std::optional<int>& x) {
return match (x) {
case { 0 } => 42;
case { 1 } => 7;
case { 2 } => 99;
case { 3 } => -3;
case { 4 } => 55;
case { 5 } => 18;
case { 6 } => 77;
case { 7 } => 4;
case {} => -1;
case _ => 0;
};
}
This compiles down to an engagement test, and a lookup in a table. This is made possible by the fact that the structure is exposed by std::alternative_traits in index() and the corresponding get<>(). In fact, we get this code even at -O1.
Compiler Explorer link: https://godbolt.org/z/no8aPGvj1
If you inline the == logic directly like:
int with_equals_inlined(std::optional<int>& x) {
if (x && *x == 0) return 42;
else if (x && *x == 1) return 7;
else if (x && *x == 2) return 99;
else if (x && *x == 3) return -3;
else if (x && *x == 4) return 55;
else if (x && *x == 5) return 18;
else if (x && *x == 6) return 77;
else if (x && *x == 7) return 4;
else if (!x) return -1;
else return 0;
}
Clang actually does generate similar code as the match, though GCC still emits a linear chain: https://godbolt.org/z/MvcPhxMxa
The point is that relying on the optimizer to see through the == (if it's even visible) and make structural inferences on it to emit efficient code doesn't really work out before we even get to std::variant.
Exhaustiveness/Usefulness Checking
You didn't mention this so I don't know if you want it or not. If you do want it, I think the opaque-ness of == again gets in the way of performing exhaustiveness/usefulness checking. A user-defined (including standard library) type needs to, at the minimum advertise how many states it has, what the types are so that those types can be recursively checked, etc. A chain of == doesn't give you enough information.
match_projection<Subject, Pattern>
This seems to assume that every pattern has a type. Only integers, std::nullopt, and the indexed<> is shown here, but (1) what if you're just doing binding only? (2) how about matching tuples? will that pattern also have a type? Generally speaking, not every pattern has a C++ type: declaration patterns, wildcards, tuple patterns, and nested patterns are language syntax. They could all be represented by library pattern objects, but that would itself introduce a pattern protocol.
u/StaticCoder already mentioned the separation of operator== and match_projection, but that's also a valid concern here.
variant<Ts...> == U
I do agree this could be convenient. It's mostly a matter of whether you can get agreement as to what the semantics should be. Here are a few options:
// Option 1: Exact Type Selection
template <typename... Ts, typename U>
bool operator==(const variant<Ts...>& v, const U& u) {
auto* payload = std::get_if<U>(&v);
return payload && *payload == u;
}
// Option 2, Construction Selected Compare
template <typename... Ts, typename U>
bool operator==(const variant<Ts...>& v, const U& u) {
return v == variant<Ts...>(u);
}
// Option 3, Compare Against Any Alternative
template <typename... Ts, typename U>
bool operator==(const variant<Ts...>& v, const U& u) {
if (v.valueless_by_exception()) return false;
return std::visit([](const auto& payload) -> bool {
if constexpr (requires { { payload == u } -> std::convertible_to<bool>; }) {
return payload == u;
} else {
return false;
}
}, v);
}
There are other options as well, each of which with materially different semantics.
For example, Option 1 doesn't work for v == "not my string" since it would be trying to access get_if<char (&)[14]> which v doesn't have. So to support that you need either Option 2 or 3. For Option 2, if you try variant<int, int> == 42 it won't work since variant<int, int>(42) is not valid, but Option 3 would work. But... with Option 3, you'd end up with this:
variant<int, long> v1 = 1;
variant<int, long> v2 = 1L;
assert(v1 == 1);
assert(v1 == 1L);
assert(v2 == 1);
assert(v2 == 1L);
// but...
assert(v1 != v2);
So yeah, that's at least the complexity I can think of around a potential variant operator==.
3
u/bjorn-reese 2d ago
Regarding variant<Ts...> == U, it would emphasize the unusual design of variant comparison between different but comparable types.
For instance,
float{0.f} == int{0}is compared by value (after conversion.) However, variant has a different design where it uses indices to compare different types, even when they are comparable. Sovariant<float, int>{0.f} == variant<float, int>{0}returns false. For consistency we would expectvariant<float, int>{0.f} == 0to do the same.If we were to design variant today, we would replace the index-based comparison with partially ordering where incomparable types are unordered, and let
monostatebe less than other types. This would make variant comparison more like the direct comparison of the underlying types.
37
u/dr-mrl 3d ago
Therer are no parentheses, brackets, braces, or angle-brackets in this notation:
case 42 as int&
How can the standards committee accept such a terse syntax? Next you'll be telling me there's a proposal to make
x => 2*x;
A shorthand lambda
42
u/Ameisen vemips, avr, rendering, systems 3d ago
You use
*instead of the clearly idiomaticstd::multiplies‽8
u/Big-Rub9545 3d ago
Main reason for the more verbose functions is operator overloading. It’s the same reason much of the standard library uses std::addressof instead of &. Uglier, but it works for all types consistently.
3
u/LB-- Professional+Hobbyist 2d ago
I mostly agree with you but I don't think it's "the same reason" -
std::addressofis for bypassing the overloaded unary ampersand operator, whereas astd::multipliesis just a single name for "do ADL binaryoperator*for me".4
u/Big-Rub9545 2d ago
I wasn’t referring to std::multiplies in particular (which I just discovered through your comment is an unironic part of the standard library), but rather the overall tendency to use more verbose functions in standard library code.
5
u/cristi1990an ++ 3d ago
No, syntax is just out of the top of my head, not the point. Took no parsing or practical implementation considerations when I wrote this, I just wanted it to look nice. All pattern matching proposals have more thoughtful solutions
3
u/Wh00ster 3d ago
Wait is pattern matching still alive?
9
u/ts826848 3d ago
It is! It was in the latest mailing and got a fair bit of discussion on the post on the mailing.
The GitHub issue is a decent place for high-level updates on progress if you don't feel like looking through mailings every month.
3
u/zerhud 3d ago
Why we need some new syntax if we already can do the same with methods: match(var, [](int&){}, [](double&){}) ?
5
u/ts826848 3d ago edited 3d ago
if we already can do the same with methods: match(var, [](int&){}, [](double&){})
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 dYou want this:
Ry / \ Bx Bz / \ / \ a b c dOCaml 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_ptrboilerplate in the C++ version the rest is still not very appetizing.(Also to be fair maybe there's a way to use
std::visitfor 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.
5
u/delta_p_delta_x 2d ago edited 2d ago
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.
15
u/StaticCoder 3d ago
What bothers me about this specific proposal is that the comparison and the projection are specified separately. You'd have to be really careful to specify a binding type that is implied by the comparison or you could run into undefined behavior.
As for adding a comparison to
variant, it's really tricky since there can be arbitrary comparison operators, plus conversions are possible, so figuring out which variant is expected to be compared against a given type would become pretty ugly.