[-Wunsafe-buffer-usage][PoC][WIP] Add #include <span> to emitted Fix-Its

[NoQ]

https://github.com/llvm/llvm-project/blob/llvmorg-16.0.0-rc3/clang/include/clang/Tooling/Transformer/RewriteRule.h#L38 hmmm.

[jkorous]

Note: The naive strategy doesn't add #include <span> to header files declaring a function which parameter we change.
We might have to track all the files we add a reference to a new type and make sure all of those have the necessary headers included.

[ziqingluo-90]

To emit an insertion of #include ... to each unique source file of fix-its associated to a variable VD according to VD's strategy.

Add tests:

1. If the insertion conflicts with other fix-its of VD, give up on fixing VD;
2. If there is already an equivalent #include ... in a file, do not emit the insertion to the file;
3. Included files (headers) will be inserted #include ..., if they have unsafe variables or parameters.

[t-rasmud]

clang/lib/Analysis/UnsafeBufferUsage.cpp

2253

Should the code that adds #include <span> be placed after this check that might erase a fixit for VD?

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

2253

One of the reasons that I place "conflict/macro overlap" check after the header insertion is that an inserted header could conflict with other fix-its. In that case, they should all be erased.

I agree that if we do the check earlier, we don't have to insert headers (which is expensive now) for erased fix-its. It is a performance gain for sure but the conflict aforementioned could happen.

I'm working on a performance optimization for this patch. Currently every variable fix-it invokes the construction of tooling::HeaderIncludes, in which the source file is scanned slowly. Even if there is just one single source file, the file is scanned n times, where n is the number of variables being fixed. Optimization will make sure that one source file is scanned at most once.

[t-rasmud]

clang/lib/Analysis/UnsafeBufferUsage.cpp

2253

Thank you for explaining your approach to me. Looking forward to the optimizations!

[ziqingluo-90]

Use a cache for loaded HeaderIncludes for a translation unit (TU). Loading HeaderIncludes is expensive so that we only want to load it for a unique file at most once per TU.

A class HeaderIncludesCache was created to represent the cache. One instance of it is created at AnalysisBasedWarnings::IssueWarnings for the whole TU.

[NoQ]

Caching is great!

