[Tooling] Add more scope specifiers until spelling is not ambiguous.

[ioeric]

Summary

Previously, when the renamed spelling is ambiguous, we simply use the
full-qualfied name (with leading "::"). This patch makes it try adding
additional specifiers one at a time until name is no longer ambiguous,
which allows us to find better disambuguated spelling.

[kadircet]

LGTM

lib/Tooling/Core/Lookup.cpp

165

maybe return or break afterwards?

[ioeric]

lib/Tooling/Core/Lookup.cpp

165

I also struggled a bit here. But I decided to let IsAmbiguousSpelling handle it because it seemed a bit more natural. Otherwise, we would somewhat duplicate the logic that spelling with leading "::" is not ambiguous.

[kadircet]

lib/Tooling/Core/Lookup.cpp

165

ok sgtm

lib/Tooling/Core/Lookup.cpp

 //===--- Lookup.cpp - Framework for clang refactoring tools ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines helper methods for clang tools performing name lookup.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/Core/Lookup.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclarationName.h"
+#include "llvm/ADT/SmallVector.h"
 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 bool isFullyQualified(const NestedNameSpecifier *NNS) {
   while (NNS) {
     if (NNS->getKind() == NestedNameSpecifier::Global)
       return true;
     NNS = NNS->getPrefix();
   }
   return false;
 }
 
-// Returns true if spelling symbol \p QName as \p Spelling in \p UseContext is
-// ambiguous. For example, if QName is "::y::bar" and the spelling is "y::bar"
-// in `UseContext` "a" that contains a nested namespace "a::y", then "y::bar"
-// can be resolved to ::a::y::bar, which can cause compile error.
+// Adds more scope specifier to the spelled name until the spelling is not
+// ambiguous. A spelling is ambiguous if the resolution of the symbol is
+// ambiguous. For example, if QName is "::y::bar", the spelling is "y::bar", and
+// context contains a nested namespace "a::y", then "y::bar" can be resolved to
+// ::a::y::bar in the context, which can cause compile error.
 // FIXME: consider using namespaces.
-static bool isAmbiguousNameInScope(StringRef Spelling, StringRef QName,
+static std::string disambiguateSpellingInScope(StringRef Spelling,
+                                               StringRef QName,
                                                const DeclContext &UseContext) {
   assert(QName.startswith("::"));
+  assert(QName.endswith(Spelling));
   if (Spelling.startswith("::"))
-    return false;
+    return Spelling;
 
-  // Lookup the first component of Spelling in all enclosing namespaces and
-  // check if there is any existing symbols with the same name but in different
-  // scope.
-  StringRef Head = Spelling.split("::").first;
+  auto UnspelledSpecifier = QName.drop_back(Spelling.size());
+  llvm::SmallVector<llvm::StringRef, 2> UnspelledScopes;
+  UnspelledSpecifier.split(UnspelledScopes, "::", /*MaxSplit=*/-1,
+                           /*KeepEmpty=*/false);
 
-  llvm::SmallVector<const NamespaceDecl *, 4> UseNamespaces =
+  llvm::SmallVector<const NamespaceDecl *, 4> EnclosingNamespaces =
       getAllNamedNamespaces(&UseContext);
   auto &AST = UseContext.getParentASTContext();
   StringRef TrimmedQName = QName.substr(2);
-  for (const auto *NS : UseNamespaces) {
+
+  auto IsAmbiguousSpelling = [&EnclosingNamespaces, &AST, &TrimmedQName](
+                                 const llvm::StringRef CurSpelling) {
+    if (CurSpelling.startswith("::"))
+      return false;
+    // Lookup the first component of Spelling in all enclosing namespaces
+    // and check if there is any existing symbols with the same name but in
+    // different scope.
+    StringRef Head = CurSpelling.split("::").first;
+    for (const auto *NS : EnclosingNamespaces) {
       auto LookupRes = NS->lookup(DeclarationName(&AST.Idents.get(Head)));
       if (!LookupRes.empty()) {
         for (const NamedDecl *Res : LookupRes)
           if (!TrimmedQName.startswith(Res->getQualifiedNameAsString()))
             return true;
       }
     }
     return false;
+  };
+
+  // Add more qualifiers until the spelling is not ambiguous.
+  std::string Disambiguated = Spelling;
+  while (IsAmbiguousSpelling(Disambiguated)) {
+    if (UnspelledScopes.empty()) {
+      Disambiguated = "::" + Disambiguated;
+    } else {
+      Disambiguated = (UnspelledScopes.back() + "::" + Disambiguated).str();
+      UnspelledScopes.pop_back();
+    }
+  }
+  return Disambiguated;
 }
 
 std::string tooling::replaceNestedName(const NestedNameSpecifier *Use,
                                        const DeclContext *UseContext,
                                        const NamedDecl *FromDecl,
                                        StringRef ReplacementString) {
   assert(ReplacementString.startswith("::") &&
          "Expected fully-qualified name!");
return Pos != StringRef::npos ? ReplacementString.substr(Pos + 2)
                                   : ReplacementString;
   }
   // We did not match this because of a using statement, so we will need to
   // figure out how good a namespace match we have with our destination type.
   // We work backwards (from most specific possible namespace to least
   // specific).
   StringRef Suggested = getBestNamespaceSubstr(UseContext, ReplacementString,
                                                isFullyQualified(Use));
-  // Use the fully qualified name if the suggested name is ambiguous.
-  // FIXME: consider re-shortening the name until the name is not ambiguous. We
-  // are not doing this because ambiguity is pretty bad and we should not try to
-  // be clever in handling such cases. Making this noticeable to users seems to
-  // be a better option.
-  return isAmbiguousNameInScope(Suggested, ReplacementString, *UseContext)
-             ? ReplacementString
-             : Suggested;
+
+  return disambiguateSpellingInScope(Suggested, ReplacementString, *UseContext);
 }

unittests/Tooling/LookupTest.cpp

TEST(LookupTest, replaceNestedFunctionName) {
   };
   Visitor.runOver("namespace a { namespace b { void foo(); } }\n"
                   "namespace a { namespace b { namespace c {"
                   "void f() { foo(); }"
                   "} } }\n");
 
   // If the shortest name is ambiguous, we need to add more qualifiers.
   Visitor.OnCall = [&](CallExpr *Expr) {
-    EXPECT_EQ("::a::y::bar", replaceCallExpr(Expr, "::a::y::bar"));
+    EXPECT_EQ("a::y::bar", replaceCallExpr(Expr, "::a::y::bar"));
   };
   Visitor.runOver(R"(
     namespace a {
      namespace b {
       namespace x { void foo() {} }
       namespace y { void foo() {} }
      }
     }
 
     namespace a {
      namespace b {
       void f() { x::foo(); }
      }
     })");
 
   Visitor.OnCall = [&](CallExpr *Expr) {
+    // y::bar would be ambiguous due to "a::b::y".
+    EXPECT_EQ("::y::bar", replaceCallExpr(Expr, "::y::bar"));
+  };
+  Visitor.runOver(R"(
+    namespace a {
+     namespace b {
+      void foo() {}
+      namespace y { }
+     }
+    }
+
+    namespace a {
+     namespace b {
+      void f() { foo(); }
+     }
+    })");
+
+  Visitor.OnCall = [&](CallExpr *Expr) {
     EXPECT_EQ("y::bar", replaceCallExpr(Expr, "::y::bar"));
   };
   Visitor.runOver(R"(
     namespace a {
     namespace b {
     namespace x { void foo() {} }
     namespace y { void foo() {} }
     }