[clangd] Query index in code completion no-compile mode.

[sammccall]

Summary

We scrape the enclosing scopes from the source file, and use them in the query.

[kadircet]

clangd/SourceCode.cpp

503

I believe it is safe to ignore(just mark the opening brace) anonymous namespaces here. Since there were no comments(and no test cases) just wanted to make sure you did not miss that case.

595

scopesForIndexQuery already de-duplicates. Do you plan to have any other users for the results of this function?

clangd/SourceCode.h

169

Does the code ever make use of it?

unittests/clangd/SourceCodeTests.cpp

325

NIT: maybe switch to TEST_P ?

[sammccall]

Add comments, add anon-namespacce test, tighten parsing rules slightly (namespace ::... is illegal)

[sammccall]

clangd/SourceCode.cpp

503

Right, this was intended. Added a comment and a test.

595

Only unit tests.
Seems a bit neater to always return canonical results, though.

clangd/SourceCode.h

169

This is passed into the ScopeDistance, and the first scope gets a quality boost. Added a comment.

I just noticed that getQueryScopes (not used on this codepath) only sometimes returns the scopes in the right order. Will fix in another patch.

unittests/clangd/SourceCodeTests.cpp

325

I find TEST_P much less readable and prefer to avoid it unless absolutely necessary.
Does it buy anything here?(

[sammccall]

Correctly handle absolutely qualifier (::foo::bar).
Fix seed scopes for proximity to be consistent with Sema case.

[sammccall]

Fix test.

[kadircet]

LGTM, thanks!

unittests/clangd/SourceCodeTests.cpp

325

I just wanted to make sure we don't have more huge test cases as in Hover.All. I believe it would've helped if we've kept cases in small groups.

But I guess we won't gain much here, since number of cases is not huge and I think there won't be many additions.

clangd/CodeComplete.cpp

auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
           PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
                         : "<none>");
     });
 
     Recorder = RecorderOwner.get();
 
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
+    logResults(Output, Tracer);
+    return Output;
+  }
 
