[include-fixer] Correct nested class search for identifiers with scoped information

[hokein]

Summary

include-fixer will firstly try to use scoped namespace context information to
search identifier. However, in some cases, it's unsafe to do nested class
search, because it might treat the identifier as a nested class of scoped
namespace.

Given the following code, and the symbol database only has two classes: "foo" and
"b::Bar".

namespace foo { Bar t; }

Before getting fixing, include-fixer will never search "Bar" symbol.
Because it firstly tries to search "foo::Bar", there is no "Bar" in foo namespace,
then it finds "foo" in database finally. So it treats "Bar" is a nested class
of "foo".

[bkramer]

include-fixer/SymbolIndexManager.h

32 ↗

(On Diff #66347)

"tries to strip"

35 ↗

(On Diff #66347)

"fails to find"

[hokein]

Address review comments.

clang-tools-extra/trunk/include-fixer/IncludeFixer.cpp

bool query(StringRef Query, StringRef ScopedQualifiers,
     //
     // namespace a {
     // b::foo f;
     // }
     //
     // 1. lookup a::b::foo.
     // 2. lookup b::foo.
     std::string QueryString = ScopedQualifiers.str() + Query.str();
-    MatchedSymbols = SymbolIndexMgr.search(QueryString);
-    if (MatchedSymbols.empty() && !ScopedQualifiers.empty())
+    // It's unsafe to do nested search for the identifier with scoped namespace
+    // context, it might treat the identifier as a nested class of the scoped
+    // namespace.
+    MatchedSymbols = SymbolIndexMgr.search(QueryString, /*IsNestedSearch=*/false);
+    if (MatchedSymbols.empty())
       MatchedSymbols = SymbolIndexMgr.search(Query);
     DEBUG(llvm::dbgs() << "Having found " << MatchedSymbols.size()
                        << " symbols\n");
     return !MatchedSymbols.empty();
   }
 
   /// The client to use to find cross-references.
   SymbolIndexManager &SymbolIndexMgr;

clang-tools-extra/trunk/include-fixer/IncludeFixerContext.cpp

std::string createQualifiedNameForReplacement(
   // we strip qualifiers from the end until we find a result. So append the
   // missing stripped qualifiers here.
   //
   // Get stripped qualifiers.
   auto SymbolQualifiers = SplitQualifiers(RawSymbolName);
   std::string StrippedQualifiers;
   while (!SymbolQualifiers.empty() &&
          !llvm::StringRef(QualifiedName).endswith(SymbolQualifiers.back())) {
-    StrippedQualifiers = "::" + SymbolQualifiers.back().str();
+    StrippedQualifiers =
+        "::" + SymbolQualifiers.back().str() + StrippedQualifiers;
     SymbolQualifiers.pop_back();
   }
   // Append the missing stripped qualifiers.
   std::string FullyQualifiedName = QualifiedName + StrippedQualifiers;
 
   // Try to find and skip the common prefix qualifiers.
   auto FullySymbolQualifiers = SplitQualifiers(FullyQualifiedName);
   auto ScopedQualifiers = SplitQualifiers(SymbolScopedQualifiersName);

clang-tools-extra/trunk/include-fixer/SymbolIndexManager.h

 public:
   void addSymbolIndex(std::unique_ptr<SymbolIndex> DB) {
     SymbolIndices.push_back(std::move(DB));
   }
 
   /// Search for header files to be included for an identifier.
   /// \param Identifier The identifier being searched for. May or may not be
   ///                   fully qualified.
-  /// \returns A list of inclusion candidates, in a format ready for being
-  ///          pasted after an #include token.
-  // FIXME: Move mapping from SymbolInfo to headers out of
-  // SymbolIndexManager::search and return SymbolInfos instead of header paths.
+  /// \param IsNestedSearch Whether searching nested classes. If true, the
+  ///        method tries to strip identifier name parts from the end until it
+  ///        finds the corresponding candidates in database (e.g for identifier
+  ///        "b::foo", the method will try to find "b" if it fails to find
+  ///        "b::foo").
+  ///
+  /// \returns A list of symbol candidates.
   std::vector<find_all_symbols::SymbolInfo>
-  search(llvm::StringRef Identifier) const;
+  search(llvm::StringRef Identifier, bool IsNestedSearch = true) const;
 
 private:
   std::vector<std::unique_ptr<SymbolIndex>> SymbolIndices;
 };
 
 } // namespace include_fixer
 } // namespace clang
 
 #endif

clang-tools-extra/trunk/include-fixer/SymbolIndexManager.cpp

std::sort(Symbols.begin(), Symbols.end(),
               auto BPop = HeaderPopularity[B.getFilePath()];
               if (APop != BPop)
                 return APop > BPop;
               return A.getFilePath() < B.getFilePath();
             });
 }
 
 std::vector<find_all_symbols::SymbolInfo>
-SymbolIndexManager::search(llvm::StringRef Identifier) const {
+SymbolIndexManager::search(llvm::StringRef Identifier,
+                           bool IsNestedSearch) const {
   // The identifier may be fully qualified, so split it and get all the context
   // names.
   llvm::SmallVector<llvm::StringRef, 8> Names;
   Identifier.split(Names, "::");
 
   bool IsFullyQualified = false;
   if (Identifier.startswith("::")) {
     Names.erase(Names.begin()); // Drop first (empty) element.
     IsFullyQualified = true;
   }
 
   // As long as we don't find a result keep stripping name parts from the end.
   // This is to support nested classes which aren't recorded in the database.
   // Eventually we will either hit a class (namespaces aren't in the database
   // either) and can report that result.
   bool TookPrefix = false;
   std::vector<clang::find_all_symbols::SymbolInfo> MatchedSymbols;
-  while (MatchedSymbols.empty() && !Names.empty()) {
+  do {
     std::vector<clang::find_all_symbols::SymbolInfo> Symbols;
     for (const auto &DB : SymbolIndices) {
       auto Res = DB->search(Names.back().str());
       Symbols.insert(Symbols.end(), Res.begin(), Res.end());
     }
 
     DEBUG(llvm::dbgs() << "Searching " << Names.back() << "... got "
                        << Symbols.size() << " results...\n");
for (const auto &Symbol : Symbols) {
             continue;
 
           MatchedSymbols.push_back(Symbol);
         }
       }
     }
     Names.pop_back();
     TookPrefix = true;
-  }
+  } while (MatchedSymbols.empty() && !Names.empty() && IsNestedSearch);
 
   rankByPopularity(MatchedSymbols);
   return MatchedSymbols;
 }
 
 } // namespace include_fixer
 } // namespace clang

