[analyzer] Fix infinite recursion in printing macros

[bruntib]

Summary

#define f(y) x
#define x f(x)
int main() { x; }

This example results a compilation error since "x" in the first line was not defined earlier. However, the macro expression printer goes to an infinite recursion on this example.

[Szelethus]

Is there a chance of obtaining a testcase for this? I would very strongly prefer one.

[bruntib]

I added a test case for this recursive case. There is also a TODO in the code indicating the place where an additional fix will be required.

[Szelethus]

Well, yea, getting rid of a crash is great, it's kind of bummer that can't expand the macro properly in the testfile. I really fear that we need a far greater overhaul of this entire effort to support them properly -- which should be the task of another patch.

Thanks!

lib/StaticAnalyzer/Core/PlistDiagnostics.cpp

 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/TokenConcatenation.h"
 #include "clang/Rewrite/Core/HTMLRewrite.h"
 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
 #include "clang/StaticAnalyzer/Core/IssueHash.h"
 #include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 
 using namespace clang;
 using namespace ento;
 using namespace markup;
 
 //===----------------------------------------------------------------------===//

 ///   #define PRINT(x) print(x)
 ///   #define DO_SOMETHING(str) PRINT(str)
 ///
 ///   DO_SOMETHING("Cute panda cubs.");
 ///
 /// As we expand the last line, we'll immediately replace PRINT(str) with
 /// print(x). The information that both 'str' and 'x' refers to the same string
 /// is an information we have to forward, hence the argument \p PrevArgs.
-static std::string getMacroNameAndPrintExpansion(TokenPrinter &Printer,
-                                                 SourceLocation MacroLoc,
-                                                 const Preprocessor &PP,
-                                                 const MacroArgMap &PrevArgs);
+///
+/// To avoid infinite recursion we maintain the already processed tokens in
+/// a set. This is carried as a parameter through the recursive calls. The set
+/// is extended with the currently processed token and after processing it, the
+/// token is removed. If the token is already in the set, then recursion stops:
+///
+/// #define f(y) x
+/// #define x f(x)
+static std::string getMacroNameAndPrintExpansion(
+    TokenPrinter &Printer,
+    const MacroArgMap &PrevArgs,
+    llvm::SmallPtrSet<IdentifierInfo *, 8> &AlreadyProcessedTokens);
 
 /// Retrieves the name of the macro and what it's arguments expand into
 /// at \p ExpanLoc.
 ///
 /// For example, for the following macro expansion:
 ///
 ///   #define SET_TO_NULL(x) x = 0
 ///   #define NOT_SUSPICIOUS(a) \

 //===----------------------------------------------------------------------===//
 
 static ExpansionInfo getExpandedMacro(SourceLocation MacroLoc,
                                       const Preprocessor &PP) {
 
   llvm::SmallString<200> ExpansionBuf;
   llvm::raw_svector_ostream OS(ExpansionBuf);
   TokenPrinter Printer(OS, PP);
+  llvm::SmallPtrSet<IdentifierInfo*, 8> AlreadyProcessedTokens;
 
-  return { getMacroNameAndPrintExpansion(Printer, MacroLoc, PP, MacroArgMap{}),
+  return { getMacroNameAndPrintExpansion(Printer, MacroLoc, PP, MacroArgMap{},
+                                         AlreadyProcessedTokens),
            OS.str() };
 }
 
-static std::string getMacroNameAndPrintExpansion(TokenPrinter &Printer,
-                                                 SourceLocation MacroLoc,
-                                                 const Preprocessor &PP,
-                                                 const MacroArgMap &PrevArgs) {
+static std::string getMacroNameAndPrintExpansion(
+    TokenPrinter &Printer,
+    const MacroArgMap &PrevArgs,
+    llvm::SmallPtrSet<IdentifierInfo *, 8> &AlreadyProcessedTokens) {
 
   const SourceManager &SM = PP.getSourceManager();
 
   MacroNameAndArgs Info = getMacroNameAndArgs(SM.getExpansionLoc(MacroLoc), PP);
+  IdentifierInfo* IDInfo = PP.getIdentifierInfo(Info.Name);
+
+  if (AlreadyProcessedTokens.find(IDInfo) != AlreadyProcessedTokens.end())
+    return Info.Name;
+  AlreadyProcessedTokens.insert(IDInfo);
 
   // Manually expand its arguments from the previous macro.
   Info.Args.expandFromPrevMacro(PrevArgs);
 
   // Iterate over the macro's tokens and stringify them.
   for (auto It = Info.MI->tokens_begin(), E = Info.MI->tokens_end(); It != E;
        ++It) {
     Token T = *It;
 
     // If this token is not an identifier, we only need to print it.
     if (T.isNot(tok::identifier)) {
       Printer.printToken(T);
       continue;
     }
 
     const auto *II = T.getIdentifierInfo();
     assert(II &&
           "This token is an identifier but has no IdentifierInfo!");
 
     // If this token is a macro that should be expanded inside the currect
     // macro.
     if (const MacroInfo *MI =
                          getMacroInfoForLocation(PP, SM, II, T.getLocation())) {
-      getMacroNameAndPrintExpansion(Printer, T.getLocation(), PP, Info.Args);
+      getMacroNameAndPrintExpansion(Printer, T.getLocation(), PP, Info.Args,
+                                    AlreadyProcessedTokens);
 
       // If this is a function-like macro, skip its arguments, as
       // getExpandedMacro() already printed them. If this is the case, let's
       // first jumo to the '(' token.
       if (MI->getNumParams() != 0)
         It = getMatchingRParen(++It, E);
       continue;
     }
if (ArgMapIt != Info.Args.end()) {
 
         const auto *MI = PP.getMacroInfo(ArgII);
         if (!MI) {
           Printer.printToken(*ArgIt);
           continue;
         }
 
         getMacroNameAndPrintExpansion(Printer, ArgIt->getLocation(), PP,
-                                      Info.Args);
+                                      Info.Args, AlreadyProcessedTokens);
         if (MI->getNumParams() != 0)
           ArgIt = getMatchingRParen(++ArgIt, ArgEnd);
       }
       continue;
     }
 
     // If control reached here, then this token isn't a macro identifier, nor an
     // unexpanded macro argument that we need to handle, print it.
     Printer.printToken(T);
   }
 
+  AlreadyProcessedTokens.erase(IDInfo);
+
   return Info.Name;
 }
 
 static MacroNameAndArgs getMacroNameAndArgs(SourceLocation ExpanLoc,
                                             const Preprocessor &PP) {
 
   const SourceManager &SM = PP.getSourceManager();
   const LangOptions &LangOpts = PP.getLangOpts();