[clangd] Helper for getting nested namespace qualification

[kadircet]

Summary

Introduce a new helper for getting minimally required qualifiers
necessary to spell a name at a point in a given DeclContext. Currently takes
using directives and nested namespecifier of DeclContext itself into account.

Initially will be used in define inline and outline actions.

[ilya-biryukov]

clang-tools-extra/clangd/AST.cpp

355

NIT: dyn_cast + assert are equivalent to a single llvm::cast

356

This can actually fail with non-namespace decl contexts, right?
Now that we expose this as a public helper, that's actually an important failure mode that we have to care about.

Maybe change the interface to accept NamespaceDecl or add assertions at the start of the function?

361

NIT: maybe check this alongside the Context->isInlineNamespace()?

auto *NSD = ...;
if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
  continue;

clang-tools-extra/clangd/AST.h

121

NIT: using namespace directives

otherwise it's too easy to confuse those with using declarations, i.e. using ns::foo;

[kadircet]

• Add support for non-namespace decl contexts.
• Add an overload for "textual namespace" handling.

[ilya-biryukov]

Just NITs about various comments and requests to optimize the code a bit.
The code itself LG, thanks!

clang-tools-extra/clangd/AST.cpp

79

s/getUsingNamespceDirectives/getUsingNamespaceDirectives

88

NIT: braces are redundant

329

Maybe exit early if NNS is not a namespace here? No need to search for it in that case.

329

llvm::any_of is O(n), maybe search in DenseSet instead?

332

Could we check against getCanonicalDecl() here?

341

Could you assert each element in VisibleNamespaces ends with :: here?

344

That's O(N) in the number of VisibleNamespaces.
Maybe accept a StringSet instead?

347

This is really inefficient and this function is called on each reference inside refactored code, so can be quite costly.
But we could optimize later if this problem actually pops up in the future.

clang-tools-extra/clangd/AST.h

124

remove this newline or add a comment marker

127

NIT: no comma is needed after 'return null'

129

Current limitation of this function is it working only for namespace.
I don't think we want to dive into complexities of lookup inside classes for C++.

Should we mention that in the doc comment?

134

Was a bit confused by the meaning of "early exit mechanism". Visible namespaces are a way to change the results of the function, yet the comment suggests it's only used to optimize and "exit early".

Could you elaborate on the intention of the comment and maybe clarify it in the code too?

clang-tools-extra/clangd/unittests/ASTTests.cpp

51

Could you add a comment describing how to read test inputs and expected results?
It seems a bit non-trivial

[ilya-biryukov]

LGTM when the comments are addressed

[kadircet]

• Address comments

[kadircet]

clang-tools-extra/clangd/AST.cpp

329

i didn't bother optimizing since it is really rare to have more than 10 using namespace directives for any given file.

[merge_guards_bot]

Build result: pass - 60224 tests passed, 0 failed and 732 were skipped.
Log files: console-log.txt, CMakeCache.txt

clang-tools-extra/clangd/AST.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_AST_H_
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_AST_H_
 
 #include "index/SymbolID.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/NestedNameSpecifier.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Lex/MacroInfo.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
