Is template instantation part of parsing C++

Question

I had a discussion with someone about parsing C++. He said that C++ has to instantiate all the templates while parsing while I thought that is not the case. You could simply create a parse tree and then so template instantiation later.

How does GCC and Clang handle this?

How do you "instantiate" templates when parsing them, when you don't know what the template parameters are until, well, they get instantiated for real-sies? — Sam Varshavchik, Apr 29 '20 at 18:07
@SamVarshavchik I think the question is whether template _instantiations_, not template _definitions_, are... instantiated... while parsing. — Thomas, Apr 29 '20 at 18:15
@SamVarshavchik You have already parsed the templates. The parser see a usage site and could theoretically instantiate the template. — CryptoNoob, Apr 29 '20 at 18:18
@Thomas Well Yeah of course I can read the source. But It isn't like this will be fast since I don't have any familiarity with the codebase. Before I know this I could busy for hours or days. — CryptoNoob, Apr 29 '20 at 18:19
You probably meant @JesperJuhl not me, but I wholly agree. Especially the GCC source code does not exactly have a reputation of being beginner-friendly... — Thomas, Apr 29 '20 at 18:24

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

Your friend is right. Tbe templates must be instantiated, and that is what compilers do. [Note 1]

There are much simpler examples but I had this one handy; it's taken from this answer.

The parse of the first line in main is dependent on the instantiation (not just the parse) of the IsPrime template. As written, it produces a syntax error if the template argument to IsPrime is not a prime; however, changing () to (0) will allow both possibilities to be valid but with very different parses. (With a composite template argument, typen is a simple integer constant, and typen<1>(0) is two comparisons, equivalent to (typen < 1) > 0.)

Not all examples are as contrived as this one. When I wrote it, I was trying to make a different point, which was that the correct parse of a C++ program might require the solution of a fairly complicated mathematical problem, like determining if a large number is prime. That takes C++ well outside of the realm of context-free languages.

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
  : IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 

template<typename A> struct foo;
template<>struct foo<answer<true>>{
  template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
  static const int typen = 0;
};

int main() {
  auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
  return 0;
}

Notes

Ira Baxter will say that you could use a GLR parser to find all the possible alternative parses without instantiating templates and then select the correct parse after you instantiate. That is true, but IMHO parsing hasn't finished until you know which parse is correct.

Is template instantation part of parsing C++

1 Answers1

Notes