clang-tools-extra/clangd/SemanticSelection.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-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