12 ms·

Parsing C++ is literally undecidable (2013)

111 points by umanwizard 7y ago

snazzycalynx 7y ago
I have nothing against C++ but the inherent complexity is ridiculous. The vast majority of C++ code I've worked with simply stays far away from these intricacies. Which leads me to think that a simpler strict subset of C++ isn't such a bad idea.
lallysingh 7y ago
This is why the tools situation in c++ had been so far behind other languages like Java. You have to build a full frontend to even parse the language. They're slowly becoming available via clang now, which is nice.
- msla 7y ago
  I wonder if it's possible to craft a non-gigantic C++ file which causes a clang frontend to crash.
  - earenndil 7y ago
    For sure. Generally it boils down to a non-gigantic number of template instantiations or macro expansions that end up generating a huge parse tree.
  - jeeyoungk 7y ago
    This is possible in almost all language, even Python (!!!) - see the Stack Overflow question https://codegolf.stackexchange.com/questions/69189/build-a-compiler-bomb https://codegolf.stackexchange.com/questions/69189/build-a-c...
  - pnako 7y ago
    There is this funny competition: https://tgceec.tumblr.com/ https://tgceec.tumblr.com/ You could pick the winning entries and use them as a corpus for a fuzzer and you might find compiler crashes.
  - gpderetta 7y ago
    ICEs [1] used to be very common from all front ends especially with malformed template code, but now a day I think most compilers don't report an ICE to the user as long as they managed to issue at least one diagnostic. It is still not uncommon to se ICEs on some extreme template constructs. [1] Internal Compiler Error, i.e. the compiler segfaulted or hit an internal assertion.
- millstone 7y ago
  Java has generics and overloading; how far can you realistically get before building a full frontend? Honest question.
  - saagarjha 7y ago
    Anecdotal, but I’ve found it difficult to find a Java autocomplete plug-in that doesn’t run Eclipse in the background to work.
  - username90 7y ago
    Java generics are just syntactic sugar for Object, so not a problem at all since you can't do anything with them. Java overloading is simple since all functions are in the same file (so doesn't change overload behavior depending on which files are imported) and Java lacks the user type casts C++ has, so just pick the signature fitting all provided values (with numeric casts) or throw.
    - josefx 7y ago
      > Java generics are just syntactic sugar for Object, Only if you do not have a concrete boundary in the generic declaration, T extends Foo can result in a function definition that takes a Foo instead of an Object. > Java overloading is simple since all functions are in the same file (so doesn't change overload behavior depending on which files are imported) import static java.lang.Math.*; for programmers too lazy to write Math.sin instead of sin.
  - lallysingh 7y ago
    The grammar is still context free.
- jonstewart 7y ago
  Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java? Visual Studio has had Intellisense since forever, clang-format can enforce style standards, static analyzers these days are amazing, the address sanitizer and valgrind find memory problems easily, etc.
  - coldpie 7y ago
    > Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java? The most obvious example to me is in Eclipse, you can right-click on a field in a Java class and choose to Rename it. It will then correctly update that field's name across the entire codebase. AFAIK this is impossible in C & C++ because they are such complicated languages to parse. Macros alone make this feature effectively impossible.
    - bluGill 7y ago
      Java had it first (by at least 10 years), but C++ IDEs do the same. Clang not being designed to make it impossible to access the AST has made this feasible for most IDEs. There are still cases where it cannot be done (macros), but in many cases it can be done now.
      - uglycoyote 7y ago
        Jetbrains makes excellent refactoring tools for multiple languages so I usually use their tools as my gauge of how well a language lends itself to refactoring. As a daily user of Resharper in both C# and C++, I really notice how much poorer they work in C++. Renaming operations, as you mentioned, do work in C++ sometimes, but not others. Generally if it is a variable or parameter that's used locally I can rename it instantly with no problem. If it's a variable exposed in the class header, then it will tend to sit there churning for enough time before I decide that I should probably cancel the operation. Likewise, simply using a "Find References" or "Find Usages" in C++ usually works, but at times it gives odd suggestions of things that are clearly not usages of the thing I'm searching, but something else with the same name that it just is not smart enough to understand is not a real usage. (possibly due to the difficulty of parsing templates or macros) "Extract Method" is one of my favorite C# refactorings. Resharper C++ also has this operation but it is a bit of a gong show, and generates results that usually have to be tidied up considerably afterwards.
millstone 7y ago
Why shouldn't C++ templates be Turing-complete? Template metaprogramming is a great strength of C++. The language is gross but the result is quite powerful.
- jchw 7y ago
  I don't feel as though the article is making value judgements based on the conclusions. At least I didn’t see anything. The implicit conclusion may be “wow, C++ is ridiculous,” but to be honest I didn’t feel that kind of tone when reading this article. That doesn’t mean it doesn’t matter though. The decidability of C++ grammar certainly matters to folks that are parsing C++ code.
- GolDDranks 7y ago
  The problem isn't that C++ templates are Turing complete. In fact, many similar macro systems are. The problem is that the result of template/macro expansion may affect the parsing of other places, so you can't parse the non-template parts separately from the Turing-complete parts.
- saagarjha 7y ago
  I don’t think it was designed to be Turing-complete, so it’s a lot more annoying than it could be when you try to use it this way.
  - bluGill 7y ago
    The early template designers specified a limit of template recursion (16 IIRC) which they thought was more than deep enough for any real use, and would ensure that it wasn't Turing complete (truing complete of course requires no limit to template recursion depth). However soon after people started finding deeper template recursion depths were required for the real problems they wanted to solve.
rienbdj 7y ago
Can we design a language (cpp-prime?) that is basically c++ but makes parsing easier? I'm thinking reduce the keyword reuse, use different symbols for multiplication and pointers etc. The code would be easy for c++ developers to read and converting between the two could be automatic. However, we would be able to build tooling for this new language much more easily. It would also compile quicker.
- saagarjha 7y ago
  C?
  - jstimpfle 7y ago
    C has its own parsing problems.
    - eru 7y ago
      Yes, though I don't think it's undecidable to parse.
- skocznymroczny 7y ago
  In theory that's D. D was designed to be easier to parse than C++, for example, it uses Foo!Bar and Foo!(Bar, 4) template syntax rather than Foo<Bar> and Foo<Bar, 4>. On the other hand, it still uses templates and supports mixins (basically #define on steroids), so while it's easy to parse, large chunks of code don't exist until compile time so can't be indexed by IDEs perfectly.
  - pjmlp 7y ago
    And as much as I like their community, I feel it already lost its spotlight opportunity, due to their lack of manpower vs other languages offerings and continuous improvements. Even if C++ is a little baroque, C++17 and now C++20 provide many of the D's benefits, while keeping all the libraries, and finally we are getting Java like C++'s tooling to just throw it away.
petters 7y ago
> If it is not SomeType, then ::name is a typedef for int and the parse tree is declaring a pointer-to-int named x. Doesn't this require "typename" at the beginning of the line?
- MauranKilom 7y ago
  No, not in this instance. typename is needed to mark dependent names as types, but you can only have dependent (i.e. on a template parameter) names within templates.
choeger 7y ago
This is one of the major issues with these languages that were initially designed by amateurs (I mean that in the positive sense, someone who does something because they care about it, and not because they are paid to do it). Often they simply did not see the long-term benefit of adhering to the limits of a "standard" architecture (i.e., context-free, unambiguous grammar, decidable static analysis (lookup!), multi-pass implementation). Yet these hackers still made a successful product. Now others must live with the consequences (for another example, have a look at javascript's scoping - I strongly suspect that it was a beginner's mistake that made it into production). That particular syntactic ambiguity in C++ would have been trivial to fix (and could still be fixed today!), but no one really cares (and it would not be backwards compatible...). Another example is the current situation with modules in C++. Instead of looking into the diverse ML implementations or even Java and trying to get the system right, the current discussion goes into wild compiler hacks just to avoid a simple limitation on filenames.
- rightbyte 7y ago
  If I remember correctly Stroustrup was working at Bell labs in the initial phases of the cpp design with a formal education in CS. Hardly an amateur? Inexperienced maybe.
  - smitty1e 7y ago
    For a random sampling of the internet, being a critic of a complex system is trivial. Offering an alternative that's an objective improvement, much less, on par with the status quo? Not so much.
  - vkazanov 7y ago
    "Formal education in CS" is not the same as, say, a degree related to programming languages or compilers.
    - tralarpa 7y ago
      Yes. There is a section in one of his books where he wrote that he added some feature in an ad-hoc way just because of a request from a colleague. Unfortunately, as I have already written in another comment some months ago, C++ was the wrong thing that came at the right time (C people were starting looking for alternatives, seeing what cool things other languages were doing).
yati 7y ago
Maybe interesting for people here is also the undecidability of parsing Perl: http://www.jeffreykegler.com/Home/perl-and-undecidability http://www.jeffreykegler.com/Home/perl-and-undecidability
einpoklum 7y ago
Key point: > In practice, compilers limit template instantiation depth, so this is more of a theoretical problem than a practical one.
- seanmcdirmid 7y ago
  Magic numbers to limit undecidability are incredibly fragile. You think you have all the cases covered and another comes up, or the numbers need to be enlarged because of some reasonable code being rejected. Better to have this problem in the parser than the type checker, at least.
  - einpoklum 7y ago
    There's no assumption that all the cases are covered up. Only some. The point is - in practice, don't try to go in too deep with templates.
john_moscow 7y ago
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; } 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...

