clang-tools-extra/clangd/FindTarget.h

   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