A C++11 Name-Lookup Problem: a Long-Term Solution and a Temporary Work-Around

Save to:
Instapaper Pocket Readability

A C++11 Name-Lookup Problem: a Long-Term Solution and a Temporary Work-Around

by Eric Niebler

[This article has been changed since it was first published. New information from the standardization committee, which is working to fix the issue, is included.]

[Disclaimer: This is an advanced article.]

Both beginner programmers and experienced library developers got new tools when C++11 came out. As a library developer, I was particularly excited by variadic templates, an advanced feature that makes it possible to write a function that takes an arbitrary number of arguments. As it turns out, the nature of the language feature, together with the existing name lookup rules of C++, can steer you down a dark alley of frustration. This article sheds some light on the issue and shows a light at the end of the tunnel in the form of a language simplification coming in C++14. Until then, there is a workaround. But first, a word about variadic templates.

Imagine you're trying to write a sum() function that takes an arbitrary number of arguments and adds them all together. In pseudo-code, you want something like this:

// pseudo-code
auto sum( t ) { return t; }
auto sum( t, ...u ) { return t + sum( u... ); }

You have two overloads: one that takes a single argument and returns it; and the other that takes multiple arguments and adds the first to the resulting of summing the rest. Simple enough, right? With variadic templates, this isn't too hard, although the syntax takes some getting used to. Let's assume we're summing ints for now:

// real code
int sum( int i )
{
  return i;
}

template< typename ...Ints >
int sum( int i, Ints ...is )
{
  return i + sum( is... );
}

OK, that wasn't so bad. It's a little strange that we had to parameterize all the arguments after the first. We would have preferred a signature like "int sum(int i, int... is)". Variadic templates don't let us do that, but it's not a huge deal.

The other thing we notice is that variadic templates can only ever expand into a comma-separated list of things. Above, we expand is... into the (comma-separated) argument list of a recursive invocation of sum(). If we could expand the argument pack into a list of things separated with '+', then we could have done all this in one shot. Instead, we're forced by the nature of variadic templates to implement sum() recursively. This may not seem like a big deal right now, but is.

Let's check to see that our sum() function works like we expect:

int i = sum( 1 );       // OK, i == 1
int j = sum( 1, 2 );    // OK, j == 3
int k = sum( 1, 2, 3 ); // OK, k == 6

Now we're feeling bold, and we'd like to generalize. Maybe we want to sum longs, or even concatenate std::strings! We need to make two changes: replace int with a template parameter, and automatically deduce the result type of the addition. We want to use type deduction so that if we, say, add an int and a long, the return type is long as it should be. C++11 makes this possible as well, although again the syntax takes some getting used to:

template< typename T >
T sum( T t )
{
  return t;
}

template< typename T, typename ...Us >
auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
{
  return t + sum( us... );
}

Above, we use decltype to deduce the return type, and we use the new trailing return type declaration syntax. The code duplication in the trailing return type declaration is a code smell, but we can live with it for now. (FWIW, the standardization committee smells it too, and wants to clean this up. Read to the end for a glimpse of the smell-free future of C++.) Let's give it a test drive:

auto i = sum( 1 );                                     // OK, i == 1
auto j = sum( 1, 2 );                                  // OK, i == 3
auto greeting = sum( std::string("hello "), "world" ); // Cool! greeting == "hello world"
auto k = sum( 1, 2, 3 );                               // ERROR! Doesn't compile.

The last line gives us the following error on Clang:

>  main.cpp:25:14: error: no matching function for call to 'sum'
>      auto k = sum( 1, 2, 3 ); // ERROR! Doesn't compile.
>               ^~~
>  main.cpp:16:6: note: candidate template ignored: substitution
>  failure [with T = int, Us = <int, int>]: call to function
>  'sum' that is neither visible in the template definition nor
>  found by argument-dependent lookup
>  auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
>       ^                                     ~~~
>  main.cpp:11:3: note: candidate function template not viable:
>  requires single argument 't', but 3 arguments were provided
>  T sum( T t )
>    ^
>  1 error generated.

What's going on here? Calls to sum() work for one argument and two arguments, but fail for three. In the error message, we see that Clang really tried to call the variadic overload of sum() but failed because "'sum' ... is neither visible in the template definition nor found by argument-dependent lookup." Huh?

I'll skip to the chase and tell you what's going on (though you might take a moment to figure it out for yourself before reading further). Look again at the definition of the variadic sum() overload:

template< typename T, typename ...Us >
auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
{
  return t + sum( us... );
}

sum() appears twice, once in the function declaration and once in the function body. It's the one in the function declaration that's causing the problem. Consider that the above is (roughly) equivalent to the following:

template< typename T, typename ...Us >
decltype( T() + sum( Us()... ) ) sum( T t, Us ...us )
{
  return t + sum( us... );
}

The main difference is that we moved the return type from the back to the front, but this makes it a little more clear that in the return type the second sum() overload hasn't been seen yet! Even in the trailing return type formulation, the compiler pretends like it hasn't seen the second overload of sum() yet. And if it hasn't seen it, it can't call it. Picky, picky.

Name Lookup for Dummies

Name lookup happens in two phases. Let's just consider what happens in the case of the non-qualified function call in the return type of sum(). The compiler builds a set of overloads by adding a dash of functions from lookup phase 1 and then another dash from lookup phase 2. In phase 1, which happens when sum() is first parsed, functions with the right name that are in scope are tossed in the overload bucket. In our case, that's the single-argument overload of sum(), since that's the only one that is currently in scope. This phase happens before the argument types are known. Phase 2 is the argument-dependent lookup (ADL) phase and happens when the argument types are known; we check the associated namespaces of the arguments and look for any sum() overloads in those namespaces. None are found, because the arguments are of type int which has no associated namespaces. Bummer, our bucket only has only one overload of sum() in it, and it's not the one we need.

If you want to see something interesting about the way ADL works, try this. Define "struct String : std::string {};" at global scope. Now do this:

auto k = sum( "", String(), "" ); // OK!

Why does it compile when one of the arguments is a String? Because now ADL is forced to look in String's associated namespaces. Since String is defined in the global scope, ADL must check the global scope during the phase 2, and presto! there's another overload of sum() hiding in plain sight.

What's curious about our case is that we're trying to use a function in the declaration of that same function. There's just no way to get a function in scope until after its declaration, so trying to get phase 1 lookup to find it is a lost cause.

Recall what we said earlier about variadic templates: recursive algorithms are pretty much the only way to get non-trivial things done with them. There's no way around it. If the return type depends on the type returned by the recursive invocation -- and it often does -- we will run into this name lookup problem. Every time. The committee is already on its way with a language simplification that will make this problem go away (more about that below). For now, we have to find a workaround. Help us, phase 2 lookup. You're our only hope.

Relax, It's Just a Phase

How do we get name lookup to cool its jets and wait for phase 2? Let's back up a second and ask ourselves why lookup is done in two phases in the first place. When the compiler first sees the definition of a function template, some things are known and some aren't. For instance, the name of the function is known, but not the types of the arguments. Anything that depends on the template parameters is called, er, dependent. Name lookup in dependent types and dependent expressions happens during phase 2. So, in order to make the sum() function call resolve correctly, we need to make it depend on a template parameter.

Once again skipping ahead a bit, here is the hackish workaround that I've found. Explanation to follow.

namespace detail
{
  // The implementation of sum() is in a function object,
  // which is really just a holder for overloads.
  struct sum_impl
  {
    template< typename T >
    T operator()( T t ) const
    {
      return t;
    }

    // Sneaky trick below to make the function call lookup
    // happen in phase 2 instead of phase 1:
    template< typename T, typename ...Us, typename Impl = sum_impl >
    auto operator()( T t, Us ...us ) const -> decltype( t + Impl()( us... ) )
    {
      return t + Impl()( us... );
    }
  };
}

constexpr detail::sum_impl sum{};

In the above code, it looks like we simply moved the implementation of the sum() function into a sum_impl function object. But look closely, because there's more going on here than at first glance. The magic happens here:

template< typename T, typename ...Us, typename Impl = sum_impl >
// ----------------------- MAGIC HERE ^^^^^^^^^^^^^^^^^^^^^^^^
auto operator()( T t, Us ...us ) const -> decltype( t + Impl()( us... ) )

The "typename Impl = sum_impl" is a default function template parameter, new in C++11. If you don't specify it explicitly, Impl defaults to sum_impl. We won't specify it explicitly, but when the compiler first sees this code (in phase 1), it doesn't know that. Instead, when the compiler sees this...

decltype( t + Impl()( us... ) )

... the compiler must be patient and wait until phase 2, when it knows what Impl is, before it can resolve the function call. And that's precisely the point.

Sum-mary

With the above trick, our sum() function now compiles for three or more arguments. In short, when the compiler isn't finding the thing it should be finding, and you're yelling at the computer, "BUT IT'S RIGHT THERE!!!", pause and consider that maybe you too have been bitten by the phases of name lookup. Try the default function template parameter trick to make your expressions dependent.

A Look to C++14

The good news is that the problem described above is about to disappear. The C++ committee is in the process of approving return type deduction for regular functions the same way as it already works for lambdas, with the happy result that you won't even have to bother to write sum's return type at all (including not having to write decltype) because it will be deduced from the return statement in the body, at which point everything is happily in scope and Just Works.

In particular, the variadic sum() will be simply:

template< typename T, typename ...Us >
auto sum( T t, Us ...us )         // look ma, no "->"
{
  return t + sum( us... );
}

See Jason Merrill's paper N3386 for details. This proposal is on track to be adopted for C++14, and has already been implemented in the current development branch of GCC; to try it out, get the current development snapshot of GCC (or wait for GCC 4.8 in a few months) and compile with the -std=c++1y switch.

Automatic return type deduction, already becoming available in GCC and soon other compilers, is another example of how C++ continues to become simpler and remove the need for knowing about old-C++ corner cases. As simpler alternatives are added, we can just stop using the older complex ways in our new code, even while enjoying C++'s great backward compatibility for our older existing code.

Add a Comment

You must sign in or register to add a comment.

Comments (19)

10 4

Bjarne Stroustrup said on Dec 14, 2012 06:56 PM:

I wish people would use this very public forum to post information that would be of use to most C++ programmers, rather than what is most entertaining for experts. I remember one of the main things that put me off Ada was the experts showing off in public forums ostensibly suitable for novices, making me - and I suspect 99% of seriously interested non-Ada experts - feel really stupid.

There are places for an article like this. I don't think this is such a place.

Am I alone in this opinion?
5 0

Grunt said on Dec 14, 2012 09:24 PM:

@Bjarne Stroustrup

I disagree somewhat. As you said, this is a public forum, so to only appeal to novices and intermediates would disenfranchise the more advanced. Being a public forum does not imply that every article has to be applicable to the general public. Moreover, articles like this are aspirational in nature, and I am glad to have a resource in this site to highlight them.

That being said, I agree that a novice coming to this sight interested in C++ might be turned off by the complexity of such articles, so possibly tagging each article Beginner, Intermediate, and Advanced would be prudent.
7 0

Eric Niebler said on Dec 15, 2012 01:39 AM:

I actually considered posting this elsewhere. But my hope for isocpp.org is that it becomes the place where all C++ programmers, regardless of ability, could go and find something useful.
8 2

Bjarne Stroustrup said on Dec 15, 2012 06:31 AM:

I certainly didn't mean to pick on a single article or author, but I didn't know where else to air my concern. If a novice or the mythical "average programmer' come here and find the first three or four articles written by experts for experts, he'll not come back. We need to find a way to get a mix of articles and (as a previous poster mentioned) consider ways of guiding readers to what is of interest to them. There are places on the web with it is "known" that unless it has a lot of deep class hierarchies and a lot of virtual functions, it is not "real C++", so you'd better write C if you don't like such hierarchies or care about efficiency. There are places on the web where it is "known" that it isn't "real C++" unless it has a lot of complicated templates. We should make an effort for isocpp not to become such a limited and (by implication) rejecting place. C++ is expert friendly, but it can also be novice friendly, and C++11 more so at both than C++98.

So, expert, please consider using some of your skills to show how C++ can make things easy. In particular to show how to make relatively simple and common things easy.
4 0

Vittorio Romeo said on Dec 15, 2012 07:40 AM:

I think Grunt's suggestion is great. I believe isocpp.org should be the definitive resource center for any C++ programmer, beginner or expert. Just add some simple "tagging" script and the problem will most likely be solved.
0 1

Joel Lamotte said on Dec 15, 2012 11:56 AM:

I kind of agree with Bjarne on his point. The only place I find good beginner article for C++ are in books. The only place I find interesting ways of simplifying most C++ code (in particular with C++11) is in presentation videos. I suppose it is easier for expert to target other experts as audience, targeting beginners is quite a challenge. Certainly the effort would be worth on the long run to have some articles more beginner friendly. Also, there are already very expert-only blogs on C++, like cpp-next (and some other).

On a side note targeted to maintainers of this website, here is a bug: in this article, all links on commenting people's name are linked to http://about.me/ericniebler ...
Is there a better place to report this kind of issue?
0 0

Bjarne Stroustrup said on Dec 15, 2012 12:52 PM:

I guess we have all been promoted to "Niebler" grin

Tutorials are hard to write and the work is generally underrated. I'd love to see explanations of how to write good code in various areas (e.g., data bases, web services, communication, math) in addition to the usual language-oriented articles.

My Tour (two chapters available here so far, the standard library comes next month) is an attempt at a systematic and reasonably complete presentation of C++. Like all writing, it has a target audience, so there is plenty of room for tutorials at other levels and with other focuses.

PS, if you want a list of features with examples, my C++11 FAQ is here: www.stroustrup.com/C++11FAQ.html
0 0

Ben Hanson said on Dec 16, 2012 01:03 PM:

I'm glad that Eric posted this article and I particularly welcome the follow on from the editor explaining that return type deduction is coming. C++11 is still young (as anyone who uses Visual C++ as their main compiler will atest) and it's good that these kinds of issues are being addressed early.

In my view Bjarne is right to be concerned about the image C++ has as an expert only language. I believe this in spite of the fact that I also think C++ can blaze a trail in taking meta-programming to the next level.

The fact is that if C++ does not attract novices of all abilities, it will slowly become more and more niche and expert only. Is it even possibe for a single language to encompass a range of users from total novice to guru? I think C++ as a language has done a remarkable job of achieving this already over the years, but the community, maybe not so much.

I fully agree that relatively simple things should be easy and I'd like to think my lexer generator library lexertl (http://www.benhanson.net/lexertl.html) falls into this category. Of course this topic is not as mainstream as database access or simple network programming etc.

The subject of a standard C++ database access library interests me, not because I am any kind of domain expert in this area, but because I wrote a simple ODBC wrapper which we use at work. A quick google shows there are more advanced libraries out there (boost.rdb or SOCI for example). I'm interested to know if there is any progress in selecting one to be proposed for the C++ standard library. I already have some ideas for making a C++ library imune to SQL injection - does anyone know if this is already a solved problem by an existing library?
1 0

Eric Niebler said on Dec 16, 2012 11:14 PM:

I picked this topic both because I believe the issue is real and important, and because the underlying problem and its work-around are non-obvious. I was delighted to find that it's already being addressed in committee. Had I know that in advance, I would have incorporated that into my article (and may yet, if I have leave to).

Tutorials *are* hard to write! Bjarne is good at it, and I have infinite respect for talented educators.
0 0

Blair Davidson said on Dec 17, 2012 01:41 AM:

Great article. Was not aware of this as an issue. Definitely going to try this out later.

As a primary C# developer who has recently learnt C++, It is definitely more of an experts language, especially as I am learning some of the meta programming tricks ect not available in C# or .NET .But those languages dont offer generics of nearly the same magnitude of flexibility so there is bound to be some extra complexity due to the extra flexibility in the language.

I understand people find it more complex as compared to managed languages, it just is. But if one puts the time into learning the language it is not so bad. Glad to have people posting a range of articles.

Enjoying the content and videos so far, so it is definitely a win for everyone to have a place to share information on C++.

Blair
0 0

seth said on Dec 17, 2012 03:00 PM:

I'd wanted to see that alternative offered by Richard Smith and I found this: http://llvm.org/bugs/show_bug.cgi?id=13263 (see the attachment by Richard)

It is quite clever. It uses a pack expansion to produce a variadic number of _leading_ arguments, with the only named argument being the last one, which it can then return directly.

Lets see if code formatting works in these posts better than it did before:


namespace detail {
struct any { template<typename T> any(T &&) {} };
template<typename T, typename U> struct fst { typedef T type; };
template<typename ...Ts> struct select_impl {
template<typename U, typename ...Vs>
static U &&select;(typename fst<any, Ts>::type..., U &&u, Vs &&...) {
return static_cast<U&&>(u);
}
};
}

template<typename T, typename ...Ts>
auto back(T &&t, Ts &&...ts) -> decltype(detail::select_impl<Ts...>::select(static_cast<T&&>(t), static_cast<Ts&&>(ts)...)) {
return detail::select_impl<Ts...>::select(static_cast<T&&>(t), static_cast<Ts&&>(ts)...);
}
0 0

Eric Niebler said on Dec 17, 2012 05:49 PM:

Yes, that is the gcc bug report that started this. Here is a direct link to the attachment with Richard Smith's truly impressive hack: <http://llvm.org/bugs/attachment.cgi?id=8838>. You've captured the essence.
0 0

Eric Niebler said on Dec 17, 2012 06:32 PM:

Here's an attempt at presenting Richard Smith's clever back() implementation with proper formatting:


namespace detail
{
struct any { template<typename T> any(T &&) {} };

template<typename T, typename U> struct fst { typedef T type; };

template<typename ...Ts>
struct select_impl
{
template<typename U, typename ...Vs>
static U&& select(typename fst<any, Ts>::type..., U &&u, Vs &&...)
{
return static_cast<U&&>(u);
}
};
}

template<typename T, typename ...Ts>
auto back(T &&t, Ts &&...ts) ->
decltype(detail::select_impl<Ts...>::
select(static_cast<T&&>(t), static_cast<Ts&&>(ts)...))
{
return detail::select_impl<Ts...>::
select(static_cast<T&&>(t), static_cast<Ts&&>(ts)...);
}

2 2

Arthur said on Dec 19, 2012 12:35 AM:

I couldn't agree more with Mr Bjarne. The whole point is that C++ should be made easier, not "clever" so only experts can actually not even use it but read (and understand) the code. I observed very interesting (but sad) tendency when comes to C++. The tendency is to write articles in a spirit: "Look how clever I am", and I believe that the tendency should be to write articles in the spirit: "Look how easy it is". Also, I believe that there is certain amount of snobbery when it comes to C++, and some people seem to be taking pride of writing (unnecessary) very difficult code and use (unnecessarily) difficult features where simpler ways exist.

When I read books by Mr Bjarne, I feel like I'm having coffe with some very good, old friend and those difficult things are explained in such a caring and nice way that sometimes I genuinely would wish not to understand them so quickly so I could read this book/chapter again and again. Because Mr Bjarne writes with the spirit: "Look, this is really easy".

On the other hand when I've tried to read book by Mr Sutter, I simply couldn't finish it. Why? Because (almost) every chapter shouted at me: Look how dumb you are! You didn't know such an easy thing.

And the good thing (for me) is that my first book about C++ was by polish author J.Grebosz, who also wrote in a "Look, this is really easy" style. And I started to love C++ immediately and I don't see it changing - unless commitee will transform this wonderful language in some elitarian language for geeks, geniuses and professors only. If on the other hand had my first book been written by Mr Sutter I'd probably never look at C++ again.

Make C++ simple and easy to use. Don't show off how clever you are. Try to teach instead.
0 0

Cedric said on Dec 19, 2012 05:46 AM:

First of all, thanks for sharing this. Let's remember that people spend their time fir the community and they are not obliged or paid for that.

Then I agree with Bjarne. I've been a C++ developper for many years, a bit off now because it's not my job anymore. My feeling is that instead of simplifying, I see complexity rising in C++ area.

Probably will this site and blog be growing (I hope), wouln't it be possible to create categories? I'd avoid levels are no programmer I know would never admit he is only an "average developper", but categories: functionnal programming, remplates or whatever...

Just a suggestion so to frustrate neither expert nor beginners...
0 0

Arthur said on Dec 19, 2012 06:37 AM:

@Cedric
Hi,

Levels:
Beginner
Intermediate
Advanced

As you see, there is no average.
1 0

Ben Hanson said on Dec 19, 2012 08:24 AM:

@Arther: I think it's unfair to have a pop at Herb. There are far more difficult C++ books out there and his Exceptional C++ series is excellent (yes it is certainly challenging in places). Simple and common things should be easy as Bjarne mentioned, but some things have inherent complexity within them. As well as standard networking and database libraries, I am also keen to see work on the successor to C++ - the "smaller and cleaner language" Bjarne spoke of years ago. I appreciate that that is unlikely to be developed seriously any time soon, what with C++14 and C++17 now being worked on. Modules will be a huge improvement.
2 0

Arthur said on Dec 19, 2012 09:35 AM:

@Ben Hanson Hi, I didn't pop at anyone, I simply compared and contrasted two styles. One, which I prefer, and I believe is preferable in general, in life, and second one which promotes showing off, flashing etc. Obviously "not my cup of tea".

As for "Exceptional C++"? This is of course my subjective opinion but I found it, how shall I put it... "A collection of obscure, very rarely used cheap 'tricks' of questionable value for everyday use". Something in style of those silly, shallow programs which are prevelant nowadays on tely: "The most dangerous this", "The ultimate the other", "The strangest that". You cannot really learn anything of value from them - at most they entertaining (for 10 mins or so but not longer), at worst they simply waste of time/money. That's why I don't watch TV. That's why I don't like Mr Sutter's style and don't read his book(s). But that's me. I also understand that I as a person am not being liked by everyone. And that's ok. Not everyone has to like my style or me in general, nor do I have to like everyone's style or everyones either. As long as we behave in civilized manners, explain our reasoning while providing arguments, then I believe we have full rights to express our opinions.

But I know what I like and what I don't like. I like (love) Mr Bjarne's style. I don't like style of Mr Sutter.
3 0

Wang Qi said on Dec 19, 2012 11:18 PM:

I can't agree more with Bjarne. And I'm glad to see the father of C++ is trying to lead C++ to a proper direction.
Seems too many articles focused too much on the language itself. That is not a problem since C++ is so complicated.
However, the problem is, too few articles focused on how to use C++ in real world.

99% programmers come to a programming language to solve the problem in real world. They don't care how smart the language can make them be, they don't care any tricks behind the language, they only want to solve their problems.
So if the newbies find most articles are playing with language tricks than real world problems, they may feel they don't have the talent to enter the language and go away and never come back.

Experts, tricks, are fine, but we may need to open a door with lower obstacle to newbies, or average level programmers. We don't want to see C++ becomes an expert-only language, no?

[This is my first comment here. I got here from reddit post. Sorry if there is any inappropriateness.]