[-Wunsafe-buffer-usage] Add a new recursive matcher to replace `forEachDescendant` in unsafe buffer check

[ziqingluo-90]

Summary

Add a new matcher forEveryDescendant that recursively matches descendants of a Stmt but skips nested callable definitions.
This matcher has same effect as using forEachDescendant and skipping forCallable explicitly but does not require the AST construction to be complete.

[xazax.hun]

Is the problem forEachDescendant matching statements inside blocks and lambdas? I wonder if this behavior would surprise people, so I think it would be better to:

• Potentially add a template bool parameter to forEachDescendant controlling this behavior.
• Review existing uses because I am not entirely sure if the current behavior is the right default.

[ziqingluo-90]

In D138329#3938351, @xazax.hun wrote:

Is the problem forEachDescendant matching statements inside blocks and lambdas? I wonder if this behavior would surprise people, so I think it would be better to:

• Potentially add a template bool parameter to forEachDescendant controlling this behavior.
• Review existing uses because I am not entirely sure if the current behavior is the right default.

Let me try to describe the problem in more detail. The goal is to recursively visit every descendant of a node n but skip all nested callable declarations in n. With forEachDescendant, one needs to explicitly test and skip, using forCallable, if a descendant does not belong to the same "callable" as n. forCallable looks for ancestors of a node through the AST so it requires the AST to be complete. But in our case, the AST is under construction. Given a node, we want the visitor only strictly look at descendants of the node.

For the questions, I think blocks and lambdas are the only cases we will have in analyzing "C/C++" + "blocks" programs. Our plan is to generalize this matcher to be an optional (off-by-default) mode of forEachDescendant once it becomes stable. So this implementation also skips other declarations. So far, this matcher is local to unsafe buffer checks.

[steakhal]

clang/lib/Analysis/UnsafeBufferUsage.cpp

55–56

Can Node be ever null if the visitor is initiated only be AST_MATCHER_P?

[NoQ]

In D138329#3938351, @xazax.hun wrote:

Is the problem forEachDescendant matching statements inside blocks and lambdas? I wonder if this behavior would surprise people, so I think it would be better to:

• Potentially add a template bool parameter to forEachDescendant controlling this behavior.

Yeah, I honestly think that it is the current behavior of forEachDescendant that's counterintuitive and almost never does what the user actually wants. People typically get surprised when it *does* descend into callables, something they didn't even think about.

And the idiom

decl(forEachDescendant(..., forCallable(equalsBoundNode("D"))).bind("D")

is not only clumsy and obscure but also algorithmically slower.

We do need a better name though, the difference between "Each" and "Every" isn't exactly the same as the difference between this matcher's behavior and that matcher's behavior. I was thinking of forEachStmtDescendant, as in it matches "statement-descendants". An even better name could be forEachDescendantInCallable which describes the behavior precisely and also connects to the old idiom for discoverability.

• Review existing uses because I am not entirely sure if the current behavior is the right default.

Yeah that's definitely a good idea.

clang/lib/Analysis/UnsafeBufferUsage.cpp

51–52

^^

60

llvm:: is unnecessary, we're under using namespace llvm.

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

55–56

Honestly I do not know the exact answer to your question. I was imagining that an AST node could have a null to be one of its children.

Our plan later is to make this matcher a general alternative to forEachDescendant, so I think the check for null here is not over-defensive.

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

55–56

There can definitely be null children in the AST. Eg. for(;;) {} has null initializer, null condition, null increment, non-null body. I guess this is more about whether RecursiveASTVisitor checks for that automatically before invoking callbacks.

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

55–56

I guess this is more about whether RecursiveASTVisitor checks for that automatically before invoking callbacks.

The override-ed TraverseDecl method in the base class RecursiveASTVisitor also has a null-check. So I feel like this null-check is needed here.

60

72

[ziqingluo-90]

Did a rebase and addressed comments.

[NoQ]

Ok LGTM! I hope we'll get a chance to implement a reusable solution later🤞

[thakis]

The clang binary should not depend on ASTMatchers.

I see this isn't new in this patch, but ASTMatchers should only be used from clang-tidy, not from the compiler itself.

[thakis]

Unrelatedly, this doesn't build on Windows: http://45.33.8.238/win/72750/step_4.txt

[NoQ]

In D138329#4027490, @thakis wrote:

The clang binary should not depend on ASTMatchers.

I see this isn't new in this patch, but ASTMatchers should only be used from clang-tidy, not from the compiler itself.

ASTMatchers have been baked into clang binary for at least a few years already, actively used by the static analyzer (some backstory in D25429). This warning is, however, probably the first use in clang proper, so they'll be there even if static analyzer support is turned off through cmake flags.

I'm open to a broader discussion. To me it's natural that there exist "analysis-based warnings" that take advantage of advanced analysis tools, and ASTMatchers is just one such tool, definitely not the most expensive one and not the most hazardous one (CFG and flow-sensitive analysis are arguably much scarier in both regards, and they're actively used in essential warnings such as -Wuninitialized).

With respect to this warning, we're also paying a lot of attention to make sure that performance is acceptable for the compiler. This patch is actually an example of our commitment to performance as it flattens the performance of this analysis down to linear time over AST size, something that wasn't previously possible with ASTMatchers.

[MaskRay]

For relands, you can just use Differential Revision: https://reviews.llvm.org/D138321 instead of Related differential revision: https://reviews.llvm.org/D138329.

Phabricator doesn't recognize Related differential revision:, so it does not connect ef47a0a711f12add401394f7af07a0b4d1635b56 to this differential.

Revert "Revert can be replaced with Reland to emphasize that it is a reland (it can be omitted as well). A reland should include the original commit message. You may additionally mention what issue it fixes.

[kstoimenov]

Is it possible these errors are due to your change: https://lab.llvm.org/buildbot/#/builders/5/builds/30522/steps/13/logs/stdio? If so please consider reverting/fixing.

[thakis]

ASTMatchers have been baked into clang binary for at least a few years already, actively used by the static analyzer (some backstory in D25429). This warning is, however, probably the first use in clang proper, so they'll be there even if static analyzer support is turned off through cmake flags.

I'm open to a broader discussion. To me it's natural that there exist "analysis-based warnings" that take advantage of advanced analysis tools, and ASTMatchers is just one such tool, definitely not the most expensive one and not the most hazardous one (CFG and flow-sensitive analysis are arguably much scarier in both regards, and they're actively used in essential warnings such as -Wuninitialized).

This has been discussed extensively when ASTMatchers were introduced. Project leadership back then (Doug Gregor and iirc Richard Smith) thought ASTMatches weren't a great approach and agreed to have them merged only if they aren't used in clang itself, but only in clang-tools-extra.

clang/lib/Analysis/UnsafeBufferUsage.cpp

 //===- UnsafeBufferUsage.cpp - Replace pointers with modern 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/Analyses/UnsafeBufferUsage.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "llvm/ADT/SmallVector.h"
 
 using namespace llvm;
 using namespace clang;
 using namespace ast_matchers;
 
+namespace clang::ast_matchers::internal {
+// A `RecursiveASTVisitor` that traverses all descendants of a given node "n"
+// except for those belonging to a different callable of "n".
+class MatchDescendantVisitor
+    : public RecursiveASTVisitor<MatchDescendantVisitor> {
+public:
+  typedef RecursiveASTVisitor<MatchDescendantVisitor> VisitorBase;
+
+  // Creates an AST visitor that matches `Matcher` on all
+  // descendants of a given node "n" except for the ones
+  // belonging to a different callable of "n".
+  MatchDescendantVisitor(const DynTypedMatcher *Matcher, ASTMatchFinder *Finder,
+                         BoundNodesTreeBuilder *Builder,
+                         ASTMatchFinder::BindKind Bind)
+      : Matcher(Matcher), Finder(Finder), Builder(Builder), Bind(Bind),
+        Matches(false) {}
+
+  // Returns true if a match is found in a subtree of `DynNode`, which belongs
+  // to the same callable of `DynNode`.
+  bool findMatch(const DynTypedNode &DynNode) {
+    Matches = false;
+    if (const Stmt *StmtNode = DynNode.get<Stmt>()) {
+      TraverseStmt(const_cast<Stmt *>(StmtNode));
+      *Builder = ResultBindings;
+      return Matches;
+    }
+    return false;
+  }
+
+  // The following are overriding methods from the base visitor class.
+  // They are public only to allow CRTP to work. They are *not *part
+  // of the public API of this class.
+
+  // For the matchers so far used in safe buffers, we only need to match
+  // `Stmt`s.  To override more as needed.
+
+  bool TraverseDecl(Decl *Node) {
+    if (!Node)
+      return true;
+    if (!match(*Node))
+      return false;
+    // To skip callables:
+    if (isa<FunctionDecl, BlockDecl, ObjCMethodDecl>(Node))
+      return true;
+    // Traverse descendants
+    return VisitorBase::TraverseDecl(Node);
+  }
+
+  bool TraverseStmt(Stmt *Node, DataRecursionQueue *Queue = nullptr) {
+    if (!Node)
+      return true;
+    if (!match(*Node))
+      return false;
+    // To skip callables:
+    if (isa<LambdaExpr>(Node))
+      return true;
+    return VisitorBase::TraverseStmt(Node);
+  }
+
+  bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const {
+    // TODO: let's ignore implicit code for now
+    return false;
+  }
+
+private:
+  // Sets 'Matched' to true if 'Matcher' matches 'Node'
+  //
+  // Returns 'true' if traversal should continue after this function
+  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
+  template <typename T> bool match(const T &Node) {
+    BoundNodesTreeBuilder RecursiveBuilder(*Builder);
+
+    if (Matcher->matches(DynTypedNode::create(Node), Finder,
+                         &RecursiveBuilder)) {
+      ResultBindings.addMatch(RecursiveBuilder);
+      Matches = true;
+      if (Bind != ASTMatchFinder::BK_All)
+        return false; // Abort as soon as a match is found.
+    }
+    return true;
+  }
+
+  const DynTypedMatcher *const Matcher;
+  ASTMatchFinder *const Finder;
+  BoundNodesTreeBuilder *const Builder;
+  BoundNodesTreeBuilder ResultBindings;
+  const ASTMatchFinder::BindKind Bind;
+  bool Matches;
+};
+
+AST_MATCHER_P(Stmt, forEveryDescendant, Matcher<Stmt>, innerMatcher) {
+  MatchDescendantVisitor Visitor(new DynTypedMatcher(innerMatcher), Finder,
+                                 Builder, ASTMatchFinder::BK_All);
+  return Visitor.findMatch(DynTypedNode::create(Node));
+}
+} // namespace clang::ast_matchers::internal
+
 namespace {
 // Because the analysis revolves around variables and their types, we'll need to
 // track uses of variables (aka DeclRefExprs).
 using DeclUseList = SmallVector<const DeclRefExpr *, 1>;
 
 // Convenience typedef.
 using FixItList = SmallVector<FixItHint, 4>;
 
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
     }
   };
 
   MatchFinder M;
   GadgetFinderCallback CB;
 
   // clang-format off
   M.addMatcher(
-    stmt(forEachDescendant(
+    stmt(forEveryDescendant(
       stmt(anyOf(
         // Add Gadget::matcher() for every gadget in the registry.
 #define GADGET(x)                                                              \
         x ## Gadget::matcher().bind(#x),
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
         // In parallel, match all DeclRefExprs so that to find out
         // whether there are any uncovered by gadgets.
         declRefExpr(hasPointerType(), to(varDecl())).bind("any_dre"),

clang/test/SemaCXX/warn-unsafe-buffer-usage.cpp

-// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -include %s -verify %s
+// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fblocks -include %s -verify %s
 #ifndef INCLUDED
 #define INCLUDED
 #pragma clang system_header
 
 // no spanification warnings for system headers
 void foo(...);  // let arguments of `foo` to hold testing expressions
 void testAsSystemHeader(char *p) {
   ++p;
foo(sp->a[1],
       funRetT().b[1],      // expected-warning{{unchecked operation on raw buffer in expression}}
       funRetTStar()->a[1],
       funRetTStar()->b[1]  // expected-warning{{unchecked operation on raw buffer in expression}}
       );
 }
 
 int garray[10];
 int * gp = garray;
-int gvar = gp[1];  // TODO: this is not warned
+int gvar = gp[1];  // FIXME: file scope unsafe buffer access is not warned
 
 void testLambdaCaptureAndGlobal(int * p) {
   int a[10];
 
   auto Lam = [p, a]() {
-    return p[1] // expected-warning2{{unchecked operation on raw buffer in expression}}
+    return p[1] // expected-warning{{unchecked operation on raw buffer in expression}}
       + a[1] + garray[1]
-      + gp[1];  // expected-warning2{{unchecked operation on raw buffer in expression}}
+      + gp[1];  // expected-warning{{unchecked operation on raw buffer in expression}}
   };
 }
 
 typedef T_t * T_ptr_t;
 
 void testTypedefs(T_ptr_t p) {
   foo(p[1],      // expected-warning{{unchecked operation on raw buffer in expression}}
       p[1].a[1], // expected-warning{{unchecked operation on raw buffer in expression}}
void testPointerToMember() {
   } S;
 
   int S_t::* p = &S_t::x;
   int * S_t::* q = &S_t::y;
 
   foo(S.*p,
       (S.*q)[1]);  // expected-warning{{unchecked operation on raw buffer in expression}}
 }
+
+// test that nested callable definitions are scanned only once
+void testNestedCallableDefinition(int * p) {
+  class A {
+    void inner(int * p) {
+      p++; // expected-warning{{unchecked operation on raw buffer in expression}}
+    }
+
+    static void innerStatic(int * p) {
+      p++; // expected-warning{{unchecked operation on raw buffer in expression}}
+    }
+
+    void innerInner(int * p) {
+      auto Lam = [p]() {
+        int * q = p;
+        q++;   // expected-warning{{unchecked operation on raw buffer in expression}}
+        return *q;
+      };
+    }
+  };
+
+  auto Lam = [p]() {
+    int * q = p;
+    q++;  // expected-warning{{unchecked operation on raw buffer in expression}}
+    return *q;
+  };
+
+  auto LamLam = [p]() {
+    auto Lam = [p]() {
+      int * q = p;
+      q++;  // expected-warning{{unchecked operation on raw buffer in expression}}
+      return *q;
+    };
+  };
+
+  void (^Blk)(int*) = ^(int *p) {
+    p++;   // expected-warning{{unchecked operation on raw buffer in expression}}
+  };
+
+  void (^BlkBlk)(int*) = ^(int *p) {
+    void (^Blk)(int*) = ^(int *p) {
+      p++;   // expected-warning{{unchecked operation on raw buffer in expression}}
+    };
+    Blk(p);
+  };
+
+  // lambda and block as call arguments...
+  foo( [p]() { int * q = p;
+              q++;  // expected-warning{{unchecked operation on raw buffer in expression}}
+              return *q;
+       },
+       ^(int *p) { p++;   // expected-warning{{unchecked operation on raw buffer in expression}}
+       }
+     );
+}
+
+void testVariableDecls(int * p) {
+  int * q = p++;      // expected-warning{{unchecked operation on raw buffer in expression}}
+  int a[p[1]];        // expected-warning{{unchecked operation on raw buffer in expression}}
+  int b = p[1];       // expected-warning{{unchecked operation on raw buffer in expression}}
+}
+
 #endif