But IIRC even a single invocation of tooling::HeaderIncludes() is too slow by compiler warning performance standards. We most likely need more optimizations before we can land this patch :(

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

50–56

Interesting, how does this really work when there's a lot of files? Do we add #include <span> in every file in which we introduce a use? This is probably always the correct thing to do, and it probably aligns pretty well with the include-what-you-use paradigm, but a many people don't actually follow that paradigm. In particular, if you include <span> in a header, you no longer need to include it again in the .cpp file. Maybe there's room for more savings there.

[ziqingluo-90]

Rebase

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

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H
 #define LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Stmt.h"
+#include "clang/Tooling/Inclusions/HeaderIncludes.h"  
 
 namespace clang {
 
+  /// This class caches loaded `tooling::HeaderIncludes` for each unique
+  /// `FileID`.
+  class HeaderIncludesCache {
+  private:
+    /// For a `FileID` 'F', `HeaderIncludeLocMap` contains 'F' iff
+    /// the `HeaderIncludes` for 'F' either has been loaded and cached already
+    /// or unloadable.  In either case, no more load attempt for `F` is ever
+    /// needed.  `HeaderIncludeLocMap.find(F)` points to a `std::nullopt` iff
+    /// the `HeaderIncludes` for 'F' is unloadable.
+    llvm::DenseMap<FileID, std::optional<tooling::HeaderIncludes>>
+    HeaderIncludeLocMap;
+
+  public:
+    /// \return header-insertion fix-its. One for each unique
+    /// `FileID` involved in `Fixes`
+    std::optional<std::vector<FixItHint>>
+    getHeaderIncludes(const SourceManager &SM,
+                      const llvm::SmallVectorImpl<FixItHint> &Fixes,
+                      StringRef HeaderName);
+  };
+
 using DefMapTy = llvm::DenseMap<const VarDecl *, std::vector<const VarDecl *>>;
 
 /// The interface that lets the caller handle unsafe buffer usage analysis
 /// results by overriding this class's handle... methods.
 class UnsafeBufferUsageHandler {
 public:
   UnsafeBufferUsageHandler() = default;
   virtual ~UnsafeBufferUsageHandler() = default;
 
   /// This analyses produces large fixits that are organized into lists
   /// of primitive fixits (individual insertions/removals/replacements).
   using FixItList = llvm::SmallVectorImpl<FixItHint>;
 
   /// Invoked when an unsafe operation over raw pointers is found.
   virtual void handleUnsafeOperation(const Stmt *Operation,
                                      bool IsRelatedToDecl) = 0;
 
   /// Invoked when a fix is suggested against a variable. This function groups
   /// all variables that must be fixed together (i.e their types must be changed to the
   /// same target type to prevent type mismatches) into a single fixit.
   virtual void handleUnsafeVariableGroup(const VarDecl *Variable,
                                          const DefMapTy &VarGrpMap,
                                          FixItList &&Fixes) = 0;
 
   /// Returns a reference to the `Preprocessor`:
   virtual bool isSafeBufferOptOut(const SourceLocation &Loc) const = 0;
 
+  /// Returns a reference to the cache for the translation unit:
+  virtual HeaderIncludesCache &headerIncludesCache() const = 0;  
+
   /// Returns the text indicating that the user needs to provide input there:
   virtual std::string
   getUserFillPlaceHolder(StringRef HintTextToUser = "placeholder") const {
     std::string s = std::string("<# ");
     s += HintTextToUser;
     s += " #>";
     return s;
   }

clang/lib/Analysis/CMakeLists.txt

add_clang_library(clangAnalysis
   UninitializedValues.cpp
   UnsafeBufferUsage.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
+  clangToolingInclusions
 
   DEPENDS
   omp_gen
   )
 
 add_subdirectory(plugins)
 add_subdirectory(FlowSensitive)

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/Decl.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
+#include "clang/Tooling/Inclusions/HeaderIncludes.h"
+#include "clang/Tooling/Inclusions/IncludeStyle.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/DenseSet.h"
 #include <memory>
 #include <optional>
 #include <sstream>
 #include <queue>
 
 using namespace llvm;
 using namespace clang;
 using namespace ast_matchers;
for (const auto &F : FixablesForUnsafeVars.byVar.find(Var)->second) {
     std::optional<FixItList> Fixits = F->getFixits(S);
     if (!Fixits) {
       return true;
     }
   }
   return false;
 }
 
+// Creates a fix-it through a `HeaderIncludes` for a source file identified
+// by`FID`. The fix-it inserts `#include <HeaderName>`.
+static std::optional<FixItHint>
+getHeaderIncludeFixIt(const tooling::HeaderIncludes &HI, FileID FID,
+                      StringRef HeaderName, const SourceManager &SM) {
+  std::optional<tooling::Replacement> Include =
+      HI.insert(HeaderName.str(), true, tooling::IncludeDirective::Include);
+
+  if (Include)
+    return FixItHint::CreateInsertion(
+        SM.getComposedLoc(FID, Include->getOffset()),
+        Include->getReplacementText());
+  return std::nullopt;
+}
+
+std::optional<std::vector<FixItHint>> HeaderIncludesCache::getHeaderIncludes(
+    const SourceManager &SM, const llvm::SmallVectorImpl<FixItHint> &FixesForVD,
+    StringRef HeaderName) {
+  if (FixesForVD.empty())
+    return std::nullopt;
+
+  std::vector<FixItHint> HeaderIncludeFixes{};
+  // Only include a header once for a file:
+  llvm::SmallSet<FileID, 4> SeenFileIDs;
+
+  for (FixItHint F : FixesForVD) {
+    FileID FID = SM.getDecomposedExpansionLoc(F.RemoveRange.getBegin()).first;
+
+    if (SeenFileIDs.contains(FID))
+      continue;
+
+    auto Iter = HeaderIncludeLocMap.find(FID);
+
+    if (Iter != HeaderIncludeLocMap.end()) {
+      if (Iter->getSecond())
+        if (auto F = getHeaderIncludeFixIt(*Iter->getSecond(), FID, HeaderName,
+                                           SM)) {
+          HeaderIncludeFixes.push_back(*F);
+          SeenFileIDs.insert(FID);
+          continue;
+        }
+      // Either `HeaderIncludes` is unloadable or something goes wrong in fix-it
+      // generation:
+      return std::nullopt;
+    }
+    // Never load `HeaderIncludes` for this `FID` before, attempt to load now:
+    if (auto FileContent = SM.getBufferOrNone(FID)) {
+      const FileEntry *FE = SM.getFileEntryForID(FID);
+      tooling::IncludeStyle InclStyle; // TODO set IncludeStyle
+      auto [Iter, EmplaceSucceed] = HeaderIncludeLocMap.try_emplace(
+          FID, tooling::HeaderIncludes(
+                   FE->getName(), FileContent.value().getBuffer(), InclStyle));
+
+      if (EmplaceSucceed)
+        if (auto F = getHeaderIncludeFixIt(*Iter->getSecond(), FID, HeaderName,
+                                           SM)) {
+          HeaderIncludeFixes.push_back(*F);
+          SeenFileIDs.insert(FID);
+          continue;
+        }
+    } else
+      // A `HeaderIncludes` for `FID` is unloadable:
+      HeaderIncludeLocMap[FID] = std::nullopt;
+    return std::nullopt;
+  }
+  return HeaderIncludeFixes;
+}
+
+static std::string getHeaderFilenameForStrategyKind(Strategy::Kind TargetType) {
+  switch (TargetType) {
+  case Strategy::Kind::Span:
+    return "span";
+  case Strategy::Kind::Array:
+    return "array";
+  case Strategy::Kind::Vector:
+    return "vector";
+  case Strategy::Kind::Iterator:
+    return "span";
+  case Strategy::Kind::Wontfix:
+    assert(false && "Wonfix strategy shouldn't be used to generate Fix-Its");
+  };
+}
+
 static std::map<const VarDecl *, FixItList>
 getFixIts(FixableGadgetSets &FixablesForUnsafeVars, const Strategy &S,
     const ASTContext &Ctx,
           /* The function decl under analysis */ const Decl *D,
     const DeclUseTracker &Tracker, UnsafeBufferUsageHandler &Handler,
     const DefMapTy &VarGrpMap) {
   std::map<const VarDecl *, FixItList> FixItsForVariable;
   for (const auto &[VD, Fixables] : FixablesForUnsafeVars.byVar) {
if (VarGroupForVD != VarGrpMap.end()) {
           FixItsForVariable.erase(V);
         }
         continue;
       }
     }
     FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),
                                  FixItsForVD.begin(), FixItsForVD.end());
 
