5 ms·

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem: void func() { a d;

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem: void func() { a d; } If a is a class template, the line in func() declares an instance of type "a<b, c>". If a is a global variable, it describes an invocation of the "<" and ">" operators for 4 different variables. Maintaining a parse tree of this is a massive mess, especially if func() is a template itself (and hence the meaning of a would change based on the instantiation).

fermenflo 7y ago
Thank you, as someone with no C++ background, this example makes the issue at hand much clearer.
waynecochran 7y ago
I have never written code to translate templates. Do you actually build a syntax tree for the template itself? I always assumed you would just store a simpler representation of the template (e.g., just a string of lexemes) and only build syntax trees when the template is instantiated. Of course you still need to "parse" the template when it is encountered but you have to do it without semantic information (e.g., you don't know what `a` will expand to until instantiation) -- I guess that is the problem. It is funny that Lisp's defmacro doesn't have this problem because the code itself is a syntax tree.
- MauranKilom 7y ago
  Either of your mentioned options for implementing template parsing were used by implementations when C++ was conceived (but before it became an ISO standard). Your "token string" approach is the route that Microsoft took with MSVC, whereas other compilers went with what later became standardized as "two phase lookup". In short: Token stream alone is not enough. You need to decide whether T::A * b; is a pointer declaration or a multiplication immediately when you parse the template. If A is a dependent name (i.e. if T is a template parameter), it is assumed to be a variable (if that's not correct, the programmer must use typename or template). MSVC has only recently completed their implementation of two-phase lookup, some twenty years after it was defined as the correct option in the ISO C++ standard. They have an excellent writeup here: https://devblogs.microsoft.com/cppblog/two-phase-name-lookup-support-comes-to-msvc/ https://devblogs.microsoft.com/cppblog/two-phase-name-lookup...
rozab 7y ago
Do Java and C# not have any problems like this?
- waynecochran 7y ago
  Generics are not templates (i.e., not instantiated at compile time) so you avoid a lot of this mess.
fusilli_jerry 7y ago
To be clear here though, you can always (*undecidably, but subject to practical constraints) fully parse a template definition into a parse tree, and that parse tree will not change for any instantiation. In your example, 'a' is known at parse time to either be a type or a value even if it's a template parameter, so the statement will always parse one way or another. Of course, 'a' itself may change in type or value so the problem is still unwieldy and, probably key to your use case, requires knowledge of type information from a possibly far-off part of the translation unit.
- john_moscow 7y ago
 Yeah, good luck with this one then: template <typename foo> void func() { foo::a < foo::b , foo::c > d; }
 - fusilli_jerry 7y ago
 This is still not ambiguous: in order for 'foo::a' to be a template, 'a' must be prefixed with the 'template' disambiguator keyword, and in fact for any of a, b, or c to be types at all they would have to be prefixed with 'typename'. As written, it must parse as two expressions; if 'foo::a' turns out to be a class template at instantiation time, it's an error.
 - MauranKilom 7y ago
 Two-phase lookup requires this to be interpreted at template parse time as two comparisons and a comma operator, because a, b and c are dependent names (which, without further disambiguation with the typename or template keyword, are taken to be variables). This has been the case since the first ISO C++ standard (published in 1998).
waynecochran 7y ago
Might as well throw in the most vexing parse (https://en.wikipedia.org/wiki/Most_vexing_parse https://en.wikipedia.org/wiki/Most_vexing_parse) with it: void func() { a d(); }

fermenflo 7y ago

Thank you, as someone with no C++ background, this example makes the issue at hand much clearer.

waynecochran 7y ago

I have never written code to translate templates. Do you actually build a syntax tree for the template itself? I always assumed you would just store a simpler representation of the template (e.g., just a string of lexemes) and only build syntax trees when the template is instantiated. Of course you still need to "parse" the template when it is encountered but you have to do it without semantic information (e.g., you don't know what `a` will expand to until instantiation) -- I guess that is the problem. It is funny that Lisp's defmacro doesn't have this problem because the code itself is a syntax tree.

MauranKilom 7y ago
Either of your mentioned options for implementing template parsing were used by implementations when C++ was conceived (but before it became an ISO standard). Your "token string" approach is the route that Microsoft took with MSVC, whereas other compilers went with what later became standardized as "two phase lookup". In short: Token stream alone is not enough. You need to decide whether T::A * b; is a pointer declaration or a multiplication immediately when you parse the template. If A is a dependent name (i.e. if T is a template parameter), it is assumed to be a variable (if that's not correct, the programmer must use typename or template). MSVC has only recently completed their implementation of two-phase lookup, some twenty years after it was defined as the correct option in the ISO C++ standard. They have an excellent writeup here: https://devblogs.microsoft.com/cppblog/two-phase-name-lookup-support-comes-to-msvc/ https://devblogs.microsoft.com/cppblog/two-phase-name-lookup...

rozab 7y ago

Do Java and C# not have any problems like this?

waynecochran 7y ago
Generics are not templates (i.e., not instantiated at compile time) so you avoid a lot of this mess.

fusilli_jerry 7y ago

To be clear here though, you can always (*undecidably, but subject to practical constraints) fully parse a template definition into a parse tree, and that parse tree will not change for any instantiation. In your example, 'a' is known at parse time to either be a type or a value even if it's a template parameter, so the statement will always parse one way or another. Of course, 'a' itself may change in type or value so the problem is still unwieldy and, probably key to your use case, requires knowledge of type information from a possibly far-off part of the translation unit.

john_moscow 7y ago
Yeah, good luck with this one then: template <typename foo> void func() { foo::a < foo::b , foo::c > d; }
- fusilli_jerry 7y ago
 This is still not ambiguous: in order for 'foo::a' to be a template, 'a' must be prefixed with the 'template' disambiguator keyword, and in fact for any of a, b, or c to be types at all they would have to be prefixed with 'typename'. As written, it must parse as two expressions; if 'foo::a' turns out to be a class template at instantiation time, it's an error.
- MauranKilom 7y ago
 Two-phase lookup requires this to be interpreted at template parse time as two comparisons and a comma operator, because a, b and c are dependent names (which, without further disambiguation with the typename or template keyword, are taken to be variables). This has been the case since the first ISO C++ standard (published in 1998).

waynecochran 7y ago

Might as well throw in the most vexing parse (https://en.wikipedia.org/wiki/Most_vexing_parse https://en.wikipedia.org/wiki/Most_vexing_parse) with it: void func() { a d(); }

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem: void func() { a < b , c > d;

As someone who had spent quite some time developing C++ refactoring tools, here's the most concise example of the problem: void func() { a < b , c > d;