Check for resource exhaustion when recursively parsing declarators

[aaron.ballman]

Summary

With sufficiently tortured code, it's possible to cause a stack overflow when parsing declarators. Thus, we now check for resource exhaustion when recursively parsing declarators so that we can at least warn the user we're about to crash before we actually crash.

This fixes https://github.com/llvm/llvm-project/issues/51642.

[arsenm]

I think I've seen this one before

[aaron.ballman]

Two things to note:

1. I'm not convinced that adding a test case is the right thing to do here. On the one hand, we want to verify that we now emit the diagnostic before crashing. But on the other hand, this test is extremely expensive to run (because it exhausts the stack) and its behavior is highly specific to the test platform its being run on. If someone asked me to remove the test coverage here, I would not be sad.
2. The runWithSufficientStackSpace() implementation is a copy of what's already in Sema. I investigated lifting this interface to something more common, but the issue is with generating a diagnostic (there's no common diagnostic engine between Sema and Parser that I could find). Given the simplicity of the implementation, I figured it's reasonably defensible to duplicate the code.

[aaron.ballman]

Rebased.

I removed the test coverage because it turned out to not be testing anything. If we exhaust resources, then we don't run the -verify to test the diagnostic behavior, and we're relying on the crash being the test condition, but any crash will suffice.

[erichkeane]

I don't see how you can test this behavior without figuring out how to get a 'perfect' number to warn but not crash... The only way to validate that I would expect would be to do some bizarre flag that has us just 'don't run' in the case where the warning is emitted, but that would be strange/only used for the test.

Note that I think you might have an improper comment on the Parser::runWithSufficientStackSpace, else we perhaps wish to combine the Sema.cpp and Parser.cpp implementations in some way.

clang/include/clang/Parse/Parser.h

800

Hmm... The Parser version of this might be used for Template Instantiation? Should we remove the SEMA one and move all uses to the Parser then?

[erichkeane]

clang/lib/Parse/Parser.cpp

2631

Another concern here: Do we properly initialize "Actions" in the case where we don't have a semantic Action? That is, if we are just preprocessing?

[aaron.ballman]

clang/include/clang/Parse/Parser.h

800

Nope, but I could be less silly and just... use the one from Sema... instead of moving it to Parser. Derp!

[aaron.ballman]

Simplify the implementation by using the facilities Sema already exposes. The behavior remains the same:

F:\source\llvm-project>llvm\out\build\x64-Debug\bin\clang.exe -cc1 -fsyntax-only "C:\Users\aballman\OneDrive - Intel Corporation\Desktop\test.c"
C:\Users\aballman\OneDrive - Intel Corporation\Desktop\test.c:8:1: warning: stack nearly exhausted; compilation time may suffer, and crashes due to stack overflow are likely [-Wstack-exhausted]
int PTR6 q3_var = 0;
^
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:

[erichkeane]

Another concern here: Do we properly initialize "Actions" in the case where we don't have a semantic Action? That is, if we are just preprocessing?

Doh! Forgot we don't do 'Parser' in preprocessor mode. LGTM!

clang/docs/ReleaseNotes.rst

- The ``-Wimplicit-function-declaration`` warning diagnostic now defaults to
   an error in C99 and later. Prior to C2x, it may be downgraded to a warning
   with ``-Wno-error=implicit-function-declaration``, or disabled entirely with
   ``-Wno-implicit-function-declaration``. As of C2x, support for implicit
   function declarations has been removed, and the warning options will have no
   effect.
 
 - ``-Wmisexpect`` warns when the branch weights collected during profiling
   conflict with those added by ``llvm.expect``.
+- Clang now checks for stack resource exhaustion when recursively parsing
+  declarators in order to give a diagnostic before we run out of stack space.
+  This fixes `Issue 51642 <https://github.com/llvm/llvm-project/issues/51642>`_.
 
 Non-comprehensive list of changes in this release
 -------------------------------------------------
 - Improve __builtin_dump_struct:
   - Support bitfields in struct and union.
   - Improve the dump format, dump both bitwidth(if its a bitfield) and field value.
   - Remove anonymous tag locations.
   - Beautify dump format, add indent for nested struct and struct members.

