Thursday, January 8, 2015

Rvalue references and function overloading.

No matter how many articles get written about rvalue references, I still get the impression that many people don't understand them fully. Some belief that rvalues work differently as template parameters than they do in non-template contexts, which requires special rules in overload resolution. I intend to show how rvalues would consistently with the rest of the language. In the coarse of writing this article, I even straightened out my own misconceptions of rvalues.

I assume that the reader has some level of familiarity with rvalue references; understanding perfect forwarding helps. For either an introduction or refresher, I recommend "C++ Rvalue References Explained", a very thorough introduction and a well indexed reference.

Today, I want to break out of my normal pedagogical style into a Q&A. I will ask that the reader thinks for a moment about what they expect a code example to do, and why.

Non-template rvalue overloading.

Typically, discussion of rvalues is limited to template functions and move constructors, but consider the following code example:
void f(int) { } void f(int&) { } void f(int&&) { } int main() { f(0); // (1) int x; f(x); // (2) } 
What overload(s) of f get chosen at (1) and (2)? Please take a moment to compare (1) and (2) to each overload before continuing.

(1) is ambiguous because it can refer to f(int) and f(int&&), while (2) is ambiguous because it can be f(int) or f(int&).

The C++ standard describes a sort of "best fit" algorithm for overload resolution by first determining the viable overloads, then ranking them based on the conversions required of the arguments being passed. The highest rank, considered an "exact match," includes identity (or: "no conversion required") and considers reference binding a member of that category. Because of that, f(int), has the same rank as f(int&) and f(int&&) in overloading.
struct T { T() { } T(const T&) { } T(T&&) { } }; void f(T&) { } void f(const T&) { } void f(T&&) { } int main() { T t; T t2(t); // (1) T t3(T{}); // (2) f(t); // (3) f(T{}); // (4) }
Does this example suffer from the same ambiguity? Why or why not?

Being familiar with copy and move constructors, we know that (1) will invoke T(const T&) and that (2) will invoke T(T&&), but shouldn't there be an ambiguity because we can bind temporaries to const references? Every overload has the "exact match" rank, but the standard also defines a sub-ranking for "implicit conversion sequences", which covers reference parameters (including rvalue references) and "qualification adjustment" such as converting an int& to const int&. Given two overloads on reference parameters, the rvalue reference overload is prefered to the lvalue one, thus T(T&&) is chosen for (1) and f(T&&) for (4). (3) has a split between f(T&) and f(const T&), but the former wins because the argument, t, is not const and would require adjustment.

Note that f would be ambiguous if we had defined an f(T) overload because every other overload would have the same relative ranking. While f(T&) matches more precisely than f(const T&), they both have the same rank compared to f(T). 

Before considering the impact of rvalues on template functions, let's ponder what we already know about perfect forwarding.
template<typename T> void f(T&&) { }
We know that this function can be called on any value and might refer to it as a "universal reference", although it has more recently been redubbed "forwarding reference". Let's try to reproduce this behaviour without templates.
void f(int&&) { } void f(int& &&) { } void f(const int& &&) { }
This code is not valid. I usually like clang's diagnostics the best, but here it complains, rather mundanely, "type name declared as a reference to a reference". Gcc gives us a very nice hint about this code: "cannot declare reference to ‘int&’, which is not a typedef or a template type argument".
using ref = int&; using cref = const int&; void f(int&&) { } void f(ref&&) { } void f(cref&&) { } int main() { int x = 0; const int y = 0; f(0); // calls f(int&&) f(x); // calls f(ref&&) f(y); // calls f(cref&&) }
Neither clang nor gcc has any difficulty with this version. The above set of overloads looks fairly similar to the familiar perfect-forwarding pattern.
using rval = int&&; using rrval = rval&&; // (1) using rrrval = rrval&&; // (2) void f(rval) { } void f(rrval) { } // (3) void f(rrrval) { } // (4)
For (1) and (2), are they valid? For (3) and (4), what values would these overloads accept?

You may be surprised, but (1) and (2) are completely valid, however (3) and (4) are not. Again, the diagnostics of gcc and clang give us some good insight. They complain that f(rrval) redefines f(rval), and ditto for f(rrrval). That is to say: rval, rrval, and rrrval all refer to the same type! The same works for normal references--(int&) & is the same as int&.

While int and int&& are distinct types, the standard states that there "shall be no references to references," which includes rvalue references to references. This is one context where non-rvalues always take precedence.
using ref = int&; using rval = int&&; using T1 = ref&&; // T1 = int& using T2 = rval&; // T2 = int& 
This explains why perfect forwarding works the way it does. You see T&&, but it actually decays to the exact type of the parameter.

Rvalues in template functions:

One might consider rvalue references in the context of template functions as forwarding references, previously called universal references, because they seem to apply to every situation.
template<typename T> void f(T) { } template<typename T> void f(T&) { } template<typename T> void f(T&&) { } int main() { int x = 0; f(0); // (1) f(x); // (2) } 
Which overload of f gets called at (1) and (2)

As a rule of thumb, one might assume that f(T&&) gets chosen for both because it can be, (with T = int and T = int&, respectively) but actually the very same rules apply as the non-template version. (1) is ambiguous between f(T) or f(T&&) and (2) is ambiguous between all three overloads (again, because they all fit into the "exact match" rank).
template<typename T> void f(T&&) { }

void f(const int&) { } int main() { int x = 0; f(x); }
Which overload of f gets called? 

This time, f(T&&) gets instantiated with T = int& and f(const int&) requires requires a qualification adjustment from int& to const int&, so f(T&&) gets chosen.
template<typename T> struct X { }; template<typename T> void f(T&&) { } template<typename T> void f(X<T&&>&) { } int main() { X<int> x; X<int&> xref; f(x); // (1) f(xref); // (2) }
Which overload of f gets chosen at (1) and (2)?

It's f(T&&) for both. Sure, T&& can bind to anything, but the T in X<T&&> can only bind to actual rvalue references. They compiler does not try to fit T&& with int or int&, but looks at the whole type, X<T&&> vs X<int> and X<int&> and cannot deduce T. Ironically, if we wanted a signature that would bind to X of anything, it would have to be X<T>.

Conclusions

Many seem to believe that template rvalue references are inconsistent with normal overload resolution in C++ and find referring to rvalues in this context as "universal" or "forwarding" references as helpful in order to reason about why they work differently. I hope that through the above examples, the reader has learned something about rvalue references and the consistency of the rules surrounding them.