clang-tools-extra/trunk/unittests/include-fixer/IncludeFixerTest.cpp

std::vector<SymbolInfo> Symbols = {
                   {SymbolInfo::ContextType::Namespace, "a"}}),
       SymbolInfo("Vector", SymbolInfo::SymbolKind::Class, "\"Vector.h\"", 1,
                  {{SymbolInfo::ContextType::Namespace, "__a"},
                   {SymbolInfo::ContextType::Namespace, "a"}},
                  /*num_occurrences=*/2),
       SymbolInfo("Vector", SymbolInfo::SymbolKind::Class, "\"Vector.h\"", 2,
                  {{SymbolInfo::ContextType::Namespace, "a"}},
                  /*num_occurrences=*/1),
+      SymbolInfo("StrCat", SymbolInfo::SymbolKind::Class, "\"strcat.h\"",
+                 1, {{SymbolInfo::ContextType::Namespace, "str"}}),
+      SymbolInfo("str", SymbolInfo::SymbolKind::Class, "\"str.h\"",
+                 1, {}),
+      SymbolInfo("foo2", SymbolInfo::SymbolKind::Class, "\"foo2.h\"",
+                 1, {}),
   };
   auto SymbolIndexMgr = llvm::make_unique<include_fixer::SymbolIndexManager>();
   SymbolIndexMgr->addSymbolIndex(
       llvm::make_unique<include_fixer::InMemorySymbolIndex>(Symbols));
 
   IncludeFixerContext FixerContext;
   IncludeFixerActionFactory Factory(*SymbolIndexMgr, FixerContext, "llvm");
 
TEST(IncludeFixer, ScopedNamespaceSymbols) {
   EXPECT_EQ("#include \"bar.h\"\nnamespace a {\nvoid func() { b::bar b; }\n}",
             runIncludeFixer("namespace a {\nvoid func() { b::bar b; }\n}"));
   EXPECT_EQ("namespace A { c::b::bar b; }\n",
             runIncludeFixer("namespace A { c::b::bar b; }\n"));
   // FIXME: The header should not be added here. Remove this after we support
   // full match.
   EXPECT_EQ("#include \"bar.h\"\nnamespace A {\na::b::bar b;\n}",
             runIncludeFixer("namespace A {\nb::bar b;\n}"));
+
+  // Finds candidates for "str::StrCat".
+  EXPECT_EQ("#include \"strcat.h\"\nnamespace foo2 {\nstr::StrCat b;\n}",
+            runIncludeFixer("namespace foo2 {\nstr::StrCat b;\n}"));
+  // str::StrCat2 doesn't exist.
+  // In these two cases, StrCat2 is a nested class of class str.
+  EXPECT_EQ("#include \"str.h\"\nnamespace foo2 {\nstr::StrCat2 b;\n}",
+            runIncludeFixer("namespace foo2 {\nstr::StrCat2 b;\n}"));
+  EXPECT_EQ("#include \"str.h\"\nnamespace ns {\nstr::StrCat2 b;\n}",
+            runIncludeFixer("namespace ns {\nstr::StrCat2 b;\n}"));
 }
 
 TEST(IncludeFixer, EnumConstantSymbols) {
   EXPECT_EQ("#include \"color.h\"\nint test = a::b::Green;\n",
             runIncludeFixer("int test = a::b::Green;\n"));
 }
 
 TEST(IncludeFixer, IgnoreSymbolFromHeader) {
EXPECT_EQ(
       runIncludeFixer("namespace a {\nnamespace d {\nbar b;\n}\n}\n"));
   EXPECT_EQ(
       "#include \"bar.h\"\nnamespace d {\nnamespace a {\na::b::bar b;\n}\n}\n",
       runIncludeFixer("namespace d {\nnamespace a {\nbar b;\n}\n}\n"));
 
   // Test nested classes.
   EXPECT_EQ("#include \"bar.h\"\nnamespace d {\na::b::bar::t b;\n}\n",
             runIncludeFixer("namespace d {\nbar::t b;\n}\n"));
-  EXPECT_EQ("#include \"bar2.h\"\nnamespace c {\na::c::bar::t b;\n}\n",
+  EXPECT_EQ("#include \"bar.h\"\nnamespace c {\na::b::bar::t b;\n}\n",
             runIncludeFixer("namespace c {\nbar::t b;\n}\n"));
   EXPECT_EQ("#include \"bar.h\"\nnamespace a {\nb::bar::t b;\n}\n",
             runIncludeFixer("namespace a {\nbar::t b;\n}\n"));
 
   EXPECT_EQ("#include \"color.h\"\nint test = a::b::Green;\n",
             runIncludeFixer("int test = Green;\n"));
   EXPECT_EQ("#include \"color.h\"\nnamespace d {\nint test = a::b::Green;\n}\n",
             runIncludeFixer("namespace d {\nint test = Green;\n}\n"));