111 points by umanwizard 7y ago

I have nothing against C++ but the inherent complexity is ridiculous. The vast majority of C++ code I've worked with simply stays far away from these intricacies. Which leads me to think that a simpler strict subset of C++ isn't such a bad idea.

lallysingh 7y ago

This is why the tools situation in c++ had been so far behind other languages like Java. You have to build a full frontend to even parse the language. They're slowly becoming available via clang now, which is nice.

msla 7y ago
I wonder if it's possible to craft a non-gigantic C++ file which causes a clang frontend to crash.
- earenndil 7y ago
  For sure. Generally it boils down to a non-gigantic number of template instantiations or macro expansions that end up generating a huge parse tree.
- jeeyoungk 7y ago
  This is possible in almost all language, even Python (!!!) - see the Stack Overflow question https://codegolf.stackexchange.com/questions/69189/build-a-compiler-bomb https://codegolf.stackexchange.com/questions/69189/build-a-c...
- pnako 7y ago
  There is this funny competition: https://tgceec.tumblr.com/ https://tgceec.tumblr.com/ You could pick the winning entries and use them as a corpus for a fuzzer and you might find compiler crashes.
- gpderetta 7y ago
  ICEs [1] used to be very common from all front ends especially with malformed template code, but now a day I think most compilers don't report an ICE to the user as long as they managed to issue at least one diagnostic. It is still not uncommon to se ICEs on some extreme template constructs. [1] Internal Compiler Error, i.e. the compiler segfaulted or hit an internal assertion.
millstone 7y ago
Java has generics and overloading; how far can you realistically get before building a full frontend? Honest question.
- saagarjha 7y ago
  Anecdotal, but I’ve found it difficult to find a Java autocomplete plug-in that doesn’t run Eclipse in the background to work.
