[-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

541–542

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

577

(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?".

610

Is this a left-over debug print?

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

174

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?

610

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

149–150

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

160

getBaseStmt() can probably go to WarningGadget now?

165

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

174

No let's wipe them out!

601

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

174

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

610

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

36

Nit: Can we add the newline?

36

Please ignore - this is a stale comment.

clang/lib/Analysis/UnsafeBufferUsage.cpp

193

I think this is a bug.

[malavikasamak]

clang/lib/Analysis/UnsafeBufferUsage.cpp

193

Yes. Good catch. Thank you.

[jkorous]

clang/lib/Analysis/UnsafeBufferUsage.cpp

489

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

clang/lib/Analysis/UnsafeBufferUsage.cpp

 }
 
 namespace {
 /// 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).
+/// Gadgets can be warning (immediately deserving a warning) or fixable (not
+/// always deserving a warning per se, but requires our attention to identify
+/// it warrants a fixit).
 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 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 std::optional<FixItList> getFixits(const Strategy &) const {
-    return std::nullopt;
-  }
-
   virtual ~Gadget() = default;
 
 private:
   Kind K;
 };
 
-using GadgetList = std::vector<std::unique_ptr<Gadget>>;
 
-/// Unsafe gadgets correspond to unsafe code patterns that warrants
+/// Warning 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) {}
 
-  static bool classof(const Gadget *G) { return G->isSafe(); }
-  bool isSafe() const final { return false; }
+  static bool classof(const Gadget *G) { return G->isWarningGadget(); }
+  bool isWarningGadget() const final { 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
+/// Fixable gadgets correspond to code patterns that aren't always unsafe but need to be
+/// properly recognized in order to emit fixes. For example, if a raw pointer-type
+/// variable is replaced by a safe C++ container, every use of such variable must 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) {}
+
+  static bool classof(const Gadget *G) { return !G->isWarningGadget(); }
+  bool isWarningGadget() const final { 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;
+  }
 
-  static bool classof(const Gadget *G) { return !G->isSafe(); }
-  bool isSafe() const final { return true; }
 };
 
+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 {
   static constexpr const char *const OpTag = "op";
   const UnaryOperator *Op;
 
 public:
   IncrementGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::Increment),
+      : WarningGadget(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(
DeclUseList getClaimedVarUseSites() const override {
     }
 
     return std::move(Uses);
   }
 };
 
 /// 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 {
   static constexpr const char *const OpTag = "op";
   const UnaryOperator *Op;
 
 public:
   DecrementGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::Decrement),
+      : WarningGadget(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(
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 {
   static constexpr const char *const ArraySubscrTag = "arraySubscr";
   const ArraySubscriptExpr *ASE;
 
 public:
   ArraySubscriptGadget(const MatchFinder::MatchResult &Result)
-      : UnsafeGadget(Kind::ArraySubscript),
+      : WarningGadget(Kind::ArraySubscript),
         ASE(Result.Nodes.getNodeAs<ArraySubscriptExpr>(ArraySubscrTag)) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::ArraySubscript;
   }
 
   static Matcher matcher() {
     // FIXME: What if the index is integer literal 0? Should this be
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 {
   static constexpr const char *const PointerArithmeticTag = "ptrAdd";
   static constexpr const char *const PointerArithmeticPointerTag = "ptrAddPtr";
   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>(PointerArithmeticTag)),
         Ptr(Result.Nodes.getNodeAs<Expr>(PointerArithmeticPointerTag)) {}
 
   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 {
       // In debug mode, assert that we've found exactly one gadget.
       // This helps us avoid conflicts in .bind() tags.
 #if NDEBUG
 #define NEXT return
 #else
#endif
       if (const auto *DS = Result.Nodes.getNodeAs<DeclStmt>("any_ds")) {
         Tracker.discoverDecl(DS);
         NEXT;
       }
 
       // Figure out which matcher we've found, and call the appropriate
       // subclass constructor.
       // FIXME: Can we do this more logarithmically?
-#define GADGET(name)                                                           \
+#define FIXABLE_GADGET(name)                                                           \
       if (Result.Nodes.getNodeAs<Stmt>(#name)) {                               \
-        Gadgets.push_back(std::make_unique<name ## Gadget>(Result));           \
+        FixableGadgets.push_back(std::make_unique<name ## Gadget>(Result));           \
+        NEXT;                                                                  \
+      }
+#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
+#define WARNING_GADGET(name)                                                           \
+      if (Result.Nodes.getNodeAs<Stmt>(#name)) {                               \
+        WarningGadgets.push_back(std::make_unique<name ## Gadget>(Result));           \
         NEXT;                                                                  \
       }
 #include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
 
       assert(numFound >= 1 && "Gadgets not found in match result!");
       assert(numFound <= 1 && "Conflicting bind tags in gadgets!");
     }
   };
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
   );
   // 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) {
   assert(D && D->getBody());
 
   SmallSet<const VarDecl *, 8> WarnedDecls;
 
-  auto [Gadgets, Tracker] = findGadgets(D);
+  auto [FixableGadgets, WarningGadgets, Tracker] = findGadgets(D);
 
-  DenseMap<const VarDecl *, std::vector<const Gadget *>> Map;
+  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 ClaimedVarUseSites = G->getClaimedVarUseSites();
 
     // Populate the map.
     bool Pushed = false;
     for (const DeclRefExpr *DRE : ClaimedVarUseSites) {
       if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
-        Map[VD].push_back(G.get());
+        Map[VD].second.push_back(G.get());
         Pushed = true;
       }
     }
 
-    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 &[VD, VDGadgets] : Map) {
+  for (const auto &Item : Map) {
+
+    const VarDecl *VD = Item.first;
+    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 (VDWarningGadgets.empty())
       continue;
 
     std::optional<FixItList> Fixes;
 
     // 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()) {
       // 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) {
         std::optional<FixItList> F = G->getFixits(S);
         if (!F) {
           Fixes = std::nullopt;
           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 WarningGadget *G : VDWarningGadgets) {