Name Lookups in C++ Templates

Name lookups in C++ templates

The problem is that templates are processed in two passes (according to the standard, VS does otherwise). In the first pass, before the type substitution, everything that does not depend on the template arguments is looked up and checked. Dependent names are then left to resolve in the second pass, once the type has been substituted.

Now, in the first pass there is nothing that indicates that next is dependent on template arguments, and thus it needs to resolve before type substitution. Now, because the base type is templated on the template argument of your current template, the compiler cannot look into it (it might be specialized for some types, and without knowing what type T we are instantiating the template with, we cannot know which specialization to use, i.e. the base depends on T and we are checking before knowing T).

The trick of adding this-> turns next into a dependent name, and that in turn means that lookup is delayed until the second pass, where T is known, and because T is known, List<T> is also known and can be looked up into.

EDIT: One important detail missing in the wording of the answer above is that second phase lookup (after type substitution) will only add functions found during argument dependent lookup. That is, if next was a free function in a namespace associated with T it would be found, but it is a member on the base, which is not visible for ADL on T.

Lookup of dependent names in C++ template instantiation

tl;dr Foo<int> doesn't invoke any ADL, but Foo<X> would (where X is a class type).

First of all, in this code foobar is a dependent name because of (C++14/N3936) [temp.dep]/1

In an expression of the form:
postfix-expression ( expression-list opt )
where the postfix-expression is an unqualified-id, the unqualified-id denotes a dependent name if [...]
any of the expressions in the expression-list is a type-dependent expression (14.6.2.2), or

and t is a dependent name because it is part of a declaration T t where T is a template parameter and thus a dependent type.

Moving onto dependent name resolution, there is [temp.dep.res]/1 which introduces the fact that names can be both looked up in the definition context, and the instantiation context, and defines where the instantiation context is. I have omitted that for brevity, but in this example template class Foo<int>; is the point of instantiation.

The next bit is [temp.dep.candidate]/1:

For a function call where the postfix-expression is a dependent name, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2) except that:
For the part of the lookup using unqualified name lookup (3.4.1), only function declarations from the template definition context are found.
For the part of the lookup using associated namespaces (3.4.2), only function declarations found in either the template definition context or the template instantiation context are found.

Those last two parts are the "two phases" of two-phase lookup. (Note - this section changed in wording from C++11 to C++14, but the effect in the same).

In the first phase, 3.4.1, no names are found for foobar.

So we move onto the second phase. The actual places that names are looked up as described in 3.4.2. The text is long but the here are two of the relevant rules:

If T is a fundamental type, its associated sets of namespaces and classes are both empty.
If T is a class type (including unions), its associated classes are: the class itself; the class of which it is a member, if any; and its direct and indirect base classes. Its associated namespaces are the innermost enclosing namespaces of its associated classes. [...]

So when you instantiate Foo<int>, then the second phase of lookup does not introduce any additional namespaces to search.

However, if you change your example to have struct X {}; and then change int to X everywhere, then the code does compile. This is because of the latter bullet point: ADL for an argument of class type does search the enclosing namespace of that class (which is the global namespace now), however ADL for an argument of built-in type does not search the global namespace.

Two phase name lookup for C++ templates - Why?

They could. This is the way most early implementations of templates
worked, and is still the way the Microsoft compiler worked. It was felt
(in the committee) that this was too error prone; it made it too easy to
accidentally hijack a name, with the instantiation in one translation
unit picking up a local name, rather than the desired global symbol. (A
typical translation unit will consist of a sequence of #includes,
declaring the names that everyone should see, followed by implementation
code. At the point of instantiation, everything preceding the point of
instantation is visible, including implementation code.)

The final decision was to classify the symbols in a template into two
categories: dependent and non-dependent, and to insist that the
non-dependent symbols be resolved at the point of definition of the
template, to reduce the risk of them accidentally being bound to some
local implementation symbols. Coupled with the requirement to specify
typename and template when appropriate for dependent symbols, this
also allows parsing and some error checking at the point of definition
of the template, rather than only when the template is instantiated.

Name lookup in template base: why do we add this-

But the second phase lookup invokes only ADL, which does not consider member functions, does it?

