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