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 "FindSymbols.h"
11 #include "ParsedAST.h"
12 #include "Protocol.h"
13 #include "Selection.h"
14 #include "SourceCode.h"
15 #include "clang/AST/DeclBase.h"
16 #include "clang/Basic/SourceLocation.h"
17 #include "clang/Basic/SourceManager.h"
18 #include "clang/Basic/TokenKinds.h"
19 #include "clang/Tooling/Syntax/BuildTree.h"
20 #include "clang/Tooling/Syntax/Nodes.h"
21 #include "clang/Tooling/Syntax/Tree.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/Support/Casting.h"
24 #include "llvm/Support/Error.h"
25 #include <queue>
26 #include <vector>
27
28 namespace clang {
29 namespace clangd {
30 namespace {
31
32 // Adds Range \p R to the Result if it is distinct from the last added Range.
33 // Assumes that only consecutive ranges can coincide.
addIfDistinct(const Range & R,std::vector<Range> & Result)34 void addIfDistinct(const Range &R, std::vector<Range> &Result) {
35 if (Result.empty() || Result.back() != R) {
36 Result.push_back(R);
37 }
38 }
39
toFoldingRange(SourceRange SR,const SourceManager & SM)40 llvm::Optional<FoldingRange> toFoldingRange(SourceRange SR,
41 const SourceManager &SM) {
42 const auto Begin = SM.getDecomposedLoc(SR.getBegin()),
43 End = SM.getDecomposedLoc(SR.getEnd());
44 // Do not produce folding ranges if either range ends is not within the main
45 // file. Macros have their own FileID so this also checks if locations are not
46 // within the macros.
47 if ((Begin.first != SM.getMainFileID()) || (End.first != SM.getMainFileID()))
48 return llvm::None;
49 FoldingRange Range;
50 Range.startCharacter = SM.getColumnNumber(Begin.first, Begin.second) - 1;
51 Range.startLine = SM.getLineNumber(Begin.first, Begin.second) - 1;
52 Range.endCharacter = SM.getColumnNumber(End.first, End.second) - 1;
53 Range.endLine = SM.getLineNumber(End.first, End.second) - 1;
54 return Range;
55 }
56
extractFoldingRange(const syntax::Node * Node,const SourceManager & SM)57 llvm::Optional<FoldingRange> extractFoldingRange(const syntax::Node *Node,
58 const SourceManager &SM) {
59 if (const auto *Stmt = dyn_cast<syntax::CompoundStatement>(Node)) {
60 const auto *LBrace = cast_or_null<syntax::Leaf>(
61 Stmt->findChild(syntax::NodeRole::OpenParen));
62 // FIXME(kirillbobyrev): This should find the last child. Compound
63 // statements have only one pair of braces so this is valid but for other
64 // node kinds it might not be correct.
65 const auto *RBrace = cast_or_null<syntax::Leaf>(
66 Stmt->findChild(syntax::NodeRole::CloseParen));
67 if (!LBrace || !RBrace)
68 return llvm::None;
69 // Fold the entire range within braces, including whitespace.
70 const SourceLocation LBraceLocInfo = LBrace->getToken()->endLocation(),
71 RBraceLocInfo = RBrace->getToken()->location();
72 auto Range = toFoldingRange(SourceRange(LBraceLocInfo, RBraceLocInfo), SM);
73 // Do not generate folding range for compound statements without any
74 // nodes and newlines.
75 if (Range && Range->startLine != Range->endLine)
76 return Range;
77 }
78 return llvm::None;
79 }
80
81 // Traverse the tree and collect folding ranges along the way.
collectFoldingRanges(const syntax::Node * Root,const SourceManager & SM)82 std::vector<FoldingRange> collectFoldingRanges(const syntax::Node *Root,
83 const SourceManager &SM) {
84 std::queue<const syntax::Node *> Nodes;
85 Nodes.push(Root);
86 std::vector<FoldingRange> Result;
87 while (!Nodes.empty()) {
88 const syntax::Node *Node = Nodes.front();
89 Nodes.pop();
90 const auto Range = extractFoldingRange(Node, SM);
91 if (Range)
92 Result.push_back(*Range);
93 if (const auto *T = dyn_cast<syntax::Tree>(Node))
94 for (const auto *NextNode = T->getFirstChild(); NextNode;
95 NextNode = NextNode->getNextSibling())
96 Nodes.push(NextNode);
97 }
98 return Result;
99 }
100
101 } // namespace
102
getSemanticRanges(ParsedAST & AST,Position Pos)103 llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos) {
104 std::vector<Range> Ranges;
105 const auto &SM = AST.getSourceManager();
106 const auto &LangOpts = AST.getLangOpts();
107
108 auto FID = SM.getMainFileID();
109 auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
110 if (!Offset) {
111 return Offset.takeError();
112 }
113
114 // Get node under the cursor.
115 SelectionTree ST = SelectionTree::createRight(
116 AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
117 for (const auto *Node = ST.commonAncestor(); Node != nullptr;
118 Node = Node->Parent) {
119 if (const Decl *D = Node->ASTNode.get<Decl>()) {
120 if (llvm::isa<TranslationUnitDecl>(D)) {
121 break;
122 }
123 }
124
125 auto SR = toHalfOpenFileRange(SM, LangOpts, Node->ASTNode.getSourceRange());
126 if (!SR.hasValue() || SM.getFileID(SR->getBegin()) != SM.getMainFileID()) {
127 continue;
128 }
129 Range R;
130 R.start = sourceLocToPosition(SM, SR->getBegin());
131 R.end = sourceLocToPosition(SM, SR->getEnd());
132 addIfDistinct(R, Ranges);
133 }
134
135 if (Ranges.empty()) {
136 // LSP provides no way to signal "the point is not within a semantic range".
137 // Return an empty range at the point.
138 SelectionRange Empty;
139 Empty.range.start = Empty.range.end = Pos;
140 return std::move(Empty);
141 }
142
143 // Convert to the LSP linked-list representation.
144 SelectionRange Head;
145 Head.range = std::move(Ranges.front());
146 SelectionRange *Tail = &Head;
147 for (auto &Range :
148 llvm::makeMutableArrayRef(Ranges.data(), Ranges.size()).drop_front()) {
149 Tail->parent = std::make_unique<SelectionRange>();
150 Tail = Tail->parent.get();
151 Tail->range = std::move(Range);
152 }
153
154 return std::move(Head);
155 }
156
157 // FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
158 // other code regions (e.g. public/private/protected sections of classes,
159 // control flow statement bodies).
160 // Related issue: https://github.com/clangd/clangd/issues/310
getFoldingRanges(ParsedAST & AST)161 llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST) {
162 syntax::Arena A(AST.getSourceManager(), AST.getLangOpts(), AST.getTokens());
163 const auto *SyntaxTree = syntax::buildSyntaxTree(A, AST.getASTContext());
164 return collectFoldingRanges(SyntaxTree, AST.getSourceManager());
165 }
166
167 } // namespace clangd
168 } // namespace clang
169