1 //===--- FindTarget.h - What does an AST node refer to? ---------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Many clangd features are concerned with references in the AST: 10 // - xrefs, go-to-definition, explicitly talk about references 11 // - hover and code actions relate to things you "target" in the editor 12 // - refactoring actions need to know about entities that are referenced 13 // to determine whether/how the edit can be applied. 14 // 15 // Historically, we have used libIndex (IndexDataConsumer) to tie source 16 // locations to referenced declarations. This file defines a more decoupled 17 // approach based around AST nodes (DynTypedNode), and can be combined with 18 // SelectionTree or other traversals. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #ifndef LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_FINDTARGET_H 23 #define LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_FINDTARGET_H 24 25 #include "clang/AST/ASTContext.h" 26 #include "clang/AST/ASTTypeTraits.h" 27 #include "clang/AST/NestedNameSpecifier.h" 28 #include "clang/AST/Stmt.h" 29 #include "clang/Basic/SourceLocation.h" 30 #include "llvm/ADT/Optional.h" 31 #include "llvm/ADT/STLExtras.h" 32 #include "llvm/ADT/SmallPtrSet.h" 33 #include "llvm/ADT/SmallVector.h" 34 #include "llvm/Support/raw_ostream.h" 35 36 #include <bitset> 37 38 namespace clang { 39 namespace clangd { 40 /// Describes the link between an AST node and a Decl it refers to. 41 enum class DeclRelation : unsigned; 42 /// A bitfield of DeclRelations. 43 class DeclRelationSet; 44 45 /// targetDecl() finds the declaration referred to by an AST node. 46 /// For example a RecordTypeLoc refers to the RecordDecl for the type. 47 /// 48 /// In some cases there are multiple results, e.g. a dependent unresolved 49 /// OverloadExpr may have several candidates. All will be returned: 50 /// 51 /// void foo(int); <-- candidate 52 /// void foo(double); <-- candidate 53 /// template <typename T> callFoo() { foo(T()); } 54 /// ^ OverloadExpr 55 /// 56 /// In other cases, there may be choices about what "referred to" means. 57 /// e.g. does naming a typedef refer to the underlying type? 58 /// The results are marked with a set of DeclRelations, and can be filtered. 59 /// 60 /// struct S{}; <-- candidate (underlying) 61 /// using T = S{}; <-- candidate (alias) 62 /// T x; 63 /// ^ TypedefTypeLoc 64 /// 65 /// Formally, we walk a graph starting at the provided node, and return the 66 /// decls that were found. Certain edges in the graph have labels, and for each 67 /// decl we return the set of labels seen on a path to the decl. 68 /// For the previous example: 69 /// 70 /// TypedefTypeLoc T 71 /// | 72 /// TypedefType T 73 /// / \ 74 /// [underlying] [alias] 75 /// / \ 76 /// RecordDecl S TypeAliasDecl T 77 /// 78 /// Note that this function only returns NamedDecls. Generally other decls 79 /// don't have references in this sense, just the node itself. 80 /// If callers want to support such decls, they should cast the node directly. 81 /// 82 /// FIXME: some AST nodes cannot be DynTypedNodes, these cannot be specified. 83 llvm::SmallVector<const NamedDecl *, 1> 84 targetDecl(const ast_type_traits::DynTypedNode &, DeclRelationSet Mask); 85 86 /// Similar to targetDecl(), however instead of applying a filter, all possible 87 /// decls are returned along with their DeclRelationSets. 88 /// This is suitable for indexing, where everything is recorded and filtering 89 /// is applied later. 90 llvm::SmallVector<std::pair<const NamedDecl *, DeclRelationSet>, 1> 91 allTargetDecls(const ast_type_traits::DynTypedNode &); 92 93 enum class DeclRelation : unsigned { 94 // Template options apply when the declaration is an instantiated template. 95 // e.g. [[vector<int>]] vec; 96 97 /// This is the template instantiation that was referred to. 98 /// e.g. template<> class vector<int> (the implicit specialization) 99 TemplateInstantiation, 100 /// This is the pattern the template specialization was instantiated from. 101 /// e.g. class vector<T> (the pattern within the primary template) 102 TemplatePattern, 103 104 // Alias options apply when the declaration is an alias. 105 // e.g. namespace client { [[X]] x; } 106 107 /// This declaration is an alias that was referred to. 108 /// e.g. using ns::X (the UsingDecl directly referenced), 109 /// using Z = ns::Y (the TypeAliasDecl directly referenced) 110 Alias, 111 /// This is the underlying declaration for a renaming-alias, decltype etc. 112 /// e.g. class ns::Y (the underlying declaration referenced). 113 /// 114 /// Note that we don't treat `using ns::X` as a first-class declaration like 115 /// `using Z = ns::Y`. Therefore reference to X that goes through this 116 /// using-decl is considered a direct reference (without the Underlying bit). 117 /// Nevertheless, we report `using ns::X` as an Alias, so that some features 118 /// like go-to-definition can still target it. 119 Underlying, 120 }; 121 llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelation); 122 123 /// Information about a reference written in the source code, independent of the 124 /// actual AST node that this reference lives in. 125 /// Useful for tools that are source-aware, e.g. refactorings. 126 struct ReferenceLoc { 127 /// Contains qualifier written in the code, if any, e.g. 'ns::' for 'ns::foo'. 128 NestedNameSpecifierLoc Qualifier; 129 /// Start location of the last name part, i.e. 'foo' in 'ns::foo<int>'. 130 SourceLocation NameLoc; 131 /// True if the reference is a declaration or definition; 132 bool IsDecl = false; 133 // FIXME: add info about template arguments. 134 /// A list of targets referenced by this name. Normally this has a single 135 /// element, but multiple is also possible, e.g. in case of using declarations 136 /// or unresolved overloaded functions. 137 /// For dependent and unresolved references, Targets can also be empty. 138 llvm::SmallVector<const NamedDecl *, 1> Targets; 139 }; 140 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R); 141 142 /// Recursively traverse \p S and report all references explicitly written in 143 /// the code. The main use-case is refactorings that need to process all 144 /// references in some subrange of the file and apply simple edits, e.g. add 145 /// qualifiers. 146 /// FIXME: currently this does not report references to overloaded operators. 147 /// FIXME: extend to report location information about declaration names too. 148 void findExplicitReferences(const Stmt *S, 149 llvm::function_ref<void(ReferenceLoc)> Out); 150 void findExplicitReferences(const Decl *D, 151 llvm::function_ref<void(ReferenceLoc)> Out); 152 void findExplicitReferences(const ASTContext &AST, 153 llvm::function_ref<void(ReferenceLoc)> Out); 154 155 /// Find declarations explicitly referenced in the source code defined by \p N. 156 /// For templates, will prefer to return a template instantiation whenever 157 /// possible. However, can also return a template pattern if the specialization 158 /// cannot be picked, e.g. in dependent code or when there is no corresponding 159 /// Decl for a template instantiation, e.g. for templated using decls: 160 /// template <class T> using Ptr = T*; 161 /// Ptr<int> x; 162 /// ^~~ there is no Decl for 'Ptr<int>', so we return the template pattern. 163 /// \p Mask should not contain TemplatePattern or TemplateInstantiation. 164 llvm::SmallVector<const NamedDecl *, 1> 165 explicitReferenceTargets(ast_type_traits::DynTypedNode N, 166 DeclRelationSet Mask); 167 168 // Boring implementation details of bitfield. 169 170 class DeclRelationSet { 171 using Set = std::bitset<static_cast<unsigned>(DeclRelation::Underlying) + 1>; 172 Set S; DeclRelationSet(Set S)173 DeclRelationSet(Set S) : S(S) {} 174 175 public: 176 DeclRelationSet() = default; DeclRelationSet(DeclRelation R)177 DeclRelationSet(DeclRelation R) { S.set(static_cast<unsigned>(R)); } 178 179 explicit operator bool() const { return S.any(); } 180 friend DeclRelationSet operator&(DeclRelationSet L, DeclRelationSet R) { 181 return L.S & R.S; 182 } 183 friend DeclRelationSet operator|(DeclRelationSet L, DeclRelationSet R) { 184 return L.S | R.S; 185 } 186 friend bool operator==(DeclRelationSet L, DeclRelationSet R) { 187 return L.S == R.S; 188 } 189 friend DeclRelationSet operator~(DeclRelationSet R) { return ~R.S; } 190 DeclRelationSet &operator|=(DeclRelationSet Other) { 191 S |= Other.S; 192 return *this; 193 } 194 DeclRelationSet &operator&=(DeclRelationSet Other) { 195 S &= Other.S; 196 return *this; 197 } 198 friend llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); 199 }; 200 // The above operators can't be looked up if both sides are enums. 201 // over.match.oper.html#3.2 202 inline DeclRelationSet operator|(DeclRelation L, DeclRelation R) { 203 return DeclRelationSet(L) | DeclRelationSet(R); 204 } 205 inline DeclRelationSet operator&(DeclRelation L, DeclRelation R) { 206 return DeclRelationSet(L) & DeclRelationSet(R); 207 } 208 inline DeclRelationSet operator~(DeclRelation R) { return ~DeclRelationSet(R); } 209 llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); 210 211 } // namespace clangd 212 } // namespace clang 213 214 #endif // LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_FINDTARGET_H 215