[-Wunsafe-buffer-usage] Reducing non-determinism in diagnostics output stream

[ziqingluo-90]

Summary

The -Wunsafe-buffer-usage analysis outputs diagnostics in the order of pointer values to associated VarDecls. This creates non-determinism in the order of diagnostics in output since it cannot be guaranteed in pointer values. However, our fix-it tests were written under the assumption that diagnostics are output in source location order. This results in non-deterministic failures in our tests when diagnostics are not output in source location order, such as
buildbot fail (We disabled the test for windows but didn't understand the failure that time).

The reason that a test fail, albeit possible, is much less likely than a test pass is probably because pointer values to AST nodes nearly respect to the order of node creation/parse.

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

1081

Warnings are still emitted in non-deterministic order within a single VarDecl group. But it should not affect test results.

[NoQ]

LGTM, let's land asap!

clang/include/clang/Analysis/Analyses/UnsafeBufferUsage.h

65–71 ↗

(On Diff #504860)

Nice template solution!

Can we keep it in the .cpp file? It's not really part of our analysis's user interface, at least not yet.

[jkorous]

+1 to moving the comparator to the .cpp file; otherwise LGTM!
Thanks for fixing this!

[ziqingluo-90]

Address comments

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/AST/RecursiveASTVisitor.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
-#include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/Lexer.h"
+#include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/SmallVector.h"
 #include <memory>
 #include <optional>
 
 using namespace llvm;
 using namespace clang;
 using namespace ast_matchers;
 
private:
   internal::BoundNodesTreeBuilder *const Builder;
   internal::BoundNodesTreeBuilder ResultBindings;
   const internal::ASTMatchFinder::BindKind Bind;
   bool Matches;
 };
 
 AST_MATCHER_P(Stmt, forEveryDescendant, internal::Matcher<Stmt>, innerMatcher) {
   const DynTypedMatcher &DTM = static_cast<DynTypedMatcher>(innerMatcher);
-  
-  MatchDescendantVisitor Visitor(&DTM, Finder, Builder, ASTMatchFinder::BK_All);  
+  MatchDescendantVisitor Visitor(&DTM, Finder, Builder, ASTMatchFinder::BK_All);
   return Visitor.findMatch(DynTypedNode::create(Node));
 }
 
 // Matches a `Stmt` node iff the node is in a safe-buffer opt-out region
-AST_MATCHER_P(Stmt, notInSafeBufferOptOut, const UnsafeBufferUsageHandler *, Handler) {
+AST_MATCHER_P(Stmt, notInSafeBufferOptOut, const UnsafeBufferUsageHandler *,
+              Handler) {
   return !Handler->isSafeBufferOptOut(Node.getBeginLoc());
 }
 
 AST_MATCHER_P(CastExpr, castSubExpr, internal::Matcher<Expr>, innerMatcher) {
   return innerMatcher.matches(*Node.getSubExpr(), Finder, Builder);
 }
 
 // Returns a matcher that matches any expression 'e' such that `innerMatcher`
 // matches 'e' and 'e' is in an Unspecified Lvalue Context.
 static auto isInUnspecifiedLvalueContext(internal::Matcher<Expr> innerMatcher) {
   // clang-format off
   return
     expr(anyOf(
       implicitCastExpr(
         hasCastKind(CastKind::CK_LValueToRValue),
         castSubExpr(innerMatcher)),
       binaryOperator(
         hasAnyOperatorName("="),
         hasLHS(innerMatcher)
static Matcher matcher() {
     // FIXME: What if the index is integer literal 0? Should this be
     // a safe gadget in this case?
       // clang-format off
       return stmt(arraySubscriptExpr(
             hasBase(ignoringParenImpCasts(
               anyOf(hasPointerType(), hasArrayType()))),
             unless(hasIndex(integerLiteral(equals(0)))))
             .bind(ArraySubscrTag));
-      // clang-format on
   }
 
   const ArraySubscriptExpr *getBaseStmt() const override { return ASE; }
 
   DeclUseList getClaimedVarUseSites() const override {
     if (const auto *DRE =
             dyn_cast<DeclRefExpr>(ASE->getBase()->IgnoreParenImpCasts())) {
       return {DRE};
     }
 
     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 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`
+  const Expr *Ptr;          // the pointer expression in `PA`
 
 public:
-    PointerArithmeticGadget(const MatchFinder::MatchResult &Result)
       : 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() {
-    auto HasIntegerType = anyOf(
-          hasType(isInteger()), hasType(enumType()));
-    auto PtrAtRight = allOf(hasOperatorName("+"),
-                            hasRHS(expr(hasPointerType()).bind(PointerArithmeticPointerTag)),
-                            hasLHS(HasIntegerType));
-    auto PtrAtLeft = allOf(
-           anyOf(hasOperatorName("+"), hasOperatorName("-"),
+    auto HasIntegerType = anyOf(hasType(isInteger()), hasType(enumType()));
+    auto PtrAtRight =
+        allOf(hasOperatorName("+"),
+    auto PtrAtLeft =
+        allOf(anyOf(hasOperatorName("+"), hasOperatorName("-"),
                     hasOperatorName("+="), hasOperatorName("-=")),
               hasLHS(expr(hasPointerType()).bind(PointerArithmeticPointerTag)),
               hasRHS(HasIntegerType));
 
-    return stmt(binaryOperator(anyOf(PtrAtLeft, PtrAtRight)).bind(PointerArithmeticTag));
+    return stmt(binaryOperator(anyOf(PtrAtLeft, PtrAtRight))
+                    .bind(PointerArithmeticTag));
   }
 
   const Stmt *getBaseStmt() const override { return PA; }
 
   DeclUseList getClaimedVarUseSites() const override {
-    if (const auto *DRE =
-            dyn_cast<DeclRefExpr>(Ptr->IgnoreParenImpCasts())) {
+    if (const auto *DRE = dyn_cast<DeclRefExpr>(Ptr->IgnoreParenImpCasts())) {
       return {DRE};
     }
 
     return {};
   }
   // FIXME: pointer adding zero should be fine
-  //FIXME: this gadge will need a fix-it
+  // FIXME: this gadge will need a fix-it
 };
 
-
 /// A call of a function or method that performs unchecked buffer operations
 /// over one of its pointer parameters.
 class UnsafeBufferUsageAttrGadget : public WarningGadget {
-    constexpr static const char *const OpTag = "call_expr";
-    const CallExpr *Op;
 
 public:
-    UnsafeBufferUsageAttrGadget(const MatchFinder::MatchResult &Result)
       : WarningGadget(Kind::UnsafeBufferUsageAttr),
         Op(Result.Nodes.getNodeAs<CallExpr>(OpTag)) {}
 
   static bool classof(const Gadget *G) {
     return G->getKind() == Kind::UnsafeBufferUsageAttr;
   }
 
   static Matcher matcher() {
     return stmt(callExpr(callee(functionDecl(hasAttr(attr::UnsafeBufferUsage))))
-                          .bind(OpTag));
   }
   const Stmt *getBaseStmt() const override { return Op; }
 
-  DeclUseList getClaimedVarUseSites() const override {
-    return {};
-  }
+  DeclUseList getClaimedVarUseSites() const override { return {}; }
 };
-  
-
 // Represents expressions of the form `DRE[*]` in the Unspecified Lvalue
 // Context (see `isInUnspecifiedLvalueContext`).
 // Note here `[]` is the built-in subscript operator.
 class ULCArraySubscriptGadget : public FixableGadget {
 private:
-  static constexpr const char *const ULCArraySubscriptTag = "ArraySubscriptUnderULC";
+  static constexpr const char *const ULCArraySubscriptTag =
+      "ArraySubscriptUnderULC";
   const ArraySubscriptExpr *Node;
 
 public:
   ULCArraySubscriptGadget(const MatchFinder::MatchResult &Result)
       : FixableGadget(Kind::ULCArraySubscript),
         Node(Result.Nodes.getNodeAs<ArraySubscriptExpr>(ULCArraySubscriptTag)) {
     assert(Node != nullptr && "Expecting a non-null matching result");
   }
static Matcher matcher() {
     return expr(isInUnspecifiedLvalueContext(Target));
   }
 
   virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
 
   virtual const Stmt *getBaseStmt() const override { return Node; }
 
   virtual DeclUseList getClaimedVarUseSites() const override {
-    if (const auto *DRE = dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts())) {
+    if (const auto *DRE =
+            dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts())) {
       return {DRE};
     }
     return {};
   }
 };
 } // namespace
 
 namespace {

 namespace {
 // Strategy is a map from variables to the way we plan to emit fixes for
 // these variables. It is figured out gradually by trying different fixes
 // for different variables depending on gadgets in which these variables
 // participate.
 class Strategy {
 public:
   enum class Kind {
-    Wontfix,    // We don't plan to emit a fixit for this variable.
-    Span,       // We recommend replacing the variable with std::span.
-    Iterator,   // We recommend replacing the variable with std::span::iterator.
-    Array,      // We recommend replacing the variable with std::array.
-    Vector      // We recommend replacing the variable with std::vector.
+    Wontfix,  // We don't plan to emit a fixit for this variable.
+    Span,     // We recommend replacing the variable with std::span.
+    Iterator, // We recommend replacing the variable with std::span::iterator.
+    Array,    // We recommend replacing the variable with std::array.
+    Vector    // We recommend replacing the variable with std::vector.
   };
 
 private:
   using MapTy = llvm::DenseMap<const VarDecl *, Kind>;
 
   MapTy Map;
 
 public:
   Strategy() = default;
   Strategy(const Strategy &) = delete; // Let's avoid copies.
   Strategy(Strategy &&) = default;
 
-  void set(const VarDecl *VD, Kind K) {
-    Map[VD] = K;
-  }
+  void set(const VarDecl *VD, Kind K) { Map[VD] = K; }
 
   Kind lookup(const VarDecl *VD) const {
     auto I = Map.find(VD);
     if (I == Map.end())
       return Kind::Wontfix;
 
     return I->second;
   }
#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 FIXABLE_GADGET(name)                                                           \
-      if (Result.Nodes.getNodeAs<Stmt>(#name)) {                               \
-        FixableGadgets.push_back(std::make_unique<name ## Gadget>(Result));           \
-        NEXT;                                                                  \
-      }
+#define FIXABLE_GADGET(name)                                                   \
+  if (Result.Nodes.getNodeAs<Stmt>(#name)) {                                   \
+    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;                                                                  \
-      }
+#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!");
     }
   };
 
   MatchFinder M;
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
   // 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.FixableGadgets) {
     for (const auto *DRE : G->getClaimedVarUseSites()) {
       CB.Tracker.claimUse(DRE);
     }
   }
 
-  return {std::move(CB.FixableGadgets), std::move(CB.WarningGadgets), std::move(CB.Tracker)};
+  return {std::move(CB.FixableGadgets), std::move(CB.WarningGadgets),
+          std::move(CB.Tracker)};
 }
 
+// Compares AST nodes by source locations.
+template <typename NodeTy> struct CompareNode {
+  bool operator()(const NodeTy *N1, const NodeTy *N2) const {
+    return N1->getBeginLoc().getRawEncoding() <
+           N2->getBeginLoc().getRawEncoding();
+  }
+};
+
 struct WarningGadgetSets {
-  std::map<const VarDecl *, std::set<std::unique_ptr<WarningGadget>>> byVar;
+  std::map<const VarDecl *, std::set<std::unique_ptr<WarningGadget>>,
+           // To keep keys sorted by their locations in the map so that the
+           // order is deterministic:
+           CompareNode<VarDecl>>
+      byVar;
   // These Gadgets are not related to pointer variables (e. g. temporaries).
   llvm::SmallVector<std::unique_ptr<WarningGadget>, 16> noVar;
 };
 
 static WarningGadgetSets
 groupWarningGadgetsByVar(WarningGadgetList &&AllUnsafeOperations) {
   WarningGadgetSets result;
   // If some gadgets cover more than one
for (const DeclRefExpr *DRE : DREs) {
       if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
         FixablesForUnsafeVars.byVar[VD].emplace(std::move(F));
       }
     }
   }
   return FixablesForUnsafeVars;
 }
 
-bool clang::internal::anyConflict(
-    const SmallVectorImpl<FixItHint> &FixIts, const SourceManager &SM) {
+bool clang::internal::anyConflict(const SmallVectorImpl<FixItHint> &FixIts,
+                                  const SourceManager &SM) {
   // A simple interval overlap detection algorithm.  Sorts all ranges by their
   // begin location then finds the first overlap in one pass.
   std::vector<const FixItHint *> All; // a copy of `FixIts`
 
   for (const FixItHint &H : FixIts)
     All.push_back(&H);
   std::sort(All.begin(), All.end(),
             [&SM](const FixItHint *H1, const FixItHint *H2) {
if (!CurrHint ||
       // conflict:
       return true;
   }
   return false;
 }
 
 std::optional<FixItList>
 ULCArraySubscriptGadget::getFixits(const Strategy &S) const {
-  if (const auto *DRE = dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts()))
+  if (const auto *DRE =
+          dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts()))
     if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
       switch (S.lookup(VD)) {
       case Strategy::Kind::Span: {
         // If the index has a negative constant value, we give up as no valid
         // fix-it can be generated:
         const ASTContext &Ctx = // FIXME: we need ASTContext to be passed in!
             VD->getASTContext();
         if (auto ConstVal = Node->getIdx()->getIntegerConstantExpr(Ctx)) {

 template <typename NodeTy>
 static SourceLocation getPastLoc(const NodeTy *Node, const SourceManager &SM,
                                  const LangOptions &LangOpts) {
   return Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
 }
 
 // Return text representation of an `Expr`.
 static StringRef getExprText(const Expr *E, const SourceManager &SM,
-                               const LangOptions &LangOpts) {
   SourceLocation LastCharLoc = getPastLoc(E, SM, LangOpts);
 
   return Lexer::getSourceText(
       CharSourceRange::getCharRange(E->getBeginLoc(), LastCharLoc), SM,
       LangOpts);
 }
 
 // For a non-null initializer `Init` of `T *` type, this function returns
if (auto CxxNew = dyn_cast<CXXNewExpr>(Init->IgnoreImpCasts())) {
     ExtentText = getAPIntText(CArrTy->getSize());
   } else {
     // In cases `Init` is of the form `&Var` after stripping of implicit
     // casts, where `&` is the built-in operator, the extent is 1.
     if (auto AddrOfExpr = dyn_cast<UnaryOperator>(Init->IgnoreImpCasts()))
       if (AddrOfExpr->getOpcode() == UnaryOperatorKind::UO_AddrOf &&
           isa_and_present<DeclRefExpr>(AddrOfExpr->getSubExpr()))
         ExtentText = One;
-    // TODO: we can handle more cases, e.g., `&a[0]`, `&a`, `std::addressof`, and explicit casting, etc.
-    // etc.
+    // TODO: we can handle more cases, e.g., `&a[0]`, `&a`, `std::addressof`,
+    // and explicit casting, etc. etc.
   }
 
   SmallString<32> StrBuffer{};
   SourceLocation LocPassInit = getPastLoc(Init, SM, LangOpts);
 
   StrBuffer.append(", ");
   StrBuffer.append(ExtentText);
   StrBuffer.append("}");

 static FixItList fixVariableWithSpan(const VarDecl *VD,
                                      const DeclUseTracker &Tracker,
                                      const ASTContext &Ctx,
                                      UnsafeBufferUsageHandler &Handler) {
   const DeclStmt *DS = Tracker.lookupDecl(VD);
   assert(DS && "Fixing non-local variables not implemented yet!");
   if (!DS->isSingleDecl()) {
     // FIXME: to support handling multiple `VarDecl`s in a single `DeclStmt`
-    return{};
+    return {};
   }
   // Currently DS is an unused variable but we'll need it when
   // non-single decls are implemented, where the pointee type name
   // and the '*' are spread around the place.
   (void)DS;
 
   // FIXME: handle cases where DS has multiple declarations
   return fixVarDeclWithSpan(VD, Ctx, Handler.getUserFillPlaceHolder());

 }
 
 static std::map<const VarDecl *, FixItList>
 getFixIts(FixableGadgetSets &FixablesForUnsafeVars, const Strategy &S,
           const DeclUseTracker &Tracker, const ASTContext &Ctx,
           UnsafeBufferUsageHandler &Handler) {
   std::map<const VarDecl *, FixItList> FixItsForVariable;
   for (const auto &[VD, Fixables] : FixablesForUnsafeVars.byVar) {
-    FixItsForVariable[VD] = fixVariable(VD, S.lookup(VD), Tracker, Ctx, Handler);
+    FixItsForVariable[VD] =
+        fixVariable(VD, S.lookup(VD), Tracker, Ctx, Handler);
     // If we fail to produce Fix-It for the declaration we have to skip the
     // variable entirely.
     if (FixItsForVariable[VD].empty()) {
       FixItsForVariable.erase(VD);
       continue;
     }
     bool ImpossibleToFix = false;
     llvm::SmallVector<FixItHint, 16> FixItsForVD;
for (const auto &[VD, Fixables] : FixablesForUnsafeVars.byVar) {
     else
       FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),
                                    FixItsForVD.begin(), FixItsForVD.end());
     // We conservatively discard fix-its of a variable if
     // a fix-it overlaps with macros; or
     // a fix-it conflicts with another one
     if (overlapWithMacro(FixItsForVariable[VD]) ||
         clang::internal::anyConflict(FixItsForVariable[VD],
-                                     Ctx.getSourceManager())) {      
+                                     Ctx.getSourceManager())) {
       FixItsForVariable.erase(VD);
     }
   }
   return FixItsForVariable;
 }
 
 static Strategy
 getNaiveStrategy(const llvm::SmallVectorImpl<const VarDecl *> &UnsafeVars) {
void clang::checkUnsafeBufferUsage(const Decl *D,
   }
 
   for (const auto &[VD, WarningGadgets] : UnsafeOps.byVar) {
     auto FixItsIt =
         EmitFixits ? FixItsForVariable.find(VD) : FixItsForVariable.end();
     Handler.handleFixableVariable(VD, FixItsIt != FixItsForVariable.end()
                                           ? std::move(FixItsIt->second)
                                           : FixItList{});
     for (const auto &G : WarningGadgets) {
       Handler.handleUnsafeOperation(G->getBaseStmt(), /*IsRelatedToDecl=*/true);
     }
   }
 }

clang/test/SemaCXX/warn-unsafe-buffer-usage-fixits-local-var-span.cpp

-// REQUIRES: !system-windows
 // RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fdiagnostics-parseable-fixits %s 2>&1 | FileCheck %s
 typedef int * Int_ptr_t;
 typedef int Int_t;
 
 void local_array_subscript_simple() {
   int tmp;
   int *p = new int[10];
   // CHECK-DAG: fix-it:"{{.*}}":{[[@LINE-1]]:3-[[@LINE-1]]:11}:"std::span<int> p"