372 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "SemanticSelection.h"10#include "ParsedAST.h"11#include "Protocol.h"12#include "Selection.h"13#include "SourceCode.h"14#include "support/Bracket.h"15#include "support/DirectiveTree.h"16#include "support/Token.h"17#include "clang/AST/DeclBase.h"18#include "clang/Basic/SourceLocation.h"19#include "clang/Basic/SourceManager.h"20#include "clang/Basic/TokenKinds.h"21#include "clang/Tooling/Syntax/BuildTree.h"22#include "clang/Tooling/Syntax/Nodes.h"23#include "clang/Tooling/Syntax/TokenBufferTokenManager.h"24#include "clang/Tooling/Syntax/Tree.h"25#include "llvm/ADT/ArrayRef.h"26#include "llvm/ADT/StringRef.h"27#include "llvm/Support/Casting.h"28#include "llvm/Support/Error.h"29#include <optional>30#include <queue>31#include <vector>32 33namespace clang {34namespace clangd {35namespace {36 37// Adds Range \p R to the Result if it is distinct from the last added Range.38// Assumes that only consecutive ranges can coincide.39void addIfDistinct(const Range &R, std::vector<Range> &Result) {40 if (Result.empty() || Result.back() != R) {41 Result.push_back(R);42 }43}44 45std::optional<FoldingRange> toFoldingRange(SourceRange SR,46 const SourceManager &SM) {47 const auto Begin = SM.getDecomposedLoc(SR.getBegin()),48 End = SM.getDecomposedLoc(SR.getEnd());49 // Do not produce folding ranges if either range ends is not within the main50 // file. Macros have their own FileID so this also checks if locations are not51 // within the macros.52 if ((Begin.first != SM.getMainFileID()) || (End.first != SM.getMainFileID()))53 return std::nullopt;54 FoldingRange Range;55 Range.startCharacter = SM.getColumnNumber(Begin.first, Begin.second) - 1;56 Range.startLine = SM.getLineNumber(Begin.first, Begin.second) - 1;57 Range.endCharacter = SM.getColumnNumber(End.first, End.second) - 1;58 Range.endLine = SM.getLineNumber(End.first, End.second) - 1;59 return Range;60}61 62std::optional<FoldingRange>63extractFoldingRange(const syntax::Node *Node,64 const syntax::TokenBufferTokenManager &TM) {65 if (const auto *Stmt = dyn_cast<syntax::CompoundStatement>(Node)) {66 const auto *LBrace = cast_or_null<syntax::Leaf>(67 Stmt->findChild(syntax::NodeRole::OpenParen));68 // FIXME(kirillbobyrev): This should find the last child. Compound69 // statements have only one pair of braces so this is valid but for other70 // node kinds it might not be correct.71 const auto *RBrace = cast_or_null<syntax::Leaf>(72 Stmt->findChild(syntax::NodeRole::CloseParen));73 if (!LBrace || !RBrace)74 return std::nullopt;75 // Fold the entire range within braces, including whitespace.76 const SourceLocation LBraceLocInfo =77 TM.getToken(LBrace->getTokenKey())->endLocation(),78 RBraceLocInfo =79 TM.getToken(RBrace->getTokenKey())->location();80 auto Range = toFoldingRange(SourceRange(LBraceLocInfo, RBraceLocInfo),81 TM.sourceManager());82 // Do not generate folding range for compound statements without any83 // nodes and newlines.84 if (Range && Range->startLine != Range->endLine)85 return Range;86 }87 return std::nullopt;88}89 90// Traverse the tree and collect folding ranges along the way.91std::vector<FoldingRange>92collectFoldingRanges(const syntax::Node *Root,93 const syntax::TokenBufferTokenManager &TM) {94 std::queue<const syntax::Node *> Nodes;95 Nodes.push(Root);96 std::vector<FoldingRange> Result;97 while (!Nodes.empty()) {98 const syntax::Node *Node = Nodes.front();99 Nodes.pop();100 const auto Range = extractFoldingRange(Node, TM);101 if (Range)102 Result.push_back(*Range);103 if (const auto *T = dyn_cast<syntax::Tree>(Node))104 for (const auto *NextNode = T->getFirstChild(); NextNode;105 NextNode = NextNode->getNextSibling())106 Nodes.push(NextNode);107 }108 return Result;109}110 111} // namespace112 113llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos) {114 std::vector<Range> Ranges;115 const auto &SM = AST.getSourceManager();116 const auto &LangOpts = AST.getLangOpts();117 118 auto FID = SM.getMainFileID();119 auto Offset = positionToOffset(SM.getBufferData(FID), Pos);120 if (!Offset) {121 return Offset.takeError();122 }123 124 // Get node under the cursor.125 SelectionTree ST = SelectionTree::createRight(126 AST.getASTContext(), AST.getTokens(), *Offset, *Offset);127 for (const auto *Node = ST.commonAncestor(); Node != nullptr;128 Node = Node->Parent) {129 if (const Decl *D = Node->ASTNode.get<Decl>()) {130 if (llvm::isa<TranslationUnitDecl>(D)) {131 break;132 }133 }134 135 auto SR = toHalfOpenFileRange(SM, LangOpts, Node->ASTNode.getSourceRange());136 if (!SR || SM.getFileID(SR->getBegin()) != SM.getMainFileID()) {137 continue;138 }139 Range R;140 R.start = sourceLocToPosition(SM, SR->getBegin());141 R.end = sourceLocToPosition(SM, SR->getEnd());142 addIfDistinct(R, Ranges);143 }144 145 if (Ranges.empty()) {146 // LSP provides no way to signal "the point is not within a semantic range".147 // Return an empty range at the point.148 SelectionRange Empty;149 Empty.range.start = Empty.range.end = Pos;150 return std::move(Empty);151 }152 153 // Convert to the LSP linked-list representation.154 SelectionRange Head;155 Head.range = std::move(Ranges.front());156 SelectionRange *Tail = &Head;157 for (auto &Range :158 llvm::MutableArrayRef(Ranges.data(), Ranges.size()).drop_front()) {159 Tail->parent = std::make_unique<SelectionRange>();160 Tail = Tail->parent.get();161 Tail->range = std::move(Range);162 }163 164 return std::move(Head);165}166 167class PragmaRegionFinder {168 // Record the token range of a region:169 //170 // #pragma region name[[171 // ...172 // ]]#pragma endregion173 std::vector<Token::Range> &Ranges;174 const TokenStream &Code;175 // Stack of starting token (the name of the region) indices for nested #pragma176 // region.177 std::vector<unsigned> Stack;178 179public:180 PragmaRegionFinder(std::vector<Token::Range> &Ranges, const TokenStream &Code)181 : Ranges(Ranges), Code(Code) {}182 183 void walk(const DirectiveTree &T) {184 for (const auto &C : T.Chunks)185 std::visit(*this, C);186 }187 188 void operator()(const DirectiveTree::Code &C) {}189 190 void operator()(const DirectiveTree::Directive &D) {191 // Get the tokens that make up this directive.192 auto Tokens = Code.tokens(D.Tokens);193 if (Tokens.empty())194 return;195 const Token &HashToken = Tokens.front();196 assert(HashToken.Kind == tok::hash);197 const Token &Pragma = HashToken.nextNC();198 if (Pragma.text() != "pragma")199 return;200 const Token &Value = Pragma.nextNC();201 202 // Handle "#pragma region name"203 if (Value.text() == "region") {204 // Find the last token at the same line.205 const Token *T = &Value.next();206 while (T < Tokens.end() && T->Line == Pragma.Line)207 T = &T->next();208 --T;209 Stack.push_back(T->OriginalIndex);210 return;211 }212 213 // Handle "#pragma endregion"214 if (Value.text() == "endregion") {215 if (Stack.empty())216 return; // unmatched end region; ignore.217 218 unsigned StartIdx = Stack.back();219 Stack.pop_back();220 Ranges.push_back(Token::Range{StartIdx, HashToken.OriginalIndex});221 }222 }223 224 void operator()(const DirectiveTree::Conditional &C) {225 // C.Branches needs to see the DirectiveTree definition, otherwise build226 // fails in C++20.227 [[maybe_unused]] DirectiveTree Dummy;228 for (const auto &[_, SubTree] : C.Branches)229 walk(SubTree);230 }231};232 233// FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and234// other code regions (e.g. public/private/protected sections of classes,235// control flow statement bodies).236// Related issue: https://github.com/clangd/clangd/issues/310237llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST) {238 syntax::Arena A;239 syntax::TokenBufferTokenManager TM(AST.getTokens(), AST.getLangOpts(),240 AST.getSourceManager());241 const auto *SyntaxTree = syntax::buildSyntaxTree(A, TM, AST.getASTContext());242 return collectFoldingRanges(SyntaxTree, TM);243}244 245// FIXME( usaxena95): Collect includes and other code regions (e.g.246// public/private/protected sections of classes, control flow statement bodies).247// Related issue: https://github.com/clangd/clangd/issues/310248llvm::Expected<std::vector<FoldingRange>>249getFoldingRanges(const std::string &Code, bool LineFoldingOnly) {250 auto OrigStream = lex(Code, genericLangOpts());251 252 auto DirectiveStructure = DirectiveTree::parse(OrigStream);253 chooseConditionalBranches(DirectiveStructure, OrigStream);254 255 std::vector<FoldingRange> Result;256 auto AddFoldingRange = [&](Position Start, Position End,257 llvm::StringLiteral Kind) {258 if (Start.line >= End.line)259 return;260 FoldingRange FR;261 FR.startLine = Start.line;262 FR.startCharacter = Start.character;263 FR.endLine = End.line;264 FR.endCharacter = End.character;265 FR.kind = Kind.str();266 Result.push_back(FR);267 };268 auto OriginalToken = [&](const Token &T) {269 return OrigStream.tokens()[T.OriginalIndex];270 };271 auto StartOffset = [&](const Token &T) {272 return OriginalToken(T).text().data() - Code.data();273 };274 auto StartPosition = [&](const Token &T) {275 return offsetToPosition(Code, StartOffset(T));276 };277 auto EndOffset = [&](const Token &T) {278 return StartOffset(T) + OriginalToken(T).Length;279 };280 auto EndPosition = [&](const Token &T) {281 return offsetToPosition(Code, EndOffset(T));282 };283 284 // Preprocessor directives285 auto PPRanges = pairDirectiveRanges(DirectiveStructure, OrigStream);286 for (const auto &R : PPRanges) {287 auto BTok = OrigStream.tokens()[R.Begin];288 auto ETok = OrigStream.tokens()[R.End];289 if (ETok.Kind == tok::eof)290 continue;291 if (BTok.Line >= ETok.Line)292 continue;293 294 Position Start = EndPosition(BTok);295 Position End = StartPosition(ETok);296 if (LineFoldingOnly)297 End.line--;298 AddFoldingRange(Start, End, FoldingRange::REGION_KIND);299 }300 301 // FIXME: Provide ranges in the disabled-PP regions as well.302 auto Preprocessed = DirectiveStructure.stripDirectives(OrigStream);303 304 auto ParseableStream = cook(Preprocessed, genericLangOpts());305 pairBrackets(ParseableStream);306 307 auto Tokens = ParseableStream.tokens();308 309 // Brackets.310 for (const auto &Tok : Tokens) {311 if (auto *Paired = Tok.pair()) {312 // Process only token at the start of the range. Avoid ranges on a single313 // line.314 if (Tok.Line < Paired->Line) {315 Position Start = offsetToPosition(Code, 1 + StartOffset(Tok));316 Position End = StartPosition(*Paired);317 if (LineFoldingOnly)318 End.line--;319 AddFoldingRange(Start, End, FoldingRange::REGION_KIND);320 }321 }322 }323 auto IsBlockComment = [&](const Token &T) {324 assert(T.Kind == tok::comment);325 return OriginalToken(T).Length >= 2 &&326 Code.substr(StartOffset(T), 2) == "/*";327 };328 329 // Multi-line comments.330 for (auto *T = Tokens.begin(); T != Tokens.end();) {331 if (T->Kind != tok::comment) {332 T++;333 continue;334 }335 Token *FirstComment = T;336 // Show starting sentinals (// and /*) of the comment.337 Position Start = offsetToPosition(Code, 2 + StartOffset(*FirstComment));338 Token *LastComment = T;339 Position End = EndPosition(*T);340 while (T != Tokens.end() && T->Kind == tok::comment &&341 StartPosition(*T).line <= End.line + 1) {342 End = EndPosition(*T);343 LastComment = T;344 T++;345 }346 if (IsBlockComment(*FirstComment)) {347 if (LineFoldingOnly)348 // Show last line of a block comment.349 End.line--;350 if (IsBlockComment(*LastComment))351 // Show ending sentinal "*/" of the block comment.352 End.character -= 2;353 }354 AddFoldingRange(Start, End, FoldingRange::COMMENT_KIND);355 }356 357 // #pragma region358 std::vector<Token::Range> Ranges;359 PragmaRegionFinder(Ranges, OrigStream).walk(DirectiveStructure);360 auto Ts = OrigStream.tokens();361 for (const auto &R : Ranges) {362 auto End = StartPosition(Ts[R.End]);363 if (LineFoldingOnly)364 End.line--;365 AddFoldingRange(EndPosition(Ts[R.Begin]), End, FoldingRange::REGION_KIND);366 }367 return Result;368}369 370} // namespace clangd371} // namespace clang372