clang-tools  16.0.0git
SemanticSelection.cpp
Go to the documentation of this file.
1 //===--- SemanticSelection.cpp -----------------------------------*- 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 #include "SemanticSelection.h"
10 #include "ParsedAST.h"
11 #include "Protocol.h"
12 #include "Selection.h"
13 #include "SourceCode.h"
14 #include "clang-pseudo/Bracket.h"
15 #include "clang-pseudo/DirectiveTree.h"
16 #include "clang-pseudo/Token.h"
17 #include "clang/AST/DeclBase.h"
18 #include "clang/Basic/SourceLocation.h"
19 #include "clang/Basic/SourceManager.h"
20 #include "clang/Tooling/Syntax/BuildTree.h"
21 #include "clang/Tooling/Syntax/Nodes.h"
22 #include "clang/Tooling/Syntax/TokenBufferTokenManager.h"
23 #include "clang/Tooling/Syntax/Tree.h"
24 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/Support/Casting.h"
27 #include "llvm/Support/Error.h"
28 #include <queue>
29 #include <vector>
30 
31 namespace clang {
32 namespace clangd {
33 namespace {
34 
35 // Adds Range \p R to the Result if it is distinct from the last added Range.
36 // Assumes that only consecutive ranges can coincide.
37 void addIfDistinct(const Range &R, std::vector<Range> &Result) {
38  if (Result.empty() || Result.back() != R) {
39  Result.push_back(R);
40  }
41 }
42 
43 llvm::Optional<FoldingRange> toFoldingRange(SourceRange SR,
44  const SourceManager &SM) {
45  const auto Begin = SM.getDecomposedLoc(SR.getBegin()),
46  End = SM.getDecomposedLoc(SR.getEnd());
47  // Do not produce folding ranges if either range ends is not within the main
48  // file. Macros have their own FileID so this also checks if locations are not
49  // within the macros.
50  if ((Begin.first != SM.getMainFileID()) || (End.first != SM.getMainFileID()))
51  return llvm::None;
52  FoldingRange Range;
53  Range.startCharacter = SM.getColumnNumber(Begin.first, Begin.second) - 1;
54  Range.startLine = SM.getLineNumber(Begin.first, Begin.second) - 1;
55  Range.endCharacter = SM.getColumnNumber(End.first, End.second) - 1;
56  Range.endLine = SM.getLineNumber(End.first, End.second) - 1;
57  return Range;
58 }
59 
60 llvm::Optional<FoldingRange>
61 extractFoldingRange(const syntax::Node *Node,
62  const syntax::TokenBufferTokenManager &TM) {
63  if (const auto *Stmt = dyn_cast<syntax::CompoundStatement>(Node)) {
64  const auto *LBrace = cast_or_null<syntax::Leaf>(
65  Stmt->findChild(syntax::NodeRole::OpenParen));
66  // FIXME(kirillbobyrev): This should find the last child. Compound
67  // statements have only one pair of braces so this is valid but for other
68  // node kinds it might not be correct.
69  const auto *RBrace = cast_or_null<syntax::Leaf>(
70  Stmt->findChild(syntax::NodeRole::CloseParen));
71  if (!LBrace || !RBrace)
72  return llvm::None;
73  // Fold the entire range within braces, including whitespace.
74  const SourceLocation LBraceLocInfo =
75  TM.getToken(LBrace->getTokenKey())->endLocation(),
76  RBraceLocInfo =
77  TM.getToken(RBrace->getTokenKey())->location();
78  auto Range = toFoldingRange(SourceRange(LBraceLocInfo, RBraceLocInfo),
79  TM.sourceManager());
80  // Do not generate folding range for compound statements without any
81  // nodes and newlines.
82  if (Range && Range->startLine != Range->endLine)
83  return Range;
84  }
85  return llvm::None;
86 }
87 
88 // Traverse the tree and collect folding ranges along the way.
89 std::vector<FoldingRange>
90 collectFoldingRanges(const syntax::Node *Root,
91  const syntax::TokenBufferTokenManager &TM) {
92  std::queue<const syntax::Node *> Nodes;
93  Nodes.push(Root);
94  std::vector<FoldingRange> Result;
95  while (!Nodes.empty()) {
96  const syntax::Node *Node = Nodes.front();
97  Nodes.pop();
98  const auto Range = extractFoldingRange(Node, TM);
99  if (Range)
100  Result.push_back(*Range);
101  if (const auto *T = dyn_cast<syntax::Tree>(Node))
102  for (const auto *NextNode = T->getFirstChild(); NextNode;
103  NextNode = NextNode->getNextSibling())
104  Nodes.push(NextNode);
105  }
106  return Result;
107 }
108 
109 } // namespace
110 
111 llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos) {
112  std::vector<Range> Ranges;
113  const auto &SM = AST.getSourceManager();
114  const auto &LangOpts = AST.getLangOpts();
115 
116  auto FID = SM.getMainFileID();
117  auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
118  if (!Offset) {
119  return Offset.takeError();
120  }
121 
122  // Get node under the cursor.
124  AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
125  for (const auto *Node = ST.commonAncestor(); Node != nullptr;
126  Node = Node->Parent) {
127  if (const Decl *D = Node->ASTNode.get<Decl>()) {
128  if (llvm::isa<TranslationUnitDecl>(D)) {
129  break;
130  }
131  }
132 
133  auto SR = toHalfOpenFileRange(SM, LangOpts, Node->ASTNode.getSourceRange());
134  if (!SR || SM.getFileID(SR->getBegin()) != SM.getMainFileID()) {
135  continue;
136  }
137  Range R;
138  R.start = sourceLocToPosition(SM, SR->getBegin());
139  R.end = sourceLocToPosition(SM, SR->getEnd());
140  addIfDistinct(R, Ranges);
141  }
142 
143  if (Ranges.empty()) {
144  // LSP provides no way to signal "the point is not within a semantic range".
145  // Return an empty range at the point.
147  Empty.range.start = Empty.range.end = Pos;
148  return std::move(Empty);
149  }
150 
151  // Convert to the LSP linked-list representation.
153  Head.range = std::move(Ranges.front());
155  for (auto &Range :
156  llvm::makeMutableArrayRef(Ranges.data(), Ranges.size()).drop_front()) {
157  Tail->parent = std::make_unique<SelectionRange>();
158  Tail = Tail->parent.get();
159  Tail->range = std::move(Range);
160  }
161 
162  return std::move(Head);
163 }
164 
165 // FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
166 // other code regions (e.g. public/private/protected sections of classes,
167 // control flow statement bodies).
168 // Related issue: https://github.com/clangd/clangd/issues/310
169 llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST) {
171  syntax::TokenBufferTokenManager TM(AST.getTokens(), AST.getLangOpts(),
172  AST.getSourceManager());
173  const auto *SyntaxTree = syntax::buildSyntaxTree(A, TM, AST.getASTContext());
174  return collectFoldingRanges(SyntaxTree, TM);
175 }
176 
177 // FIXME( usaxena95): Collect PP conditional regions, includes and other code
178 // regions (e.g. public/private/protected sections of classes, control flow
179 // statement bodies).
180 // Related issue: https://github.com/clangd/clangd/issues/310
181 llvm::Expected<std::vector<FoldingRange>>
182 getFoldingRanges(const std::string &Code, bool LineFoldingOnly) {
183  auto OrigStream = pseudo::lex(Code, clang::pseudo::genericLangOpts());
184 
185  auto DirectiveStructure = pseudo::DirectiveTree::parse(OrigStream);
186  pseudo::chooseConditionalBranches(DirectiveStructure, OrigStream);
187 
188  // FIXME: Provide ranges in the disabled-PP regions as well.
189  auto Preprocessed = DirectiveStructure.stripDirectives(OrigStream);
190 
191  auto ParseableStream = cook(Preprocessed, clang::pseudo::genericLangOpts());
192  pseudo::pairBrackets(ParseableStream);
193 
194  std::vector<FoldingRange> Result;
195  auto AddFoldingRange = [&](Position Start, Position End,
196  llvm::StringLiteral Kind) {
197  if (Start.line >= End.line)
198  return;
199  FoldingRange FR;
200  FR.startLine = Start.line;
201  FR.startCharacter = Start.character;
202  FR.endLine = End.line;
203  FR.endCharacter = End.character;
204  FR.kind = Kind.str();
205  Result.push_back(FR);
206  };
207  auto OriginalToken = [&](const pseudo::Token &T) {
208  return OrigStream.tokens()[T.OriginalIndex];
209  };
210  auto StartOffset = [&](const pseudo::Token &T) {
211  return OriginalToken(T).text().data() - Code.data();
212  };
213  auto StartPosition = [&](const pseudo::Token &T) {
214  return offsetToPosition(Code, StartOffset(T));
215  };
216  auto EndOffset = [&](const pseudo::Token &T) {
217  return StartOffset(T) + OriginalToken(T).Length;
218  };
219  auto EndPosition = [&](const pseudo::Token &T) {
220  return offsetToPosition(Code, EndOffset(T));
221  };
222  auto Tokens = ParseableStream.tokens();
223  // Brackets.
224  for (const auto &Tok : Tokens) {
225  if (auto *Paired = Tok.pair()) {
226  // Process only token at the start of the range. Avoid ranges on a single
227  // line.
228  if (Tok.Line < Paired->Line) {
229  Position Start = offsetToPosition(Code, 1 + StartOffset(Tok));
230  Position End = StartPosition(*Paired);
231  if (LineFoldingOnly)
232  End.line--;
233  AddFoldingRange(Start, End, FoldingRange::REGION_KIND);
234  }
235  }
236  }
237  auto IsBlockComment = [&](const pseudo::Token &T) {
238  assert(T.Kind == tok::comment);
239  return OriginalToken(T).Length >= 2 &&
240  Code.substr(StartOffset(T), 2) == "/*";
241  };
242  // Multi-line comments.
243  for (auto *T = Tokens.begin(); T != Tokens.end();) {
244  if (T->Kind != tok::comment) {
245  T++;
246  continue;
247  }
248  pseudo::Token *FirstComment = T;
249  // Show starting sentinals (// and /*) of the comment.
250  Position Start = offsetToPosition(Code, 2 + StartOffset(*FirstComment));
251  pseudo::Token *LastComment = T;
252  Position End = EndPosition(*T);
253  while (T != Tokens.end() && T->Kind == tok::comment &&
254  StartPosition(*T).line <= End.line + 1) {
255  End = EndPosition(*T);
256  LastComment = T;
257  T++;
258  }
259  if (IsBlockComment(*FirstComment)) {
260  if (LineFoldingOnly)
261  // Show last line of a block comment.
262  End.line--;
263  if (IsBlockComment(*LastComment))
264  // Show ending sentinal "*/" of the block comment.
265  End.character -= 2;
266  }
267  AddFoldingRange(Start, End, FoldingRange::COMMENT_KIND);
268  }
269  return Result;
270 }
271 
272 } // namespace clangd
273 } // namespace clang
Range
CharSourceRange Range
SourceRange for the file name.
Definition: IncludeOrderCheck.cpp:39
clang::clangd::Head
@ Head
Definition: FuzzyMatch.h:58
clang::clangd::FoldingRange::startLine
unsigned startLine
Definition: Protocol.h:1792
clang::clangd::getFoldingRanges
llvm::Expected< std::vector< FoldingRange > > getFoldingRanges(ParsedAST &AST)
Returns a list of ranges whose contents might be collapsible in an editor.
Definition: SemanticSelection.cpp:169
Selection.h
clang::clangd::toHalfOpenFileRange
llvm::Optional< SourceRange > toHalfOpenFileRange(const SourceManager &SM, const LangOptions &LangOpts, SourceRange R)
Turns a token range into a half-open range and checks its correctness.
Definition: SourceCode.cpp:425
clang::clangd::ParsedAST::getASTContext
ASTContext & getASTContext()
Note that the returned ast will not contain decls from the preamble that were not deserialized during...
Definition: ParsedAST.cpp:700
Root
ASTNode Root
Definition: DumpAST.cpp:332
Kind
BindArgumentKind Kind
Definition: AvoidBindCheck.cpp:59
clang::clangd::Range::start
Position start
The range's start position.
Definition: Protocol.h:187
clang::clangd::FoldingRange::endCharacter
unsigned endCharacter
Definition: Protocol.h:1795
clang::clangd::getSemanticRanges
llvm::Expected< SelectionRange > getSemanticRanges(ParsedAST &AST, Position Pos)
Returns the list of all interesting ranges around the Position Pos.
Definition: SemanticSelection.cpp:111
clang::clangd::FoldingRange::kind
std::string kind
Definition: Protocol.h:1800
clang::clangd::FoldingRange::COMMENT_KIND
const static llvm::StringLiteral COMMENT_KIND
Definition: Protocol.h:1798
clang::clangd::sourceLocToPosition
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc)
Turn a SourceLocation into a [line, column] pair.
Definition: SourceCode.cpp:213
clang::clangd::Tail
@ Tail
Definition: FuzzyMatch.h:57
clang::clangd::ParsedAST::getLangOpts
const LangOptions & getLangOpts() const
Definition: ParsedAST.h:81
Pos
size_t Pos
Definition: NoLintDirectiveHandler.cpp:97
Protocol.h
Offset
size_t Offset
Definition: CodeComplete.cpp:1213
ns1::ns2::A
@ A
Definition: CategoricalFeature.h:3
clang::clangd::Position
Definition: Protocol.h:156
Code
std::string Code
Definition: FindTargetTests.cpp:67
clang::clangd::FoldingRange::REGION_KIND
const static llvm::StringLiteral REGION_KIND
Definition: Protocol.h:1797
clang::clangd::FoldingRange::endLine
unsigned endLine
Definition: Protocol.h:1794
ns1::ns2::D
@ D
Definition: CategoricalFeature.h:3
Decl
const FunctionDecl * Decl
Definition: AvoidBindCheck.cpp:100
clang::clangd::SelectionTree::createRight
static SelectionTree createRight(ASTContext &AST, const syntax::TokenBuffer &Tokens, unsigned Begin, unsigned End)
Definition: Selection.cpp:1059
clang::clangd::lex
static void lex(llvm::StringRef Code, const LangOptions &LangOpts, llvm::function_ref< void(const syntax::Token &, const SourceManager &SM)> Action)
Definition: SourceCode.cpp:605
SemanticSelection.h
clang::clangd::positionToOffset
llvm::Expected< size_t > positionToOffset(llvm::StringRef Code, Position P, bool AllowColumnsBeyondLineLength)
Turn a [line, column] pair into an offset in Code.
Definition: SourceCode.cpp:172
clang::clangd::Range::end
Position end
The range's end position.
Definition: Protocol.h:190
clang::clangd::offsetToPosition
Position offsetToPosition(llvm::StringRef Code, size_t Offset)
Turn an offset in Code into a [line, column] pair.
Definition: SourceCode.cpp:201
clang::clangd::SelectionTree
Definition: Selection.h:76
clang::clangd::SelectionRange
Definition: Protocol.h:1735
clang::clangd::SelectionTree::commonAncestor
const Node * commonAncestor() const
Definition: Selection.cpp:1089
SourceCode.h
clang::clangd::Empty
@ Empty
Definition: FuzzyMatch.h:42
clang::clangd::Range
Definition: Protocol.h:185
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::FoldingRange
Stores information about a region of code that can be folded.
Definition: Protocol.h:1791
clang::clangd::ParsedAST::getTokens
const syntax::TokenBuffer & getTokens() const
Tokens recorded while parsing the main file.
Definition: ParsedAST.h:107
Arena
llvm::BumpPtrAllocator Arena
Definition: Serialization.cpp:213
LangOpts
const LangOptions * LangOpts
Definition: ExtractFunction.cpp:375
clang::clangd::ParsedAST
Stores and provides access to parsed AST.
Definition: ParsedAST.h:46
clang::clangd::FoldingRange::startCharacter
unsigned startCharacter
Definition: Protocol.h:1793
clang::clangd::ParsedAST::getSourceManager
SourceManager & getSourceManager()
Definition: ParsedAST.h:74
ParsedAST.h