[-Wunsafe-buffer-usage][NFC] Slightly refactor and optimize the code

[ziqingluo-90]

Summary

Slightly refactor and optimize the code in preparation for implementing grouping parameters for a single fix-it.

[ziqingluo-90]

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

26

Use the VariableGroupsManager class as an interface to clients. It hides the details about how groups are implemented (which may involve several containers).

clang/lib/Analysis/UnsafeBufferUsage.cpp

1182

To make the order of variables in every group deterministic.

2313

Instead of calling fixVariable to generate fix-its for group mates, directly copying those fix-its from the FixItsForVariable container.

At this point, FixItsForVariable is complete. That is, it maps every variable to its own fix-its (excluding fix-its of group mates).

2332

An implementation of VariableGroupsManager: keep a unique copy of each group in Groups and use their indexes for access.

Note that getGroupOfVar assumes that Var must in the map. This is guaranteed by the changed made in D155524---only "Fixables" associated to variables in the final graph(es) will stay and be fixed. The key set of the VarGrpMap is the set of variables in the final graph(es). Therefore, after the graph(es) are computed and "Fixables" are pruned, VarGrpMap is the variable domain that we will deal with.

2470

Use SetVector to make order deterministic.

2530

I removed this guard so that VarGrpMap is complete---it has an entry for every variable that we need to deal with later.

2555

Mapping variables to group indexes instead of groups themselves to avoid copies.

clang/lib/Sema/AnalysisBasedWarnings.cpp

2180

Factor this procedure out to a method for easy re-use later.

[t-rasmud]

clang/lib/Analysis/UnsafeBufferUsage.cpp

2313

Do you mean "including fix-its of group mates"? If not, I might have misunderstood the changes and will take a look again.

2555

I think this is a really clever optimization and believe it would save a bunch of time and space in code having significant variable grouping.

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

1182

Would it make sense to immediately clean up the regexps in tests then?

2479–2480

These objects don't really define any move semantics, so std::move is probably redundant.

Maybe structured binding instead?

[t-rasmud]

clang/lib/Analysis/UnsafeBufferUsage.cpp

1182

@NoQ I had an offline discussion with @ziqingluo-90 about this and we agreed (IIRC) that I would clean up the tests since I added those regexps. I plan to create a patch as soon as this lands. Does that make sense?

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

1182

Yes sure SGTM!

[ziqingluo-90]

clang/lib/Analysis/UnsafeBufferUsage.cpp

2313

No.
FixItsForVariable is a map from variables to their own fix-its, excluding fix-its of group mates.
FinalFixItsForVariable is a map from variables to the set of fix-its that fix the whole group.

The construction of FinalFixItsForVariable reads FixItsForVariable.

Maybe I should have better names for these two variables.

[t-rasmud]

LGTM!

clang/lib/Analysis/UnsafeBufferUsage.cpp

2313

Ah! That makes sense, I misread the FixItsForVariable as FinalFixItsForVariable in you comment. Thank you for explaining.

[NoQ]

