Index: clang-tools-extra/trunk/include-fixer/IncludeFixer.cpp
===================================================================
--- clang-tools-extra/trunk/include-fixer/IncludeFixer.cpp
+++ clang-tools-extra/trunk/include-fixer/IncludeFixer.cpp
@@ -275,8 +275,11 @@
     // 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");
Index: clang-tools-extra/trunk/include-fixer/IncludeFixerContext.cpp
===================================================================
--- clang-tools-extra/trunk/include-fixer/IncludeFixerContext.cpp
+++ clang-tools-extra/trunk/include-fixer/IncludeFixerContext.cpp
@@ -44,7 +44,8 @@
   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.
Index: clang-tools-extra/trunk/include-fixer/SymbolIndexManager.h
===================================================================
--- clang-tools-extra/trunk/include-fixer/SymbolIndexManager.h
+++ clang-tools-extra/trunk/include-fixer/SymbolIndexManager.h
@@ -28,12 +28,15 @@
   /// 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;
Index: clang-tools-extra/trunk/include-fixer/SymbolIndexManager.cpp
===================================================================
--- clang-tools-extra/trunk/include-fixer/SymbolIndexManager.cpp
+++ clang-tools-extra/trunk/include-fixer/SymbolIndexManager.cpp
@@ -42,7 +42,8 @@
 }
 
 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;
@@ -60,7 +61,7 @@
   // 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());
@@ -116,7 +117,7 @@
     }
     Names.pop_back();
     TookPrefix = true;
-  }
+  } while (MatchedSymbols.empty() && !Names.empty() && IsNestedSearch);
 
   rankByPopularity(MatchedSymbols);
   return MatchedSymbols;
Index: clang-tools-extra/trunk/unittests/include-fixer/IncludeFixerTest.cpp
===================================================================
--- clang-tools-extra/trunk/unittests/include-fixer/IncludeFixerTest.cpp
+++ clang-tools-extra/trunk/unittests/include-fixer/IncludeFixerTest.cpp
@@ -77,6 +77,12 @@
       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(
@@ -189,6 +195,16 @@
   // 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) {
@@ -253,7 +269,7 @@
   // 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"));