| 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 <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 = pseudo::lex(Code, clang::pseudo::genericLangOpts()); |
| 185 |
|
| 186 |
auto DirectiveStructure = pseudo::DirectiveTree::parse(OrigStream); |
| 187 |
pseudo::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, clang::pseudo::genericLangOpts()); |
| 193 |
pseudo::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 pseudo::Token &T) { |
| 209 |
return OrigStream.tokens()[T.OriginalIndex]; |
| 210 |
}; |
| 211 |
auto StartOffset = [&](const pseudo::Token &T) { |
| 212 |
return OriginalToken(T).text().data() - Code.data(); |
| 213 |
}; |
| 214 |
auto StartPosition = [&](const pseudo::Token &T) { |
| 215 |
return offsetToPosition(Code, StartOffset(T)); |
| 216 |
}; |
| 217 |
auto EndOffset = [&](const pseudo::Token &T) { |
| 218 |
return StartOffset(T) + OriginalToken(T).Length; |
| 219 |
}; |
| 220 |
auto EndPosition = [&](const pseudo::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 pseudo::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 |
pseudo::Token *FirstComment = T; |
| 250 |
// Show starting sentinals (// and /*) of the comment. |
| 251 |
Position Start = offsetToPosition(Code, 2 + StartOffset(*FirstComment)); |
| 252 |
pseudo::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 |