Overloading template functions

[mattias.nissler]

Hi!

Here is a problem I ran into at work. The following example doesn't
compile on gcc-4.1:

struct cons_end {};

template<typename U,typename V> struct cons {
U elem;
V tail;
};

template<typename U, typename V>
void foo4(U elem, V tail)
{
::foo4(tail.elem,tail.tail);
}

template<typename U>
void foo4(U elem, cons_end tail)
{
}

int main()
{
typedef cons<int,cons<int,cons_end> > tList;
tList list;
foo4(list.elem,list.tail);
}


The problem occurs in the first call to foo4 [U = int, V = cons<int,
cons_end>]. Now the compiler needs to resolve the nested call to (the
overloaded) foo4 given parameters of type int and cons_end. However,
not the template<typename U> foo4(U, cons_end) is selected, but again
the generic version, leading to the following error:

test1.cpp: In function 'void foo4(U, V) [with U = int, V = cons_end]':
test1.cpp:22: instantiated from 'void foo4(U, V) [with U = int, V =
cons<int, cons_end>]'
test1.cpp:58: instantiated from here
test1.cpp:22: error: 'struct cons_end' has no member named 'elem'
test1.cpp:22: error: 'struct cons_end' has no member named 'tail'

If I change the order of the definitions like so...

struct cons_end {};

template<typename U,typename V> struct cons {
U elem;
V tail;
};

/* N.B. THE TWO VERSIONS OF FOO4() NOW IN DIFFERENT ORDER */
template<typename U>
void foo4(U elem, cons_end tail)
{
}

template<typename U, typename V>
void foo4(U elem, V tail)
{
::foo4(tail.elem,tail.tail);
}

int main()
{
typedef cons<int,cons<int,cons_end> > tList;
tList list;
foo4(list.elem,list.tail);
}

.... the code compiles, the cons_end version of foo4 is selected.

So my question now is: Is this correct behaviour or not? What does the
standard say? If the first version is wrong, why exactly?

Thanks,

Mattias

 

[Zeppe]

Hi!

Here is a problem I ran into at work. The following example doesn't
compile on gcc-4.1:

struct cons_end {};

template<typename U,typename V> struct cons {
U elem;
V tail;
};

at least, declare the function that you want to call before calling it:

template<typename U, typename V>
void foo4(U elem, V tail)
{
::foo4(tail.elem,tail.tail);
}

you want the one argument template function to be called, but you
haven't declared it. At this point, ::foo4 refers to the only declared
(and defined) one, that is that one with two templates argument.

template<typename U>
void foo4(U elem, cons_end tail)
{
}

int main()
{
typedef cons<int,cons<int,cons_end> > tList;
tList list;
foo4(list.elem,list.tail);

return 0;

}


If I change the order of the definitions like so...
... the code compiles, the cons_end version of foo4 is selected.

because now the overloaded function is defined at the point in which is
called.

Regards,

Zeppe

 

[Sylvester Hesp]

Hi!

Here is a problem I ran into at work. The following example doesn't
compile on gcc-4.1:

struct cons_end {};

template<typename U,typename V> struct cons {
U elem;
V tail;
};

template<typename U, typename V>
void foo4(U elem, V tail)
{
::foo4(tail.elem,tail.tail);
}

template<typename U>
void foo4(U elem, cons_end tail)
{
}

int main()
{
typedef cons<int,cons<int,cons_end> > tList;
tList list;
foo4(list.elem,list.tail);
}


The problem occurs in the first call to foo4 [U = int, V = cons<int,
cons_end>]. Now the compiler needs to resolve the nested call to (the
overloaded) foo4 given parameters of type int and cons_end. However,
not the template<typename U> foo4(U, cons_end) is selected, but again
the generic version, leading to the following error:

test1.cpp: In function 'void foo4(U, V) [with U = int, V = cons_end]':
test1.cpp:22: instantiated from 'void foo4(U, V) [with U = int, V =
cons<int, cons_end>]'
test1.cpp:58: instantiated from here
test1.cpp:22: error: 'struct cons_end' has no member named 'elem'
test1.cpp:22: error: 'struct cons_end' has no member named 'tail'

[.. snap ..]

So my question now is: Is this correct behaviour or not?
Yes

What does the standard say? If the first version is wrong, why exactly?

----------
14.6.2/1
In an expression of the form:
postfix-expression ( expression-listopt )
where the postfix-expression is an identifier, the identifier denotes a
dependent name if and only if any of the expressions in the expression-list
is a type-dependent expression (14.6.2.2).
----------

and

----------
14.6.3/1
Non-dependent names used in a template definition are found using the usual
name lookup and bound at the point they are used.
----------


The function call expression in foo4 is:
::foo4(tail.elem,tail.tail);

"::foo4" is the postfix-expression here, and it's not an identifier (but a
fully qualified name). So it's not a dependent name, therefore regular name
lookup is used as with normal functions, at the point of definition.
However, if you used
foo4(tail.elem, tail.tail)
(note the omission of "::"), foo4 would be a dependent name, in which case:

----------
14.6.4
In resolving dependent names, names from the following sources are
considered:
- Declarations that are visible at the point of definition of the template.
- Declarations from namespaces associated with the types of the function
arguments both from the instantiation
context (14.6.4.1) and from the definition context.
----------

tail.tail is of type ::cons_end, thus the global namespace is searched for
the name 'foo4' at point of instantiation (in main()). In main(),
foo4(cons<T,cons_end>) is known, and because it is more specialized, that
function is called.


- Sylvester

 

[mattias.nissler]

----------
14.6.2/1
In an expression of the form:
postfix-expression ( expression-listopt )
where the postfix-expression is an identifier, the identifier denotes a
dependent name if and only if any of the expressions in the expression-list
is a type-dependent expression (14.6.2.2).
----------

and

----------
14.6.3/1
Non-dependent names used in a template definition are found using the usual
name lookup and bound at the point they are used.
----------

The function call expression in foo4 is:
::foo4(tail.elem,tail.tail);

"::foo4" is the postfix-expression here, and it's not an identifier (but a
fully qualified name). So it's not a dependent name, therefore regular name
lookup is used as with normal functions, at the point of definition.

Thanks, that clarifies a lot!

However, if you used
foo4(tail.elem, tail.tail)
(note the omission of "::"), foo4 would be a dependent name, in which case:

----------
14.6.4
In resolving dependent names, names from the following sources are
considered:
- Declarations that are visible at the point of definition of the template.
- Declarations from namespaces associated with the types of the function
arguments both from the instantiation
context (14.6.4.1) and from the definition context.
----------

tail.tail is of type ::cons_end, thus the global namespace is searched for
the name 'foo4' at point of instantiation (in main()). In main(),
foo4(cons<T,cons_end>) is known, and because it is more specialized, that
function is called.

Yeah, gcc implements that behaviour, the whole thing working without
the "::" qualifier is why I originally asked here.

Now what if I need to call, say, a function in another namespace. I
can't just write the (qualified) name, since that would make it
syntactically something that is not an identifier, right? Is there
some 'good practice' way to handle this situation? [I'm just curious,
I probably have a correct workaround for my original problem now.]

Cheers,

Mattias

 

[Zeppe]

tail.tail is of type ::cons_end, thus the global namespace is searched for
the name 'foo4' at point of instantiation (in main()). In main(),
foo4(cons<T,cons_end>) is known, and because it is more specialized, that
function is called.

testspecialization.cpp: In function ‘void foo4(U, V) [with U = int, V =
cons_end]’:
testspecialization.cpp:14: instantiated from ‘void foo4(U, V) [with U
= int, V = cons<int, cons_end>]’
testspecialization.cpp:26: instantiated from here
testspecialization.cpp:14: error: ‘struct cons_end’ has no member named
‘elem’
testspecialization.cpp:14: error: ‘struct cons_end’ has no member named
‘tail’

for g++ the istantiation of the second call to foo4 is inside foo4<U,V>.
I don't know if it is standard, but I suppose it is. A simple function
declaration works just well, and it is also quite reasonable, given that
you don't usually call a function without having declared it...

Regards,

Zeppe

 

[Sylvester Hesp]

tail.tail is of type ::cons_end, thus the global namespace is searched
for the name 'foo4' at point of instantiation (in main()). In main(),
foo4(cons<T,cons_end>) is known, and because it is more specialized, that
function is called.

testspecialization.cpp: In function ‘void foo4(U, V) [with U = int, V =
cons_end]’:
testspecialization.cpp:14: instantiated from ‘void foo4(U, V) [with U =
int, V = cons<int, cons_end>]’
testspecialization.cpp:26: instantiated from here
testspecialization.cpp:14: error: ‘struct cons_end’ has no member named
‘elem’
testspecialization.cpp:14: error: ‘struct cons_end’ has no member named
‘tail’

for g++ the istantiation of the second call to foo4 is inside foo4<U,V>.

-----------
14.6.4.1/1 For a function template specialization, a member function
template specialization, or a specialization for a member function or static
data member of a class template, if the specialization is implicitly
instantiated because it is referenced from within another template
specialization and the context from which it is referenced
depends on a template parameter, the point of instantiation of the
specialization is the point of instantiation of the enclosing
specialization. Otherwise, the point of instantiation for such a
specialization immediately follows the namespace scope declaration or
definition that refers to the specialization.
-----------

So, the point of instantiation is in main()

I don't know if it is standard, but I suppose it is. A simple function
declaration works just well, and it is also quite reasonable, given that
you don't usually call a function without having declared it...

Actually, it happens all the time:

#include <set>

class MyType
{
// whatever
};

bool operator <(MyType&, MyType&);

int main()
{
std::set<MyType> s;
s.insert(MyType);
}

std::set<T> uses std::less<T> to compare types. The (least specialized
version of) std::less<T> uses the < operator for comparison. But,
operator<(MyType&, MyType&) is declared *after* the implementation of
std::less<T> (which is defined by including <set> at the top of the
sourcefile).

Not having this kind of two-phase name lookup (14.6.4) is devestating for
the use of templates and generic programming. Luckily, compilers that do not
fully implement the two-phase name lookup (VC++ for example) do implement
the second part (lookup at point of instantiation), which is imho the most
important one.

- Sylvester

 

[Zeppe]

Actually, it happens all the time:

true, and actually the code wasn't compiling due to an error introduced
by me .

Regards,

Zeppe

 

[James Kanze]

(e-mail address removed) wrote:

at least, declare the function that you want to call before calling it:

template<typename U>
void foo4(U elem, cons_end tail);

IMHO, it is generally a good idea to declare functions before
use. For the reader, even in cases where the compiler doesn't
need it.

you want the one argument template function to be called, but you
haven't declared it. At this point, ::foo4 refers to the only declared
(and defined) one, that is that one with two templates argument.

I'm not sure; this is one of the more complicated aspects of
C++. But as I understand it, the problem is that the :: in
front of foo prevent the lookup from being dependent, so name
binding occurs at the point of definition. Since in this case,
the author probably wants dependent lookup (which takes place at
the point of instantiation), he should in any case drop the ::,
which are typically used to tell the compiler *not* to consider
anything not yet visible.

(In this particular case, I still think it would be clearer to
declare the function before use. But I'd also drop the ::,
because I think dependant name lookup for foo4 is really what is
wanted.)

return 0;

because now the overloaded function is defined at the point in which is
called.

And because that definition is also a declaration---all that is
necessary, of course, is that a declaration be visible.

It's important to realize, though, that even though the function
is a template, name lookup does NOT depend on the instantiation
types, and occurs at the point of definition of the template, if
the name isn't dependent, and that using :: is one way to ensure
that the name isn't dependent.

 

[Sylvester Hesp]

It's important to realize, though, that even though the function
is a template, name lookup does NOT depend on the instantiation
types, and occurs at the point of definition of the template, if
the name isn't dependent, and that using :: is one way to ensure
that the name isn't dependent.

using (foo)(params) is another, with a slightly different semantic
meaning (names are looked up in the currently visible scopes, rather
than in the specified namespace). That may be preferable because it
does not force you to specify the complete namespace scope, thus
improving maintainability.

- Sylvester