Two Phase Lookup - Explanation Needed

Two phase lookup - explanation needed

Templates are compiled (at least) twice:

1. Without Instantiation the template code itself is checked for syntax.
   
   Eg: Any syntax errors such as ; etc.

2. At the time of instantiation(when the exact type is known), the template code is checked again to ensure all calls are valid for that particular type.
   
   Eg: The template might in turn call to functions which might not be present for that particular type.

This is called as Two Phase Lookup.

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.

Conditional operator's return type and two-phase lookup

Using the latest version of the C++ standard Currently n4582.

In section 14.6 (p10) it says the name is bound at the point of declaration if the name is not dependent on a template parameter. If it depends on a template parameter this is defined in section 14.6.2.

Section 14.6.2.2 goes on to say an expression is type dependent if any subexpression is type dependent.

Now since the call to f() is dependent on its parameter. You look at the parameter type to see if it is depending on the type. The parameter is False<T>::value ? d : d. Here the first conditional is depending on the type T.

Therefore we conclude that the call is bound at the point of instantiation not declaration. And therefore should bind to: void f(Derived &) { std::cout << "f(Derived&)\n"; }

Thus g++ has the more accurate implementation.

14.6 Name resolution [temp.res]

Para 10:

If a name does not depend on a template-parameter (as defined in 14.6.2), a declaration (or set of declarations) for that name shall be in scope at the point where the name appears in the template definition; the name is bound to the declaration (or declarations) found at that point and this binding is not affected by declarations that are visible at the point of instantiation.

14.6.2.2 Type-dependent expressions [temp.dep.expr]

Except as described below, an expression is type-dependent if any subexpression is type-dependent.

What exactly is broken with Microsoft Visual C++'s two-phase template instantiation?

I'll just copy an example from my "notebook"

int foo(void*);

template<typename T> struct S {
  S() { int i = foo(0); }
  // A standard-compliant compiler is supposed to 
  // resolve the 'foo(0)' call here (i.e. early) and 
  // bind it to 'foo(void*)'
};

void foo(int);

int main() {
  S<int> s;
  // VS2005 will resolve the 'foo(0)' call here (i.e. 
  // late, during instantiation of 'S::S()') and
  // bind it to 'foo(int)', reporting an error in the 
  // initialization of 'i'
}

The above code is supposed to compile in a standard C++ compiler. However, MSVC (2005 as well as 2010 Express) will report an error because of incorrect implementation of two-phase lookup.

---

And if you look closer, the issue is actually two-layered. At the surface, it is the obvious fact that Microsoft's compiler fails to perform early (first phase) lookup for a non-dependent expression foo(0). But what it does after that does not really behave as a proper implementation of the second lookup phase.

The language specification clearly states that during the second lookup phase only ADL-nominated namespaces get extended with additional declarations accumulated between the point of definition and point of instantiation. Meanwhile, non-ADL lookup (i.e. ordinary unqualified name lookup) is not extended by the second phase - it still sees those and only those declarations that were visible at the first phase.

That means that in the above example the compiler is not supposed to see void foo(int) at the second phase either. In other words, the MSVC's behavior cannot be described by a mere "MSVC postpones all lookup till the second phase". What MSVC implements is not a proper implementation of the second phase either.

To better illustrate the issue, consider the following example

namespace N {
  struct S {};
}

void bar(void *) {}

template <typename T> void foo(T *t) {
  bar(t);
}

void bar(N::S *s) {}

int main() {
  N::S s;
  foo(&s);
}

Note that even though bar(t) call inside the template definition is a dependent expression resolved at the second lookup phase, it should still resolve to void bar(void *). In this case ADL does not help the compiler to find void bar(N::S *s), while the regular unqualified lookup is not supposed to get "extended" by the second phase and thus is not supposed to see void bar(N::S *s) either.

Yet, Microsoft's compiler resolves the call to void bar(N::S *s). This is incorrect.

The problem is still present in its original glory in VS2015.

Two-phase name lookup: PODs vs. custom types

Since T is a template parameter, the expression t is type-dependent and hence foo is a dependent name in the function call foo(t). [temp.dep.candidate] 14.6.4.2/1 says:

For a function call that depends on a template parameter, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2, 3.4.3) except that:

• For the part of the lookup using unqualified name lookup (3.4.1) or qualified name lookup (3.4.3), 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.

If the function name is an unqualified-id and the call would be ill-formed or would find a better match had the lookup within the associated namespaces considered all the function declarations with external linkage introduced in those namespaces in all translation units, not just considering those declarations found in the template definition and template instantiation contexts, then the program has undefined behavior.

When instantiating S<double>::foobar, T is obviously double and has no associated namespaces. So the only declarations of foo that will be found are those from the template definition context (void foo(int)) as described in the first bullet.

When instantiating S<A>::foobar, T is A. Declarations of foo from both the definition context

• void foo(int)

  and from A's associated namespace (the global namespace) are found:

• inline void foo( A ) { std::cout << "foo(A)" << std::endl; }