+#include <string>
+#include <vector>
 
 namespace clang {
 class SourceManager;
 class Decl;
 
 namespace clangd {
 
 /// Returns true if the declaration is considered implementation detail based on

 /// could change these semantics in the future by reimplementing this funcure
 /// (e.g. avoid USR for macros).
 llvm::Optional<SymbolID> getSymbolID(const llvm::StringRef MacroName,
                                      const MacroInfo *MI,
                                      const SourceManager &SM);
 
 /// Returns a QualType as string. The result doesn't contain unwritten scopes
 /// like annoymous/inline namespace.
-std::string printType(const QualType QT, const DeclContext & Context);
+std::string printType(const QualType QT, const DeclContext &Context);
 
 /// Try to shorten the OriginalName by removing namespaces from the left of
 /// the string that are redundant in the CurrentNamespace. This way the type
 /// idenfier become shorter and easier to read.
 /// Limitation: It only handles the qualifier of the type itself, not that of
 /// templates.
 /// FIXME: change type of parameter CurrentNamespace to DeclContext ,
 /// take in to account using directives etc

 /// source, e.g.
 ///     void ns::something::foo() -> returns 'ns::something'
 ///     void foo() -> returns null
 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND);
 
 // Returns a type corresponding to a declaration of that type.
 // Unlike the method on ASTContext, attempts to preserve the type as-written
 // (i.e. vector<T*> rather than vector<type-parameter-0-0 *>.
 QualType declaredType(const TypeDecl *D);
 
 /// Retrieves the deduced type at a given location (auto, decltype).
 /// Retuns None unless Loc starts an auto/decltype token.
 /// It will return the underlying type.
 llvm::Optional<QualType> getDeducedType(ASTContext &, SourceLocation Loc);
 
+/// Gets the nested name specifier necessary for spelling \p ND in \p
+/// DestContext, at \p InsertionPoint. It selects the shortest suffix of \p ND
+/// such that it is visible in \p DestContext.
+/// Returns an empty string if no qualification is necessary. For example, if
+/// you want to qualify clang::clangd::bar::foo in clang::clangd::x, this
+/// function will return bar. Note that the result might be sub-optimal for
+/// classes, e.g. when the \p ND is a member of the base class.
+///
+/// This version considers all the using namespace directives before \p
+/// InsertionPoint. i.e, if you have `using namespace
+/// clang::clangd::bar`, this function will return an empty string for the
+/// example above since no qualification is necessary in that case.
+std::string getQualification(ASTContext &Context,
+                             const DeclContext *DestContext,
+                             SourceLocation InsertionPoint,
+                             const NamedDecl *ND);
+
+/// This function uses the \p VisibleNamespaces to figure out if a shorter
+/// qualification is sufficient for \p ND, and ignores any using namespace
+/// directives. It can be useful if there's no AST for the DestContext, but some
+/// pseudo-parsing is done. i.e. if \p ND is ns1::ns2::X and \p DestContext is
+/// ns1::, users can provide `ns2::` as visible to change the result to be
+/// empty.
+/// Elements in VisibleNamespaces should be in the form: `ns::`, with trailing
+/// "::".
+/// Note that this is just textual and might be incorrect. e.g. when there are
+/// two namespaces ns1::a and ns2::a, the function will early exit if "a::" is
+/// present in \p VisibleNamespaces, no matter whether it is from ns1:: or ns2::
+std::string getQualification(ASTContext &Context,
+                             const DeclContext *DestContext,
+                             SourceLocation InsertionPoint, const NamedDecl *ND,
+                             llvm::ArrayRef<std::string> VisibleNamespaces);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_AST_H_

clang-tools-extra/clangd/AST.cpp

 //===--- AST.cpp - Utility AST functions  -----------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "AST.h"
 
 #include "SourceCode.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TemplateBase.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Specifiers.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Lex/Lexer.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/raw_ostream.h"
+#include <string>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 namespace {
 llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>>
 getTemplateSpecializationArgLocs(const NamedDecl &ND) {
   if (auto *Func = llvm::dyn_cast<FunctionDecl>(&ND)) {

 
 bool isTemplateSpecializationKind(const NamedDecl *D,
                                   TemplateSpecializationKind Kind) {
   return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
          isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
          isTemplateSpecializationKind<VarDecl>(D, Kind);
 }
 
+// Store all UsingDirectiveDecls in parent contexts of DestContext, that were
+// introduced before InsertionPoint.
+llvm::DenseSet<const NamespaceDecl *>
+getUsingNamespaceDirectives(const DeclContext *DestContext,
+                            SourceLocation Until) {
+  const auto &SM = DestContext->getParentASTContext().getSourceManager();
+  llvm::DenseSet<const NamespaceDecl *> VisibleNamespaceDecls;
+  for (const auto *DC = DestContext; DC; DC = DC->getLookupParent()) {
+    for (const auto *D : DC->decls()) {
+      if (!SM.isWrittenInSameFile(D->getLocation(), Until) ||
+          !SM.isBeforeInTranslationUnit(D->getLocation(), Until))
+        continue;
+      if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
+        VisibleNamespaceDecls.insert(
+            UDD->getNominatedNamespace()->getCanonicalDecl());
+    }
+  }
+  return VisibleNamespaceDecls;
+}
+
+// Goes over all parents of SourceContext until we find a comman ancestor for
+// DestContext and SourceContext. Any qualifier including and above common
+// ancestor is redundant, therefore we stop at lowest common ancestor.
+// In addition to that stops early whenever IsVisible returns true. This can be
+// used to implement support for "using namespace" decls.
+std::string
+getQualification(ASTContext &Context, const DeclContext *DestContext,
+                 const DeclContext *SourceContext,
+                 llvm::function_ref<bool(NestedNameSpecifier *)> IsVisible) {
+  std::vector<const NestedNameSpecifier *> Parents;
+  bool ReachedNS = false;
+  for (const DeclContext *CurContext = SourceContext; CurContext;
+       CurContext = CurContext->getLookupParent()) {
+    // Stop once we reach a common ancestor.
+    if (CurContext->Encloses(DestContext))
+      break;
+
+    NestedNameSpecifier *NNS = nullptr;
+    if (auto *TD = llvm::dyn_cast<TagDecl>(CurContext)) {
+      // There can't be any more tag parents after hitting a namespace.
+      assert(!ReachedNS);
+      NNS = NestedNameSpecifier::Create(Context, nullptr, false,
+                                        TD->getTypeForDecl());
+    } else {
+      ReachedNS = true;
+      auto *NSD = llvm::cast<NamespaceDecl>(CurContext);
+      NNS = NestedNameSpecifier::Create(Context, nullptr, NSD);
+      // Anonymous and inline namespace names are not spelled while qualifying a
+      // name, so skip those.
+      if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
+        continue;
+    }
+    // Stop if this namespace is already visible at DestContext.
+    if (IsVisible(NNS))
+      break;
+
+    Parents.push_back(NNS);
+  }
+
+  // Go over name-specifiers in reverse order to create necessary qualification,
+  // since we stored inner-most parent first.
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  for (const auto *Parent : llvm::reverse(Parents))
+    Parent->print(OS, Context.getPrintingPolicy());
+  return OS.str();
+}
+
 } // namespace
 
 bool isImplicitTemplateInstantiation(const NamedDecl *D) {
   return isTemplateSpecializationKind(D, TSK_ImplicitInstantiation);
 }
 
 bool isExplicitTemplateSpecialization(const NamedDecl *D) {
   return isTemplateSpecializationKind(D, TSK_ExplicitSpecialization);
 }
 
 bool isImplementationDetail(const Decl *D) {
   return !isSpelledInSource(D->getLocation(),
                             D->getASTContext().getSourceManager());
 }
 
-SourceLocation findName(const clang::Decl *D) {
-  return D->getLocation();
-}
+SourceLocation findName(const clang::Decl *D) { return D->getLocation(); }
 
 std::string printQualifiedName(const NamedDecl &ND) {
   std::string QName;
   llvm::raw_string_ostream OS(QName);
   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
   // Note that inline namespaces are treated as transparent scopes. This
   // reflects the way they're most commonly used for lookup. Ideally we'd
   // include them, but at query time it's hard to find all the inline
std::string shortenNamespace(const llvm::StringRef OriginalName,
   llvm::SmallVector<llvm::StringRef, 8> CurrentParts;
   llvm::SmallVector<llvm::StringRef, 8> Result;
   OriginalName.split(OriginalParts, "::");
   CurrentNamespace.split(CurrentParts, "::");
   auto MinLength = std::min(CurrentParts.size(), OriginalParts.size());
 
   unsigned DifferentAt = 0;
   while (DifferentAt < MinLength &&
          CurrentParts[DifferentAt] == OriginalParts[DifferentAt]) {
     DifferentAt++;
   }
 
   for (unsigned i = DifferentAt; i < OriginalParts.size(); ++i) {
     Result.push_back(OriginalParts[i]);
   }
   return join(Result, "::");
 }
 
-std::string printType(const QualType QT, const DeclContext & Context){
+std::string printType(const QualType QT, const DeclContext &Context) {
   PrintingPolicy PP(Context.getParentASTContext().getPrintingPolicy());
   PP.SuppressUnwrittenScope = 1;
   PP.SuppressTagKeyword = 1;
-  return shortenNamespace(
-      QT.getAsString(PP),
-      printNamespaceScope(Context) );
+  return shortenNamespace(QT.getAsString(PP), printNamespaceScope(Context));
 }
 
 QualType declaredType(const TypeDecl *D) {
   if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D))
     if (const auto *TSI = CTSD->getTypeAsWritten())
       return TSI->getType();
   return D->getASTContext().getTypeDeclType(D);
 }
 
 namespace {
 /// Computes the deduced type at a given location by visiting the relevant
 /// nodes. We use this to display the actual type when hovering over an "auto"
 /// keyword or "decltype()" expression.
 /// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
 /// seems that the AutoTypeLocs that can be visited along with their AutoType do
 /// not have the deduced type set. Instead, we have to go to the appropriate
 /// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
 /// a deduced type set. The AST should be improved to simplify this scenario.
 class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
   SourceLocation SearchedLocation;
 
 public:
   DeducedTypeVisitor(SourceLocation SearchedLocation)
       : SearchedLocation(SearchedLocation) {}
 
   // Handle auto initializers:
   //- auto i = 1;
   //- decltype(auto) i = 1;
   //- auto& i = 1;
   //- auto* i = &a;
   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
     if (!D->getTypeSourceInfo() ||
         D->getTypeSourceInfo()->getTypeLoc().getBeginLoc() != SearchedLocation)
       return true;
 
     if (auto *AT = D->getType()->getContainedAutoType()) {
       if (!AT->getDeducedType().isNull())
         DeducedType = AT->getDeducedType();
     }
     return true;
   }
 
   // Handle auto return types:
   //- auto foo() {}
   //- auto& foo() {}
   //- auto foo() -> int {}
   //- auto foo() -> decltype(1+1) {}
   //- operator auto() const { return 10; }
   bool VisitFunctionDecl(FunctionDecl *D) {
     if (!D->getTypeSourceInfo())
       return true;
llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
   }
   DeducedTypeVisitor V(Loc);
   V.TraverseAST(ASTCtx);
   if (V.DeducedType.isNull())
     return llvm::None;
   return V.DeducedType;
 }
 
+std::string getQualification(ASTContext &Context,
+                             const DeclContext *DestContext,
+                             SourceLocation InsertionPoint,
+                             const NamedDecl *ND) {
+  auto VisibleNamespaceDecls =
+      getUsingNamespaceDirectives(DestContext, InsertionPoint);
+  return getQualification(
+      Context, DestContext, ND->getDeclContext(),
+      [&](NestedNameSpecifier *NNS) {
+        if (NNS->getKind() != NestedNameSpecifier::Namespace)
+          return false;
+        const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
+        return llvm::any_of(VisibleNamespaceDecls,
+                            [CanonNSD](const NamespaceDecl *NSD) {
+                              return NSD->getCanonicalDecl() == CanonNSD;
+                            });
+      });
+}
+
+std::string getQualification(ASTContext &Context,
+                             const DeclContext *DestContext,
+                             SourceLocation InsertionPoint, const NamedDecl *ND,
+                             llvm::ArrayRef<std::string> VisibleNamespaces) {
+  for (llvm::StringRef NS : VisibleNamespaces)
+    assert(NS.endswith("::"));
+  return getQualification(
+      Context, DestContext, ND->getDeclContext(),
+      [&](NestedNameSpecifier *NNS) {
+        return llvm::any_of(VisibleNamespaces, [&](llvm::StringRef Namespace) {
+          std::string NS;
+          llvm::raw_string_ostream OS(NS);
+          NNS->print(OS, Context.getPrintingPolicy());
+          return OS.str() == Namespace;
+        });
+      });
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/ASTTests.cpp

 //===-- ASTTests.cpp --------------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "AST.h"
 
 #include "Annotations.h"
+#include "ParsedAST.h"
 #include "TestTU.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
 #include "clang/Basic/SourceManager.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <cstddef>
+#include <string>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 TEST(ShortenNamespace, All) {
   ASSERT_EQ("TestClass", shortenNamespace("TestClass", ""));
 
ASSERT_EQ(
       "testns2::TestClass",
       shortenNamespace("testns1::testns2::TestClass", "testns1"));
 
   ASSERT_EQ("TestClass<testns1::OtherClass>",
             shortenNamespace(
                 "testns1::TestClass<testns1::OtherClass>", "testns1"));
 }
 
 TEST(GetDeducedType, KwAutoExpansion) {
   struct Test {
     StringRef AnnotatedCode;
     const char *DeducedType;
   } Tests[] = {
       {"^auto i = 0;", "int"},
       {"^auto f(){ return 1;};", "int"},
   };
   for (Test T : Tests) {
     Annotations File(T.AnnotatedCode);
     auto AST = TestTU::withCode(File.code()).build();
     ASSERT_TRUE(AST.getDiagnostics().empty())
         << AST.getDiagnostics().begin()->Message;
     SourceManagerForFile SM("foo.cpp", File.code());
 
     for (Position Pos : File.points()) {
       auto Location = sourceLocationInMainFile(SM.get(), Pos);
       ASSERT_TRUE(!!Location) << llvm::toString(Location.takeError());
       auto DeducedType = getDeducedType(AST.getASTContext(), *Location);
       EXPECT_EQ(DeducedType->getAsString(), T.DeducedType);
     }
   }
 }
 
+TEST(ClangdAST, GetQualification) {
+  // Tries to insert the decl `Foo` into position of each decl named `insert`.
+  // This is done to get an appropriate DeclContext for the insertion location.
+  // Qualifications are the required nested name specifier to spell `Foo` at the
+  // `insert`ion location.
+  // VisibleNamespaces are assumed to be visible at every insertion location.
+  const struct {
+    llvm::StringRef Test;
+    std::vector<llvm::StringRef> Qualifications;
+    std::vector<std::string> VisibleNamespaces;
+  } Cases[] = {
+      {
+          R"cpp(
+            namespace ns1 { namespace ns2 { class Foo {}; } }
+            void insert(); // ns1::ns2::Foo
+            namespace ns1 {
+              void insert(); // ns2::Foo
+              namespace ns2 {
+                void insert(); // Foo
+              }
+              using namespace ns2;
+              void insert(); // Foo
+            }
+            using namespace ns1;
+            void insert(); // ns2::Foo
+            using namespace ns2;
+            void insert(); // Foo
+          )cpp",
+          {"ns1::ns2::", "ns2::", "", "", "ns2::", ""},
+          {},
+      },
+      {
+          R"cpp(
+            namespace ns1 { namespace ns2 { class Bar { void Foo(); }; } }
+            void insert(); // ns1::ns2::Bar::Foo
+            namespace ns1 {
+              void insert(); // ns2::Bar::Foo
+              namespace ns2 {
+                void insert(); // Bar::Foo
+              }
+              using namespace ns2;
+              void insert(); // Bar::Foo
+            }
+            using namespace ns1;
+            void insert(); // ns2::Bar::Foo
+            using namespace ns2;
+            void insert(); // Bar::Foo
+          )cpp",
+          {"ns1::ns2::Bar::", "ns2::Bar::", "Bar::", "Bar::", "ns2::Bar::",
+           "Bar::"},
+          {},
+      },
+      {
+          R"cpp(
+            namespace ns1 { namespace ns2 { void Foo(); } }
+            void insert(); // ns2::Foo
+            namespace ns1 {
+              void insert(); // ns2::Foo
+              namespace ns2 {
+                void insert(); // Foo
+              }
+            }
+          )cpp",
+          {"ns2::", "ns2::", ""},
+          {"ns1::"},
+      },
+  };
+  for (const auto &Case : Cases) {
+    Annotations Test(Case.Test);
+    TestTU TU = TestTU::withCode(Test.code());
+    ParsedAST AST = TU.build();
+    std::vector<const Decl *> InsertionPoints;
+    const NamedDecl *TargetDecl;
+    findDecl(AST, [&](const NamedDecl &ND) {
+      if (ND.getNameAsString() == "Foo") {
+        TargetDecl = &ND;
+        return true;
+      }
+
+      if (ND.getNameAsString() == "insert")
+        InsertionPoints.push_back(&ND);
+      return false;
+    });
+
+    ASSERT_EQ(InsertionPoints.size(), Case.Qualifications.size());
+    for (size_t I = 0, E = InsertionPoints.size(); I != E; ++I) {
+      const Decl *D = InsertionPoints[I];
+      if (Case.VisibleNamespaces.empty()) {
+        EXPECT_EQ(getQualification(AST.getASTContext(),
+                                   D->getLexicalDeclContext(), D->getBeginLoc(),
+                                   TargetDecl),
+                  Case.Qualifications[I]);
+      } else {
+        EXPECT_EQ(getQualification(AST.getASTContext(),
+                                   D->getLexicalDeclContext(), D->getBeginLoc(),
+                                   TargetDecl, Case.VisibleNamespaces),
+                  Case.Qualifications[I]);
+      }
+    }
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang