[clangd] auto-index stores symbols per-file instead of per-TU.

[ioeric]

Summary

This allows us to deduplicate header symbols across TUs. File digests
are collects when collecting symbols/refs. And the index store deduplicates
file symbols based on the file digest.

[sammccall]

clangd/index/FileIndex.cpp

167 ↗

(On Diff #170188)

This is a good FIXME to carry over to FileSymbols::buildIndex(). It may (or may not) make sense to control this behavior with the same param that controls merge behavior, the logic being that it's also a quality/accuracy tradeoff.

clangd/index/FileIndex.h

49 ↗

(On Diff #170188)

FileSymbols isn't actually that opinionated about the data it manages:

• the keys ("filenames") just identify shards so we can tell whether a new shard is an addition or replaces an existing one.
• the values (tu symbols/refs) are merged using pretty generic logic, we don't look at the details.

I think we should be able to use FileSymbols mostly unmodified, and store digests in parallel, probably in BackgroundIndexer. Is there a strong reason to store "main file" digests separately to header digests?

There are a couple of weak points:

• The merging makes subtle assumptions: for symbols it picks one copy arbitrarily, assuming there are many copies (merging would be expensive) and they're mostly interchangeable duplicates. We could add a constructor or buildIndex() param to FileSymbols to control this, similar to the IndexType param. (For refs it assumes no duplicates and simply concatenates, which is also fine for our purposes).
• FileSymbols locks internally to be threadsafe while keeping critical sections small. To keep digests in sync with FileSymbols contents we probably have to lock externally with a second mutex. This is a little ugly but not a real problem I think.

clangd/index/IndexAction.h

31 ↗

(On Diff #170188)

these parallel callbacks that always get called together are a bit ridiculous (my fault).
Can you add a FIXME to replace them with a single callback that passes a struct?

[ioeric]

• address review comments
• minor cleanup

[ioeric]

clangd/index/FileIndex.h

49 ↗

(On Diff #170188)

Good idea! Thanks!

FileSymbols locks internally to be threadsafe while keeping critical sections small. To keep digests in sync with FileSymbols contents we probably have to lock externally with a second mutex. This is a little ugly but not a real problem I think.

This doesn't seem to be a problem as Background::index() currently assumes single-thread? I can either make it thread-safe now or add a FIXME. WDYT?

[sammccall]

clangd/index/Background.h

68 ↗

(On Diff #170440)

Keying this with file URIs seems suspicious to me - why this change?

It seems to be motivated by the current implementation where the partitioning is done post-hoc by looking at strings that contain file URIs.
But this seems likely to change in the long term, and producing data that's sharded in the first place. At that point it'll be just as natural and semantically cleaner just to use file paths, I think.

If performance of converting URI -> path is a concern in the meantime, can we just add a cache to that loop?

clangd/index/FileIndex.cpp

121 ↗

(On Diff #170440)

I don't think you want to build a new slab and copy all the strings here.

This seems like it's saving data (you're not keeping everything alive!) but in practice that only allows GC of data that changes, and most data doesn't change. So mostly this just introduces another copy of the data.

So I think you just want a vector<Symbol> MergedSymbols, and either push all the pointers in there or use concat(make_pointee_range(SymbolPointers), MergedSymbols)

clangd/index/FileIndex.h

41 ↗

(On Diff #170440)

as noted elsewhere I think this is the wrong place for this decl.
The values are somewhat self-explanatory, but the keys need to be documented.

68 ↗

(On Diff #170440)

can we pull out something like enum class DuplicateHandling { PickOne, Merge }?

I think that's much clearer at the callsite than /*MergeSymbols=*/true, and not really longer.

49 ↗

(On Diff #170188)

Right, currently we're only reading/writing with a single thread. The mutex thing is more for the future. Don't bother with a FIXME, when we add multiple threads we'll need to work out what to lock.

clangd/index/IndexAction.h

12 ↗

(On Diff #170440)

This looks like an inverted dependency. The FileDigests struct should be part of symbolcollector, no?

33 ↗

(On Diff #170440)

thinking about what we eventually want here:

• the index action needs to tell the auto-indexer what the file content or digests are
• the auto-indexer needs to tell the index action which files to index symbols from
• this decision is in turn based on the digests

What about this design:

• createStaticIndexingAction accepts a filter-function: "should we index symbols from file X"?
• SymbolCollector invokes this once per file and caches the result.
• the signature is something like bool(SourceManager&, FileEntry*)
• auto-index passes a function that reads the contents from the FileEntry, checks whether the hash is up-to-date to return true/false, and stores the resulting hashes for later

That way the caching/hash stuff never actually leaks outside auto-index that needs it, and we get the interface we need to precisely avoid generating Symbols we don't want.

(That function could just always return true in this patch, if the filtering isn't trivial).

It would mean that auto-index would need to redundantly compute the URI once per file, I don't think that matters.

[ioeric]

• address review comments
• merged with origin/master
• Cleanup

clangd/index/IndexAction.h

33 ↗

(On Diff #170440)

This indeed sounds like a better design for the long term use. Thanks!

[ioeric]

• minor cleanup and a friendly ping.

[sammccall]

Great stuff! Just nits (though a few of them; this is a tricky patch!).

clangd/index/Background.cpp

122 ↗

(On Diff #171467)

static rather than inline?

135 ↗

(On Diff #171467)

Might be cleanest to wrap the cache, the URISchemes&, the hint path, and this function into a tiny class

160 ↗

(On Diff #171467)

Maybe add a comment "eventually SymbolCollector may do this for us to avoid all this copying"?

311 ↗

(On Diff #171467)

It looks like you never write the FilesToUpdate hashes back to the IndexedFileDigests, so we'll always update headers?

clangd/index/Background.h

55 ↗

(On Diff #171467)

private.

75 ↗

(On Diff #171467)

There's no need for this to be global to the class, it's going to cause some hassle once there are multiple worker threads.

I think can a cache can be scoped to a single call to update() (and both it and uriToPath() can be hidden in the cpp file.)

clangd/index/FileIndex.cpp

123 ↗

(On Diff #171467)

comment is stale

140 ↗

(On Diff #171467)

since we're deduplicating above, we could deduplicate here too and remove the deduplicating logic from Dex (MemIndex gets it by mistake). That would avoid duplicated deduplication (!) in the Merge + Dex case, and seems a little cleaner.

Not something for this patch, but maybe add a FIXME.

clangd/index/SymbolCollector.cpp

212 ↗

(On Diff #171467)

nit: simplify logic by inverting the if here and sharing the return?

441 ↗

(On Diff #171467)

why is this hoisted above shouldIndexFile? or did you mean to use DefLoc below?

442 ↗

(On Diff #171467)

just to check - this is basically trivial to do now but would need tests etc?
(fine to defer from this patch)

clangd/index/SymbolCollector.h

78 ↗

(On Diff #171467)

I think we should explicitly test this in SymbolCollectorTests - I think it should be straightforward?

unittests/clangd/BackgroundIndexTests.cpp

28 ↗

(On Diff #171467)

stale comment?

29 ↗

(On Diff #171467)

nit: R"cpp(

33 ↗

(On Diff #171467)

naming here seems confusing: A_H seems to refer to the header, but then what does B_H refer to?

40 ↗

(On Diff #171467)

these should be raw strings now I think (sorry, the old test was already marginal)

[ioeric]

• address review comments.

clangd/index/Background.cpp

311 ↗

(On Diff #171467)

It's updated in update when slabs are updated.

clangd/index/Background.h

55 ↗

(On Diff #171467)

These are also used in some helpers in the cpp file. I can make these private and make those helper members if you think it would be better?

clangd/index/FileIndex.cpp

140 ↗

(On Diff #171467)

Added the duduplication for the PickOne case.

clangd/index/SymbolCollector.cpp

442 ↗

(On Diff #171467)

Do you mean just do this for macros for now? Yes, changes for macros should be trivial.

clangd/index/SymbolCollector.h

78 ↗

(On Diff #171467)

This should be trivial for macros, but we still need some refactoring to make it work for symbols (e.g. addDeclaration doesn't support dropping symbols).

unittests/clangd/BackgroundIndexTests.cpp

33 ↗

(On Diff #171467)

Changed to A_CC and B_CC

[sammccall]

clangd/index/Background.cpp

311 ↗

(On Diff #171467)

In that case, do we need to update IndexedFileDigests here too?

(I just realized there's an edge case: what if there are no symbols or references in a file? but I'm not sure if this is different between mainfile and headers, either)

clangd/index/Background.h

55 ↗

(On Diff #171467)

oops, true. I'd suggest splitting the difference and keeping FileDigest public and dropping the FileDigests alias altogether, but up to you.

clangd/index/FileIndex.cpp

140 ↗

(On Diff #171467)

Thanks! The FIXME is still warranted, to remove deduping from Dex.

[kadircet]

clangd/index/SymbolCollector.cpp

619 ↗

(On Diff #171684)

ND.getASTContext().getSourceManager() -> SM ?

[ioeric]

• Merged with multi-threading changes. Added mutex for file digests.

[ioeric]

Made some more changes to make the code work in multiple threads (add mutex for digests, take snapshot of digests for each run etc). PTAL

clangd/index/Background.cpp

311 ↗

(On Diff #171467)

The edge case seems to justify the update here. We want to make sure that hash for main files are always updated, even when there's no index data from it.

clangd/index/FileIndex.cpp

140 ↗

(On Diff #171467)

Done. I removed it in this patch as it seems trivial enough.

[sammccall]

clangd/index/Background.cpp

194 ↗

(On Diff #171901)

um, this (before your patch) doesn't look even slightly threadsafe. Sorry I didn't catch it in code review.

Now I'm not sure whether it makes sense for you to fix it or not. It seems fine to use two independent locks here, to me - we don't need actual consistency.

unittests/clangd/DexTests.cpp

494 ↗

(On Diff #171901)

at this point we should remove the corresponding test for MemIndex (in IndexTests.cpp I think) too

[kadircet]

clangd/index/Background.cpp

194 ↗

(On Diff #171901)

Ah, sorry for missing on my side as well. But IIUC, the only unsafe part is access to FileHash since FileSymbols::update is already thread-safe ?

If need be I can send out a patch to fix those issues.

[sammccall]

clangd/index/Background.cpp

194 ↗

(On Diff #171901)

Oops, you're right - I forgot FileSymbols was threadsafe.

Then I think FileHash itself is indeed the only issue and this patch (DigestsMu) fixes it already. Carry on!

[kadircet]

clangd/index/Background.cpp

235 ↗

(On Diff #171901)

This call is already thread-safe, no need for it to be under lock.

[ioeric]

clangd/index/Background.cpp

235 ↗

(On Diff #171901)

This is for making sure that the update of digest and index data is atomic. If FileSymbols update is not in the lock, we might get the wrong digest for the indexed symbols in corner cases (e.g. T1 updates digest -> T2 updates digest -> T2 update symbols -> T1 updates symbols ).

[ioeric]

• Rebase

clang-tools-extra/trunk/clangd/index/Background.h

 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
 
 #include "Context.h"
 #include "FSProvider.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/Threading.h"
 #include <condition_variable>
 #include <deque>
 #include <string>
 #include <thread>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Builds an in-memory index by by running the static indexer action over
 // all commands in a compilation database. Indexing happens in the background.
 // FIXME: it should also persist its state on disk for fast start.
 // FIXME: it should watch for changes to files on disk.
 class BackgroundIndex : public SwapIndex {
 public:
   // FIXME: resource-dir injection should be hoisted somewhere common.
   BackgroundIndex(Context BackgroundContext, StringRef ResourceDir,
-                  const FileSystemProvider &,
-                  ArrayRef<std::string> URISchemes = {},
+                  const FileSystemProvider &, ArrayRef<std::string> URISchemes,
                   size_t ThreadPoolSize = llvm::hardware_concurrency());
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue a translation unit for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(llvm::StringRef Directory, tooling::CompileCommand);
   // Index all TUs described in the compilation database.
   void enqueueAll(llvm::StringRef Directory,
                   const tooling::CompilationDatabase &);
 
   // Cause background threads to stop after ther current task, any remaining
   // tasks will be discarded.
   void stop();
 
   // Wait until the queue is empty, to allow deterministic testing.
   void blockUntilIdleForTest();
 
+  using FileDigest = decltype(llvm::SHA1::hash({}));
+
 private:
+  /// Given index results from a TU, only update files in \p FilesToUpdate.
+  void update(llvm::StringRef MainFile, SymbolSlab Symbols, RefSlab Refs,
+              const llvm::StringMap<FileDigest> &FilesToUpdate);
+
   // configuration
   std::string ResourceDir;
   const FileSystemProvider &FSProvider;
   Context BackgroundContext;
   std::vector<std::string> URISchemes;
 
   // index state
   llvm::Error index(tooling::CompileCommand);
-  FileSymbols IndexedSymbols; // Index contents.
-  using Hash = decltype(llvm::SHA1::hash({}));
-  llvm::StringMap<Hash> FileHash; // Digest of indexed file.
+
+  FileSymbols IndexedSymbols;
+  llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
+  std::mutex DigestsMu;
 
   // queue management
   using Task = std::function<void()>;
   void run(); // Main loop executed by Thread. Runs tasks from Queue.
   void enqueueLocked(tooling::CompileCommand Cmd);
   std::mutex QueueMu;
   unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
   std::condition_variable QueueCV;

clang-tools-extra/trunk/clangd/index/Background.cpp

 //===-- Background.cpp - Build an index in a background thread ------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "index/Background.h"
 #include "ClangdUnit.h"
 #include "Compiler.h"
 #include "Logger.h"
 #include "Threading.h"
 #include "Trace.h"
+#include "URI.h"
 #include "index/IndexAction.h"
 #include "index/MemIndex.h"
 #include "index/Serialization.h"
+#include "index/SymbolCollector.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/SHA1.h"
 #include <random>
+#include <string>
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 BackgroundIndex::BackgroundIndex(Context BackgroundContext,
                                  StringRef ResourceDir,
                                  const FileSystemProvider &FSProvider,
Queue.push_back(Bind(
         std::string Filename = Cmd.Filename;
         Cmd.CommandLine.push_back("-resource-dir=" + ResourceDir);
         if (auto Error = index(std::move(Cmd)))
           log("Indexing {0} failed: {1}", Filename, std::move(Error));
       },
       std::move(Cmd)));
 }
 
+static BackgroundIndex::FileDigest digest(StringRef Content) {
+  return SHA1::hash({(const uint8_t *)Content.data(), Content.size()});
+}
+
+static Optional<BackgroundIndex::FileDigest> digestFile(const SourceManager &SM,
+                                                        FileID FID) {
+  bool Invalid = false;
+  StringRef Content = SM.getBufferData(FID, &Invalid);
+  if (Invalid)
+    return None;
+  return digest(Content);
+}
+
+// Resolves URI to file paths with cache.
+class URIToFileCache {
+public:
+  URIToFileCache(llvm::StringRef HintPath) : HintPath(HintPath) {}
+
+  llvm::StringRef resolve(llvm::StringRef FileURI) {
+    auto I = URIToPathCache.try_emplace(FileURI);
+    if (I.second) {
+      auto U = URI::parse(FileURI);
+      if (!U) {
+        elog("Failed to parse URI {0}: {1}", FileURI, U.takeError());
+        assert(false && "Failed to parse URI");
+        return "";
+      }
+      auto Path = URI::resolve(*U, HintPath);
+      if (!Path) {
+        elog("Failed to resolve URI {0}: {1}", FileURI, Path.takeError());
+        assert(false && "Failed to resolve URI");
+        return "";
+      }
+      I.first->second = *Path;
+    }
+    return I.first->second;
+  }
+
+private:
+  std::string HintPath;
+  llvm::StringMap<std::string> URIToPathCache;
+};
+
+/// Given index results from a TU, only update files in \p FilesToUpdate.
+void BackgroundIndex::update(StringRef MainFile, SymbolSlab Symbols,
+                             RefSlab Refs,
+                             const StringMap<FileDigest> &FilesToUpdate) {
+  // Partition symbols/references into files.
+  struct File {
+    DenseSet<const Symbol *> Symbols;
+    DenseSet<const Ref *> Refs;
+  };
+  StringMap<File> Files;
+  URIToFileCache URICache(MainFile);
+  for (const auto &Sym : Symbols) {
+    if (Sym.CanonicalDeclaration) {
+      auto DeclPath = URICache.resolve(Sym.CanonicalDeclaration.FileURI);
+      if (FilesToUpdate.count(DeclPath) != 0)
+        Files[DeclPath].Symbols.insert(&Sym);
+    }
+    // For symbols with different declaration and definition locations, we store
+    // the full symbol in both the header file and the implementation file, so
+    // that merging can tell the preferred symbols (from canonical headers) from
+    // other symbols (e.g. forward declarations).
+    if (Sym.Definition &&
+        Sym.Definition.FileURI != Sym.CanonicalDeclaration.FileURI) {
+      auto DefPath = URICache.resolve(Sym.Definition.FileURI);
+      if (FilesToUpdate.count(DefPath) != 0)
+        Files[DefPath].Symbols.insert(&Sym);
+    }
+  }
+  DenseMap<const Ref *, SymbolID> RefToIDs;
+  for (const auto &SymRefs : Refs) {
+    for (const auto &R : SymRefs.second) {
+      auto Path = URICache.resolve(R.Location.FileURI);
+      if (FilesToUpdate.count(Path) != 0) {
+        auto &F = Files[Path];
+        RefToIDs[&R] = SymRefs.first;
+        F.Refs.insert(&R);
+      }
+    }
+  }
+
+  // Build and store new slabs for each updated file.
+  for (const auto &F : Files) {
+    StringRef Path = F.first();
+    vlog("Update symbols in {0}", Path);
+    SymbolSlab::Builder Syms;
+    RefSlab::Builder Refs;
+    for (const auto *S : F.second.Symbols)
+      Syms.insert(*S);
+    for (const auto *R : F.second.Refs)
+      Refs.insert(RefToIDs[R], *R);
+
+    std::lock_guard<std::mutex> Lock(DigestsMu);
+    // This can override a newer version that is added in another thread,
+    // if this thread sees the older version but finishes later. This should be
+    // rare in practice.
+    IndexedFileDigests[Path] = FilesToUpdate.lookup(Path);
+    IndexedSymbols.update(Path,
+                          make_unique<SymbolSlab>(std::move(Syms).build()),
+                          make_unique<RefSlab>(std::move(Refs).build()));
+  }
+}
+
+// Creates a filter to not collect index results from files with unchanged
+// digests.
+// \p FileDigests contains file digests for the current indexed files, and all changed files will be added to \p FilesToUpdate.
+decltype(SymbolCollector::Options::FileFilter) createFileFilter(
+    const llvm::StringMap<BackgroundIndex::FileDigest> &FileDigests,
+    llvm::StringMap<BackgroundIndex::FileDigest> &FilesToUpdate) {
+  return [&FileDigests, &FilesToUpdate](const SourceManager &SM, FileID FID) {
+    StringRef Path;
+    if (const auto *F = SM.getFileEntryForID(FID))
+      Path = F->getName();
+    if (Path.empty())
+      return false; // Skip invalid files.
+    SmallString<128> AbsPath(Path);
+    if (std::error_code EC =
+            SM.getFileManager().getVirtualFileSystem()->makeAbsolute(AbsPath)) {
+      elog("Warning: could not make absolute file: {0}", EC.message());
+      return false; // Skip files without absolute path.
+    }
+    sys::path::remove_dots(AbsPath, /*remove_dot_dot=*/true);
+    auto Digest = digestFile(SM, FID);
+    if (!Digest)
+      return false;
+    auto D = FileDigests.find(AbsPath);
+    if (D != FileDigests.end() && D->second == Digest)
+      return false; // Skip files that haven't changed.
+
+    FilesToUpdate[AbsPath] = *Digest;
+    return true;
+  };
+}
+
 Error BackgroundIndex::index(tooling::CompileCommand Cmd) {
   trace::Span Tracer("BackgroundIndex");
   SPAN_ATTACH(Tracer, "file", Cmd.Filename);
   SmallString<128> AbsolutePath;
   if (sys::path::is_absolute(Cmd.Filename)) {
     AbsolutePath = Cmd.Filename;
   } else {
     AbsolutePath = Cmd.Directory;
     sys::path::append(AbsolutePath, Cmd.Filename);
   }
 
   auto FS = FSProvider.getFileSystem();
   auto Buf = FS->getBufferForFile(AbsolutePath);
   if (!Buf)
     return errorCodeToError(Buf.getError());
-  StringRef Contents = Buf->get()->getBuffer();
-  auto Hash = SHA1::hash({(const uint8_t *)Contents.data(), Contents.size()});
+  auto Hash = digest(Buf->get()->getBuffer());
 
-  if (FileHash.lookup(AbsolutePath) == Hash) {
+  // Take a snapshot of the digests to avoid locking for each file in the TU.
+  llvm::StringMap<FileDigest> DigestsSnapshot;
+  {
+    std::lock_guard<std::mutex> Lock(DigestsMu);
+    if (IndexedFileDigests.lookup(AbsolutePath) == Hash) {
       vlog("No need to index {0}, already up to date", AbsolutePath);
       return Error::success();
     }
 
+    DigestsSnapshot = IndexedFileDigests;
+  }
+
   log("Indexing {0}", Cmd.Filename, toHex(Hash));
   ParseInputs Inputs;
   Inputs.FS = std::move(FS);
   Inputs.FS->setCurrentWorkingDirectory(Cmd.Directory);
   Inputs.CompileCommand = std::move(Cmd);
   auto CI = buildCompilerInvocation(Inputs);
   if (!CI)
     return createStringError(inconvertibleErrorCode(),
                              "Couldn't build compiler invocation");
   IgnoreDiagnostics IgnoreDiags;
   auto Clang = prepareCompilerInstance(
       std::move(CI), /*Preamble=*/nullptr, std::move(*Buf),
       std::make_shared<PCHContainerOperations>(), Inputs.FS, IgnoreDiags);
   if (!Clang)
     return createStringError(inconvertibleErrorCode(),
                              "Couldn't build compiler instance");
 
   SymbolCollector::Options IndexOpts;
+  IndexOpts.URISchemes = URISchemes;
+  StringMap<FileDigest> FilesToUpdate;
+  IndexOpts.FileFilter = createFileFilter(DigestsSnapshot, FilesToUpdate);
   SymbolSlab Symbols;
   RefSlab Refs;
-  IndexFileIn IndexData;
   auto Action = createStaticIndexingAction(
       IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); },
       [&](RefSlab R) { Refs = std::move(R); });
 
   // We're going to run clang here, and it could potentially crash.
   // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
   // but the leaky "recovery" is pretty scary too in a long-running process.
   // If crashes are a real problem, maybe we should fork a child process.
 
   const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
   if (!Action->BeginSourceFile(*Clang, Input))
     return createStringError(inconvertibleErrorCode(),
                              "BeginSourceFile() failed");
   if (!Action->Execute())
     return createStringError(inconvertibleErrorCode(), "Execute() failed");
   Action->EndSourceFile();
 
   log("Indexed {0} ({1} symbols, {2} refs)", Inputs.CompileCommand.Filename,
       Symbols.size(), Refs.numRefs());
   SPAN_ATTACH(Tracer, "symbols", int(Symbols.size()));
   SPAN_ATTACH(Tracer, "refs", int(Refs.numRefs()));
-  // FIXME: partition the symbols by file rather than TU, to avoid duplication.
-  IndexedSymbols.update(AbsolutePath,
-                        llvm::make_unique<SymbolSlab>(std::move(Symbols)),
-                        llvm::make_unique<RefSlab>(std::move(Refs)));
-  FileHash[AbsolutePath] = Hash;
+  update(AbsolutePath, std::move(Symbols), std::move(Refs), FilesToUpdate);
+  {
+    // Make sure hash for the main file is always updated even if there is no
+    // index data in it.
+    std::lock_guard<std::mutex> Lock(DigestsMu);
+    IndexedFileDigests[AbsolutePath] = Hash;
+  }
 
   // FIXME: this should rebuild once-in-a-while, not after every file.
   //       At that point we should use Dex, too.
   vlog("Rebuilding automatic index");
-  reset(IndexedSymbols.buildIndex(IndexType::Light, URISchemes));
+  reset(IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge,
+                                  URISchemes));
+
   return Error::success();
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/FileIndex.h

 /// Select between in-memory index implementations, which have tradeoffs.
 enum class IndexType {
   // MemIndex is trivially cheap to build, but has poor query performance.
   Light,
   // Dex is relatively expensive to build and uses more memory, but is fast.
   Heavy,
 };
 
+/// How to handle duplicated symbols across multiple files.
+enum class DuplicateHandling {
+  // Pick a random symbol. Less accurate but faster.
+  PickOne,
+  // Merge symbols. More accurate but slower.
+  Merge,
+};
+
 /// A container of Symbols from several source files. It can be updated
 /// at source-file granularity, replacing all symbols from one file with a new
 /// set.
 ///
 /// This implements a snapshot semantics for symbols in a file. Each update to a
 /// file will create a new snapshot for all symbols in the file. Snapshots are
 /// managed with shared pointers that are shared between this class and the
 /// users. For each file, this class only stores a pointer pointing to the
 /// newest snapshot, and an outdated snapshot is deleted by the last owner of
 /// the snapshot, either this class or the symbol index.
 ///
 /// The snapshot semantics keeps critical sections minimal since we only need
 /// locking when we swap or obtain references to snapshots.
 class FileSymbols {
 public:
   /// Updates all symbols and refs in a file.
   /// If either is nullptr, corresponding data for \p Path will be removed.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
               std::unique_ptr<RefSlab> Refs);
 
   // The index keeps the symbols alive.
   std::unique_ptr<SymbolIndex>
-  buildIndex(IndexType, ArrayRef<std::string> URISchemes = {});
+  buildIndex(IndexType,
+             DuplicateHandling DuplicateHandle = DuplicateHandling::PickOne,
+             ArrayRef<std::string> URISchemes = {});
 
 private:
   mutable std::mutex Mutex;
 
   /// Stores the latest symbol snapshots for all active files.
   llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSymbols;
   /// Stores the latest ref snapshots for all active files.
   llvm::StringMap<std::shared_ptr<RefSlab>> FileToRefs;

clang-tools-extra/trunk/clangd/index/FileIndex.cpp

 //===--- FileIndex.cpp - Indexes for files. ------------------------ C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "FileIndex.h"
 #include "ClangdUnit.h"
 #include "Logger.h"
 #include "SymbolCollector.h"
 #include "index/Index.h"
+#include "index/MemIndex.h"
 #include "index/Merge.h"
 #include "index/dex/Dex.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Preprocessor.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
 #include <memory>
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 static std::pair<SymbolSlab, RefSlab>
 indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
else
     FileToSymbols[Path] = std::move(Symbols);
   if (!Refs)
     FileToRefs.erase(Path);
   else
     FileToRefs[Path] = std::move(Refs);
 }
 
 std::unique_ptr<SymbolIndex>
-FileSymbols::buildIndex(IndexType Type, ArrayRef<std::string> URISchemes) {
+FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle,
+                        ArrayRef<std::string> URISchemes) {
   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto &FileAndSymbols : FileToSymbols)
       SymbolSlabs.push_back(FileAndSymbols.second);
     for (const auto &FileAndRefs : FileToRefs)
       RefSlabs.push_back(FileAndRefs.second);
   }
   std::vector<const Symbol *> AllSymbols;
+  std::vector<Symbol> SymsStorage;
+  switch (DuplicateHandle) {
+  case DuplicateHandling::Merge: {
+    DenseMap<SymbolID, Symbol> Merged;
+    for (const auto &Slab : SymbolSlabs) {
+      for (const auto &Sym : *Slab) {
+        auto I = Merged.try_emplace(Sym.ID, Sym);
+        if (!I.second)
+          I.first->second = mergeSymbol(std::move(I.first->second), Sym);
+      }
+    }
+    SymsStorage.reserve(Merged.size());
+    for (auto &Sym : Merged) {
+      SymsStorage.push_back(std::move(Sym.second));
+      AllSymbols.push_back(&SymsStorage.back());
+    }
+    // FIXME: aggregate symbol reference count based on references.
+    break;
+  }
+  case DuplicateHandling::PickOne: {
+    llvm::DenseSet<SymbolID> AddedSymbols;
     for (const auto &Slab : SymbolSlabs)
       for (const auto &Sym : *Slab)
+        if (AddedSymbols.insert(Sym.ID).second)
           AllSymbols.push_back(&Sym);
+    break;
+  }
+  }
 
   std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
   DenseMap<SymbolID, ArrayRef<Ref>> AllRefs;
   {
     DenseMap<SymbolID, SmallVector<Ref, 4>> MergedRefs;
     size_t Count = 0;
     for (const auto &RefSlab : RefSlabs)
       for (const auto &Sym : *RefSlab) {
for (auto &Sym : MergedRefs) {
       llvm::copy(SymRefs, back_inserter(RefsStorage));
       AllRefs.try_emplace(
           Sym.first,
           ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
                         SymRefs.size()));
     }
   }
 
-  size_t StorageSize = RefsStorage.size() * sizeof(Ref);
+  size_t StorageSize =
+      RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
   for (const auto &Slab : SymbolSlabs)
     StorageSize += Slab->bytes();
   for (const auto &RefSlab : RefSlabs)
     StorageSize += RefSlab->bytes();
 
   // Index must keep the slabs and contiguous ranges alive.
   switch (Type) {
   case IndexType::Light:
     return llvm::make_unique<MemIndex>(
         make_pointee_range(AllSymbols), std::move(AllRefs),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
-                        std::move(RefsStorage)),
+                        std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   case IndexType::Heavy:
     return llvm::make_unique<dex::Dex>(
         make_pointee_range(AllSymbols), std::move(AllRefs),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
-                        std::move(RefsStorage)),
+                        std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize, std::move(URISchemes));
   }
   llvm_unreachable("Unknown clangd::IndexType");
 }
 
 FileIndex::FileIndex(std::vector<std::string> URISchemes, bool UseDex)
     : MergedIndex(&MainFileIndex, &PreambleIndex), UseDex(UseDex),
       URISchemes(std::move(URISchemes)),
       PreambleIndex(llvm::make_unique<MemIndex>()),
       MainFileIndex(llvm::make_unique<MemIndex>()) {}
 
 void FileIndex::updatePreamble(PathRef Path, ASTContext &AST,
                                std::shared_ptr<Preprocessor> PP) {
   auto Symbols = indexHeaderSymbols(AST, std::move(PP), URISchemes);
   PreambleSymbols.update(Path,
                          llvm::make_unique<SymbolSlab>(std::move(Symbols)),
                          llvm::make_unique<RefSlab>());
-  PreambleIndex.reset(PreambleSymbols.buildIndex(
-      UseDex ? IndexType::Heavy : IndexType::Light, URISchemes));
+  PreambleIndex.reset(
+      PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
+                                 DuplicateHandling::PickOne, URISchemes));
 }
 
 void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
   auto Contents = indexMainDecls(AST, URISchemes);
   MainFileSymbols.update(
       Path, llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
       llvm::make_unique<RefSlab>(std::move(Contents.second)));
-  MainFileIndex.reset(MainFileSymbols.buildIndex(IndexType::Light, URISchemes));
+  MainFileIndex.reset(MainFileSymbols.buildIndex(
+      IndexType::Light, DuplicateHandling::PickOne, URISchemes));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/SymbolCollector.h

 //===--- SymbolCollector.h ---------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_COLLECTOR_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_COLLECTOR_H
 
 #include "CanonicalIncludes.h"
 #include "Index.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
+#include "llvm/ADT/DenseMap.h"
+#include <functional>
 
 namespace clang {
 namespace clangd {
 
 /// \brief Collect declarations (symbols) from an AST.
 /// It collects most declarations except:
 /// - Implicit declarations
 /// - Anonymous declarations (anonymous enum/class/struct, etc)
struct Options {
     bool RefsInHeaders = false;
     // Every symbol collected will be stamped with this origin.
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     /// Collect macros.
     /// Note that SymbolCollector must be run with preprocessor in order to
     /// collect macros. For example, `indexTopLevelDecls` will not index any
     /// macro even if this is true.
     bool CollectMacro = false;
+    /// If this is set, only collect symbols/references from a file if
+    /// `FileFilter(SM, FID)` is true. If not set, all files are indexed.
+    std::function<bool(const SourceManager &, FileID)> FileFilter = nullptr;
   };
 
   SymbolCollector(Options Opts);
 
   /// Returns true is \p ND should be collected.
   /// AST matchers require non-const ASTContext.
   static bool shouldCollectSymbol(const NamedDecl &ND, ASTContext &ASTCtx,
                                   const Options &Opts);
private:
   llvm::DenseSet<const IdentifierInfo *> ReferencedMacros;
   llvm::DenseMap<const NamedDecl *, std::vector<DeclRef>> DeclRefs;
   // Maps canonical declaration provided by clang to canonical declaration for
   // an index symbol, if clangd prefers a different declaration than that
   // provided by clang. For example, friend declaration might be considered
   // canonical by clang but should not be considered canonical in the index
   // unless it's a definition.
   llvm::DenseMap<const Decl *, const Decl *> CanonicalDecls;
+  // Cache whether to index a file or not.
+  llvm::DenseMap<FileID, bool> FilesToIndexCache;
 };
 
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/trunk/clangd/index/SymbolCollector.cpp

auto CreatePosition = [&SM](SourceLocation Loc) {
     return Pos;
   };
 
   auto TokenLength = clang::Lexer::MeasureTokenLength(TokLoc, SM, LangOpts);
   return {CreatePosition(TokLoc),
           CreatePosition(TokLoc.getLocWithOffset(TokenLength))};
 }
 
+bool shouldIndexFile(const SourceManager &SM, FileID FID,
+                     const SymbolCollector::Options &Opts,
+                     llvm::DenseMap<FileID, bool> *FilesToIndexCache) {
+  if (!Opts.FileFilter)
+    return true;
+  auto I = FilesToIndexCache->try_emplace(FID);
+  if (I.second)
+    I.first->second = Opts.FileFilter(SM, FID);
+  return I.first->second;
+}
+
 // Return the symbol location of the token at \p TokLoc.
 Optional<SymbolLocation> getTokenLocation(SourceLocation TokLoc,
                                           const SourceManager &SM,
                                           const SymbolCollector::Options &Opts,
                                           const clang::LangOptions &LangOpts,
                                           std::string &FileURIStorage) {
   auto U = toURI(SM, SM.getFilename(TokLoc), Opts);
   if (!U)
bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
                                            const MacroInfo *MI,
                                            index::SymbolRoleSet Roles,
                                            SourceLocation Loc) {
   if (!Opts.CollectMacro)
     return true;
   assert(PP.get());
 
   const auto &SM = PP->getSourceManager();
-  if (SM.isInMainFile(SM.getExpansionLoc(MI->getDefinitionLoc())))
+  auto DefLoc = MI->getDefinitionLoc();
+  if (SM.isInMainFile(SM.getExpansionLoc(DefLoc)))
     return true;
   // Header guards are not interesting in index. Builtin macros don't have
   // useful locations and are not needed for code completions.
   if (MI->isUsedForHeaderGuard() || MI->isBuiltinMacro())
     return true;
 
   // Mark the macro as referenced if this is a reference coming from the main
   // file. The macro may not be an interesting symbol, but it's cheaper to check
if (Symbols.find(*ID) != nullptr)
     return true;
 
   Symbol S;
   S.ID = std::move(*ID);
   S.Name = Name->getName();
   S.Flags |= Symbol::IndexedForCodeCompletion;
   S.SymInfo = index::getSymbolInfoForMacro(*MI);
   std::string FileURI;
-  if (auto DeclLoc = getTokenLocation(MI->getDefinitionLoc(), SM, Opts,
-                                      PP->getLangOpts(), FileURI))
+  // FIXME: use the result to filter out symbols.
+  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  if (auto DeclLoc =
+          getTokenLocation(DefLoc, SM, Opts, PP->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
   CodeCompletionResult SymbolCompletion(Name);
   const auto *CCS = SymbolCompletion.CreateCodeCompletionStringForMacro(
       *PP, *CompletionAllocator, *CompletionTUInfo);
   std::string Signature;
   std::string SnippetSuffix;
   getSignature(*CCS, &Signature, &SnippetSuffix);
 
   std::string Include;
   if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
-    if (auto Header =
-            getIncludeHeader(Name->getName(), SM,
-                             SM.getExpansionLoc(MI->getDefinitionLoc()), Opts))
+    if (auto Header = getIncludeHeader(Name->getName(), SM,
+                                       SM.getExpansionLoc(DefLoc), Opts))
       Include = std::move(*Header);
   }
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
   if (!Include.empty())
     S.IncludeHeaders.emplace_back(Include, 1);
 
   Symbols.insert(S);
auto GetURI = [&](FileID FID) -> Optional<std::string> {
     return Found->second;
   };
 
   if (auto MainFileURI = GetURI(SM.getMainFileID())) {
     for (const auto &It : DeclRefs) {
       if (auto ID = getSymbolID(It.first)) {
         for (const auto &LocAndRole : It.second) {
           auto FileID = SM.getFileID(LocAndRole.first);
+          // FIXME: use the result to filter out references.
+          shouldIndexFile(SM, FileID, Opts, &FilesToIndexCache);
           if (auto FileURI = GetURI(FileID)) {
             auto Range =
                 getTokenRange(LocAndRole.first, SM, ASTCtx->getLangOpts());
             Ref R;
             R.Location.Start = Range.first;
             R.Location.End = Range.second;
             R.Location.FileURI = *FileURI;
             R.Kind = toRefKind(LocAndRole.second);
             Refs.insert(*ID, R);
           }
         }
       }
     }
   }
 
   ReferencedDecls.clear();
   ReferencedMacros.clear();
   DeclRefs.clear();
+  FilesToIndexCache.clear();
 }
 
 const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
                                               SymbolID ID) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
 
   Symbol S;
   S.ID = std::move(ID);
   std::string QName = printQualifiedName(ND);
   std::tie(S.Scope, S.Name) = splitQualifiedName(QName);
   // FIXME: this returns foo:bar: for objective-C methods, we prefer only foo:
   // for consistency with CodeCompletionString and a clean name/signature split.
 
   if (isIndexedForCodeCompletion(ND, Ctx))
     S.Flags |= Symbol::IndexedForCodeCompletion;
   if (isImplementationDetail(&ND))
     S.Flags |= Symbol::ImplementationDetail;
   S.SymInfo = index::getSymbolInfo(&ND);
   std::string FileURI;
-  if (auto DeclLoc = getTokenLocation(findNameLoc(&ND), SM, Opts,
-                                      ASTCtx->getLangOpts(), FileURI))
+  auto Loc = findNameLoc(&ND);
+  // FIXME: use the result to filter out symbols.
+  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  if (auto DeclLoc =
+          getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
   // Add completion info.
   // FIXME: we may want to choose a different redecl, or combine from several.
   assert(ASTCtx && PP.get() && "ASTContext and Preprocessor must be set.");
   // We use the primary template, as clang does during code completion.
   CodeCompletionResult SymbolCompletion(&getTemplateOrThis(ND), 0);
   const auto *CCS = SymbolCompletion.CreateCodeCompletionString(
void SymbolCollector::addDefinition(const NamedDecl &ND,
                                     const Symbol &DeclSym) {
   if (DeclSym.Definition)
     return;
   // If we saw some forward declaration, we end up copying the symbol.
   // This is not ideal, but avoids duplicating the "is this a definition" check
   // in clang::index. We should only see one definition.
   Symbol S = DeclSym;
   std::string FileURI;
-  if (auto DefLoc = getTokenLocation(findNameLoc(&ND),
-                                     ND.getASTContext().getSourceManager(),
-                                     Opts, ASTCtx->getLangOpts(), FileURI))
+  auto Loc = findNameLoc(&ND);
+  const auto &SM = ND.getASTContext().getSourceManager();
+  // FIXME: use the result to filter out symbols.
+  shouldIndexFile(SM, SM.getFileID(Loc), Opts, &FilesToIndexCache);
+  if (auto DefLoc =
+          getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.Definition = *DefLoc;
   Symbols.insert(S);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/dex/Dex.h

Dex(SymbolRange &&Symbols, RefsRange &&Refs,
       llvm::ArrayRef<std::string> Schemes)
       : Corpus(0), URISchemes(Schemes) {
     // If Schemes don't contain any items, fall back to SymbolCollector's
     // default URI schemes.
     if (URISchemes.empty()) {
       SymbolCollector::Options Opts;
       URISchemes = Opts.URISchemes;
     }
-    llvm::DenseSet<SymbolID> SeenIDs;
     for (auto &&Sym : Symbols)
-      if (SeenIDs.insert(Sym.ID).second)
-        this->Symbols.push_back(&Sym);
     for (auto &&Ref : Refs)
       this->Refs.try_emplace(Ref.first, Ref.second);
     buildIndex();
   }
   // Symbols and Refs are owned by BackingData, Index takes ownership.
   template <typename SymbolRange, typename RefsRange, typename Payload>
   Dex(SymbolRange &&Symbols, RefsRange &&Refs, Payload &&BackingData,
       size_t BackingDataSize, llvm::ArrayRef<std::string> URISchemes)

clang-tools-extra/trunk/unittests/clangd/BackgroundIndexTests.cpp

 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "index/Background.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
+using testing::_;
+using testing::AllOf;
+using testing::Not;
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
+MATCHER(Declared, "") { return !arg.CanonicalDeclaration.FileURI.empty(); }
+MATCHER(Defined, "") { return !arg.Definition.FileURI.empty(); }
+
+MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
+testing::Matcher<const RefSlab &>
+RefsAre(std::vector<testing::Matcher<Ref>> Matchers) {
+  return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers)));
+}
 
 TEST(BackgroundIndexTest, IndexTwoFiles) {
   MockFSProvider FS;
   // a.h yields different symbols when included by A.cc vs B.cc.
-  // Currently we store symbols for each TU, so we get both.
-  FS.Files[testPath("root/A.h")] = "void a_h(); void NAME(){}";
-  FS.Files[testPath("root/A.cc")] = "#include \"A.h\"";
-  FS.Files[testPath("root/B.cc")] = "#define NAME bar\n#include \"A.h\"";
-  BackgroundIndex Idx(Context::empty(), "", FS);
+  FS.Files[testPath("root/A.h")] = R"cpp(
+      void common();
+      void f_b();
+      #if A
+        class A_CC {};
+      #else
+        class B_CC{};
+      #endif
+      )cpp";
+  FS.Files[testPath("root/A.cc")] =
+      "#include \"A.h\"\nvoid g() { (void)common; }";
+  FS.Files[testPath("root/B.cc")] =
+      R"cpp(
+      #define A 0
+      #include "A.h"
+      void f_b() {
+        (void)common;
+      })cpp";
+  BackgroundIndex Idx(Context::empty(), "", FS, /*URISchmes=*/{"unittest"});
 
   tooling::CompileCommand Cmd;
   Cmd.Filename = testPath("root/A.cc");
   Cmd.Directory = testPath("root");
-  Cmd.CommandLine = {"clang++", "-DNAME=foo", testPath("root/A.cc")};
+  Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
   Idx.enqueue(testPath("root"), Cmd);
-  Cmd.CommandLine.back() = Cmd.Filename = testPath("root/B.cc");
+
+  Idx.blockUntilIdleForTest();
+  EXPECT_THAT(
+      runFuzzyFind(Idx, ""),
+      UnorderedElementsAre(Named("common"), Named("A_CC"),
+                           AllOf(Named("f_b"), Declared(), Not(Defined()))));
+
+  Cmd.Filename = testPath("root/B.cc");
+  Cmd.CommandLine = {"clang++", Cmd.Filename};
   Idx.enqueue(testPath("root"), Cmd);
 
   Idx.blockUntilIdleForTest();
+  // B_CC is dropped as we don't collect symbols from A.h in this compilation.
   EXPECT_THAT(runFuzzyFind(Idx, ""),
-              UnorderedElementsAre(Named("a_h"), Named("foo"), Named("bar")));
+              UnorderedElementsAre(Named("common"), Named("A_CC"),
+                                   AllOf(Named("f_b"), Declared(), Defined())));
+
+  auto Syms = runFuzzyFind(Idx, "common");
+  EXPECT_THAT(Syms, UnorderedElementsAre(Named("common")));
+  auto Common = *Syms.begin();
+  EXPECT_THAT(getRefs(Idx, Common.ID),
+              RefsAre({FileURI("unittest:///root/A.h"),
+                       FileURI("unittest:///root/A.cc"),
+                       FileURI("unittest:///root/B.cc")}));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/unittests/clangd/DexTests.cpp

TEST(Dex, FuzzyFind) {
   Req.Query = "";
   Req.Scopes = {};
   EXPECT_THAT(match(*Index, Req),
               UnorderedElementsAre("ns::ABC", "ns::BCD", "::ABC",
                                    "ns::nested::ABC", "other::ABC",
                                    "other::A"));
 }
 
-TEST(DexTest, DexDeduplicate) {
-  std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"),
-                                 symbol("2") /* duplicate */};
-  FuzzyFindRequest Req;
-  Req.Query = "2";
-  Dex I(Symbols, RefSlab(), URISchemes);
-  EXPECT_THAT(match(I, Req), ElementsAre("2"));
-}
-
 TEST(DexTest, DexLimitedNumMatches) {
   auto I = Dex::build(generateNumSymbols(0, 100), RefSlab(), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.Limit = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
   EXPECT_TRUE(Req.Limit);

clang-tools-extra/trunk/unittests/clangd/FileIndexTests.cpp

 //===-- FileIndexTests.cpp  ---------------------------*- C++ -*-----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AST.h"
 #include "Annotations.h"
 #include "ClangdUnit.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "index/FileIndex.h"
+#include "index/Index.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Frontend/Utils.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"

 MATCHER_P(RefRange, Range, "") {
   return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(),
                          arg.Location.End.line(), arg.Location.End.column()) ==
          std::make_tuple(Range.start.line, Range.start.character,
                          Range.end.line, Range.end.character);
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 MATCHER_P(DeclURI, U, "") { return arg.CanonicalDeclaration.FileURI == U; }
+MATCHER_P(DefURI, U, "") { return arg.Definition.FileURI == U; }
 MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; }
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 namespace {
 testing::Matcher<const RefSlab &>
 RefsAre(std::vector<testing::Matcher<Ref>> Matchers) {
std::unique_ptr<RefSlab> refSlab(const SymbolID &ID, StringRef Path) {
   RefSlab::Builder Slab;
   Ref R;
   R.Location.FileURI = Path;
   R.Kind = RefKind::Reference;
   Slab.insert(ID, R);
   return llvm::make_unique<RefSlab>(std::move(Slab).build());
 }
 
-RefSlab getRefs(const SymbolIndex &I, SymbolID ID) {
-  RefsRequest Req;
-  Req.IDs = {ID};
-  RefSlab::Builder Slab;
-  I.refs(Req, [&](const Ref &S) { Slab.insert(ID, S); });
-  return std::move(Slab).build();
-}
-
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty());
 
   FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"));
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*FS.buildIndex(IndexType::Light), SymbolID("1")),
               RefsAre({FileURI("f1.cc")}));
 }
 
 TEST(FileSymbolsTest, Overlap) {
   FileSymbols FS;
   FS.update("f1", numSlab(1, 3), nullptr);
   FS.update("f2", numSlab(3, 5), nullptr);
   for (auto Type : {IndexType::Light, IndexType::Heavy})
     EXPECT_THAT(runFuzzyFind(*FS.buildIndex(Type), ""),
                 UnorderedElementsAre(QName("1"), QName("2"), QName("3"),
                                      QName("4"), QName("5")));
 }
 
+TEST(FileSymbolsTest, MergeOverlap) {
+  FileSymbols FS;
+  auto OneSymboSlab = [](Symbol Sym) {
+    SymbolSlab::Builder S;
+    S.insert(Sym);
+    return make_unique<SymbolSlab>(std::move(S).build());
+  };
+  auto X1 = symbol("x");
+  X1.CanonicalDeclaration.FileURI = "file:///x1";
+  auto X2 = symbol("x");
+  X2.Definition.FileURI = "file:///x2";
+
+  FS.update("f1", OneSymboSlab(X1), nullptr);
+  FS.update("f2", OneSymboSlab(X2), nullptr);
+  for (auto Type : {IndexType::Light, IndexType::Heavy})
+    EXPECT_THAT(
+        runFuzzyFind(*FS.buildIndex(Type, DuplicateHandling::Merge), "x"),
+        UnorderedElementsAre(
+            AllOf(QName("x"), DeclURI("file:///x1"), DefURI("file:///x2"))));
+}
+
 TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
   FileSymbols FS;
 
   SymbolID ID("1");
   FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"));
 
   auto Symbols = FS.buildIndex(IndexType::Light);
   EXPECT_THAT(runFuzzyFind(*Symbols, ""),

clang-tools-extra/trunk/unittests/clangd/SyncAPI.h

 llvm::Expected<std::vector<SymbolInformation>>
 runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit);
 
 llvm::Expected<std::vector<SymbolInformation>>
 runDocumentSymbols(ClangdServer &Server, PathRef File);
 
 SymbolSlab runFuzzyFind(const SymbolIndex &Index, StringRef Query);
 SymbolSlab runFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req);
+RefSlab getRefs(const SymbolIndex &Index, SymbolID ID);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_SYNCAPI_H

clang-tools-extra/trunk/unittests/clangd/SyncAPI.cpp

 //===--- SyncAPI.cpp - Sync version of ClangdServer's API --------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SyncAPI.h"
+#include "index/Index.h"
 
 using namespace llvm;
 namespace clang {
 namespace clangd {
 
 void runAddDocument(ClangdServer &Server, PathRef File, StringRef Contents,
                     WantDiagnostics WantDiags) {
   Server.addDocument(File, Contents, WantDiags);

 }
 
 SymbolSlab runFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req) {
   SymbolSlab::Builder Builder;
   Index.fuzzyFind(Req, [&](const Symbol &Sym) { Builder.insert(Sym); });
   return std::move(Builder).build();
 }
 
+RefSlab getRefs(const SymbolIndex &Index, SymbolID ID) {
+  RefsRequest Req;
+  Req.IDs = {ID};
+  RefSlab::Builder Slab;
+  Index.refs(Req, [&](const Ref &S) { Slab.insert(ID, S); });
+  return std::move(Slab).build();
+}
+
+
 } // namespace clangd
 } // namespace clang