It does not. However ADL adds to the lookup set, it does not comprise all of it. Also, the idea you are paraphrasing here applies to a postfix-expression in postfix-expression(args), when said postfix-expression is an unqualified-id.

[temp.dep]

1 ... In an expression of the form:
postfix-expression ( expression-list_opt )
where the postfix-expression is an unqualified-id, the unqualified-id
denotes a dependent name if

[... specific conditions ...]

If an operand of an operator is a type-dependent expression, the
operator also denotes a dependent name. Such names are unbound and are
looked up at the point of the template instantiation ([temp.point]) in
both the context of the template definition and the context of the
point of instantiation.

So if you had there foo() instead, lookup would not consider members, and would instead try only free functions, both at the point of definition and instantiation (where ADL can add to the lookup set, assuming we had a dependent expression).

But for this->foo (I omitted the call intentionally, to discuss the postfix-expression), we have class member access. And here other paragraphs apply:

[temp.dep.type]

5 A name is a member of the current instantiation if it is

[...]

An id-expression denoting the member in a class member access expression for which the type of the object expression is the current instantiation, and the id-expression, when looked up, refers to at least one member of a class that is the current instantiation or a non-dependent base class thereof. [ Note: If no such member is found, and the current instantiation has any dependent base classes, then the id-expression is a member of an unknown specialization; see below. — end note ]

6 A name is a member of an unknown specialization if it is

[...]

An id-expression denoting the member in a class member access expression in which either

the type of the object expression is the current instantiation, the current instantiation has at least one dependent base class, and name
lookup of the id-expression does not find a member of a class that is
the current instantiation or a non-dependent base class thereof; or

7 Similarly, if the id-expression in a class member access expression for which the type of the object expression is the current instantiation does not refer to a member of the current instantiation or a member of an unknown specialization, the program is ill-formed even if the template containing the member access expression is not instantiated; no diagnostic required.

These bullets tell us what lookup to perform when this->foo is encountered. It looks up members only. In our case, we have a non-dependent base class in the current instantiation, so that's where the member is to be found, unambiguously.

Having found the member function, the postfix-expression this->foo denotes a callable, and that is how the function call is resolved.

Trying to understand templates and name lookup

I believe these essentially boil down to [temp.inst]/2 (emphasis mine):

The implicit instantiation of a class template specialization causes the implicit instantiation of the declarations, but not of the definitions, default arguments, or noexcept-specifiers of the class member functions, member classes, scoped member enumerations, static data members, member templates, and friends; […]

and [temp.inst]/9

An implementation shall not implicitly instantiate […] a static data member of a class template […] unless such instantiation is required.

The wording in the standard concerning implicit template instantiation leaves many details open to interpretation. In general, it would seem to me that you simply cannot rely on parts of a template not being instantiated unless the specification explicitly says so. Thus:

Snippet #1

Q. Why does this code compile? Aren't we instantiating A when inheriting from B? There is no VD in B, so shouldn't the compiler throw an error here?

You are instantiating A<B>. But instantiating A<B> only instantiates the declarations, not the definitions of its static data members. VB is never used in a way that would require a definition to exist. The compiler should accept this code.

Snippet #2

Q. Why does it compile with gcc9/why doesn't it compile with clang9?

As pointed out by Jarod42, the declaration of AB contains a placeholder type. It would seem to me that the wording of the standard is not really clear on what is supposed to happen here. Does the instantiation of the declaration of a static data member that contains a placeholder type trigger placeholder type deduction and, thus, constitute a use that requires the definition of the static data member? I can't find wording in the standard that would clearly say either yes or no to that. Thus, I would say that both interpretations are equally valid here and, thus, GCC and clang are both right…

Snippet #3

Q. If struct B is incomplete here then why is it not incomplete in snippet #2?

A class type is only complete at the point where you reach the closing } of the class-specifier [class.mem]/6. Thus, B is incomplete during the implicit instantiation of A<B> in all your snippets. It's just that this was irrelevant for Snippet #1. In Snippet #2, clang did give you an error No member named AD in B as a result. Similar to the case of Snippet #2, I can't find wording on when exactly member alias declarations would be instantiated. However, unlike for the definition of static data members, there is no wording in place to explicitly prevent the instantiation of member alias declarations during implicit instantiation of a class template. Thus, I would say that the behavior of both GCC and clang is a valid interpretation of the standard in this case…

