Odd behavior when recursively building a return type for variadic functions
- by Dennis Zickefoose
This is probably going to be a really simple explanation, but I'm going to give as much backstory as possible in case I'm wrong. Advanced apologies for being so verbose. I'm using gcc4.5, and I realize the c++0x support is still somewhat experimental, but I'm going to act on the assumption that there's a non-bug related reason for the behavior I'm seeing.
I'm experimenting with variadic function templates. The end goal was to build a cons-list out of std::pair. It wasn't meant to be a custom type, just a string of pair objects. The function that constructs the list would have to be in some way recursive, with the ultimate return value being dependent on the result of the recursive calls. As an added twist, successive parameters are added together before being inserted into the list. So if I pass [1, 2, 3, 4, 5, 6] the end result should be {1+2, {3+4, 5+6}}.
My initial attempt was fairly naive. A function, Build, with two overloads. One took two identical parameters and simply returned their sum. The other took two parameters and a parameter pack. The return value was a pair consisting of the sum of the two set parameters, and the recursive call. In retrospect, this was obviously a flawed strategy, because the function isn't declared when I try to figure out its return type, so it has no choice but to resolve to the non-recursive version.
That I understand. Where I got confused was the second iteration. I decided to make those functions static members of a template class. The function calls themselves are not parameterized, but instead the entire class is. My assumption was that when the recursive function attempts to generate its return type, it would instantiate a whole new version of the structure with its own static function, and everything would work itself out.
The result was: "error: no matching function for call to BuildStruct<double, double, char, char>::Go(const char&, const char&)"
The offending code:
static auto Go(const Type& t0, const Type& t1, const Types&... rest)
-> std::pair<Type, decltype(BuildStruct<Types...>::Go(rest...))>
My confusion comes from the fact that the parameters to BuildStruct should always be the same types as the arguments sent to BuildStruct::Go, but in the error code Go is missing the initial two double parameters. What am I missing here? If my initial assumption about how the static functions would be chosen was incorrect, why is it trying to call the wrong function rather than just not finding a function at all? It seems to just be mixing types willy-nilly, and I just can't come up with an explanation as to why. If I add additional parameters to the initial call, it always burrows down to that last step before failing, so presumably the recursion itself is at least partially working. This is in direct contrast to the initial attempt, which always failed to find a function call right away.
Ultimately, I've gotten past the problem, with a fairly elegant solution that hardly resembles either of the first two attempts. So I know how to do what I want to do. I'm looking for an explanation for the failure I saw.
Full code to follow since I'm sure my verbal description was insufficient. First some boilerplate, if you feel compelled to execute the code and see it for yourself. Then the initial attempt, which failed reasonably, then the second attempt, which did not.
#include <iostream>
using std::cout;
using std::endl;
#include <utility>
template<typename T1, typename T2>
std::ostream& operator <<(std::ostream& str, const std::pair<T1, T2>& p) {
return str << "[" << p.first << ", " << p.second << "]";
}
//Insert code here
int main() {
Execute(5, 6, 4.3, 2.2, 'c', 'd');
Execute(5, 6, 4.3, 2.2);
Execute(5, 6);
return 0;
}
Non-struct solution:
template<typename Type>
Type BuildFunction(const Type& t0, const Type& t1) {
return t0 + t1;
}
template<typename Type, typename... Rest>
auto BuildFunction(const Type& t0, const Type& t1, const Rest&... rest)
-> std::pair<Type, decltype(BuildFunction(rest...))> {
return std::pair<Type, decltype(BuildFunction(rest...))>
(t0 + t1, BuildFunction(rest...));
}
template<typename... Types>
void Execute(const Types&... t) {
cout << BuildFunction(t...) << endl;
}
Resulting errors:
test.cpp: In function 'void Execute(const Types& ...) [with Types = {int, int, double, double, char, char}]':
test.cpp:33:35: instantiated from here
test.cpp:28:3: error: no matching function for call to 'BuildFunction(const int&, const int&, const double&, const double&, const char&, const char&)'
Struct solution:
template<typename... Types>
struct BuildStruct;
template<typename Type>
struct BuildStruct<Type, Type> {
static Type Go(const Type& t0, const Type& t1) { return t0 + t1; }
};
template<typename Type, typename... Types>
struct BuildStruct<Type, Type, Types...> {
static auto Go(const Type& t0, const Type& t1, const Types&... rest)
-> std::pair<Type, decltype(BuildStruct<Types...>::Go(rest...))> {
return std::pair<Type, decltype(BuildStruct<Types...>::Go(rest...))>
(t0 + t1, BuildStruct<Types...>::Go(rest...));
}
};
template<typename... Types>
void Execute(const Types&... t) {
cout << BuildStruct<Types...>::Go(t...) << endl;
}
Resulting errors:
test.cpp: In instantiation of 'BuildStruct<int, int, double, double, char, char>':
test.cpp:33:3: instantiated from 'void Execute(const Types& ...) [with Types = {int, int, double, double, char, char}]'
test.cpp:38:41: instantiated from here
test.cpp:24:15: error: no matching function for call to 'BuildStruct<double, double, char, char>::Go(const char&, const char&)'
test.cpp:24:15: note: candidate is: static std::pair<Type, decltype (BuildStruct<Types ...>::Go(BuildStruct<Type, Type, Types ...>::Go::rest ...))> BuildStruct<Type, Type, Types ...>::Go(const Type&, const Type&, const Types& ...) [with Type = double, Types = {char, char}, decltype (BuildStruct<Types ...>::Go(BuildStruct<Type, Type, Types ...>::Go::rest ...)) = char]
test.cpp: In function 'void Execute(const Types& ...) [with Types = {int, int, double, double, char, char}]':
test.cpp:38:41: instantiated from here
test.cpp:33:3: error: 'Go' is not a member of 'BuildStruct<int, int, double, double, char, char>'
