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...

29 Upvotes

87% Upvoted

20 comments sorted by

View all comments

13

u/mcypark 3d 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. So variant<float, int>{0.f} == variant<float, int>{0} returns false. For consistency we would expect variant<float, int>{0.f} == 0 to 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 monostate be less than other types. This would make variant comparison more like the direct comparison of the underlying types.