+  void logResults(const CodeCompleteResult &Output, const trace::Span &Tracer) {
     SPAN_ATTACH(Tracer, "sema_results", NSema);
     SPAN_ATTACH(Tracer, "index_results", NIndex);
     SPAN_ATTACH(Tracer, "merged_results", NSemaAndIndex);
     SPAN_ATTACH(Tracer, "identifier_results", NIdent);
     SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
     SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
     log("Code complete: {0} results from Sema, {1} from Index, "
         "{2} matched, {3} from identifiers, {4} returned{5}.",
         NSema, NIndex, NSemaAndIndex, NIdent, Output.Completions.size(),
         Output.HasMore ? " (incomplete)" : "");
     assert(!Opts.Limit || Output.Completions.size() <= Opts.Limit);
     // We don't assert that isIncomplete means we hit a limit.
     // Indexes may choose to impose their own limits even if we don't have one.
-    return Output;
   }
 
   CodeCompleteResult
   runWithoutSema(llvm::StringRef Content, size_t Offset,
                  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS) && {
-    auto CCPrefix = guessCompletionPrefix(Content, Offset);
+    trace::Span Tracer("CodeCompleteWithoutSema");
     // Fill in fields normally set by runWithSema()
+    HeuristicPrefix = guessCompletionPrefix(Content, Offset);
     CCContextKind = CodeCompletionContext::CCC_Recovery;
-    Filter = FuzzyMatcher(CCPrefix.Name);
+    Filter = FuzzyMatcher(HeuristicPrefix.Name);
     auto Pos = offsetToPosition(Content, Offset);
     ReplacedRange.start = ReplacedRange.end = Pos;
-    ReplacedRange.start.character -= CCPrefix.Name.size();
+    ReplacedRange.start.character -= HeuristicPrefix.Name.size();
 
     llvm::StringMap<SourceParams> ProxSources;
     ProxSources[FileName].Cost = 0;
     FileProximity.emplace(ProxSources);
 
-    // FIXME: collect typed scope specifier and potentially parse the enclosing
-    // namespaces.
-    // FIXME: initialize ScopeProximity when scopes are added.
-
     auto Style = getFormatStyleForFile(FileName, Content, VFS.get());
     // This will only insert verbatim headers.
     Inserter.emplace(FileName, Content, Style,
                      /*BuildDir=*/"", /*HeaderSearchInfo=*/nullptr);
 
     auto Identifiers = collectIdentifiers(Content, Style);
     std::vector<RawIdentifier> IdentifierResults;
     for (const auto &IDAndCount : Identifiers) {
       RawIdentifier ID;
       ID.Name = IDAndCount.first();
       ID.References = IDAndCount.second;
       // Avoid treating typed filter as an identifier.
-      if (ID.Name == CCPrefix.Name)
+      if (ID.Name == HeuristicPrefix.Name)
         --ID.References;
       if (ID.References > 0)
         IdentifierResults.push_back(std::move(ID));
     }
 
-    // FIXME: add results from Opts.Index when we know more about scopes (e.g.
-    // typed scope specifier).
-    return toCodeCompleteResult(mergeResults(
-        /*SemaResults=*/{}, /*IndexResults*/ {}, IdentifierResults));
+    // Simplified version of getQueryScopes():
+    //  - accessible scopes are determined heuristically.
+    //  - all-scopes query if no qualifier was typed (and it's allowed).
+    SpecifiedScope Scopes;
+    Scopes.AccessibleScopes =
+        visibleNamespaces(Content.take_front(Offset), Style);
+    for (std::string &S : Scopes.AccessibleScopes)
+      if (!S.empty())
+        S.append("::"); // visibleNamespaces doesn't include trailing ::.
+    if (HeuristicPrefix.Qualifier.empty())
+      AllScopes = Opts.AllScopes;
+    else
+      Scopes.UnresolvedQualifier = HeuristicPrefix.Qualifier;
+    QueryScopes = Scopes.scopesForIndexQuery();
+    ScopeProximity.emplace(Scopes.AccessibleScopes);
+
+    SymbolSlab IndexResults = Opts.Index ? queryIndex() : SymbolSlab();
+
+    CodeCompleteResult Output = toCodeCompleteResult(mergeResults(
+        /*SemaResults=*/{}, IndexResults, IdentifierResults));
+    logResults(Output, Tracer);
+    return Output;
   }
 
 private:
   // This is called by run() once Sema code completion is done, but before the
   // Sema data structures are torn down. It does all the real work.
   CodeCompleteResult runWithSema() {
     const auto &CodeCompletionRange = CharSourceRange::getCharRange(
         Recorder->CCSema->getPreprocessor().getCodeCompletionTokenRange());

clangd/SourceCode.h

 llvm::Expected<tooling::Replacements>
 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
                  const format::FormatStyle &Style);
 
 /// Collects identifiers with counts in the source code.
 llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
                                              const format::FormatStyle &Style);
 
+/// Heuristically determine namespaces visible at a point, without parsing Code.
+/// This considers using-directives and enclosing namespace-declarations that
+/// are visible (and not obfuscated) in the file itself (not headers).
+/// Code should be truncated at the point of interest.
+///
+/// The returned vector is always non-empty.
+/// - The first element is the namespace that encloses the point: a declaration
+///   near the point would be within this namespace.
+/// - The elements are the namespaces in scope at the point: an unqualified
+///   lookup would search within these namespaces.
+///
+/// Using directives are resolved against all enclosing scopes, but no other
+/// namespace directives.
+///
+/// example:
+///   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);
+
 } // namespace clangd
 } // namespace clang
 #endif

clangd/SourceCode.cpp

 //===--- SourceCode.h - Manipulating source code as strings -----*- 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 "SourceCode.h"
 
 #include "Context.h"
 #include "Logger.h"
 #include "Protocol.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Format/Format.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Path.h"
+#include <algorithm>
 
 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,

 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);
 }
 
-llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
-                                             const format::FormatStyle &Style) {
-  SourceManagerForFile FileSM("dummy.cpp", Content);
+template <typename Action>
+static void lex(llvm::StringRef Code, const format::FormatStyle &Style,
+                Action 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);
+}
+
+llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
+                                             const format::FormatStyle &Style) {
   llvm::StringMap<unsigned> Identifiers;
-  while (!Lex.LexFromRawLexer(Tok)) {
+  lex(Content, Style, [&](const clang::Token &Tok) {
     switch (Tok.getKind()) {
     case tok::identifier:
       ++Identifiers[Tok.getIdentifierInfo()->getName()];
       break;
     case tok::raw_identifier:
       ++Identifiers[Tok.getRawIdentifier()];
       break;
     default:
-      continue;
-    }
+      break;
     }
+  });
   return Identifiers;
 }
 
+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>.
+};
+// 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) {
+
+  // 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()) {
+    case tok::raw_identifier:
+      switch (State) {
+      case UsingNamespace:
+      case UsingNamespaceName:
+        NSName.append(Tok.getRawIdentifier());
+        State = UsingNamespaceName;
+        break;
+      case Namespace:
+      case NamespaceName:
+        NSName.append(Tok.getRawIdentifier());
+        State = NamespaceName;
+        break;
+      case Using:
+        State =
+            (Tok.getRawIdentifier() == "namespace") ? UsingNamespace : Default;
+        break;
+      case Default:
+        NSName.clear();
+        if (Tok.getRawIdentifier() == "namespace")
+          State = Namespace;
+        else if (Tok.getRawIdentifier() == "using")
+          State = Using;
+        break;
+      }
+      break;
+    case tok::coloncolon:
+      switch (State) {
+      case UsingNamespace:
+      case UsingNamespaceName:
+        NSName.append("::");
+        State = UsingNamespaceName;
+        break;
+      case Namespace:
+      case NamespaceName:
+        NSName.append("::");
+        State = NamespaceName;
+        break;
+      case Using:
+      case Default:
+        State = Default;
+        break;
+      }
+      break;
+    case tok::l_brace:
+      if (State == NamespaceName) {
+        // Parsed: namespace <name> {
+        BraceStack.push_back(true);
+        Enclosing.push_back(NSName);
+        Callback(BeginNamespace, llvm::join(Enclosing, "::"));
+      } else {
+        BraceStack.push_back(false);
+      }
+      State = Default;
+      break;
+    case tok::r_brace:
+      if (!BraceStack.empty()) {
+        if (BraceStack.back()) {
+          // Parsed: } // namespace
+          Enclosing.pop_back();
+          Callback(EndNamespace, llvm::join(Enclosing, "::"));
+        }
+        BraceStack.pop_back();
+      }
+      break;
+    case tok::semi:
+      if (State == UsingNamespaceName)
+        // Parsed: using namespace <name> ;
+        Callback(UsingDirective, llvm::StringRef(NSName));
+      State = Default;
+      break;
+    default:
+      State = Default;
+      break;
+    }
+  });
+}
+
+// Returns the prefix namespaces of NS: {"" ... NS}.
+llvm::SmallVector<llvm::StringRef, 8> ancestorNamespaces(llvm::StringRef NS) {
+  llvm::SmallVector<llvm::StringRef, 8> Results;
+  Results.push_back(NS.take_front(0));
+  NS.split(Results, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+  for (llvm::StringRef &R : Results)
+    R = NS.take_front(R.end() - NS.begin());
+  return Results;
+}
+
+} // 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;
+                         }
+                       });
+
+  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)
+        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;
+    return LHS < RHS;
+  });
+  Found.erase(std::unique(Found.begin(), Found.end()), Found.end());
+  return Found;
+}
+
 } // namespace clangd
 } // namespace clang

unittests/clangd/CodeCompleteTests.cpp

 #include "Matchers.h"
 #include "Protocol.h"
 #include "Quality.h"
 #include "SourceCode.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "TestIndex.h"
 #include "TestTU.h"
+#include "index/Index.h"
 #include "index/MemIndex.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
void func() {
       int xyz2;
       sy^
     }
   )cpp");
   EXPECT_THAT(Results.Completions,
               UnorderedElementsAre(Named("sym1"), Named("sym2")));
 }
 
+TEST(NoCompileCompletionTest, WithIndex) {
+  std::vector<Symbol> Syms = {func("xxx"), func("a::xxx"), func("ns::b::xxx"),
+                              func("c::xxx"), func("ns::d::xxx")};
+  auto Results = completionsNoCompile(
+      R"cpp(
+        // Current-scopes, unqualified completion.
+        using namespace a;
+        namespace ns {
+        using namespace b;
+        void foo() {
+        xx^
+        }
+      )cpp",
+      Syms);
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(AllOf(Qualifier(""), Scope("")),
+                                   AllOf(Qualifier(""), Scope("a::")),
+                                   AllOf(Qualifier(""), Scope("ns::b::"))));
+  CodeCompleteOptions Opts;
+  Opts.AllScopes = true;
+  Results = completionsNoCompile(
+      R"cpp(
+        // All-scopes unqualified completion.
+        using namespace a;
+        namespace ns {
+        using namespace b;
+        void foo() {
+        xx^
+        }
+      )cpp",
+      Syms, Opts);
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(AllOf(Qualifier(""), Scope("")),
+                                   AllOf(Qualifier(""), Scope("a::")),
+                                   AllOf(Qualifier(""), Scope("ns::b::")),
+                                   AllOf(Qualifier("c::"), Scope("c::")),
+                                   AllOf(Qualifier("d::"), Scope("ns::d::"))));
+  Results = completionsNoCompile(
+      R"cpp(
+        // Qualified completion.
+        using namespace a;
+        namespace ns {
+        using namespace b;
+        void foo() {
+        b::xx^
+        }
+      )cpp",
+      Syms, Opts);
+  EXPECT_THAT(Results.Completions,
+              ElementsAre(AllOf(Qualifier(""), Scope("ns::b::"))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/SourceCodeTests.cpp

TEST(SourceCodeTests, CollectIdentifiers) {
   EXPECT_EQ(IDs["void"], 1u);
   EXPECT_EQ(IDs["int"], 2u);
   EXPECT_EQ(IDs["xyz"], 2u);
   EXPECT_EQ(IDs["abc"], 1u);
   EXPECT_EQ(IDs["return"], 1u);
   EXPECT_EQ(IDs["foo"], 2u);
 }
 
+TEST(SourceCodeTests, VisibleNamespaces) {
+  std::vector<std::pair<const char *, std::vector<std::string>>> Cases = {
+      {
+          R"cpp(
+            // Using directive resolved against enclosing namespaces.
+            using namespace foo;
+            namespace ns {
+            using namespace bar;
+          )cpp",
+          {"ns", "", "bar", "foo", "ns::bar"},
+      },
+      {
+          R"cpp(
+            // Don't include namespaces we've closed, ignore namespace aliases.
+            using namespace clang;
+            using std::swap;
+            namespace clang {
+            namespace clangd {}
+            namespace ll = ::llvm;
+            }
+            namespace clang {
+          )cpp",
+          {"clang", ""},
+      },
+      {
+          R"cpp(
+            // Using directives visible even if a namespace is reopened.
+            namespace foo{ using namespace bar; }
+            namespace foo{
+          )cpp",
+          {"foo", "", "bar", "foo::bar"},
+      },
+      {
+          R"cpp(
+            // Mismatched braces
+            namespace foo{}
+            }}}
+            namespace bar{
+          )cpp",
+          {"bar", ""},
+      },
+      {
+          R"cpp(
+            // Namespaces with multiple chunks.
+            namespace a::b {
+              using namespace c::d;
+              namespace e::f {
+          )cpp",
+          {
+              "a::b::e::f",
+              "",
+              "a",
+              "a::b",
+              "a::b::c::d",
+              "a::b::e",
+              "a::c::d",
+              "c::d",
+          },
+      },
+  };
+  for (const auto& Case : Cases) {
+    EXPECT_EQ(Case.second,
+              visibleNamespaces(Case.first, format::getLLVMStyle()))
+        << Case.first;
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang