Template Metaprogramming Discriminated Union

Question

std::variant and boost::variant do not require the types involved to be unique, but lose some functionality when types repeat.

I'm trying to create a simple type that has a fixed number of cases (std::variant and boost::variant are variadic) and has an elimination form that approximates the look and feel of match/case.

Here's a sum type with two variants in OCaml:

type red_or_blue_int = Red of int | Blue of int

and here's a match statement:

match r_or_b with
| Red r -> string_of_int r
| Blue b -> string_of_int b

That is more or less the syntax that I'm trying to emulate.

The syntax that I did manage to get looks like this:

BinaryPatternMatch<std::string, int, int, decltype(on_left), decltype(on_right)>::match(
 &inr,
 on_left,
 on_right
 )

where on_left and on_right would typically be lambdas. I'm not sure how to set up the deduction so that the types can be omitted.

Here's the header file:

#ifndef BINARY_SUM_HPP
#define BINARY_SUM_HPP
#include <cstring>
#include <type_traits>
#include <utility>
#include <cassert>
namespace binary_sum {
/* is_decayed */
template <class T>
struct is_decayed {
 static constexpr bool value =
 std::is_same<T, typename std::decay<T>::type>::value;
};
/* end_is_decayed */
/* is_initializer_list */
template <class T>
struct is_initializer_list {
 static constexpr bool value = false;
};
template <class T>
struct is_initializer_list<std::initializer_list<T>> {
 static constexpr bool value = true;
};
/* end is_initializer_list */
template <class Left, class Right>
class Either {
public:
 virtual bool is_left() = 0;
 virtual bool is_left() const = 0;
};
template <class Left, class Right>
class InLeft : public Either<Left, Right> {
protected:
 Left left;
 template <class T>
 static constexpr bool enable_from_left_ctor =
 std::is_convertible<T, Left>::value &&
 is_decayed<T>::value &&
 (!(is_initializer_list<T>::value));
public:
 bool is_left() override {
 return true;
 }
 bool is_left() const override {
 return true;
 }
 template <
 class T,
 class = typename std::enable_if<enable_from_left_ctor<T>>::type
 >
 InLeft(T&& t) : left(t) {}
 InLeft(InLeft<Left, Right>&& t) : left(std::move(t.left)) {}
 InLeft(const InLeft<Left, Right>& t) : left(t.left) {}
};
template <class Left, class Right>
class InRight : public Either<Left, Right> {
protected:
 Right right;
 template <class T>
 static constexpr bool enable_from_right_ctor =
 std::is_convertible<T, Right>::value &&
 is_decayed<T>::value &&
 (!(is_initializer_list<T>::value));
public:
 bool is_left() override {
 return false;
 }
 bool is_left() const override {
 return false;
 }
 template <
 class T,
 class = typename std::enable_if<enable_from_right_ctor<T>>::type
 >
 InRight(T&& t) : right(t) {}
 InRight(InRight<Left, Right>&& t) : right(t.right) {}
 InRight(const InRight<Left, Right>& t) : right(t.right) {}
};
template <class Res, class Left, class Right, class LeftBranch, class RightBranch>
struct BinaryPatternMatch {
 static Res match(const Either<Left, Right> *e, LeftBranch lb, RightBranch rb) {
 assert(e != nullptr);
 if (e->is_left()) {
 return lb(*(static_cast<const InLeft<Left, Right> *>(e)));
 } else {
 return rb(*(static_cast<const InRight<Left, Right> *>(e)));
 }
 }
};
};
#endif

And here's the corresponding (minimal) test suite:

// binary sum
#include <gtest/gtest.h>
#include "binary_sum.hpp"
#include <string>
#define UNUSED(x) \
 ((void)(x))