- username90 7y ago
  Java generics are just syntactic sugar for Object, so not a problem at all since you can't do anything with them. Java overloading is simple since all functions are in the same file (so doesn't change overload behavior depending on which files are imported) and Java lacks the user type casts C++ has, so just pick the signature fitting all provided values (with numeric casts) or throw.
  - josefx 7y ago
    > Java generics are just syntactic sugar for Object, Only if you do not have a concrete boundary in the generic declaration, T extends Foo can result in a function definition that takes a Foo instead of an Object. > Java overloading is simple since all functions are in the same file (so doesn't change overload behavior depending on which files are imported) import static java.lang.Math.*; for programmers too lazy to write Math.sin instead of sin.
- lallysingh 7y ago
  The grammar is still context free.
jonstewart 7y ago
Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java? Visual Studio has had Intellisense since forever, clang-format can enforce style standards, static analyzers these days are amazing, the address sanitizer and valgrind find memory problems easily, etc.
- coldpie 7y ago
  > Can you be more specific and/or support the argument that the tools for C++ are behind what's available for Java? The most obvious example to me is in Eclipse, you can right-click on a field in a Java class and choose to Rename it. It will then correctly update that field's name across the entire codebase. AFAIK this is impossible in C & C++ because they are such complicated languages to parse. Macros alone make this feature effectively impossible.
  - bluGill 7y ago
    Java had it first (by at least 10 years), but C++ IDEs do the same. Clang not being designed to make it impossible to access the AST has made this feasible for most IDEs. There are still cases where it cannot be done (macros), but in many cases it can be done now.
    - uglycoyote 7y ago
      Jetbrains makes excellent refactoring tools for multiple languages so I usually use their tools as my gauge of how well a language lends itself to refactoring. As a daily user of Resharper in both C# and C++, I really notice how much poorer they work in C++. Renaming operations, as you mentioned, do work in C++ sometimes, but not others. Generally if it is a variable or parameter that's used locally I can rename it instantly with no problem. If it's a variable exposed in the class header, then it will tend to sit there churning for enough time before I decide that I should probably cancel the operation. Likewise, simply using a "Find References" or "Find Usages" in C++ usually works, but at times it gives odd suggestions of things that are clearly not usages of the thing I'm searching, but something else with the same name that it just is not smart enough to understand is not a real usage. (possibly due to the difficulty of parsing templates or macros) "Extract Method" is one of my favorite C# refactorings. Resharper C++ also has this operation but it is a bit of a gong show, and generates results that usually have to be tidied up considerably afterwards.

millstone 7y ago

Why shouldn't C++ templates be Turing-complete? Template metaprogramming is a great strength of C++. The language is gross but the result is quite powerful.

jchw 7y ago
I don't feel as though the article is making value judgements based on the conclusions. At least I didn’t see anything. The implicit conclusion may be “wow, C++ is ridiculous,” but to be honest I didn’t feel that kind of tone when reading this article. That doesn’t mean it doesn’t matter though. The decidability of C++ grammar certainly matters to folks that are parsing C++ code.
GolDDranks 7y ago
The problem isn't that C++ templates are Turing complete. In fact, many similar macro systems are. The problem is that the result of template/macro expansion may affect the parsing of other places, so you can't parse the non-template parts separately from the Turing-complete parts.
saagarjha 7y ago
I don’t think it was designed to be Turing-complete, so it’s a lot more annoying than it could be when you try to use it this way.
- bluGill 7y ago
  The early template designers specified a limit of template recursion (16 IIRC) which they thought was more than deep enough for any real use, and would ensure that it wasn't Turing complete (truing complete of course requires no limit to template recursion depth). However soon after people started finding deeper template recursion depths were required for the real problems they wanted to solve.

rienbdj 7y ago

Can we design a language (cpp-prime?) that is basically c++ but makes parsing easier? I'm thinking reduce the keyword reuse, use different symbols for multiplication and pointers etc. The code would be easy for c++ developers to read and converting between the two could be automatic. However, we would be able to build tooling for this new language much more easily. It would also compile quicker.

saagarjha 7y ago
C?
- jstimpfle 7y ago
  C has its own parsing problems.
  - eru 7y ago
    Yes, though I don't think it's undecidable to parse.
skocznymroczny 7y ago
In theory that's D. D was designed to be easier to parse than C++, for example, it uses Foo!Bar and Foo!(Bar, 4) template syntax rather than Foo<Bar> and Foo<Bar, 4>. On the other hand, it still uses templates and supports mixins (basically #define on steroids), so while it's easy to parse, large chunks of code don't exist until compile time so can't be indexed by IDEs perfectly.
- pjmlp 7y ago
  And as much as I like their community, I feel it already lost its spotlight opportunity, due to their lack of manpower vs other languages offerings and continuous improvements. Even if C++ is a little baroque, C++17 and now C++20 provide many of the D's benefits, while keeping all the libraries, and finally we are getting Java like C++'s tooling to just throw it away.

petters 7y ago

> If it is not SomeType, then ::name is a typedef for int and the parse tree is declaring a pointer-to-int named x. Doesn't this require "typename" at the beginning of the line?

MauranKilom 7y ago
No, not in this instance. typename is needed to mark dependent names as types, but you can only have dependent (i.e. on a template parameter) names within templates.

choeger 7y ago

This is one of the major issues with these languages that were initially designed by amateurs (I mean that in the positive sense, someone who does something because they care about it, and not because they are paid to do it). Often they simply did not see the long-term benefit of adhering to the limits of a "standard" architecture (i.e., context-free, unambiguous grammar, decidable static analysis (lookup!), multi-pass implementation). Yet these hackers still made a successful product. Now others must live with the consequences (for another example, have a look at javascript's scoping - I strongly suspect that it was a beginner's mistake that made it into production). That particular syntactic ambiguity in C++ would have been trivial to fix (and could still be fixed today!), but no one really cares (and it would not be backwards compatible...). Another example is the current situation with modules in C++. Instead of looking into the diverse ML implementations or even Java and trying to get the system right, the current discussion goes into wild compiler hacks just to avoid a simple limitation on filenames.

rightbyte 7y ago
If I remember correctly Stroustrup was working at Bell labs in the initial phases of the cpp design with a formal education in CS. Hardly an amateur? Inexperienced maybe.
- smitty1e 7y ago
  For a random sampling of the internet, being a critic of a complex system is trivial. Offering an alternative that's an objective improvement, much less, on par with the status quo? Not so much.
- vkazanov 7y ago
  "Formal education in CS" is not the same as, say, a degree related to programming languages or compilers.
  - tralarpa 7y ago
    Yes. There is a section in one of his books where he wrote that he added some feature in an ad-hoc way just because of a request from a colleague. Unfortunately, as I have already written in another comment some months ago, C++ was the wrong thing that came at the right time (C people were starting looking for alternatives, seeing what cool things other languages were doing).

yati 7y ago

Maybe interesting for people here is also the undecidability of parsing Perl: http://www.jeffreykegler.com/Home/perl-and-undecidability http://www.jeffreykegler.com/Home/perl-and-undecidability

einpoklum 7y ago

Key point: > In practice, compilers limit template instantiation depth, so this is more of a theoretical problem than a practical one.

seanmcdirmid 7y ago
Magic numbers to limit undecidability are incredibly fragile. You think you have all the cases covered and another comes up, or the numbers need to be enlarged because of some reasonable code being rejected. Better to have this problem in the parser than the type checker, at least.
- einpoklum 7y ago
  There's no assumption that all the cases are covered up. Only some. The point is - in practice, don't try to go in too deep with templates.

john_moscow 7y ago

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; } 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...