[clangd] Initial supoprt for cross-namespace global code completion.

Summary:
When no scope qualifier is specified, allow completing index symbols
from any scope and insert proper automatically. This is still experimental and
hidden behind a flag.

Things missing:
- Scope proximity based scoring.
- FuzzyFind supports weighted scopes.

Reviewers: sammccall

Reviewed By: sammccall

Subscribers: kbobyrev, ilya-biryukov, MaskRay, jkorous, arphaman, kadircet, cfe-commits

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

8 files changed, 130 insertions, 15 deletions

diff --git a/clang-tools-extra/clangd/CodeComplete.cpp b/clang-tools-extra/clangd/CodeComplete.cpp
index e43389ba849..cd237268db4 100644
--- a/clang-tools-extra/clangd/CodeComplete.cpp
+++ b/clang-tools-extra/clangd/CodeComplete.cpp
@@ -44,6 +44,7 @@
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Error.h"
@@ -330,6 +331,7 @@ struct ScoredBundleGreater {
 struct CodeCompletionBuilder {
   CodeCompletionBuilder(ASTContext &ASTCtx, const CompletionCandidate &C,
                         CodeCompletionString *SemaCCS,
+                        llvm::ArrayRef<std::string> QueryScopes,
                         const IncludeInserter &Includes, StringRef FileName,
                         CodeCompletionContext::Kind ContextKind,
                         const CodeCompleteOptions &Opts)
@@ -374,6 +376,18 @@ struct CodeCompletionBuilder {
         Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
       if (Completion.Name.empty())
         Completion.Name = C.IndexResult->Name;
+      // If the completion was visible to Sema, no qualifier is needed. This
+      // avoids unneeded qualifiers in cases like with `using ns::X`.
+      if (Completion.RequiredQualifier.empty() && !C.SemaResult) {
+        StringRef ShortestQualifier = C.IndexResult->Scope;
+        for (StringRef Scope : QueryScopes) {
+          StringRef Qualifier = C.IndexResult->Scope;
+          if (Qualifier.consume_front(Scope) &&
+              Qualifier.size() < ShortestQualifier.size())
+            ShortestQualifier = Qualifier;
+        }
+        Completion.RequiredQualifier = ShortestQualifier;
+      }
       Completion.Deprecated |= (C.IndexResult->Flags & Symbol::Deprecated);
     }
 
@@ -604,9 +618,11 @@ struct SpecifiedScope {
   }
 };
 
-// Get all scopes that will be queried in indexes.
-std::vector<std::string> getQueryScopes(CodeCompletionContext &CCContext,
-                                        const SourceManager &SM) {
+// Get all scopes that will be queried in indexes and whether symbols from
+// any scope is allowed.
+std::pair<std::vector<std::string>, bool>
+getQueryScopes(CodeCompletionContext &CCContext, const SourceManager &SM,
+               const CodeCompleteOptions &Opts) {
   auto GetAllAccessibleScopes = [](CodeCompletionContext &CCContext) {
     SpecifiedScope Info;
     for (auto *Context : CCContext.getVisitedContexts()) {
@@ -627,13 +643,15 @@ std::vector<std::string> getQueryScopes(CodeCompletionContext &CCContext,
     // FIXME: Capture scopes and use for scoring, for example,
     //        "using namespace std; namespace foo {v^}" =>
     //        foo::value > std::vector > boost::variant
-    return GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    auto Scopes = GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    // Allow AllScopes completion only for there is no explicit scope qualifier.
+    return {Scopes, Opts.AllScopes};
   }
 
   // Qualified completion ("std::vec^"), we have two cases depending on whether
   // the qualifier can be resolved by Sema.
   if ((*SS)->isValid()) { // Resolved qualifier.
-    return GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    return {GetAllAccessibleScopes(CCContext).scopesForIndexQuery(), false};
   }
 
   // Unresolved qualifier.
@@ -651,7 +669,7 @@ std::vector<std::string> getQueryScopes(CodeCompletionContext &CCContext,
   if (!Info.UnresolvedQualifier->empty())
     *Info.UnresolvedQualifier += "::";
 
-  return Info.scopesForIndexQuery();
+  return {Info.scopesForIndexQuery(), false};
 }
 
 // Should we perform index-based completion in a context of the specified kind?
@@ -1262,8 +1280,10 @@ class CodeCompleteFlow {
   CompletionRecorder *Recorder = nullptr;
   int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
   bool Incomplete = false; // Would more be available with a higher limit?
-  llvm::Optional<FuzzyMatcher> Filter;       // Initialized once Sema runs.
-  std::vector<std::string> QueryScopes;      // Initialized once Sema runs.
+  llvm::Optional<FuzzyMatcher> Filter;  // Initialized once Sema runs.
+  std::vector<std::string> QueryScopes; // Initialized once Sema runs.
+  // Whether to query symbols from any scope. Initialized once Sema runs.
+  bool AllScopes = false;
   // Include-insertion and proximity scoring rely on the include structure.
   // This is available after Sema has run.
   llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
@@ -1339,9 +1359,9 @@ public:
       Inserter.reset(); // Make sure this doesn't out-live Clang.
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
-      log("Code complete: sema context {0}, query scopes [{1}]",
+      log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2})",
           getCompletionKindString(Recorder->CCContext.getKind()),
-          llvm::join(QueryScopes.begin(), QueryScopes.end(), ","));
+          llvm::join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes);
     });
 
     Recorder = RecorderOwner.get();
@@ -1387,8 +1407,8 @@ private:
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
-    QueryScopes = getQueryScopes(Recorder->CCContext,
-                                 Recorder->CCSema->getSourceManager());
+    std::tie(QueryScopes, AllScopes) = getQueryScopes(
+        Recorder->CCContext, Recorder->CCSema->getSourceManager(), Opts);
     // Sema provides the needed context to query the index.
     // FIXME: in addition to querying for extra/overlapping symbols, we should
     //        explicitly request symbols corresponding to Sema results.
@@ -1428,6 +1448,7 @@ private:
     Req.Query = Filter->pattern();
     Req.RestrictForCodeCompletion = true;
     Req.Scopes = QueryScopes;
+    Req.AnyScope = AllScopes;
     // FIXME: we should send multiple weighted paths here.
     Req.ProximityPaths.push_back(FileName);
     vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
@@ -1538,6 +1559,8 @@ private:
     Relevance.Context = Recorder->CCContext.getKind();
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     Relevance.FileProximityMatch = FileProximity.getPointer();
+    // FIXME: incorparate scope proximity into relevance score.
+
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
@@ -1587,8 +1610,8 @@ private:
                           : nullptr;
       if (!Builder)
         Builder.emplace(Recorder->CCSema->getASTContext(), Item, SemaCCS,
-                        *Inserter, FileName, Recorder->CCContext.getKind(),
-                        Opts);
+                        QueryScopes, *Inserter, FileName,
+                        Recorder->CCContext.getKind(), Opts);
       else
         Builder->add(Item, SemaCCS);
     }
