[clangd] Implement semantic selections.

[usaxena95]

Summary

For a given cursor position, it returns ranges that are interesting to the user.
Currently the semantic ranges correspond to the nodes of the syntax trees.

[usaxena95]

Removed logs for debugging.

[usaxena95]

Create range only if it represents a valid file range.

[sammccall]

Nice! Particularly: great tests.

Only big thing is toHalfOpenFileRange should get you substantially better macro handling.

clang-tools-extra/clangd/SemanticSelection.cpp

19

nit: "unique" suggests this function checks against all the ranges in *Result (which it doesn't, and indeed doesn't need to)
I'd suggest renaming addIfDistinct and adding a comment that only consecutive ranges should be able to coincide

34

we use log() or elog() for this, make sure you include Offset.takeError() for the original message

Alternatively, you might consider returning Expected<SemanticSelectionResult> so the error gets propagated to the client (as this really is a client error)

40

I think you probably want to bail out once you hit TranslationUnitDecl.

And maybe at namespace decls? Though I have often in my editor wondered "what's the enclosing namespace"...

46

Ah, this will work if the start and the end of the AST node are written directly in the file, and no macros are involved. But try toHalfOpenFileRange in SourceCode.h, which should work in a lot more cases.

In particular, this should work:

#define INC(X) X + 1
int a, b;
int c = INC(a * b);
            ^
            ~
            ~~~~~
        ~~~~~~~~~~
~~~~~~~~~~~~~~~~~~

clang-tools-extra/clangd/SemanticSelection.h

22

I'm not sure this struct pulls its weight, I'd suggest just returning vector<Range> here.
This isn't a stable API, we can change it if we need to add things.
Or is there something you have in mind?

Often we mirror the LSP here, but LSP is weird enough here (a linked list, seriously?) that I don't particularly think we should.

28

incomplete sentence. It'd be nice to spell out on this line what an "interesting" range is (just one that corresponds to an AST node, right?)

29

somewhere you should mention that front() is the inner most range, and back() the outermost.

clang-tools-extra/clangd/unittests/SemanticSelectionTests.cpp

54

this is the case where toHalfOpenFileName should help

60

interesting, this *might* be worth special handling, to select the whole macro expansion. Wonder if people will complain. Let's leave it for now for simplicity

83

If you're interested, I think the fix here is in pointBounds() in selection.cpp.
Since selection-tree now treats semicolons as if they don't exist, we should probably handle them the same way we do whitespace, and look left instead of right.

(definitely a different patch though)

89

oh, this is interesting. it's a side-effect of how selectiontree now ignores whitespace (and semicolons, and comments).

We convert a cursor into a size-one selection, and that used to always select something, but no longer does.
This is unfortunate but hopefully pretty rare. If it's common to e.g. want to select a functiondecl while on a blank line inside it, we may want to revisit this.

116

why commented out?

[usaxena95]

Addressed comments.

[usaxena95]

Minor changes.

[usaxena95]

clang-tools-extra/clangd/SemanticSelection.cpp

34

Returning Expected<vector<Ranges>> now to propagate the error.

40

Bailing out once we hit the TUDecl. I am not sure about exiting on namespace decl. I am keeping this for now. We can remove this later if the need be.

46

Interesting. This works fine in such cases. Thanks.
Though it works strangely with these ugly macros. I guess this is because it tries to follow the macro expansion.

#define MUL ) * (
int var = (4 + 15 MUL 6 + 10);
                ^
               ~~
           ~~~~~~
          ~~~~~~~~~~~

clang-tools-extra/clangd/unittests/SemanticSelectionTests.cpp

116

Since the statement contains many [[ and ]], I have added the actual statement in comments to make it more readable.

[usaxena95]

Remove extraneous namespace comment.

[sammccall]

Nice!

