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