How does `is_base_of` work?

Question

How does the following code work?

typedef char (&yes)[1];
typedef char (&no)[2];

template <typename B, typename D>
struct Host
{
  operator B*() const;
  operator D*();
};

template <typename B, typename D>
struct is_base_of
{
  template <typename T> 
  static yes check(D*, T);
  static no check(B*, int);

  static const bool value = sizeof(check(Host<B,D>(), int())) == sizeof(yes);
};

//Test sample
class Base {};
class Derived : private Base {};

//Expression is true.
int test[is_base_of<Base,Derived>::value && !is_base_of<Derived,Base>::value];

1. Note that B is private base. How does this work?

2. Note that operator B*() is const. Why is it important?

3. Why is template<typename T> static yes check(D*, T); better than static yes check(B*, int); ?

Note: It is reduced version (macros are removed) of boost::is_base_of. And this works on wide range of compilers.

Solution 1

If they are related

Let's for a moment assume that B is actually a base of D. Then for the call to check, both versions are viable because Host can be converted to D* and B*. It's a user defined conversion sequence as described by 13.3.3.1.2 from Host<B, D> to D* and B* respectively. For finding conversion functions that can convert the class, the following candidate functions are synthesized for the first check function according to 13.3.1.5/1

D* (Host<B, D>&)

The first conversion function isn't a candidate, because B* can't be converted to D*.

For the second function, the following candidates exist:

B* (Host<B, D> const&)
D* (Host<B, D>&)

Those are the two conversion function candidates that take the host object. The first takes it by const reference, and the second doesn't. Thus the second is a better match for the non-const *this object (the implied object argument) by 13.3.3.2/3b1sb4 and is used to convert to B* for the second check function.

If you would remove the const, we would have the following candidates

B* (Host<B, D>&)
D* (Host<B, D>&)

This would mean that we can't select by constness anymore. In an ordinary overload resolution scenario, the call would now be ambiguous because normally the return type won't participate in overload resolution. For conversion functions, however, there is a backdoor. If two conversion functions are equally good, then the return type of them decides who is best according to 13.3.3/1. Thus, if you would remove the const, then the first would be taken, because B* converts better to B* than D* to B*.

Now what user defined conversion sequence is better? The one for the second or the first check function? The rule is that user defined conversion sequences can only be compared if they use the same conversion function or constructor according to 13.3.3.2/3b2. This is exactly the case here: Both use the second conversion function. Notice that thus the const is important because it forces the compiler to take the second conversion function.

Since we can compare them - which one is better? The rule is that the better conversion from the return type of the conversion function to the destination type wins (again by 13.3.3.2/3b2). In this case, D* converts better to D* than to B*. Thus the first function is selected and we recognize the inheritance!

Notice that since we never needed to actually convert to a base class, we can thereby recognize private inheritance because whether we can convert from a D* to a B* isn't dependent on the form of inheritance according to 4.10/3

If they are not related

Now let's assume they are not related by inheritance. Thus for the first function we have the following candidates

D* (Host<B, D>&) 

And for the second we now have another set

B* (Host<B, D> const&)

Since we cannot convert D* to B* if we haven't got a inheritance relationship, we now have no common conversion function among the two user defined conversion sequences! Thus, we would be ambiguous if not for the fact that the first function is a template. Templates are second choice when there is a non-template function that is equally good according to 13.3.3/1. Thus, we select the non-template function (second one) and we recognize that there is no inheritance between B and D!

Solution 2

Let's work out how it works by looking at the steps.

Start with the sizeof(check(Host<B,D>(), int())) part. The compiler can quickly see that this check(...) is a function call expression, so it needs to do overload resolution on check. There are two candidate overloads available, template <typename T> yes check(D*, T); and no check(B*, int);. If the first is chosen, you get sizeof(yes), else sizeof(no)

Next, let's look at the overload resolution. The first overload is a template instantiation check<int> (D*, T=int) and the second candidate is check(B*, int). The actual arguments provided are Host<B,D> and int(). The second parameter clearly doesn't distinguish them; it merely served to make the first overload a template one. We'll see later why the template part is relevant.

Now look at the conversion sequences that are needed. For the first overload, we have Host<B,D>::operator D* - one user-defined conversion. For the second, the overload is trickier. We need a B*, but there are possibly two conversion sequences. One is via Host<B,D>::operator B*() const. If (and only if) B and D are related by inheritance will the conversion sequence Host<B,D>::operator D*() + D*->B* exist. Now assume D indeed inherits from B. The two conversion sequences are Host<B,D> -> Host<B,D> const -> operator B* const -> B* and Host<B,D> -> operator D* -> D* -> B*.

So, for related B and D, no check(<Host<B,D>(), int()) would ambiguous. As a result, the templated yes check<int>(D*, int) is chosen. However, if D does not inherit from B, then no check(<Host<B,D>(), int()) is not ambiguous. At this point, overload resolution cannot happen based on shortest conversion sequence. However, given equal conversion sequences, overload resolution prefers non-template functions, i.e. no check(B*, int).

You now see why it doesn't matter that the inheritance is private: that relation only serves to eliminate no check(Host<B,D>(), int()) from overload resolution before the access check happens. And you also see why the operator B* const must be const: else there's no need for the Host<B,D> -> Host<B,D> const step, no ambiguity, and no check(B*, int) would always be chosen.

