[clang-rename] speedup RenamingAction

The complexity of renaming a USR is O(N) [N stands for number of nodes in
Translation Unit]. In some cases there are more than one USR for a single symbol
(see overridden functions and ctor/dtor handling), which means that the
complexity of finding all of the corresponding USRs is O(N * M) [M stands for
number of USRs corresponding to the symbols, which may be not quite small]. With
a simple tweak we can make it O(N * log(M)) by passing whole list of USRs
corresponding to the symbol to USRLocFinder.

llvm-svn: 277131

3 files changed, 28 insertions, 32 deletions

diff --git a/clang-tools-extra/clang-rename/RenamingAction.cpp b/clang-tools-extra/clang-rename/RenamingAction.cpp
index 3e3d536620d..910f4fdaafd 100644
--- a/clang-tools-extra/clang-rename/RenamingAction.cpp
+++ b/clang-tools-extra/clang-rename/RenamingAction.cpp
@@ -34,27 +34,21 @@ namespace rename {
 
 class RenamingASTConsumer : public ASTConsumer {
 public:
-  RenamingASTConsumer(const std::string &NewName,
-                      const std::string &PrevName,
+  RenamingASTConsumer(const std::string &NewName, const std::string &PrevName,
                       const std::vector<std::string> &USRs,
-                      tooling::Replacements &Replaces,
-                      bool PrintLocations)
+                      tooling::Replacements &Replaces, bool PrintLocations)
       : NewName(NewName), PrevName(PrevName), USRs(USRs), Replaces(Replaces),
-        PrintLocations(PrintLocations) {
-  }
+        PrintLocations(PrintLocations) {}
 
   void HandleTranslationUnit(ASTContext &Context) override {
     const auto &SourceMgr = Context.getSourceManager();
     std::vector<SourceLocation> RenamingCandidates;
     std::vector<SourceLocation> NewCandidates;
 
-    for (const auto &USR : USRs) {
-      NewCandidates = getLocationsOfUSR(USR, PrevName,
-                                        Context.getTranslationUnitDecl());
-      RenamingCandidates.insert(RenamingCandidates.end(), NewCandidates.begin(),
-                                NewCandidates.end());
-      NewCandidates.clear();
-    }
+    NewCandidates =
+        getLocationsOfUSRs(USRs, PrevName, Context.getTranslationUnitDecl());
+    RenamingCandidates.insert(RenamingCandidates.end(), NewCandidates.begin(),
+                              NewCandidates.end());
 
     auto PrevNameLen = PrevName.length();
     for (const auto &Loc : RenamingCandidates) {
@@ -64,8 +58,8 @@ public:
                << ":" << FullLoc.getSpellingLineNumber() << ":"
                << FullLoc.getSpellingColumnNumber() << "\n";
       }
-      Replaces.insert(tooling::Replacement(SourceMgr, Loc, PrevNameLen,
-                                           NewName));
+      Replaces.insert(
+          tooling::Replacement(SourceMgr, Loc, PrevNameLen, NewName));
     }
   }
 
diff --git a/clang-tools-extra/clang-rename/USRLocFinder.cpp b/clang-tools-extra/clang-rename/USRLocFinder.cpp
index 5ab155874ab..394569a4a7d 100644
--- a/clang-tools-extra/clang-rename/USRLocFinder.cpp
+++ b/clang-tools-extra/clang-rename/USRLocFinder.cpp
@@ -34,9 +34,11 @@ namespace {
 class USRLocFindingASTVisitor
     : public clang::RecursiveASTVisitor<USRLocFindingASTVisitor> {
 public:
-  explicit USRLocFindingASTVisitor(StringRef USR, StringRef PrevName,
+  explicit USRLocFindingASTVisitor(const std::vector<std::string> &USRs,
+                                   StringRef PrevName,
                                    const ASTContext &Context)
-      : USR(USR), PrevName(PrevName), Context(Context) {}
+      : USRSet(USRs.begin(), USRs.end()), PrevName(PrevName), Context(Context) {
+  }
 
   // Declaration visitors:
 
@@ -47,7 +49,7 @@ public:
         continue;
       }
       if (const clang::FieldDecl *FieldDecl = Initializer->getAnyMember()) {
-        if (getUSRForDecl(FieldDecl) == USR) {
+        if (USRSet.find(getUSRForDecl(FieldDecl)) != USRSet.end()) {
           // The initializer refers to a field that is to be renamed.
           SourceLocation Location = Initializer->getSourceLocation();
           StringRef TokenName = Lexer::getSourceText(
@@ -65,7 +67,7 @@ public:
   }
 
   bool VisitNamedDecl(const NamedDecl *Decl) {
-    if (getUSRForDecl(Decl) == USR) {
+    if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
       checkAndAddLocation(Decl->getLocation());
     }
     return true;
@@ -76,7 +78,7 @@ public:
   bool VisitDeclRefExpr(const DeclRefExpr *Expr) {
     const auto *Decl = Expr->getFoundDecl();
 
-    if (getUSRForDecl(Decl) == USR) {
+    if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
       const SourceManager &Manager = Decl->getASTContext().getSourceManager();
       SourceLocation Location = Manager.getSpellingLoc(Expr->getLocation());
       checkAndAddLocation(Location);
@@ -87,7 +89,7 @@ public:
 
   bool VisitMemberExpr(const MemberExpr *Expr) {
     const auto *Decl = Expr->getFoundDecl().getDecl();
-    if (getUSRForDecl(Decl) == USR) {
+    if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
       const SourceManager &Manager = Decl->getASTContext().getSourceManager();
       SourceLocation Location = Manager.getSpellingLoc(Expr->getMemberLoc());
       checkAndAddLocation(Location);
@@ -98,7 +100,8 @@ public:
   // Other visitors:
 
   bool VisitTypeLoc(const TypeLoc Loc) {
-    if (getUSRForDecl(Loc.getType()->getAsCXXRecordDecl()) == USR) {
+    if (USRSet.find(getUSRForDecl(Loc.getType()->getAsCXXRecordDecl())) !=
+        USRSet.end()) {
       checkAndAddLocation(Loc.getBeginLoc());
     }
     return true;
@@ -116,7 +119,7 @@ public:
   void handleNestedNameSpecifierLoc(NestedNameSpecifierLoc NameLoc) {
     while (NameLoc) {
       const auto *Decl = NameLoc.getNestedNameSpecifier()->getAsNamespace();
-      if (Decl && getUSRForDecl(Decl) == USR) {
+      if (Decl && USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
         checkAndAddLocation(NameLoc.getLocalBeginLoc());
       }
       NameLoc = NameLoc.getPrefix();
@@ -127,8 +130,7 @@ private:
   void checkAndAddLocation(SourceLocation Loc) {
     const auto BeginLoc = Loc;
     const auto EndLoc = Lexer::getLocForEndOfToken(
-                                   BeginLoc, 0, Context.getSourceManager(),
-                                   Context.getLangOpts());
+        BeginLoc, 0, Context.getSourceManager(), Context.getLangOpts());
     StringRef TokenName =
         Lexer::getSourceText(CharSourceRange::getTokenRange(BeginLoc, EndLoc),
                              Context.getSourceManager(), Context.getLangOpts());
@@ -140,18 +142,17 @@ private:
     }
   }
 
-  // All the locations of the USR were found.
-  const std::string USR;
-  // Old name that is renamed.
+  const std::set<std::string> USRSet;
   const std::string PrevName;
   std::vector<clang::SourceLocation> LocationsFound;
   const ASTContext &Context;
 };
 } // namespace
 
-std::vector<SourceLocation> getLocationsOfUSR(StringRef USR, StringRef PrevName,
-                                              Decl *Decl) {
-  USRLocFindingASTVisitor Visitor(USR, PrevName, Decl->getASTContext());
+std::vector<SourceLocation>
+getLocationsOfUSRs(const std::vector<std::string> &USRs, StringRef PrevName,
+                   Decl *Decl) {
+  USRLocFindingASTVisitor Visitor(USRs, PrevName, Decl->getASTContext());
   Visitor.TraverseDecl(Decl);
   NestedNameSpecifierLocFinder Finder(Decl->getASTContext());
   for (const auto &Location : Finder.getNestedNameSpecifierLocations()) {
diff --git a/clang-tools-extra/clang-rename/USRLocFinder.h b/clang-tools-extra/clang-rename/USRLocFinder.h
index e70af59a06f..1b5473bd273 100644
--- a/clang-tools-extra/clang-rename/USRLocFinder.h
+++ b/clang-tools-extra/clang-rename/USRLocFinder.h
@@ -26,7 +26,8 @@ namespace rename {
 
 // FIXME: make this an AST matcher. Wouldn't that be awesome??? I agree!
 std::vector<SourceLocation>
-getLocationsOfUSR(llvm::StringRef USR, llvm::StringRef PrevName, Decl *Decl);
+getLocationsOfUSRs(const std::vector<std::string> &USRs,
+                   llvm::StringRef PrevName, Decl *Decl);
 
 } // namespace rename
 } // namespace clang