+    // Now adding insertions of `#include ...` to fix-its of `VD`.
+    const SourceManager &SM = Ctx.getSourceManager();
+
+    if (auto HeaderIncFixes = Handler.headerIncludesCache().getHeaderIncludes(
+            SM, FixItsForVariable[VD],
+            getHeaderFilenameForStrategyKind(S.lookup(VD))))
+      FixItsForVariable[VD].insert(
+          FixItsForVariable[VD].end(),
+          std::make_move_iterator(HeaderIncFixes->begin()),
+          std::make_move_iterator(HeaderIncFixes->end()));
+    // FIXME: do we want to give up other fix-its in headers cannot be included?
+
     // Fix-it shall not overlap with macros or/and templates:
     if (overlapWithMacro(FixItsForVariable[VD]) ||
         clang::internal::anyConflict(FixItsForVariable[VD],
                                      Ctx.getSourceManager())) {
       FixItsForVariable.erase(VD);
       continue;
     }
   }
auto [FixableGadgets, WarningGadgets, Tracker] =
     findGadgets(D, Handler, EmitSuggestions);
 
   if (!EmitSuggestions) {
     // Our job is very easy without suggestions. Just warn about
     // every problematic operation and consider it done. No need to deal
     // with fixable gadgets, no need to group operations by variable.
     for (const auto &G : WarningGadgets) {
       Handler.handleUnsafeOperation(G->getBaseStmt(),
                                     /*IsRelatedToDecl=*/false);
     }
 
     // This return guarantees that most of the machine doesn't run when
     // suggestions aren't requested.
     assert(FixableGadgets.size() == 0 &&
            "Fixable gadgets found but suggestions not requested!");
     return;
   }

