[-Wunsafe-buffer-usage] Safe-buffers re-architecture to introduce Fixable gadgets

[NoQ]

Ok let's explain what's going on.

We're basically realizing that most unsafe patterns aren't fixable without additional context. The original design was like

"Suppose we see arr[n] in the code. This is both an indication that the code is unsafe, and an acknowledgement that this use of arr doesn't require fixing as all safe containers will act as a drop-in replacement."

This isn't correct though, because overloaded operator [] is very different from raw operator []. Namely, if the array has N elements, then &arr[N] is valid code when the operator is raw but undefined behavior when the operator is overloaded (which would be caught by -fsanitize=library as a hard crash). Therefore, even though arr[n] is an unsafe pattern, we cannot actually fix it until we discover more context, such as an implicit lvalue-to-rvalue conversion of the subscript result.

Well, technically, we can always "fix" expression arr[n] by replacing it with arr.data()[n]. We don't even need to include [n] in our context, we can replace any occurrence of arr with arr.data() and call it a day. Such "fix", even though it works in every context, is hovewer a "low-quality" fix because it defeats the purpose of safe buffer usage: the container will no longer be able to check bounds in this operation at runtime.

Of course, in some contexts such "low-quality fix" may be the only possible fix.

Which naturally leads to the idea of fixable gadgets acting as "refinements" of each other: out of all gadgets that consume the given use of the variable we could pick the one that acknowledges the most context, because it provides the most high-quality fix. This could potentially save us some work, but it could also lead to sometimes emitting low-quality fixits when manual user intervention would have led to much better code. This would also maintain the uniformity between unsafe and safe gadgets: unsafe gadgets are still fixable gadgets, just most of them will be "refined" later.

Another solution could be to turn gadgets inside out by using ParentMap to discover the context as part of fixit. Such solution is prone to rapidly getting out of control when contexts of different variable use sites start overlapping (eg. in expressions like ptr1 = ptr2).

So for now, in order to avoid overengineering, we stick to a very simple approach instead: keep unsafe gadgets completely separate, not use them for fixit generation at all. Don't have gadgets refine each other, but only implement gadgets that capture *all* the necessary context. Now the only thing they have in common with safe gadgets is that they both are represented as ASTMatcher-based patterns for which the code can be easily scanned. Therefore the getFixits() method gets moved to the safe gadget interface, and unsafe gadgets don't even need to worry about it. If an unsafe gadget turns out to be fixable without additional context, it will have to be duplicated as safe gadget. But this is fine because that's like 1-2 extra classes in a hierarchy of ~30.

[jkorous]

I did a superficial pass and the code LGTM (just nits).

Let me add one more thought to our motivation here.
@malavikasamak has pointed out that replacing arr with arr.data() when its type changes from T* to std::span<T> is not a universally correct fix. A counter-example is LHS of an assignment as arr.data() is not an LValue:

arr = nullptr;
=>
arr.data() = nullptr; // error: expression is not assignable

Which means that not only would gadgets that ignore relevant context be of lower quality but in some cases these would also be incorrect.

clang/lib/Analysis/UnsafeBufferUsage.cpp

579

This looks like a debug print in the parent commit. We should remove it from this patch.

620

(unrelated to this patch)
In some follow-up patch we should rename Pushed to make the code easier to understand. IIUC it means "is there a variable declaration this warning relates to?".

652

Is this a left-over debug print?

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

202

Do we still keep these terms "safe gadget" and "unsafe gadget" for referring to something else or we should forget about them from now on?

652

I think an assertion assert(false && "This should not be entered" ) might be better. But why this code should be unreachable?

[NoQ]

In D140062#4000094, @jkorous wrote:

Let me add one more thought to our motivation here.
@malavikasamak has pointed out that replacing arr with arr.data() when its type changes from T* to std::span<T> is not a universally correct fix. A counter-example is LHS of an assignment as arr.data() is not an LValue:

arr = nullptr;
=>
arr.data() = nullptr; // error: expression is not assignable

Which means that not only would gadgets that ignore relevant context be of lower quality but in some cases these would also be incorrect.

Yeah that's right, my bad, it's only a correct fix for ImplicitCastExpr<LValueToRValue>(arr). You cannot turn a std::span or std::array into a pointer lvalue, so it's fine that we don't have a low-quality fix for such cases.

[NoQ]

