Template Type Dependent Name Lookup

[Keean Schupke]

Hi,

I am interested in the interaction of [temp.dep.res] and [basic.lookup.argdep]. I notice these have changed in the latest working draft. I am interested in generic programming in C++ (like in Stepanov's Elements of Programming).

The question is: Is it the intention of the standard that the following code should be possible:

template <typename T> T f(T t) {
    return g(t);
} 
int g(int x) {
    return x + 1;
}
main() {
    int x(1);
    x = f(x);
}

The template represents a concept that would usually be defined in an algorithm library, for example an algorithm that requires a semi-group. The definition of "g" represents adding the built-in type to the library concept of a semi-group (and this would naturally happen after the library is included) and finally calling the generic algorithm with an integer type, which should use the 'semi-group' functions I have defined for integer.

Regards,

Keean.

[Ville Voutilainen]

The call g(t) in f looks very much dependent to me, so I'd at least hope this
is intended to work.

[Keean Schupke]

On Tuesday, 26 June 2012 16:10:39 UTC+1, Ville Voutilainen wrote:

Hi,

quoting Jonathan Wakely:

[temp.dep.res] says dependent name resolution considers declarations visible at
the point of definition, and declarations from associated namespaces from the
instantiation context and the definition context.
[basic.lookup.argdep]/2 says "If T is a fundamental type, its associated sets
of namespaces and classes are both empty."

 

So specifically only declarations from associated namespaces are considered at the instantiation context, and for fundamental types the set of associated namespaces is empty, hence no lookup in the instantiation context can take place.

Is this the intention of these clauses, or is this an accidental consequence? I notice the latest working draft has changed the language in these clauses. Does the latest working draft of the C++ standard imply that the sample code I posted should or should not work?

Regards,

Keean Schupke. 

[Alberto Ganesh Barbati]

Yes. I can confirm that the code above is not expected to compile in C++11. For example Clang 3.0 gives the error message: "call to function 'g' that is neither visible in the template definition nor found by argument-dependent lookup"

Is this the intention of these clauses, or is this an accidental consequence? I notice the latest working draft has changed the language in these clauses. Does the latest working draft of the C++ standard imply that the sample code I posted should or should not work?

Which changes do you refer to specifically?

Ganesh

[Keean Schupke]

Hi,

Can you explain to me what technical problem requires the code not to run? I am interested in why the standard is worded to exclude this code. The standard currently allows this if the type is an enum for example:

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

enum E {e}; 
int g(E x) {

    return x + 1;
}
main() {

    E x(e);
    x = f(x);
}

This code works (according to the standard). Why are we treating one type (enum, class) differenly from others (int, float). What is the reason for treating them differently?

Cheers,

Keean.

[Alberto Ganesh Barbati]

Il giorno 27/giu/2012, alle ore 10:55, Keean Schupke ha scritto:

> Can you explain to me what technical problem requires the code not to run?

Because it doesn't compile? :-D More seriously, even "compile" is not the correct term here. It's not that code "does not run" nor that it "does not compile" but rather that the code "is ill-formed". An ill-formed program may still compile and run, but if it does, it would have an undefined behavior.

> I am interested in why the standard is worded to exclude this code. The standard currently allows this if the type is an enum for example:
>
>
> template <typename T> T f(T t) {
> return g(t);
> }
> enum E {e};
> int g(E x) {
> return x + 1;
> }
> main() {
> E x(e);
> x = f(x);
> }
>
>
> This code works (according to the standard).

Yes. This code is well-formed, because E is not a fundamental type, so it has an associated namespace (the global namespace, in this case).

> Why are we treating one type (enum, class) differenly from others (int, float). What is the reason for treating them differently?

Fundamental types do not have associated namespaces. That is the key point. So the instantiation-point lookup, which only looks in the associated namespaces, finds nothing. Frankly, I agree that it might have made more sense to have the global namespace be associated with the fundamental types. In that case, the lookup would find g() and the code would be well-formed. However, it was like this since the beginning, so I have to presume that either there is a valid reason or it was a mistake that created a precedent which couldn't be corrected for backward compatibility issues.

For example, consider the code:

class A {
public:
A(int) {}
};

int g(A) {
return 0;

}

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

int g(int x) {
return x + 1;
}

int main() {
int x(1);
std::cout << f(x) << "\n";
}

This is well-formed in C++03 and C++11 and produces the output "0". If we were to change the associated namespaces of the fundamental types to include the global namespace, the code would still be well-formed but would produce the output "2". From the point of view of the standard committee, a silent change in the behavior of a well-formed program is usually unacceptable. It may be acceptable only if the benefits significantly outweighs the potential backward compatibility issues. I don't think that's the case, here.

So my point is: I don't know why this decision was taken, but it seems anyway too late to change direction.

Ganesh

[Keean Schupke]

On Wednesday, 27 June 2012 11:05:52 UTC+1, Alberto Ganesh Barbati wrote:

Il giorno 27/giu/2012, alle ore 10:55, Keean Schupke ha scritto:

> Can you explain to me what technical problem requires the code not to run?

Because it doesn't compile? :-D More seriously, even "compile" is not the correct term here. It's not that code "does not run" nor that it "does not compile" but rather that the code "is ill-formed". An ill-formed program may still compile and run, but if it does, it would have an undefined behavior.

It can be compiled. G++ prior to version 4.7 compiled this and it ran as expected (as people would assume dependent type lookup would work).

 

> I am interested in why the standard is worded to exclude this code. The standard currently allows this if the type is an enum for example:
>
>
> template <typename T> T f(T t) {
>     return g(t);
> }
> enum E {e};
> int g(E x) {
>     return x + 1;
> }
> main() {
>     E x(e);
>     x = f(x);
> }
>
>
> This code works (according to the standard).

Yes. This code is well-formed, because E is not a fundamental type, so it has an associated namespace (the global namespace, in this case).

This is not the question I am asking. Well formed is defined by the standard - I am asking why the standard is as it is.

 

> Why are we treating one type (enum, class) differenly from others (int, float). What is the reason for treating them differently?

Fundamental types do not have associated namespaces. That is the key point. So the instantiation-point lookup, which only looks in the associated namespaces, finds nothing. Frankly, I agree that it might have made more sense to have the global namespace be associated with the fundamental types. In that case, the lookup would find g() and the code would be well-formed. However, it was like this since the beginning, so I have to presume that either there is a valid reason or it was a mistake that created a precedent which couldn't be corrected for backward compatibility issues.

Can we define the associated namespace of a fundamental type to be the default namespace? Obviously we can - so why not?

 

For example, consider the code:

class A {
public:
    A(int) {}
};

int g(A) {
    return 0;
}

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

int g(int x) {
    return x + 1;
}

int main() {
    int x(1);
    std::cout << f(x) << "\n";
}

This is well-formed in C++03 and C++11 and produces the output "0". If we were to change the associated namespaces of the fundamental types to include the global namespace, the code would still be well-formed but would produce the output "2". From the point of view of the standard committee, a silent change in the behavior of a well-formed program is usually unacceptable. It may be acceptable only if the benefits significantly outweighs the potential backward compatibility issues. I don't think that's the case, here.

The results would be different if we started from an enum instead of an int. What happens if we put all of this in a template?

 

enum E {e};

struct A {

    A(E) {};

    A(int) {};

};

int g(A) {

    return 0;

}

template <typename T> int f(T t) {

    return g(t);

}

int g(int) {

    return 1;

}

int g(E) {

    return 1;

}

template <typename T> void test() {

    T t;

    std::cout << f(t) << "\n";

}

int main() {

    test<int>();

    test<E>();

}

Imagine this was all buried in a library, how logical is it that the type returned depends on the type of the template argument to test?

  

So my point is: I don't know why this decision was taken, but it seems anyway too late to change direction.

As I explained in the introduction, for generic programming the template would be in a library, we would want to include the library and then define some functions to implement a concept from the library on the type we are using, and then call the generic algorithms.

I want to understand why the decision was taken, as I don't think its ever too late to fix a mistake, but was it a mistake?

 

Cheers,

Keean.

[Keean Schupke]

Just thinking a bit more, you agree that it may have made more sense to have the global namespace associated with fundamental types.  Can we have a way to force the global namespace, for example (a completely un-thought through suggestion):

template <typename T> T f(T t) {

    return ::g(t);

}

Which would allow the template author to force the global namespace to be considered without breaking backwards compatibility?

Cheers,
Keean.

[Jean-Marc Bourguet]

Le mercredi 27 juin 2012 13:11:07 UTC+2, Keean Schupke a écrit :

Just thinking a bit more, you agree that it may have made more sense to have the global namespace associated with fundamental types.  Can we have a way to force the global namespace, for example (a completely un-thought through suggestion):

template <typename T> T f(T t) {

    return ::g(t);

}

Which would allow the template author to force the global namespace to be considered without breaking backwards compatibility?

:g is qualified and so looked up only in the context of the template definition. Thus it will be found if g is defined before the template and not found if g is defined after.

Yours,

--
Jean-Marc

[Keean Schupke]

Yes, and of course it is the type that needs to reference the global namespace not the function so this would be more appropriate:

template <typename T> T f(T t) {

    return g(::t);

}

Cheers,

Keean.

 

[Jean-Marc Bourguet]

Le mercredi 27 juin 2012 13:46:16 UTC+2, Keean Schupke a écrit :

Yes, and of course it is the type that needs to reference the global namespace not the function so this would be more appropriate:

template <typename T> T f(T t) {

    return g(::t);

}

This obviously will search for a global variable t declared before the template.

Yours,

--
Jean-Marc

[Keean Schupke]

Okay, here's something more to consider. How does this interact with multiple-dispatch on overloaded functions:

enum E {e};

struct A {

    A(E) {};

    A(int) {};

};

int g(A, A) {

    return 0;

}

template <typename T, typename S> int f(T t, S s) {

    g(t, s);

}

int g(int, int) {

    return 1;

}

int g(int, E) {

    return 2;

}

int g(E, int) {

    return 3;

}

int g(E, E) {

    return 4;

}

template <typename T, typename S> void test() {

    T t;

    S s;

    std::cout << f(t, s) << "\n";

}

int main() {

    test<int, int>();

    test<int, E>();

    test<E, int>();

    test<E, E>();

}

What will each call to test print out? Can you guess without running the code?

Cheers,

Keean.

[Keean Schupke]

It appears by using template specialisation instead of overloading, we get the desired result:

enum E {e};

struct A {

    A(E) {};

    A(int) {};

};

template <typename T, typename S> int g(T t, S s);

template <> int g(A, A) {

    return 0;

}

template <typename T, typename S> int f(T t, S s) {

    g(t, s);

}

template <> int g(int, int) {

    return 1;

}

template <> int g(int, E) {

    return 2;

}

template <> int g(E, int) {

    return 3;

}

template <> int g(E, E) {

    return 4;

}

template <typename T, typename S> void test() {

    T t;

    S s;

    std::cout << f(t, s) << "\n";

}

int main() {

    test<int, int>();

    test<int, E>();

    test<E, int>();

    test<E, E>();

}

However function template specialization has problems, that make normal overloaded functions preferable. Another work-around would be to include an unused enum argument in every function call, forcing the global namespace to be considered for the overload resolution. This second work-around seems even more problematic than the first.

 

Cheers,

Keean.

[Alberto Ganesh Barbati]

Il giorno 27/giu/2012, alle ore 13:11, Keean Schupke ha scritto:

> On Wednesday, 27 June 2012 11:05:52 UTC+1, Alberto Ganesh Barbati wrote:
>
>
> Just thinking a bit more, you agree that it may have made more sense to have the global namespace associated with fundamental types.

Yes, I do.

> Can we have a way to force the global namespace, for example (a completely un-thought through suggestion):
>
> template <typename T> T f(T t) {
> return ::g(t);
> }
>
> Which would allow the template author to force the global namespace to be considered without breaking backwards compatibility?

What about:

template <typename T>
struct ForceADL
{
T value;
ForceADL(T x) : value(x) {}
operator T() { return value; }
};

template <typename T> int f(T t) {

return g(ForceADL<T>(t));
}

This is the basic idea. I believe that it could be improved to avoid the unnecessary copy thus allowing T to be non-copiable.

Ganesh

[Keean Schupke]

I have been looking at the assembly generated by various solutions:

With the ForceADL class, the code after optimisation is not the same at without it. Interestingly adding a dummy parameter:

#include <iostream>

enum E {e};

struct A {

    A(E) {};

    A(int) {};

};

int g(A, A) {

    return 0;

}

template <typename T, typename S> int f(T t, S s) {

    g(e, t, s);

}

int g(E, int x, int) {

    return 1 + x;

}

int g(E, int, E) {

    return 2;

}

int g(E, E, int) {

    return 3;

}

int g(E, E, E) {

    return 4;

}

template <typename T, typename S> void test(T t, S s) {

    std::cout << f(t, s) << "\n";

}

int main() {

    int x(1);

    E y(e);

    test(x, x);

    test(x, y);

    test(y, x);

    test(y, y);

}

Seems to produce better assembly output.

However I think the function template specialisation solution is going to work best for my project because I already need to do partial specialisations in some places for example:

template <typename T, typename S> int g(T, S);

template <> int g(int, int) {

    return 1;

}

template <typename T, typename S> int g(T* x, T* y) {

[Keean Schupke]

Sorry, hit post by accident...

 template <typename T, typename S> int g(T* x, T* y) {

    g(*x, *y);

 }

etc...

Cheers,
Keean.

[Alberto Ganesh Barbati]

Il giorno 27/giu/2012, alle ore 17:58, Keean Schupke ha scritto:

What about:

template <typename T>
struct ForceADL
{
        T value;
        ForceADL(T x) : value(x) {}
        operator T() { return value; }
};

template <typename T> int f(T t) {
    return g(ForceADL<T>(t));
}

This is the basic idea. I believe that it could be improved to avoid the unnecessary copy thus allowing T to be non-copiable.

Ganesh

I have been looking at the assembly generated by various solutions:

With the ForceADL class, the code after optimisation is not the same at without it.

That's probably because of the unnecessary copy I mentioned. Try this more elaborated approach instead, using references and perfect forwarding:

template <typename T> 
struct force_adl_aux 
{ 
        T&& value; 
        force_adl_aux(T&& x) : value(x) {} 
        operator T&&() { return std::forward<T>(value); } 
};

template <typename T> 

force_adl_aux<T> force_adl(T&& x)

{

return force_adl_aux<T>(x);

}

template <typename T> int f(T t) { 

    return g(force_adl(t)); 

}

Ganesh

[Keean Schupke]

Or maybe this is a better approach using templates that allows partial specialisation, and has the added advantage that functions passed as arguments can be inlined:

 

enum E {e};

struct A {

    A(E) {};

    A(int) {};

};

template <typename T, typename S> struct g {

    int operator() (T, S);

};

template <> struct g<A, A> {

    int operator() (A, A) {

        return 0;

    }

};

template <typename T, typename S> int f(T t, S s) {

    g<T, S> gg;

    gg(t, s);

}

template <typename T> struct g<T, int> {

    int operator() (T, int) {

        return 1;

    }

};

template <> struct g<int, E> {

    int operator() (int, E) {

        return 2;

    }

};

template <> struct g<E, int> {

    int operator() (E, int) {

        return 3;

    }

};

template <> struct g<E, E> {

    int operator() (E, E) {

        return 4;

    }

};

template <typename T> struct g<T*, T*> {

    int operator() (T*, T*) {

        return 5;

    }

};

template <typename T> struct g<T**, T**> {

    int operator() (T**, T**) {

        return 6;

    }

};

template <typename T, typename S> void test(T t, S s) {

    std::cout << f(t, s) << "\n";

}

int main() {

    int x(1);

    E y(e);

    test(x, x);

    test(x, y);

    test(y, x);

    test(y, y);

    test(&x, &x);

    test(&y, &y);

    int* xx(&x);

    E* yy(&y);

    test(&xx, &xx);

    test(&yy, &yy);

}

Its starting to look like a lot of boiler-plate to work around this though...

Cheers,

Keean.

[Keean Schupke]

I have implemented the above in my project and this has solved my immediate problem. There appears to be no performance penalty (after optimisation) and the only change is the use of specialisation (and partial specialisation) instead of overloading to select the function to be used, and so far this has not changed the program behaviour.

Can anyone think of any problems with this approach, or where using specialisation instead of overloading has the potential to cause problems?

It does feel like C++ legacy issues are hurting readability and maintainability of code (certainly for me at least). I guess at some point it would be beneficial to take all the lessons learned from designing C++ and take it forward into a new clean language without all the legacy issues (C+=2?)

Cheers,

Keean.