[clang][Analysis] ExprMutationAnalyzer: break infinite recursion on recursive function call

[danix800]

Summary

Fixes https://github.com/llvm/llvm-project/issues/62487

[danix800]

Apply git-clang-format

[PiotrZSL]

clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

31

NOTE: This memory allocation could be removed by creating class ExprMutationAnalyzerWithHistory that could keep DeclSet as private object and use ExprMutationAnalyzer as base class.

clang/lib/Analysis/ExprMutationAnalyzer.cpp

574

I would assume that Func should be removed from DeclAnalyzed when leaving scope. Otherwise it may not work to good when for example same function would be called twice.

clang-tools-extra/test/clang-tidy/checkers/readability/use-anyofallof-nocrash.cpp

+// RUN: %check_clang_tidy -std=c++14,c++17 %s readability-use-anyofallof %t --
+
+struct V {
+  V* begin() const;
+  V* end() const;
+};
+
+void bad_all_of(V &elem) {
+  auto rec = [](const auto& e, auto&& self) -> bool {
+    // CHECK-MESSAGES: :[[@LINE+1]]:5: warning: replace loop by 'std::all_of()' [readability-use-anyofallof]
+    for (auto& child : e) {
+      if (!self(child, self)) {
+        return false;
+      }
+    }
+    return true;
+  };
+
+  rec(elem, rec);
+}

clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h

 
 class FunctionParmMutationAnalyzer;
 
+using DeclSet = llvm::DenseSet<const Decl *>;
+
 /// Analyzes whether any mutative operations are applied to an expression within
 /// a given statement.
 class ExprMutationAnalyzer {
 public:
-  ExprMutationAnalyzer(const Stmt &Stm, ASTContext &Context)
-      : Stm(Stm), Context(Context) {}
+  ExprMutationAnalyzer(const Stmt &Stm, ASTContext &Context,
+                       DeclSet *DeclAnalyzed = nullptr)
+      : Stm(Stm), Context(Context), DeclAnalyzed(DeclAnalyzed) {
+    if (nullptr == DeclAnalyzed) {
+      OwningDeclAnalyzed = std::make_unique<DeclSet>();
+      this->DeclAnalyzed = OwningDeclAnalyzed.get();
+    }
+  }
 
   bool isMutated(const Expr *Exp) { return findMutation(Exp) != nullptr; }
   bool isMutated(const Decl *Dec) { return findMutation(Dec) != nullptr; }

       FuncParmAnalyzer;
   ResultMap Results;
   ResultMap PointeeResults;
+  DeclSet *DeclAnalyzed;
+  std::unique_ptr<DeclSet> OwningDeclAnalyzed;
 };
 
 // A convenient wrapper around ExprMutationAnalyzer for analyzing function
 // params.
 class FunctionParmMutationAnalyzer {
 public:
-  FunctionParmMutationAnalyzer(const FunctionDecl &Func, ASTContext &Context);
+  FunctionParmMutationAnalyzer(const FunctionDecl &Func, ASTContext &Context,
+                               DeclSet *DeclAnalyzed = nullptr);
 
   bool isMutated(const ParmVarDecl *Parm) {
     return findMutation(Parm) != nullptr;

clang/lib/Analysis/ExprMutationAnalyzer.cpp

     if (!Func->getBody() || !Func->getPrimaryTemplate())
       return Exp;
 
+    if (DeclAnalyzed->contains(Func)) {
+      return nullptr;
+    }
+    DeclAnalyzed->insert(Func);
+
     const auto *Parm = Nodes.getNodeAs<ParmVarDecl>("parm");
     const ArrayRef<ParmVarDecl *> AllParams =
         Func->getPrimaryTemplate()->getTemplatedDecl()->parameters();

         std::unique_ptr<FunctionParmMutationAnalyzer> &Analyzer =
             FuncParmAnalyzer[Func];
         if (!Analyzer)
-          Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context));
+          Analyzer.reset(new FunctionParmMutationAnalyzer(*Func, Context,
+                                                          DeclAnalyzed));
         if (Analyzer->findMutation(Parm))
           return Exp;
         continue;

 }
 
 FunctionParmMutationAnalyzer::FunctionParmMutationAnalyzer(
-    const FunctionDecl &Func, ASTContext &Context)
-    : BodyAnalyzer(*Func.getBody(), Context) {
+    const FunctionDecl &Func, ASTContext &Context, DeclSet *DeclAnalyzed)
+    : BodyAnalyzer(*Func.getBody(), Context, DeclAnalyzed) {
   if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(&Func)) {
     // CXXCtorInitializer might also mutate Param but they're not part of
     // function body, check them eagerly here since they're typically trivial.

clang/unittests/Analysis/ExprMutationAnalyzerTest.cpp

   EXPECT_FALSE(isMutated(Results, AST.get()));
 }
 
+TEST(ExprMutationAnalyzerTest, RangeForNonArrayByConstRefNoCrash) {
+  const auto AST = buildASTFromCode(R"(
+    struct V {
+      V* begin() const;
+      V* end() const;
+    };
+    void f(V &elem) {
+      auto rec = [](const auto& e, auto&& self) -> bool {
+        for (auto& child : e) {
+          if (!self(child, self)) {
+            return false;
+          }
+        }
+        return true;
+      };
+
+      rec(elem, rec);
+    }
+  )");
+  const auto Results =
+      match(withEnclosingCompound(declRefTo("elem")), AST->getASTContext());
+  EXPECT_FALSE(isMutated(Results, AST.get()));
+}
+
 // section: unevaluated expressions
 
 TEST(ExprMutationAnalyzerTest, UnevaluatedExpressions) {