[clangd] Implement GetEligiblePoints

Summary:
This is an helper for incoming move definition out-of-line action to
figure out possible insertion locations for definition of a qualified name.

Reviewers: hokein, ilya-biryukov

Subscribers: MaskRay, jkorous, arphaman, usaxena95, cfe-commits

Tags: #clang

Differential Revision: https://reviews.llvm.org/D68024

3 files changed, 195 insertions, 44 deletions

diff --git a/clang-tools-extra/clangd/SourceCode.cpp b/clang-tools-extra/clangd/SourceCode.cpp
index 05ca7aaaa1e..a0cec30f10a 100644
--- a/clang-tools-extra/clangd/SourceCode.cpp
+++ b/clang-tools-extra/clangd/SourceCode.cpp
@@ -20,9 +20,11 @@
 #include "clang/Format/Format.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
+#include "clang/Lex/Token.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
@@ -37,6 +39,9 @@
 #include "llvm/Support/VirtualFileSystem.h"
 #include "llvm/Support/xxhash.h"
 #include <algorithm>
+#include <cstddef>
+#include <string>
+#include <vector>
 
 namespace clang {
 namespace clangd {
@@ -396,7 +401,6 @@ SourceLocation includeHashLoc(FileID IncludedFile, const SourceManager &SM) {
   }
 }
 
-
 static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
                                     const LangOptions &LangOpts) {
   Token TheTok;
@@ -715,9 +719,8 @@ cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
   return formatReplacements(Code, std::move(*CleanReplaces), Style);
 }
 
