sammccall updated this revision to Diff 217576. sammccall marked an inline comment as done. sammccall added a comment.
use llvm::Annotations Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D66751/new/ https://reviews.llvm.org/D66751 Files: clang-tools-extra/clangd/CMakeLists.txt clang-tools-extra/clangd/FindTarget.cpp clang-tools-extra/clangd/FindTarget.h clang-tools-extra/clangd/unittests/ASTTests.cpp clang-tools-extra/clangd/unittests/CMakeLists.txt clang-tools-extra/clangd/unittests/FindTargetTests.cpp
Index: clang-tools-extra/clangd/unittests/FindTargetTests.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/unittests/FindTargetTests.cpp @@ -0,0 +1,468 @@ +//===-- FindSymbolsTests.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 "FindTarget.h" + +#include "Selection.h" +#include "TestTU.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Testing/Support/Annotations.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include <initializer_list> + +namespace clang { +namespace clangd { +namespace { + +// A referenced Decl together with its DeclRelationSet, for assertions. +// +// There's no great way to assert on the "content" of a Decl in the general case +// that's both expressive and unambiguous (e.g. clearly distinguishes between +// templated decls and their specializations). +// +// We use the result of pretty-printing the decl, with the {body} truncated. +struct PrintedDecl { + PrintedDecl(const char *Name, DeclRelationSet Relations = {}) + : Name(Name), Relations(Relations) {} + PrintedDecl(const Decl *D, DeclRelationSet Relations = {}) + : Relations(Relations) { + std::string S; + llvm::raw_string_ostream OS(S); + D->print(OS); + llvm::StringRef FirstLine = + llvm::StringRef(OS.str()).take_until([](char C) { return C == '\n'; }); + FirstLine = FirstLine.rtrim(" {"); + Name = FirstLine.rtrim(" {"); + } + + std::string Name; + DeclRelationSet Relations; +}; +bool operator==(const PrintedDecl &L, const PrintedDecl &R) { + return std::tie(L.Name, L.Relations) == std::tie(R.Name, R.Relations); +} +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const PrintedDecl &D) { + return OS << D.Name << " Rel=" << D.Relations; +} + +// The test cases in for targetDecl() take the form +// - a piece of code (Code = "...") +// - Code should have a single AST node marked as a [[range]] +// - an EXPECT_DECLS() assertion that verify the type of node selected, and +// all the decls that targetDecl() considers it to reference +// Despite the name, these cases actually test allTargetDecls() for brevity. +class TargetDeclTest : public ::testing::Test { +protected: + using Rel = DeclRelation; + std::string Code; + std::vector<const char *> Flags; + + // Asserts that `Code` has a marked selection of a node `NodeType`, + // and returns allTargetDecls() as PrintedDecl structs. + // Use via EXPECT_DECLS(). + std::vector<PrintedDecl> assertNodeAndPrintDecls(const char *NodeType) { + llvm::Annotations A(Code); + auto TU = TestTU::withCode(A.code()); + TU.ExtraArgs = Flags; + auto AST = TU.build(); + EXPECT_THAT(AST.getDiagnostics(), ::testing::IsEmpty()) << Code; + llvm::Annotations::Range R = A.range(); + SelectionTree Selection(AST.getASTContext(), AST.getTokens(), R.Begin, + R.End); + const SelectionTree::Node *N = Selection.commonAncestor(); + if (!N) { + ADD_FAILURE() << "No node selected!\n" << Code; + return {}; + } + EXPECT_EQ(N->kind(), NodeType) << Selection; + + std::vector<PrintedDecl> ActualDecls; + for (const auto &Entry : allTargetDecls(N->ASTNode)) + ActualDecls.emplace_back(Entry.first, Entry.second); + return ActualDecls; + } +}; + +// This is a macro to preserve line numbers in assertion failures. +// It takes the expected decls as varargs to work around comma-in-macro issues. +#define EXPECT_DECLS(NodeType, ...) \ + EXPECT_THAT(assertNodeAndPrintDecls(NodeType), \ + ::testing::UnorderedElementsAreArray( \ + std::vector<PrintedDecl>({__VA_ARGS__}))) \ + << Code +using ExpectedDecls = std::vector<PrintedDecl>; + +TEST_F(TargetDeclTest, Exprs) { + Code = R"cpp( + int f(); + int x = [[f]](); + )cpp"; + EXPECT_DECLS("DeclRefExpr", "int f()"); + + Code = R"cpp( + struct S { S operator+(S) const; }; + auto X = S() [[+]] S(); + )cpp"; + EXPECT_DECLS("DeclRefExpr", "S operator+(S) const"); +} + +TEST_F(TargetDeclTest, UsingDecl) { + Code = R"cpp( + namespace foo { + int f(int); + int f(char); + } + using foo::f; + int x = [[f]](42); + )cpp"; + // f(char) is not referenced! + EXPECT_DECLS("DeclRefExpr", {"using foo::f", Rel::Alias}, + {"int f(int)", Rel::Underlying}); + + Code = R"cpp( + namespace foo { + int f(int); + int f(char); + } + [[using foo::f]]; + )cpp"; + // All overloads are referenced. + EXPECT_DECLS("UsingDecl", {"using foo::f", Rel::Alias}, + {"int f(int)", Rel::Underlying}, + {"int f(char)", Rel::Underlying}); + + Code = R"cpp( + struct X { + int foo(); + }; + struct Y : X { + using X::foo; + }; + int x = Y().[[foo]](); + )cpp"; + EXPECT_DECLS("MemberExpr", {"using X::foo", Rel::Alias}, + {"int foo()", Rel::Underlying}); +} + +TEST_F(TargetDeclTest, ConstructorInitList) { + Code = R"cpp( + struct X { + int a; + X() : [[a]](42) {} + }; + )cpp"; + EXPECT_DECLS("CXXCtorInitializer", "int a"); + + Code = R"cpp( + struct X { + X() : [[X]](1) {} + X(int); + }; + )cpp"; + EXPECT_DECLS("RecordTypeLoc", "struct X"); +} + +TEST_F(TargetDeclTest, DesignatedInit) { + Code = R"cpp( + struct X { int a; }; + struct Y { int b; X c[2]; }; + Y y = { .c[0].[[a]] = 1 }; + )cpp"; + EXPECT_DECLS("DesignatedInitExpr", "int a"); +} + +TEST_F(TargetDeclTest, NestedNameSpecifier) { + Code = R"cpp( + namespace a { namespace b { int c; } } + int x = a::[[b::]]c; + )cpp"; + EXPECT_DECLS("NestedNameSpecifierLoc", "namespace b"); + + Code = R"cpp( + namespace a { struct X { enum { y }; }; } + int x = a::[[X::]]y; + )cpp"; + EXPECT_DECLS("NestedNameSpecifierLoc", "struct X"); + + Code = R"cpp( + template <typename T> + int x = [[T::]]y; + )cpp"; + // FIXME: We don't do a good job printing TemplateTypeParmDecls, apparently! + EXPECT_DECLS("NestedNameSpecifierLoc", ""); + + Code = R"cpp( + namespace a { int x; } + namespace b = a; + int y = [[b]]::x; + )cpp"; + EXPECT_DECLS("NestedNameSpecifierLoc", {"namespace b = a", Rel::Alias}, + {"namespace a", Rel::Underlying}); +} + +TEST_F(TargetDeclTest, Types) { + Code = R"cpp( + struct X{}; + [[X]] x; + )cpp"; + EXPECT_DECLS("RecordTypeLoc", "struct X"); + + Code = R"cpp( + struct S{}; + typedef S X; + [[X]] x; + )cpp"; + EXPECT_DECLS("TypedefTypeLoc", {"typedef S X", Rel::Alias}, + {"struct S", Rel::Underlying}); + + Code = R"cpp( + template<class T> + void foo() { [[T]] x; } + )cpp"; + // FIXME: We don't do a good job printing TemplateTypeParmDecls, apparently! + EXPECT_DECLS("TemplateTypeParmTypeLoc", ""); + + Code = R"cpp( + template<template<typename> class T> + void foo() { [[T<int>]] x; } + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", "template <typename> class T"); + + Code = R"cpp( + struct S{}; + S X; + [[decltype]](X) Y; + )cpp"; + EXPECT_DECLS("DecltypeTypeLoc", {"struct S", Rel::Underlying}); + + Code = R"cpp( + struct S{}; + [[auto]] X = S{}; + )cpp"; + // FIXME: deduced type missing in AST. https://llvm.org/PR42914 + EXPECT_DECLS("AutoTypeLoc"); +} + +TEST_F(TargetDeclTest, ClassTemplate) { + Code = R"cpp( + // Implicit specialization. + template<int x> class Foo{}; + [[Foo<42>]] B; + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", + {"template<> class Foo<42>", Rel::TemplateInstantiation}, + {"class Foo", Rel::TemplatePattern}); + + Code = R"cpp( + // Explicit specialization. + template<int x> class Foo{}; + template<> class Foo<42>{}; + [[Foo<42>]] B; + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", "template<> class Foo<42>"); + + Code = R"cpp( + // Partial specialization. + template<typename T> class Foo{}; + template<typename T> class Foo<T*>{}; + [[Foo<int*>]] B; + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", + {"template<> class Foo<int *>", Rel::TemplateInstantiation}, + {"template <typename T> class Foo<type-parameter-0-0 *>", + Rel::TemplatePattern}); +} + +TEST_F(TargetDeclTest, FunctionTemplate) { + Code = R"cpp( + // Implicit specialization. + template<typename T> bool foo(T) { return false; }; + bool x = [[foo]](42); + )cpp"; + EXPECT_DECLS("DeclRefExpr", + {"template<> bool foo<int>(int)", Rel::TemplateInstantiation}, + {"bool foo(T)", Rel::TemplatePattern}); + + Code = R"cpp( + // Explicit specialization. + template<typename T> bool foo(T) { return false; }; + template<> bool foo<int>(int) { return false; }; + bool x = [[foo]](42); + )cpp"; + EXPECT_DECLS("DeclRefExpr", "template<> bool foo<int>(int)"); +} + +TEST_F(TargetDeclTest, VariableTemplate) { + // Pretty-printer doesn't do a very good job of variable templates :-( + Code = R"cpp( + // Implicit specialization. + template<typename T> int foo; + int x = [[foo]]<char>; + )cpp"; + EXPECT_DECLS("DeclRefExpr", {"int foo", Rel::TemplateInstantiation}, + {"int foo", Rel::TemplatePattern}); + + Code = R"cpp( + // Explicit specialization. + template<typename T> int foo; + template <> bool foo<char>; + int x = [[foo]]<char>; + )cpp"; + EXPECT_DECLS("DeclRefExpr", "bool foo"); + + Code = R"cpp( + // Partial specialization. + template<typename T> int foo; + template<typename T> bool foo<T*>; + bool x = [[foo]]<char*>; + )cpp"; + EXPECT_DECLS("DeclRefExpr", {"bool foo", Rel::TemplateInstantiation}, + {"bool foo", Rel::TemplatePattern}); +} + +TEST_F(TargetDeclTest, TypeAliasTemplate) { + Code = R"cpp( + template<typename T, int X> class SmallVector {}; + template<typename U> using TinyVector = SmallVector<U, 1>; + [[TinyVector<int>]] X; + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", + {"template<> class SmallVector<int, 1>", + Rel::TemplateInstantiation | Rel::Underlying}, + {"class SmallVector", Rel::TemplatePattern | Rel::Underlying}, + {"using TinyVector = SmallVector<U, 1>", + Rel::Alias | Rel::TemplatePattern}); +} + +TEST_F(TargetDeclTest, MemberOfTemplate) { + Code = R"cpp( + template <typename T> struct Foo { + int x(T); + }; + int y = Foo<int>().[[x]](42); + )cpp"; + EXPECT_DECLS("MemberExpr", {"int x(int)", Rel::TemplateInstantiation}, + {"int x(T)", Rel::TemplatePattern}); + + Code = R"cpp( + template <typename T> struct Foo { + template <typename U> + int x(T, U); + }; + int y = Foo<char>().[[x]]('c', 42); + )cpp"; + EXPECT_DECLS("MemberExpr", + {"template<> int x<int>(char, int)", Rel::TemplateInstantiation}, + {"int x(T, U)", Rel::TemplatePattern}); +} + +TEST_F(TargetDeclTest, Lambda) { + Code = R"cpp( + void foo(int x = 42) { + auto l = [ [[x]] ]{ return x + 1; }; + }; + )cpp"; + EXPECT_DECLS("DeclRefExpr", "int x = 42"); + + // It seems like this should refer to another var, with the outer param being + // an underlying decl. But it doesn't seem to exist. + Code = R"cpp( + void foo(int x = 42) { + auto l = [x]{ return [[x]] + 1; }; + }; + )cpp"; + EXPECT_DECLS("DeclRefExpr", "int x = 42"); + + Code = R"cpp( + void foo() { + auto l = [x = 1]{ return [[x]] + 1; }; + }; + )cpp"; + // FIXME: why both auto and int? + EXPECT_DECLS("DeclRefExpr", "auto int x = 1"); +} + +TEST_F(TargetDeclTest, ObjC) { + Flags = {"-xobjective-c"}; + Code = R"cpp( + @interface Foo {} + -(void)bar; + @end + void test(Foo *f) { + [f [[bar]] ]; + } + )cpp"; + EXPECT_DECLS("ObjCMessageExpr", "- (void)bar"); + + Code = R"cpp( + @interface Foo { @public int bar; } + @end + int test(Foo *f) { + return [[f->bar]]; + } + )cpp"; + EXPECT_DECLS("ObjCIvarRefExpr", "int bar"); + + Code = R"cpp( + @interface Foo {} + -(int) x; + -(void) setX:(int)x; + @end + void test(Foo *f) { + [[f.x]] = 42; + } + )cpp"; + EXPECT_DECLS("ObjCPropertyRefExpr", "- (void)setX:(int)x"); + + Code = R"cpp( + @interface Foo {} + @property int x; + @end + void test(Foo *f) { + [[f.x]] = 42; + } + )cpp"; + EXPECT_DECLS("ObjCPropertyRefExpr", + "@property(atomic, assign, unsafe_unretained, readwrite) int x"); + + Code = R"cpp( + @protocol Foo + @end + id test() { + return [[@protocol(Foo)]]; + } + )cpp"; + EXPECT_DECLS("ObjCProtocolExpr", "@protocol Foo"); + + Code = R"cpp( + @interface Foo + @end + void test([[Foo]] *p); + )cpp"; + EXPECT_DECLS("ObjCInterfaceTypeLoc", "@interface Foo"); + + Code = R"cpp( + @protocol Foo + @end + void test([[id<Foo>]] p); + )cpp"; + EXPECT_DECLS("ObjCObjectTypeLoc", "@protocol Foo"); + + Code = R"cpp( + @class C; + @protocol Foo + @end + void test(C<[[Foo]]> *p); + )cpp"; + // FIXME: there's no AST node corresponding to 'Foo', so we're stuck. + EXPECT_DECLS("ObjCObjectTypeLoc"); +} + +} // namespace +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/unittests/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/unittests/CMakeLists.txt +++ clang-tools-extra/clangd/unittests/CMakeLists.txt @@ -39,6 +39,7 @@ FileDistanceTests.cpp FileIndexTests.cpp FindSymbolsTests.cpp + FindTargetTests.cpp FormattedStringTests.cpp FormatTests.cpp FSTests.cpp Index: clang-tools-extra/clangd/unittests/ASTTests.cpp =================================================================== --- clang-tools-extra/clangd/unittests/ASTTests.cpp +++ clang-tools-extra/clangd/unittests/ASTTests.cpp @@ -36,7 +36,6 @@ "testns1::TestClass<testns1::OtherClass>", "testns1")); } - } // namespace } // namespace clangd } // namespace clang Index: clang-tools-extra/clangd/FindTarget.h =================================================================== --- /dev/null +++ clang-tools-extra/clangd/FindTarget.h @@ -0,0 +1,144 @@ +//===--- FindTarget.h - What does an AST node refer to? ---------*- 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 +// +//===----------------------------------------------------------------------===// +// +// Many clangd features are concerned with references in the AST: +// - xrefs, go-to-definition, explicitly talk about references +// - hover and code actions relate to things you "target" in the editor +// - refactoring actions need to know about entities that are referenced +// to determine whether/how the edit can be applied. +// +// Historically, we have used libIndex (IndexDataConsumer) to tie source +// locations to referenced declarations. This file defines a more decoupled +// approach based around AST nodes (DynTypedNode), and can be combined with +// SelectionTree or other traversals. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/ASTTypeTraits.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/SmallPtrSet.h" + +#include <bitset> + +namespace clang { +namespace clangd { +/// Describes the link between an AST node and a Decl it refers to. +enum class DeclRelation : unsigned; +/// A bitfield of DeclRelations. +class DeclRelationSet; + +/// targetDecl() finds the declaration referred to by an AST node. +/// For example a RecordTypeLoc refers to the RecordDecl for the type. +/// +/// In some cases there are multiple results, e.g. a dependent unresolved +/// OverloadExpr may have several candidates. All will be returned: +/// +/// void foo(int); <-- candidate +/// void foo(double); <-- candidate +/// template <typename T> callFoo() { foo(T()); } +/// ^ OverloadExpr +/// +/// In other cases, there may be choices about what "referred to" means. +/// e.g. does naming a typedef refer to the underlying type? +/// The results are marked with a set of DeclRelations, and can be filtered. +/// +/// struct S{}; <-- candidate (underlying) +/// using T = S{}; <-- candidate (alias) +/// T x; +/// ^ TypedefTypeLoc +/// +/// Formally, we walk a graph starting at the provided node, and return the +/// decls that were found. Certain edges in the graph have labels, and for each +/// decl we return the set of labels seen on a path to the decl. +/// For the previous example: +/// +/// TypedefTypeLoc T +/// | +/// TypedefType T +/// / \ +/// [underlying] [alias] +/// / \ +/// RecordDecl S TypeAliasDecl T +/// +/// FIXME: some AST nodes cannot be DynTypedNodes, these cannot be specified. +llvm::SmallVector<const Decl *, 1> +targetDecl(const ast_type_traits::DynTypedNode &, DeclRelationSet Mask); + +/// 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 +/// is applied later. +llvm::SmallVector<std::pair<const Decl *, DeclRelationSet>, 1> +allTargetDecls(const ast_type_traits::DynTypedNode &); + +enum class DeclRelation : unsigned { + // Template options apply when the declaration is an instantiated template. + // e.g. [[vector<int>]] vec; + + /// This is the template instantiation that was referred to. + /// e.g. template<> class vector<int> (the implicit specialization) + TemplateInstantiation, + /// This is the pattern the template specialization was instantiated from. + /// e.g. class vector<T> (the pattern within the primary template) + TemplatePattern, + + // Alias options apply when the declaration is an alias. + // e.g. namespace clang { [[StringRef]] S; } + + /// This declaration is an alias that was referred to. + /// e.g. using llvm::StringRef (the UsingDecl directly referenced). + Alias, + /// This is the underlying declaration for an alias, decltype etc. + /// e.g. class llvm::StringRef (the underlying declaration referenced). + Underlying, +}; +llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelation); + +class DeclRelationSet { + using Set = std::bitset<static_cast<unsigned>(DeclRelation::Underlying) + 1>; + Set S; + DeclRelationSet(Set S) : S(S) {} + +public: + DeclRelationSet() = default; + DeclRelationSet(DeclRelation R) { S.set(static_cast<unsigned>(R)); } + + explicit operator bool() const { return S.any(); } + friend DeclRelationSet operator&(DeclRelationSet L, DeclRelationSet R) { + return L.S & R.S; + } + friend DeclRelationSet operator|(DeclRelationSet L, DeclRelationSet R) { + return L.S | R.S; + } + friend bool operator==(DeclRelationSet L, DeclRelationSet R) { + return L.S == R.S; + } + friend DeclRelationSet operator~(DeclRelationSet R) { return ~R.S; } + DeclRelationSet &operator|=(DeclRelationSet Other) { + S |= Other.S; + return *this; + } + DeclRelationSet &operator&=(DeclRelationSet Other) { + S &= Other.S; + return *this; + } + friend llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); +}; +// The above operators can't be looked up if both sides are enums. +// over.match.oper.html#3.2 +inline DeclRelationSet operator|(DeclRelation L, DeclRelation R) { + return DeclRelationSet(L) | DeclRelationSet(R); +} +inline DeclRelationSet operator&(DeclRelation L, DeclRelation R) { + return DeclRelationSet(L) & DeclRelationSet(R); +} +inline DeclRelationSet operator~(DeclRelation R) { return ~DeclRelationSet(R); } +llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); + +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/FindTarget.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/FindTarget.cpp @@ -0,0 +1,381 @@ +//===--- FindTarget.cpp - What does an AST node refer to? -----------------===// +// +// 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 "FindTarget.h" +#include "AST.h" +#include "Logger.h" +#include "clang/AST/ASTTypeTraits.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclTemplate.h" +#include "clang/AST/DeclVisitor.h" +#include "clang/AST/DeclarationName.h" +#include "clang/AST/ExprObjC.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/AST/Type.h" +#include "clang/AST/TypeLocVisitor.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { +namespace clangd { +namespace { + +LLVM_DUMP_METHOD std::string +nodeToString(const ast_type_traits::DynTypedNode &N) { + std::string S = N.getNodeKind().asStringRef(); + { + llvm::raw_string_ostream OS(S); + OS << ": "; + N.print(OS, PrintingPolicy(LangOptions())); + } + std::replace(S.begin(), S.end(), '\n', ' '); + return S; +} + +// TargetFinder locates the entities that an AST node refers to. +// +// Typically this is (possibly) one declaration and (possibly) one type, but +// may be more: +// - for ambiguous nodes like OverloadExpr +// - if we want to include e.g. both typedefs and the underlying type +// +// This is organized as a set of mutually recursive helpers for particular node +// types, but for most nodes this is a short walk rather than a deep traversal. +// +// It's tempting to do e.g. typedef resolution as a second normalization step, +// after finding the 'primary' decl etc. But we do this monolithically instead +// because: +// - normalization may require these traversals again (e.g. unwrapping a +// typedef reveals a decltype which must be traversed) +// - it doesn't simplify that much, e.g. the first stage must still be able +// to yield multiple decls to handle OverloadExpr +// - there are cases where it's required for correctness. e.g: +// template<class X> using pvec = vector<x*>; pvec<int> x; +// There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>` +// and both are lossy. We must know upfront what the caller ultimately wants. +// +// FIXME: improve common dependent scope using name lookup in primary templates. +// e.g. template<typename T> int foo() { return std::vector<T>().size(); } +// formally size() is unresolved, but the primary template is a good guess. +// This affects: +// - DependentTemplateSpecializationType, +// - DependentScopeMemberExpr +// - DependentScopeDeclRefExpr +// - DependentNameType +struct TargetFinder { + using RelSet = DeclRelationSet; + using Rel = DeclRelation; + llvm::SmallDenseMap<const Decl *, RelSet> Decls; + RelSet Flags; + + static const Decl *getTemplatePattern(const Decl *D) { + if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) { + return CRD->getTemplateInstantiationPattern(); + } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { + return FD->getTemplateInstantiationPattern(); + } else if (auto *VD = dyn_cast<VarDecl>(D)) { + // Hmm: getTIP returns its arg if it's not an instantiation?! + VarDecl *T = VD->getTemplateInstantiationPattern(); + return (T == D) ? nullptr : T; + } else if (const auto *ED = dyn_cast<EnumDecl>(D)) { + return ED->getInstantiatedFromMemberEnum(); + } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) { + const auto *ND = cast<NamedDecl>(D); + if (const DeclContext *Parent = dyn_cast_or_null<DeclContext>( + getTemplatePattern(llvm::cast<Decl>(ND->getDeclContext())))) + for (const NamedDecl *BaseND : Parent->lookup(ND->getDeclName())) + if (!BaseND->isImplicit() && BaseND->getKind() == ND->getKind()) + return BaseND; + } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) { + if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) { + if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) { + for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName())) + return BaseECD; + } + } + } + return nullptr; + } + + template <typename T> void debug(T &Node, RelSet Flags) { + dlog("visit [{0}] {1}", Flags, + nodeToString(ast_type_traits::DynTypedNode::create(Node))); + } + + void report(const Decl *D, RelSet Flags) { + dlog("--> [{0}] {1}", Flags, + nodeToString(ast_type_traits::DynTypedNode::create(*D))); + Decls[D] |= Flags; + } + +public: + void add(const Decl *D, RelSet Flags) { + if (!D) + return; + debug(*D, Flags); + if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D)) + D = UDD->getNominatedNamespaceAsWritten(); + + if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) { + add(TND->getUnderlyingType(), Flags | Rel::Underlying); + Flags |= Rel::Alias; // continue with the alias. + } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) { + for (const UsingShadowDecl *S : UD->shadows()) + add(S->getUnderlyingDecl(), Flags | Rel::Underlying); + Flags |= Rel::Alias; // continue with the alias. + } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) { + add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying); + Flags |= Rel::Alias; // continue with the alias + } else if (const UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D)) { + // Include the using decl, but don't traverse it. This may end up + // including *all* shadows, which we don't want. + report(USD->getUsingDecl(), Flags | Rel::Alias); + // Shadow decls are synthetic and not themselves interesting. + // Record the underlying decl instead, if allowed. + D = USD->getTargetDecl(); + Flags |= Rel::Underlying; // continue with the underlying decl. + } + + if (const Decl *Pat = getTemplatePattern(D)) { + assert(Pat != D); + add(Pat, Flags | Rel::TemplatePattern); + // Now continue with the instantiation. + Flags |= Rel::TemplateInstantiation; + } + + report(D, Flags); + } + + void add(const Stmt *S, RelSet Flags) { + if (!S) + return; + debug(*S, Flags); + struct Visitor : public ConstStmtVisitor<Visitor> { + TargetFinder &Outer; + RelSet Flags; + Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} + + void VisitDeclRefExpr(const DeclRefExpr *DRE) { + const Decl *D = DRE->getDecl(); + // UsingShadowDecl allows us to record the UsingDecl. + // getFoundDecl() returns the wrong thing in other cases (templates). + if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl())) + D = USD; + Outer.add(D, Flags); + } + void VisitMemberExpr(const MemberExpr *ME) { + const Decl *D = ME->getMemberDecl(); + if (auto *USD = + llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl())) + D = USD; + Outer.add(D, Flags); + } + void VisitCXXConstructExpr(const CXXConstructExpr *CCE) { + Outer.add(CCE->getConstructor(), Flags); + } + void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) { + for (const DesignatedInitExpr::Designator &D : + llvm::reverse(DIE->designators())) + if (D.isFieldDesignator()) { + Outer.add(D.getField(), Flags); + // We don't know which designator was intended, we assume the outer. + break; + } + } + void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) { + Outer.add(OIRE->getDecl(), Flags); + } + void VisitObjCMessageExpr(const ObjCMessageExpr *OME) { + Outer.add(OME->getMethodDecl(), Flags); + } + void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) { + if (OPRE->isExplicitProperty()) + Outer.add(OPRE->getExplicitProperty(), Flags); + else { + if (OPRE->isMessagingGetter()) + Outer.add(OPRE->getImplicitPropertyGetter(), Flags); + if (OPRE->isMessagingSetter()) + Outer.add(OPRE->getImplicitPropertySetter(), Flags); + } + } + void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) { + Outer.add(OPE->getProtocol(), Flags); + } + }; + Visitor(*this, Flags).Visit(S); + } + + void add(QualType T, RelSet Flags) { + if (T.isNull()) + return; + debug(T, Flags); + struct Visitor : public TypeVisitor<Visitor> { + TargetFinder &Outer; + RelSet Flags; + Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} + + void VisitTagType(const TagType *TT) { + Outer.add(TT->getAsTagDecl(), Flags); + } + void VisitDecltypeType(const DecltypeType *DTT) { + Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying); + } + void VisitDeducedType(const DeducedType *DT) { + // FIXME: In practice this doesn't work: the AutoType you find inside + // TypeLoc never has a deduced type. https://llvm.org/PR42914 + Outer.add(DT->getDeducedType(), Flags | Rel::Underlying); + } + void VisitTypedefType(const TypedefType *TT) { + Outer.add(TT->getDecl(), Flags); + } + void + VisitTemplateSpecializationType(const TemplateSpecializationType *TST) { + // Have to handle these case-by-case. + + // templated type aliases: there's no specialized/instantiated using + // decl to point to. So try to find a decl for the underlying type + // (after substitution), and failing that point to the (templated) using + // decl. + if (TST->isTypeAlias()) { + Outer.add(TST->getAliasedType(), Flags | Rel::Underlying); + // Don't *traverse* the alias, which would result in traversing the + // template of the underlying type. + Outer.report( + TST->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(), + Flags | Rel::Alias | Rel::TemplatePattern); + } + // specializations of template template parameters aren't instantiated + // into decls, so they must refer to the parameter itself. + else if (const auto *Parm = + llvm::dyn_cast_or_null<TemplateTemplateParmDecl>( + TST->getTemplateName().getAsTemplateDecl())) + Outer.add(Parm, Flags); + // class template specializations have a (specialized) CXXRecordDecl. + else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl()) + Outer.add(RD, Flags); // add(Decl) will despecialize if needed. + else { + // fallback: the (un-specialized) declaration from primary template. + if (auto *TD = TST->getTemplateName().getAsTemplateDecl()) + Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern); + } + } + void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) { + Outer.add(TTPT->getDecl(), Flags); + } + void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) { + Outer.add(OIT->getDecl(), Flags); + } + void VisitObjCObjectType(const ObjCObjectType *OOT) { + // FIXME: ObjCObjectTypeLoc has no children for the protocol list, so + // there is no node in id<Foo> that refers to ObjCProtocolDecl Foo. + if (OOT->isObjCQualifiedId() && OOT->getNumProtocols() == 1) + Outer.add(OOT->getProtocol(0), Flags); + } + }; + Visitor(*this, Flags).Visit(T.getTypePtr()); + } + + void add(const NestedNameSpecifier *NNS, RelSet Flags) { + if (!NNS) + return; + debug(*NNS, Flags); + switch (NNS->getKind()) { + case NestedNameSpecifier::Identifier: + return; + case NestedNameSpecifier::Namespace: + add(NNS->getAsNamespace(), Flags); + return; + case NestedNameSpecifier::NamespaceAlias: + add(NNS->getAsNamespaceAlias(), Flags); + return; + case NestedNameSpecifier::TypeSpec: + case NestedNameSpecifier::TypeSpecWithTemplate: + add(QualType(NNS->getAsType(), 0), Flags); + return; + case NestedNameSpecifier::Global: + // This should be TUDecl, but we can't get a pointer to it! + return; + case NestedNameSpecifier::Super: + add(NNS->getAsRecordDecl(), Flags); + return; + } + llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind"); + } + + void add(const CXXCtorInitializer *CCI, RelSet Flags) { + if (!CCI) + return; + debug(*CCI, Flags); + + if (CCI->isAnyMemberInitializer()) + add(CCI->getAnyMember(), Flags); + // Constructor calls contain a TypeLoc node, so we don't handle them here. + } +}; + +} // namespace + +llvm::SmallVector<std::pair<const Decl *, DeclRelationSet>, 1> +allTargetDecls(const ast_type_traits::DynTypedNode &N) { + dlog("allTargetDecls({0})", nodeToString(N)); + TargetFinder Finder; + DeclRelationSet Flags; + if (const Decl *D = N.get<Decl>()) + Finder.add(D, Flags); + else if (const Stmt *S = N.get<Stmt>()) + Finder.add(S, Flags); + else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>()) + Finder.add(NNSL->getNestedNameSpecifier(), Flags); + else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>()) + Finder.add(NNS, Flags); + else if (const TypeLoc *TL = N.get<TypeLoc>()) + Finder.add(TL->getType(), Flags); + else if (const QualType *QT = N.get<QualType>()) + Finder.add(*QT, Flags); + else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) + Finder.add(CCI, Flags); + + return {Finder.Decls.begin(), Finder.Decls.end()}; +} + +llvm::SmallVector<const Decl *, 1> +targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) { + llvm::SmallVector<const Decl *, 1> Result; + for (const auto &Entry : allTargetDecls(N)) + if (!(Entry.second & ~Mask)) + Result.push_back(Entry.first); + return Result; +} + +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) { + switch (R) { +#define REL_CASE(X) \ + case DeclRelation::X: \ + return OS << #X; + REL_CASE(Alias); + REL_CASE(Underlying); + REL_CASE(TemplateInstantiation); + REL_CASE(TemplatePattern); +#undef REL_CASE + }; +} +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) { + const char *Sep = ""; + for (unsigned I = 0; I < RS.S.size(); ++I) { + if (RS.S.test(I)) { + OS << Sep << static_cast<DeclRelation>(I); + Sep = "|"; + } + } + return OS; +} + +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/CMakeLists.txt +++ clang-tools-extra/clangd/CMakeLists.txt @@ -48,6 +48,7 @@ DraftStore.cpp ExpectedTypes.cpp FindSymbols.cpp + FindTarget.cpp FileDistance.cpp Format.cpp FS.cpp
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