LGTM!

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

 #define LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Stmt.h"
 #include "llvm/Support/Debug.h"
 
 namespace clang {
 
-using DefMapTy = llvm::DenseMap<const VarDecl *, std::vector<const VarDecl *>>;
+using VarGrpTy = std::vector<const VarDecl *>;
+using VarGrpRef = ArrayRef<const VarDecl *>;
+
+class VariableGroupsManager {
+public:
+  VariableGroupsManager() = default;
+  virtual ~VariableGroupsManager() = default;
+  /// Returns the set of variables (including `Var`) that need to be fixed
+  /// together in one step.
+  ///
+  /// `Var` must be a variable that needs fix (so it must be in a group).
+  virtual VarGrpRef getGroupOfVar(const VarDecl *Var) const;
+};
 
 /// The interface that lets the caller handle unsafe buffer usage analysis
 /// results by overriding this class's handle... methods.
 class UnsafeBufferUsageHandler {
 #ifndef NDEBUG
 public:
   // A self-debugging facility that you can use to notify the user when
   // suggestions or fixits are incomplete.
public:
   /// 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,
+                                         const VariableGroupsManager &VarGrpMgr,
                                          FixItList &&Fixes) = 0;
 
 #ifndef NDEBUG
 public:
   bool areDebugNotesRequested() {
     DEBUG_WITH_TYPE("SafeBuffers", return true);
     return false;
   }

clang/lib/Analysis/UnsafeBufferUsage.cpp

if (!AssociatedWithVarDecl) {
       result.noVar.push_back(G.get());
       continue;
     }
   }
   return result;
 }
 
 struct FixableGadgetSets {
-  std::map<const VarDecl *, std::set<const FixableGadget *>> byVar;
+  std::map<const VarDecl *, std::set<const FixableGadget *>,
+           // To keep keys sorted by their locations in the map so that the
+           // order is deterministic:
+           CompareNode<VarDecl>>
+      byVar;
 };
 
 static FixableGadgetSets
 groupFixablesByVar(FixableGadgetList &&AllFixableOperations) {
   FixableGadgetSets FixablesForUnsafeVars;
   for (auto &F : AllFixableOperations) {
     DeclUseList DREs = F->getClaimedVarUseSites();
 
static std::optional<StringRef> getExprText(const Expr *E,
   return std::nullopt;
 }
 
 // Returns the literal text in `SourceRange SR`, if `SR` is a valid range.
 static std::optional<StringRef> getRangeText(SourceRange SR,
                                              const SourceManager &SM,
                                              const LangOptions &LangOpts) {
   bool Invalid = false;
-  CharSourceRange CSR = CharSourceRange::getCharRange(SR.getBegin(), SR.getEnd());
+  CharSourceRange CSR = CharSourceRange::getCharRange(SR);
   StringRef Text = Lexer::getSourceText(CSR, SM, LangOpts, &Invalid);
 
   if (!Invalid)
     return Text;
   return std::nullopt;
 }
 
 // Returns the begin location of the identifier of the given variable
static bool impossibleToFixForVar(const FixableGadgetSets &FixablesForAllVars,
   return false;
 }
 
 static std::map<const VarDecl *, FixItList>
 getFixIts(FixableGadgetSets &FixablesForAllVars, const Strategy &S,
     ASTContext &Ctx,
           /* The function decl under analysis */ const Decl *D,
           const DeclUseTracker &Tracker, UnsafeBufferUsageHandler &Handler,
-          const DefMapTy &VarGrpMap) {
+          const VariableGroupsManager &VarGrpMgr) {
   std::map<const VarDecl *, FixItList> FixItsForVariable;
   for (const auto &[VD, Fixables] : FixablesForAllVars.byVar) {
     FixItsForVariable[VD] =
         fixVariable(VD, S.lookup(VD), D, 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);
#endif
       }
     }
 
     if (ImpossibleToFix) {
       FixItsForVariable.erase(VD);
       continue;
     }
 
-    const auto VarGroupForVD = VarGrpMap.find(VD);
-    if (VarGroupForVD != VarGrpMap.end()) {
-      for (const VarDecl * V : VarGroupForVD->second) {
+    
+   {
+      const auto VarGroupForVD = VarGrpMgr.getGroupOfVar(VD);
+      for (const VarDecl * V : VarGroupForVD) {
         if (V == VD) {
           continue;
         }
         if (impossibleToFixForVar(FixablesForAllVars, S, V)) {
           ImpossibleToFix = true;
           break;
         }
       }
 
       if (ImpossibleToFix) {
         FixItsForVariable.erase(VD);
-        for (const VarDecl * V : VarGroupForVD->second) {
+        for (const VarDecl * V : VarGroupForVD) {
           FixItsForVariable.erase(V);
         }
         continue;
       }
     }
     FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),
                                  FixItsForVD.begin(), FixItsForVD.end());
 
     // 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;
     }
   }
 
-  for (auto VD : FixItsForVariable) {
-    const auto VarGroupForVD = VarGrpMap.find(VD.first);
-    const Strategy::Kind ReplacementTypeForVD = S.lookup(VD.first);
-    if (VarGroupForVD != VarGrpMap.end()) {
-      for (const VarDecl * Var : VarGroupForVD->second) {
-        if (Var == VD.first) {
-          continue;
-        }
+  // The map that maps each variable `v` to fix-its for the whole group where
+  // `v` is in:
+  std::map<const VarDecl *, FixItList> FinalFixItsForVariable{
+      FixItsForVariable};
 
-        FixItList GroupFix;
-        if (FixItsForVariable.find(Var) == FixItsForVariable.end()) {
-          GroupFix = fixVariable(Var, ReplacementTypeForVD, D, Tracker,
-                                 Var->getASTContext(), Handler);
-        } else {
-          GroupFix = FixItsForVariable[Var];
-        }
+  for (auto &[Var, Ignore] : FixItsForVariable) {
+    const auto VarGroupForVD = VarGrpMgr.getGroupOfVar(Var);
 
-        for (auto Fix : GroupFix) {
-          FixItsForVariable[VD.first].push_back(Fix);
-        }
-      }
+    for (const VarDecl *GrpMate : VarGroupForVD) {
+      if (Var == GrpMate)
+        continue;
+      if (FixItsForVariable.count(GrpMate))
+        FinalFixItsForVariable[Var].insert(FinalFixItsForVariable[Var].end(),
+                                           FixItsForVariable[GrpMate].begin(),
+                                           FixItsForVariable[GrpMate].end());
     }
   }
-  return FixItsForVariable;
+  return FinalFixItsForVariable;
 }
 
 
 static Strategy
 getNaiveStrategy(const llvm::SmallVectorImpl<const VarDecl *> &UnsafeVars) {
   Strategy S;
   for (const VarDecl *VD : UnsafeVars) {
     S.set(VD, Strategy::Kind::Span);
   }
   return S;
 }
 
+//  Manages variable groups:
+class VariableGroupsManagerImpl : public VariableGroupsManager {
+  const std::vector<VarGrpTy> Groups;
+  const std::map<const VarDecl *, unsigned> &VarGrpMap;
+
+public:
+  VariableGroupsManagerImpl(
+      const std::vector<VarGrpTy> &Groups,
+      const std::map<const VarDecl *, unsigned> &VarGrpMap)
+      : Groups(Groups), VarGrpMap(VarGrpMap) {}
+
+  VarGrpRef getGroupOfVar(const VarDecl *Var) const override {
+    auto I = VarGrpMap.find(Var);
+    assert(I != VarGrpMap.end());
+    return Groups[I->second];
+  }
+};
+
 void clang::checkUnsafeBufferUsage(const Decl *D,
                                    UnsafeBufferUsageHandler &Handler,
                                    bool EmitSuggestions) {
 #ifndef NDEBUG
   Handler.clearDebugNotes();
 #endif
 
   assert(D && D->getBody());
#endif
   // return is correct for now.
   if (WarningGadgets.empty())
     return;
 
   UnsafeOps = groupWarningGadgetsByVar(std::move(WarningGadgets));
   FixablesForAllVars = groupFixablesByVar(std::move(FixableGadgets));
 
   std::map<const VarDecl *, FixItList> FixItsForVariableGroup;
-  DefMapTy VariableGroupsMap{};
 
   // Filter out non-local vars and vars with unclaimed DeclRefExpr-s.
   for (auto it = FixablesForAllVars.byVar.cbegin();
        it != FixablesForAllVars.byVar.cend();) {
       // FIXME: need to deal with global variables later
       if ((!it->first->isLocalVarDecl() && !isa<ParmVarDecl>(it->first))) {
 #ifndef NDEBUG
           Handler.addDebugNoteForVar(
#endif
     }
   }
 
   llvm::SmallVector<const VarDecl *, 16> UnsafeVars;
   for (const auto &[VD, ignore] : FixablesForAllVars.byVar)
     UnsafeVars.push_back(VD);
 
   // Fixpoint iteration for pointer assignments
-  using DepMapTy = DenseMap<const VarDecl *, std::set<const VarDecl *>>;
+  using DepMapTy = DenseMap<const VarDecl *, llvm::SetVector<const VarDecl *>>;
   DepMapTy DependenciesMap{};
   DepMapTy PtrAssignmentGraph{};
 
   for (auto it : FixablesForAllVars.byVar) {
     for (const FixableGadget *fixable : it.second) {
       std::optional<std::pair<const VarDecl *, const VarDecl *>> ImplPair =
                                   fixable->getStrategyImplications();
       if (ImplPair) {
-        std::pair<const VarDecl *, const VarDecl *> Impl = ImplPair.value();
+        std::pair<const VarDecl *, const VarDecl *> Impl = std::move(*ImplPair);
         PtrAssignmentGraph[Impl.first].insert(Impl.second);
       }
     }
   }
 
   /*
    The following code does a BFS traversal of the `PtrAssignmentGraph`
    considering all unsafe vars as starting nodes and constructs an undirected
    graph `DependenciesMap`. Constructing the `DependenciesMap` in this manner
if (VisitedVarsDirected.find(Var) == VisitedVarsDirected.end()) {
           }
           DependenciesMap[Var].insert(Adj);
           DependenciesMap[Adj].insert(Var);
         }
       }
     }
   }
 
+  // `Groups` stores the set of Connected Components in the graph.
+  std::vector<VarGrpTy> Groups;
+  // `VarGrpMap` maps variables that need fix to the groups (indexes) that the
+  // variables belong to.  Group indexes refer to the elements in `Groups`.
+  // `VarGrpMap` is complete in that every variable that needs fix is in it.
+  std::map<const VarDecl *, unsigned> VarGrpMap;
+
   // Group Connected Components for Unsafe Vars
   // (Dependencies based on pointer assignments)
   std::set<const VarDecl *> VisitedVars{};
   for (const auto &[Var, ignore] : UnsafeOps.byVar) {
     if (VisitedVars.find(Var) == VisitedVars.end()) {
-      std::vector<const VarDecl *> VarGroup{};
-
+      VarGrpTy &VarGroup = Groups.emplace_back();
       std::queue<const VarDecl*> Queue{};
+
       Queue.push(Var);
       while(!Queue.empty()) {
         const VarDecl* CurrentVar = Queue.front();
         Queue.pop();
         VisitedVars.insert(CurrentVar);
         VarGroup.push_back(CurrentVar);
         auto AdjacentNodes = DependenciesMap[CurrentVar];
         for (const VarDecl *Adj : AdjacentNodes) {
           if (VisitedVars.find(Adj) == VisitedVars.end()) {
             Queue.push(Adj);
           }
         }
       }
-      for (const VarDecl * V : VarGroup) {
-        if (UnsafeOps.byVar.find(V) != UnsafeOps.byVar.end()) {
-          VariableGroupsMap[V] = VarGroup;
-        }
+      unsigned GrpIdx = Groups.size() - 1;
+
+      for (const VarDecl *V : VarGroup) {
+        VarGrpMap[V] = GrpIdx;
       }
     }
   }
 
   // Remove a `FixableGadget` if the associated variable is not in the graph
   // computed above.  We do not want to generate fix-its for such variables,
   // since they are neither warned nor reachable from a warned one.
   //
for (auto I = FixablesForAllVars.byVar.begin();
     if (VisitedVars.find((*I).first) == VisitedVars.end()) {
       // no such var in graph:
       I = FixablesForAllVars.byVar.erase(I);
     } else
       ++I;
   }
 
   Strategy NaiveStrategy = getNaiveStrategy(UnsafeVars);
+  VariableGroupsManagerImpl VarGrpMgr(Groups, VarGrpMap);
 
   FixItsForVariableGroup =
       getFixIts(FixablesForAllVars, NaiveStrategy, D->getASTContext(), D,
-                Tracker, Handler, VariableGroupsMap);
-
-  // FIXME Detect overlapping FixIts.
+                Tracker, Handler, VarGrpMgr);
 
   for (const auto &G : UnsafeOps.noVar) {
     Handler.handleUnsafeOperation(G->getBaseStmt(), /*IsRelatedToDecl=*/false);
   }
 
   for (const auto &[VD, WarningGadgets] : UnsafeOps.byVar) {
     auto FixItsIt = FixItsForVariableGroup.find(VD);
-    Handler.handleUnsafeVariableGroup(VD, VariableGroupsMap,
+    Handler.handleUnsafeVariableGroup(VD, VarGrpMgr,
                                       FixItsIt != FixItsForVariableGroup.end()
                                       ? std::move(FixItsIt->second)
                                       : FixItList{});
     for (const auto &G : WarningGadgets) {
       Handler.handleUnsafeOperation(G->getBaseStmt(), /*IsRelatedToDecl=*/true);
     }
   }
 }

clang/lib/Sema/AnalysisBasedWarnings.cpp

 // Unsafe buffer usage analysis.
 //===----------------------------------------------------------------------===//
 
 namespace {
 class UnsafeBufferUsageReporter : public UnsafeBufferUsageHandler {
   Sema &S;
   bool SuggestSuggestions;  // Recommend -fsafe-buffer-usage-suggestions?
 
+  // Lists as a string the names of variables in `VarGroupForVD` except for `VD`
+  // itself:
+  std::string listVariableGroupAsString(
+      const VarDecl *VD, const ArrayRef<const VarDecl *> &VarGroupForVD) const {
+    if (VarGroupForVD.size() <= 1)
+      return "";
+
+    std::vector<StringRef> VarNames;
+    auto PutInQuotes = [](StringRef S) -> std::string {
+      return "'" + S.str() + "'";
+    };
+
+    for (auto *V : VarGroupForVD) {
+      if (V == VD)
+        continue;
+      VarNames.push_back(V->getName());
+    }
+    if (VarNames.size() == 1) {
+      return PutInQuotes(VarNames[0]);
+    }
+    if (VarNames.size() == 2) {
+      return PutInQuotes(VarNames[0]) + " and " + PutInQuotes(VarNames[1]);
+    }
+    assert(VarGroupForVD.size() > 3);
+    const unsigned N = VarNames.size() -
+                       2; // need to print the last two names as "..., X, and Y"
+    std::string AllVars = "";
+
+    for (unsigned I = 0; I < N; ++I)
+      AllVars.append(PutInQuotes(VarNames[I]) + ", ");
+    AllVars.append(PutInQuotes(VarNames[N]) + ", and " +
+                   PutInQuotes(VarNames[N + 1]));
+    return AllVars;
+  }
+
 public:
   UnsafeBufferUsageReporter(Sema &S, bool SuggestSuggestions)
     : S(S), SuggestSuggestions(SuggestSuggestions) {}
 
   void handleUnsafeOperation(const Stmt *Operation,
                              bool IsRelatedToDecl) override {
     SourceLocation Loc;
     SourceRange Range;
if (IsRelatedToDecl) {
       S.Diag(Loc, diag::warn_unsafe_buffer_operation) << MsgParam << Range;
       if (SuggestSuggestions) {
         S.Diag(Loc, diag::note_safe_buffer_usage_suggestions_disabled);
       }
     }
   }
 
   void handleUnsafeVariableGroup(const VarDecl *Variable,
-                                 const DefMapTy &VarGrpMap,
+                                 const VariableGroupsManager &VarGrpMgr,
                                  FixItList &&Fixes) override {
     assert(!SuggestSuggestions &&
            "Unsafe buffer usage fixits displayed without suggestions!");
     S.Diag(Variable->getLocation(), diag::warn_unsafe_buffer_variable)
         << Variable << (Variable->getType()->isPointerType() ? 0 : 1)
         << Variable->getSourceRange();
     if (!Fixes.empty()) {
-      const auto VarGroupForVD = VarGrpMap.find(Variable)->second;
+      const auto VarGroupForVD = VarGrpMgr.getGroupOfVar(Variable);
       unsigned FixItStrategy = 0; // For now we only have 'std::span' strategy
       const auto &FD = S.Diag(Variable->getLocation(),
                               diag::note_unsafe_buffer_variable_fixit_group);
 
       FD << Variable << FixItStrategy;
-      std::string AllVars = "";
-      if (VarGroupForVD.size() > 1) {
-        if (VarGroupForVD.size() == 2) {
-          if (VarGroupForVD[0] == Variable) {
-            AllVars.append("'" + VarGroupForVD[1]->getName().str() + "'");
-          } else {
-            AllVars.append("'" + VarGroupForVD[0]->getName().str() + "'");
-          }
-        } else {
-          bool first = false;
-          if (VarGroupForVD.size() == 3) {
-            for (const VarDecl * V : VarGroupForVD) {
-              if (V == Variable) {
-                continue;
-              }
-              if (!first) {
-                first = true;
-                AllVars.append("'" + V->getName().str() + "'" + " and ");
-              } else {
-                AllVars.append("'" + V->getName().str() + "'");
-              }
-            }
-          } else {
-            for (const VarDecl * V : VarGroupForVD) {
-              if (V == Variable) {
-                continue;
-              }
-              if (VarGroupForVD.back() != V) {
-                AllVars.append("'" + V->getName().str() + "'" + ", ");
-              } else {
-                AllVars.append("and '" + V->getName().str() + "'");
-              }
-            }
-          }
-        }
-        FD << AllVars << 1;
-      } else {
-        FD << "" << 0;
-      }
-
-      for (const auto &F : Fixes)
+      FD << listVariableGroupAsString(Variable, VarGroupForVD)
+         << (VarGroupForVD.size() > 1);
+      for (const auto &F : Fixes) {
         FD << F;
       }
+    }
 
 #ifndef NDEBUG
     if (areDebugNotesRequested())
       for (const DebugNote &Note: DebugNotesByVar[Variable])
         S.Diag(Note.first, diag::note_safe_buffer_debug_mode) << Note.second;
 #endif
   }