Index: lib/Tooling/Core/Lookup.cpp
===================================================================
--- lib/Tooling/Core/Lookup.cpp
+++ lib/Tooling/Core/Lookup.cpp
@@ -16,47 +16,66 @@
 using namespace clang;
 using namespace clang::tooling;
 
+// Gets all namespaces that \p Context is in as a vector (ignoring anonymous
+// namespaces). The inner namespaces come before outer namespaces in the vector.
+// For example, if the context is in the following namespace:
+//    `namespace a { namespace b { namespace c ( ... ) } }`,
+// the vector will be `{c, b, a}`.
+static llvm::SmallVector<const NamespaceDecl *, 4>
+getAllNamedNamespaces(const DeclContext *Context) {
+  llvm::SmallVector<const NamespaceDecl *, 4> Namespaces;
+  auto GetNextNameNamespace = [](const DeclContext *Context) {
+    // Look past non-namespaces and anonymous namespaces on FromContext.
+    while (Context &&
+           (!isa<NamespaceDecl>(Context) ||
+            cast<NamespaceDecl>(Context)->isAnonymousNamespace()))
+      Context = Context->getParent();
+    return Context;
+  };
+  for (Context = GetNextNameNamespace(Context); Context != nullptr;
+       Context = GetNextNameNamespace(Context->getParent()))
+    Namespaces.push_back(cast<NamespaceDecl>(Context));
+  return Namespaces;
+}
+
 // Returns true if the context in which the type is used and the context in
 // which the type is declared are the same semantical namespace but different
 // lexical namespaces.
 static bool
 usingFromDifferentCanonicalNamespace(const DeclContext *FromContext,
                                      const DeclContext *UseContext) {
-  while (true) {
-    // Look past non-namespaces and anonymous namespaces on FromContext.
-    // We can skip anonymous namespace because:
-    // 1. `FromContext` and `UseContext` must be in the same anonymous
-    // namespaces since referencing across anonymous namespaces is not possible.
-    // 2. If `FromContext` and `UseContext` are in the same anonymous namespace,
-    // the function will still return `false` as expected.
-    while (FromContext &&
-           (!isa<NamespaceDecl>(FromContext) ||
-            cast<NamespaceDecl>(FromContext)->isAnonymousNamespace()))
-      FromContext = FromContext->getParent();
-
-    // Look past non-namespaces and anonymous namespaces on UseContext.
-    while (UseContext &&
-           (!isa<NamespaceDecl>(UseContext) ||
-            cast<NamespaceDecl>(UseContext)->isAnonymousNamespace()))
-      UseContext = UseContext->getParent();
-
-    // We hit the root, no namespace collision.
-    if (!FromContext || !UseContext)
-      return false;
-
+  // We can skip anonymous namespace because:
+  // 1. `FromContext` and `UseContext` must be in the same anonymous namespaces
+  // since referencing across anonymous namespaces is not possible.
+  // 2. If `FromContext` and `UseContext` are in the same anonymous namespace,
+  // the function will still return `false` as expected.
+  llvm::SmallVector<const NamespaceDecl *, 4> FromNamespaces =
+      getAllNamedNamespaces(FromContext);
+  llvm::SmallVector<const NamespaceDecl *, 4> UseNamespaces =
+      getAllNamedNamespaces(UseContext);
+  // If `UseContext` has fewer level of nested namespaces, it cannot be in the
+  // same canonical namespace as the `FromContext`.
+  if (UseNamespaces.size() < FromNamespaces.size())
+    return false;
+  unsigned Diff = UseNamespaces.size() - FromNamespaces.size();
+  auto FromIter = FromNamespaces.begin();
+  // Only compare `FromNamespaces` with namespaces in `UseNamespaces` that can
+  // collide, i.e. the top N namespaces where N is the number of namespaces in
+  // `FromNamespaces`.
+  auto UseIter = UseNamespaces.begin() + Diff;
+  for (; FromIter != FromNamespaces.end() && UseIter != UseNamespaces.end();
+       ++FromIter, ++UseIter) {
     // Literally the same namespace, not a collision.
-    if (FromContext == UseContext)
+    if (*FromIter == *UseIter)
       return false;
-
-    // Now check the names. If they match we have a different namespace with the
-    // same name.
-    if (cast<NamespaceDecl>(FromContext)->getDeclName() ==
-        cast<NamespaceDecl>(UseContext)->getDeclName())
+    // Now check the names. If they match we have a different canonical
+    // namespace with the same name.
+    if (cast<NamespaceDecl>(*FromIter)->getDeclName() ==
+        cast<NamespaceDecl>(*UseIter)->getDeclName())
       return true;
-
-    FromContext = FromContext->getParent();
-    UseContext = UseContext->getParent();
   }
+  assert(FromIter == FromNamespaces.end() && UseIter == UseNamespaces.end());
+  return false;
 }
 
 static StringRef getBestNamespaceSubstr(const DeclContext *DeclA,
Index: unittests/Tooling/LookupTest.cpp
===================================================================
--- unittests/Tooling/LookupTest.cpp
+++ unittests/Tooling/LookupTest.cpp
@@ -111,6 +111,14 @@
                   "namespace a { namespace b { namespace {"
                   "void f() { foo(); }"
                   "} } }\n");
+
+  Visitor.OnCall = [&](CallExpr *Expr) {
+    EXPECT_EQ("x::bar", replaceCallExpr(Expr, "::a::x::bar"));
+  };
+  Visitor.runOver("namespace a { namespace b { void foo(); } }\n"
+                  "namespace a { namespace b { namespace c {"
+                  "void f() { foo(); }"
+                  "} } }\n");
 }
 
 } // end anonymous namespace