You know what’s stuck on my mind? Ever since writing my last post, it’s been the word “better.” It came up when we were talking about overload resolution and implicit conversion sequences. I explained a necessary special case of it—something about how adding const in a reference-binding is preferred against—and then strategically shut up about the rest.

void run(int (**f)());                // #1
void run(int (*const *f)() noexcept); // #2
int foo() noexcept;

int (*p)() noexcept = &foo;
run(&p); // ???

But it’s so tantalizing, isn’t it? Which one will it choose? How can we reason about this? I can see it in your eyes, sore but eager. You yearn for conversion. Well, I wasn’t going to— I— well… Alright, since you’re so insistent. Just for you. Shall we?

∗  ∗  ∗

Let’s start small and work our way up. An implicit conversion sequence is a standard conversion sequence, possibly followed by a user-defined conversion and another standard conversion sequence in the case of a class type.¹ A user-defined conversion is something like T::operator S(), which defines how to convert a T into an S. These are easy: they work exactly how we tell them to. So, it evidently suffices to understand standard conversion sequences.

Definition 1

A standard conversion sequence is a sequence of zero or one conversions from each of the following categories, in order:

1. Lvalue-to-rvalue, array-to-pointer, or function-to-pointer conversions:
   • Lvalue-to-rvalue: converts a glvalue of non-function, non-array type to a prvalue. Not particularly relevant to overload resolution, and kind of sophisticated, so we’ll mostly forget about this.
   • Array-to-pointer: converts an expression of type “array of $N$ T” or “array of unknown bound of T” to a prvalue of type “pointer to T,” applying temporary materialization conversion if the expression was a prvalue (note that GCC has a bug and won’t do this; temporary materialization is defined later).
   • Function-to-pointer: converts an lvalue function of type T to a prvalue of type “pointer to T.”
2. Integral/floating-point/boolean/pointer/pointer-to-member conversions and promotions:
   • There are a bunch of rules for converting between various integral and floating-point types that are necessary but, frankly, menial and uninteresting, so we’ll omit these too. The pointer/pointer-to-member conversions are probably things you already know.
3. Function pointer conversion: converts a prvalue of type “pointer to noexcept function” to a prvalue of type “pointer to function.”
4. Qualification conversion: unifies constness of two types somehow. Oh boy. It can’t be that bad, right? Right?

OK— OK. Uh. Hear me out.

In C++, const and volatile are often called cv-qualifiers, so called because they qualify types to form cv-qualified types. The cv-qualified versions of a cv-unqualified type T are const T, volatile T, and const volatile T. We could also consider types T which have cv-qualifiers nested inside—for example, const int** const (“const pointer to pointer to const int”) could be written alternatively as X in the following series of type aliases:

using U = const int;
using V = U*;
using W = V*;
using X = const W;

Now, a mathematically inclined reader may choose to write “const pointer to pointer to const int” as

$$cv_0~P_0~cv_1~P_1~cv_2~mathtt{U}$$

where $cv_0={mathtt{const}}$, $cv_1=emptyset$, $cv_2={mathtt{const}}$, $P_0=P_1=text{“pointer to”}$, and $mathtt{U}=mathtt{int}$. More generally, we could write any type $mathtt{T}$ (not necessarily uniquely) as

$$cv_0~P_0~cv_1~P_1~ldots~cv_{n-1}~P_{n-1}~cv_n~mathtt{U}$$

for some $nge 0$ and some type $mathtt{U}$; each $P_i$ is either “pointer to,” “array of $N_i$,” or “array of unknown size of.” For simplicity, let’s assume each $P_i$ will always be “pointer to.”

Notice that, for determining whether one type can be qualification-converted into another type (e.g., trying to convert int* to const int*), we can always drop $cv_0$ from consideration altogether—in particular, at the top level, we can always initialize a const T from a T and vice versa, and likewise we can always convert from one to the other. So, let’s forget about $cv_0$.

Since we don’t care as much about any of the $P_i$ or $mathtt{U}$—these are the “non-const-y” parts, and we’ll deal with them separately—let’s write this even more compactly as the $n$-tuple $(cv_1,cv_2,ldots,cv_n)$. The longest possible such tuple is called cv-qualification signature of $mathtt{T}$.

We’re almost there. I’m trying really hard to make the C++ standard more palatable here, so bear with me. Two types $mathtt{T1}$ and $mathtt{T2}$ are called similar if they have cv-decompositions of equal size such that each of their respective $P_i$’s are either (1) the same, or (2) one is “array of $N_i$” and the other is “array of unknown size of”; and, moreover, their $mathtt{U}$’s should agree. Basically, if the “not-const-y” parts of their cv-decompositions mostly agree, they’re called “similar.”

OK. It’s time. I’m only barely paraphrasing the standard because it’s all I can do at this point—it’s honestly worded pretty tightly. Let $mathtt{T1}$ and $mathtt{T2}$ be two types. Then, their cv-combined type $mathtt{T3}$, if it exists, is a type similar to $mathtt{T1}$ such that, for each $i>0$:

• $cv_i^3=cv_i^1cup cv_i^2$;
• if either $P_i^1$ or $P_i^2$ are “array of unknown bound of,” then so is $P_i^3$; and,
• if $cv_i^3ne cv_i^1$, $cv_i^3ne cv_i^2$, $P_i^3ne P_i^1$ or $P_1^3ne P_i^2$, then $mathtt{const}$ is added to each $cv_j^3$ for $0$.

This can be thought of as an algorithm for finding the converted type $mathtt{T3}$. If it ends up finding in the end that $mathtt{T3}=mathtt{T2}$ (up to top-level cv-qualifiers), then a prvalue of type $mathtt{T1}$ can be successfully converted to a prvalue of type $mathtt{T2}$.

Hey, that was only a little awful. It’s actually cute if you think about it for a bit. The gist is that, if the cv-qualification signature of $mathtt{T2}$ doesn’t have $mathtt{const}$ up to the last point of disagreement with $mathtt{T1}$, the conversion probably won’t work out.

I learn best when I look at a few examples, so here are two I found to be useful:

// q :: "pointer to pointer to pointer to int"
int*** q{};
// p :: "pointer to const pointer to pointer to int"
int** const* p = q;

This one compiles. The $P_i$’s and $U$ both match up, so we we’ll only focus on the cv-qualifiers. The cv-qualification signature for int*** is $a := (emptyset, emptyset, emptyset)$ while, for int** const*, it’s $b := ({mathtt{const}}, emptyset, emptyset)$. So, we determine the cv-qualification signature $c$ for the cv-combined type as follows:

1. Set $c_1 := a_1cup b_1={mathtt{const}}$. Although $a_1 ne b_1$, there are no prior sets to change (i.e., $i=1$), so just move on.
2. Set $c_2 := a_2cup b_2=emptyset$. Since $a_2 = b_2$, move on.
3. Set $c_3 := a_3cup b_3=emptyset$. Since $a_3 = b_3$, move on.

Then, $c=b=(mathtt{const}, emptyset, emptyset)$ is the cv-qualification signature for int** const*, matching $b$ exactly so that the conversion of q to the type of p succeeds.

As you might’ve come to expect by now, the story gets worse when we move one of those stars in p over:

// q :: "pointer to pointer to pointer to int"
int*** q;
// p :: "pointer to pointer const to pointer to int"
int* const** p = q;

This one kept me up at night. It actually does not compile, for a reason that’s easy to miss. Let’s go through it: the cv-qualification signature for int*** is $a := (emptyset, emptyset, emptyset)$ while, for int** const*, it’s $b := (emptyset, {mathtt{const}}, emptyset)$. So, we determine the cv-decomposition $c$ for the cv-combined type as follows:

1. Set $c_1 := a_1cup b_1=emptyset$. Since $a_1 = b_1$, move on.
2. Set $c_2 := a_2cup b_2={mathtt{const}}$. Since $a_2ne b_2$, set $c_1:=c_1cup{mathtt{const}}={mathtt{const}}$.
3. Set $c_3 := a_3cup b_3=emptyset$. Since $a_3 = b_3$, move on.

Then, $c=({mathtt{const}}, {mathtt{const}}, emptyset)ne b$, so the conversion fails and we get a compiler error which doesn’t illuminate very much about this process. Great.

What were we talking about again? Oh.

Right. I guess you might want to re-skim the beginning of this post to refresh yourself on the rest of the standard conversion stuff. Before we move on, I’ll add one kind of implicit conversion I didn’t mention that you’re probably already aware of. Temporary materialization is a conversion applied to a prvalue which initializes the prvalue-designated object and produces an xvalue denoting it. This is a cute way of extending the lifetime of a temporary: it happens in cases like the array-to-pointer conversion mentioned earlier, binding a reference to a prvalue, and so on. In general, this only extends the lifetime of the temporary until the evaluation of the originating statement is complete; one of the few exceptions to this is for reference binding:

void foo(int* arr);
using U = int[4];

foo(U{1,2,3,4}); // OK
int* ptr = U{1,2,3,4}; // dangling pointer...
const U& ref = U{1,2,3,4}; // OK

With that rotten cherry on top, let’s zoom back out to overload resolution.

While we have an idea of how to convert between types, overload resolution involves converting between many possible types—for each overload—and deciding which conversions are “better.” Recall the definitions given in the previous post:

Definition 2

In overload resolution for an expression f(E1, ..., En), a candidate function $F$ is called viable if:

• the number of arguments given “matches” the number of parameters to $F$;
• its constraints (i.e., C++20 concepts/constraints) are satisfied by the expression; and
• for each argument, there is some implicit conversion sequence that converts it to the type of the corresponding parameter.

Definition 3

Let $F$ and $G$ be two viable candidates, and let $operatorname{ICS}_i(F)$ represent the (possibly trivial) sequence of implicit conversions that converts the $i^{rm th}$ argument to the type of the $i^{rm th}$ parameter of $F$. We say $F$ is better than $G$ if, for each $i$, $operatorname{ICS}_i(F)$ is not worse than $operatorname{ICS}_i(G)$, and:

• There is some $j$ such that $operatorname{ICS}_j(F)$ is a “better” conversion sequence than $operatorname{ICS}_j(G)$; or, otherwise,
• (A list of some other things, omitted for brevity).

There’s that itch. There are so many unanswered questions. For one, we still can’t shake out why one conversion sequence might be better than another; moreover, it’s still not clear why this code shakes out the way it does:

void foo(const int&); // #1
void foo(int&);       // #2

const int x; int y;
foo(4); // #1
foo(x); // #1
foo(y); // #2

We need a rigorous notion of “better.”

Well, here’s a start: let’s say that any standard conversion sequence is always better than a user-defined conversion sequence. Moreover, we’ll say that for two user-defined conversion sequences S1 and S2 which call the same conversion function/non-explicit constructor, S1 is better than S2 if the standard conversion sequence following S1 is better than that following S2 (recall that a (possibly trivial) standard conversion sequence always follows a user-defined conversion, by definition of implicit conversion sequence). That puts user-defined conversion sequences to rest (noting that the term “better” is already itself becoming slightly overloaded), so it remains to rank the standard conversions.

We’re getting there—I can feel it. Let’s kick this off with a table ripped out of [over.ics.scs] in the standard:

As you might imagine, “exact match” is better than “promotion” which is better than “conversion,” and the rank of a conversion sequence is the lowest across the ranks of its constituent conversions. So, if it’s a fight between two conversion sequences, pick the one with the better rank. If they have the same rank, though, it gets a bit more complicated. Let S1 and S2 be standard conversion sequences of the same rank. Then:

1. If S1 is a proper subsequence of S2, choose S1.
2. If S1 and S2 are conversions between base/derived class pointers, there are a whole bunch of broadly uninteresting rules about which one’s better that you can probably mostly intuit.
3. In general, prefer binding rvalue references where possible.²
4. Prefer having function lvalues bound to lvalue references over rvalue references.³
5. If S1 and S2 are conversions from T0 to similar types T1 and T2 respectively, differing only in a qualification conversion step, and T1 is qualification-convertible to T2, then S1 is better than S2 (if T1 sits between T0 and T2, it’s “less work” to convert to T1, so we prefer S1).
6. If references are bound during S1 and S2 and the referred-to types are the same up to top-level cv-qualifiers, prefer the sequence for which the referred-to type is less qualified (i.e., avoid unnecessary cv-qualification in reference binding).

That last rule explains the overload resolution in that earlier example, and it also came up in my last post. Go figure. In any case, we now have standard conversions, hence implicit conversion sequences, and hence overload resolution as a whole. Got all that? No? Fine—this was at least a little dense, so here are some examples:

void foo(const int p); // #1
void foo(int p);       // #2
foo(5); // #1 or #2?

void run(int (*f)());                // #1
void run(int (*const f)() noexcept); // #2
int foo() noexcept;

run(foo); // #1 or #2?

// f :: "pointer to pointer to `int()`"
void run(int (**f)());                // #1
// g :: "pointer to const pointer to `int() noexcept`"
void run(int (*const *g)() noexcept); // #2
int foo() noexcept;

int (*p)() noexcept = &foo;
// &p :: "pointer to pointer to `int() noexcept`"
run(&p); // #1 or #2?

void foo(int*& p);

int arr[3];
foo(arr); // well-formed?

// p :: "pointer to pointer to const pointer to int"
void foo(int* const** p);

// a :: "pointer to array of 5 `pointer to int`"
int* (*a)[5]{};
foo(a); // well-formed?

∗  ∗  ∗

Fuck. It just works. Like a well-oiled machine. I mean, obviously it does—the compilers make it work, after all—but it’s something else to feel how it all works and to be able to reason about it more thoroughly.

…On the other hand, like, that was awful, right? Sure, you can avoid this nonsense by writing sane overloads and not nesting pointers too deeply, but it’s a little terrifying standing back and looking at this grand, winding Rube Goldberg machine that exists just to support ad hoc polymorphism—i.e, name sharing. Conversions, too, I guess, but I think there’s broad agreement right now that implicit conversions are usually something that make it easier to write incorrect code. Was it really worth it? Hard to say. It’s hard not to peer at it, though, in a morbid way, like watching some kind of wounded animal.

A closing note: the standard is very long and dense and scattered and, moreover, I am very stupid, so there’s a non-zero chance something here is wrong. If you’re smarter than me and spot any such instances, send me an email or something. As they say, the easiest way to learn is to be wrong on the internet.

❦