Index: clangd/CodeComplete.cpp
===================================================================
--- clangd/CodeComplete.cpp
+++ clangd/CodeComplete.cpp
@@ -1269,7 +1269,11 @@
 
     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);
@@ -1283,28 +1287,24 @@
     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,
@@ -1317,16 +1317,34 @@
       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:
Index: clangd/SourceCode.h
===================================================================
--- clangd/SourceCode.h
+++ clangd/SourceCode.h
@@ -160,6 +160,29 @@
 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
Index: clangd/SourceCode.cpp
===================================================================
--- clangd/SourceCode.cpp
+++ clangd/SourceCode.cpp
@@ -12,13 +12,17 @@
 #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 {
@@ -391,16 +395,25 @@
   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()];
@@ -409,11 +422,179 @@
       ++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
Index: unittests/clangd/CodeCompleteTests.cpp
===================================================================
--- unittests/clangd/CodeCompleteTests.cpp
+++ unittests/clangd/CodeCompleteTests.cpp
@@ -18,6 +18,7 @@
 #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"
@@ -2452,6 +2453,58 @@
               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
Index: unittests/clangd/SourceCodeTests.cpp
===================================================================
--- unittests/clangd/SourceCodeTests.cpp
+++ unittests/clangd/SourceCodeTests.cpp
@@ -322,6 +322,73 @@
   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