[clang-tidy] refactor bugprone-exception-escape analysis into class

[JonasToth]

Summary

The check bugprone-exception-escape does an AST-based analysis to determine
if a function might throw an exception and warns based on that information.
The analysis part is refactored into a standalone class similiar to
ExprMutAnalyzer that is generally useful.
I intent to use that class in a new check to automatically introduce noexcept
if possible.

bugprone-exception-escape uses the consistent semicolon-separated list for
configuration now as well.

[lebedev.ri]

Two passing-by remarks:

1. I would *love* for this check to produce less cryptic reports :) It currently does not output any details whatsoever. It's really unhelpful.
2. It would be great for it to be generalized to not only detect the escaping of exceptions out of functions, but out of "statements" too. Namely, i would love some better handling of openmp directives. I might look into that later.

[JonasToth]

In D57100#1367813, @lebedev.ri wrote:

Two passing-by remarks:

1. I would *love* for this check to produce less cryptic reports :) It currently does not output any details whatsoever. It's really unhelpful.

I would do that in a second refactoring. As it is now possible to have state within the analysis it should be possible to extract a path that lead to the exception. I think the 'highest' throwing function should be noted as the source.

void indirect_throw() { call_something_throwing(); }
void diagnose() noexcept {
// warning: this function can throw

  indirect_throw();
  // note: this function is not safe to call
}

2. It would be great for it to be generalized to not only detect the escaping of exceptions out of functions, but out of "statements" too. Namely, i would love some better handling of openmp directives. I might look into that later.

The internals can handle Stmt already and do traverse all statements of a FunctionDecl, so it should be possible to expose that.
Can OpenMP directives throw?

I think making this class and its interface is the first step to both features, incremental improvements are then easier to do.

[JonasToth]

• adjust doc to say semicolon separated list instead of comma

[lebedev.ri]

In D57100#1367817, @JonasToth wrote:

In D57100#1367813, @lebedev.ri wrote:

2. It would be great for it to be generalized to not only detect the escaping of exceptions out of functions, but out of "statements" too. Namely, i would love some better handling of openmp directives. I might look into that later.

The internals can handle Stmt already and do traverse all statements of a FunctionDecl, so it should be possible to expose that.
Can OpenMP directives throw?

The other way around, it's the same problem as with exceptions escaping noexcept functions,
but just with narrower scope - a statement - as opposed to whole function

I think making this class and its interface is the first step to both features, incremental improvements are then easier to do.

Yep, don't want to drag anything sideways, just voicing some thoughts.

[JonasToth]

• [Fix] make class name correct

[lebedev.ri]

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

35 ↗

