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

396

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

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

695–696

Nitpicks.

clang/unittests/Analysis/UnsafeBufferUsageTest.cpp

17

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

760

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

public:
   virtual void handleFixableVariable(const VarDecl *Variable,
                                      FixItList &&List) = 0;
 };
 
 // This function invokes the analysis and allows the caller to react to it
 // through the handler class.
 void checkUnsafeBufferUsage(const Decl *D, UnsafeBufferUsageHandler &Handler);
 
+// Tests if any two `FixItHint`s in `FixIts` conflict.  Two `FixItHint`s
+// conflict if they have overlapping source ranges.
+bool anyConflict(const SourceManager &SM, const llvm::SmallVectorImpl<FixItHint> &FixIts);
+
 /// The text indicating that the user needs to provide input there:
 constexpr static const char *const UserFillPlaceHolder = "...";
 } // end namespace clang
 
 #endif /* LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H */

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);  
   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).
public:
 
   // A variable is unclaimed if at least one use is unclaimed.
   bool hasUnclaimedUses(const VarDecl *VD) const {
     // FIXME: Can this be less linear? Maybe maintain a map from VDs to DREs?
     return any_of(*Uses, [VD](const DeclRefExpr *DRE) {
       return DRE->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl();
     });
   }
 
   void discoverDecl(const DeclStmt *DS) {
     for (const Decl *D : DS->decls()) {
       if (const auto *VD = dyn_cast<VarDecl>(D)) {
         // FIXME: Assertion temporarily disabled due to a bug in
         // ASTMatcher internal behavior in presence of GNU
         // statement-expressions. We need to properly investigate this
         // because it can screw up our algorithm in other ways.
         // assert(Defs.count(VD) == 0 && "Definition already discovered!");
static FixItList fixVariable(const VarDecl *VD, Strategy::Kind K,
   case Strategy::Kind::Array:
   case Strategy::Kind::Vector:
     llvm_unreachable("Strategy not implemented yet!");
   case Strategy::Kind::Wontfix:
     llvm_unreachable("Invalid strategy!");
   }
 }
 
+bool clang::anyConflict(const SourceManager &SM,
+                        const llvm::SmallVectorImpl<FixItHint> &FixIts) {
+  // A simple interval overlap detecting algorithm.  Sorts all ranges by their
+  // begin location then find any 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) {
+              return SM.isBeforeInTranslationUnit(H1->RemoveRange.getBegin(),
+                                                  H2->RemoveRange.getBegin());
+            });
+
+  const FixItHint *CurrHint = nullptr;
+
+  for (const FixItHint *Hint : All) {
+    if (!CurrHint ||
+        SM.isBeforeInTranslationUnit(CurrHint->RemoveRange.getEnd(),
+                                     Hint->RemoveRange.getBegin())) {
+      // Either to initialize `CurrHint` or `CurrHint` does not
+      // overlap with `Hint`:
+      CurrHint = Hint;
+    } else
+      // In case `Hint` overlaps the `CurrHint`, we found at least one
+      // conflict:
+      return true;
+  }
+  return false;
+}
+
 void clang::checkUnsafeBufferUsage(const Decl *D,
                                    UnsafeBufferUsageHandler &Handler) {
   assert(D && D->getBody());
 
   SmallSet<const VarDecl *, 8> WarnedDecls;
 
   auto [FixableGadgets, WarningGadgets, Tracker] = findGadgets(D);
 
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;
 
if (!Tracker.hasUnclaimedUses(VD) && VD->isLocalVarDecl()) {
       // fix for both variables, revert to the old one.
       Fixes = FixItList{};
       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));
+        Fixes->insert(Fixes->end(), F->begin(), F->end());
       }
     }
 
     if (Fixes) {
       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.
+      if (!anyConflict(Ctx.getSourceManager(), *Fixes))
         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 WarningGadget *G : VDWarningGadgets) {
         Handler.handleUnsafeOperation(G->getBaseStmt());
       }
     }
   }
 }

clang/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisTests
   CFGDominatorTree.cpp
   CFGTest.cpp
   CloneDetectionTest.cpp
   ExprMutationAnalyzerTest.cpp
   MacroExpansionContextTest.cpp
+  UnsafeBufferUsageTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisTests
   PRIVATE
   clangAnalysis
   clangAST
   clangASTMatchers
   clangBasic

clang/unittests/Analysis/UnsafeBufferUsageTest.cpp

+#include "gtest/gtest.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/FileManager.h"
+#include "clang/Analysis/Analyses/UnsafeBufferUsage.h"
+
+using namespace clang;
+
+namespace {
+// The test fixture.
+class UnsafeBufferUsageTest : public ::testing::Test {
+protected:
+  UnsafeBufferUsageTest()
+      : FileMgr(FileMgrOpts), DiagID(new DiagnosticIDs()),
+        Diags(DiagID, new DiagnosticOptions, new IgnoringDiagConsumer()),
+        SourceMgr(Diags, FileMgr) {}
+
+  FileSystemOptions FileMgrOpts;
+  FileManager FileMgr;
+  IntrusiveRefCntPtr<DiagnosticIDs> DiagID;
+  DiagnosticsEngine Diags;
+  SourceManager SourceMgr;
+};
+} // namespace
+
+TEST_F(UnsafeBufferUsageTest, FixItHintsConflict) {
+  const FileEntry *DummyFile = FileMgr.getVirtualFile("<virtual>", 100, 0);
+  FileID DummyFileID = SourceMgr.getOrCreateFileID(DummyFile, SrcMgr::C_User);
+  SourceLocation StartLoc = SourceMgr.getLocForStartOfFile(DummyFileID);
+
+#define MkDummyHint(Begin, End)                                                \
+  FixItHint::CreateReplacement(SourceRange(StartLoc.getLocWithOffset((Begin)), \
+                                           StartLoc.getLocWithOffset((End))),  \
+                               "dummy")
+
+  FixItHint H1 = MkDummyHint(0, 5);
+  FixItHint H2 = MkDummyHint(6, 10);
+  FixItHint H3 = MkDummyHint(20, 25);
+  llvm::SmallVector<FixItHint> Fixes;
+
+  // Test non-overlapping fix-its:
+  Fixes = {H1, H2, H3};
+  EXPECT_FALSE(anyConflict(SourceMgr, Fixes));
+  Fixes = {H3, H2, H1}; // re-order
+  EXPECT_FALSE(anyConflict(SourceMgr, Fixes));
+
+  // Test overlapping fix-its:
+  Fixes = {H1, H2, H3, MkDummyHint(0, 4) /* included in H1 */};
+  EXPECT_TRUE(anyConflict(SourceMgr, Fixes));
+
+  Fixes = {H1, H2, H3, MkDummyHint(10, 15) /* overlaps H2 */};
+  EXPECT_TRUE(anyConflict(SourceMgr, Fixes));
+
+  Fixes = {H1, H2, H3, MkDummyHint(7, 23) /* overlaps H2, H3 */};
+  EXPECT_TRUE(anyConflict(SourceMgr, Fixes));
+
+  Fixes = {H1, H2, H3, MkDummyHint(2, 23) /* overlaps H1, H2, and H3 */};
+  EXPECT_TRUE(anyConflict(SourceMgr, Fixes));
+}
 No newline at end of file