using namespace binary_sum;
TEST(BinarySum, InLeftConstr1) {
 InLeft<int, int> inl(4.0);
 ASSERT_EQ(inl.is_left(), true);
 auto on_left = [](const InLeft<int, int>& x) {
 UNUSED(x);
 return std::string("LEFT");
 };
 auto on_right = [](const InRight<int, int>& x) {
 UNUSED(x);
 return std::string("RIGHT");
 };
 std::string patres(
 BinaryPatternMatch<std::string, int, int, decltype(on_left), decltype(on_right)>::match(
 &inl,
 on_left,
 on_right
 )
 );
 ASSERT_STREQ(
 "LEFT",
 patres.c_str()
 );
}
TEST(BinarySum, InLeftConstr2) {
 InLeft<int, int> inl{4.0};
 ASSERT_EQ(inl.is_left(), true);
}
TEST(BinarySum, InRight1) {
 InRight<int, int> inr(4.0);
 ASSERT_EQ(inr.is_left(), false);
 auto on_left = [](const InLeft<int, int>& x) {
 UNUSED(x);
 return std::string("LEFT");
 };
 auto on_right = [](const InRight<int, int>& x) {
 UNUSED(x);
 return std::string("RIGHT");
 };
 std::string patres(
 BinaryPatternMatch<std::string, int, int, decltype(on_left), decltype(on_right)>::match(
 &inr,
 on_left,
 on_right
 )
 );
 ASSERT_STREQ(
 "RIGHT",
 patres.c_str()
 );
}

The project was build using two Makefiles, one handling gtest and one for the main project. They aren't terrible idiomatic, CMake would probably be a better choice here. They aren't really the main subject of the review, but are here for the sake of completeness/reproducibility.

# Makefile
CC ?= clang
CXX ?= clang++
# our values come first, so they can be overridden
CFLAGS ?=
CPPFLAGS := -Igtest/include $(CPPFLAGS)
CXXFLAGS := -std=c++14 -g -O2 -Wall -Werror -Wextra -fsanitize=address $(CXXFLAGS)
LDFLAGS := -fsanitize=address -L. -lgtest -lgtest_main -lpthread $(LDFLAGS)
# ugly, ugly rule. call ourselves with the libgtest in order
# to prevent the dependency from appearing in $^
binary_sum: binary_sum.cpp.o
 $(MAKE) libgtest.a
 $(MAKE) libgtest_main.a
 $(CXX) $(CPPFLAGS) $(CXXFLAGS) $(LDFLAGS) -o $@ $^
%.cpp.o : %.cpp $(wildcard *.hpp)
 $(CXX) $(CPPFLAGS) -c $(CXXFLAGS) -o $@ $<
clean:
 $(RM) $(wildcard *.cpp.o) binary_sum
 $(MAKE) -f gtest.mak clean
libgtest.a:
 $(MAKE) -f gtest.mak $@
libgtest_main.a:
 $(MAKE) -f gtest.mak $@

and for building gtest and depositing its artifacts in the local directory.