clang/include/clang/Parse/Parser.h

private:
   /// Note that this differs from the Preprocessor's LookAhead method, because
   /// the Parser always has one token lexed that the preprocessor doesn't.
   ///
   const Token &GetLookAheadToken(unsigned N) {
     if (N == 0 || Tok.is(tok::eof)) return Tok;
     return PP.LookAhead(N-1);
   }
 
+  /// Warn that the stack is nearly exhausted.
+  void warnStackExhausted(SourceLocation Loc);
+
+  /// Run some code with "sufficient" stack space. (Currently, at least 256K is
+  /// guaranteed). Produces a warning if we're low on stack space and allocates
+  /// more in that case. Use this in code that may recurse deeply (for example,
+  /// in template instantiation) to avoid stack overflow.
+  void runWithSufficientStackSpace(SourceLocation Loc,
+                                   llvm::function_ref<void()> Fn);
+
 public:
   /// NextToken - This peeks ahead one token and returns it without
   /// consuming it.
   const Token &NextToken() {
     return PP.LookAhead(0);
   }
 
   /// getTypeAnnotation - Read a parsed type out of an annotation token.

clang/lib/Parse/ParseDecl.cpp

       assert(PrevSpec && "Method did not return previous specifier!");
       Diag(Tok, DiagID) << PrevSpec;
     }
     EndLoc = ConsumeToken();
   }
 }
 
 /// ParseDeclarator - Parse and verify a newly-initialized declarator.
-///
 void Parser::ParseDeclarator(Declarator &D) {
   /// This implements the 'declarator' production in the C grammar, then checks
   /// for well-formedness and issues diagnostics.
-  ParseDeclaratorInternal(D, &Parser::ParseDirectDeclarator);
+  runWithSufficientStackSpace(D.getBeginLoc(), [&] {
+    ParseDeclaratorInternal(D, &Parser::ParseDirectDeclarator);
+  });
 }
 
 static bool isPtrOperatorToken(tok::TokenKind Kind, const LangOptions &Lang,
                                DeclaratorContext TheContext) {
   if (Kind == tok::star || Kind == tok::caret)
     return true;
 
   // OpenCL 2.0 and later define this keyword.

 
       SourceLocation StarLoc = ConsumeToken();
       D.SetRangeEnd(StarLoc);
       DeclSpec DS(AttrFactory);
       ParseTypeQualifierListOpt(DS);
       D.ExtendWithDeclSpec(DS);
 
       // Recurse to parse whatever is left.
-      ParseDeclaratorInternal(D, DirectDeclParser);
+      runWithSufficientStackSpace(D.getBeginLoc(), [&] {
+        ParseDeclaratorInternal(D, DirectDeclParser);
+      });
 
       // Sema will have to catch (syntactically invalid) pointers into global
       // scope. It has to catch pointers into namespace scope anyway.
       D.AddTypeInfo(DeclaratorChunk::getMemberPointer(
                         SS, DS.getTypeQualifiers(), StarLoc, DS.getEndLoc()),
                     std::move(DS.getAttributes()),
                     /* Don't replace range end. */ SourceLocation());
       return;

     unsigned Reqs = AR_CXX11AttributesParsed | AR_DeclspecAttributesParsed |
                     ((D.getContext() != DeclaratorContext::CXXNew)
                          ? AR_GNUAttributesParsed
                          : AR_GNUAttributesParsedAndRejected);
     ParseTypeQualifierListOpt(DS, Reqs, true, !D.mayOmitIdentifier());
     D.ExtendWithDeclSpec(DS);
 
     // Recursively parse the declarator.
-    ParseDeclaratorInternal(D, DirectDeclParser);
+    runWithSufficientStackSpace(
+        D.getBeginLoc(), [&] { ParseDeclaratorInternal(D, DirectDeclParser); });
     if (Kind == tok::star)
       // Remember that we parsed a pointer type, and remember the type-quals.
       D.AddTypeInfo(DeclaratorChunk::getPointer(
                         DS.getTypeQualifiers(), Loc, DS.getConstSpecLoc(),
                         DS.getVolatileSpecLoc(), DS.getRestrictSpecLoc(),
                         DS.getAtomicSpecLoc(), DS.getUnalignedSpecLoc()),
                     std::move(DS.getAttributes()), SourceLocation());
     else

              diag::err_invalid_reference_qualifier_application) << "volatile";
       // 'restrict' is permitted as an extension.
       if (DS.getTypeQualifiers() & DeclSpec::TQ_atomic)
         Diag(DS.getAtomicSpecLoc(),
              diag::err_invalid_reference_qualifier_application) << "_Atomic";
     }
 
     // Recursively parse the declarator.