Looks great to me as well! I have a few nitpicks.

clang/lib/Analysis/UnsafeBufferUsage.cpp

159

I already nuked this function, so you probably need to rebase :(

187

getBaseStmt() can probably go to WarningGadget now?

192

Hmm so this function has to stay on the Gadget class because we want to group warnings by variables. Ok right.

202

No let's wipe them out!

643

In your case *every* gadget in the list is a warning gadget. So you can simply check whether the list is empty.

[malavikasamak]

Addressed some comments. Need to rebase to Artem's changes.

[malavikasamak]

clang/lib/Analysis/UnsafeBufferUsage.cpp

202

I will do a round and wipe these out from comments.

652

This is a left over debug message I added to test the re-architecture works as intended. Currently, it should not be reachable as we don't have any fixable gadgets available.

[jkorous]

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

30

Nit: Can we add the newline?

30

Please ignore - this is a stale comment.

clang/lib/Analysis/UnsafeBufferUsage.cpp

224

I think this is a bug.

[malavikasamak]

clang/lib/Analysis/UnsafeBufferUsage.cpp

224

Yes. Good catch. Thank you.

[jkorous]

clang/lib/Analysis/UnsafeBufferUsage.cpp

527

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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef GADGET
 #define GADGET(name)
 #endif
 
-#ifndef UNSAFE_GADGET
-#define UNSAFE_GADGET(name) GADGET(name)
+#ifndef WARNING_GADGET
+#define WARNING_GADGET(name) GADGET(name)
 #endif
 
-#ifndef SAFE_GADGET
-#define SAFE_GADGET(name) GADGET(name)
+#ifndef FIXABLE_GADGET
+#define FIXABLE_GADGET(name) GADGET(name)
 #endif
 
-UNSAFE_GADGET(Increment)
-UNSAFE_GADGET(Decrement)
-UNSAFE_GADGET(ArraySubscript)
-UNSAFE_GADGET(UnsafeBufferUsageAttr)
-UNSAFE_GADGET(PointerArithmetic)
+WARNING_GADGET(Increment)
+WARNING_GADGET(Decrement)
+WARNING_GADGET(ArraySubscript)
+WARNING_GADGET(UnsafeBufferUsageAttr)
+WARNING_GADGET(PointerArithmetic)
 
-#undef SAFE_GADGET
-#undef UNSAFE_GADGET
+#undef FIXABLE_GADGET
+#undef WARNING_GADGET
 #undef GADGET

clang/lib/Analysis/UnsafeBufferUsage.cpp

 class Gadget {
 public:
   enum class Kind {
 #define GADGET(x) x,
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
 #undef GADGETS
   };
 
-  /// Determine if a kind is a safe kind. Slower than calling isSafe().
-  static bool isSafeKind(Kind K) {
+  /// Determine if a kind is a safe kind. Slower than calling isWarningGadget().
+  static bool isWarningKind(Kind K) {
     switch (K) {
-#define UNSAFE_GADGET(x)                                                       \
+#define WARNING_GADGET(x)                                                       \
     case Kind::x:
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
-#undef UNSAFE_GADGET
-      return false;
+#undef WARNING_GADGET
+      return true;
 
-#define SAFE_GADGET(x)                                                         \
+#define FIXABLE_GADGET(x)                                                         \
     case Kind::x:
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
-#undef SAFE_GADGET
-      return true;
+#undef FIXABLE_GADGET
+      return false;
     }
     llvm_unreachable("Invalid gadget kind!");
   }
 
   /// 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 bool isWarningGadget() const = 0;
   virtual const Stmt *getBaseStmt() const = 0;
 
   /// Returns the list of pointer-type variables on which this gadget performs
   /// its operation. Typically there's only one variable. This isn't a list
   /// of all DeclRefExprs in the gadget's AST!
   virtual DeclUseList getClaimedVarUseSites() const = 0;
 
-  /// Returns a fixit that would fix the current gadget according to
-  /// the current strategy. Returns None if the fix cannot be produced;
-  /// returns an empty list if no fixes are necessary.
-  virtual Optional<FixItList> getFixits(const Strategy &) const {
-    return None;
-  }
 
   virtual ~Gadget() {}
 
 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 {
+class WarningGadget : public Gadget {
 public:
-  UnsafeGadget(Kind K) : Gadget(K) {
+  WarningGadget(Kind K) : Gadget(K) {
     assert(classof(this) && "Invalid unsafe gadget kind!");
   }
 
-  static bool classof(const Gadget *G) { return !isSafeKind(G->getKind()); }
-  bool isSafe() const override { return false; }
+  static bool classof(const Gadget *G) { return isWarningKind(G->getKind()); }
+  bool isWarningGadget() const override { return true; }
 };
 
 /// 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 {
+class FixableGadget : public Gadget {
 public:
-  SafeGadget(Kind K) : Gadget(K) {
+  FixableGadget(Kind K) : Gadget(K) {
     assert(classof(this) && "Invalid safe gadget kind!");
   }
 
-  static bool classof(const Gadget *G) { return isSafeKind(G->getKind()); }
-  bool isSafe() const override { return true; }
+  static bool classof(const Gadget *G) { return !isWarningKind(G->getKind()); }
+  bool isWarningGadget() const override { return false; }
+
+  /// Returns a fixit that would fix the current gadget according to
+  /// the current strategy. Returns None if the fix cannot be produced;
+  /// returns an empty list if no fixes are necessary.
+  virtual Optional<FixItList> getFixits(const Strategy &) const {
+    return None;
+  }
+
 };
+using FixableGadgetList = std::vector<std::unique_ptr<FixableGadget>>;
+using WarningGadgetList = std::vector<std::unique_ptr<WarningGadget>>;
 
 /// An increment of a pointer-type value is unsafe as it may run the pointer
 /// out of bounds.
-class IncrementGadget : public UnsafeGadget {
+class IncrementGadget : public WarningGadget {
   const UnaryOperator *Op;
 
 public:
   IncrementGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::Increment),
+      : WarningGadget(Kind::Increment),
         Op(Result.Nodes.getNodeAs<UnaryOperator>("op")) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::Increment;
   }
 
   static Matcher matcher() {
     return stmt(unaryOperator(
DeclUseList getClaimedVarUseSites() const override {
     }
 
     return {};
   }
 };
 
 /// A decrement of a pointer-type value is unsafe as it may run the pointer
 /// out of bounds.
-class DecrementGadget : public UnsafeGadget {
+class DecrementGadget : public WarningGadget {
   const UnaryOperator *Op;
 
 public:
   DecrementGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::Decrement),
+      : WarningGadget(Kind::Decrement),
         Op(Result.Nodes.getNodeAs<UnaryOperator>("op")) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::Decrement;
   }
 
   static Matcher matcher() {
     return stmt(unaryOperator(
DeclUseList getClaimedVarUseSites() const override {
     }
 
     return {};
   }
 };
 
 /// Array subscript expressions on raw pointers as if they're arrays. Unsafe as
 /// it doesn't have any bounds checks for the array.
-class ArraySubscriptGadget : public UnsafeGadget {
+class ArraySubscriptGadget : public WarningGadget {
   const ArraySubscriptExpr *ASE;
 
 public:
   ArraySubscriptGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::ArraySubscript),
+      : WarningGadget(Kind::ArraySubscript),
         ASE(Result.Nodes.getNodeAs<ArraySubscriptExpr>("arraySubscr")) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::ArraySubscript;
   }
 
   static Matcher matcher() {
     return stmt(
DeclUseList getClaimedVarUseSites() const override {
     }
 
     return {};
   }
 };
 
 /// A call of a function or method that performs unchecked buffer operations
 /// over one of its pointer parameters.
-class UnsafeBufferUsageAttrGadget : public UnsafeGadget {
+class UnsafeBufferUsageAttrGadget : public WarningGadget {
     const CallExpr *Op;
 
 public:
     UnsafeBufferUsageAttrGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::UnsafeBufferUsageAttr),
+      : WarningGadget(Kind::UnsafeBufferUsageAttr),
         Op(Result.Nodes.getNodeAs<CallExpr>("call_expr")) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::UnsafeBufferUsageAttr;
   }
 
   static Matcher matcher() {
     return stmt(callExpr(callee(functionDecl(hasAttr(attr::UnsafeBufferUsage))))
DeclUseList getClaimedVarUseSites() const override {
     return {};
   }
 };
 
 /// A pointer arithmetic expression of one of the forms:
 ///  \code
 ///  ptr + n | n + ptr | ptr - n | ptr += n | ptr -= n
 ///  \endcode
-class PointerArithmeticGadget : public UnsafeGadget {
+class PointerArithmeticGadget : public WarningGadget {
   const BinaryOperator *PA; // pointer arithmetic expression
   const Expr * Ptr;         // the pointer expression in `PA`
 
 public:
     PointerArithmeticGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::PointerArithmetic),
+      : WarningGadget(Kind::PointerArithmetic),
         PA(Result.Nodes.getNodeAs<BinaryOperator>("ptrAdd")),
         Ptr(Result.Nodes.getNodeAs<Expr>("ptrAddPtr")) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::PointerArithmetic;
   }
 
   static Matcher matcher() {
if (I == Map.end())
       return Kind::Wontfix;
 
     return I->second;
   }
 };
 } // namespace
 
 /// Scan the function and return a list of gadgets found with provided kits.
-static std::pair<GadgetList, DeclUseTracker> findGadgets(const Decl *D) {
+static std::tuple<FixableGadgetList, WarningGadgetList, DeclUseTracker> findGadgets(const Decl *D) {
 
   struct GadgetFinderCallback : MatchFinder::MatchCallback {
-    GadgetList Gadgets;
+    FixableGadgetList FixableGadgets;
+    WarningGadgetList WarningGadgets;
     DeclUseTracker Tracker;
 
     void run(const MatchFinder::MatchResult &Result) override {
       if (const auto *DRE = Result.Nodes.getNodeAs<DeclRefExpr>("any_dre")) {
         Tracker.discoverUse(DRE);
       }
 
       if (const auto *DS = Result.Nodes.getNodeAs<DeclStmt>("any_ds")) {
         Tracker.discoverDecl(DS);
       }
 
       // Figure out which matcher we've found, and call the appropriate
       // subclass constructor.
       // FIXME: Can we do this more logarithmically?
-#define GADGET(x)                                                              \
+#define FIXABLE_GADGET(x)                                                              \
       if (Result.Nodes.getNodeAs<Stmt>(#x)) {                                  \
-        Gadgets.push_back(std::make_unique<x ## Gadget>(Result));              \
+        FixableGadgets.push_back(std::make_unique<x ## Gadget>(Result));              \
         return;                                                                \
       }
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
-#undef GADGET
+#undef FIXABLE_GADGET
+#define WARNING_GADGET(x)                                                              \
+      if (Result.Nodes.getNodeAs<Stmt>(#x)) {                                  \
+        WarningGadgets.push_back(std::make_unique<x ## Gadget>(Result));              \
+        return;                                                                \
+      }
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+#undef WARNING_GADGET
     }
   };
 
   MatchFinder M;
   GadgetFinderCallback CB;
 
   // clang-format off
   M.addMatcher(
     stmt(forEveryDescendant(
       stmt(anyOf(
         // Add Gadget::matcher() for every gadget in the registry.
-#define GADGET(x)                                                              \
+#define FIXABLE_GADGET(x)                                                              \
         x ## Gadget::matcher().bind(#x),
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
-#undef GADGET
+#undef FIXABLE_GADGET
+#define WARNING_GADGET(x)                                                              \
+        x ## Gadget::matcher().bind(#x),
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+#undef WARNING_GADGET
+
         // In parallel, match all DeclRefExprs so that to find out
         // whether there are any uncovered by gadgets.
         declRefExpr(hasPointerType(), to(varDecl())).bind("any_dre"),
         // Also match DeclStmts because we'll need them when fixing
         // their underlying VarDecls that otherwise don't have
         // any backreferences to DeclStmts.
         declStmt().bind("any_ds")
       ))
       // 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?
     )),
     &CB
   );
   // clang-format on
 
   M.match(*D->getBody(), D->getASTContext());
 
   // Gadgets "claim" variables they're responsible for. Once this loop finishes,
   // the tracker will only track DREs that weren't claimed by any gadgets,
   // i.e. not understood by the analysis.
-  for (const auto &G : CB.Gadgets) {
+  for (const auto &G : CB.FixableGadgets) {
     for (const auto *DRE : G->getClaimedVarUseSites()) {
       CB.Tracker.claimUse(DRE);
     }
   }
 
-  return {std::move(CB.Gadgets), std::move(CB.Tracker)};
+  return {std::move(CB.FixableGadgets), std::move(CB.WarningGadgets), std::move(CB.Tracker)};
 }
 
 void clang::checkUnsafeBufferUsage(const Decl *D,
                                    UnsafeBufferUsageHandler &Handler) {
-  std::cout << "REACHED HERE \n";
   assert(D && D->getBody());
 
   SmallSet<const VarDecl *, 8> WarnedDecls;
 
-  auto [Gadgets, Tracker] = findGadgets(D);
-
-  DenseMap<const VarDecl *, std::vector<const Gadget *>> Map;
-  int count = 0;
+  auto [FixableGadgets, WarningGadgets, Tracker] = findGadgets(D);
+  DenseMap<const VarDecl *, std::pair<std::vector<const FixableGadget *>, 
+                                std::vector<const WarningGadget *>>> Map;
 
   // First, let's sort gadgets by variables. If some gadgets cover more than one
   // variable, they'll appear more than once in the map.
-  for (const auto &G : Gadgets) {
+  for (const auto &G : FixableGadgets) {
+    DeclUseList DREs = G->getClaimedVarUseSites();
+
+    // Populate the map.
+    for (const DeclRefExpr *DRE : DREs) {
+      if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
+        Map[VD].first.push_back(G.get()); 
+      }
+    }
+  }
+
+  for (const auto &G : WarningGadgets) {
     DeclUseList DREs = G->getClaimedVarUseSites();
 
     // Populate the map.
     bool Pushed = false;
     for (const DeclRefExpr *DRE : DREs) {
       if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
-        Map[VD].push_back(G.get());
+        Map[VD].second.push_back(G.get()); 
         Pushed = true;
       }
     }
 
-    bool b = !Pushed && !G->isSafe();
-    std::cout << "count" << count << " " << b <<"\n";
-    count++;
-    if (!Pushed && !G->isSafe()) {
+    if (!Pushed) {
       // We won't return to this gadget later. Emit the warning right away.
       Handler.handleUnsafeOperation(G->getBaseStmt());
       continue;
     }
   }
 
   Strategy S;
 
   for (const auto &Item : Map) {
     const VarDecl *VD = Item.first;
-    const std::vector<const Gadget *> &VDGadgets = Item.second;
+    const std::vector<const FixableGadget *> &VDFixableGadgets = Item.second.first;
+    const std::vector<const WarningGadget *> &VDWarningGadgets = Item.second.second;
 
     // If the variable has no unsafe gadgets, skip it entirely.
-    if (!any_of(VDGadgets, [](const Gadget *G) { return !G->isSafe(); }))
+    if (!any_of(VDWarningGadgets, [](const Gadget *G) { return G->isWarningGadget(); }))
       continue;
 
     Optional<FixItList> Fixes = None;
 
     // Avoid suggesting fixes if not all uses of the variable are identified
     // as known gadgets.
     // FIXME: Support parameter variables as well.
     if (!Tracker.hasUnclaimedUses(VD) && VD->isLocalVarDecl()) {
+      std::cout << " This should not be entered";
       // Choose the appropriate strategy. FIXME: We should try different
       // strategies.
       S.set(VD, Strategy::Kind::Span);
 
       // Check if it works.
       // FIXME: This isn't sufficient (or even correct) when a gadget has
       // already produced a fixit for a different variable i.e. it was mentioned
       // in the map twice (or more). In such case the correct thing to do is
       // to undo the previous fix first, and then if we can't produce the new
       // fix for both variables, revert to the old one.
       Fixes = FixItList{};
-      for (const Gadget *G : VDGadgets) {
+      for (const FixableGadget *G : VDFixableGadgets) {
         Optional<FixItList> F = G->getFixits(S);
         if (!F) {
           Fixes = None;
           break;
         }
 
         for (auto &&Fixit: *F)
           Fixes->push_back(std::move(Fixit));
       }
     }
 
     if (Fixes) {
       // If we reach this point, the strategy is applicable.
       Handler.handleFixableVariable(VD, std::move(*Fixes));
     } else {
       // The strategy has failed. Emit the warning without the fixit.
       S.set(VD, Strategy::Kind::Wontfix);
-      for (const Gadget *G : VDGadgets) {
-        if (!G->isSafe()) {
-          Handler.handleUnsafeOperation(G->getBaseStmt());
-        }
-      }
-    }
-  }
-}
+      for (const Gadget *G : VDWarningGadgets) {