stragety of the name lookup about full specialization of function?

Your program has undefined behaviour, because you define the explicit specialization of WithTemplate<double> after it has been implicitly instantiated through the call WithTemplate(1.1). Explicit specializations must appear before any use of them that would cause instantiation - see e.g. http://en.cppreference.com/w/cpp/language/template_specialization.

So there's no point trying to reconcile the behaviour with what the standard says; the standard explicitly says nothing about what should happen here.

where's the relevant rule for phase two name lookup of template instantiation in the current standard

In other words, these rules mean that only ADL is used to perform in phase two lookup.

This is the wrong conclusion to draw from the given specification quotes. You seem to be confusing two different concepts.

The first concept is what is commonly called "two-phase lookup": the fact that when a template gets parsed, names which are dependent on template parameters cannot be looked up at parse time. They can only be lookup up at instantiation time. There are two phases of lookup: one for non-dependent names, and one for dependent names.

The second concept is just name lookup, which has two scopes of names to search: regular unqualified lookup (defined in [basic.lookup.unqual]) and argument-dependent lookup (defined in [basic.lookup.argdep]). Unqualified lookup searches in the scope of the code itself, while ADL searches in the scope of the namespace of a function's arguments.

Both phases of template name lookup use both of these scopes. To be clear, dependent name lookup also does unqualified lookup. This is why one of the bullet points you quoted said "for the part of the lookup using unqualified name lookup... ". If dependent name lookup didn't use the rules for unqualified name lookup, it wouldn't have mentioned them.

Now, dependent name lookup does restrict what the candidate names are compared to the regular rules. But it doesn't restrict it to just ADL; it does both scopes of lookup.

These restrictions used to be specified in [temp.dep.candidate]/1, as you pointed out. But they got moved around a bit.

For the unqualified lookup part, the new [temp.dep.candidate]/1 covers that as you quoted it, because it says "usual lookup rules from the template definition context". This specifies the context of the unqualified lookup as being the template's definition only.

Note that the second bullet point also says to look in that scope, so it covers part of that.

The rest of the second bullet point is covered by [basic.lookup.argdep]/4.5:

If the lookup is for a dependent name ([temp.dep], [temp.dep.candidate]), any declaration D in N is visible if D would be visible to qualified name lookup ([namespace.qual]) at any point in the instantiation context ([module.context]) of the lookup, unless D is declared in another translation unit, attached to the global module, and is either discarded ([module.global.frag]) or has internal linkage.

This expands the lookup to include the "instantiation context", which largely matches the C++17 text (though with module-based modifications).

c++: the context of an unqualified name lookup in a template

The look-up depends on whether it is a dependent name or not. Since your function call depends on the template argument type T (through being called using the object t of this type), it is a dependent name.

Non-dependent names are just looked up in the context where the template is defined. Anything relating to the actual instantiation is not taken into consideration: Since the name is determined as not depending on the template argument, it wouldn't make sense to take the instantiation into account. This is phase I look-up.

Dependent function names are looked up taking the instantiation into account. This uses all arguments and determines associated namespaces to look up functions in these associated namespace only. For built-in types, the associated namespace added is the global namespace. For other types, the associated namespaces added are the namespace they live in plus all enclosing namespace. In addition, the associated namespace of things visible from the class definition are added: the associated namespaces of base classes, for templates the namespaces of the template arguments, etc. This is phase II look-up and also called argument dependent look-up (I think the terms are not entirely identical and the details are not as easy as described above, of course).

In the code you quoted, the do_run() function in the global scope is, obviously, found for lib::details::runner<domain::mystruct> as it is in the global namespace. It would also be found if it were moved to domain. The do_run() method in namespace lib::details is not found in an instantiation lib::details::runner<int>, however: the associated namespaces for int are only the global namespace but the function isn't there and it isn't looked up until instantiation because it is a dependent name.

That said, my understanding is that MSVC++ doesn't implement two-phase name look-up the way it is specified but I don't know in which ways it deviates.

Name Lookups in C++ Templates