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/Support/Casting.h"
26 #include "llvm/Support/Error.h"
27 #include <queue>
28 #include <vector>
29 
30 namespace clang {
31 namespace clangd {
32 namespace {
33 
34 // Adds Range \p R to the Result if it is distinct from the last added Range.
35 // Assumes that only consecutive ranges can coincide.
36 void addIfDistinct(const Range &R, std::vector<Range> &Result) {
37   if (Result.empty() || Result.back() != R) {
38     Result.push_back(R);
39   }
40 }
41 
42 llvm::Optional<FoldingRange> toFoldingRange(SourceRange SR,
43                                             const SourceManager &SM) {
44   const auto Begin = SM.getDecomposedLoc(SR.getBegin()),
45              End = SM.getDecomposedLoc(SR.getEnd());
46   // Do not produce folding ranges if either range ends is not within the main
47   // file. Macros have their own FileID so this also checks if locations are not
48   // within the macros.
49   if ((Begin.first != SM.getMainFileID()) || (End.first != SM.getMainFileID()))
50     return llvm::None;
51   FoldingRange Range;
52   Range.startCharacter = SM.getColumnNumber(Begin.first, Begin.second) - 1;
53   Range.startLine = SM.getLineNumber(Begin.first, Begin.second) - 1;
54   Range.endCharacter = SM.getColumnNumber(End.first, End.second) - 1;
55   Range.endLine = SM.getLineNumber(End.first, End.second) - 1;
56   return Range;
57 }
58 
59 llvm::Optional<FoldingRange>
60 extractFoldingRange(const syntax::Node *Node,
61                     const syntax::TokenBufferTokenManager &TM) {
62   if (const auto *Stmt = dyn_cast<syntax::CompoundStatement>(Node)) {
63     const auto *LBrace = cast_or_null<syntax::Leaf>(
64         Stmt->findChild(syntax::NodeRole::OpenParen));
65     // FIXME(kirillbobyrev): This should find the last child. Compound
66     // statements have only one pair of braces so this is valid but for other
67     // node kinds it might not be correct.
68     const auto *RBrace = cast_or_null<syntax::Leaf>(
69         Stmt->findChild(syntax::NodeRole::CloseParen));
70     if (!LBrace || !RBrace)
71       return llvm::None;
72     // Fold the entire range within braces, including whitespace.
73     const SourceLocation LBraceLocInfo =
74                              TM.getToken(LBrace->getTokenKey())->endLocation(),
75                          RBraceLocInfo =
76                              TM.getToken(RBrace->getTokenKey())->location();
77     auto Range = toFoldingRange(SourceRange(LBraceLocInfo, RBraceLocInfo),
78                                 TM.sourceManager());
79     // Do not generate folding range for compound statements without any
80     // nodes and newlines.
81     if (Range && Range->startLine != Range->endLine)
82       return Range;
83   }
84   return llvm::None;
85 }
86 
87 // Traverse the tree and collect folding ranges along the way.
88 std::vector<FoldingRange>
89 collectFoldingRanges(const syntax::Node *Root,
90                      const syntax::TokenBufferTokenManager &TM) {
91   std::queue<const syntax::Node *> Nodes;
92   Nodes.push(Root);
93   std::vector<FoldingRange> Result;
94   while (!Nodes.empty()) {
95     const syntax::Node *Node = Nodes.front();
96     Nodes.pop();
97     const auto Range = extractFoldingRange(Node, TM);
98     if (Range)
99       Result.push_back(*Range);
100     if (const auto *T = dyn_cast<syntax::Tree>(Node))
101       for (const auto *NextNode = T->getFirstChild(); NextNode;
102            NextNode = NextNode->getNextSibling())
103         Nodes.push(NextNode);
104   }
105   return Result;
106 }
107 
108 } // namespace
109 
110 llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos) {
111   std::vector<Range> Ranges;
112   const auto &SM = AST.getSourceManager();
113   const auto &LangOpts = AST.getLangOpts();
114 
115   auto FID = SM.getMainFileID();
116   auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
117   if (!Offset) {
118     return Offset.takeError();
119   }
120 
121   // Get node under the cursor.
122   SelectionTree ST = SelectionTree::createRight(
123       AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
124   for (const auto *Node = ST.commonAncestor(); Node != nullptr;
125        Node = Node->Parent) {
126     if (const Decl *D = Node->ASTNode.get<Decl>()) {
127       if (llvm::isa<TranslationUnitDecl>(D)) {
128         break;
129       }
130     }
131 
132     auto SR = toHalfOpenFileRange(SM, LangOpts, Node->ASTNode.getSourceRange());
133     if (!SR || SM.getFileID(SR->getBegin()) != SM.getMainFileID()) {
134       continue;
135     }
136     Range R;
137     R.start = sourceLocToPosition(SM, SR->getBegin());
138     R.end = sourceLocToPosition(SM, SR->getEnd());
139     addIfDistinct(R, Ranges);
140   }
141 
142   if (Ranges.empty()) {
143     // LSP provides no way to signal "the point is not within a semantic range".
144     // Return an empty range at the point.
145     SelectionRange Empty;
146     Empty.range.start = Empty.range.end = Pos;
147     return std::move(Empty);
148   }
149 
150   // Convert to the LSP linked-list representation.
151   SelectionRange Head;
152   Head.range = std::move(Ranges.front());
153   SelectionRange *Tail = &Head;
154   for (auto &Range :
155        llvm::makeMutableArrayRef(Ranges.data(), Ranges.size()).drop_front()) {
156     Tail->parent = std::make_unique<SelectionRange>();
157     Tail = Tail->parent.get();
158     Tail->range = std::move(Range);
159   }
160 
161   return std::move(Head);
162 }
163 
164 // FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
165 // other code regions (e.g. public/private/protected sections of classes,
166 // control flow statement bodies).
167 // Related issue: https://github.com/clangd/clangd/issues/310
168 llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST) {
169   syntax::Arena A;
170   syntax::TokenBufferTokenManager TM(AST.getTokens(), AST.getLangOpts(),
171                                      AST.getSourceManager());
172   const auto *SyntaxTree = syntax::buildSyntaxTree(A, TM, AST.getASTContext());
173   return collectFoldingRanges(SyntaxTree, TM);
174 }
175 
176 // FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
177 // other code regions (e.g. public/private/protected sections of classes,
178 // control flow statement bodies).
179 // Related issue: https://github.com/clangd/clangd/issues/310
180 llvm::Expected<std::vector<FoldingRange>>
181 getFoldingRanges(const std::string &Code) {
182   auto OrigStream = clang::pseudo::lex(Code, clang::pseudo::genericLangOpts());
183 
184   auto DirectiveStructure = clang::pseudo::DirectiveTree::parse(OrigStream);
185   clang::pseudo::chooseConditionalBranches(DirectiveStructure, OrigStream);
186 
187   // FIXME: Provide ranges in the disabled-PP regions as well.
188   auto Preprocessed = DirectiveStructure.stripDirectives(OrigStream);
189 
190   auto ParseableStream = cook(Preprocessed, clang::pseudo::genericLangOpts());
191   pseudo::pairBrackets(ParseableStream);
192 
193   std::vector<FoldingRange> Result;
194   for (const auto &Tok : ParseableStream.tokens()) {
195     if (auto *Paired = Tok.pair()) {
196       // Process only token at the start of the range. Avoid ranges on a single
197       // line.
198       if (Tok.Line < Paired->Line) {
199         Position Start = offsetToPosition(
200             Code,
201             OrigStream.tokens()[Tok.OriginalIndex].text().data() - Code.data());
202         Position End = offsetToPosition(
203             Code, OrigStream.tokens()[Paired->OriginalIndex].text().data() -
204                       Code.data());
205         FoldingRange FR;
206         FR.startLine = Start.line;
207         FR.startCharacter = Start.character + 1;
208         FR.endLine = End.line;
209         FR.endCharacter = End.character;
210         Result.push_back(FR);
211       }
212     }
213   }
214   return Result;
215 }
216 
217 } // namespace clangd
218 } // namespace clang
219