[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

281

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

282

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?

287

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

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

clang-tools-extra/clangd/AST.h

118

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

71

s/getUsingNamespceDirectives/getUsingNamespaceDirectives

80

NIT: braces are redundant

255

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

255

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

258

Could we check against getCanonicalDecl() here?

267

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

270

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

273

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

121

remove this newline or add a comment marker

124

NIT: no comma is needed after 'return null'

126

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?

131

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

48

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

255

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"
 
 namespace clang {
 class SourceManager;
 class Decl;
 
 namespace clangd {
 
 /// Returns true if the declaration is considered implementation detail based on

 bool isExplicitTemplateSpecialization(const NamedDecl *D);
 
 /// Returns a nested name specifier loc of \p ND if it was present in the
 /// source, e.g.
 ///     void ns::something::foo() -> returns 'ns::something'
 ///     void foo() -> returns null
 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND);
 
+/// 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, considering all the using
+/// directives before \p InsertionPoint.
+/// Returns null 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. Also if you have `using namespace clang::clangd::bar` before \p
+/// InsertionPoint this function will return null, since no qualification is
+/// necessary in that case.
+NestedNameSpecifier *getQualification(ASTContext &Context,
+                                      const DeclContext *DestContext,
+                                      SourceLocation InsertionPoint,
+                                      const NamedDecl *ND);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_AST_H_

clang-tools-extra/clangd/AST.cpp

bool isTemplateSpecializationKind(const NamedDecl *D,
   return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
          isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
          isTemplateSpecializationKind<VarDecl>(D, Kind);
 }
 
 } // 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();
 }
 
 std::string printQualifiedName(const NamedDecl &ND) {
   std::string QName;
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) );
 }
 
+NestedNameSpecifier *getQualification(ASTContext &Context,
+                                      const DeclContext *DestContext,
+                                      SourceLocation InsertionPoint,
+                                      const NamedDecl *ND) {
+  const auto &SM = Context.getSourceManager();
+  // Store all UsingDirectiveDecls in parent contexts of DestContext, that were
+  // introduced before InsertionPoint.
+  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(), InsertionPoint) ||
+          !SM.isBeforeInTranslationUnit(D->getLocation(), InsertionPoint))
+        continue;
+      if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D)) {
+        VisibleNamespaceDecls.insert(
+            UDD->getNominatedNamespace()->getCanonicalDecl());
+      }
+    }
+  }
+
+  // Goes over all parents of ND until we find a comman ancestor for DestContext
+  // and ND. Any qualifier including and above common ancestor is redundant,
+  // therefore we stop at lowest common ancestor.
+  std::vector<const NamespaceDecl *> SourceParents;
+  for (const DeclContext *Context = ND->getLexicalDeclContext(); Context;
+       Context = Context->getLookupParent()) {
+    // Stop once we reach a common ancestor.
+    if (Context->Encloses(DestContext))
+      break;
+    // Inline namespace names are not spelled while qualifying a name, so skip
+    // those.
+    if (Context->isInlineNamespace())
+      continue;
+
+    auto *NSD = llvm::dyn_cast<NamespaceDecl>(Context);
+    assert(NSD && "Non-namespace decl context found.");
+    // Stop if this namespace is already visible at DestContext.
+    if (VisibleNamespaceDecls.count(NSD->getCanonicalDecl()))
+      break;
+    // Again, ananoymous namespaces are not spelled while qualifying a name.
+    if (NSD->isAnonymousNamespace())
+      continue;
+
+    SourceParents.push_back(NSD);
+  }
+
+  // Go over name-specifiers in reverse order to create necessary qualification,
+  // since we stored inner-most parent first.
+  NestedNameSpecifier *Result = nullptr;
+  for (const auto *Parent : llvm::reverse(SourceParents))
+    Result = NestedNameSpecifier::Create(Context, Result, Parent);
+  return Result;
+}
 
 } // 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 "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <cstddef>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 TEST(ExpandAutoType, ShortenNamespace) {
   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(ClangdAST, GetQualification) {
+  struct {
+    llvm::StringRef Test;
+    std::vector<llvm::StringRef> Qualifications;
+  } 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::", ""},
+      },
+  };
+  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];
+      auto Qual =
+          getQualification(AST.getASTContext(), D->getLexicalDeclContext(),
+                           D->getBeginLoc(), TargetDecl);
+      if (!Qual)
+        EXPECT_TRUE(Case.Qualifications[I].empty());
+      else {
+        std::string Qualifier;
+        llvm::raw_string_ostream OS(Qualifier);
+        Qual->print(OS, AST.getASTContext().getPrintingPolicy(), true);
+        EXPECT_EQ(OS.str(), Case.Qualifications[I]);
+      }
+    }
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang