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.
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 
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 
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.
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 
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
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