-    ParseDeclaratorInternal(D, DirectDeclParser);
+    runWithSufficientStackSpace(
+        D.getBeginLoc(), [&] { ParseDeclaratorInternal(D, DirectDeclParser); });
 
     if (D.getNumTypeObjects() > 0) {
       // C++ [dcl.ref]p4: There shall be no references to references.
       DeclaratorChunk& InnerChunk = D.getTypeObject(D.getNumTypeObjects() - 1);
       if (InnerChunk.Kind == DeclaratorChunk::Reference) {
         if (const IdentifierInfo *II = D.getIdentifier())
           Diag(InnerChunk.Loc, diag::err_illegal_decl_reference_to_reference)
            << II;

clang/lib/Parse/Parser.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Parse/Parser.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/FileManager.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Parse/ParseDiagnostic.h"
 #include "clang/Parse/RAIIObjectsForParser.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/Scope.h"
 #include "llvm/Support/Path.h"
 using namespace clang;
 

       continue;
     default:
       return false;
     }
   }
   return false;
 }
 
+void Parser::warnStackExhausted(SourceLocation Loc) {
+  // Only warn about this once.
+  if (!Actions.WarnedStackExhausted) {
+    Diag(Loc, diag::warn_stack_exhausted);
+    Actions.WarnedStackExhausted = true;
+  }
+}
+
+void Parser::runWithSufficientStackSpace(SourceLocation Loc,
+                                         llvm::function_ref<void()> Fn) {
+  clang::runWithSufficientStackSpace([&] { warnStackExhausted(Loc); }, Fn);
+}
+
 bool BalancedDelimiterTracker::diagnoseOverflow() {
   P.Diag(P.Tok, diag::err_bracket_depth_exceeded)
     << P.getLangOpts().BracketDepth;
   P.Diag(P.Tok, diag::note_bracket_depth);
   P.cutOffParsing();
   return true;
 }
 
 bool BalancedDelimiterTracker::expectAndConsume(unsigned DiagID,
                                                 const char *Msg,
                                                 tok::TokenKind SkipToTok) {
   LOpen = P.Tok.getLocation();
   if (P.ExpectAndConsume(Kind, DiagID, Msg)) {

clang/test/Parser/declarators-recursion-crash.c

+// RUN: not %clang_cc1 %s -fsyntax-only -verify
+
+#define PTR1 * * * * * * * * * *
+#define PTR2 PTR1 PTR1 PTR1 PTR1 PTR1 PTR1 PTR1 PTR1 PTR1 PTR1
+#define PTR3 PTR2 PTR2 PTR2 PTR2 PTR2 PTR2 PTR2 PTR2 PTR2 PTR2
+#define PTR4 PTR3 PTR3 PTR3 PTR3 PTR3 PTR3 PTR3 PTR3 PTR3 PTR3
+#define PTR5 PTR4 PTR4 PTR4 PTR4 PTR4 PTR4 PTR4 PTR4 PTR4 PTR4
+#define PTR6 PTR5 PTR5 PTR5 PTR5 PTR5 PTR5 PTR5 PTR5 PTR5 PTR5
+
+int PTR6 q3_var = 0; // expected-warning {{stack nearly exhausted; compilation time may suffer, and crashes due to stack overflow are likely}}