Please make sure you run clang-format (I think it'll add missing newlines at EOF)

clang-tools-extra/clangd/SemanticSelection.cpp

23

nit: it's idiomatic in LLVM to pass mutable references rather than pointers where possible

53

|| SM.getFileID(SR->getBegin()) != SM.getMainFileID()

(begin and end are guaranteed to be the same file, but it may not be the main file)

clang-tools-extra/clangd/SemanticSelection.h

23

nit: if you intend to use doxygen comments (with \p syntax) you probably want /// so doxygen will render them

[nridge]

Which LSP feature is this related to?

[sammccall]

In D67358#1670810, @nridge wrote:

Which LSP feature is this related to?

selectionRange:

• https://github.com/microsoft/vscode-languageserver-node/blob/master/protocol/src/protocol.selectionRange.ts
• https://github.com/microsoft/language-server-protocol/issues/613

It hasn't been published/released yet, but AIUI it will be soon. (Thus no mention of it being an extension everywhere).
I think @usaxena95 is working on a followup to add the LSP bindings.

[usaxena95]

Resolved comments.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   Logger.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp
   Selection.cpp
   SemanticHighlighting.cpp
+  SemanticSelection.cpp
   SourceCode.cpp
   QueryDriverDatabase.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
 

clang-tools-extra/clangd/SemanticSelection.h

+//===--- SemanticSelection.h -------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Features for giving interesting semantic ranges around the cursor.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H
+#include "ParsedAST.h"
+#include "Protocol.h"
+#include "llvm/Support/Error.h"
+#include <vector>
+namespace clang {
+namespace clangd {
+
+// Returns the list of all interesting ranges around the Position \p Pos.
+// The result is computed by iterating over all the nodes in the SelectionTree
+// containing this \p Pos. Any range in the result strictly contains all the
+// previous ranges in the result.
+llvm::Expected<std::vector<Range>> getSemanticRanges(ParsedAST &AST,
+                                                     Position Pos);
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H
 No newline at end of file

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 "ParsedAST.h"
+#include "Protocol.h"
+#include "Selection.h"
+#include "SourceCode.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/Basic/SourceLocation.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 addIfDistinct(const Range &R, std::vector<Range> *Result) {
+  if (Result->empty() || Result->back() != R) {
+    Result->push_back(R);
+  }
+}
+} // namespace
+
+llvm::Expected<std::vector<Range>> getSemanticRanges(ParsedAST &AST,
+                                                     Position Pos) {
+  std::vector<Range> Result;
+  const auto &SM = AST.getSourceManager();
+  const auto &LangOpts = AST.getASTContext().getLangOpts();
+
+  auto FID = SM.getMainFileID();
+  auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
+  if (!Offset) {
+    return Offset.takeError();
+  }
+
+  // Get node under the cursor.
+  SelectionTree ST(AST.getASTContext(), AST.getTokens(), *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()) {
+      continue;
+    }
+    Range R;
+    R.start = sourceLocToPosition(SM, SR->getBegin());
+    R.end = sourceLocToPosition(SM, SR->getEnd());
+    addIfDistinct(R, &Result);
+  }
+  return Result;
+} // namespace clangd
+
+} // namespace clangd
+} // namespace clang
 No newline at end of file

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   JSONTransportTests.cpp
   ParsedASTTests.cpp
   PrintASTTests.cpp
   QualityTests.cpp
   RenameTests.cpp
   RIFFTests.cpp
   SelectionTests.cpp
   SemanticHighlightingTests.cpp
+  SemanticSelectionTests.cpp
   SerializationTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SymbolInfoTests.cpp
   SyncAPI.cpp
   TUSchedulerTests.cpp
   TestFS.cpp
   TestIndex.cpp

clang-tools-extra/clangd/unittests/SemanticSelectionTests.cpp

