Index: clang-tools-extra/trunk/clangd/FindTarget.h =================================================================== --- clang-tools-extra/trunk/clangd/FindTarget.h +++ clang-tools-extra/trunk/clangd/FindTarget.h @@ -20,8 +20,14 @@ //===----------------------------------------------------------------------===// #include "clang/AST/ASTTypeTraits.h" +#include "clang/AST/NestedNameSpecifier.h" +#include "clang/AST/Stmt.h" #include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/raw_ostream.h" #include @@ -69,6 +75,34 @@ llvm::SmallVector targetDecl(const ast_type_traits::DynTypedNode &, DeclRelationSet Mask); +/// Information about a reference written in the source code, independent of the +/// actual AST node that this reference lives in. +/// Useful for tools that are source-aware, e.g. refactorings. +struct ReferenceLoc { + /// Contains qualifier written in the code, if any, e.g. 'ns::' for 'ns::foo'. + NestedNameSpecifierLoc Qualifier; + /// Start location of the last name part, i.e. 'foo' in 'ns::foo'. + SourceLocation NameLoc; + // FIXME: add info about template arguments. + /// A list of targets referenced by this name. Normally this has a single + /// element, but multiple is also possible, e.g. in case of using declarations + /// or unresolved overloaded functions. + /// For dependent and unresolved references, Targets can also be empty. + llvm::SmallVector Targets; +}; +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R); + +/// Recursively traverse \p S and report all references explicitly written in +/// the code. The main use-case is refactorings that need to process all +/// references in some subrange of the file and apply simple edits, e.g. add +/// qualifiers. +/// FIXME: currently this does not report references to overloaded operators. +/// FIXME: extend to report location information about declaration names too. +void findExplicitReferences(Stmt *S, + llvm::function_ref Out); +void findExplicitReferences(Decl *D, + llvm::function_ref Out); + /// Similar to targetDecl(), however instead of applying a filter, all possible /// decls are returned along with their DeclRelationSets. /// This is suitable for indexing, where everything is recorded and filtering Index: clang-tools-extra/trunk/clangd/FindTarget.cpp =================================================================== --- clang-tools-extra/trunk/clangd/FindTarget.cpp +++ clang-tools-extra/trunk/clangd/FindTarget.cpp @@ -10,22 +10,33 @@ #include "AST.h" #include "Logger.h" #include "clang/AST/ASTTypeTraits.h" +#include "clang/AST/Decl.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/DeclTemplate.h" #include "clang/AST/DeclVisitor.h" #include "clang/AST/DeclarationName.h" +#include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" +#include "clang/AST/NestedNameSpecifier.h" +#include "clang/AST/PrettyPrinter.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/StmtVisitor.h" #include "clang/AST/Type.h" +#include "clang/AST/TypeLoc.h" #include "clang/AST/TypeLocVisitor.h" +#include "clang/Basic/LangOptions.h" #include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" +#include namespace clang { namespace clangd { namespace { +using ast_type_traits::DynTypedNode; LLVM_ATTRIBUTE_UNUSED std::string nodeToString(const ast_type_traits::DynTypedNode &N) { @@ -348,12 +359,274 @@ llvm::SmallVector targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) { llvm::SmallVector Result; - for (const auto &Entry : allTargetDecls(N)) + for (const auto &Entry : allTargetDecls(N)) { if (!(Entry.second & ~Mask)) Result.push_back(Entry.first); + } return Result; } +namespace { +/// Find declarations explicitly referenced in the source code defined by \p N. +/// For templates, will prefer to return a template instantiation whenever +/// possible. However, can also return a template pattern if the specialization +/// cannot be picked, e.g. in dependent code or when there is no corresponding +/// Decl for a template instantitation, e.g. for templated using decls: +/// template using Ptr = T*; +/// Ptr x; +/// ^~~ there is no Decl for 'Ptr', so we return the template pattern. +llvm::SmallVector +explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask = {}) { + assert(!(Mask & (DeclRelation::TemplatePattern | + DeclRelation::TemplateInstantiation)) && + "explicitRefenceTargets handles templates on its own"); + auto Decls = allTargetDecls(N); + + // We prefer to return template instantiation, but fallback to template + // pattern if instantiation is not available. + Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation; + + llvm::SmallVector TemplatePatterns; + llvm::SmallVector Targets; + bool SeenTemplateInstantiations = false; + for (auto &D : Decls) { + if (D.second & ~Mask) + continue; + if (D.second & DeclRelation::TemplatePattern) { + TemplatePatterns.push_back(llvm::cast(D.first)); + continue; + } + if (D.second & DeclRelation::TemplateInstantiation) + SeenTemplateInstantiations = true; + Targets.push_back(llvm::cast(D.first)); + } + if (!SeenTemplateInstantiations) + Targets.insert(Targets.end(), TemplatePatterns.begin(), + TemplatePatterns.end()); + return Targets; +} + +Optional refInDecl(const Decl *D) { + struct Visitor : ConstDeclVisitor { + llvm::Optional Ref; + + void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) { + Ref = ReferenceLoc{D->getQualifierLoc(), + D->getIdentLocation(), + {D->getNominatedNamespaceAsWritten()}}; + } + + void VisitUsingDecl(const UsingDecl *D) { + Ref = ReferenceLoc{D->getQualifierLoc(), D->getLocation(), + explicitReferenceTargets(DynTypedNode::create(*D), + DeclRelation::Underlying)}; + } + + void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) { + Ref = ReferenceLoc{D->getQualifierLoc(), + D->getTargetNameLoc(), + {D->getAliasedNamespace()}}; + } + }; + + Visitor V; + V.Visit(D); + return V.Ref; +} + +Optional refInExpr(const Expr *E) { + struct Visitor : ConstStmtVisitor { + // FIXME: handle more complicated cases, e.g. ObjC, designated initializers. + llvm::Optional Ref; + + void VisitDeclRefExpr(const DeclRefExpr *E) { + Ref = ReferenceLoc{ + E->getQualifierLoc(), E->getNameInfo().getLoc(), {E->getFoundDecl()}}; + } + + void VisitMemberExpr(const MemberExpr *E) { + Ref = ReferenceLoc{E->getQualifierLoc(), + E->getMemberNameInfo().getLoc(), + {E->getFoundDecl()}}; + } + }; + + Visitor V; + V.Visit(E); + return V.Ref; +} + +Optional refInTypeLoc(TypeLoc L) { + struct Visitor : TypeLocVisitor { + llvm::Optional Ref; + + void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) { + // We only know about qualifier, rest if filled by inner locations. + Visit(L.getNamedTypeLoc().getUnqualifiedLoc()); + // Fill in the qualifier. + if (!Ref) + return; + assert(!Ref->Qualifier.hasQualifier() && "qualifier already set"); + Ref->Qualifier = L.getQualifierLoc(); + } + + void VisitDeducedTemplateSpecializationTypeLoc( + DeducedTemplateSpecializationTypeLoc L) { + Ref = ReferenceLoc{ + NestedNameSpecifierLoc(), L.getNameLoc(), + explicitReferenceTargets(DynTypedNode::create(L.getType()))}; + } + + void VisitTagTypeLoc(TagTypeLoc L) { + Ref = + ReferenceLoc{NestedNameSpecifierLoc(), L.getNameLoc(), {L.getDecl()}}; + } + + void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) { + Ref = ReferenceLoc{ + NestedNameSpecifierLoc(), L.getTemplateNameLoc(), + explicitReferenceTargets(DynTypedNode::create(L.getType()))}; + } + + void VisitDependentTemplateSpecializationTypeLoc( + DependentTemplateSpecializationTypeLoc L) { + Ref = ReferenceLoc{ + L.getQualifierLoc(), L.getTemplateNameLoc(), + explicitReferenceTargets(DynTypedNode::create(L.getType()))}; + } + + void VisitDependentNameTypeLoc(DependentNameTypeLoc L) { + Ref = ReferenceLoc{ + L.getQualifierLoc(), L.getNameLoc(), + explicitReferenceTargets(DynTypedNode::create(L.getType()))}; + } + + void VisitTypedefTypeLoc(TypedefTypeLoc L) { + Ref = ReferenceLoc{ + NestedNameSpecifierLoc(), L.getNameLoc(), {L.getTypedefNameDecl()}}; + } + }; + + Visitor V; + V.Visit(L.getUnqualifiedLoc()); + return V.Ref; +} + +class ExplicitReferenceColletor + : public RecursiveASTVisitor { +public: + ExplicitReferenceColletor(llvm::function_ref Out) + : Out(Out) { + assert(Out); + } + + bool VisitTypeLoc(TypeLoc TTL) { + if (TypeLocsToSkip.count(TTL.getBeginLoc().getRawEncoding())) + return true; + visitNode(DynTypedNode::create(TTL)); + return true; + } + + bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) { + // ElaboratedTypeLoc will reports information for its inner type loc. + // Otherwise we loose information about inner types loc's qualifier. + TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc(); + TypeLocsToSkip.insert(Inner.getBeginLoc().getRawEncoding()); + return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L); + } + + bool VisitExpr(Expr *E) { + visitNode(DynTypedNode::create(*E)); + return true; + } + + bool VisitDecl(Decl *D) { + visitNode(DynTypedNode::create(*D)); + return true; + } + + // We have to use Traverse* because there is no corresponding Visit*. + bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) { + if (!L.getNestedNameSpecifier()) + return true; + visitNode(DynTypedNode::create(L)); + // Inner type is missing information about its qualifier, skip it. + if (auto TL = L.getTypeLoc()) + TypeLocsToSkip.insert(TL.getBeginLoc().getRawEncoding()); + return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L); + } + +private: + /// Obtain information about a reference directly defined in \p N. Does not + /// recurse into child nodes, e.g. do not expect references for constructor + /// initializers + /// + /// Any of the fields in the returned structure can be empty, but not all of + /// them, e.g. + /// - for implicitly generated nodes (e.g. MemberExpr from range-based-for), + /// source location information may be missing, + /// - for dependent code, targets may be empty. + /// + /// (!) For the purposes of this function declarations are not considered to + /// be references. However, declarations can have references inside them, + /// e.g. 'namespace foo = std' references namespace 'std' and this + /// function will return the corresponding reference. + llvm::Optional explicitReference(DynTypedNode N) { + if (auto *D = N.get()) + return refInDecl(D); + if (auto *E = N.get()) + return refInExpr(E); + if (auto *NNSL = N.get()) + return ReferenceLoc{NNSL->getPrefix(), NNSL->getLocalBeginLoc(), + explicitReferenceTargets(DynTypedNode::create( + *NNSL->getNestedNameSpecifier()))}; + if (const TypeLoc *TL = N.get()) + return refInTypeLoc(*TL); + if (const CXXCtorInitializer *CCI = N.get()) { + if (CCI->isBaseInitializer()) + return refInTypeLoc(CCI->getBaseClassLoc()); + assert(CCI->isAnyMemberInitializer()); + return ReferenceLoc{NestedNameSpecifierLoc(), + CCI->getMemberLocation(), + {CCI->getAnyMember()}}; + } + // We do not have location information for other nodes (QualType, etc) + return llvm::None; + } + + void visitNode(DynTypedNode N) { + auto Ref = explicitReference(N); + if (!Ref) + return; + // Our promise is to return only references from the source code. If we lack + // location information, skip these nodes. + // Normally this should not happen in practice, unless there are bugs in the + // traversals or users started the traversal at an implicit node. + if (Ref->NameLoc.isInvalid()) { + dlog("invalid location at node {0}", nodeToString(N)); + return; + } + Out(*Ref); + } + + llvm::function_ref Out; + /// TypeLocs starting at these locations must be skipped, see + /// TraverseElaboratedTypeSpecifierLoc for details. + llvm::DenseSet TypeLocsToSkip; +}; +} // namespace + +void findExplicitReferences(Stmt *S, + llvm::function_ref Out) { + assert(S); + ExplicitReferenceColletor(Out).TraverseStmt(S); +} +void findExplicitReferences(Decl *D, + llvm::function_ref Out) { + assert(D); + ExplicitReferenceColletor(Out).TraverseDecl(D); +} + llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) { switch (R) { #define REL_CASE(X) \ @@ -378,5 +651,26 @@ return OS; } +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) { + // note we cannot print R.NameLoc without a source manager. + OS << "targets = {"; + bool First = true; + for (const NamedDecl *T : R.Targets) { + if (!First) + OS << ", "; + else + First = false; + OS << printQualifiedName(*T) << printTemplateSpecializationArgs(*T); + } + OS << "}"; + if (R.Qualifier) { + OS << ", qualifier = '"; + R.Qualifier.getNestedNameSpecifier()->print(OS, + PrintingPolicy(LangOptions())); + OS << "'"; + } + return OS; +} + } // namespace clangd } // namespace clang Index: clang-tools-extra/trunk/clangd/unittests/FindTargetTests.cpp =================================================================== --- clang-tools-extra/trunk/clangd/unittests/FindTargetTests.cpp +++ clang-tools-extra/trunk/clangd/unittests/FindTargetTests.cpp @@ -9,6 +9,9 @@ #include "Selection.h" #include "TestTU.h" +#include "clang/AST/Decl.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Testing/Support/Annotations.h" #include "gmock/gmock.h" @@ -464,6 +467,223 @@ EXPECT_DECLS("ObjCObjectTypeLoc"); } +class FindExplicitReferencesTest : public ::testing::Test { +protected: + struct AllRefs { + std::string AnnotatedCode; + std::string DumpedReferences; + }; + + /// Parses \p Code, finds function '::foo' and annotates its body with results + /// of findExplicitReferecnces. + /// See actual tests for examples of annotation format. + AllRefs annotateReferencesInFoo(llvm::StringRef Code) { + TestTU TU; + TU.Code = Code; + + auto AST = TU.build(); + auto &Func = llvm::cast(findDecl(AST, "foo")); + + std::vector Refs; + findExplicitReferences(Func.getBody(), [&Refs](ReferenceLoc R) { + Refs.push_back(std::move(R)); + }); + + auto &SM = AST.getSourceManager(); + llvm::sort(Refs, [&](const ReferenceLoc &L, const ReferenceLoc &R) { + return SM.isBeforeInTranslationUnit(L.NameLoc, R.NameLoc); + }); + + std::string AnnotatedCode; + unsigned NextCodeChar = 0; + for (unsigned I = 0; I < Refs.size(); ++I) { + auto &R = Refs[I]; + + SourceLocation Pos = R.NameLoc; + assert(Pos.isValid()); + if (Pos.isMacroID()) // FIXME: figure out how to show macro locations. + Pos = SM.getExpansionLoc(Pos); + assert(Pos.isFileID()); + + FileID File; + unsigned Offset; + std::tie(File, Offset) = SM.getDecomposedLoc(Pos); + if (File == SM.getMainFileID()) { + // Print the reference in a source code. + assert(NextCodeChar <= Offset); + AnnotatedCode += Code.substr(NextCodeChar, Offset - NextCodeChar); + AnnotatedCode += "$" + std::to_string(I) + "^"; + + NextCodeChar = Offset; + } + } + AnnotatedCode += Code.substr(NextCodeChar); + + std::string DumpedReferences; + for (unsigned I = 0; I < Refs.size(); ++I) + DumpedReferences += llvm::formatv("{0}: {1}\n", I, Refs[I]); + + return AllRefs{std::move(AnnotatedCode), std::move(DumpedReferences)}; + } +}; + +TEST_F(FindExplicitReferencesTest, All) { + std::pair Cases[] = + { + // Simple expressions. + {R"cpp( + int global; + int func(); + void foo(int param) { + $0^global = $1^param + $2^func(); + } + )cpp", + "0: targets = {global}\n" + "1: targets = {param}\n" + "2: targets = {func}\n"}, + {R"cpp( + struct X { int a; }; + void foo(X x) { + $0^x.$1^a = 10; + } + )cpp", + "0: targets = {x}\n" + "1: targets = {X::a}\n"}, + // Namespaces and aliases. + {R"cpp( + namespace ns {} + namespace alias = ns; + void foo() { + using namespace $0^ns; + using namespace $1^alias; + } + )cpp", + "0: targets = {ns}\n" + "1: targets = {alias}\n"}, + // Using declarations. + {R"cpp( + namespace ns { int global; } + void foo() { + using $0^ns::$1^global; + } + )cpp", + "0: targets = {ns}\n" + "1: targets = {ns::global}, qualifier = 'ns::'\n"}, + // Simple types. + {R"cpp( + struct Struct { int a; }; + using Typedef = int; + void foo() { + $0^Struct x; + $1^Typedef y; + static_cast<$2^Struct*>(0); + } + )cpp", + "0: targets = {Struct}\n" + "1: targets = {Typedef}\n" + "2: targets = {Struct}\n"}, + // Name qualifiers. + {R"cpp( + namespace a { namespace b { struct S { typedef int type; }; } } + void foo() { + $0^a::$1^b::$2^S x; + using namespace $3^a::$4^b; + $5^S::$6^type y; + } + )cpp", + "0: targets = {a}\n" + "1: targets = {a::b}, qualifier = 'a::'\n" + "2: targets = {a::b::S}, qualifier = 'a::b::'\n" + "3: targets = {a}\n" + "4: targets = {a::b}, qualifier = 'a::'\n" + "5: targets = {a::b::S}\n" + "6: targets = {a::b::S::type}, qualifier = 'struct S::'\n"}, + // Simple templates. + {R"cpp( + template struct vector { using value_type = T; }; + template <> struct vector { using value_type = bool; }; + void foo() { + $0^vector vi; + $1^vector vb; + } + )cpp", + "0: targets = {vector}\n" + "1: targets = {vector}\n"}, + // FIXME: Fix 'allTargetDecls' to return alias template and re-enable. + // Template type aliases. + // {R"cpp( + // template struct vector { using value_type = T; }; + // template <> struct vector { using value_type = bool; }; + // template using valias = vector; + // void foo() { + // $0^valias vi; + // $1^valias vb; + // } + // )cpp", + // "0: targets = {valias}\n" + // "1: targets = {valias}\n"}, + + // MemberExpr should know their using declaration. + {R"cpp( + struct X { void func(int); } + struct Y : X { + using X::func; + }; + void foo(Y y) { + $0^y.$1^func(1); + } + )cpp", + "0: targets = {y}\n" + "1: targets = {Y::func}\n"}, + // DeclRefExpr should know their using declaration. + {R"cpp( + namespace ns { void bar(int); } + using ns::bar; + + void foo() { + $0^bar(10); + } + )cpp", + "0: targets = {bar}\n"}, + // References from a macro. + {R"cpp( + #define FOO a + #define BAR b + + void foo(int a, int b) { + $0^FOO+$1^BAR; + } + )cpp", + "0: targets = {a}\n" + "1: targets = {b}\n"}, + // No references from implicit nodes. + {R"cpp( + struct vector { + int *begin(); + int *end(); + }; + + void foo() { + for (int x : $0^vector()) { + $1^x = 10; + } + } + )cpp", + "0: targets = {vector}\n" + "1: targets = {x}\n"}, + }; + + for (const auto &C : Cases) { + llvm::StringRef ExpectedCode = C.first; + llvm::StringRef ExpectedRefs = C.second; + + auto Actual = + annotateReferencesInFoo(llvm::Annotations(ExpectedCode).code()); + EXPECT_EQ(ExpectedCode, Actual.AnnotatedCode); + EXPECT_EQ(ExpectedRefs, Actual.DumpedReferences) << ExpectedCode; + } +} + } // namespace } // namespace clangd } // namespace clang