-template <typename Action>
-static void lex(llvm::StringRef Code, const format::FormatStyle &Style,
-                Action A) {
+void lex(llvm::StringRef Code, const format::FormatStyle &Style,
+         llvm::function_ref<void(const clang::Token &, Position)> Action) {
   // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
   std::string NullTerminatedCode = Code.str();
   SourceManagerForFile FileSM("dummy.cpp", NullTerminatedCode);
@@ -727,16 +730,16 @@ static void lex(llvm::StringRef Code, const format::FormatStyle &Style,
   Token Tok;
 
   while (!Lex.LexFromRawLexer(Tok))
-    A(Tok);
+    Action(Tok, sourceLocToPosition(SM, Tok.getLocation()));
   // LexFromRawLexer returns true after it lexes last token, so we still have
   // one more token to report.
-  A(Tok);
+  Action(Tok, sourceLocToPosition(SM, Tok.getLocation()));
 }
 
 llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
                                              const format::FormatStyle &Style) {
   llvm::StringMap<unsigned> Identifiers;
-  lex(Content, Style, [&](const clang::Token &Tok) {
+  lex(Content, Style, [&](const clang::Token &Tok, Position) {
     switch (Tok.getKind()) {
     case tok::identifier:
       ++Identifiers[Tok.getIdentifierInfo()->getName()];
@@ -752,15 +755,20 @@ llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
 }
 
 namespace {
-enum NamespaceEvent {
-  BeginNamespace, // namespace <ns> {.     Payload is resolved <ns>.
-  EndNamespace,   // } // namespace <ns>.  Payload is resolved *outer* namespace.
-  UsingDirective  // using namespace <ns>. Payload is unresolved <ns>.
+struct NamespaceEvent {
+  enum {
+    BeginNamespace, // namespace <ns> {.     Payload is resolved <ns>.
+    EndNamespace,   // } // namespace <ns>.  Payload is resolved *outer*
+                    // namespace.
+    UsingDirective  // using namespace <ns>. Payload is unresolved <ns>.
+  } Trigger;
+  std::string Payload;
+  Position Pos;
 };
 // Scans C++ source code for constructs that change the visible namespaces.
-void parseNamespaceEvents(
-    llvm::StringRef Code, const format::FormatStyle &Style,
-    llvm::function_ref<void(NamespaceEvent, llvm::StringRef)> Callback) {
+void parseNamespaceEvents(llvm::StringRef Code,
+                          const format::FormatStyle &Style,
+                          llvm::function_ref<void(NamespaceEvent)> Callback) {
 
   // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
   std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
@@ -777,8 +785,10 @@ void parseNamespaceEvents(
   } State = Default;
   std::string NSName;
 
-  lex(Code, Style, [&](const clang::Token &Tok) {
-    switch(Tok.getKind()) {
+  NamespaceEvent Event;
+  lex(Code, Style, [&](const clang::Token &Tok, Position P) {
+    Event.Pos = std::move(P);
+    switch (Tok.getKind()) {
     case tok::raw_identifier:
       // In raw mode, this could be a keyword or a name.
       switch (State) {
@@ -830,7 +840,9 @@ void parseNamespaceEvents(
         // Parsed: namespace <name> {
         BraceStack.push_back(true);
         Enclosing.push_back(NSName);
-        Callback(BeginNamespace, llvm::join(Enclosing, "::"));
+        Event.Trigger = NamespaceEvent::BeginNamespace;
+        Event.Payload = llvm::join(Enclosing, "::");
+        Callback(Event);
       } else {
         // This case includes anonymous namespaces (State = Namespace).
         // For our purposes, they're not namespaces and we ignore them.
@@ -844,15 +856,20 @@ void parseNamespaceEvents(
         if (BraceStack.back()) {
           // Parsed: } // namespace
           Enclosing.pop_back();
-          Callback(EndNamespace, llvm::join(Enclosing, "::"));
+          Event.Trigger = NamespaceEvent::EndNamespace;
+          Event.Payload = llvm::join(Enclosing, "::");
+          Callback(Event);
         }
         BraceStack.pop_back();
       }
       break;
     case tok::semi:
-      if (State == UsingNamespaceName)
+      if (State == UsingNamespaceName) {
         // Parsed: using namespace <name> ;
-        Callback(UsingDirective, llvm::StringRef(NSName));
+        Event.Trigger = NamespaceEvent::UsingDirective;
+        Event.Payload = std::move(NSName);
+        Callback(Event);
+      }
       State = Default;
       break;
     default:
@@ -880,36 +897,34 @@ std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
   // Map from namespace to (resolved) namespaces introduced via using directive.
   llvm::StringMap<llvm::StringSet<>> UsingDirectives;
 
-  parseNamespaceEvents(Code, Style,
-                       [&](NamespaceEvent Event, llvm::StringRef NS) {
-                         switch (Event) {
-                         case BeginNamespace:
-                         case EndNamespace:
-                           Current = NS;
-                           break;
-                         case UsingDirective:
-                           if (NS.consume_front("::"))
-                             UsingDirectives[Current].insert(NS);
-                           else {
-                             for (llvm::StringRef Enclosing :
-                                  ancestorNamespaces(Current)) {
-                               if (Enclosing.empty())
-                                 UsingDirectives[Current].insert(NS);
-                               else
-                                 UsingDirectives[Current].insert(
-                                     (Enclosing + "::" + NS).str());
-                             }
-                           }
-                           break;
-                         }
-                       });
+  parseNamespaceEvents(Code, Style, [&](NamespaceEvent Event) {
+    llvm::StringRef NS = Event.Payload;
+    switch (Event.Trigger) {
+    case NamespaceEvent::BeginNamespace:
+    case NamespaceEvent::EndNamespace:
+      Current = std::move(Event.Payload);
+      break;
+    case NamespaceEvent::UsingDirective:
+      if (NS.consume_front("::"))
+        UsingDirectives[Current].insert(NS);
+      else {
+        for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
+          if (Enclosing.empty())
+            UsingDirectives[Current].insert(NS);
+          else
+            UsingDirectives[Current].insert((Enclosing + "::" + NS).str());
+        }
+      }
+      break;
+    }
+  });
 
   std::vector<std::string> Found;
   for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
     Found.push_back(Enclosing);
     auto It = UsingDirectives.find(Enclosing);
     if (It != UsingDirectives.end())
-      for (const auto& Used : It->second)
+      for (const auto &Used : It->second)
         Found.push_back(Used.getKey());
   }
 
@@ -1040,5 +1055,58 @@ llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
   return llvm::Error::success();
 }
 
+EligibleRegion getEligiblePoints(llvm::StringRef Code,
+                                 llvm::StringRef FullyQualifiedName,
+                                 const format::FormatStyle &Style) {
+  EligibleRegion ER;
+  // Start with global namespace.
+  std::vector<std::string> Enclosing = {""};
+  // FIXME: In addition to namespaces try to generate events for function
+  // definitions as well. One might use a closing parantheses(")" followed by an
+  // opening brace "{" to trigger the start.
+  parseNamespaceEvents(Code, Style, [&](NamespaceEvent Event) {
+    // Using Directives only introduces declarations to current scope, they do
+    // not change the current namespace, so skip them.
+    if (Event.Trigger == NamespaceEvent::UsingDirective)
+      return;
+    // Do not qualify the global namespace.
+    if (!Event.Payload.empty())
+      Event.Payload.append("::");
+
+    std::string CurrentNamespace;
+    if (Event.Trigger == NamespaceEvent::BeginNamespace) {
+      Enclosing.emplace_back(std::move(Event.Payload));
+      CurrentNamespace = Enclosing.back();
+      // parseNameSpaceEvents reports the beginning position of a token; we want
+      // to insert after '{', so increment by one.
+      ++Event.Pos.character;
+    } else {
+      // Event.Payload points to outer namespace when exiting a scope, so use
+      // the namespace we've last entered instead.
+      CurrentNamespace = std::move(Enclosing.back());
+      Enclosing.pop_back();
+      assert(Enclosing.back() == Event.Payload);
+    }
+
+    // Ignore namespaces that are not a prefix of the target.
+    if (!FullyQualifiedName.startswith(CurrentNamespace))
+      return;
+
+    // Prefer the namespace that shares the longest prefix with target.
+    if (CurrentNamespace.size() > ER.EnclosingNamespace.size()) {
+      ER.EligiblePoints.clear();
+      ER.EnclosingNamespace = CurrentNamespace;
+    }
+    if (CurrentNamespace.size() == ER.EnclosingNamespace.size())
+      ER.EligiblePoints.emplace_back(std::move(Event.Pos));
+  });
+  // If there were no shared namespaces just return EOF.
+  if (ER.EligiblePoints.empty()) {
+    assert(ER.EnclosingNamespace.empty());
+    ER.EligiblePoints.emplace_back(offsetToPosition(Code, Code.size()));
+  }
+  return ER;
+}
+
 } // namespace clangd
 } // namespace clang
diff --git a/clang-tools-extra/clangd/SourceCode.h b/clang-tools-extra/clangd/SourceCode.h
index 3017746c17e..a05d8adf923 100644
--- a/clang-tools-extra/clangd/SourceCode.h
+++ b/clang-tools-extra/clangd/SourceCode.h
@@ -262,6 +262,27 @@ llvm::StringSet<> collectWords(llvm::StringRef Content);
 std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
                                            const format::FormatStyle &Style);
 
+/// Represents locations that can accept a definition.
+struct EligibleRegion {
+  /// Namespace that owns all of the EligiblePoints, e.g.
+  /// namespace a{ namespace b {^ void foo();^} }
+  /// It will be “a::b” for both carrot locations.
+  std::string EnclosingNamespace;
+  /// Offsets into the code marking eligible points to insert a function
+  /// definition.
+  std::vector<Position> EligiblePoints;
+};
+
+/// Returns most eligible region to insert a definition for \p
+/// FullyQualifiedName in the \p Code.
+/// Pseudo parses \pCode under the hood to determine namespace decls and
+/// possible insertion points. Choses the region that matches the longest prefix
+/// of \p FullyQualifiedName. Returns EOF if there are no shared namespaces.
+/// \p FullyQualifiedName should not contain anonymous namespaces.
+EligibleRegion getEligiblePoints(llvm::StringRef Code,
+                                 llvm::StringRef FullyQualifiedName,
+                                 const format::FormatStyle &Style);
+
 struct DefinedMacro {
   llvm::StringRef Name;
   const MacroInfo *Info;
diff --git a/clang-tools-extra/clangd/unittests/SourceCodeTests.cpp b/clang-tools-extra/clangd/unittests/SourceCodeTests.cpp
index e49f64cef13..cbed9a0f064 100644
--- a/clang-tools-extra/clangd/unittests/SourceCodeTests.cpp
+++ b/clang-tools-extra/clangd/unittests/SourceCodeTests.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <tuple>
 
 namespace clang {
 namespace clangd {
@@ -618,6 +619,67 @@ $foo^#include "foo.inc"
             Test.llvm::Annotations::point("bar"));
 }
 
+TEST(SourceCodeTests, GetEligiblePoints) {
+  constexpr struct {
+    const char *Code;
+    const char *FullyQualifiedName;
+    const char *EnclosingNamespace;
+  } Cases[] = {
+      {R"cpp(// FIXME: We should also mark positions before and after
+                 //declarations/definitions as eligible.
+              namespace ns1 {
+              namespace a { namespace ns2 {} }
+              namespace ns2 {^
+              void foo();
+              namespace {}
+              void bar() {}
+              namespace ns3 {}
+              class T {};
+              ^}
+              using namespace ns2;
+              })cpp",
+       "ns1::ns2::symbol", "ns1::ns2::"},
+      {R"cpp(
+              namespace ns1 {^
+              namespace a { namespace ns2 {} }
+              namespace b {}
+              namespace ns {}
+              ^})cpp",
+       "ns1::ns2::symbol", "ns1::"},
+      {R"cpp(
+              namespace x {
+              namespace a { namespace ns2 {} }
+              namespace b {}
+              namespace ns {}
+              }^)cpp",
+       "ns1::ns2::symbol", ""},
+      {R"cpp(
+              namespace ns1 {
+              namespace ns2 {^^}
+              namespace b {}
+              namespace ns2 {^^}
+              }
+              namespace ns1 {namespace ns2 {^^}})cpp",
+       "ns1::ns2::symbol", "ns1::ns2::"},
+      {R"cpp(
+              namespace ns1 {^
+              namespace ns {}
+              namespace b {}
+              namespace ns {}
+              ^}
+              namespace ns1 {^namespace ns {}^})cpp",
+       "ns1::ns2::symbol", "ns1::"},
+  };
+  for (auto Case : Cases) {
+    Annotations Test(Case.Code);
+
+    auto Res = getEligiblePoints(Test.code(), Case.FullyQualifiedName,
+                                 format::getLLVMStyle());
+    EXPECT_THAT(Res.EligiblePoints, testing::ElementsAreArray(Test.points()))
+        << Test.code();
+    EXPECT_EQ(Res.EnclosingNamespace, Case.EnclosingNamespace) << Test.code();
+  }
+}
 } // namespace
 } // namespace clangd
 } // namespace clang