clang-tools-extra/clangd/AST.cpp - toolchain/llvm-project - Gitiles

 //===--- 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 "FindTarget.h"
 #include "SourceCode.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.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 "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)) {
     if (const ASTTemplateArgumentListInfo *Args =
             Func->getTemplateSpecializationArgsAsWritten())
       return Args->arguments();
   } else if (auto *Cls =
                  llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(&ND)) {
     if (auto *Args = Cls->getTemplateArgsAsWritten())
       return Args->arguments();
   } else if (auto *Var =
                  llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(&ND)) {
     if (auto *Args = Var->getTemplateArgsAsWritten())
       return Args->arguments();
   } else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(&ND))
     return Var->getTemplateArgsInfo().arguments();
   // We return None for ClassTemplateSpecializationDecls because it does not
   // contain TemplateArgumentLoc information.
   return llvm::None;
 }

 template <class T>
 bool isTemplateSpecializationKind(const NamedDecl *D,
                                   TemplateSpecializationKind Kind) {
   if (const auto *TD = dyn_cast<T>(D))
     return TD->getTemplateSpecializationKind() == Kind;
   return false;
 }

 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 nameLocation(const clang::Decl &D, const SourceManager &SM) {
   auto L = D.getLocation();
   if (isSpelledInSource(L, SM))
     return SM.getSpellingLoc(L);
   return SM.getExpansionLoc(L);
 }

 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
   // namespaces to query: the preamble doesn't have a dedicated list.
   Policy.SuppressUnwrittenScope = true;
   ND.printQualifiedName(OS, Policy);
   OS.flush();
   assert(!StringRef(QName).startswith("::"));
   return QName;
 }

 static bool isAnonymous(const DeclarationName &N) {
   return N.isIdentifier() && !N.getAsIdentifierInfo();
 }

 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
   if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
     return V->getQualifierLoc();
   if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
     return T->getQualifierLoc();
   return NestedNameSpecifierLoc();
 }

 std::string printUsingNamespaceName(const ASTContext &Ctx,
                                     const UsingDirectiveDecl &D) {
   PrintingPolicy PP(Ctx.getLangOpts());
   std::string Name;
   llvm::raw_string_ostream Out(Name);

   if (auto *Qual = D.getQualifier())
     Qual->print(Out, PP);
   D.getNominatedNamespaceAsWritten()->printName(Out);
   return Out.str();
 }

 std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
   std::string Name;
   llvm::raw_string_ostream Out(Name);
   PrintingPolicy PP(Ctx.getLangOpts());
   // We don't consider a class template's args part of the constructor name.
   PP.SuppressTemplateArgsInCXXConstructors = true;

   // Handle 'using namespace'. They all have the same name - <using-directive>.
   if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
     Out << "using namespace ";
     if (auto *Qual = UD->getQualifier())
       Qual->print(Out, PP);
     UD->getNominatedNamespaceAsWritten()->printName(Out);
     return Out.str();
   }

   if (isAnonymous(ND.getDeclName())) {
     // Come up with a presentation for an anonymous entity.
     if (isa<NamespaceDecl>(ND))
       return "(anonymous namespace)";
     if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
       if (Cls->isLambda())
         return "(lambda)";
       return ("(anonymous " + Cls->getKindName() + ")").str();
     }
     if (isa<EnumDecl>(ND))
       return "(anonymous enum)";
     return "(anonymous)";
   }

   // Print nested name qualifier if it was written in the source code.
   if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
     Qualifier->print(Out, PP);
   // Print the name itself.
   ND.getDeclName().print(Out, PP);
   // Print template arguments.
   Out << printTemplateSpecializationArgs(ND);

   return Out.str();
 }

 std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
   std::string TemplateArgs;
   llvm::raw_string_ostream OS(TemplateArgs);
   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
   if (llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
           getTemplateSpecializationArgLocs(ND)) {
     printTemplateArgumentList(OS, *Args, Policy);
   } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
     if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
       // ClassTemplateSpecializationDecls do not contain
       // TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
       // create a new argument location list from TypeSourceInfo.
       auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
       llvm::SmallVector<TemplateArgumentLoc, 8> ArgLocs;
       ArgLocs.reserve(STL.getNumArgs());
       for (unsigned I = 0; I < STL.getNumArgs(); ++I)
         ArgLocs.push_back(STL.getArgLoc(I));
       printTemplateArgumentList(OS, ArgLocs, Policy);
     } else {
       // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
       // e.g. friend decls. Currently we fallback to Template Arguments without
       // location information.
       printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
     }
   }
   OS.flush();
   return TemplateArgs;
 }

 std::string printNamespaceScope(const DeclContext &DC) {
   for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
     if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
       if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
         return printQualifiedName(*NS) + "::";
   return "";
 }

 llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
   llvm::SmallString<128> USR;
   if (index::generateUSRForDecl(D, USR))
     return None;
   return SymbolID(USR);
 }

 llvm::Optional<SymbolID> getSymbolID(const llvm::StringRef MacroName,
                                      const MacroInfo *MI,
                                      const SourceManager &SM) {
   if (MI == nullptr)
     return None;
   llvm::SmallString<128> USR;
   if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
     return None;
   return SymbolID(USR);
 }

 // FIXME: This should be handled while printing underlying decls instead.
 std::string printType(const QualType QT, const DeclContext &CurContext) {
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   auto Decls = explicitReferenceTargets(
       ast_type_traits::DynTypedNode::create(QT), DeclRelation::Alias);
   if (!Decls.empty())
     OS << getQualification(CurContext.getParentASTContext(), &CurContext,
                            Decls.front(),
                            /*VisibleNamespaces=*/llvm::ArrayRef<std::string>{});
   PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
   PP.SuppressScope = true;
   PP.SuppressTagKeyword = true;
   QT.print(OS, PP);
   return OS.str();
 }

 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;
     // Loc of auto in return type (c++14).
     auto CurLoc = D->getReturnTypeSourceRange().getBegin();
     // Loc of "auto" in operator auto()
     if (CurLoc.isInvalid() && dyn_cast<CXXConversionDecl>(D))
       CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
     // Loc of "auto" in function with trailing return type (c++11).
     if (CurLoc.isInvalid())
       CurLoc = D->getSourceRange().getBegin();
     if (CurLoc != SearchedLocation)
       return true;

     const AutoType *AT = D->getReturnType()->getContainedAutoType();
     if (AT && !AT->getDeducedType().isNull()) {
       DeducedType = AT->getDeducedType();
     } else if (auto DT = dyn_cast<DecltypeType>(D->getReturnType())) {
       // auto in a trailing return type just points to a DecltypeType and
       // getContainedAutoType does not unwrap it.
       if (!DT->getUnderlyingType().isNull())
         DeducedType = DT->getUnderlyingType();
     } else if (!D->getReturnType().isNull()) {
       DeducedType = D->getReturnType();
     }
     return true;
   }

   // Handle non-auto decltype, e.g.:
   // - auto foo() -> decltype(expr) {}
   // - decltype(expr);
   bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
     if (TL.getBeginLoc() != SearchedLocation)
       return true;

     // A DecltypeType's underlying type can be another DecltypeType! E.g.
     //  int I = 0;
     //  decltype(I) J = I;
     //  decltype(J) K = J;
     const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
     while (DT && !DT->getUnderlyingType().isNull()) {
       DeducedType = DT->getUnderlyingType();
       DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
     }
     return true;
   }

   QualType DeducedType;
 };
 } // namespace

 llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
                                         SourceLocation Loc) {
   if (!Loc.isValid())
     return {};
   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,
                              const NamedDecl *ND,
                              llvm::ArrayRef<std::string> VisibleNamespaces) {
   for (llvm::StringRef NS : VisibleNamespaces) {
     assert(NS.endswith("::"));
     (void)NS;
   }
   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;
         });
       });
 }

 bool hasUnstableLinkage(const Decl *D) {
   // Linkage of a ValueDecl depends on the type.
   // If that's not deduced yet, deducing it may change the linkage.
   auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
   return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
 }

 } // namespace clangd
 } // namespace clang
	//===--- 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 "FindTarget.h"
	#include "SourceCode.h"
	#include "clang/AST/ASTContext.h"
	#include "clang/AST/ASTTypeTraits.h"
	#include "clang/AST/Decl.h"
	#include "clang/AST/DeclBase.h"
	#include "clang/AST/DeclCXX.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 "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)) {
	if (const ASTTemplateArgumentListInfo *Args =
	Func->getTemplateSpecializationArgsAsWritten())
	return Args->arguments();
	} else if (auto *Cls =
	llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(&ND)) {
	if (auto *Args = Cls->getTemplateArgsAsWritten())
	return Args->arguments();
	} else if (auto *Var =
	llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(&ND)) {
	if (auto *Args = Var->getTemplateArgsAsWritten())
	return Args->arguments();
	} else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(&ND))
	return Var->getTemplateArgsInfo().arguments();
	// We return None for ClassTemplateSpecializationDecls because it does not
	// contain TemplateArgumentLoc information.
	return llvm::None;
	}

	template <class T>
	bool isTemplateSpecializationKind(const NamedDecl *D,
	TemplateSpecializationKind Kind) {
	if (const auto *TD = dyn_cast<T>(D))
	return TD->getTemplateSpecializationKind() == Kind;
	return false;
	}

	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 nameLocation(const clang::Decl &D, const SourceManager &SM) {
	auto L = D.getLocation();
	if (isSpelledInSource(L, SM))
	return SM.getSpellingLoc(L);
	return SM.getExpansionLoc(L);
	}

	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
	// namespaces to query: the preamble doesn't have a dedicated list.
	Policy.SuppressUnwrittenScope = true;
	ND.printQualifiedName(OS, Policy);
	OS.flush();
	assert(!StringRef(QName).startswith("::"));
	return QName;
	}

	static bool isAnonymous(const DeclarationName &N) {
	return N.isIdentifier() && !N.getAsIdentifierInfo();
	}

	NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
	if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
	return V->getQualifierLoc();
	if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
	return T->getQualifierLoc();
	return NestedNameSpecifierLoc();
	}

	std::string printUsingNamespaceName(const ASTContext &Ctx,
	const UsingDirectiveDecl &D) {
	PrintingPolicy PP(Ctx.getLangOpts());
	std::string Name;
	llvm::raw_string_ostream Out(Name);

	if (auto *Qual = D.getQualifier())
	Qual->print(Out, PP);
	D.getNominatedNamespaceAsWritten()->printName(Out);
	return Out.str();
	}

	std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
	std::string Name;
	llvm::raw_string_ostream Out(Name);
	PrintingPolicy PP(Ctx.getLangOpts());
	// We don't consider a class template's args part of the constructor name.
	PP.SuppressTemplateArgsInCXXConstructors = true;

	// Handle 'using namespace'. They all have the same name - <using-directive>.
	if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
	Out << "using namespace ";
	if (auto *Qual = UD->getQualifier())
	Qual->print(Out, PP);
	UD->getNominatedNamespaceAsWritten()->printName(Out);
	return Out.str();
	}

	if (isAnonymous(ND.getDeclName())) {
	// Come up with a presentation for an anonymous entity.
	if (isa<NamespaceDecl>(ND))
	return "(anonymous namespace)";
	if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
	if (Cls->isLambda())
	return "(lambda)";
	return ("(anonymous " + Cls->getKindName() + ")").str();
	}
	if (isa<EnumDecl>(ND))
	return "(anonymous enum)";
	return "(anonymous)";
	}

	// Print nested name qualifier if it was written in the source code.
	if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
	Qualifier->print(Out, PP);
	// Print the name itself.
	ND.getDeclName().print(Out, PP);
	// Print template arguments.
	Out << printTemplateSpecializationArgs(ND);

	return Out.str();
	}

	std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
	std::string TemplateArgs;
	llvm::raw_string_ostream OS(TemplateArgs);
	PrintingPolicy Policy(ND.getASTContext().getLangOpts());
	if (llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
	getTemplateSpecializationArgLocs(ND)) {
	printTemplateArgumentList(OS, *Args, Policy);
	} else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
	if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
	// ClassTemplateSpecializationDecls do not contain
	// TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
	// create a new argument location list from TypeSourceInfo.
	auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
	llvm::SmallVector<TemplateArgumentLoc, 8> ArgLocs;
	ArgLocs.reserve(STL.getNumArgs());
	for (unsigned I = 0; I < STL.getNumArgs(); ++I)
	ArgLocs.push_back(STL.getArgLoc(I));
	printTemplateArgumentList(OS, ArgLocs, Policy);
	} else {
	// FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
	// e.g. friend decls. Currently we fallback to Template Arguments without
	// location information.
	printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
	}
	}
	OS.flush();
	return TemplateArgs;
	}

	std::string printNamespaceScope(const DeclContext &DC) {
	for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
	if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
	if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
	return printQualifiedName(*NS) + "::";
	return "";
	}

	llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
	llvm::SmallString<128> USR;
	if (index::generateUSRForDecl(D, USR))
	return None;
	return SymbolID(USR);
	}

	llvm::Optional<SymbolID> getSymbolID(const llvm::StringRef MacroName,
	const MacroInfo *MI,
	const SourceManager &SM) {
	if (MI == nullptr)
	return None;
	llvm::SmallString<128> USR;
	if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
	return None;
	return SymbolID(USR);
	}

	// FIXME: This should be handled while printing underlying decls instead.
	std::string printType(const QualType QT, const DeclContext &CurContext) {
	std::string Result;
	llvm::raw_string_ostream OS(Result);
	auto Decls = explicitReferenceTargets(
	ast_type_traits::DynTypedNode::create(QT), DeclRelation::Alias);
	if (!Decls.empty())
	OS << getQualification(CurContext.getParentASTContext(), &CurContext,
	Decls.front(),
	/VisibleNamespaces=/llvm::ArrayRef<std::string>{});
	PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
	PP.SuppressScope = true;
	PP.SuppressTagKeyword = true;
	QT.print(OS, PP);
	return OS.str();
	}

	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;
	// Loc of auto in return type (c++14).
	auto CurLoc = D->getReturnTypeSourceRange().getBegin();
	// Loc of "auto" in operator auto()
	if (CurLoc.isInvalid() && dyn_cast<CXXConversionDecl>(D))
	CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
	// Loc of "auto" in function with trailing return type (c++11).
	if (CurLoc.isInvalid())
	CurLoc = D->getSourceRange().getBegin();
	if (CurLoc != SearchedLocation)
	return true;

	const AutoType *AT = D->getReturnType()->getContainedAutoType();
	if (AT && !AT->getDeducedType().isNull()) {
	DeducedType = AT->getDeducedType();
	} else if (auto DT = dyn_cast<DecltypeType>(D->getReturnType())) {
	// auto in a trailing return type just points to a DecltypeType and
	// getContainedAutoType does not unwrap it.
	if (!DT->getUnderlyingType().isNull())
	DeducedType = DT->getUnderlyingType();
	} else if (!D->getReturnType().isNull()) {
	DeducedType = D->getReturnType();
	}
	return true;
	}

	// Handle non-auto decltype, e.g.:
	// - auto foo() -> decltype(expr) {}
	// - decltype(expr);
	bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
	if (TL.getBeginLoc() != SearchedLocation)
	return true;

	// A DecltypeType's underlying type can be another DecltypeType! E.g.
	// int I = 0;
	// decltype(I) J = I;
	// decltype(J) K = J;
	const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
	while (DT && !DT->getUnderlyingType().isNull()) {
	DeducedType = DT->getUnderlyingType();
	DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
	}
	return true;
	}

	QualType DeducedType;
	};
	} // namespace

	llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
	SourceLocation Loc) {
	if (!Loc.isValid())
	return {};
	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,
	const NamedDecl *ND,
	llvm::ArrayRef<std::string> VisibleNamespaces) {
	for (llvm::StringRef NS : VisibleNamespaces) {
	assert(NS.endswith("::"));
	(void)NS;
	}
	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;
	});
	});
	}

	bool hasUnstableLinkage(const Decl *D) {
	// Linkage of a ValueDecl depends on the type.
	// If that's not deduced yet, deducing it may change the linkage.
	auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
	return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
	}

	} // namespace clangd
	} // namespace clang