[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

 #include "clang/AST/AST.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "llvm/ADT/DenseMap.h"
 
 namespace clang {
 
 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; }
   const Stmt *findMutation(const Expr *Exp);
   const Stmt *findMutation(const Decl *Dec);
 
   bool isPointeeMutated(const Expr *Exp) {
     return findPointeeMutation(Exp) != nullptr;
private:
 
   const Stmt &Stm;
   ASTContext &Context;
   llvm::DenseMap<const FunctionDecl *,
                  std::unique_ptr<FunctionParmMutationAnalyzer>>
       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;
   }
   const Stmt *findMutation(const ParmVarDecl *Parm);
 
 private:
   ExprMutationAnalyzer BodyAnalyzer;
   llvm::DenseMap<const ParmVarDecl *, const Stmt *> Results;
 };
 
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_EXPRMUTATIONANALYZER_H

clang/lib/Analysis/ExprMutationAnalyzer.cpp

                   .bind(NodeID<Expr>::value))),
       Stm, Context);
   for (const auto &Nodes : Matches) {
     const auto *Exp = Nodes.getNodeAs<Expr>(NodeID<Expr>::value);
     const auto *Func = Nodes.getNodeAs<FunctionDecl>("func");
     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();
     QualType ParmType =
         AllParams[std::min<size_t>(Parm->getFunctionScopeIndex(),
                                    AllParams.size() - 1)]
             ->getType();
     if (const auto *T = ParmType->getAs<PackExpansionType>())
       ParmType = T->getPattern();
 
     // If param type is forwarding reference, follow into the function
     // definition and see whether the param is mutated inside.
     if (const auto *RefType = ParmType->getAs<RValueReferenceType>()) {
       if (!RefType->getPointeeType().getQualifiers() &&
           RefType->getPointeeType()->getAs<TemplateTypeParmType>()) {
         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;
       }
     }
     // Not forwarding reference.
     return Exp;
   }
   return nullptr;
 }
 
 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.
     for (const CXXCtorInitializer *Init : Ctor->inits()) {
       ExprMutationAnalyzer InitAnalyzer(*Init->getInit(), Context);
       for (const ParmVarDecl *Parm : Ctor->parameters()) {
         if (Results.contains(Parm))
           continue;

clang/unittests/Analysis/ExprMutationAnalyzerTest.cpp

   const auto AST = buildASTFromCode(
       "struct V { const int* begin() const; const int* end() const; };"
       "void f() { V x; for (const int& e : x) e; }");
   const auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   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) {
   auto AST = buildASTFromCode("void f() { int x, y; decltype(x = 10) z = y; }");
   auto Results =
       match(withEnclosingCompound(declRefTo("x")), AST->getASTContext());
   EXPECT_FALSE(isMutated(Results, AST.get()));