[clangd] Implement GetEligiblePoints

[kadircet]

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.

[kadircet]

• Rename regions to points
• Return EOF if there are no shared namespaces with the target

[ilya-biryukov]

A few go-by comments from me, Haojian should have better context here!

clang-tools-extra/clangd/SourceCode.cpp

655

Yay! Thanks! Less templates, more type-checking!

Could you rename 'A' to something more specific, though?
Not that there is no nice type name to guide the readers, A feels a bit confusing.

655

why const Position and not const Position&?
top-level const in function parameters is weird, it's basically ignored (except at the definition site)

674

Should this be const Position& or Position?

996

If we were to do this, I'd rather try matching brace structure and only report closing brace that is probably end of the top-level decl(function, struct, etc) events.

Everything else seems super hard to get right.

clang-tools-extra/clangd/SourceCode.h

270

Do we ever name anonymous namespace here? How do we represent them?

[kadircet]

clang-tools-extra/clangd/SourceCode.cpp

655

dropping the const

996

agreed, my suggestion was also just for figuring out when a { might start a definition, and trigger an event at the corresponding }

[kadircet]

• Address comments

[ilya-biryukov]

clang-tools-extra/clangd/SourceCode.cpp

996

Actually, now I remembered that this should also work just fine.
) { is a good marker for start of the function body, I believe clang also uses this to detect and skip function bodies for members.

So LG

[hokein]

The implementation looks good, just have some questions on the API.

clang-tools-extra/clangd/SourceCode.cpp

998

If I understand the FIXME well, so we will extend the API to parse functions, so that we could get a more eligible point e.g. near the near the neighboring declaration.

clang-tools-extra/clangd/SourceCode.h

270

Current seems not clear enough, how about "MatchNamespace"?

273

I'm curious how the caller use this, it seems that the caller has no/little information to distinguish all the positions, even for a simple case where we add a definition at the last eligible point (I assume just just using EligiblePoints.back()).

[kadircet]

clang-tools-extra/clangd/SourceCode.cpp

998

yes that's the idea. we'll try to provide as many valid insertion points as possible in the closest namespace.

clang-tools-extra/clangd/SourceCode.h

273

for example a caller with access to AST and Index, could first look at the decls surrounding the target(fully qualified name), then check for their definition locations using index and find an eligible point between these two.

[kadircet]

clang-tools-extra/clangd/SourceCode.h

270

what about enclosing?

[hokein]

clang-tools-extra/clangd/SourceCode.h

270

sounds good.

273

Fair enough, thanks for the explanation.

[kadircet]

• Address comments

clang-tools-extra/clangd/SourceCode.h

270

Do we ever name anonymous namespace here? How do we represent them?

No we don't, represents anonymous namespaces. I also updated docs to mention that FullyQualifiedName should not contain anon namespaces.

[hokein]

looks good.

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

610

nit: I'd use a struct, it is hard to infer the member by reading get<0>, get<1> (I have to go back to the top)

[kadircet]

• Address comments

clang-tools-extra/clangd/SourceCode.h

 ///   using namespace a;
 ///   namespace foo {
 ///     using namespace b;
 ///
 /// visibleNamespaces are {"foo::", "", "a::", "b::", "foo::b::"}, not "a::b::".
 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 CurrentNamespace;
+  /// 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 FullyQualifiedName
+/// in the Code. Pseudo parses Code under the hood to determine namespace decls
+/// and possible insertion points. Choses the region that matches the longest
+/// prefix of FullyQualifiedName. Returns EOF if there are no shared namespaces.
+EligibleRegion getEligiblePoints(llvm::StringRef Code,
+                                 llvm::StringRef FullyQualifiedName,
+                                 const format::FormatStyle &Style);
+
 struct DefinedMacro {
   llvm::StringRef Name;
   const MacroInfo *Info;
 };
 // Gets the macro at a specified \p Loc.
 llvm::Optional<DefinedMacro> locateMacroAt(SourceLocation Loc,
                                            Preprocessor &PP);
 
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/clangd/SourceCode.cpp

 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #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"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include "llvm/Support/xxhash.h"
 #include <algorithm>
+#include <cstddef>
+#include <string>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Here be dragons. LSP positions use columns measured in *UTF-16 code units*!
 // Clangd uses UTF-8 and byte-offsets internally, so conversion is nontrivial.
 
 // Iterates over unicode codepoints in the (UTF-8) string. For each,
SourceLocation includeHashLoc(FileID IncludedFile, const SourceManager &SM) {
   for (;; --Offset) {
     if (Buf[Offset] == '#')
       return SM.getComposedLoc(IncludingFile, Offset);
     if (Buf[Offset] == '\n' || Offset == 0) // no hash, what's going on?
       return SourceLocation();
   }
 }
 
-
 static unsigned getTokenLengthAtLoc(SourceLocation Loc, const SourceManager &SM,
                                     const LangOptions &LangOpts) {
   Token TheTok;
   if (Lexer::getRawToken(Loc, TheTok, SM, LangOpts))
     return 0;
   // FIXME: Here we check whether the token at the location is a greatergreater
   // (>>) token and consider it as a single greater (>). This is to get it
   // working for templates but it isn't correct for the right shift operator. We

 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
                  const format::FormatStyle &Style) {
   auto CleanReplaces = cleanupAroundReplacements(Code, Replaces, Style);
   if (!CleanReplaces)
     return CleanReplaces;
   return formatReplacements(Code, std::move(*CleanReplaces), Style);
 }
 
-template <typename Action>
-static void lex(llvm::StringRef Code, const format::FormatStyle &Style,
-                Action A) {
+static void
+lex(llvm::StringRef Code, const format::FormatStyle &Style,
+    llvm::function_ref<void(const clang::Token &, const Position)> A) {
   // FIXME: InMemoryFileAdapter crashes unless the buffer is null terminated!
   std::string NullTerminatedCode = Code.str();
   SourceManagerForFile FileSM("dummy.cpp", NullTerminatedCode);
   auto &SM = FileSM.get();
   auto FID = SM.getMainFileID();
   Lexer Lex(FID, SM.getBuffer(FID), SM, format::getFormattingLangOpts(Style));
   Token Tok;
 
   while (!Lex.LexFromRawLexer(Tok))
-    A(Tok);
+    A(Tok, sourceLocToPosition(SM, Tok.getLocation()));
   // LexFromRawLexer returns true after it lexes last token, so we still have
   // one more token to report.
-  A(Tok);
+  A(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, const Position) {
     switch (Tok.getKind()) {
     case tok::identifier:
       ++Identifiers[Tok.getIdentifierInfo()->getName()];
       break;
     case tok::raw_identifier:
       ++Identifiers[Tok.getRawIdentifier()];
       break;
     default:
       break;
     }
   });
   return Identifiers;
 }
 
 namespace {
-enum NamespaceEvent {
+struct NamespaceEvent {
+  enum {
     BeginNamespace, // namespace <ns> {.     Payload is resolved <ns>.
-  EndNamespace,   // } // namespace <ns>.  Payload is resolved *outer* namespace.
+    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"
   // Stack counts open braces. true if the brace opened a namespace.
   std::vector<bool> BraceStack;
 
   enum {
     Default,
     Namespace,          // just saw 'namespace'
     NamespaceName,      // just saw 'namespace' NSName
     Using,              // just saw 'using'
     UsingNamespace,     // just saw 'using namespace'
     UsingNamespaceName, // just saw 'using namespace' NSName
   } State = Default;
   std::string NSName;
 
-  lex(Code, Style, [&](const clang::Token &Tok) {
-    switch(Tok.getKind()) {
+  NamespaceEvent Event;
+  lex(Code, Style, [&](const clang::Token &Tok, const 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) {
       case UsingNamespace:
       case UsingNamespaceName:
         NSName.append(Tok.getRawIdentifier());
         State = UsingNamespaceName;
         break;
case tok::coloncolon:
       }
       break;
     case tok::l_brace:
       // Record which { started a namespace, so we know when } ends one.
       if (State == NamespaceName) {
         // 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.
         BraceStack.push_back(false);
       }
       State = Default;
       break;
     case tok::r_brace:
       // If braces are unmatched, we're going to be confused, but don't crash.
       if (!BraceStack.empty()) {
         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:
       State = Default;
       break;
     }
   });
 }

 } // namespace
 
 std::vector<std::string> visibleNamespaces(llvm::StringRef Code,
                                            const format::FormatStyle &Style) {
   std::string Current;
   // 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);
+    case NamespaceEvent::UsingDirective:
+        for (llvm::StringRef Enclosing : ancestorNamespaces(Current)) {
+            UsingDirectives[Current].insert((Enclosing + "::" + NS).str());
 
   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());
   }
 
   llvm::sort(Found, [&](const std::string &LHS, const std::string &RHS) {
     if (Current == RHS)
       return false;
     if (Current == LHS)
       return true;

 llvm::Error reformatEdit(Edit &E, const format::FormatStyle &Style) {
   if (auto NewEdits = cleanupAndFormat(E.InitialCode, E.Replacements, Style))
     E.Replacements = std::move(*NewEdits);
   else
     return NewEdits.takeError();
   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.CurrentNamespace.size()) {
+      ER.EligiblePoints.clear();
+      ER.CurrentNamespace = CurrentNamespace;
+    }
+    if (CurrentNamespace.size() == ER.CurrentNamespace.size())
+      ER.EligiblePoints.emplace_back(std::move(Event.Pos));
+  });
+  // If there were no shared namespaces just return EOF.
+  if (ER.EligiblePoints.empty()) {
+    assert(ER.CurrentNamespace.empty());
+    ER.EligiblePoints.emplace_back(offsetToPosition(Code, Code.size()));
+  }
+  return ER;
+}
+
 } // namespace clangd
 } // namespace clang

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

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Format/Format.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/raw_os_ostream.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <tuple>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using llvm::Failed;
 using llvm::HasValue;
 using ::testing::UnorderedElementsAreArray;
#define HEADER "bar.inc"
   FileID Foo = SM.getFileID(findDecl(AST, "foo").getLocation());
   EXPECT_EQ(SM.getFileOffset(includeHashLoc(Foo, SM)),
             Test.llvm::Annotations::point("foo"));
   FileID Bar = SM.getFileID(findDecl(AST, "bar").getLocation());
   EXPECT_EQ(SM.getFileOffset(includeHashLoc(Bar, SM)),
             Test.llvm::Annotations::point("bar"));
 }
 
+TEST(SourceCodeTests, GetEligiblePoints) {
+  constexpr std::tuple</*Code=*/const char *,
+                       /*FullyQualifiedName=*/const char *,
+                       /*CurrentNamespace*/ const char *>
+      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(std::get<0>(Case));
+
+    auto Res = getEligiblePoints(Test.code(), std::get<1>(Case),
+                                 format::getLLVMStyle());
+    EXPECT_THAT(Res.EligiblePoints, testing::ElementsAreArray(Test.points()))
+        << Test.code();
+    EXPECT_EQ(Res.CurrentNamespace, std::get<2>(Case)) << Test.code();
+  }
+}
 } // namespace
 } // namespace clangd
 } // namespace clang