clang/lib/Sema/AnalysisBasedWarnings.cpp

 //===----------------------------------------------------------------------===//
 // Unsafe buffer usage analysis.
 //===----------------------------------------------------------------------===//
 
 namespace {
 class UnsafeBufferUsageReporter : public UnsafeBufferUsageHandler {
   Sema &S;
   bool SuggestSuggestions;  // Recommend -fsafe-buffer-usage-suggestions?
+  HeaderIncludesCache &HeaderIncludes;
 
 public:
-  UnsafeBufferUsageReporter(Sema &S, bool SuggestSuggestions)
-    : S(S), SuggestSuggestions(SuggestSuggestions) {}
+  UnsafeBufferUsageReporter(Sema &S, bool SuggestSuggestions,
+                            HeaderIncludesCache &HeaderIncludesCache)
+      : S(S), SuggestSuggestions(SuggestSuggestions),
+        HeaderIncludes(HeaderIncludesCache) {}
+
+  HeaderIncludesCache &headerIncludesCache() const override { return HeaderIncludes; }
 
   void handleUnsafeOperation(const Stmt *Operation,
                              bool IsRelatedToDecl) override {
     SourceLocation Loc;
     SourceRange Range;
     unsigned MsgParam = 0;
     if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(Operation)) {
       Loc = ASE->getBase()->getExprLoc();
void clang::sema::AnalysisBasedWarnings::IssueWarnings(
   // UnsafeBufferUsage analysis settings.
   bool UnsafeBufferUsageCanEmitSuggestions = S.getLangOpts().CPlusPlus20;
   bool UnsafeBufferUsageShouldEmitSuggestions =  // Should != Can.
       UnsafeBufferUsageCanEmitSuggestions &&
       DiagOpts.ShowSafeBufferUsageSuggestions;
   bool UnsafeBufferUsageShouldSuggestSuggestions =
       UnsafeBufferUsageCanEmitSuggestions &&
       !DiagOpts.ShowSafeBufferUsageSuggestions;
-  UnsafeBufferUsageReporter R(S, UnsafeBufferUsageShouldSuggestSuggestions);
+  HeaderIncludesCache HIC;
+  UnsafeBufferUsageReporter R(S, UnsafeBufferUsageShouldSuggestSuggestions,
+                              HIC);
 
   // The Callback function that performs analyses:
   auto CallAnalyzers = [&](const Decl *Node) -> void {
     // Perform unsafe buffer usage analysis:
     if (!Diags.isIgnored(diag::warn_unsafe_buffer_operation,
                          Node->getBeginLoc()) ||
         !Diags.isIgnored(diag::warn_unsafe_buffer_variable,
                          Node->getBeginLoc())) {

clang/test/SemaCXX/warn-unsafe-buffer-usage-fixits-include-header/span

+// Dummy std::span header
 No newline at end of file

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

+// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -isystem %S -fdiagnostics-parseable-fixits -fsafe-buffer-usage-suggestions %s 2>&1 | FileCheck %s
+
+// No `#include <span>` will be emitted if it's already included
+
+#include <span>
+// CHECK-NOT: fix-it:"{{.*}}:"#include <span>\n"
+
+void unsafe_code(int *p) {
+  // CHECK: fix-it:"{{.*}}:{[[@LINE-1]]:18-[[@LINE-1]]:24}:"std::span<int> p"
+  int tmp;
+  tmp = p[5];
+}
+// CHECK: fix-it:"{{.*}}:{[[@LINE-1]]:2-[[@LINE-1]]:2}:"\n{{\[}}{{\[}}clang::unsafe_buffer_usage{{\]}}{{\]}}\nvoid unsafe_code(int *p) {return unsafe_code(std::span<int>(p, <# size #>));}\n"

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

+// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fdiagnostics-parseable-fixits %s 2>&1 | FileCheck %s
+
+// For now, insertions of `#include` and an unsafe-buffer attribute
+// conflict at the beginning of the source file. So we do not emit
+// fix-its for the parameter `p`.
+
+// CHECK-NOT: fix-it:
+void unsafe_code(int *p);
+
+void unsafe_code(int *p) {
+  int tmp;
+  tmp = p[5];
+}

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

+// RUN:
+// This file is included in test: warn-unsafe-buffer-usage-fixits-include-header.cpp
+void unsafe_code() {
+  int tmp;
+  int *p = new int[10];
+  tmp = p[5];
+}

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

+// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fdiagnostics-parseable-fixits -fsafe-buffer-usage-suggestions %s 2>&1 | FileCheck %s
+
+// Make sure that if we emit Fix-Its for an included file we also add
+// the #include directive to that file (and not necessarily the main
+// file).
+#include "warn-unsafe-buffer-usage-fixits-include-header-included.cpp"
+// CHECK: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-include-header-included.cpp":{3:1-3:1}:"#include <span>\n"
+// CHECK: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-include-header.cpp":{[[@LINE-1]]:1-[[@LINE-1]]:1}:"#include <span>\n"
+// CHECK: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-include-header.cpp":{[[@LINE-2]]:1-[[@LINE-2]]:1}:"#include <span>\n"
+
+
+// Both the fix-its for `p` in `unsafe_code2` and `unsafe_code3` emit an insertion of `#include <span>`:
+
+void unsafe_code2() {
+  int tmp;
+  int *p = new int[10];
+  tmp = p[5];
+}
+
+
+void unsafe_code3() {
+  int tmp;
+  int *p = new int[10];
+  tmp = p[5];
+}

clang/test/SemaCXX/warn-unsafe-buffer-usage-fixits-include-header/warn-unsafe-buffer-usage-fixits-parm-in-header.h

+void f(); // some irrelevant decl
+
+void unsafe_code(int *p);

clang/test/SemaCXX/warn-unsafe-buffer-usage-fixits-include-header/warn-unsafe-buffer-usage-fixits-parm-in-header.cpp

+// RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fdiagnostics-parseable-fixits -fsafe-buffer-usage-suggestions %s 2>&1 | FileCheck %s
+
+// Test that if a function parameter in header needs to be fixed, a
+// `#include <span>` is inserted in header as well.
+
+// "CHECK DAG" is needed here since we are not sure whether fix-its in the header are emitted first.
+
+#include "warn-unsafe-buffer-usage-fixits-parm-in-header.h"
+// CHECK-DAG: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-parm-in-header.h":{1:1-1:1}:"#include <span>\n"
+// CHECK-DAG: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-parm-in-header.h":{3:1-3:1}:"{{\[}}{{\[}}clang::unsafe_buffer_usage{{\]}}{{\]}}\n"
+// CHECK-DAG: fix-it:"{{.*}}warn-unsafe-buffer-usage-fixits-parm-in-header.h":{3:25-3:25}:";\nvoid unsafe_code(std::span<int> p)"
+// CHECK-DAG: fix-it:"{{.*}}:{[[@LINE-3]]:1-[[@LINE-3]]:1}:"#include <span>\n"
+
+void unsafe_code(int *p) {
+  // CHECK-DAG: fix-it:"{{.*}}:{[[@LINE-1]]:18-[[@LINE-1]]:24}:"std::span<int> p"
+  int tmp;
+  tmp = p[5];
+}
+// CHECK-DAG: fix-it:"{{.*}}:{[[@LINE-1]]:2-[[@LINE-1]]:2}:"\n{{\[}}{{\[}}clang::unsafe_buffer_usage{{\]}}{{\]}}\nvoid unsafe_code(int *p) {return unsafe_code(std::span<int>(p, <# size #>));}\n"

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

 // RUN: %clang_cc1 -std=c++20 -Wunsafe-buffer-usage -fdiagnostics-parseable-fixits -fsafe-buffer-usage-suggestions -include %s %s 2>&1 | FileCheck %s
 
 // TODO test if there's not a single character in the file after a decl or def
 
 #ifndef INCLUDE_ME
 #define INCLUDE_ME
 
+// FIXME: currently the insertion of `#include<span>` conflicts with
+// the insertion of the unsafe-buffer attribute if both of them are
+// inserted at the same location.
+void f();
+
 void simple(int *p);
 // CHECK-DAG: fix-it:{{.*}}:{[[@LINE-1]]:1-[[@LINE-1]]:1}:"{{\[}}{{\[}}clang::unsafe_buffer_usage{{\]}}{{\]}}\n"
 // CHECK-DAG: fix-it:{{.*}}:{[[@LINE-2]]:20-[[@LINE-2]]:20}:";\nvoid simple(std::span<int> p)"
 
 #else
 
 void simple(int *);
 // CHECK-DAG: fix-it:{{.*}}:{[[@LINE-1]]:1-[[@LINE-1]]:1}:"{{\[}}{{\[}}clang::unsafe_buffer_usage{{\]}}{{\]}}\n"