| 1 |
//===--- Selection.h - What's under the cursor? -------------------*-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 |
// Many features are triggered at locations/ranges and operate on AST nodes. |
| 9 |
// (e.g. go-to-definition or code tweaks). |
| 10 |
// At a high level, such features need to work out which node is the correct |
| 11 |
// target. |
| 12 |
// |
| 13 |
// There are a few levels of ambiguity here: |
| 14 |
// |
| 15 |
// Which tokens are included: |
| 16 |
// int x = one + two; // what should "go to definition" do? |
| 17 |
// ^^^^^^ |
| 18 |
// |
| 19 |
// Same token means multiple things: |
| 20 |
// string("foo") // class string, or a constructor? |
| 21 |
// ^ |
| 22 |
// |
| 23 |
// Which level of the AST is interesting? |
| 24 |
// if (err) { // reference to 'err', or operator bool(), |
| 25 |
// ^ // or the if statement itself? |
| 26 |
// |
| 27 |
// Here we build and expose a data structure that allows features to resolve |
| 28 |
// these ambiguities in an appropriate way: |
| 29 |
// - we determine which low-level nodes are partly or completely covered |
| 30 |
// by the selection. |
| 31 |
// - we expose a tree of the selected nodes and their lexical parents. |
| 32 |
// |
| 33 |
// Sadly LSP specifies locations as being between characters, and this causes |
| 34 |
// some ambiguities we cannot cleanly resolve: |
| 35 |
// lhs+rhs // targeting '+' or 'lhs'? |
| 36 |
// ^ // in GUI editors, double-clicking 'lhs' yields this position! |
| 37 |
// |
| 38 |
// The best we can do in these cases is try both, which leads to the awkward |
| 39 |
// SelectionTree::createEach() API. |
| 40 |
//===----------------------------------------------------------------------===// |
| 41 |
|
| 42 |
#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SELECTION_H |
| 43 |
#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SELECTION_H |
| 44 |
#include "clang/AST/ASTTypeTraits.h" |
| 45 |
#include "clang/AST/PrettyPrinter.h" |
| 46 |
#include "clang/Tooling/Syntax/Tokens.h" |
| 47 |
#include "llvm/ADT/SmallVector.h" |
| 48 |
|
| 49 |
namespace clang { |
| 50 |
namespace clangd { |
| 51 |
|
| 52 |
// A selection can partially or completely cover several AST nodes. |
| 53 |
// The SelectionTree contains nodes that are covered, and their parents. |
| 54 |
// SelectionTree does not contain all AST nodes, rather only: |
| 55 |
// Decl, Stmt, TypeLoc, NestedNamespaceSpecifierLoc, CXXCtorInitializer. |
| 56 |
// (These are the nodes with source ranges that fit in DynTypedNode). |
| 57 |
// |
| 58 |
// Usually commonAncestor() is the place to start: |
| 59 |
// - it's the simplest answer to "what node is under the cursor" |
| 60 |
// - the selected Expr (for example) can be found by walking up the parent |
| 61 |
// chain and checking Node->ASTNode. |
| 62 |
// - if you want to traverse the selected nodes, they are all under |
| 63 |
// commonAncestor() in the tree. |
| 64 |
// |
| 65 |
// SelectionTree tries to behave sensibly in the presence of macros, but does |
| 66 |
// not model any preprocessor concepts: the output is a subset of the AST. |
| 67 |
// When a macro argument is specifically selected, only its first expansion is |
| 68 |
// selected in the AST. (Returning a selection forest is unreasonably difficult |
| 69 |
// for callers to handle correctly.) |
| 70 |
// |
| 71 |
// Comments, directives and whitespace are completely ignored. |
| 72 |
// Semicolons are also ignored, as the AST generally does not model them well. |
| 73 |
// |
| 74 |
// The SelectionTree owns the Node structures, but the ASTNode attributes |
| 75 |
// point back into the AST it was constructed with. |
| 76 |
class SelectionTree { |
| 77 |
public: |
| 78 |
// Create selection trees for the given range, and pass them to Func. |
| 79 |
// |
| 80 |
// There may be multiple possible selection trees: |
| 81 |
// - if the range is empty and borders two tokens, a tree for the right token |
| 82 |
// and a tree for the left token will be yielded. |
| 83 |
// - Func should return true on success (stop) and false on failure (continue) |
| 84 |
// |
| 85 |
// Always yields at least one tree. If no tokens are touched, it is empty. |
| 86 |
static bool createEach(ASTContext &AST, const syntax::TokenBuffer &Tokens, |
| 87 |
unsigned Begin, unsigned End, |
| 88 |
llvm::function_ref<bool(SelectionTree)> Func); |
| 89 |
|
| 90 |
// Create a selection tree for the given range. |
| 91 |
// |
| 92 |
// Where ambiguous (range is empty and borders two tokens), prefer the token |
| 93 |
// on the right. |
| 94 |
static SelectionTree createRight(ASTContext &AST, |
| 95 |
const syntax::TokenBuffer &Tokens, |
| 96 |
unsigned Begin, unsigned End); |
| 97 |
|
| 98 |
// Copies are no good - contain pointers to other nodes. |
| 99 |
SelectionTree(const SelectionTree &) = delete; |
| 100 |
SelectionTree &operator=(const SelectionTree &) = delete; |
| 101 |
// Moves are OK though - internal storage is pointer-stable when moved. |
| 102 |
SelectionTree(SelectionTree &&) = default; |
| 103 |
SelectionTree &operator=(SelectionTree &&) = default; |
| 104 |
|
| 105 |
// Describes to what extent an AST node is covered by the selection. |
| 106 |
enum Selection : unsigned char { |
| 107 |
// The AST node owns no characters covered by the selection. |
| 108 |
// Note that characters owned by children don't count: |
| 109 |
// if (x == 0) scream(); |
| 110 |
// ^^^^^^ |
| 111 |
// The IfStmt would be Unselected because all the selected characters are |
| 112 |
// associated with its children. |
| 113 |
// (Invisible nodes like ImplicitCastExpr are always unselected). |
| 114 |
Unselected, |
| 115 |
// The AST node owns selected characters, but is not completely covered. |
| 116 |
Partial, |
| 117 |
// The AST node owns characters, and is covered by the selection. |
| 118 |
Complete, |
| 119 |
}; |
| 120 |
// An AST node that is implicated in the selection. |
| 121 |
// (Either selected directly, or some descendant is selected). |
| 122 |
struct Node { |
| 123 |
// The parent within the selection tree. nullptr for TranslationUnitDecl. |
| 124 |
Node *Parent; |
| 125 |
// Direct children within the selection tree. |
| 126 |
llvm::SmallVector<const Node *> Children; |
| 127 |
// The corresponding node from the full AST. |
| 128 |
DynTypedNode ASTNode; |
| 129 |
// The extent to which this node is covered by the selection. |
| 130 |
Selection Selected; |
| 131 |
// Walk up the AST to get the lexical DeclContext of this Node, which is not |
| 132 |
// the node itself. |
| 133 |
const DeclContext &getDeclContext() const; |
| 134 |
// Printable node kind, like "CXXRecordDecl" or "AutoTypeLoc". |
| 135 |
std::string kind() const; |
| 136 |
// If this node is a wrapper with no syntax (e.g. implicit cast), return |
| 137 |
// its contents. (If multiple wrappers are present, unwraps all of them). |
| 138 |
const Node &ignoreImplicit() const; |
| 139 |
// If this node is inside a wrapper with no syntax (e.g. implicit cast), |
| 140 |
// return that wrapper. (If multiple are present, unwraps all of them). |
| 141 |
const Node &outerImplicit() const; |
| 142 |
}; |
| 143 |
// The most specific common ancestor of all the selected nodes. |
| 144 |
// Returns nullptr if the common ancestor is the root. |
| 145 |
// (This is to avoid accidentally traversing the TUDecl and thus preamble). |
| 146 |
const Node *commonAncestor() const; |
| 147 |
// The selection node corresponding to TranslationUnitDecl. |
| 148 |
const Node &root() const { return *Root; } |
| 149 |
|
| 150 |
private: |
| 151 |
// Creates a selection tree for the given range in the main file. |
| 152 |
// The range includes bytes [Start, End). |
| 153 |
SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens, |
| 154 |
unsigned Start, unsigned End); |
| 155 |
|
| 156 |
std::deque<Node> Nodes; // Stable-pointer storage. |
| 157 |
const Node *Root; |
| 158 |
clang::PrintingPolicy PrintPolicy; |
| 159 |
|
| 160 |
void print(llvm::raw_ostream &OS, const Node &N, int Indent) const; |
| 161 |
friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, |
| 162 |
const SelectionTree &T) { |
| 163 |
T.print(OS, T.root(), 1); |
| 164 |
return OS; |
| 165 |
} |
| 166 |
}; |
| 167 |
|
| 168 |
} // namespace clangd |
| 169 |
} // namespace clang |
| 170 |
#endif |