| 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 |
namespace clangd { |
| 37 |
class HeuristicResolver; |
| 38 |
|
| 39 |
/// Describes the link between an AST node and a Decl it refers to. |
| 40 |
enum class DeclRelation : unsigned; |
| 41 |
/// A bitfield of DeclRelations. |
| 42 |
class DeclRelationSet; |
| 43 |
|
| 44 |
/// targetDecl() finds the declaration referred to by an AST node. |
| 45 |
/// For example a RecordTypeLoc refers to the RecordDecl for the type. |
| 46 |
/// |
| 47 |
/// In some cases there are multiple results, e.g. a dependent unresolved |
| 48 |
/// OverloadExpr may have several candidates. All will be returned: |
| 49 |
/// |
| 50 |
/// void foo(int); <-- candidate |
| 51 |
/// void foo(double); <-- candidate |
| 52 |
/// template <typename T> callFoo() { foo(T()); } |
| 53 |
/// ^ OverloadExpr |
| 54 |
/// |
| 55 |
/// In other cases, there may be choices about what "referred to" means. |
| 56 |
/// e.g. does naming a typedef refer to the underlying type? |
| 57 |
/// The results are marked with a set of DeclRelations, and can be filtered. |
| 58 |
/// |
| 59 |
/// struct S{}; <-- candidate (underlying) |
| 60 |
/// using T = S{}; <-- candidate (alias) |
| 61 |
/// T x; |
| 62 |
/// ^ TypedefTypeLoc |
| 63 |
/// |
| 64 |
/// Formally, we walk a graph starting at the provided node, and return the |
| 65 |
/// decls that were found. Certain edges in the graph have labels, and for each |
| 66 |
/// decl we return the set of labels seen on a path to the decl. |
| 67 |
/// For the previous example: |
| 68 |
/// |
| 69 |
/// TypedefTypeLoc T |
| 70 |
/// | |
| 71 |
/// TypedefType T |
| 72 |
/// / \ |
| 73 |
/// [underlying] [alias] |
| 74 |
/// / \ |
| 75 |
/// RecordDecl S TypeAliasDecl T |
| 76 |
/// |
| 77 |
/// Note that this function only returns NamedDecls. Generally other decls |
| 78 |
/// don't have references in this sense, just the node itself. |
| 79 |
/// If callers want to support such decls, they should cast the node directly. |
| 80 |
/// |
| 81 |
/// FIXME: some AST nodes cannot be DynTypedNodes, these cannot be specified. |
| 82 |
llvm::SmallVector<const NamedDecl *, 1> |
| 83 |
targetDecl(const DynTypedNode &, DeclRelationSet Mask, |
| 84 |
const HeuristicResolver *Resolver); |
| 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 DynTypedNode &, const HeuristicResolver *); |
| 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 |
const HeuristicResolver *Resolver); |
| 151 |
void findExplicitReferences(const Decl *D, |
| 152 |
llvm::function_ref<void(ReferenceLoc)> Out, |
| 153 |
const HeuristicResolver *Resolver); |
| 154 |
void findExplicitReferences(const ASTContext &AST, |
| 155 |
llvm::function_ref<void(ReferenceLoc)> Out, |
| 156 |
const HeuristicResolver *Resolver); |
| 157 |
|
| 158 |
/// Find declarations explicitly referenced in the source code defined by \p N. |
| 159 |
/// For templates, will prefer to return a template instantiation whenever |
| 160 |
/// possible. However, can also return a template pattern if the specialization |
| 161 |
/// cannot be picked, e.g. in dependent code or when there is no corresponding |
| 162 |
/// Decl for a template instantiation, e.g. for templated using decls: |
| 163 |
/// template <class T> using Ptr = T*; |
| 164 |
/// Ptr<int> x; |
| 165 |
/// ^~~ there is no Decl for 'Ptr<int>', so we return the template pattern. |
| 166 |
/// \p Mask should not contain TemplatePattern or TemplateInstantiation. |
| 167 |
llvm::SmallVector<const NamedDecl *, 1> |
| 168 |
explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask, |
| 169 |
const HeuristicResolver *Resolver); |
| 170 |
|
| 171 |
// Boring implementation details of bitfield. |
| 172 |
|
| 173 |
class DeclRelationSet { |
| 174 |
using Set = std::bitset<static_cast<unsigned>(DeclRelation::Underlying) + 1>; |
| 175 |
Set S; |
| 176 |
DeclRelationSet(Set S) : S(S) {} |
| 177 |
|
| 178 |
public: |
| 179 |
DeclRelationSet() = default; |
| 180 |
DeclRelationSet(DeclRelation R) { S.set(static_cast<unsigned>(R)); } |
| 181 |
|
| 182 |
explicit operator bool() const { return S.any(); } |
| 183 |
friend DeclRelationSet operator&(DeclRelationSet L, DeclRelationSet R) { |
| 184 |
return L.S & R.S; |
| 185 |
} |
| 186 |
friend DeclRelationSet operator|(DeclRelationSet L, DeclRelationSet R) { |
| 187 |
return L.S | R.S; |
| 188 |
} |
| 189 |
friend bool operator==(DeclRelationSet L, DeclRelationSet R) { |
| 190 |
return L.S == R.S; |
| 191 |
} |
| 192 |
friend DeclRelationSet operator~(DeclRelationSet R) { return ~R.S; } |
| 193 |
DeclRelationSet &operator|=(DeclRelationSet Other) { |
| 194 |
S |= Other.S; |
| 195 |
return *this; |
| 196 |
} |
| 197 |
DeclRelationSet &operator&=(DeclRelationSet Other) { |
| 198 |
S &= Other.S; |
| 199 |
return *this; |
| 200 |
} |
| 201 |
bool contains(DeclRelationSet Other) const { |
| 202 |
return (S & Other.S) == Other.S; |
| 203 |
} |
| 204 |
friend llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); |
| 205 |
}; |
| 206 |
// The above operators can't be looked up if both sides are enums. |
| 207 |
// over.match.oper.html#3.2 |
| 208 |
inline DeclRelationSet operator|(DeclRelation L, DeclRelation R) { |
| 209 |
return DeclRelationSet(L) | DeclRelationSet(R); |
| 210 |
} |
| 211 |
inline DeclRelationSet operator&(DeclRelation L, DeclRelation R) { |
| 212 |
return DeclRelationSet(L) & DeclRelationSet(R); |
| 213 |
} |
| 214 |
inline DeclRelationSet operator~(DeclRelation R) { return ~DeclRelationSet(R); } |
| 215 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet); |
| 216 |
|
| 217 |
} // namespace clangd |
| 218 |
} // namespace clang |
| 219 |
|
| 220 |
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDTARGET_H |