diff --git a/clang-tools-extra/clangd/CodeComplete.h b/clang-tools-extra/clangd/CodeComplete.h
index 6467ad35499..92fa2279a5c 100644
--- a/clang-tools-extra/clangd/CodeComplete.h
+++ b/clang-tools-extra/clangd/CodeComplete.h
@@ -101,6 +101,13 @@ struct CodeCompleteOptions {
   /// Whether to generate snippets for function arguments on code-completion.
   /// Needs snippets to be enabled as well.
   bool EnableFunctionArgSnippets = true;
+
+  /// Whether to include index symbols that are not defined in the scopes
+  /// visible from the code completion point. This applies in contexts without
+  /// explicit scope qualifiers.
+  ///
+  /// Such completions can insert scope qualifiers.
+  bool AllScopes = false;
 };
 
 // Semi-structured representation of a code-complete suggestion for our C++ API.
diff --git a/clang-tools-extra/clangd/index/Index.h b/clang-tools-extra/clangd/index/Index.h
index 746638229af..06de5d44536 100644
--- a/clang-tools-extra/clangd/index/Index.h
+++ b/clang-tools-extra/clangd/index/Index.h
@@ -428,7 +428,13 @@ struct FuzzyFindRequest {
   /// namespace xyz::abc.
   ///
   /// The global scope is "", a top level scope is "foo::", etc.
+  /// FIXME: drop the special case for empty list, which is the same as
+  /// `AnyScope = true`.
+  /// FIXME: support scope proximity.
   std::vector<std::string> Scopes;
+  /// If set to true, allow symbols from any scope. Scopes explicitly listed
+  /// above will be ranked higher.
+  bool AnyScope = false;
   /// \brief The number of top candidates to return. The index may choose to
   /// return more than this, e.g. if it doesn't know which candidates are best.
   llvm::Optional<uint32_t> Limit;
diff --git a/clang-tools-extra/clangd/index/MemIndex.cpp b/clang-tools-extra/clangd/index/MemIndex.cpp
index d39b86f232d..279969dfc29 100644
--- a/clang-tools-extra/clangd/index/MemIndex.cpp
+++ b/clang-tools-extra/clangd/index/MemIndex.cpp
@@ -39,7 +39,8 @@ bool MemIndex::fuzzyFind(
     const Symbol *Sym = Pair.second;
 
     // Exact match against all possible scopes.
-    if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
+    if (!Req.AnyScope && !Req.Scopes.empty() &&
+        !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;
     if (Req.RestrictForCodeCompletion &&
         !(Sym->Flags & Symbol::IndexedForCodeCompletion))
diff --git a/clang-tools-extra/clangd/index/dex/Dex.cpp b/clang-tools-extra/clangd/index/dex/Dex.cpp
index 880be3d71e6..b201fd87d97 100644
--- a/clang-tools-extra/clangd/index/dex/Dex.cpp
+++ b/clang-tools-extra/clangd/index/dex/Dex.cpp
@@ -13,6 +13,8 @@
 #include "Logger.h"
 #include "Quality.h"
 #include "Trace.h"
+#include "index/Index.h"
+#include "index/dex/Iterator.h"
 #include "llvm/ADT/StringSet.h"
 #include <algorithm>
 #include <queue>
@@ -166,6 +168,10 @@ bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
     if (It != InvertedIndex.end())
       ScopeIterators.push_back(It->second.iterator());
   }
+  if (Req.AnyScope)
+    ScopeIterators.push_back(createBoost(createTrue(Symbols.size()),
+                                         ScopeIterators.empty() ? 1.0 : 0.2));
+
   // Add OR iterator for scopes if there are any Scope Iterators.
   if (!ScopeIterators.empty())
     TopLevelChildren.push_back(createOr(move(ScopeIterators)));
diff --git a/clang-tools-extra/clangd/tool/ClangdMain.cpp b/clang-tools-extra/clangd/tool/ClangdMain.cpp
index 4c6a4c35246..aebff518932 100644
--- a/clang-tools-extra/clangd/tool/ClangdMain.cpp
+++ b/clang-tools-extra/clangd/tool/ClangdMain.cpp
@@ -136,6 +136,15 @@ static llvm::cl::opt<bool> EnableIndex(
         "enabled separatedly."),
     llvm::cl::init(true), llvm::cl::Hidden);
 
+static llvm::cl::opt<bool> AllScopesCompletion(
+    "all-scopes-completion",
+    llvm::cl::desc(
+        "If set to true, code completion will include index symbols that are "
+        "not defined in the scopes (e.g. "
+        "namespaces) visible from the code completion point. Such completions "
+        "can insert scope qualifiers."),
+    llvm::cl::init(false), llvm::cl::Hidden);
+
 static llvm::cl::opt<bool>
     ShowOrigins("debug-origin",
                 llvm::cl::desc("Show origins of completion items"),
@@ -304,6 +313,7 @@ int main(int argc, char *argv[]) {
   }
   CCOpts.SpeculativeIndexRequest = Opts.StaticIndex;
   CCOpts.EnableFunctionArgSnippets = EnableFunctionArgSnippets;
+  CCOpts.AllScopes = AllScopesCompletion;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(
diff --git a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
index fc707baf2c6..68b13da17e1 100644
--- a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
+++ b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
@@ -2093,6 +2093,57 @@ TEST(CompletionTest, IncludedCompletionKinds) {
                     Has("bar.h\"", CompletionItemKind::File)));
 }
 
+TEST(CompletionTest, NoAllScopesCompletionWhenQualified) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(
+      R"cpp(
+    void f() { na::Clangd^ }
+  )cpp",
+      {cls("na::ClangdA"), cls("nx::ClangdX"), cls("Clangd3")}, Opts);
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(
+                  AllOf(Qualifier(""), Scope("na::"), Named("ClangdA"))));
+}
+
+TEST(CompletionTest, AllScopesCompletion) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(
+      R"cpp(
+    namespace na {
+    void f() { Clangd^ }
+    }
+  )cpp",
+      {cls("nx::Clangd1"), cls("ny::Clangd2"), cls("Clangd3"),
+       cls("na::nb::Clangd4")},
+      Opts);
+  EXPECT_THAT(
+      Results.Completions,
+      UnorderedElementsAre(AllOf(Qualifier("nx::"), Named("Clangd1")),
+                           AllOf(Qualifier("ny::"), Named("Clangd2")),
+                           AllOf(Qualifier(""), Scope(""), Named("Clangd3")),
+                           AllOf(Qualifier("nb::"), Named("Clangd4"))));
+}
+
+TEST(CompletionTest, NoQualifierIfShadowed) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(R"cpp(
+    namespace nx { class Clangd1 {}; }
+    using nx::Clangd1;
+    void f() { Clangd^ }
+  )cpp",
+                             {cls("nx::Clangd1"), cls("nx::Clangd2")}, Opts);
+  // Although Clangd1 is from another namespace, Sema tells us it's in-scope and
+  // needs no qualifier.
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(AllOf(Qualifier(""), Named("Clangd1")),
+                                   AllOf(Qualifier("nx::"), Named("Clangd2"))));
+}
 
 } // namespace
 } // namespace clangd
diff --git a/clang-tools-extra/unittests/clangd/DexTests.cpp b/clang-tools-extra/unittests/clangd/DexTests.cpp
index d9db3087f94..231343cd78b 100644
--- a/clang-tools-extra/unittests/clangd/DexTests.cpp
+++ b/clang-tools-extra/unittests/clangd/DexTests.cpp
@@ -523,6 +523,17 @@ TEST(DexTest, NoMatchNestedScopes) {
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
 }
 
+TEST(DexTest, WildcardScope) {
+  auto I =
+      Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), URISchemes);
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes = {"a::"};
+  Req.AnyScope = true;
+  EXPECT_THAT(match(*I, Req),
+              UnorderedElementsAre("a::y1", "a::b::y2", "c::y3"));
+}
+
 TEST(DexTest, IgnoreCases) {
   auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), URISchemes);
   FuzzyFindRequest Req;