(On Diff #183131)

Does it also accept ',' delimitter?
If not, i'm not sure how good of an idea it is to break existing configs..

clang-tidy/utils/ExceptionAnalyzer.cpp

1 ↗

(On Diff #183131)

Standard licence blurb missing.

test/clang-tidy/bugprone-exception-escape.cpp

1 ↗

(On Diff #183131)

Hm, this may be a breaking change, and the check existed in 7.0 already.

[JonasToth]

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

35 ↗

(On Diff #183131)

No it doesn't. It is a breaking change but at the same time it is inconsistent and duplicated functionality.
Should be mentioned in release notes, that for sure.

test/clang-tidy/bugprone-exception-escape.cpp

1 ↗

(On Diff #183131)

See above.

[JonasToth]

• add license to exceptionanalyzer

[lebedev.ri]

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

35 ↗

(On Diff #183131)

The thing is, if said list was set (as in user-specified to non-empty), it will be impossible
to use that same .clang-tidy config with clang-tidy <=8 and trunk.
I'm personally not affected, but if i was, i wouldn't think this is a great idea..

Can you at least make the breakage less crippling by also renaming the config field?

[JonasToth]

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

35 ↗

(On Diff #183131)

Oh thats true, i didnt consider the config files. Maybe I just leave it as is.

[lebedev.ri]

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

35 ↗

(On Diff #183131)

I understand the cleanup and the inconsistency and duplicated functionality,
but maybe regardless of the fix, it should be addressed in a separate review?

[lebedev.ri]

To me, modulo the "IgnoredExceptions" change, this seems like a straight-forward refactoring.

clang-tidy/utils/ExceptionAnalyzer.h

25 ↗

(On Diff #183134)

What is the test plan for this utility class, BTW?
Ensuring that the main user (bugprone-exception-escape) has sufficiently full test coverage?

[JonasToth]

• revert the option configuration change for comma/semicolon

[JonasToth]

Reverted the changes. Maybe the comma thingie will just stay as is ;)

clang-tidy/utils/ExceptionAnalyzer.h

25 ↗

(On Diff #183134)

Simplify code first, generate a trace, use it in other context (modernize-patch you have seen already).

[JonasToth]

• revert doc change as well

[baloghadamsoftware]

Hello! I am glad to see that this check gets improved by the community. I also think a "modernize" check which marks functions with noexcept is also useful.

As for the comma or semicolon, I think semicolon would be better. I see that this part is reverted now, but is there any reason for using std::string instead of llvm::StringRef? I always thought this latter is the standard for LLVM code wherever possible.

[JonasToth]

In D57100#1373430, @baloghadamsoftware wrote:

Hello! I am glad to see that this check gets improved by the community. I also think a "modernize" check which marks functions with noexcept is also useful.

Great to hear!

As for the comma or semicolon, I think semicolon would be better. I see that this part is reverted now, but is there any reason for using std::string instead of llvm::StringRef? I always thought this latter is the standard for LLVM code wherever possible.

Which part to you mean? The original semicolon-splitting?
I think there the issue is, that StringRef is just a handle, but if you split a big string into smaller ones you want the result to be owning its own memory instead of just pointing to a span in the original full string.
Even though that would be correct in some cases it has a subtle dangling-bug if you work further with the result of the split or the underlying string disappears for some reason.
Otherwise StringRef is definitly the goto-class for string operations (that dont change underlying memory).

For now the comma-vs-semicolon thingie will stay as is, because its a breaking change in the configurations and the gain for switching to semicolon is small, whereas the pain to figuring out that changed is big.

@baloghadamsoftware Do you see any problems with the refactoring, especially the new FunctionDecl*-Caching is not exactly a refactoring. If you have any thoughts on that would be great to hear!

[lebedev.ri]

Looked this over once more. To me this looks pretty straight-forward.
The caching seems ok, too. As long as ExceptionAnalyzer does not outlive
it's TU, everything should be fine.

@baloghadamsoftware - thoughts?

clang-tidy/bugprone/ExceptionEscapeCheck.cpp

73–81 ↗

(On Diff #183490)

I think you could do early-exit.
Also, if you de-split the string, clang-format might produce better formatting.

[baloghadamsoftware]

In D57100#1373440, @JonasToth wrote:

@baloghadamsoftware Do you see any problems with the refactoring, especially the new FunctionDecl*-Caching is not exactly a refactoring. If you have any thoughts on that would be great to hear!

Yes, it looks a good improvement, I expect another huge speedup. (We had a previous huge speedup after I optimized the matcher expression in 7.0.1 because in 7.0.0 it seemed to hang, it was really bad).

clang-tidy/utils/ExceptionAnalyzer.h

23 ↗

(On Diff #183490)

std::bad_alloc is hardwired to ignore, so I think this comment should be rephrased.

[JonasToth]

In D57100#1377687, @baloghadamsoftware wrote:

In D57100#1373440, @JonasToth wrote:

@baloghadamsoftware Do you see any problems with the refactoring, especially the new FunctionDecl*-Caching is not exactly a refactoring. If you have any thoughts on that would be great to hear!

Yes, it looks a good improvement, I expect another huge speedup. (We had a previous huge speedup after I optimized the matcher expression in 7.0.1 because in 7.0.0 it seemed to hang, it was really bad).

I revisited the reproducer for that bug and there was no bigger performance gain with the new version in bugprone-exception-escape. But it didnt get worse either :)

[JonasToth]

• [Misc] rewrite parts of a comment that were unprecise.

clang-tools-extra/trunk/clang-tidy/bugprone/ExceptionEscapeCheck.h

-//===--- ExceptionEscapeCheck.h - clang-tidy---------------------*- C++ -*-===//
+//===--- ExceptionEscapeCheck.h - clang-tidy --------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_EXCEPTION_ESCAPE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_EXCEPTION_ESCAPE_H
 
 #include "../ClangTidy.h"
-
+#include "../utils/ExceptionAnalyzer.h"
 #include "llvm/ADT/StringSet.h"
 
 namespace clang {
 namespace tidy {
 namespace bugprone {
 
 /// Finds functions which should not throw exceptions: Destructors, move
 /// constructors, move assignment operators, the main() function,
public:
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
 
 private:
   std::string RawFunctionsThatShouldNotThrow;
   std::string RawIgnoredExceptions;
 
   llvm::StringSet<> FunctionsThatShouldNotThrow;
-  llvm::StringSet<> IgnoredExceptions;
+  utils::ExceptionAnalyzer Tracer;
 };
 
 } // namespace bugprone
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_EXCEPTION_ESCAPE_H

clang-tools-extra/trunk/clang-tidy/bugprone/ExceptionEscapeCheck.cpp

-//===--- ExceptionEscapeCheck.cpp - clang-tidy-----------------------------===//
+//===--- ExceptionEscapeCheck.cpp - clang-tidy ----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ExceptionEscapeCheck.h"
 
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
-
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringSet.h"
 
 using namespace clang::ast_matchers;
 
-namespace {
-typedef llvm::SmallVector<const clang::Type *, 8> TypeVec;
-} // namespace
-
 namespace clang {
-
-static bool isBaseOf(const Type *DerivedType, const Type *BaseType) {
-  const auto *DerivedClass = DerivedType->getAsCXXRecordDecl();
-  const auto *BaseClass = BaseType->getAsCXXRecordDecl();
-  if (!DerivedClass || !BaseClass)
-    return false;
-
-  return !DerivedClass->forallBases(
-      [BaseClass](const CXXRecordDecl *Cur) { return Cur != BaseClass; });
-}
-
-static const TypeVec
-throwsException(const Stmt *St, const TypeVec &Caught,
-                llvm::SmallSet<const FunctionDecl *, 32> &CallStack);
-
-static const TypeVec
-throwsException(const FunctionDecl *Func,
-                llvm::SmallSet<const FunctionDecl *, 32> &CallStack) {
-  if (CallStack.count(Func))
-    return TypeVec();
-
-  if (const Stmt *Body = Func->getBody()) {
-    CallStack.insert(Func);
-    const TypeVec Result = throwsException(Body, TypeVec(), CallStack);
-    CallStack.erase(Func);
-    return Result;
-  }
-
-  TypeVec Result;
-  if (const auto *FPT = Func->getType()->getAs<FunctionProtoType>()) {
-    for (const QualType Ex : FPT->exceptions()) {
-      Result.push_back(Ex.getTypePtr());
-    }
-  }
-  return Result;
-}
-
-static const TypeVec
-throwsException(const Stmt *St, const TypeVec &Caught,
-                llvm::SmallSet<const FunctionDecl *, 32> &CallStack) {
-  TypeVec Results;
-
-  if (!St)
-    return Results;
-
-  if (const auto *Throw = dyn_cast<CXXThrowExpr>(St)) {
-    if (const auto *ThrownExpr = Throw->getSubExpr()) {
-      const auto *ThrownType =
-          ThrownExpr->getType()->getUnqualifiedDesugaredType();
-      if (ThrownType->isReferenceType()) {
-        ThrownType = ThrownType->castAs<ReferenceType>()
-                         ->getPointeeType()
-                         ->getUnqualifiedDesugaredType();
-      }
-      if (const auto *TD = ThrownType->getAsTagDecl()) {
-        if (TD->getDeclName().isIdentifier() && TD->getName() == "bad_alloc"
-            && TD->isInStdNamespace())
-          return Results;
-      }
-      Results.push_back(ThrownExpr->getType()->getUnqualifiedDesugaredType());
-    } else {
-      Results.append(Caught.begin(), Caught.end());
-    }
-  } else if (const auto *Try = dyn_cast<CXXTryStmt>(St)) {
-    TypeVec Uncaught = throwsException(Try->getTryBlock(), Caught, CallStack);
-    for (unsigned i = 0; i < Try->getNumHandlers(); ++i) {
-      const CXXCatchStmt *Catch = Try->getHandler(i);
-      if (!Catch->getExceptionDecl()) {
-        const TypeVec Rethrown =
-            throwsException(Catch->getHandlerBlock(), Uncaught, CallStack);
-        Results.append(Rethrown.begin(), Rethrown.end());
-        Uncaught.clear();
-      } else {
-        const auto *CaughtType =
-            Catch->getCaughtType()->getUnqualifiedDesugaredType();
-        if (CaughtType->isReferenceType()) {
-          CaughtType = CaughtType->castAs<ReferenceType>()
-                           ->getPointeeType()
-                           ->getUnqualifiedDesugaredType();
-        }
-        auto NewEnd =
-            llvm::remove_if(Uncaught, [&CaughtType](const Type *ThrownType) {
-              return ThrownType == CaughtType ||
-                     isBaseOf(ThrownType, CaughtType);
-            });
-        if (NewEnd != Uncaught.end()) {
-          Uncaught.erase(NewEnd, Uncaught.end());
-          const TypeVec Rethrown = throwsException(
-              Catch->getHandlerBlock(), TypeVec(1, CaughtType), CallStack);
-          Results.append(Rethrown.begin(), Rethrown.end());
-        }
-      }
-    }
-    Results.append(Uncaught.begin(), Uncaught.end());
-  } else if (const auto *Call = dyn_cast<CallExpr>(St)) {
-    if (const FunctionDecl *Func = Call->getDirectCallee()) {
-      TypeVec Excs = throwsException(Func, CallStack);
-      Results.append(Excs.begin(), Excs.end());
-    }
-  } else {
-    for (const Stmt *Child : St->children()) {
-      TypeVec Excs = throwsException(Child, Caught, CallStack);
-      Results.append(Excs.begin(), Excs.end());
-    }
-  }
-  return Results;
-}
-
-static const TypeVec throwsException(const FunctionDecl *Func) {
-  llvm::SmallSet<const FunctionDecl *, 32> CallStack;
-  return throwsException(Func, CallStack);
-}
-
-namespace ast_matchers {
-AST_MATCHER_P(FunctionDecl, throws, internal::Matcher<Type>, InnerMatcher) {
-  TypeVec ExceptionList = throwsException(&Node);
-  auto NewEnd = llvm::remove_if(
-      ExceptionList, [this, Finder, Builder](const Type *Exception) {
-        return !InnerMatcher.matches(*Exception, Finder, Builder);
-      });
-  ExceptionList.erase(NewEnd, ExceptionList.end());
-  return ExceptionList.size();
-}
-
-AST_MATCHER_P(Type, isIgnored, llvm::StringSet<>, IgnoredExceptions) {
-  if (const auto *TD = Node.getAsTagDecl()) {
-    if (TD->getDeclName().isIdentifier())
-      return IgnoredExceptions.count(TD->getName()) > 0;
-  }
-  return false;
-}
-
+namespace {
 AST_MATCHER_P(FunctionDecl, isEnabled, llvm::StringSet<>,
               FunctionsThatShouldNotThrow) {
   return FunctionsThatShouldNotThrow.count(Node.getNameAsString()) > 0;
 }
-} // namespace ast_matchers
+} // namespace
 
 namespace tidy {
 namespace bugprone {
-
 ExceptionEscapeCheck::ExceptionEscapeCheck(StringRef Name,
                                            ClangTidyContext *Context)
     : ClangTidyCheck(Name, Context), RawFunctionsThatShouldNotThrow(Options.get(
                                          "FunctionsThatShouldNotThrow", "")),
       RawIgnoredExceptions(Options.get("IgnoredExceptions", "")) {
   llvm::SmallVector<StringRef, 8> FunctionsThatShouldNotThrowVec,
       IgnoredExceptionsVec;
   StringRef(RawFunctionsThatShouldNotThrow)
       .split(FunctionsThatShouldNotThrowVec, ",", -1, false);
   FunctionsThatShouldNotThrow.insert(FunctionsThatShouldNotThrowVec.begin(),
                                      FunctionsThatShouldNotThrowVec.end());
+
+  llvm::StringSet<> IgnoredExceptions;
   StringRef(RawIgnoredExceptions).split(IgnoredExceptionsVec, ",", -1, false);
   IgnoredExceptions.insert(IgnoredExceptionsVec.begin(),
                            IgnoredExceptionsVec.end());
+  Tracer.ignoreExceptions(std::move(IgnoredExceptions));
 }
 
 void ExceptionEscapeCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "FunctionsThatShouldNotThrow",
                 RawFunctionsThatShouldNotThrow);
   Options.store(Opts, "IgnoredExceptions", RawIgnoredExceptions);
 }
 
 void ExceptionEscapeCheck::registerMatchers(MatchFinder *Finder) {
   if (!getLangOpts().CPlusPlus || !getLangOpts().CXXExceptions)
     return;
 
   Finder->addMatcher(
       functionDecl(anyOf(isNoThrow(), cxxDestructorDecl(),
                          cxxConstructorDecl(isMoveConstructor()),
                          cxxMethodDecl(isMoveAssignmentOperator()),
                          hasName("main"), hasName("swap"),
-                         isEnabled(FunctionsThatShouldNotThrow)),
-                   throws(unless(isIgnored(IgnoredExceptions))))
+                         isEnabled(FunctionsThatShouldNotThrow)))
           .bind("thrower"),
       this);
 }
 
 void ExceptionEscapeCheck::check(const MatchFinder::MatchResult &Result) {
-  const FunctionDecl *MatchedDecl =
-      Result.Nodes.getNodeAs<FunctionDecl>("thrower");
+  const auto *MatchedDecl = Result.Nodes.getNodeAs<FunctionDecl>("thrower");
+
   if (!MatchedDecl)
     return;
 
+  if (Tracer.throwsException(MatchedDecl))
     // FIXME: We should provide more information about the exact location where
     // the exception is thrown, maybe the full path the exception escapes
-  diag(MatchedDecl->getLocation(), "an exception may be thrown in function %0 "
-       "which should not throw exceptions") << MatchedDecl;
+    diag(MatchedDecl->getLocation(),
+         "an exception may be thrown in function %0 "
+
+         "which should not throw exceptions")
+        << MatchedDecl;
 }
 
 } // namespace bugprone
 } // namespace tidy
 } // namespace clang

clang-tools-extra/trunk/clang-tidy/utils/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyUtils
   ASTUtils.cpp
   DeclRefExprUtils.cpp
+  ExceptionAnalyzer.cpp
   ExprSequence.cpp
   FixItHintUtils.cpp
   HeaderFileExtensionsUtils.cpp
   HeaderGuard.cpp
   IncludeInserter.cpp
   IncludeSorter.cpp
   LexerUtils.cpp
   NamespaceAliaser.cpp

clang-tools-extra/trunk/clang-tidy/utils/ExceptionAnalyzer.h

+//===--- ExceptionAnalyzer.h - clang-tidy -----------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_UTILS_EXCEPTION_ANALYZER_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_UTILS_EXCEPTION_ANALYZER_H
+
+#include "clang/AST/ASTContext.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/StringSet.h"
+
+namespace clang {
+namespace tidy {
+namespace utils {
+
+/// This class analysis if a `FunctionDecl` can in principle throw an exception,
+/// either directly or indirectly.
+/// It can be configured to ignore custom exception types.
+class ExceptionAnalyzer {
+public:
+  ExceptionAnalyzer() = default;
+
+  bool throwsException(const FunctionDecl *Func);
+  void ignoreExceptions(llvm::StringSet<> ExceptionNames) {
+    IgnoredExceptions = std::move(ExceptionNames);
+  }
+
+private:
+  using TypeVec = llvm::SmallVector<const Type *, 8>;
+
+  TypeVec throwsException(const FunctionDecl *Func,
+                          llvm::SmallSet<const FunctionDecl *, 32> &CallStack);
+  TypeVec throwsException(const Stmt *St, const TypeVec &Caught,
+                          llvm::SmallSet<const FunctionDecl *, 32> &CallStack);
+  bool isIgnoredExceptionType(const Type *Exception);
+
+  llvm::StringSet<> IgnoredExceptions;
+  llvm::DenseMap<const FunctionDecl *, bool> FunctionCache;
+};
+} // namespace utils
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_UTILS_EXCEPTION_ANALYZER_H

clang-tools-extra/trunk/clang-tidy/utils/ExceptionAnalyzer.cpp

+//===--- ExceptionAnalyzer.cpp - clang-tidy -------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ExceptionAnalyzer.h"
+
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+namespace clang {
+static bool isBaseOf(const Type *DerivedType, const Type *BaseType) {
+  const auto *DerivedClass = DerivedType->getAsCXXRecordDecl();
+  const auto *BaseClass = BaseType->getAsCXXRecordDecl();
+  if (!DerivedClass || !BaseClass)
+    return false;
+
+  return !DerivedClass->forallBases(
+      [BaseClass](const CXXRecordDecl *Cur) { return Cur != BaseClass; });
+}
+
+namespace tidy {
+namespace utils {
+
+ExceptionAnalyzer::TypeVec ExceptionAnalyzer::throwsException(
+    const FunctionDecl *Func,
+    llvm::SmallSet<const FunctionDecl *, 32> &CallStack) {
+  if (CallStack.count(Func))
+    return TypeVec();
+
+  if (const Stmt *Body = Func->getBody()) {
+    CallStack.insert(Func);
+    const TypeVec Result = throwsException(Body, TypeVec(), CallStack);
+    CallStack.erase(Func);
+    return Result;
+  }
+
+  TypeVec Result;
+  if (const auto *FPT = Func->getType()->getAs<FunctionProtoType>()) {
+    for (const QualType Ex : FPT->exceptions()) {
+      Result.push_back(Ex.getTypePtr());
+    }
+  }
+  return Result;
+}
+
+ExceptionAnalyzer::TypeVec ExceptionAnalyzer::throwsException(
+    const Stmt *St, const TypeVec &Caught,
+    llvm::SmallSet<const FunctionDecl *, 32> &CallStack) {
+  TypeVec Results;
+
+  if (!St)
+    return Results;
+
+  if (const auto *Throw = dyn_cast<CXXThrowExpr>(St)) {
+    if (const auto *ThrownExpr = Throw->getSubExpr()) {
+      const auto *ThrownType =
+          ThrownExpr->getType()->getUnqualifiedDesugaredType();
+      if (ThrownType->isReferenceType()) {
+        ThrownType = ThrownType->castAs<ReferenceType>()
+                         ->getPointeeType()
+                         ->getUnqualifiedDesugaredType();
+      }
+      if (const auto *TD = ThrownType->getAsTagDecl()) {
+        if (TD->getDeclName().isIdentifier() && TD->getName() == "bad_alloc" &&
+            TD->isInStdNamespace())
+          return Results;
+      }
+      Results.push_back(ThrownExpr->getType()->getUnqualifiedDesugaredType());
+    } else {
+      Results.append(Caught.begin(), Caught.end());
+    }
+  } else if (const auto *Try = dyn_cast<CXXTryStmt>(St)) {
+    TypeVec Uncaught = throwsException(Try->getTryBlock(), Caught, CallStack);
+    for (unsigned i = 0; i < Try->getNumHandlers(); ++i) {
+      const CXXCatchStmt *Catch = Try->getHandler(i);
+      if (!Catch->getExceptionDecl()) {
+        const TypeVec Rethrown =
+            throwsException(Catch->getHandlerBlock(), Uncaught, CallStack);
+        Results.append(Rethrown.begin(), Rethrown.end());
+        Uncaught.clear();
+      } else {
+        const auto *CaughtType =
+            Catch->getCaughtType()->getUnqualifiedDesugaredType();
+        if (CaughtType->isReferenceType()) {
+          CaughtType = CaughtType->castAs<ReferenceType>()
+                           ->getPointeeType()
+                           ->getUnqualifiedDesugaredType();
+        }
+        auto NewEnd =
+            llvm::remove_if(Uncaught, [&CaughtType](const Type *ThrownType) {
+              return ThrownType == CaughtType ||
+                     isBaseOf(ThrownType, CaughtType);
+            });
+        if (NewEnd != Uncaught.end()) {
+          Uncaught.erase(NewEnd, Uncaught.end());
+          const TypeVec Rethrown = throwsException(
+              Catch->getHandlerBlock(), TypeVec(1, CaughtType), CallStack);
+          Results.append(Rethrown.begin(), Rethrown.end());
+        }
+      }
+    }
+    Results.append(Uncaught.begin(), Uncaught.end());
+  } else if (const auto *Call = dyn_cast<CallExpr>(St)) {
+    if (const FunctionDecl *Func = Call->getDirectCallee()) {
+      TypeVec Excs = throwsException(Func, CallStack);
+      Results.append(Excs.begin(), Excs.end());
+    }
+  } else {
+    for (const Stmt *Child : St->children()) {
+      TypeVec Excs = throwsException(Child, Caught, CallStack);
+      Results.append(Excs.begin(), Excs.end());
+    }
+  }
+  return Results;
+}
+
+bool ExceptionAnalyzer::throwsException(const FunctionDecl *Func) {
+  // Check if the function has already been analyzed and reuse that result.
+  if (FunctionCache.count(Func) > 0)
+    return FunctionCache[Func];
+
+  llvm::SmallSet<const FunctionDecl *, 32> CallStack;
+  TypeVec ExceptionList = throwsException(Func, CallStack);
+
+  // Remove all ignored exceptions from the list of exceptions that can be
+  // thrown.
+  auto NewEnd = llvm::remove_if(ExceptionList, [this](const Type *Exception) {
+    return isIgnoredExceptionType(Exception);
+  });
+  ExceptionList.erase(NewEnd, ExceptionList.end());
+
+  // Cache the result of the analysis.
+  bool FunctionThrows = ExceptionList.size() > 0;
+  FunctionCache.insert(std::make_pair(Func, FunctionThrows));
+
+  return FunctionThrows;
+}
+
+bool ExceptionAnalyzer::isIgnoredExceptionType(const Type *Exception) {
+  if (const auto *TD = Exception->getAsTagDecl()) {
+    if (TD->getDeclName().isIdentifier())
+      return IgnoredExceptions.count(TD->getName()) > 0;
+  }
+  return false;
+}
+
+} // namespace utils
+} // namespace tidy
+
+} // namespace clang