[clangd][WIP] Make use of SyntaxTrees for SemanticSelection

[kadircet]

Summary

This patch is not intended for production, it is merely an experiment
to see how SyntaxTrees can be used inside clangd.

Depends on D84973

[gribozavr2]

clang-tools-extra/clangd/SemanticSelection.cpp

51

It would be nice to make it into a method on syntax::Node itself, or otherwise put it into a shared location, include/clang/Tooling/Syntax/???.h.

60

lastLeaf() is traversing all children. Instead, you could compare against the location of C->nextSibling()->firstLeaf().

clang-tools-extra/clangd/SemanticSelection.cpp

 //===--- SemanticSelection.cpp -----------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "SemanticSelection.h"
 #include "FindSymbols.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "Selection.h"
 #include "SourceCode.h"
+#include "support/Logger.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Tooling/Syntax/BuildTree.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Adds Range \p R to the Result if it is distinct from the last added Range.
 // Assumes that only consecutive ranges can coincide.
void collectFoldingRanges(DocumentSymbol Symbol,
   Range.startCharacter = Symbol.range.start.character;
   Range.endLine = Symbol.range.end.line;
   Range.endCharacter = Symbol.range.end.character;
   Result.push_back(Range);
   for (const auto &Child : Symbol.children)
     collectFoldingRanges(Child, Result);
 }
 
+syntax::Leaf *leafContaining(const syntax::Token *Tok, syntax::Tree *Root,
+                             syntax::Arena &A, const SourceManager &SM) {
+  if (!Tok)
+    return nullptr;
+  vlog("searching for {0} in:\n{1}", Tok->text(SM), Root->dump(A));
+  for (auto *C = Root->firstChild(); C; C = C->nextSibling()) {
+    if (auto *L = llvm::dyn_cast<syntax::Leaf>(C)) {
+      if (L->token() == Tok)
+        return L;
+    } else if (auto *T = llvm::dyn_cast<syntax::Tree>(C)) {
+      if (T->firstLeaf()->token() <= Tok && Tok <= T->lastLeaf()->token())
+        return leafContaining(Tok, T, A, SM);
+    }
+  }
+  return nullptr;
+}
+
 } // namespace
 
 llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos) {
+  syntax::Arena A(AST.getSourceManager(), AST.getLangOpts(), AST.getTokens());
+  auto *STree =
+      syntax::buildSyntaxTree(A, *AST.getASTContext().getTranslationUnitDecl());
   std::vector<Range> Ranges;
   const auto &SM = AST.getSourceManager();
-  const auto &LangOpts = AST.getLangOpts();
 
   auto FID = SM.getMainFileID();
   auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
   if (!Offset) {
     return Offset.takeError();
   }
 
   // Get node under the cursor.
-  SelectionTree ST = SelectionTree::createRight(
-      AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
-  for (const auto *Node = ST.commonAncestor(); Node != nullptr;
-       Node = Node->Parent) {
-    if (const Decl *D = Node->ASTNode.get<Decl>()) {
-      if (llvm::isa<TranslationUnitDecl>(D)) {
-        break;
-      }
-    }
-
-    auto SR = toHalfOpenFileRange(SM, LangOpts, Node->ASTNode.getSourceRange());
-    if (!SR.hasValue() || SM.getFileID(SR->getBegin()) != SM.getMainFileID()) {
+  auto Toks = AST.getTokens().expandedForSpelled(syntax::spelledTokensTouching(
+      SM.getComposedLoc(FID, *Offset), AST.getTokens()));
+  Toks.push_back({});
+  for (const auto &Tok : Toks.front()) {
+    if (auto *L = leafContaining(&Tok, STree, A, SM)) {
+      for (const syntax::Tree *Node = L->parent(); Node != nullptr;
+           Node = Node->parent()) {
+        SourceRange SR(Node->firstLeaf()->token()->location(),
+                       Node->lastLeaf()->token()->location());
+        auto FR = toHalfOpenFileRange(SM, AST.getLangOpts(), SR);
+        if (!FR || SM.getFileID(SR.getBegin()) != SM.getMainFileID())
           continue;
+        addIfDistinct(halfOpenToRange(SM, CharSourceRange::getCharRange(*FR)),
+                      Ranges);
+      }
+      break;
     }
-    Range R;
-    R.start = sourceLocToPosition(SM, SR->getBegin());
-    R.end = sourceLocToPosition(SM, SR->getEnd());
-    addIfDistinct(R, Ranges);
   }
 
   if (Ranges.empty()) {
     // LSP provides no way to signal "the point is not within a semantic range".
     // Return an empty range at the point.
     SelectionRange Empty;
     Empty.range.start = Empty.range.end = Pos;
     return std::move(Empty);