[clang-tidy] Optimize query in bugprone-exception-escape

[baloghadamsoftware]

Summary

Checking whether a functions throws indirectly may be very expensive because it needs to visit its whole call graph. Therefore we should first check whether the function is forbidden to throw and only check whether it throws afterward. This also seems to solve bug bug 39167 where the execution time is so long that it seems to hang.

[JonasToth]

This looks reasonable to me but could you please explain a bit what the issue was in the bugreport? So a very deep hierarchy causing the problem makes sense, but why was "ignoring first" the difference maker?
Would it make sense to add a warning in the documentation that this check can be very expensive? And are there measures to speed the process up somehow?

[baloghadamsoftware]

I think that with this optimization it is not so expensive anymore. I do not think it was an endless loop in the bugreport but it was insufferable execution time. Maybe we could speed it up a little more by changing it totally to a width-first CFG visitor. Then we could apply your solution as well (not removing visited function from the call stack) so the algorithm would visit every called function (for every function that should not throw) only once along the shortest path. This would not introduce new false positives neither would it lose true positives.

[JonasToth]

In D53187#1263294, @baloghadamsoftware wrote:

I think that with this optimization it is not so expensive anymore. I do not think it was an endless loop in the bugreport but it was insufferable execution time. Maybe we could speed it up a little more by changing it totally to a width-first CFG visitor. Then we could apply your solution as well (not removing visited function from the call stack) so the algorithm would visit every called function (for every function that should not throw) only once along the shortest path. This would not introduce new false positives neither would it lose true positives.

In the debugging if have seen some functions analyzed thousands of times so I think this would really make a difference. Caching the result might work too?
If you have time for this I would really appreciate if you took a look into!

[baloghadamsoftware]

In D53187#1263323, @JonasToth wrote:

In D53187#1263294, @baloghadamsoftware wrote:

I think that with this optimization it is not so expensive anymore. I do not think it was an endless loop in the bugreport but it was insufferable execution time. Maybe we could speed it up a little more by changing it totally to a width-first CFG visitor. Then we could apply your solution as well (not removing visited function from the call stack) so the algorithm would visit every called function (for every function that should not throw) only once along the shortest path. This would not introduce new false positives neither would it lose true positives.

In the debugging if have seen some functions analyzed thousands of times so I think this would really make a difference. Caching the result might work too?

Thousands? After the query optimization the max was 173, and that only for a single function. The next number was 64.

[JonasToth]

Thousands? After the query optimization the max was 173, and that only for a single function. The next number was 64.

See https://bugs.llvm.org/attachment.cgi?id=20963
I did not run again with your patch. But even 173 and 64 seem like a lot and might be worth optimizing.

[baloghadamsoftware]

Warning added to the docs.

[baloghadamsoftware]

I think further optimization steps should be done is separate patches. However, this is the biggest step.

[JonasToth]

In D53187#1264415, @baloghadamsoftware wrote:

I think further optimization steps should be done is separate patches. However, this is the biggest step.

Agreed.

LGTM.

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

void ExceptionEscapeCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "IgnoredExceptions", RawIgnoredExceptions);
 }
 
 void ExceptionEscapeCheck::registerMatchers(MatchFinder *Finder) {
   if (!getLangOpts().CPlusPlus || !getLangOpts().CXXExceptions)
     return;
 
   Finder->addMatcher(
-      functionDecl(allOf(throws(unless(isIgnored(IgnoredExceptions))),
-                         anyOf(isNoThrow(), cxxDestructorDecl(),
+      functionDecl(allOf(anyOf(isNoThrow(), cxxDestructorDecl(),
                                cxxConstructorDecl(isMoveConstructor()),
                                cxxMethodDecl(isMoveAssignmentOperator()),
                                hasName("main"), hasName("swap"),
-                               isEnabled(FunctionsThatShouldNotThrow))))
+                               isEnabled(FunctionsThatShouldNotThrow)),
+                         throws(unless(isIgnored(IgnoredExceptions)))))
           .bind("thrower"),
       this);
 }
 
 void ExceptionEscapeCheck::check(const MatchFinder::MatchResult &Result) {
   const FunctionDecl *MatchedDecl =
       Result.Nodes.getNodeAs<FunctionDecl>("thrower");
   if (!MatchedDecl)

clang-tools-extra/trunk/docs/clang-tidy/checks/bugprone-exception-escape.rst

 A destructor throwing an exception may result in undefined behavior, resource
 leaks or unexpected termination of the program. Throwing move constructor or
 move assignment also may result in undefined behavior or resource leak. The
 ``swap()`` operations expected to be non throwing most of the cases and they
 are always possible to implement in a non throwing way. Non throwing ``swap()``
 operations are also used to create move operations. A throwing ``main()``
 function also results in unexpected termination.
 
+WARNING! This check may be expensive on large source files.
+
 Options
 -------
 
 .. option:: FunctionsThatShouldNotThrow
 
    Comma separated list containing function names which should not throw. An
    example value for this parameter can be ``WinMain`` which adds function
    ``WinMain()`` in the Windows API to the list of the funcions which should
    not throw. Default value is an empty string.
 
 .. option:: IgnoredExceptions
 
    Comma separated list containing type names which are not counted as thrown
    exceptions in the check. Default value is an empty string.

clang-tools-extra/trunk/test/clang-tidy/bugprone-exception-escape.cpp

 }
 
 void this_counts(int n) noexcept {
   // CHECK-MESSAGES: :[[@LINE-1]]:6: warning: an exception may be thrown in function 'this_counts' which should not throw exceptions
   if (n) throw 1;
   throw ignored1();
 }
 
+void thrower(int n) {
+  throw n;
+}
+
+int directly_recursive(int n) noexcept {
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: an exception may be thrown in funcion 'directly_recursive' which should not throw exceptions
+  if (n == 0)
+    thrower(n);
+  return directly_recursive(n);
+}
+
+int indirectly_recursive(int n) noexcept;
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: an exception may be thrown in functin 'indirectly_recursive' which should not throw exceptions
+
+int recursion_helper(int n) {
+  indirectly_recursive(n);
+}
+
+int indirectly_recursive(int n) noexcept {
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: an exception may be thrown in funcion 'indirectly_recursive' which should not throw exceptions
+  if (n == 0)
+    thrower(n);
+  return recursion_helper(n);
+}
+
 int main() {
   // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: an exception may be thrown in function 'main' which should not throw exceptions
   throw 1;
   return 0;
 }