# gtest.mak
GTEST_SRC ?= /usr/src/gtest
GTEST_INCLUDE ?= /usr/include/gtest
CPPFLAGS := -isystem -I$(dirname $(GTEST_HEADERS)) -I$(GTEST_SRC) $(CPPFLAGS)
CXXFLAGS := -g -Wall -Wextra $(CXXFLAGS)
# specifically override link-time options
LDFLAGS :=
GTEST_HEADERS ?= $(wildcard $(GTEST_INCLUDE)/*.h) $(wildcard $(GTEST_INCLUDE)/internal/*.h)
GTEST_SRCS ?= $(wildcard $(GTEST_SRC)/*.cc) $(wildcard $(GTEST_SRC)/*.h)
gtest-all.o : $(GTEST_SRCS) $(GTEST_HEADERS)
 $(CXX) $(CPPFLAGS) -c $(CXXFLAGS) -o $@ $(GTEST_SRC)/src/gtest-all.cc
gtest_main.o : $(GTEST_SRCS) $(GTEST_HEADERS)
 $(CXX) $(CPPFLAGS) -c $(CXXFLAGS) -o $@ $(GTEST_SRC)/src/gtest_main.cc
libgtest.a : gtest-all.o
 $(AR) $(ARFLAGS) $@ $^
libgtest_main.a : gtest-all.o gtest_main.o
 $(AR) $(ARFLAGS) $@ $^
clean:
 $(RM) gtest-all.o gtest_main.o libgtest.a libgtest_main.a

• Incomputable: IIRC, std::variant can have multiple equal types, but accessing them is only allowed through std::get with index specialization.
• Greg Nisbet: @Incomputable, you are absolutely correct. Some functionality like std::holds_alternative is ill-formed if the type appears more than once, so a std::variant with repeating types has less functionality, but nothing stops you from creating one.
• Incomputable: I actually worked on a paper that involved pattern matching in C++. We couldn't get a nice syntax because return type deduction in lambdas is inconvenient for such a case.
• Quuxplusone: (For all I know, Incomputable could be Michael Park, but...) if you haven't seen MPark.Patterns it is totally worth a look at.

Answer 1

The way to fix your template deduction is: You have a function you're calling with certain arguments that you want to deduce the types of, right? So make that function into a template! That is, take your current:

template <class Res, class Left, class Right, class LeftBranch, class RightBranch>
struct BinaryPatternMatch {
 static Res match(const Either<Left, Right> *e, LeftBranch lb, RightBranch rb) {
 assert(e != nullptr);
 if (e->is_left()) {
 return lb(*(static_cast<const InLeft<Left, Right> *>(e)));
 } else {
 return rb(*(static_cast<const InRight<Left, Right> *>(e)));
 }
 }
};

and rewrite it so that the function is a template:

namespace BinaryPatternMatch {
 template <class Res, class Left, class Right, class LeftBranch, class RightBranch>
 Res match(const Either<Left, Right> *e, LeftBranch lb, RightBranch rb) {
 assert(e != nullptr);
 if (e->is_left()) {
 return lb(*(static_cast<const InLeft<Left, Right> *>(e)));
 } else {
 return rb(*(static_cast<const InRight<Left, Right> *>(e)));
 }
 }
};

This immediately lets you rewrite your test cases as e.g.

std::string patres(
 BinaryPatternMatch::match<std::string, int, int, decltype(on_left), decltype(on_right)>(
 &inr,
 on_left,
 on_right
 )
);

and then you can drop any explicit parameters that are deducible:

std::string patres(
 BinaryPatternMatch::match<std::string>(
 &inr,
 on_left,
 on_right
 )
);

The final step would be to provide template parameter Res with a default value of decltype(lb(*(static_cast<const InLeft<Left, Right> *>(e)))) — of course using std::declval<LeftBranch>() in place of lb, and so on.

---

Why do you want your lambdas to take e.g. const InLeft<int, int>& x instead of just int x? It seems to me that the lambda shouldn't care that the int it's receiving is a "left int"; all it needs to care about is the actual integer value. The only reason I can think of to tag the lambda with the "leftness" of its parameter type would be if you were going to actually use that information for overload resolution. That is, it would be nice to make this kind of thing work:

int result1 = 
 BinaryPatternMatch::match(
 &inr,
 [](const Left<int>& x) { return x + 1; },
 [](const Right<int>& x) { return x + 2; }
 )
);
int result2 = 
 BinaryPatternMatch::match(
 &inr,
 [](const Right<int>& x) { return x + 2; },
 [](const Left<int>& x) { return x + 1; }
 )
);
assert(result1 == result2);

But I don't advise trying to make that work, because it would fall flat on its face when confronted with the perfectly reasonable code

int result2 = 
 BinaryPatternMatch::match(
 &inr,
 [](const auto& x) { /* Don't make me write out long types! */ }
 ...
 )
);

---

Speaking of passing lambda arguments in-line... notice that your test cases are testing only the situation where the lambda arguments are lvalues (e.g. on_left). You don't have any tests for the more expected situation where the lambda arguments are prvalues (e.g. [](Left<int>) { }). You should definitely have some tests for that.

The closer your tests resemble real life, the fewer bugs you'll have — and you might even discover some new usage patterns that end up informing your API design! (For example, you might discover that Left<int> x would be a much more convenient parameter declaration than const InLeft<int, int>& x... and then think about how to implement it.)

---

Speaking of which, you have no tests for Either<A,B> at all! That's surely a problem. Once you try using Either, you might realize that there's no good way to create an Either on the stack, and no way to dynamically reassign an Either from "left" to "right" without doing a new heap allocation.

If you're doing this for real code, instead of as a [[reinventing-the-wheel]] exercise, you should probably stop and go back to std::variant, where you can already do things like

template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> auto overload(Ts... ts) { return overloaded<Ts...>{ts...}; }
template<class T> struct Left { T value; };
template<class T> struct Right { T value; };
using Either = std::variant<Left<int>, Right<int>>;
Either e = Left<int>{42};
std::string result = std::visit(overload(
 [](Left<int> x) { return "left " + std::to_string(x.value); },
 [](Right<int> x) { return "right " + std::to_string(x.value); }
), e);

That's the sort of syntax you're competing with when you try to roll your own pattern-matching.