• inline void foo( double ) { std::cout << "foo(double)" << std::endl; }

Clearly void foo(A) is the best match.

Two Phase Lookup operator issue?

Your immediate problem is that you try to pass a temporary streamAggrator object to a function which takes a streamAggrator by non-const reference. You can't bind temporary object to non-const references. The work-around for this problem is to make the output operator member of your streamAggrator: while you cannot bind a temporary to a non-const reference, you can call non-const member functions. Note that you'll also get problems with maniputors like std::flush (the issue there is that these are templates themselves and you actually need to a concrete operator to call them with to have the compiler deduce their template arguments).

Clearly, I would solve the problem properly, i.e., instead of trying to dig about an attempt to a solution which doesn't create a stream, I would create a std::streambuf do do the actual work. Your examples doesn't do anything useful, i.e., I can't really tell what you are trying to do but the code looks remarkably like trying to do something like teestream: write once but send the output to multiple destintations. I have posted corresponding stream buffers quite a few times in the post (mostly on Usenet, though, but I think, at least, once on Stackoverflow, too).

Although I don't know how to get rid of the macro to fill in the __FILE__ and the __LINE__, the actual stream formatting should probably use a stream buffer:

struct teebuf: std::streambuf {
private:
    std::streambuf* sb1;
    std::streambuf* sb2;
public:
    teebuf(std::streambuf* sb1, std::streambuf* sb2): sb1(sb1), sb2(sb2) {}
    int overflow(int c) {
        this->sb1->sputc(c);
        this->sb2->sputc(c);
        return std::char_traits<char>::not_eof(c);
    }
    int sync() {
        this->sb1->pubsync();
        this->sb2->pubsync();
    }
};
class logstream
    : std::ostream {
    std::ofstream out;
    teebuf        sbuf;
public:
    logstream()
        : out("file.log")
        , sbuf(out.rdbuf(), std::clog.rdbuf()) {
        this->init(&this->sbuf);
    }
    logstream(logstream&& other)
        : out(std::move(other.out))
        , sbuf(std::move(other.sbuf)) {
        this->init(&this->sbuf);
};

I think you can return the log stream. I don't know what your logging level is meant to do but I guess its processing was removed while preparing the question: it is probably necessary to change the implementation to take the logging level suitably into account.

Why will two-phase lookup fail to choose overloaded version of 'swap'?

Preamble with plenty of Standardese

The call to swap() in the example entails a dependent name because its arguments begin[0] and begin[1] depend on the template parameter T of the surrounding algorithm() function template. Two-phase name lookup for such dependent names is defined in the Standard as follows:

14.6.4.2 Candidate functions [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.

Unqualified lookup is defined by

3.4.1 Unqualified name lookup [basic.lookup.unqual]

1 In all the cases listed in 3.4.1, the scopes are searched for a
declaration in the order listed in each of the respective categories;
name lookup ends as soon as a declaration is found for the name. If no
declaration is found, the program is ill-formed.

and argument-dependent lookup (ADL) as

3.4.2 Argument-dependent name lookup [basic.lookup.argdep]

1 When the postfix-expression in a function call (5.2.2) is an
unqualified-id, other namespaces not considered during the usual
unqualified lookup (3.4.1) may be searched, and in those namespaces,
namespace-scope friend function or function template declarations
(11.3) not otherwise visible may be found. These modifications to the
search depend on the types of the arguments (and for template template
arguments, the namespace of the template argument).

Applying the Standard to the example

The first example calls exp::swap(). This is not a dependent name and does not require two-phase name lookup. Because the call to swap is qualified, ordinary lookup takes place which finds only the generic swap(T&, T&) function template.

The second example (what @HowardHinnant calls "the modern solution") calls swap() and also has an overload swap(A&, A&) in the same namespace as where class A lives (the global namespace in this case). Because the call to swap is unqualified, both ordinary lookup and ADL take place at the point of definition (again only finding the generic swap(T&, T&)) but another ADL takes place at the point of instantiation (i.e where exp::algorithm() is being called in main()) and this picks up swap(A&, A&) which is a better match during overload resolution.

So far so good. Now for the encore: the third example calls swap() and has a specialization template<> swap(A&, A&) inside namespace exp. The lookup is the same as in the second example, but now ADL does not pick up the template specialization because it is not in an associated namespace of class A. However, even though the specialization template<> swap(A&, A&) does not play a role during overload resolution, it is still instantiated at the point of use.

Finally, the fourth example calls swap() and has an overload template<class T> swap(A<T>&, A<T>&) inside namespace exp for template<class T> class A living in the global namespace. The lookup is the same as in the third example, and again ADL does not pick up the overload swap(A<T>&, A<T>&) because it is not in an associated namespace of the class template A<T>. And in this case, there is also no specialization that has to be instantiated at the point of use, so the generic swap(T&, T&) is being callled here.

Conclusion

Even though you are not allowed to add new overloads to namespace std, and only explicit specializations, it would not even work because of the various intricacies of two-phase name lookup.

---

Related Topics