[clangd] Collect definitions when indexing.

[sammccall]

Summary

Within a TU:

• as now, collect a declaration from the first occurrence of a symbol (taking clang's canonical declaration)
• when we first see a definition occurrence, copy the symbol and add it

Across TUs/sources:

• mergeSymbol in Merge.h is responsible for combining matching Symbols. This covers dynamic/static merges and cross-TU merges in the static index.
• it prefers declarations from Symbols that have a definition.
• GlobalSymbolBuilderMain is modified to use mergeSymbol as a reduce step.

Random cleanups (can be pulled out):

• SymbolFromYAML -> SymbolsFromYAML, new singular SymbolFromYAML added
• avoid uninit'd SymbolLocations. Add an idiomatic way to check "absent".
• CanonicalDeclaration (as well as Definition) are mapped as optional in YAML.
• added operator<< for Symbol & SymbolLocation, for debugging

[sammccall]

This does seem to get at least the simple cases right:

ID:              0EF8ACCCCF4D08B11EBF3FFB8004CE702991B15F
Name:            SymbolsFromYAML
Scope:           'clang::clangd::'
SymInfo:         
  Kind:            Function
  Lang:            C
CanonicalDeclaration: 
  StartOffset:     956
  EndOffset:       1010
  FilePath:        /usr/local/google/home/sammccall/src/llvm/tools/clang/tools/extra/clangd/index/SymbolYAML.h
Definition:      
  StartOffset:     4999
  EndOffset:       5348
  FilePath:        /usr/local/google/home/sammccall/src/llvm/tools/clang/tools/extra/clangd/index/SymbolYAML.cpp
CompletionLabel: 'SymbolsFromYAML(llvm::StringRef YAMLContent)'
CompletionFilterText: SymbolsFromYAML
CompletionPlainInsertText: SymbolsFromYAML
CompletionSnippetInsertText: 'SymbolsFromYAML(${1:llvm::StringRef YAMLContent})'
Detail:          
  Documentation:   ''
  CompletionDetail: SymbolSlab

[ioeric]

looks good

clangd/index/Index.h

25 ↗

(On Diff #132927)

It might be worth mentioning here whether the range covers the entire declaration/definition body, or just the symbol identifier.

clangd/index/Merge.cpp

71 ↗

(On Diff #132927)

Do we also need to copy other information such as completion detail, since forward declarations usually have minimum symbol information?

[hokein]

I like where the patch is going now.

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

67 ↗

(On Diff #132927)

It is fine for debugging, but I think we don't want this behavior by default.

global-symbol-builder also supports running a single TU (global-symbol-builder /path/to/file), which is sufficient for debugging, I think?

clangd/index/Index.h

131 ↗

(On Diff #132927)

We might want to update the comment above.

[sammccall]

[clangd] Prefer data from TUs with symbol defn to data from TUs without.

[sammccall]

Thanks for comments! (Still not done, adding tests)

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

67 ↗

(On Diff #132927)

Yeah, I'm not going to check this in, thus the XXX comment :-)

Single TU isn't enough - it doesn't test the reducer. On the other hand the full compilation database is too big. So this option would actually be useful! But it doesn't belong here.

clangd/index/Index.h

131 ↗

(On Diff #132927)

I think the comment above is still valid, but added one for definition.

clangd/index/Merge.cpp

71 ↗

(On Diff #132927)

Done. Now if one of the symbols has a definition and the other doesn't, we prefer the one that does. Otherwise we fall back to preferring L over R.

This means we prefer a definition from the global index over a declaration from the local one, which seems OK for now.

[sammccall]

Add tests for SymbolCollector (finding def/decl locations) and merge.

Found some bugs in SymbolCollector's locations - added fixmes.

[sammccall]

OK, I think this is good to go now. Rebased against Eric's URI change and added tests.

[ioeric]

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

67 ↗

(On Diff #132927)

Drive-by: you could also run the tool in the default standalone mode and provide a list of files.

clangd/index/Merge.cpp

93 ↗

(On Diff #133024)

else if (S.Detail)?

/*Current state: S.Detail = S.Detail*/?

clangd/index/SymbolCollector.cpp

210 ↗

(On Diff #133024)

It seems that we store definition even if it's the same as declaration, which might be true for most classes? This is probably fine, but it would be worth documenting. Or maybe consider not storing the same location twice?

236 ↗

(On Diff #133024)

Could you elaborate a bit more on this one? What is the current heuristic, and what would we prefer?

unittests/clangd/SymbolCollectorTests.cpp

49 ↗

(On Diff #133024)

Fallout of a git merge?

108 ↗

(On Diff #133024)

neat!

[hokein]

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

159 ↗

(On Diff #133024)

nit: we could get rid of the loop by using SymbolsToYAML(UniqueSymbols) .

67 ↗

(On Diff #132927)

However the default standalone mode is not multiple thread :(.

clangd/index/SymbolCollector.cpp

137 ↗

(On Diff #133024)

That's bad, thanks for finding it.

210 ↗

(On Diff #133024)

I think it is fine to store the same location twice. We can't tell whether the CanonicalLoc is a definition or not.

[sammccall]

Address review comments.
Make SymbolsToYAML take an ostream instead of returning a string.
Define SymbolSlab::iterator so googletest will print it as a container.

[sammccall]

Revert hack in global-symbol-builder to filter the input files.

[sammccall]

Thanks for the comments!
And sorry for the delay, I was haunted by useless gtest messages, which D43091 should fix.

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

159 ↗

(On Diff #133024)

Yeah, but we'd put the whole text form of the index into a single in-memory string, which seems pretty wasteful. Building a YAML output for each seems silly too though.

Changed SymbolsToYAML to take a raw_ostream ref parameter to write to.

clangd/index/Merge.cpp

93 ↗

(On Diff #133024)

Good catch.
Reworked the structure here to avoid needing to name this case, since it was awkward.

clangd/index/SymbolCollector.cpp

210 ↗

(On Diff #133024)

Documented that these may be the same.
We wouldn't actually save any memory by avoiding saving this twice - the filename is a stringref to the same data, and the offsets get stored even if they're null.

236 ↗

(On Diff #133024)

Done a bit, though I don't know the detailed answer to either question.
Using forward declarations of classes as canonical indicates that we probably want something better.

unittests/clangd/SymbolCollectorTests.cpp

108 ↗

(On Diff #133024)

Indeed :-)
This is needed because otherwise all the offsets in the annotated testcase are off.
I got it slightly wrong though: need the full path to the header name because it's not resolved relative to the main file.

[hokein]

LGTM.

clangd/index/Index.h

129 ↗

(On Diff #133502)

a typo here? multiple?

[ioeric]

Lg

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

67 ↗

(On Diff #132927)

You are right :) But I don't think this matters much if you only want to test reduction.

clangd/index/SymbolCollector.cpp

210 ↗

(On Diff #133024)

I'm less concerned about space. I think this would also make it easy to check whether a symbol has a separate definition (e.g. we might want to do this for go-to-definition/go-to-declaration). A comparison would also work but seems less natural. But I'm not sure, up tp you :)

[sammccall]

clangd/index/SymbolCollector.cpp

210 ↗

(On Diff #133024)

Yeah sometimes we'll definitely want to check if they're different, but other times we'll want to use one without caring if they are. Comparison seems less surprising than either of the fields sometimes being empty even though data is available - that seems likely to lead to bugs I think.

clang-tools-extra/trunk/clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

 //===--- GlobalSymbolBuilderMain.cpp -----------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // GlobalSymbolBuilder is a tool to generate YAML-format symbols across the
 // whole project. This tools is for **experimental** only. Don't use it in
 // production code.
 //
 //===---------------------------------------------------------------------===//
 
 #include "index/Index.h"
+#include "index/Merge.h"
 #include "index/SymbolCollector.h"
 #include "index/SymbolYAML.h"
 #include "clang/Frontend/FrontendActions.h"
+#include "clang/Frontend/CompilerInstance.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Tooling/CommonOptionsParser.h"
 #include "clang/Tooling/Execution.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/ThreadPool.h"
 
 using namespace llvm;
 using namespace clang::tooling;
 using clang::clangd::SymbolSlab;
 
 namespace clang {
 namespace clangd {
+namespace {
 
 static llvm::cl::opt<std::string> AssumedHeaderDir(
     "assume-header-dir",
     llvm::cl::desc("The index includes header that a symbol is defined in. "
                    "If the absolute path cannot be determined (e.g. an "
                    "in-memory VFS) then the relative path is resolved against "
                    "this directory, which must be absolute. If this flag is "
                    "not given, such headers will have relative paths."),
clang::FrontendAction *create() override {
     return new WrappedIndexAction(
         std::make_shared<SymbolCollector>(std::move(CollectorOpts)), IndexOpts,
         Ctx);
   }
 
   tooling::ExecutionContext *Ctx;
 };
 
+// Combine occurrences of the same symbol across translation units.
+SymbolSlab mergeSymbols(tooling::ToolResults *Results) {
+  SymbolSlab::Builder UniqueSymbols;
+  llvm::BumpPtrAllocator Arena;
+  Symbol::Details Scratch;
+  Results->forEachResult([&](llvm::StringRef Key, llvm::StringRef Value) {
+    Arena.Reset();
+    auto Sym = clang::clangd::SymbolFromYAML(Value, Arena);
+    clang::clangd::SymbolID ID;
+    Key >> ID;
+    if (const auto *Existing = UniqueSymbols.find(ID))
+      UniqueSymbols.insert(mergeSymbol(*Existing, Sym, &Scratch));
+    else
+      UniqueSymbols.insert(Sym);
+  });
+  return std::move(UniqueSymbols).build();
+}
+
+} // namespace
 } // namespace clangd
 } // namespace clang
 
 int main(int argc, const char **argv) {
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
 
   const char* Overview =
       "This is an **experimental** tool to generate YAML-format "
       "project-wide symbols for clangd (global code completion). It would be "
       "changed and deprecated eventually. Don't use it in production code!";
   auto Executor = clang::tooling::createExecutorFromCommandLineArgs(
       argc, argv, cl::GeneralCategory, Overview);
 
   if (!Executor) {
     llvm::errs() << llvm::toString(Executor.takeError()) << "\n";
     return 1;
   }
 
   if (!clang::clangd::AssumedHeaderDir.empty() &&
       !llvm::sys::path::is_absolute(clang::clangd::AssumedHeaderDir)) {
     llvm::errs() << "--assume-header-dir must be an absolute path.\n";
     return 1;
   }
 
+  // Map phase: emit symbols found in each translation unit.
   auto Err = Executor->get()->execute(
       llvm::make_unique<clang::clangd::SymbolIndexActionFactory>(
           Executor->get()->getExecutionContext()));
   if (Err) {
     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
   }
 
-  // Deduplicate the result by key and keep the longest value.
-  // FIXME(ioeric): Merge occurrences, rather than just dropping all but one.
-  // Definitions and forward declarations have the same key and may both have
-  // information. Usage count will need to be aggregated across occurrences,
-  // too.
-  llvm::StringMap<llvm::StringRef> UniqueSymbols;
-  Executor->get()->getToolResults()->forEachResult(
-      [&UniqueSymbols](llvm::StringRef Key, llvm::StringRef Value) {
-        auto Ret = UniqueSymbols.try_emplace(Key, Value);
-        if (!Ret.second) {
-          // If key already exists, keep the longest value.
-          llvm::StringRef &V = Ret.first->second;
-          V = V.size() < Value.size() ? Value : V;
-        }
-      });
-  for (const auto &Sym : UniqueSymbols)
-    llvm::outs() << Sym.second;
+  // Reduce phase: combine symbols using the ID as a key.
+  auto UniqueSymbols =
+      clang::clangd::mergeSymbols(Executor->get()->getToolResults());
+
+  // Output phase: emit YAML for result symbols.
+  SymbolsToYAML(UniqueSymbols, llvm::outs());
   return 0;
 }

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

 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // The URI of the source file where a symbol occurs.
   llvm::StringRef FileURI;
   // The 0-based offset to the first character of the symbol from the beginning
   // of the source file.
-  unsigned StartOffset;
+  unsigned StartOffset = 0;
   // The 0-based offset to the last character of the symbol from the beginning
   // of the source file.
-  unsigned EndOffset;
+  unsigned EndOffset = 0;
+
+  operator bool() const { return !FileURI.empty(); }
 };
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
 
 // The class identifies a particular C++ symbol (class, function, method, etc).
 //
 // As USRs (Unified Symbol Resolution) could be large, especially for functions
 // with long type arguments, SymbolID is using 160-bits SHA1(USR) values to
 // guarantee the uniqueness of symbols while using a relatively small amount of
 // memory (vs storing USRs directly).
 //
 // SymbolID can be used as key in the symbol indexes to lookup the symbol.
 class SymbolID {
 public:
   SymbolID() = default;
-  SymbolID(llvm::StringRef USR);
+  explicit SymbolID(llvm::StringRef USR);
 
   bool operator==(const SymbolID &Sym) const {
     return HashValue == Sym.HashValue;
   }
   bool operator<(const SymbolID &Sym) const {
     return HashValue < Sym.HashValue;
   }
 
struct Symbol {
   // The ID of the symbol.
   SymbolID ID;
   // The symbol information, like symbol kind.
   index::SymbolInfo SymInfo;
   // The unqualified name of the symbol, e.g. "bar" (for ns::bar).
   llvm::StringRef Name;
   // The containing namespace. e.g. "" (global), "ns::" (top-level namespace).
   llvm::StringRef Scope;
-  // The location of the canonical declaration of the symbol.
+  // The location of the symbol's definition, if one was found.
+  // This covers the whole definition (e.g. class body).
+  SymbolLocation Definition;
+  // The location of the preferred declaration of the symbol.
+  // This may be the same as Definition.
   //
-  // A C++ symbol could have multiple declarations and one definition (e.g.
-  // a function is declared in ".h" file, and is defined in ".cc" file).
-  //   * For classes, the canonical declaration is usually definition.
-  //   * For non-inline functions, the canonical declaration is a declaration
-  //     (not a definition), which is usually declared in ".h" file.
+  // A C++ symbol may have multiple declarations, and we pick one to prefer.
+  //   * For classes, the canonical declaration should be the definition.
+  //   * For non-inline functions, the canonical declaration typically appears
+  //     in the ".h" file corresponding to the definition.
   SymbolLocation CanonicalDeclaration;
 
   /// A brief description of the symbol that can be displayed in the completion
   /// candidate list. For example, "Foo(X x, Y y) const" is a labal for a
   /// function.
   llvm::StringRef CompletionLabel;
   /// The piece of text that the user is expected to type to match the
   /// code-completion string, typically a keyword or the name of a declarator or
struct Symbol {
 
   // Optional details of the symbol.
   const Details *Detail = nullptr;
 
   // FIXME: add definition location of the symbol.
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
 
 // An immutable symbol container that stores a set of symbols.
 // The container will maintain the lifetime of the symbols.
 class SymbolSlab {
 public:
   using const_iterator = std::vector<Symbol>::const_iterator;
+  using iterator = const_iterator;
 
   SymbolSlab() = default;
 
   const_iterator begin() const { return Symbols.begin(); }
   const_iterator end() const { return Symbols.end(); }
   const_iterator find(const SymbolID &SymID) const;
 
   size_t size() const { return Symbols.size(); }

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

 //===--- Index.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Index.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/SHA1.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
+raw_ostream &operator<<(raw_ostream &OS, const SymbolLocation &L) {
+  if (!L)
+    return OS << "(none)";
+  return OS << L.FileURI << "[" << L.StartOffset << "-" << L.EndOffset << "]";
+}
+
 SymbolID::SymbolID(StringRef USR)
     : HashValue(SHA1::hash(arrayRefFromStringRef(USR))) {}
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolID &ID) {
   OS << toHex(toStringRef(ID.HashValue));
   return OS;
 }
 
 void operator>>(StringRef Str, SymbolID &ID) {
   std::string HexString = fromHex(Str);
   assert(HexString.size() == ID.HashValue.size());
   std::copy(HexString.begin(), HexString.end(), ID.HashValue.begin());
 }
 
+raw_ostream &operator<<(raw_ostream &OS, const Symbol &S) {
+  return OS << S.Scope << S.Name;
+}
+
 SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &ID) const {
   auto It = std::lower_bound(Symbols.begin(), Symbols.end(), ID,
                              [](const Symbol &S, const SymbolID &I) {
                                return S.ID < I;
                              });
   if (It != Symbols.end() && It->ID == ID)
     return It;
   return Symbols.end();
auto Intern = [&](StringRef &V) {
     }
     V = *R.first;
   };
 
   // We need to copy every StringRef field onto the arena.
   Intern(S.Name);
   Intern(S.Scope);
   Intern(S.CanonicalDeclaration.FileURI);
+  Intern(S.Definition.FileURI);
 
   Intern(S.CompletionLabel);
   Intern(S.CompletionFilterText);
   Intern(S.CompletionPlainInsertText);
   Intern(S.CompletionSnippetInsertText);
 
   if (S.Detail) {
     // Copy values of StringRefs into arena.

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

 private:
   const SymbolIndex *Dynamic, *Static;
 };
 }
 
 Symbol
 mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   assert(L.ID == R.ID);
-  Symbol S = L;
-  // For each optional field, fill it from R if missing in L.
-  // (It might be missing in R too, but that's a no-op).
-  if (S.CanonicalDeclaration.FileURI == "")
-    S.CanonicalDeclaration = R.CanonicalDeclaration;
+  // We prefer information from TUs that saw the definition.
+  // Classes: this is the def itself. Functions: hopefully the header decl.
+  // If both did (or both didn't), continue to prefer L over R.
+  bool PreferR = R.Definition && !L.Definition;
+  Symbol S = PreferR ? R : L;        // The target symbol we're merging into.
+  const Symbol &O = PreferR ? L : R; // The "other" less-preferred symbol.
+
+  // For each optional field, fill it from O if missing in S.
+  // (It might be missing in O too, but that's a no-op).
+  if (!S.Definition)
+    S.Definition = O.Definition;
+  if (!S.CanonicalDeclaration)
+    S.CanonicalDeclaration = O.CanonicalDeclaration;
   if (S.CompletionLabel == "")
-    S.CompletionLabel = R.CompletionLabel;
+    S.CompletionLabel = O.CompletionLabel;
   if (S.CompletionFilterText == "")
-    S.CompletionFilterText = R.CompletionFilterText;
+    S.CompletionFilterText = O.CompletionFilterText;
   if (S.CompletionPlainInsertText == "")
-    S.CompletionPlainInsertText = R.CompletionPlainInsertText;
+    S.CompletionPlainInsertText = O.CompletionPlainInsertText;
   if (S.CompletionSnippetInsertText == "")
-    S.CompletionSnippetInsertText = R.CompletionSnippetInsertText;
+    S.CompletionSnippetInsertText = O.CompletionSnippetInsertText;
 
-  if (L.Detail && R.Detail) {
+  if (O.Detail) {
+    if (S.Detail) {
       // Copy into scratch space so we can merge.
-    *Scratch = *L.Detail;
+      *Scratch = *S.Detail;
       if (Scratch->Documentation == "")
-      Scratch->Documentation = R.Detail->Documentation;
+        Scratch->Documentation = O.Detail->Documentation;
       if (Scratch->CompletionDetail == "")
-      Scratch->CompletionDetail = R.Detail->CompletionDetail;
+        Scratch->CompletionDetail = O.Detail->CompletionDetail;
       S.Detail = Scratch;
-  } else if (L.Detail)
-    S.Detail = L.Detail;
-  else if (R.Detail)
-    S.Detail = R.Detail;
+    } else
+      S.Detail = O.Detail;
+  }
   return S;
 }
 
 std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
                                         const SymbolIndex *Static) {
   return llvm::make_unique<MergedIndex>(Dynamic, Static);
 }
 } // namespace clangd
 } // namespace clang

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

public:
   handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       ArrayRef<index::SymbolRelation> Relations, FileID FID,
                       unsigned Offset,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override;
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
 
 private:
+  const Symbol *addDeclaration(const NamedDecl &, SymbolID);
+  void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
+
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
 };
 
 } // namespace clangd
 } // namespace clang

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

bool shouldFilterDecl(const NamedDecl *ND, ASTContext *ASTCtx,
   return false;
 }
 
 // Return the symbol location of the given declaration `D`.
 //
 // For symbols defined inside macros:
 //   * use expansion location, if the symbol is formed via macro concatenation.
 //   * use spelling location, otherwise.
+//
+// FIXME: EndOffset is inclusive (closed range), and should be exclusive.
+// FIXME: Because the underlying ranges are token ranges, this code chops the
+//        last token in half if it contains multiple characters.
+// FIXME: We probably want to get just the location of the symbol name, not
+//        the whole e.g. class.
 llvm::Optional<SymbolLocation>
-getSymbolLocation(const NamedDecl *D, SourceManager &SM,
+getSymbolLocation(const NamedDecl &D, SourceManager &SM,
                   const SymbolCollector::Options &Opts,
                   std::string &FileURIStorage) {
-  SourceLocation Loc = D->getLocation();
-  SourceLocation StartLoc = SM.getSpellingLoc(D->getLocStart());
-  SourceLocation EndLoc = SM.getSpellingLoc(D->getLocEnd());
+  SourceLocation Loc = D.getLocation();
+  SourceLocation StartLoc = SM.getSpellingLoc(D.getLocStart());
+  SourceLocation EndLoc = SM.getSpellingLoc(D.getLocEnd());
   if (Loc.isMacroID()) {
     std::string PrintLoc = SM.getSpellingLoc(Loc).printToString(SM);
     if (llvm::StringRef(PrintLoc).startswith("<scratch") ||
         llvm::StringRef(PrintLoc).startswith("<command line>")) {
       // We use the expansion location for the following symbols, as spelling
       // locations of these symbols are not interesting to us:
       //   * symbols formed via macro concatenation, the spelling location will
       //     be "<scratch space>"
       //   * symbols controlled and defined by a compile command-line option
       //     `-DName=foo`, the spelling location will be "<command line>".
-      StartLoc = SM.getExpansionRange(D->getLocStart()).first;
-      EndLoc = SM.getExpansionRange(D->getLocEnd()).second;
+      StartLoc = SM.getExpansionRange(D.getLocStart()).first;
+      EndLoc = SM.getExpansionRange(D.getLocEnd()).second;
     }
   }
 
   auto U = toURI(SM, SM.getFilename(StartLoc), Opts);
   if (!U)
     return llvm::None;
   FileURIStorage = std::move(*U);
-  return SymbolLocation{FileURIStorage, SM.getFileOffset(StartLoc),
-                        SM.getFileOffset(EndLoc)};
+  SymbolLocation Result;
+  Result.FileURI = FileURIStorage;
+  Result.StartOffset = SM.getFileOffset(StartLoc);
+  Result.EndOffset = SM.getFileOffset(EndLoc);
+  return std::move(Result);
 }
 
 } // namespace
 
 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 
 void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
bool SymbolCollector::handleDeclOccurence(
   if (const NamedDecl *ND = llvm::dyn_cast<NamedDecl>(D)) {
     if (shouldFilterDecl(ND, ASTCtx, Opts))
       return true;
     llvm::SmallString<128> USR;
     if (index::generateUSRForDecl(ND, USR))
       return true;
 
     auto ID = SymbolID(USR);
-    if (Symbols.find(ID) != nullptr)
-      return true;
+    const Symbol* BasicSymbol = Symbols.find(ID);
+    if (!BasicSymbol) // Regardless of role, ND is the canonical declaration.
+      BasicSymbol = addDeclaration(*ND, std::move(ID));
+    if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
+      addDefinition(*cast<NamedDecl>(ASTNode.OrigD), *BasicSymbol);
+  }
+}
 
-    auto &SM = ND->getASTContext().getSourceManager();
+const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
+                                              SymbolID ID) {
+  auto &SM = ND.getASTContext().getSourceManager();
 
-    std::string QName;
-    llvm::raw_string_ostream OS(QName);
-    PrintingPolicy Policy(ASTCtx->getLangOpts());
-    // Note that inline namespaces are treated as transparent scopes. This
-    // reflects the way they're most commonly used for lookup. Ideally we'd
-    // include them, but at query time it's hard to find all the inline
-    // namespaces to query: the preamble doesn't have a dedicated list.
-    Policy.SuppressUnwrittenScope = true;
-    ND->printQualifiedName(OS, Policy);
-    OS.flush();
+  ND.printQualifiedName(OS, Policy);
 
-    Symbol S;
-    S.ID = std::move(ID);
-    std::tie(S.Scope, S.Name) = splitQualifiedName(QName);
-    S.SymInfo = index::getSymbolInfo(D);
-    std::string URIStorage;
-    if (auto DeclLoc = getSymbolLocation(ND, SM, Opts, URIStorage))
-      S.CanonicalDeclaration = *DeclLoc;
+  S.SymInfo = index::getSymbolInfo(&ND);
+  std::string FileURI;
+  // FIXME: we may want a different "canonical" heuristic than clang chooses.
+  // Clang seems to choose the first, which may not have the most information.
+  if (auto DeclLoc = getSymbolLocation(ND, SM, Opts, FileURI))
 
-    // Add completion info.
-    assert(ASTCtx && PP.get() && "ASTContext and Preprocessor must be set.");
-    CodeCompletionResult SymbolCompletion(ND, 0);
-    const auto *CCS = SymbolCompletion.CreateCodeCompletionString(
-        *ASTCtx, *PP, CodeCompletionContext::CCC_Name, *CompletionAllocator,
-        *CompletionTUInfo,
-        /*IncludeBriefComments*/ true);
-    std::string Label;
-    std::string SnippetInsertText;
-    std::string IgnoredLabel;
-    std::string PlainInsertText;
-    getLabelAndInsertText(*CCS, &Label, &SnippetInsertText,
-                          /*EnableSnippets=*/true);
-    getLabelAndInsertText(*CCS, &IgnoredLabel, &PlainInsertText,
-                          /*EnableSnippets=*/false);
-    std::string FilterText = getFilterText(*CCS);
-    std::string Documentation = getDocumentation(*CCS);
-    std::string CompletionDetail = getDetail(*CCS);
+  // FIXME: we may want to choose a different redecl, or combine from several.
+  CodeCompletionResult SymbolCompletion(&ND, 0);
 
-    S.CompletionFilterText = FilterText;
-    S.CompletionLabel = Label;
-    S.CompletionPlainInsertText = PlainInsertText;
-    S.CompletionSnippetInsertText = SnippetInsertText;
-    Symbol::Details Detail;
-    Detail.Documentation = Documentation;
-    Detail.CompletionDetail = CompletionDetail;
-    S.Detail = &Detail;
 
-    Symbols.insert(S);
-  }
+  return Symbols.find(S.ID);
 
-  return true;
+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 = getSymbolLocation(ND, ND.getASTContext().getSourceManager(),
+                                      Opts, FileURI))
+    S.Definition = *DefLoc;
+  Symbols.insert(S);
 }
 
 } // namespace clangd
 } // namespace clang

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

 //
 //===---------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_FROM_YAML_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_FROM_YAML_H
 
 #include "Index.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 
 // Read symbols from a YAML-format string.
-SymbolSlab SymbolFromYAML(llvm::StringRef YAMLContent);
+SymbolSlab SymbolsFromYAML(llvm::StringRef YAMLContent);
+
+// Read one symbol from a YAML-format string, backed by the arena.
+Symbol SymbolFromYAML(llvm::StringRef YAMLContent,
+                      llvm::BumpPtrAllocator &Arena);
 
 // Convert a single symbol to YAML-format string.
 // The YAML result is safe to concatenate.
 std::string SymbolToYAML(Symbol Sym);
 
 // Convert symbols to a YAML-format string.
 // The YAML result is safe to concatenate if you have multiple symbol slabs.
-std::string SymbolsToYAML(const SymbolSlab& Symbols);
+void SymbolsToYAML(const SymbolSlab& Symbols, llvm::raw_ostream &OS);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_FROM_YAML_H

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

template <> struct MappingTraits<Symbol> {
   static void mapping(IO &IO, Symbol &Sym) {
     MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(IO, Sym.ID);
     MappingNormalization<ArenaPtr<Symbol::Details>, const Symbol::Details *>
         NDetail(IO, Sym.Detail);
     IO.mapRequired("ID", NSymbolID->HexString);
     IO.mapRequired("Name", Sym.Name);
     IO.mapRequired("Scope", Sym.Scope);
     IO.mapRequired("SymInfo", Sym.SymInfo);
-    IO.mapRequired("CanonicalDeclaration", Sym.CanonicalDeclaration);
+    IO.mapOptional("CanonicalDeclaration", Sym.CanonicalDeclaration,
+                   SymbolLocation());
+    IO.mapOptional("Definition", Sym.Definition, SymbolLocation());
     IO.mapRequired("CompletionLabel", Sym.CompletionLabel);
     IO.mapRequired("CompletionFilterText", Sym.CompletionFilterText);
     IO.mapRequired("CompletionPlainInsertText", Sym.CompletionPlainInsertText);
 
     IO.mapOptional("CompletionSnippetInsertText",
                    Sym.CompletionSnippetInsertText);
     IO.mapOptional("Detail", NDetail->Opt);
   }

 };
 
 } // namespace yaml
 } // namespace llvm
 
 namespace clang {
 namespace clangd {
 
-SymbolSlab SymbolFromYAML(llvm::StringRef YAMLContent) {
+SymbolSlab SymbolsFromYAML(llvm::StringRef YAMLContent) {
   // Store data of pointer fields (excl. `StringRef`) like `Detail`.
   llvm::BumpPtrAllocator Arena;
   llvm::yaml::Input Yin(YAMLContent, &Arena);
   std::vector<Symbol> S;
   Yin >> S;
 
   SymbolSlab::Builder Syms;
   for (auto &Sym : S)
     Syms.insert(Sym);
   return std::move(Syms).build();
 }
 
-std::string SymbolsToYAML(const SymbolSlab& Symbols) {
-  std::string Str;
-  llvm::raw_string_ostream OS(Str);
+Symbol SymbolFromYAML(llvm::StringRef YAMLContent,
+                      llvm::BumpPtrAllocator &Arena) {
+  llvm::yaml::Input Yin(YAMLContent, &Arena);
+  Symbol S;
+  Yin >> S;
+  return S;
+}
+
+void SymbolsToYAML(const SymbolSlab& Symbols, llvm::raw_ostream &OS) {
   llvm::yaml::Output Yout(OS);
   for (Symbol S : Symbols) // copy: Yout<< requires mutability.
     Yout << S;
-  return OS.str();
 }
 
 std::string SymbolToYAML(Symbol Sym) {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
   llvm::yaml::Output Yout(OS);
   Yout << Sym;
   return OS.str();
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/tool/ClangdMain.cpp

 // The size of global symbols should be relatively small, so that all symbols
 // can be managed in memory.
 std::unique_ptr<SymbolIndex> BuildStaticIndex(llvm::StringRef YamlSymbolFile) {
   auto Buffer = llvm::MemoryBuffer::getFile(YamlSymbolFile);
   if (!Buffer) {
     llvm::errs() << "Can't open " << YamlSymbolFile << "\n";
     return nullptr;
   }
-  auto Slab = SymbolFromYAML(Buffer.get()->getBuffer());
+  auto Slab = SymbolsFromYAML(Buffer.get()->getBuffer());
   SymbolSlab::Builder SymsBuilder;
   for (auto Sym : Slab)
     SymsBuilder.insert(Sym);
 
   return MemIndex::build(std::move(SymsBuilder).build());
 }
 } // namespace
 

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

TEST(MergeTest, Merge) {
   EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:///left.h");
   EXPECT_EQ(M.CompletionPlainInsertText, "f00");
   EXPECT_EQ(M.CompletionSnippetInsertText, "f0{$1:0}");
   ASSERT_TRUE(M.Detail);
   EXPECT_EQ(M.Detail->CompletionDetail, "DetL");
   EXPECT_EQ(M.Detail->Documentation, "--doc--");
 }
 
+TEST(MergeTest, PreferSymbolWithDefn) {
+  Symbol L, R;
+  Symbol::Details Scratch;
+
+  L.ID = R.ID = SymbolID("hello");
+  L.CanonicalDeclaration.FileURI = "file:/left.h";
+  R.CanonicalDeclaration.FileURI = "file:/right.h";
+  L.CompletionPlainInsertText = "left-insert";
+  R.CompletionPlainInsertText = "right-insert";
+
+  Symbol M = mergeSymbol(L, R, &Scratch);
+  EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:/left.h");
+  EXPECT_EQ(M.Definition.FileURI, "");
+  EXPECT_EQ(M.CompletionPlainInsertText, "left-insert");
+
+  R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored.
+  M = mergeSymbol(L, R, &Scratch);
+  EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:/right.h");
+  EXPECT_EQ(M.Definition.FileURI, "file:/right.cpp");
+  EXPECT_EQ(M.CompletionPlainInsertText, "right-insert");
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 }
 MATCHER_P(Doc, D, "") { return arg.Detail && arg.Detail->Documentation == D; }
 MATCHER_P(Plain, Text, "") { return arg.CompletionPlainInsertText == Text; }
 MATCHER_P(Snippet, S, "") {
   return arg.CompletionSnippetInsertText == S;
 }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
 MATCHER_P(DeclURI, P, "") { return arg.CanonicalDeclaration.FileURI == P; }
-MATCHER_P(LocationOffsets, Offsets, "") {
+MATCHER_P(DeclRange, Offsets, "") {
   // Offset range in SymbolLocation is [start, end] while in Clangd is [start,
   // end).
+  // FIXME: SymbolLocation should be [start, end).
   return arg.CanonicalDeclaration.StartOffset == Offsets.first &&
       arg.CanonicalDeclaration.EndOffset == Offsets.second - 1;
 }
+MATCHER_P(DefRange, Offsets, "") {
+  return arg.Definition.StartOffset == Offsets.first &&
+         arg.Definition.EndOffset == Offsets.second - 1;
+}
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
 public:
   SymbolIndexActionFactory(SymbolCollector::Options COpts)
bool runSymbolCollector(StringRef HeaderCode, StringRef MainCode,
     llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
         new vfs::InMemoryFileSystem);
     llvm::IntrusiveRefCntPtr<FileManager> Files(
         new FileManager(FileSystemOptions(), InMemoryFileSystem));
 
     auto Factory = llvm::make_unique<SymbolIndexActionFactory>(CollectorOpts);
 
     std::vector<std::string> Args = {"symbol_collector", "-fsyntax-only",
-                                     "-std=c++11", TestFileName};
+                                     "-std=c++11",       "-include",
+                                     TestHeaderName,     TestFileName};
     Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
     tooling::ToolInvocation Invocation(
         Args,
         Factory->create(), Files.get(),
         std::make_shared<PCHContainerOperations>());
 
     InMemoryFileSystem->addFile(TestHeaderName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(HeaderCode));
-
-    std::string Content = MainCode;
-    if (!HeaderCode.empty())
-      Content = (llvm::Twine("#include\"") +
-                 llvm::sys::path::filename(TestHeaderName) + "\"\n" + Content)
-                    .str();
     InMemoryFileSystem->addFile(TestFileName, 0,
-                                llvm::MemoryBuffer::getMemBuffer(Content));
+                                llvm::MemoryBuffer::getMemBuffer(MainCode));
     Invocation.run();
     Symbols = Factory->Collector->takeSymbols();
     return true;
   }
 
 protected:
   std::string TestHeaderName;
   std::string TestHeaderURI;
TEST_F(SymbolCollectorTest, CollectSymbols) {
   EXPECT_THAT(Symbols,
               UnorderedElementsAreArray(
                   {QName("Foo"), QName("f1"), QName("f2"), QName("KInt"),
                    QName("kStr"), QName("foo"), QName("foo::bar"),
                    QName("foo::int32"), QName("foo::int32_t"), QName("foo::v1"),
                    QName("foo::bar::v2"), QName("foo::baz")}));
 }
 
+TEST_F(SymbolCollectorTest, Locations) {
+  // FIXME: the behavior here is bad: chopping tokens, including more than the
+  // ident range, using half-open ranges. See fixmes in getSymbolLocation().
+  CollectorOpts.IndexMainFiles = true;
+  Annotations Header(R"cpp(
+    // Declared in header, defined in main.
+    $xdecl[[extern int X]];
+    $clsdecl[[class C]]ls;
+    $printdecl[[void print()]];
+
+    // Declared in header, defined nowhere.
+    $zdecl[[extern int Z]];
+  )cpp");
+  Annotations Main(R"cpp(
+    $xdef[[int X = 4]]2;
+    $clsdef[[class Cls {}]];
+    $printdef[[void print() {}]]
+
+    // Declared/defined in main only.
+    $y[[int Y]];
+  )cpp");
+  runSymbolCollector(Header.code(), Main.code());
+  EXPECT_THAT(
+      Symbols,
+      UnorderedElementsAre(
+          AllOf(QName("X"), DeclRange(Header.offsetRange("xdecl")),
+                DefRange(Main.offsetRange("xdef"))),
+          AllOf(QName("Cls"), DeclRange(Header.offsetRange("clsdecl")),
+                DefRange(Main.offsetRange("clsdef"))),
+          AllOf(QName("print"), DeclRange(Header.offsetRange("printdecl")),
+                DefRange(Main.offsetRange("printdef"))),
+          AllOf(QName("Z"), DeclRange(Header.offsetRange("zdecl"))),
+          AllOf(QName("Y"), DeclRange(Main.offsetRange("y")),
+                DefRange(Main.offsetRange("y")))));
+}
+
 TEST_F(SymbolCollectorTest, SymbolRelativeNoFallback) {
   CollectorOpts.IndexMainFiles = false;
   runSymbolCollector("class Foo {};", /*Main=*/"");
   EXPECT_THAT(Symbols,
               UnorderedElementsAre(AllOf(QName("Foo"), DeclURI(TestHeaderURI))));
 }
 
 TEST_F(SymbolCollectorTest, SymbolRelativeWithFallback) {
Annotations Header(R"(
 
     FF2();
   )");
 
   runSymbolCollector(Header.code(), /*Main=*/"");
   EXPECT_THAT(
       Symbols,
       UnorderedElementsAre(
-          AllOf(QName("abc_Test"),
-                LocationOffsets(Header.offsetRange("expansion")),
+          AllOf(QName("abc_Test"), DeclRange(Header.offsetRange("expansion")),
                 DeclURI(TestHeaderURI)),
-          AllOf(QName("Test"), LocationOffsets(Header.offsetRange("spelling")),
+          AllOf(QName("Test"), DeclRange(Header.offsetRange("spelling")),
                 DeclURI(TestHeaderURI))));
 }
 
 TEST_F(SymbolCollectorTest, SymbolFormedFromMacroInMainFile) {
   CollectorOpts.IndexMainFiles = true;
 
   Annotations Main(R"(
     #define FF(name) \
       class name##_Test {};
 
     $expansion[[FF(abc)]];
 
     #define FF2() \
       $spelling[[class Test {}]];
 
     FF2();
   )");
   runSymbolCollector(/*Header=*/"", Main.code());
-  EXPECT_THAT(Symbols, UnorderedElementsAre(
-                           AllOf(QName("abc_Test"),
-                                 LocationOffsets(Main.offsetRange("expansion")),
-                                 DeclURI(TestFileURI)),
-                           AllOf(QName("Test"),
-                                 LocationOffsets(Main.offsetRange("spelling")),
-                                 DeclURI(TestFileURI))));
+  EXPECT_THAT(
+      Symbols,
+      UnorderedElementsAre(
+          AllOf(QName("abc_Test"), DeclRange(Main.offsetRange("expansion")),
+          AllOf(QName("Test"), DeclRange(Main.offsetRange("spelling")),
 }
 
 TEST_F(SymbolCollectorTest, SymbolFormedByCLI) {
   CollectorOpts.IndexMainFiles = false;
 
   Annotations Header(R"(
     #ifdef NAME
     $expansion[[class NAME {}]];
     #endif
   )");
 
   runSymbolCollector(Header.code(), /*Main=*/"",
                      /*ExtraArgs=*/{"-DNAME=name"});
-  EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(
-                           QName("name"),
-                           LocationOffsets(Header.offsetRange("expansion")),
-                           DeclURI(TestHeaderURI))));
+  EXPECT_THAT(Symbols,
+              UnorderedElementsAre(AllOf(
+                  QName("name"), DeclRange(Header.offsetRange("expansion")),
 }
 
 TEST_F(SymbolCollectorTest, IgnoreSymbolsInMainFile) {
   CollectorOpts.IndexMainFiles = false;
   const std::string Header = R"(
     class Foo {};
     void f1();
     inline void f2() {}
CanonicalDeclaration:
   FileURI:        file:///path/bar.h
 CompletionLabel:    'Foo2-label'
 CompletionFilterText:    'filter'
 CompletionPlainInsertText:    'plain'
 CompletionSnippetInsertText:    'snippet'
 ...
 )";
 
-  auto Symbols1 = SymbolFromYAML(YAML1);
+  auto Symbols1 = SymbolsFromYAML(YAML1);
   EXPECT_THAT(Symbols1,
               UnorderedElementsAre(AllOf(
                   QName("clang::Foo1"), Labeled("Foo1-label"), Doc("Foo doc"),
                   Detail("int"), DeclURI("file:///path/foo.h"))));
-  auto Symbols2 = SymbolFromYAML(YAML2);
+  auto Symbols2 = SymbolsFromYAML(YAML2);
   EXPECT_THAT(Symbols2, UnorderedElementsAre(AllOf(
                             QName("clang::Foo2"), Labeled("Foo2-label"),
                             Not(HasDetail()), DeclURI("file:///path/bar.h"))));
 
-  std::string ConcatenatedYAML =
-      SymbolsToYAML(Symbols1) + SymbolsToYAML(Symbols2);
-  auto ConcatenatedSymbols = SymbolFromYAML(ConcatenatedYAML);
+  std::string ConcatenatedYAML;
+  {
+    llvm::raw_string_ostream OS(ConcatenatedYAML);
+    SymbolsToYAML(Symbols1, OS);
+    SymbolsToYAML(Symbols2, OS);
+  }
+  auto ConcatenatedSymbols = SymbolsFromYAML(ConcatenatedYAML);
   EXPECT_THAT(ConcatenatedSymbols,
               UnorderedElementsAre(QName("clang::Foo1"),
                                    QName("clang::Foo2")));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang