www.digitalmars.com         C & C++   DMDScript  

c++ - [bug report] recursive template definition

reply "Szabolcs Horvát" <szhorvat yahoo.co.uk> writes:
The dmc compiler crashes on recursive template definitions without any stop
condition, without issuing any error message.

Example:

template<int N> float power(float x) { return power<N-1>(x)*x; }

int main() { power<10>(2); }


In most cases this isn't a problem, because such source code is incorrect
anyway, but it also crashes with the following function used to quickly
compute small integer powers (which works well when compiled with Borland
C++):

template<unsigned N, typename T>
inline T power(T x) {
 return
  N == 0
   ? 1
  : (N == 1
   ? x
  : (N == 2
   ? x*x
  : (N == 3
   ? x*x*x
  : (N == 4
   ? power<2>(power<2>(x))
  : (N == 9
   ? power<3>(power<3>(x))
  : (N == 12
   ? power<3>(power<4>(x))
  : (N == 16
   ? power<4>(power<4>(x))
  : (N == 25
   ? power<5>(power<5>(x))
  : (N%2 == 0
   ? power<2>(power<N/2>(x))
  : (N%3 == 0
   ? power<3>(power<N/3>(x))
  : power<N-1>(x)*x
  ))))))))));
}


It doesn't crash when the same function is written this way (but I couldn't
figure out how to templatise the type of the function argument when using
this solution):


template<unsigned N> inline float power(float x) {
 return N%2 == 0
  ? power<2>(power<N/2>(x))
  : (N%3 == 0 ? power<3>(power<N/3>(x)) : x*power<N-1>(x));
}
template<> inline float power<25>(float x) {
 return power<5>(power<5>(x));
}
template<> inline float power<16>(float x) {
 return power<4>(power<4>(x));
}
template<> inline float power<12>(float x) {
 return power<3>(power<4>(x));
}
template<> inline float power<9>(float x) {
 return power<3>(power<3>(x));
}
template<> inline float power<4>(float x) {
 return power<2>(power<2>(x));
}
template<> inline float power<3>(float x) {
 return x*x*x;
}
template<> inline float power<2>(float x) {
 return x*x;
}
template<> inline float power<1>(float x) {
 return x;
}
template<> inline float power<0>(float x) {
 return 1;
}
Sep 09 2004
parent reply Daniel James <daniel calamity.org.uk> writes:
Szabolcs Horvát wrote:
 In most cases this isn't a problem, because such source code is incorrect
 anyway, but it also crashes with the following function used to quickly
 compute small integer powers (which works well when compiled with Borland
 C++):
 
 template<unsigned N, typename T>
 inline T power(T x) {
  return
   N == 0
    ? 1
   : (N == 1
    ? x
   : (N == 2
    ? x*x
   : (N == 3
    ? x*x*x
   : (N == 4
    ? power<2>(power<2>(x))
   : (N == 9
    ? power<3>(power<3>(x))
   : (N == 12
    ? power<3>(power<4>(x))
   : (N == 16
    ? power<4>(power<4>(x))
   : (N == 25
    ? power<5>(power<5>(x))
   : (N%2 == 0
    ? power<2>(power<N/2>(x))
   : (N%3 == 0
    ? power<3>(power<N/3>(x))
   : power<N-1>(x)*x
   ))))))))));
 }
Sorry, I don't think you're allowed to do that. The compiler can't be expected to know which functions to instantiate.
 It doesn't crash when the same function is written this way (but I couldn't
 figure out how to templatise the type of the function argument when using
 this solution):
By coincidence, I was playing around with doing something like this the other day. One way to do this kind of thing is by using an extra paramter to select the required function. I wrote this: namespace detail { enum power_type { zero, one, even, odd }; template <power_type N> struct gen_power_type {}; template <unsigned n, typename T> inline T power(T const& x, gen_power_type<zero> const&) { return 1; } template <unsigned n, typename T> inline T power(T const& x, gen_power_type<one> const&) { return x; } template <unsigned n, typename T> inline T power(T const& x, gen_power_type<even> const&) { return power<n/2>(x*x); } template <unsigned n, typename T> inline T power(T const& x, gen_power_type<odd> const&) { return x * power<n-1>(x); } template <unsigned n, typename T> inline T power(T const& x) { return detail::power<n>(x, detail::gen_power_type< (n == 0 ? detail::zero : n == 1 ? detail::one : n % 2 == 0 ? detail::even : detail::odd)>()); } } template <unsigned n, typename T> T power(T const& x) { return detail::power<n>(x); I used an enum there, but you could you this technique with integers instead. An alternative is to use a specialised template structure: namespace detail { template <unsigned n> struct power_impl; template <> struct power_impl<0> { template <class T> static inline T calc(T const& x) { return 1; } }; template <> struct power_impl<1> { template <class T> static inline T calc(T const& x) { return x; } }; template <unsigned n> struct power_impl { template <class T> static inline T calc(T const& x) { if(n & 1 == 0) return power_impl<(n >> 1)>::calc(x * x); else return x * power_impl<n-1>::calc(x); } }; } template <unsigned n, typename T> T power(T const& x) { return detail::power_impl<n>::calc(x); } I hope that helps. Daniel
Sep 09 2004
parent reply "Szabolcs Horvát" <szhorvat yahoo.co.uk> writes:
Daniel James wrote:
 An alternative is to use a specialised template structure:

 I hope that helps.

 Daniel
Thank you, it did help. But when I tried to use the same technique inside a class, the compiler failed to instantiate the member classes. This is a minimal code fragment that produces the error: class Class { template<unsigned U> struct Member { static void g() {} }; public: void f() { Member<0>::g(); } }; int main() { Class u; u.f(); } Borland C++ 5.5 compiles this without any error while dmc 8.40 stops with test.cpp(5) : Error: '?$Member Class $0 ' is not a member of struct 'Class' --- errorlevel 1 Do you think this is a compiler bug or am I doing something wrong again? Szabolcs
Sep 13 2004
parent Daniel James <daniel calamity.org.uk> writes:
Szabolcs Horvát wrote:
     class Class {
         template<unsigned U> struct Member { static void g() {} };
     public:
         void f() { Member<0>::g(); }
     };
 
     int main() {
         Class u;
         u.f();
     }
 
 
 Borland C++ 5.5 compiles this without any error while dmc 8.40 stops with
 
 test.cpp(5) : Error: '?$Member Class $0 ' is not a member of struct 'Class'
 --- errorlevel 1
 
 Do you think this is a compiler bug or am I doing something wrong again?
Yep, it's a bug. To work around it you can use a typedef: void f() { typedef Member<0> Member_0; Member_0::g(); } I've come across similar problems when using static member variables. Daniel
Sep 15 2004