Tip of the Week #229: Ranked Overloads for Template Metaprogramming

Originally posted as TotW #229 on February 5, 2024

By Miguel Young de la Sota and Matt Kulukundis

Updated 2024-02-20

Quicklink: abseil.io/tips/229

Warning: This is an advanced tip for folks doing template metaprogramming. In general, avoid template metaprogramming unless you have a very, very good reason. If you are reading this, it’s because you need to do some template metaprogramming or just want to learn something nifty.

One Cool Trick

Ordinarily, C++ requires every function invocation to resolve to a single “best” function or it produces an ambiguity error. The exact definition of “best” is more complex than we want to go into, but involves things like implicit conversions and type qualifiers.

In situations that would produce ambiguity errors, we can use explicit class hierarchies to force the definition of “best” to be what we prefer. This “ranked overloads” technique uses structures with a class hierarchy so they have a priority ordering and the compiler will select the highest priority method first. We’ll define a family of empty tag types Rank0, Rank1, etc., that are related by inheritance, and use those to guide the overload resolution process.¹

// Public API with good comments.
template <typename T>
size_t Size(const T& t);

// Everything below here is a working example of ranked overloads, that
// you can copy and paste to get you started!
namespace internal_size {

// Use go/ranked-overloads for dispatching.
struct Rank0 {};
struct Rank1 : Rank0 {};
struct Rank2 : Rank1 {};
struct Rank3 : Rank2 {};

template <typename T>
size_t SizeImpl(Rank3, const std::optional<T>& x) {
  return x.has_value() ? Size(*x) : 0;
}

template <typename T>
size_t SizeImpl(Rank3, const std::vector<T>& v) {
  size_t res = 0;
  for (const auto& e : v) res += Size(e);
  return res;
}

template <typename T>
size_t SizeImpl(Rank3, const T& t)
  requires std::convertible_to<T, absl::string_view>
{
  return absl::string_view{t}.size();
}

template <typename T>
size_t SizeImpl(Rank2, const T& x)
  requires requires { x.length(); }
{
  return x.length();
}

template <typename T>
size_t SizeImpl(Rank1, const T& x)
  requires requires { x.size(); }
{
  return x.size();
}

template <typename T>
size_t SizeImpl(Rank0, const T& x) { return 1; }

}  // namespace internal_size

template <typename T>
size_t Size(const T& t) {
  // Start with the highest rank, Rank3.
  return internal_size::SizeImpl(internal_size::Rank3{}, t);
}

auto i = Size("foo");                      // hits the string_view overload
auto j = Size(std::vector<int>{1, 2, 3});  // hits the vector overload
auto k = Size(17);                         // hits the lowest rank "catch all"

Note that the absl::string_view, std::optional, and std::vector overloads use Rank3. When overloads are mutually incompatible (the call can’t be ambiguous by construction), the same rank type can be used. You can think of all overloads with the same rank as being tried in parallel.

NOTE: The astute reader may wonder why the absl::string_view overload is declared as a template. Doing so ensures that no implicit conversions will take place in the signature other than the one for the rank structs. If this overload were declared with an absl::string_view parameter then the call would be ambiguous: Rank2{} -> Rank0{} would count as a conversion but const char[] to absl::string_view would also and the call would become ambiguous again.

Detailed Example

Let’s suppose we want Size(x) to return x.length(), x.size(), or 1 depending on what the passed type x implements. The naive approach does not work:

template <typename T>
size_t Size(const T& x)
  requires requires { x.length(); }
{
  return x.length();
}

template <typename T>
size_t Size(const T& x)
  requires requires { x.size(); }
{
  return x.size();
}

template <typename T>
size_t Size(const T& x) { return 1; }

auto i = Size(std::string("foo"));  // Ambiguous.

Because the size and length overloads are of equal rank, they are equally good matches for the call. Because overload resolution does not eliminate all but one candidate, the compiler declares the callsite ambiguous. There are clever tricks using variadic functions or int/long promotion to create an ordering for two options, but these do not scale to having N descending ranks of overloads.

Using ranked overloads as we’ve suggested attaches explicit ranks in the form of inheritance to specific overloads. This rank is based on the following rule: overloads with more derived classes have higher rank than overloads with less specific ones. That is, if two overloads differ by a single argument’s type, and both are bases of the argument, the type closest in the inheritance hierarchy has higher rank and is a better match.