+//===-- SemanticSelectionTests.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 "Annotations.h"
+#include "Matchers.h"
+#include "Protocol.h"
+#include "SemanticSelection.h"
+#include "SourceCode.h"
+#include "TestTU.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <vector>
+namespace clang {
+namespace clangd {
+namespace {
+using ::testing::ElementsAreArray;
+
+TEST(SemanticSelection, All) {
+  const char *Tests[] = {
+      R"cpp( // Single statement in a function body.
+        [[void func() [[{
+          [[[[int v = [[1^00]]]];]]
+        }]]]]
+      )cpp",
+      R"cpp( // Expression
+        [[void func() [[{
+          int a = 1;
+          // int v = (10 + 2) * (a + a);
+          [[[[int v = [[[[([[[[10^]] + 2]])]] * (a + a)]]]];]]
+        }]]]]
+      )cpp",
+      R"cpp( // Function call.
+        int add(int x, int y) { return x + y; }
+        [[void callee() [[{
+          // int res = add(11, 22);
+          [[[[int res = [[add([[1^1]], 22)]]]];]]
+        }]]]]
+      )cpp",
+      R"cpp( // Tricky macros.
+        #define MUL ) * (
+        [[void func() [[{
+          // int var = (4 + 15 MUL 6 + 10);
+          [[[[int var = [[[[([[4 + [[1^5]]]] MUL]] 6 + 10)]]]];]]
+        }]]]]
+       )cpp",
+      R"cpp( // Cursor inside a macro.
+        #define HASH(x) ((x) % 10)
+        [[void func() [[{
+          [[[[int a = [[HASH([[[[2^3]] + 34]])]]]];]]
+        }]]]]
+       )cpp",
+      R"cpp( // Cursor on a macro.
+        #define HASH(x) ((x) % 10)
+        [[void func() [[{
+          [[[[int a = [[HA^SH(23)]]]];]]
+        }]]]]
+       )cpp",
+      R"cpp( // Multiple declaration.
+        [[void func() [[{
+          [[[[int var1, var^2]], var3;]]
+        }]]]]
+       )cpp",
+      R"cpp( // Before comment.
+        [[void func() [[{
+          int var1 = 1;
+          [[[[int var2 = [[[[var1]]^ /*some comment*/ + 41]]]];]]
+        }]]]]
+       )cpp",
+      // Empty file.
+      "^",
+      // FIXME: We should get the whole DeclStmt as a range.
+      R"cpp( // Single statement in TU.
+        [[int v = [[1^00]]]];
+      )cpp",
+      // FIXME: No node found associated to the position.
+      R"cpp( // Cursor at end of VarDecl.
+        void func() {
+          int v = 100 + 100^;
+        }
+      )cpp",
+      // FIXME: No node found associated to the position.
+      R"cpp( // Cursor in between spaces.
+        void func() {
+          int v = 100 + ^  100;
+        }
+      )cpp",
+      // Structs.
+      R"cpp(
+        struct AAA { struct BBB { static int ccc(); };};
+        [[void func() [[{
+          // int x = AAA::BBB::ccc();
+          [[[[int x = [[[[AAA::BBB::c^cc]]()]]]];]]
+        }]]]]
+      )cpp",
+      R"cpp(
+        struct AAA { struct BBB { static int ccc(); };};
+        [[void func() [[{
+          // int x = AAA::BBB::ccc();
+          [[[[int x = [[[[[[[[[[AA^A]]::]]BBB::]]ccc]]()]]]];]]
+        }]]]]
+      )cpp",
+      R"cpp( // Inside struct.
+        struct A { static int a(); };
+        [[struct B { 
+          [[static int b() [[{
+            [[return [[[[1^1]] + 2]]]];
+          }]]]]
+        }]];
+      )cpp",
+      // Namespaces.
+      R"cpp( 
+        [[namespace nsa { 
+          [[namespace nsb { 
+            static int ccc();
+            [[void func() [[{
+              // int x = nsa::nsb::ccc();
+              [[[[int x = [[[[nsa::nsb::cc^c]]()]]]];]]
+            }]]]]
+          }]]
+        }]]
+      )cpp",
+
+  };
+
+  for (const char *Test : Tests) {
+    auto T = Annotations(Test);
+    auto AST = TestTU::withCode(T.code()).build();
+    EXPECT_THAT(llvm::cantFail(getSemanticRanges(AST, T.point())),
+                ElementsAreArray(T.ranges()))
+        << Test;
+  }
+}
+} // namespace
+} // namespace clangd
+} // namespace clang
 No newline at end of file