[-Wunsafe-buffer-usage] Introduce an abstraction for fixable code patterns.

[NoQ]

Summary

This patch introduces a hierarchy of Gadget classes, which are going to be the core concept in our fixit machine.

A gadget is a rigid code pattern that constitutes an operation that the fixit machine "understands" well enough to work with. A gadget may be "unsafe" (i.e., constitute a raw buffer access) or "safe" (constitute a use of a pointer or array variable that isn't unsafe per se, but may need fixing if the participating variable changes type to a safe container/view).

By "rigid" I mean something like "matchable with a sequence of nested if-dyncast-statements or an ASTMatcher without forEachDescendant() or other non-trivial traversal, except maybe ignoringParenImpCasts() and such. The point is to make it very clear what the semantics of that code is.

We'll be able to make decisions about how to fix the code depending on the set of gadgets that we've enumerated. Basically, in order to fix a type of a variable, each use of that variable has to participate in a gadget, and each such gadget has to consent to fixing itself according to the variable's new type. More on that in follow-up patches!

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

37

Whoops typo!

[xazax.hun]

clang/lib/Analysis/UnsafeBufferUsage.cpp

70

107

How deep will the Gadget Hierarchy be? Using inheritance only to classify safe and unsafe gadgets feels like a very heavy weight solution to a relatively simple problem.

[aaron.ballman]

clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def

2

Is this file named properly if it is also going to handle SAFE_GADGET?

10

You have some comments below about what gadgets are and what makes one safe or unsafe; should those comments be hoisted into this .def file?

clang/lib/Analysis/UnsafeBufferUsage.cpp

17–21

Something to think about: ObjC pointers are pointer-like but not actual pointers; should those be covered as well (via isAnyPointerType())?

37

We don't even need the #undef because the .def file already does that for us. Same observation applies below.

63

Should this be an explicit constructor? (Same question applies below to derived classes as well.)

113

Should we make a static constexpr const char * for these strings so we can give it a name and ensure it's used consistently?

[steakhal]

clang/lib/Analysis/UnsafeBufferUsage.cpp

40

We could have a GADGET_RANGE(UnsafeGadgets, Increment, Decrement), which could expand to BEGIN_##x = Increment, END_##x = Decrement, when declaring the Kind enum, similarly how SymExpr::Kind::Begin_BINARYSYMEXPRS is defined.
That way this code could look like:

return !(Kind::Begin_UnsafeGadgets <= K && K <= Kind::End_UnsafeGadgets);

43–45

I'd advocate for using the same macro variable name here as an XMACRO argument as it's present in the definition as parameter.
Same for the rest of the XMACRO expansions.

87

102

123

I thought this matcher was already bound as "Increment" by x ## Gadget::matcher().bind(#x) inside GadgetFinderCallback::run()

142

I wonder if we should assert that we only expect exactly one match (entry) inside Result.Nodes.

150

I'd advocate for covariant return types for such cases.

182–183

I was thinking of constructing a std::vector<DynTypedMatcher> of the matchers of the disjunction because the extra comma is allowed inside the initializer expression.
After that, you could probably use constructVariadic(VO_AnyOf, ...) as demonstrated by the TEST(ConstructVariadic, MismatchedTypes_Regression) unit-test. But TBH, I don't think it's more readable than this :D

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

63

What's the value of making it explicit given that it's an abstract class that can't be constructed directly anyway?

113

I think it makes perfect sense to have different bind-names in different classes. They don't all correspond to the same role the bound expression plays.

123

Yeah it's a bit redundant but it makes the class properly incapsulated, not reliant on the external machine to use it in a certain way. A bit more resistant to renaming as well.

And while this time these two bindings coincided, in the general case they can be different. So I wanted to establish an idiom that works in all cases.

If we ever run into performance problems, I'm totally open to optimizing this.

142

You mean like, exactly one if-statement succeeds? That'd require us to run the entire list every time (at least in debug mode) but it's probably not too bad. I'll look for a clean solution^^

182–183

One way or another, D138253 cleans up this FIXME.

[aaron.ballman]

clang/lib/Analysis/UnsafeBufferUsage.cpp

63

None, I had missed that this was an abstract class and forgot to delete the comment here on the base class. It does apply to the (non-abstract) derived classes though.

113

Sorry, I was unclear. I meant a private data member of IncrementGadget so that the constructor and the matcher() functions use a named constant rather than a string literal.

[NoQ]

clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def

2

UnsafeBufferUsage is the name of the analysis. It's somewhat valuable to keep this file next to UnsafeBufferUsage.h so that it was obvious at a glance that these two files work together.

I'm open to renaming the entire analysis though, a non-judgemental "BufferUsage analysis" totally works for me, WDYT?

Or I can make a folder. But I don't expect more than 2 files in this folder.

clang/lib/Analysis/UnsafeBufferUsage.cpp

17–21

Great question! Technically unsafe operations on ObjC pointers are not a compile error, but they never actually make sense because you can't have buffers of ObjC objects. Technically, you're not even supposed to know their size or layout until runtime (https://en.wikipedia.org/wiki/Objective-C#Non-fragile_instance_variables). So this is an insanely exotic situation that we most likely won't be covering.

37

Whoops right.

113

Oh, fair enough!

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

107

I'm expecting UnsafeGadget and SafeGadget to grow some common methods in the future. But I'm already second-guessing this decision (https://reviews.llvm.org/D137379?id=473092#inline-1340017) so I guess I'll ungrow these intermediate classes if things become too tedious.

[NoQ]

Address review comments.

[NoQ]

clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def

2

I expect @malavikasamak to do some renaming in a follow-up patch in the near future as she seeks to introduce more precise distinction between unsafe and safe gadgets.

clang/lib/Analysis/UnsafeBufferUsage.cpp

40

Nuked this entire facility. It's always possible to simply call isSafe().

87

I love that!

107

To answer the original question, SafeGadget and UnsafeGadget are most likely going to be the only intermediate class. So, it'll be 2 abstract classes deep.

142

Ok I added this huge #ifdef NDEBUG thing. I agree that it's valuable but I'm also somewhat worried that it may diverge from the non-debug code.

[NoQ]

A cleaner way to implement the debug facility.

[NoQ]

Because we're approaching a stack of ~15 patches and it's starting to become unmanageable, I'm really interested in landing these older patches quickly. I think I addressed the feedback, and I'm definitely committed to addressing more feedback as it comes in, but it's likely that I'd ask for a chance to address it in follow-up patches anyway. Because otherwise the rest of our team will have to undergo annoying rebases, and it's probably also super confusing to review when all patches in the stack are out of sync from each other. So I'll try to land this tomorrow.

[xazax.hun]

I don't mind committing these patches, I have a high confidence in you going back and addressing feedback post-commit if something is coming up.

[jkorous]

LGTM

[MaskRay]

clang/lib/Analysis/UnsafeBufferUsage.cpp

164

numFound was undefined in non-assertion builds. Fixed in 893a0ea948a65421013b62bd1855e430ca184739

clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def

+//=- UnsafeBufferUsageGadgets.def - List of ways to use a buffer --*- 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
+//
+//===----------------------------------------------------------------------===//
+
+/// A gadget is an individual operation in the code that may be of interest to
+/// the UnsafeBufferUsage analysis.
+#ifndef GADGET
+#define GADGET(name)
+#endif
+
+/// Unsafe gadgets correspond to unsafe code patterns that warrant
+/// an immediate warning.
+#ifndef UNSAFE_GADGET
+#define UNSAFE_GADGET(name) GADGET(name)
+#endif
+
+/// Safe gadgets correspond to code patterns that aren't unsafe but need to be
+/// properly recognized in order to emit correct warnings and fixes over unsafe
+/// gadgets.
+#ifndef SAFE_GADGET
+#define SAFE_GADGET(name) GADGET(name)
+#endif
+
+UNSAFE_GADGET(Increment)
+UNSAFE_GADGET(Decrement)
+
+#undef SAFE_GADGET
+#undef UNSAFE_GADGET
+#undef GADGET

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 "llvm/ADT/SmallVector.h"
 
 using namespace llvm;
 using namespace clang;
 using namespace ast_matchers;
 
+// Because we're dealing with raw pointers, let's define what we mean by that.
+static auto hasPointerType() {
+  return anyOf(hasType(pointerType()),
+               hasType(autoType(hasDeducedType(
+                   hasUnqualifiedDesugaredType(pointerType())))));
+}
+
 namespace {
-// TODO: Better abstractions over gadgets.
-using GadgetList = std::vector<const Stmt *>;
+/// Gadget is an individual operation in the code that may be of interest to
+/// this analysis. Each (non-abstract) subclass corresponds to a specific
+/// rigid AST structure that constitutes an operation on a pointer-type object.
+/// Discovery of a gadget in the code corresponds to claiming that we understand
+/// what this part of code is doing well enough to potentially improve it.
+/// Gadgets can be unsafe (immediately deserving a warning) or safe (not
+/// deserving a warning per se, but affecting our decision-making process
+/// nonetheless).
+class Gadget {
+public:
+  enum class Kind {
+#define GADGET(x) x,
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+  };
+
+  /// Common type of ASTMatchers used for discovering gadgets.
+  /// Useful for implementing the static matcher() methods
+  /// that are expected from all non-abstract subclasses.
+  using Matcher = decltype(stmt());
+
+  Gadget(Kind K) : K(K) {}
+
+  Kind getKind() const { return K; }
+
+  virtual bool isSafe() const = 0;
+  virtual const Stmt *getBaseStmt() const = 0;
+
+  virtual ~Gadget() = default;
+
+private:
+  Kind K;
+};
+
+using GadgetList = std::vector<std::unique_ptr<Gadget>>;
+
+/// Unsafe gadgets correspond to unsafe code patterns that warrants
+/// an immediate warning.
+class UnsafeGadget : public Gadget {
+public:
+  UnsafeGadget(Kind K) : Gadget(K) {}
+
+  static bool classof(const Gadget *G) { return G->isSafe(); }
+  bool isSafe() const final { return false; }
+};
+
+/// Safe gadgets correspond to code patterns that aren't unsafe but need to be
+/// properly recognized in order to emit correct warnings and fixes over unsafe
+/// gadgets. For example, if a raw pointer-type variable is replaced by
+/// a safe C++ container, every use of such variable may need to be
+/// carefully considered and possibly updated.
+class SafeGadget : public Gadget {
+public:
+  SafeGadget(Kind K) : Gadget(K) {}
+
+  static bool classof(const Gadget *G) { return !G->isSafe(); }
+  bool isSafe() const final { return true; }
+};
+
+/// An increment of a pointer-type value is unsafe as it may run the pointer
+/// out of bounds.
+class IncrementGadget : public UnsafeGadget {
+  static constexpr const char *const OpTag = "op";
+  const UnaryOperator *Op;
+
+public:
+  IncrementGadget(const MatchFinder::MatchResult &Result)
+      : UnsafeGadget(Kind::Increment),
+        Op(Result.Nodes.getNodeAs<UnaryOperator>(OpTag)) {}
+
+  static bool classof(const Gadget *G) {
+    return G->getKind() == Kind::Increment;
   }
 
+  static Matcher matcher() {
+    return stmt(unaryOperator(
+      hasOperatorName("++"),
+      hasUnaryOperand(ignoringParenImpCasts(hasPointerType()))
+    ).bind(OpTag));
+  }
+
+  const UnaryOperator *getBaseStmt() const override { return Op; }
+};
+
+/// A decrement of a pointer-type value is unsafe as it may run the pointer
+/// out of bounds.
+class DecrementGadget : public UnsafeGadget {
+  static constexpr const char *const OpTag = "op";
+  const UnaryOperator *Op;
+
+public:
+  DecrementGadget(const MatchFinder::MatchResult &Result)
+      : UnsafeGadget(Kind::Decrement),
+        Op(Result.Nodes.getNodeAs<UnaryOperator>(OpTag)) {}
+
+  static bool classof(const Gadget *G) {
+    return G->getKind() == Kind::Decrement;
+  }
+
+  static Matcher matcher() {
+    return stmt(unaryOperator(
+      hasOperatorName("--"),
+      hasUnaryOperand(ignoringParenImpCasts(hasPointerType()))
+    ).bind(OpTag));
+  }
+
+  const UnaryOperator *getBaseStmt() const override { return Op; }
+};
+} // namespace
+
 // Scan the function and return a list of gadgets found with provided kits.
 static GadgetList findGadgets(const Decl *D) {
 
   class GadgetFinderCallback : public MatchFinder::MatchCallback {
     GadgetList &Output;
 
   public:
     GadgetFinderCallback(GadgetList &Output) : Output(Output) {}
 
     void run(const MatchFinder::MatchResult &Result) override {
-      Output.push_back(Result.Nodes.getNodeAs<Stmt>("root_node"));
+      // Figure out which matcher we've found, and call the appropriate
+      // subclass constructor.
+      // FIXME: Can we do this more logarithmically?
+#ifdef NDEBUG
+#define GADGET(x)                                                              \
+      if (Result.Nodes.getNodeAs<Stmt>(#x)) {                                  \
+        Output.push_back(std::make_unique<x ## Gadget>(Result));               \
+        return;                                                                \
+      }
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+#else
+      // In asserts mode add a runtime check to make sure there aren't
+      // any unexpected matches. This protects us from gadgets that define
+      // sub-operation tags that conflict with gadget names.
+      int numFound = 0;
+#define GADGET(x)                                                              \
+      if (Result.Nodes.getNodeAs<Stmt>(#x)) {                                  \
+        Output.push_back(std::make_unique<x ## Gadget>(Result));               \
+        ++numFound;                                                            \
+      }
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+      assert(numFound <= 1 && "Conflicting gadget names!");
+#endif
     }
   };
 
   GadgetList G;
   MatchFinder M;
-
-  auto IncrementMatcher = unaryOperator(
-    hasOperatorName("++"),
-    hasUnaryOperand(hasType(pointerType()))
-  );
-  auto DecrementMatcher = unaryOperator(
-    hasOperatorName("--"),
-    hasUnaryOperand(hasType(pointerType()))
-  );
-
   GadgetFinderCallback CB(G);
 
+  // clang-format off
   M.addMatcher(
-      stmt(forEachDescendant(
-        stmt(
-          anyOf(
-            IncrementMatcher,
-            DecrementMatcher
-            /* Fill me in! */
-          )
-          // FIXME: Idiomatically there should be a forCallable(equalsNode(D))
-          // here, to make sure that the statement actually belongs to the
-          // function and not to a nested function. However, forCallable uses
-          // ParentMap which can't be used before the AST is fully constructed.
-          // The original problem doesn't sound like it needs ParentMap though,
-          // maybe there's a more direct solution?
-        ).bind("root_node")
-      )), &CB);
+      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"
+        // FIXME: Is there a better way to avoid hanging comma?
+        unless(stmt())
+      ))
+    )),
+    &CB
+  );
+  // clang-format on
 
   M.match(*D->getBody(), D->getASTContext());
 
   return G; // NRVO!
 }
 
 void clang::checkUnsafeBufferUsage(const Decl *D,
                                    UnsafeBufferUsageHandler &Handler) {
   assert(D && D->getBody());
 
-  GadgetList G = findGadgets(D);
-  for (const Stmt *S : G) {
-    Handler.handleUnsafeOperation(S);
+  GadgetList Gadgets = findGadgets(D);
+  for (const auto &G : Gadgets) {
+    Handler.handleUnsafeOperation(G->getBaseStmt());
   }
 }