This means we can build a tower of empty structs, each deriving from the previous, to put an explicit, numeric rank on each overload. Using this trick, we would write Size like this:

// Public API with good comments.
template <typename T>
size_t Size(const T& t);

namespace internal_size {

// Use go/ranked-overloads for dispatching.
struct Rank0 {};
struct Rank1 : Rank0 {};
struct Rank2 : Rank1 {};

template <typename T>
size_t SizeImpl(Rank2, const T& x)
  requires requires { x.length(); }
{
  return x.length();
}

template <typename T>
size_t SizeImpl(Rank1, const T& x)
  requires requires { x.size(); }
{
  return x.size();
}

template <typename T>
size_t SizeImpl(Rank0, const T& x) { return 1; }

}  // namespace internal_size

template <typename T>
size_t Size(const T& t) {
  // Start with the highest rank
  return internal_size::SizeImpl(internal_size::Rank2{}, t);
}

auto i = Size(std::string("foo"));  // 3

The overloads can now be read as an if/else chain. First we try the Rank2 overload; if substitution fails, we fall back to the next rank, Rank1, and then Rank0. Of course, this particular method will treat Size(std::string("foo")) differently from Size("foo"). This highlights some of the dangers of generic programming, though the fix is relatively straightforward: add an explicit rank to handle strings, as below.

// Public API with good comments.
template <typename T>
size_t Size(const T& t);

namespace internal_size {
// Use go/ranked-overloads for dispatching.
struct Rank0 {};
struct Rank1 : Rank0 {};
struct Rank2 : Rank1 {};
struct Rank3 : Rank2 {};

template <typename T>
size_t SizeImpl(Rank3, const T& t)
  requires std::convertible_to<T, absl::string_view>
{
  return absl::string_view{t}.size();
}

template <typename T>
size_t SizeImpl(Rank2, const T& x)
  requires requires { x.length(); }
{
  return x.length();
}

template <typename T>
size_t SizeImpl(Rank1, const T& x)
  requires requires { x.size(); }
{
  return x.size();
}

template <typename T>
size_t SizeImpl(Rank0, const T& x) { return 1; }

}  // namespace internal_size

template <typename T>
size_t Size(const T& t) {
  // Start with the highest rank
  return internal_size::SizeImpl(internal_size::Rank3{}, t);
}

auto i = Size("foo");  // 3

Now extending this to vector and optional is quite straightforward!

// Public API with good comments.
template <typename T>
size_t Size(const T& t);

namespace internal_size {
// Use go/ranked-overloads for dispatching.
struct Rank0 {};
struct Rank1 : Rank0 {};
struct Rank2 : Rank1 {};
struct Rank3 : Rank2 {};

template <typename T>
size_t SizeImpl(Rank3, const std::optional<T>& x) {
  return x.has_value() ? Size(*x) : 0;
}

template <typename T>
size_t SizeImpl(Rank3, const std::vector<T>& v) {
  size_t res = 0;
  for (const auto& e : v) res += Size(e);
  return res;
}

template <typename T>
size_t SizeImpl(Rank3, const T& t)
  requires std::convertible_to<T, absl::string_view>
{
  return absl::string_view{t}.size();
}

template <typename T>
size_t SizeImpl(Rank2, const T& x)
  requires requires { x.length(); }
{
  return x.length();
}

template <typename T>
size_t SizeImpl(Rank1, const T& x)
  requires requires { x.size(); }
{
  return x.size();
}

template <typename T>
size_t SizeImpl(Rank0, const T& x) { return 1; }

}  // namespace internal_size

template <typename T>
size_t Size(const T& t) {
  // Start with the highest rank
  return internal_size::SizeImpl(internal_size::Rank3{}, t);
}

auto i = Size("foo");                      // hits the string_view overload
auto j = Size(std::vector<int>{1, 2, 3});  // hits the vector overload
auto k = Size(17);                         // hits the lowest rank "catch all"

Parting Thoughts

Now that you have learned this awesome power, please remember to use it sparingly. As we saw with the absl::string_view overload, generic programming is subtle and can lead to unexpected results.