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

467

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

58–61

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

916–917

Nitpicks.

clang/unittests/Analysis/UnsafeBufferUsageTest.cpp

18

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

961

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

public:
   /// Returns a reference to the `Preprocessor`:
   virtual const Preprocessor & getPP() const;
 };
 
 // This function invokes the analysis and allows the caller to react to it
 // through the handler class.
 void checkUnsafeBufferUsage(const Decl *D, UnsafeBufferUsageHandler &Handler);
 
+namespace internal {
+// Tests if any two `FixItHint`s in `FixIts` conflict.  Two `FixItHint`s
+// conflict if they have overlapping source ranges.
+bool anyConflict(const llvm::SmallVectorImpl<FixItHint> &FixIts,
+                 const SourceManager &SM);
+} // namespace internal
 } // end namespace clang
 
 #endif /* LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H */

clang/lib/Analysis/UnsafeBufferUsage.cpp

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.
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) {
+  // 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;
+}
+
 Optional<FixItList>
 ULCArraySubscriptGadget::getFixits(const Strategy &S) const {
   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:
         return FixItList{};
       case Strategy::Kind::Wontfix:
case Strategy::Kind::Vector:
     llvm_unreachable("Strategy not implemented yet!");
   case Strategy::Kind::Wontfix:
     llvm_unreachable("Invalid strategy!");
   }
 }
 
 // Returns true iff there exists a `FixItHint` 'h' in `FixIts` such that the
 // `RemoveRange` of 'h' overlaps with a macro use.
 static bool overlapWithMacro(const FixItList &FixIts) {
   // FIXME: For now we only check if the range (or the first token) is (part of)
   // a macro expansion.  Ideally, we want to check for all tokens in the range.
   return llvm::any_of(FixIts, [](const FixItHint &Hint) {
     auto BeginLoc = Hint.RemoveRange.getBegin();
     if (BeginLoc.isMacroID())
       // If the range (or the first token) is (part of) a macro expansion:
       return true;
     return false;
   });
for (const auto &F : Fixables) {
                            CorrectFixes.end());
       }
     }
     if (ImpossibleToFix)
       FixItsForVariable.erase(VD);
     else
       FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),
                                    FixItsForVD.begin(), FixItsForVD.end());
-    // Fix-it shall not overlap with macros or/and templates:
-    if (overlapWithMacro(FixItsForVariable[VD])) {
+    // 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())) {
       FixItsForVariable.erase(VD);
     }
   }
   return FixItsForVariable;
 }
 
 static Strategy
 getNaiveStrategy(const llvm::SmallVectorImpl<const VarDecl *> &UnsafeVars) {

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(internal::anyConflict(Fixes, SourceMgr));
+  Fixes = {H3, H2, H1}; // re-order
+  EXPECT_FALSE(internal::anyConflict(Fixes, SourceMgr));
+
+  // Test overlapping fix-its:
+  Fixes = {H1, H2, H3, MkDummyHint(0, 4) /* included in H1 */};
+  EXPECT_TRUE(internal::anyConflict(Fixes, SourceMgr));
+
+  Fixes = {H1, H2, H3, MkDummyHint(10, 15) /* overlaps H2 */};
+  EXPECT_TRUE(internal::anyConflict(Fixes, SourceMgr));
+
+  Fixes = {H1, H2, H3, MkDummyHint(7, 23) /* overlaps H2, H3 */};
+  EXPECT_TRUE(internal::anyConflict(Fixes, SourceMgr));
+
+  Fixes = {H1, H2, H3, MkDummyHint(2, 23) /* overlaps H1, H2, and H3 */};
+  EXPECT_TRUE(internal::anyConflict(Fixes, SourceMgr));
+}
 No newline at end of file