Solution 3

The private bit is completely ignored by is_base_of because overload resolution occurs before accessibility checks.

You can verify this simply:

class Foo
{
public:
  void bar(int);
private:
  void bar(double);
};

int main(int argc, char* argv[])
{
  Foo foo;
  double d = 0.3;
  foo.bar(d);       // Compiler error, cannot access private member function
}

The same applies here, the fact that B is a private base does not prevent the check from taking place, it would only prevent the conversion, but we never ask for the actual conversion ;)

Solution 4

It possibly has something to do with partial ordering w.r.t. overload resolution. D* is more specialized than B* in case D derives from B.

The exact details are rather complicated. You have to figure out the precedences of various overload resolution rules. Partial ordering is one. Lengths/kinds of conversion sequences is another one. Finally, if two viable functions are deemed equally good, non-templates are chosen over function templates.

I've never needed to look up how these rules interact. But it seems partial ordering is dominating the other overload resolution rules. When D doesn't derive from B the partial ordering rules don't apply and the non-template is more attractive. When D derives from B, partial ordering kicks in and makes the function template more attractive -- as it seems.

As for inheritance being privete: the code never asks for a conversion from D* to B* which would require public inheritence.

View more solutions

Comments

[Matthieu M.]

I think it's something like that, I remember having seen an extensive discussion on the boost archives about the implementation of is_base_of and the loops the contributors went through to ensure this.

[Potatoswatter]

Sort of. No base conversion is performed at all. host is arbitrarily converted to D* or B* in the unevaluated expression. For some reason, D* is preferable over B* under certain conditions.

[Andreas Brinck]

I think the answer is in 13.3.1.1.2 but I've yet to sort out the details :)

[Matthieu M.]

My answer only explains the "why even private works" part, sellibitze's answer is certainly more complete though I am eagerly waiting for a clear explanation of the full resolution process depending on the cases.

[Alexey Malistov]

The exact details are rather complicated - that's the point. Please, explain. I do want to know.

[Alexey Malistov]

Your explanation does not account for the presence of const. If your answer is true then no const is needed. But it is not true. Remove const and trick will not work.

[sellibitze]

@Alexey: Well, I thought I pointed you into the right direction. Check out how the various overload resolution rules interact in this case. The only difference between D deriving from B and D not deriving from B with respect to the resolution of this overloading case is the partial ordering rule. Overload resolution is described in §13 of the C++ standard. You can get a draft for free: open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1804.pdf

[sellibitze]

Overload resolution spans 16 pages in that draft. I guess, if you really need to understand the rules and the interaction between them for this case you should read the complete section §13.3. I wouldn't count on getting an answer here that is 100% correct and up to your standards.

[MSalters]

Without the const the two conversion sequences for no check(B*, int) are no longer ambiguous.

[Johannes Schaub - litb]

If you leave only no check(B*, int), then for related B and D, it wouldn't be ambiguous. The compiler would unambiguously choose operator D*() to perform the conversion because it doesn't have a const. It's rather a bit in the opposite direction: If you remove the const, you introduce some sense of ambiguity, but which is resolved by the fact that operator B*() provides a superior return type which doesn't need a pointer conversion to B* like D* does.

[Johannes Schaub - litb]

please see my answer for an explanation of it if you are interested.

[Matthieu M.]

Ah! Andreas had the paragraph right, too bad he didn't give such answer :) Thanks for your time, I wish I could put favorite it.

[MSalters]

That's indeed the point: the ambiguity is between the two different conversion sequences to get a B* from the <Host<B,D>() temporary.

[Marco A.]

This is going to be my favorite answer ever... a question: have you read the whole C++ standard or are you just working in the C++ committee?? Congratulations!

[Johannes Schaub - litb]

@DavidKernin working in the C++ committe doesn't automatically make you know how C++ work :) So you definitely have to read the part of the Standard that is needed to know the details, which I have done. Haven't read all of it, so I definitely can't help with most of the Standard library or threading related questions :)

[user1289]

This is a better answer. Thanks! So, as i understood, if one function is better, but ambiguous, then another function is choosed?

[MSalters]

@GrigorApoyan: Indeed. But note that this isn't a general rule. With templates, Substitution Failure Is Not An Error (SFINAE). Early in the design of C++ is was noticed that unintended template instantiations would often be errors, which is why the SFINAE rule was introduced. This rule is now often intentionally used in situations like this.

[underscore_d]

Fantastic explanation. But it makes me wonder: at what point would the Committee accept that certain compile-time checks would be better implemented as keywords, than as - clever but highly byzantine - template acrobatics?

[Johannes Schaub - litb]

@underscore_d To be fair, the spec doesn't forbid the std:: traits to use some compiler magic so standard library implemers can use them of they like. They will avoid the template acrobatics which also helps speed up compile time and memory usage. This is true even if the interface looks like std::is_base_of<...>. It's all under the hood.

[Johannes Schaub - litb]

Of course, general libraries like boost:: need to make sure they have these intrinsics available before using them. And I have the feeling there's some kind of a "challenge accepted" mentality among them to implement things without the help of the compiler :)

[underscore_d]

@JohannesSchaub-litb Good point, I guess compiler intrinsics are nearest to what I was speculating, with how much the language resists adding new keywords! TMP can definitely be a challenge, and even fun... to a point :D