[-Wunsafe-buffer-usage] Filter out conflicting fix-its

[ziqingluo-90]

Summary

Two fix-its conflict if they have overlapping source ranges. We shall not emit conflicting fix-its.
This patch adds a class to find all conflicting fix-its (as well as their associated gadgets or declarations).

[NoQ]

Looks awesome!

I'm worried that the test is going to rapidly become stale as you develop fixits for DeclStmt further. It might make sense to write some unittests for this class directly, to put into clang/unittest/Analysis/.... Then you can create some fixits defined by hand, without invoking UnsafeBufferUsage analysis, and feed them to this class directly and verify the results.

Also let's explain motivation a bit more. Normally compiler warnings don't need such machine because the fixits they come with are very simple and hand-crafted. However, unsafe buffer usage analysis is a large emergent behavior machine that may fix different parts of user code, and different parts of the machine that can produce parts of such fixits aren't necessarily aware of each other. In some cases no progress can be made without making sure these parts of the machine talk to each other. However, every time the machine does emit individual fixits, they're actually correct; conflicts between such fixits are entirely a representation problem (we're unable to present overlapping fixits to the user because this requires us to resolve the merge conflict), not an underlying correctness problem. So @ziqingluo-90 is implementing a bailout for the situation when the fixits were perfectly correct in isolation but can't be properly displayed to the user due to merge conflicts between them. This makes it possible for such "merge conflicts" detection to be purely SourceRange-based, so it doesn't need to take the details of the underlying AST into account.

clang/lib/Analysis/UnsafeBufferUsage.cpp

406

Result is unused here!

[ziqingluo-90]

In D141338#4042050, @NoQ wrote:

Looks awesome!

I'm worried that the test is going to rapidly become stale as you develop fixits for DeclStmt further. It might make sense to write some unittests for this class directly, to put into clang/unittest/Analysis/.... Then you can create some fixits defined by hand, without invoking UnsafeBufferUsage analysis, and feed them to this class directly and verify the results.

Also let's explain motivation a bit more. Normally compiler warnings don't need such machine because the fixits they come with are very simple and hand-crafted. However, unsafe buffer usage analysis is a large emergent behavior machine that may fix different parts of user code, and different parts of the machine that can produce parts of such fixits aren't necessarily aware of each other. In some cases no progress can be made without making sure these parts of the machine talk to each other. However, every time the machine does emit individual fixits, they're actually correct; conflicts between such fixits are entirely a representation problem (we're unable to present overlapping fixits to the user because this requires us to resolve the merge conflict), not an underlying correctness problem. So @ziqingluo-90 is implementing a bailout for the situation when the fixits were perfectly correct in isolation but can't be properly displayed to the user due to merge conflicts between them. This makes it possible for such "merge conflicts" detection to be purely SourceRange-based, so it doesn't need to take the details of the underlying AST into account.

Thanks for adding the motivation here!

I updated the revision by getting rid of things we don't need for now.
At this point, we just need to tell if there is any conflict in the fix-its generated for one variable (including variable declaration fix-its and variable usage fix-its). If there is any, we do NOT emit any fix-it for that variable.

At some point later, we may want to know the exact conflicting subsets. That will be another patch.

[NoQ]

Looks awesome!

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

45–48 ↗

(On Diff #488429)

Maybe we should put it into some namespace, so that it didn't look like it's part of our public interface?

clang/lib/Analysis/UnsafeBufferUsage.cpp

817–818

Nitpicks.

clang/unittests/Analysis/UnsafeBufferUsageTest.cpp

17 ↗

(On Diff #488429)

Oh my, you constructed it just like that and it worked? This is awesome!

[ziqingluo-90]

Rebase the change

[NoQ]

Looks great!

clang/lib/Analysis/UnsafeBufferUsage.cpp

851

clang/lib/Analysis/UnsafeBufferUsage.cpp

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));
 }
 } // namespace clang::ast_matchers
 
 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>;
 
+// To bind each `FixItList` with the `FixableGadget` which it will fix:
+// FIXME: for now declarations are not Gadgets so a FixItList is associated to
+// either a Gadget or a VarDecl (only one of them is significant).
+using GadgetFix =
+    std::tuple<FixItList, const class FixableGadget *, const class VarDecl *>;
+// naming component indexes of `GadgetFix`:
+constexpr const int GFFixItList = 0;
+// constexpr const int GFGadget = 1;  //unused for now
+constexpr const int GFVarDecl = 2;
+
 // Defined below.
 class Strategy;
 } // namespace
 
 // Because we're dealing with raw pointers, let's define what we mean by that.
 static auto hasPointerType() {
     return hasType(hasCanonicalType(pointerType()));
 }
DeclUseList getClaimedVarUseSites() const override {
     return {};
   }
   // FIXME: pointer adding zero should be fine
   //FIXME: this gadge will need a fix-it
 };
 } // namespace
 
 namespace {
+// This class represents all fixes generated in one function declaration, and
+// allows to iterate over the non-conflicting subset as well as its'
+// complementary subset (i.e., conflicting subset).  Any fix in the
+// non-conflicting subset does not conflict with any other generated fix.  Two
+// fixes conflict if their source ranges overlap.
+class NonConflictingFixes {
+private:
+  // All Fix-its:
+  const GadgetFix * const FixIts;
+
+  // Number of Fix-its;
+  const int NumFixIts;
+
+  // Indices of Fix-its in `FixIts` that shall not be emitted:
+  BitVector ConflictingFixIts;
+
+public:
+  /// \return the range of the non-conflicting `GadgetFixIt`s
+  auto nonConflictingFixIts() const {
+    const GadgetFix *Begin = FixIts;
+    const GadgetFix *End = FixIts + NumFixIts;
+    const BitVector &BV = ConflictingFixIts;
+
+    return llvm::make_filter_range(llvm::make_range(Begin, End),
+                                   [&BV, Begin](const GadgetFix &Elt) {
+                                     return !BV.test(&Elt - Begin);
+                                   });
+  }
+
+  /// \return the range of the conflicting `GadgetFixIt`s
+  auto conflictingFixIts() const {
+    const GadgetFix *Begin = FixIts;
+    const GadgetFix *End = FixIts + NumFixIts;
+    std::vector<GadgetFix> Result;
+    const BitVector &BV = ConflictingFixIts;
+
+    return llvm::make_filter_range(
+        llvm::make_range(Begin, End),
+        [&BV, Begin](const GadgetFix &Elt) { return BV.test(&Elt - Begin); });
+  }
+
+  // The constructor. Populating `ConflictingFixIts` and `ConflictingGroups`:
+  NonConflictingFixes(const SourceManager &SM,
+                       const std::vector<GadgetFix> &&FixIts)
+      : FixIts(FixIts.data()), NumFixIts(FixIts.size()) {
+    // To find out all conflicting hints (i.e., `FixItHint`s), we sorts the
+    // source ranges of all hints and keeps "merging" adjacent ones if they
+    // conflict. Eventually, we have a sequence of non-conflicting source
+    // ranges, each of which is associated to a set of fix-its.  For each such
+    // fix-it set `F`,  if `F` has more than one elements, `F` is added to
+    // `ConflictingFixIts`.
+
+    // Wrap a `FixItHint`'s source range with the index of its' onwer in
+    // `FixIts`:
+    using HintSrcRange_t = std::pair<SourceRange, int>;
+    std::vector<HintSrcRange_t> AllHintRanges;
+    const int NumFixIts = FixIts.size();
+
+    for (int i = 0; i < NumFixIts; i++)
+      for (FixItHint Hint : get<GFFixItList>(FixIts[i])) {
+        AllHintRanges.emplace_back(Hint.RemoveRange.getAsRange(), i);
+    }
+    // Sorts all hints' source ranges:
+    std::sort(AllHintRanges.begin(), AllHintRanges.end(),
+              [&SM](const HintSrcRange_t &R1, const HintSrcRange_t &R2) {
+                return SM.isBeforeInTranslationUnit(R1.first.getBegin(),
+                                                    R2.first.getBegin());
+              });
+
+    // To iterate and merge conflicting source ranges, maintaining
+    // `MergedRange`--- the source range merged from the most recently
+    //                  iterated ones; and
+    // `MRFixIts`--- the set of indices of fix-it in `FixIts` associated
+    //               to `MergedRange`.  These fix-its owns hints covered by
+    //               the `MergedRange`.
+    SourceRange MergedRange;
+    BitVector MRFixIts = BitVector(FixIts.size());
+
+    ConflictingFixIts = BitVector(FixIts.size());
+    for (auto &HintRange : AllHintRanges) {
+      if (MRFixIts.none() ||
+          SM.isBeforeInTranslationUnit(MergedRange.getEnd(),
+                                       HintRange.first.getBegin())) {
+        // In this case we need a "new" `MergedRange` as either it is the
+        // initial case or the current `HintRange` does not overlap the
+        // `MergedRange`.
+        // Before having a "new" `MergedRange`, to save the associated
+        // conflicting fix-its in `ConflictingFixIts`:
+        if (MRFixIts.count() > 1)
+          ConflictingFixIts |= MRFixIts;
+        MRFixIts.reset();
+        MergedRange =
+            SourceRange(HintRange.first.getBegin(), HintRange.first.getEnd());
+      } else {
+        // In case `HintRange` overlaps the `MergedRange`:
+        if (SM.isBeforeInTranslationUnit(MergedRange.getEnd(),
+                                         HintRange.first.getEnd())) {
+          // Expanding `MergedRange` to include `HintRange`:
+          MergedRange.setEnd(HintRange.first.getEnd());
+        } // Else, `MergedRange` includes `HintRange` already.
+      }
+      MRFixIts.set(HintRange.second);
+    }
+    // Saving conflicting fix-its associated to the last `MergedRange`:
+    if (MRFixIts.count() > 1)
+      ConflictingFixIts |= MRFixIts;
+  }
+};
+
 // An auxiliary tracking facility for the fixit analysis. It helps connect
 // declarations to its and make sure we've covered all uses with our analysis
 // before we try to fix the declaration.
 class DeclUseTracker {
   using UseSetTy = SmallSet<const DeclRefExpr *, 16>;
   using DefMapTy = DenseMap<const VarDecl *, const DeclStmt *>;
 
   // Allocate on the heap for easier move.

 // `int **`, the converted type will be `span<int*>`.
 // We need to handle multi-level pointers correctly later.
 //
 // Parameters:
 //   `D` a pointer the variable declaration node
 //   `Ctx` a reference to the ASTContext
 // Returns:
 //    the generated fix-it
-static FixItHint fixVarDeclWithSpan(const VarDecl *D,
+static FixItList fixVarDeclWithSpan(const VarDecl *D,
                                           const ASTContext &Ctx) {
   const QualType &T = D->getType().getDesugaredType(Ctx);
   const QualType &SpanEltT = T->getPointeeType();
   assert(!SpanEltT.isNull() && "Trying to fix a non-pointer type variable!");
 
   SmallString<32> Replacement;
   raw_svector_ostream OS(Replacement);
 
   // Simply make `D` to be of span type:
   OS << "std::span<" << SpanEltT.getAsString() << "> " << D->getName();
   if (const Expr *Init = D->getInit())
     populateInitializerFixItWithSpan(Init, Ctx, OS);
 
-  return FixItHint::CreateReplacement(
-      SourceRange{D->getInnerLocStart(), D->getEndLoc()}, OS.str());
+  return {FixItHint::CreateReplacement(
+      SourceRange{D->getInnerLocStart(), D->getEndLoc()}, OS.str())};
 }
 
 static FixItList fixVariableWithSpan(const VarDecl *VD,
                                      const DeclUseTracker &Tracker,
                                      const ASTContext &Ctx) {
   const DeclStmt *DS = Tracker.lookupDecl(VD);
   assert(DS && "Fixing non-local variables not implemented yet!");
-  assert(DS->getSingleDecl() == VD &&
-         "Fixing non-single declarations not implemented yet!");
+  //  assert(DS->getSingleDecl() == VD &&
+  //         "Fixing non-single declarations not implemented yet!"); // now they will conflict
   // 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
-  FixItHint Fix = fixVarDeclWithSpan(VD, Ctx);
-  return {Fix};
+  return fixVarDeclWithSpan(VD, Ctx);
 }
 
 static FixItList fixVariable(const VarDecl *VD, Strategy::Kind K,
                              const DeclUseTracker &Tracker,
                              const ASTContext &Ctx) {
   switch (K) {
-  case Strategy::Kind::Span:
+  case Strategy::Kind::Span: {
+    if (!VD->getType()->getPointeeType().isNull())
+      // Only pointer-type variable can be transformed to be of `std::span`:
       return fixVariableWithSpan(VD, Tracker, Ctx);
+    return {};
+  }
   case Strategy::Kind::Iterator:
   case Strategy::Kind::Array:
   case Strategy::Kind::Vector:
     llvm_unreachable("Strategy not implemented yet!");
   case Strategy::Kind::Wontfix:
     llvm_unreachable("Invalid strategy!");
   }
 }
 
 void clang::checkUnsafeBufferUsage(const Decl *D,
                                    UnsafeBufferUsageHandler &Handler) {
   assert(D && D->getBody());
 
   SmallSet<const VarDecl *, 8> WarnedDecls;
 
   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
for (const auto &G : WarningGadgets) {
     bool Pushed = false;
     for (const DeclRefExpr *DRE : ClaimedVarUseSites) {
       if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
         Map[VD].second.push_back(G.get());
         Pushed = true;
       }
     }
 
     if (!Pushed) {
       // We won't return to this gadget later. Emit the warning right away.
       Handler.handleUnsafeOperation(G->getBaseStmt());
       continue;
     }
   }
 
   Strategy S;
+  const ASTContext &Ctx = D->getASTContext();
+  std::vector<GadgetFix> Fixes; // Collecting all fixes
 
   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 (VDWarningGadgets.empty())
       continue;
 
-    std::optional<FixItList> Fixes;
-    const ASTContext &Ctx = D->getASTContext();
+    std::optional<std::vector<GadgetFix>> VDFixes; // fix-its for this variable
 
     if (VD->isLocalVarDecl()) {
       // For test purpose, we emit fix-its for local variables always for
       // now.
       // FIXME: Remove this code block once we have needed `FixableGadget`s
       S.set(VD, Strategy::Kind::Span);
-      Handler.handleFixableVariable(
-          VD, fixVariable(VD, S.lookup(VD), Tracker, Ctx));
+      Fixes.emplace_back(fixVariable(VD, S.lookup(VD), Tracker, Ctx), nullptr,
+                           VD);
     }
     // 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{};
+      VDFixes = std::vector<GadgetFix>();
       for (const FixableGadget *G : VDFixableGadgets) {
         std::optional<FixItList> F = G->getFixits(S);
         if (!F) {
-          Fixes = std::nullopt;
+          VDFixes = std::nullopt;
           break;
         }
-
-        for (auto &&Fixit: *F)
-          Fixes->push_back(std::move(Fixit));
+        VDFixes->emplace_back(std::move(*F), G, nullptr);
       }
     }
 
-    if (Fixes) {
+    if (VDFixes) {
+      // If we reach this point, the strategy is applicable.
       FixItList VarF = fixVariable(VD, S.lookup(VD), Tracker, Ctx);
 
-      Fixes->insert(Fixes->end(), std::make_move_iterator(VarF.begin()),
-                    std::make_move_iterator(VarF.end()));
-      // If we reach this point, the strategy is applicable.
-      Handler.handleFixableVariable(VD, std::move(*Fixes));
+      Fixes.insert(Fixes.end(), std::make_move_iterator(VDFixes->begin()),
+                   std::make_move_iterator(VDFixes->end()));
+      Fixes.emplace_back(std::move(VarF), nullptr, VD);
     } else {
       // The strategy has failed. Emit the warning without the fixit.
       S.set(VD, Strategy::Kind::Wontfix);
       for (const WarningGadget *G : VDWarningGadgets) {
         Handler.handleUnsafeOperation(G->getBaseStmt());
       }
     }
   }
+
+  // Process all fixes with the knowledge if they conflict:
+  NonConflictingFixes NC =
+      NonConflictingFixes{Ctx.getSourceManager(), std::move(Fixes)};
+
+  for (GadgetFix GF : NC.nonConflictingFixIts()) {
+    // To emit fix-its for non-conflicting variable declaration fixes
+    if (get<GFVarDecl>(GF) != nullptr) {
+      Handler.handleFixableVariable(get<GFVarDecl>(GF),
+                                    std::move(get<GFFixItList>(GF)));
+    }
+  }
+  for (auto CGF : NC.conflictingFixIts())
+    // To emit warnings only (with empty fix-its) for conflicting variable
+    // declaration fixes
+    if (get<GFVarDecl>(CGF) != nullptr) {
+      Handler.handleFixableVariable(get<GFVarDecl>(CGF), FixItList{});
+    }
 }

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

 // CHECK: std::span<int> q{&var, 1};
 // CHECK: foo(p[5], q[5]);
   int (*p)[10] = &a; // expected-warning{{variable 'p' participates in unchecked buffer operations}}
   int * q = &var; // expected-warning{{variable 'q' participates in unchecked buffer operations}}
   // These two expressions involve unsafe buffer accesses, which will
   // crash at runtime after applying the fix-it,
   foo(p[5], q[5]);  // expected-warning2{{unchecked operation on raw buffer in expression}}
 }
+
+void fixits_conflict() {
+  // no fix-its will be emitted since fixits of `a` and `b` conflict in source locations:
+  // CHECK: int * a = new int[10],
+  // CHECK:   * b = new int[10];
+  // CHECK: foo(a[5], b[5]);
+  int * a = new int[10], // expected-warning{{variable 'a' participates in unchecked buffer operations}} \
+       expected-warning{{variable 'b' participates in unchecked buffer operations}}
+    * b = new int[10];
+
+  foo(a[5], b[5]);     // expected-warning2{{unchecked operation on raw buffer in expression}}
+
+
+  // CHECK: std::span<int> c{new int [10], 10};
+  // CHECK: foo(c[5]);
+  int * c = new int[10]; // expected-warning{{variable 'c' participates in unchecked buffer operations}}
+
+  foo(c[5]); // expected-warning{{unchecked operation on raw buffer in expression}}
+}