[clangd] Support multiple #include headers in one symbol.

[ioeric]

Summary

Currently, a symbol can have only one #include header attached, which
might not work well if the symbol can be imported via different #includes depending
on where it's used. This patch stores multiple #include headers (with # references)
for each symbol, so that CodeCompletion can decide which include to insert.

In this patch, code completion simply picks the most popular include as the default inserted header. We also return all possible includes and their edits in the CodeCompletion results.

[ioeric]

@sammccall The code still needs cleanup but should be useful for providing high-level feedback, which I would like to get before moving further. Thanks!

[ioeric]

• minor cleanup

[sammccall]

Nice!

We could reduce the scope of this patch somewhat by ignoring file proximity and just switching to return the most popular header. This would be a solid improvement over current behavior, and provide the infrastructure for the file-proximity approach.

clangd/CodeComplete.cpp

1396 ↗

(On Diff #162650)

I remain unconvinced that providing multiple completion candidates is the right thing to do here:

• if the index hasn't seen a definition, then we're going to show one copy of the completion for each header that has a declaration
• the user isn't going to have a useful way to distinguish between them. Note that e.g. we're going to show the #include path in the detail, but the documentation is going to be identical for each.
• we lose the invariant that each completion item (pre-bundling) maps to a different symbol
• C++ embedders don't have the option of displaying the multiple options once the completion is selected

The alternative approach of sorting the includes by proximity * log(refs) or so, and then using the top one for scoring, seems less of a drastic change to the current behavior. (Visible effect: more accurate includes inserted).

clangd/Quality.cpp

190 ↗

(On Diff #162650)

This looks a bit sketchy. Particularly the += boost where everything else is *=.
What's this trying to do?

clangd/index/Index.h

220 ↗

(On Diff #162650)

via this header -> and include this header?

(otherwise, what does "via" mean?)

clangd/index/Merge.cpp

105 ↗

(On Diff #162650)

This describes the logic, and the logic always produces the right result, but it's not clear *why*. Maybe add something like:

This is associative because it preserves the invariant:
 - if we haven't seen a definition, Includes covers all declarations
 - if we have seen a definition, Includes covers declarations visible from any definition

in fact it seems hard to reason about this field in Symbol without understanding this, so maybe this invariant belongs on the IncludeHeaders field itself.

105 ↗

(On Diff #162650)

Thinking more about it - what's the intent here?
I'm not sure sorting by (seen by def, #refs) produces better ranking than just #refs.

But there are other possible reasons for dropping includes not seen by any def:

• remove spam from the completion list (only a problem if we clone the completion items)
• reduce size for items that are often redeclared (I can imagine this being a problem, not obvious)

Curious what your thinking is.

[ioeric]

• Addressed review comments.

[ioeric]

Thanks for the review! I reduced the scope of the patch. PTAL

clangd/CodeComplete.cpp

1396 ↗

(On Diff #162650)

These are all valid points. I agree that we should start with less drastic change in the first version.

My concern was that there can be cases where it's impossible for clangd to suggest the correct #include (e.g. all includes have the same proximity and popularity). But I guess there are also alternative solutions to these than creating multiple completion results. For example, we could simply give up inserting include during code completion and let an include-fixer-like feature handle it.

clangd/Quality.cpp

190 ↗

(On Diff #162650)

(This is no longer needed in this patch.)

As we were generating multiple candidates for the same symbol (for each include), I was trying to group them together using the small score differences as the tie breaker.

clangd/index/Merge.cpp

105 ↗

(On Diff #162650)

in fact it seems hard to reason about this field in Symbol without understanding this, so maybe this invariant belongs on the IncludeHeaders field itself.

Make sense. Thanks!

Thinking more about it - what's the intent here?

The intention is basically to filter out headers with forward declarations where definition is not seen. I could hardly think of a case where we would favor headers where def is not seen over those where definition is seen.

[ioeric]

• minor cleanup

[sammccall]

• It would be useful for the C++ API (CodeCompletion struct) to provide the includes/edits in ranked order, if possible. Frontends could experiment with showing all the options.
• Still not sure that adding more complicated behavior to Code Complete (vs just improving ranking) is the right thing for now (bigger comment below)

clangd/CodeComplete.cpp

303 ↗

(On Diff #163074)

I'm not sure about this:

• we're adding new user-visible behavior which is potentially confusing (not inserting even though insertion is turned on and we're offering a completion that requires insertion)
• it's not clear that first > 10 * second is the right heuristic or tuning
• this probably isn't the right place for this heuristic - e.g. it causes us not to show the location of the symbol in the detail field. (IIRC, the fact that this is only shown when header insertion is active is a limitation we wanted to fix, not furither entrench).

Can we start with the simplest behavior, closest to what we do today: just choose the most popular include?

Probably the most forward-looking way to do this is to pick the winner when we construct the CompletionCandidate and stash it in a field there. (The scoring function is going to become more complex as we add proximity, and this function gets called twice. Also this function won't have access to the info needed for proximity).

316 ↗

(On Diff #163074)

nit: Includes[0] and Includes[1]?

[ioeric]

• Return all possible #includes in CodeComplete.

[sammccall]

clangd/CodeComplete.cpp

396 ↗

(On Diff #163351)

nit: this could be std::stable_partition. Not sure if faster, but maybe clearer.

clangd/CodeComplete.h

145 ↗

(On Diff #163351)

if we've bundled together overloads that have different sets of providing headers, these includes may not be accurate for all of them. Maybe comment this limitation?

[ioeric]

• Rebase

[ioeric]

• Document limitation for overload bundling.

clang-tools-extra/trunk/clangd/CodeComplete.h

 #include "Path.h"
 #include "Protocol.h"
 #include "index/Index.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/CodeCompleteOptions.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include <future>
 
 namespace clang {
 class NamedDecl;
 class PCHContainerOperations;
 namespace clangd {
struct CodeCompletion {
   // the following fields are summaries:
   //  - Signature is e.g. "(...)" for functions.
   //  - SnippetSuffix is similarly e.g. "(${0})".
   //  - ReturnType may be empty
   //  - Documentation may be from one symbol, or a combination of several
   // Other fields should apply equally to all bundled completions.
   unsigned BundleSize = 1;
   SymbolOrigin Origin = SymbolOrigin::Unknown;
+
+  struct IncludeCandidate {
     // The header through which this symbol could be included.
     // Quoted string as expected by an #include directive, e.g. "<memory>".
     // Empty for non-symbol completions, or when not known.
     std::string Header;
-  // Present if Header is set and should be inserted to use this item.
-  llvm::Optional<TextEdit> HeaderInsertion;
+    // Present if Header should be inserted to use this item.
+    llvm::Optional<TextEdit> Insertion;
+  };
+  // All possible include headers ranked by preference. By default, the first
+  // include is used.
+  // If we've bundled together overloads that have different sets of includes,
+  // thse includes may not be accurate for all of them.
+  llvm::SmallVector<IncludeCandidate, 1> Includes;
 
   /// Holds information about small corrections that needs to be done. Like
   /// converting '->' to '.' on member access.
   std::vector<TextEdit> FixIts;
 
   /// Holds the range of the token we are going to replace with this completion.
   Range CompletionTokenRange;
 

clang-tools-extra/trunk/clangd/CodeComplete.cpp

 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/ScopedPrinter.h"
+#include <algorithm>
+#include <iterator>
 #include <queue>
 
 // We log detailed candidate here if you run with -debug-only=codecomplete.
 #define DEBUG_TYPE "CodeComplete"
 
 namespace clang {
 namespace clangd {
 namespace {

 
 /// A code completion result, in clang-native form.
 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
 struct CompletionCandidate {
   llvm::StringRef Name; // Used for filtering and sorting.
   // We may have a result from Sema, from the index, or both.
   const CodeCompletionResult *SemaResult = nullptr;
   const Symbol *IndexResult = nullptr;
+  llvm::SmallVector<StringRef, 1> RankedIncludeHeaders;
 
   // States whether this item is an override suggestion.
   bool IsOverride = false;
 
   // Returns a token identifying the overload set this is part of.
   // 0 indicates it's not part of any overload set.
   size_t overloadSet() const {
     SmallString<256> Scratch;
     if (IndexResult) {
       switch (IndexResult->SymInfo.Kind) {
       case index::SymbolKind::ClassMethod:
       case index::SymbolKind::InstanceMethod:
       case index::SymbolKind::StaticMethod:
         assert(false && "Don't expect members from index in code completion");
         // fall through
       case index::SymbolKind::Function:
         // We can't group overloads together that need different #includes.
         // This could break #include insertion.
         return hash_combine(
             (IndexResult->Scope + IndexResult->Name).toStringRef(Scratch),
-            headerToInsertIfNotPresent().getValueOr(""));
+            headerToInsertIfAllowed().getValueOr(""));
       default:
         return 0;
       }
     }
     assert(SemaResult);
     // We need to make sure we're consistent with the IndexResult case!
     const NamedDecl *D = SemaResult->Declaration;
     if (!D || !D->isFunctionOrFunctionTemplate())
       return 0;
     {
       llvm::raw_svector_ostream OS(Scratch);
       D->printQualifiedName(OS);
     }
-    return hash_combine(Scratch, headerToInsertIfNotPresent().getValueOr(""));
+    return hash_combine(Scratch, headerToInsertIfAllowed().getValueOr(""));
   }
 
-  llvm::Optional<llvm::StringRef> headerToInsertIfNotPresent() const {
-    if (!IndexResult || IndexResult->IncludeHeader.empty())
+  // The best header to include if include insertion is allowed.
+  llvm::Optional<llvm::StringRef> headerToInsertIfAllowed() const {
+    if (RankedIncludeHeaders.empty())
       return llvm::None;
     if (SemaResult && SemaResult->Declaration) {
       // Avoid inserting new #include if the declaration is found in the current
       // file e.g. the symbol is forward declared.
       auto &SM = SemaResult->Declaration->getASTContext().getSourceManager();
       for (const Decl *RD : SemaResult->Declaration->redecls())
         if (SM.isInMainFile(SM.getExpansionLoc(RD->getBeginLoc())))
           return llvm::None;
     }
-    return IndexResult->IncludeHeader;
+    return RankedIncludeHeaders[0];
   }
 
   using Bundle = llvm::SmallVector<CompletionCandidate, 4>;
 };
 using ScoredBundle =
     std::pair<CompletionCandidate::Bundle, CodeCompletion::Scores>;
 struct ScoredBundleGreater {
   bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
if (C.IndexResult) {
       Completion.Origin |= C.IndexResult->Origin;
       if (Completion.Scope.empty())
         Completion.Scope = C.IndexResult->Scope;
       if (Completion.Kind == CompletionItemKind::Missing)
         Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
       if (Completion.Name.empty())
         Completion.Name = C.IndexResult->Name;
     }
-    if (auto Inserted = C.headerToInsertIfNotPresent()) {
-      // Turn absolute path into a literal string that can be #included.
-      auto Include = [&]() -> Expected<std::pair<std::string, bool>> {
-        auto ResolvedDeclaring =
-            toHeaderFile(C.IndexResult->CanonicalDeclaration.FileURI, FileName);
-        if (!ResolvedDeclaring)
-          return ResolvedDeclaring.takeError();
-        auto ResolvedInserted = toHeaderFile(*Inserted, FileName);
-        if (!ResolvedInserted)
-          return ResolvedInserted.takeError();
-        return std::make_pair(Includes.calculateIncludePath(*ResolvedDeclaring,
-                                                            *ResolvedInserted),
-                              Includes.shouldInsertInclude(*ResolvedDeclaring,
-                                                           *ResolvedInserted));
-      }();
-      if (Include) {
-        Completion.Header = Include->first;
-        if (Include->second)
-          Completion.HeaderInsertion = Includes.insert(Include->first);
+
+    auto Inserted =
+        [&](StringRef Header) -> Expected<std::pair<std::string, bool>> {
+      auto ResolvedInserted = toHeaderFile(Header, FileName);
+      return std::make_pair(
+          Includes.calculateIncludePath(*ResolvedDeclaring, *ResolvedInserted),
+          Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
+    };
+    bool ShouldInsert = C.headerToInsertIfAllowed().hasValue();
+    // Calculate include paths and edits for all possible headers.
+    for (const auto &Inc : C.RankedIncludeHeaders) {
+      if (auto ToInclude = Inserted(Inc)) {
+        CodeCompletion::IncludeCandidate Include;
+        Include.Header = ToInclude->first;
+        if (ToInclude->second && ShouldInsert)
+          Include.Insertion = Includes.insert(ToInclude->first);
+        Completion.Includes.push_back(std::move(Include));
       } else
         log("Failed to generate include insertion edits for adding header "
             "(FileURI='{0}', IncludeHeader='{1}') into {2}",
-            C.IndexResult->CanonicalDeclaration.FileURI,
-            C.IndexResult->IncludeHeader, FileName);
+            C.IndexResult->CanonicalDeclaration.FileURI, Inc, FileName);
     }
+    // Prefer includes that do not need edits (i.e. already exist).
+    std::stable_partition(Completion.Includes.begin(),
+                          Completion.Includes.end(),
+                          [](const CodeCompletion::IncludeCandidate &I) {
+                            return !I.Insertion.hasValue();
+                          });
   }
 
   void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS) {
     assert(bool(C.SemaResult) == bool(SemaCCS));
     Bundled.emplace_back();
     BundledEntry &S = Bundled.back();
     if (C.SemaResult) {
       getSignature(*SemaCCS, &S.Signature, &S.SnippetSuffix,
clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
   // the index can provide results from the preamble.
   // Tell Sema not to deserialize the preamble to look for results.
   Result.LoadExternal = !Index;
   Result.IncludeFixIts = IncludeFixIts;
 
   return Result;
 }
 
+// Returns the most popular include header for \p Sym. If two headers are
+// equally popular, prefer the shorter one. Returns empty string if \p Sym has
+// no include header.
+llvm::SmallVector<StringRef, 1>
+getRankedIncludes(const Symbol &Sym) {
+  auto Includes = Sym.IncludeHeaders;
+  // Sort in descending order by reference count and header length.
+  std::sort(Includes.begin(), Includes.end(),
+            [](const Symbol::IncludeHeaderWithReferences &LHS,
+               const Symbol::IncludeHeaderWithReferences &RHS) {
+              if (LHS.References == RHS.References)
+                return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
+              return LHS.References > RHS.References;
+            });
+  llvm::SmallVector<StringRef, 1> Headers;
+  for (const auto &Include : Includes)
+    Headers.push_back(Include.IncludeHeader);
+  return Headers;
+}
+
 // Runs Sema-based (AST) and Index-based completion, returns merged results.
 //
 // There are a few tricky considerations:
 //   - the AST provides information needed for the index query (e.g. which
 //     namespaces to search in). So Sema must start first.
 //   - we only want to return the top results (Opts.Limit).
 //     Building CompletionItems for everything else is wasteful, so we want to
 //     preserve the "native" format until we're done with scoring.
mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
     std::vector<CompletionCandidate::Bundle> Bundles;
     llvm::DenseMap<size_t, size_t> BundleLookup;
     auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
                             const Symbol *IndexResult,
                             bool IsOverride = false) {
       CompletionCandidate C;
       C.SemaResult = SemaResult;
       C.IndexResult = IndexResult;
+      if (C.IndexResult)
+        C.RankedIncludeHeaders = getRankedIncludes(*C.IndexResult);
       C.IsOverride = IsOverride;
       C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
       if (auto OverloadSet = Opts.BundleOverloads ? C.overloadSet() : 0) {
         auto Ret = BundleLookup.try_emplace(OverloadSet, Bundles.size());
         if (Ret.second)
           Bundles.emplace_back();
         Bundles[Ret.first->second].push_back(std::move(C));
       } else {
return !match(decl(anyOf(InTopLevelScope,
                            hasDeclContext(
                                enumDecl(InTopLevelScope, unless(isScoped()))))),
                 ND, ASTCtx)
               .empty();
 }
 
 CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
   CompletionItem LSP;
-  LSP.label = (HeaderInsertion ? Opts.IncludeIndicator.Insert
-                               : Opts.IncludeIndicator.NoInsert) +
+  const auto *InsertInclude = Includes.empty() ? nullptr : &Includes[0];
+  LSP.label = ((InsertInclude && InsertInclude->Insertion)
+                   ? Opts.IncludeIndicator.Insert
               (Opts.ShowOrigins ? "[" + llvm::to_string(Origin) + "]" : "") +
               RequiredQualifier + Name + Signature;
 
   LSP.kind = Kind;
   LSP.detail = BundleSize > 1 ? llvm::formatv("[{0} overloads]", BundleSize)
                               : ReturnType;
-  if (!Header.empty())
-    LSP.detail += "\n" + Header;
+  if (InsertInclude)
+    LSP.detail += "\n" + InsertInclude->Header;
   LSP.documentation = Documentation;
   LSP.sortText = sortText(Score.Total, Name);
   LSP.filterText = Name;
   LSP.textEdit = {CompletionTokenRange, RequiredQualifier + Name};
   // Merge continious additionalTextEdits into main edit. The main motivation
   // behind this is to help LSP clients, it seems most of them are confused when
   // they are provided with additionalTextEdits that are consecutive to main
   // edit.
CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
   if (Opts.EnableSnippets)
     LSP.textEdit->newText += SnippetSuffix;
 
   // FIXME(kadircet): Do not even fill insertText after making sure textEdit is
   // compatible with most of the editors.
   LSP.insertText = LSP.textEdit->newText;
   LSP.insertTextFormat = Opts.EnableSnippets ? InsertTextFormat::Snippet
                                              : InsertTextFormat::PlainText;
-  if (HeaderInsertion)
-    LSP.additionalTextEdits.push_back(*HeaderInsertion);
+  if (InsertInclude && InsertInclude->Insertion)
+    LSP.additionalTextEdits.push_back(*InsertInclude->Insertion);
   return LSP;
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const CodeCompletion &C) {
   // For now just lean on CompletionItem.
   return OS << C.render(CodeCompleteOptions());
 }
 

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

 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/StringSaver.h"
 #include <array>
 #include <string>
 #include <tuple>
 
 namespace clang {
 namespace clangd {
 
struct Symbol {
   /// This is in LSP snippet syntax (e.g. "({$0})" for a no-args function).
   /// (When snippets are disabled, the symbol name alone is used).
   llvm::StringRef CompletionSnippetSuffix;
   /// Documentation including comment for the symbol declaration.
   llvm::StringRef Documentation;
   /// Type when this symbol is used in an expression. (Short display form).
   /// e.g. return type of a function, or type of a variable.
   llvm::StringRef ReturnType;
-  /// This can be either a URI of the header to be #include'd for this symbol,
-  /// or a literal header quoted with <> or "" that is suitable to be included
-  /// directly. When this is a URI, the exact #include path needs to be
-  /// calculated according to the URI scheme.
+
+  struct IncludeHeaderWithReferences {
+    IncludeHeaderWithReferences() = default;
+
+    IncludeHeaderWithReferences(llvm::StringRef IncludeHeader,
+                                unsigned References)
+        : IncludeHeader(IncludeHeader), References(References) {}
+
+    /// This can be either a URI of the header to be #include'd
+    /// for this symbol, or a literal header quoted with <> or "" that is
+    /// suitable to be included directly. When it is a URI, the exact #include
+    /// path needs to be calculated according to the URI scheme.
     ///
-  /// This is a canonical include for the symbol and can be different from
-  /// FileURI in the CanonicalDeclaration.
-  llvm::StringRef IncludeHeader;
+    /// Note that the include header is a canonical include for the symbol and
+    /// can be different from FileURI in the CanonicalDeclaration.
+    llvm::StringRef IncludeHeader = "";
+    /// The number of translation units that reference this symbol and include
+    /// this header. This number is only meaningful if aggregated in an index.
+    unsigned References = 0;
+  };
+  /// One Symbol can potentially be incuded via different headers.
+  ///   - If we haven't seen a definition, this covers all declarations.
+  ///   - If we have seen a definition, this covers declarations visible from
+  ///   any definition.
+  llvm::SmallVector<IncludeHeaderWithReferences, 1> IncludeHeaders;
 
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
 
 // Computes query-independent quality score for a Symbol.
 // This currently falls in the range [1, ln(#indexed documents)].

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/ADT/StringRef.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) {
static void own(Symbol &S, llvm::UniqueStringSaver &Strings,
   // 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.Signature);
   Intern(S.CompletionSnippetSuffix);
+
   Intern(S.Documentation);
   Intern(S.ReturnType);
-  Intern(S.IncludeHeader);
+  for (auto &I : S.IncludeHeaders)
+    Intern(I.IncludeHeader);
 }
 
 void SymbolSlab::Builder::insert(const Symbol &S) {
   auto R = SymbolIndex.try_emplace(S.ID, Symbols.size());
   if (R.second) {
     Symbols.push_back(S);
     own(Symbols.back(), UniqueStrings, Arena);
   } else {

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

 } // namespace
 
 Symbol mergeSymbol(const Symbol &L, const Symbol &R) {
   assert(L.ID == R.ID);
   // 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;
+  // Merge include headers only if both have definitions or both have no
+  // definition; otherwise, only accumulate references of common includes.
+  bool MergeIncludes =
+      L.Definition.FileURI.empty() == R.Definition.FileURI.empty();
   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;
   S.References += O.References;
   if (S.Signature == "")
     S.Signature = O.Signature;
   if (S.CompletionSnippetSuffix == "")
     S.CompletionSnippetSuffix = O.CompletionSnippetSuffix;
   if (S.Documentation == "")
     S.Documentation = O.Documentation;
   if (S.ReturnType == "")
     S.ReturnType = O.ReturnType;
-  if (S.IncludeHeader == "")
-    S.IncludeHeader = O.IncludeHeader;
+  for (const auto &OI : O.IncludeHeaders) {
+    bool Found = false;
+    for (auto &SI : S.IncludeHeaders) {
+      if (SI.IncludeHeader == OI.IncludeHeader) {
+        Found = true;
+        SI.References += OI.References;
+        break;
+      }
+    }
+    if (!Found && MergeIncludes)
+      S.IncludeHeaders.emplace_back(OI.IncludeHeader, OI.References);
+  }
 
   S.Origin |= O.Origin | SymbolOrigin::Merge;
   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.cpp

bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
   if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
     if (auto Header =
             getIncludeHeader(Name->getName(), SM,
                              SM.getExpansionLoc(MI->getDefinitionLoc()), Opts))
       Include = std::move(*Header);
   }
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
-  S.IncludeHeader = Include;
+  if (!Include.empty())
+    S.IncludeHeaders.emplace_back(Include, 1);
+
   Symbols.insert(S);
   return true;
 }
 
 void SymbolCollector::finish() {
   // At the end of the TU, add 1 to the refcount of all referenced symbols.
   auto IncRef = [this](const SymbolID &ID) {
     if (const auto *S = Symbols.find(ID)) {
if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
     if (auto Header = getIncludeHeader(
             QName, SM, SM.getExpansionLoc(ND.getLocation()), Opts))
       Include = std::move(*Header);
   }
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
   S.Documentation = Documentation;
   S.ReturnType = ReturnType;
-  S.IncludeHeader = Include;
+  if (!Include.empty())
+    S.IncludeHeaders.emplace_back(Include, 1);
 
   S.Origin = Opts.Origin;
   Symbols.insert(S);
   return Symbols.find(S.ID);
 }
 
 void SymbolCollector::addDefinition(const NamedDecl &ND,
                                     const Symbol &DeclSym) {

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

 //===--- SymbolYAML.cpp ------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolYAML.h"
 #include "Index.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
 LLVM_YAML_IS_DOCUMENT_LIST_VECTOR(clang::clangd::Symbol)
+LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol::IncludeHeaderWithReferences)
 
 namespace llvm {
 namespace yaml {
 
 using clang::clangd::Symbol;
 using clang::clangd::SymbolID;
 using clang::clangd::SymbolLocation;
 using clang::index::SymbolInfo;

 template <> struct MappingTraits<SymbolInfo> {
   static void mapping(IO &io, SymbolInfo &SymInfo) {
     // FIXME: expose other fields?
     io.mapRequired("Kind", SymInfo.Kind);
     io.mapRequired("Lang", SymInfo.Lang);
   }
 };
 
+template <>
+struct MappingTraits<clang::clangd::Symbol::IncludeHeaderWithReferences> {
+  static void mapping(IO &io,
+                      clang::clangd::Symbol::IncludeHeaderWithReferences &Inc) {
+    io.mapRequired("Header", Inc.IncludeHeader);
+    io.mapRequired("References", Inc.References);
+  }
+};
+
 template <> struct MappingTraits<Symbol> {
   static void mapping(IO &IO, Symbol &Sym) {
     MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(IO, Sym.ID);
     IO.mapRequired("ID", NSymbolID->HexString);
     IO.mapRequired("Name", Sym.Name);
     IO.mapRequired("Scope", Sym.Scope);
     IO.mapRequired("SymInfo", Sym.SymInfo);
     IO.mapOptional("CanonicalDeclaration", Sym.CanonicalDeclaration,
                    SymbolLocation());
     IO.mapOptional("Definition", Sym.Definition, SymbolLocation());
     IO.mapOptional("References", Sym.References, 0u);
     IO.mapOptional("IsIndexedForCodeCompletion", Sym.IsIndexedForCodeCompletion,
                    false);
     IO.mapOptional("Signature", Sym.Signature);
     IO.mapOptional("CompletionSnippetSuffix", Sym.CompletionSnippetSuffix);
     IO.mapOptional("Documentation", Sym.Documentation);
     IO.mapOptional("ReturnType", Sym.ReturnType);
-    IO.mapOptional("IncludeHeader", Sym.IncludeHeader);
+    IO.mapOptional("IncludeHeaders", Sym.IncludeHeaders);
   }
 };
 
 template <> struct ScalarEnumerationTraits<SymbolLanguage> {
   static void enumeration(IO &IO, SymbolLanguage &Value) {
     IO.enumCase(Value, "C", SymbolLanguage::C);
     IO.enumCase(Value, "Cpp", SymbolLanguage::CXX);
     IO.enumCase(Value, "ObjC", SymbolLanguage::ObjC);

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

 MATCHER_P(Qualifier, Q, "") { return arg.RequiredQualifier == Q; }
 MATCHER_P(Labeled, Label, "") {
   return arg.RequiredQualifier + arg.Name + arg.Signature == Label;
 }
 MATCHER_P(SigHelpLabeled, Label, "") { return arg.label == Label; }
 MATCHER_P(Kind, K, "") { return arg.Kind == K; }
 MATCHER_P(Doc, D, "") { return arg.Documentation == D; }
 MATCHER_P(ReturnType, D, "") { return arg.ReturnType == D; }
+MATCHER_P(HasInclude, IncludeHeader, "") {
+  return !arg.Includes.empty() && arg.Includes[0].Header == IncludeHeader;
+}
 MATCHER_P(InsertInclude, IncludeHeader, "") {
-  return arg.Header == IncludeHeader && bool(arg.HeaderInsertion);
+  return !arg.Includes.empty() && arg.Includes[0].Header == IncludeHeader &&
+         bool(arg.Includes[0].Insertion);
+}
+MATCHER(InsertInclude, "") {
+  return !arg.Includes.empty() && bool(arg.Includes[0].Insertion);
 }
-MATCHER(InsertInclude, "") { return bool(arg.HeaderInsertion); }
 MATCHER_P(SnippetSuffix, Text, "") { return arg.SnippetSuffix == Text; }
 MATCHER_P(Origin, OriginSet, "") { return arg.Origin == OriginSet; }
 
 // Shorthand for Contains(Named(Name)).
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name) {
   return Contains(Named(std::move(Name)));
 }
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name,
TEST(CompletionTest, IncludeInsertionPreprocessorIntegrationTests) {
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = "";
 
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
   auto BarURI = URI::createFile(BarHeader).toString();
   Symbol Sym = cls("ns::X");
   Sym.CanonicalDeclaration.FileURI = BarURI;
-  Sym.IncludeHeader = BarURI;
+  Sym.IncludeHeaders.emplace_back(BarURI, 1);
   // Shoten include path based on search dirctory and insert.
   auto Results = completions(Server,
                              R"cpp(
           int main() { ns::^ }
       )cpp",
                              {Sym});
   EXPECT_THAT(Results.Completions,
               ElementsAre(AllOf(Named("X"), InsertInclude("\"bar.h\""))));
TEST(CompletionTest, NoIncludeInsertionWhenDeclFoundInFile) {
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
   Symbol SymX = cls("ns::X");
   Symbol SymY = cls("ns::Y");
   std::string BarHeader = testPath("bar.h");
   auto BarURI = URI::createFile(BarHeader).toString();
   SymX.CanonicalDeclaration.FileURI = BarURI;
   SymY.CanonicalDeclaration.FileURI = BarURI;
-  SymX.IncludeHeader = "<bar>";
-  SymY.IncludeHeader = "<bar>";
+  SymX.IncludeHeaders.emplace_back("<bar>", 1);
+  SymY.IncludeHeaders.emplace_back("<bar>", 1);
   // Shoten include path based on search dirctory and insert.
   auto Results = completions(Server,
                              R"cpp(
           namespace ns {
             class X;
             class Y {}
           }
           int main() { ns::^ }
TEST(CompletionTest, OverloadBundling) {
   Symbol NoArgsGFunc = func("GFuncC");
   EXPECT_THAT(
       completions(Context + "int y = GFunc^", {NoArgsGFunc}, Opts).Completions,
       UnorderedElementsAre(Labeled("GFuncC(…)"), Labeled("GFuncD(int)")));
 
   // Differences in header-to-insert suppress bundling.
   std::string DeclFile = URI::createFile(testPath("foo")).toString();
   NoArgsGFunc.CanonicalDeclaration.FileURI = DeclFile;
-  NoArgsGFunc.IncludeHeader = "<foo>";
+  NoArgsGFunc.IncludeHeaders.emplace_back("<foo>", 1);
   EXPECT_THAT(
       completions(Context + "int y = GFunc^", {NoArgsGFunc}, Opts).Completions,
       UnorderedElementsAre(AllOf(Named("GFuncC"), InsertInclude("<foo>")),
                            Labeled("GFuncC(int)"), Labeled("GFuncD(int)")));
 
   // Examine a bundled completion in detail.
   auto A =
       completions(Context + "int y = X().a^", {}, Opts).Completions.front();
TEST(CompletionTest, Render) {
   CodeCompletion C;
   C.Name = "x";
   C.Signature = "(bool) const";
   C.SnippetSuffix = "(${0:bool})";
   C.ReturnType = "int";
   C.RequiredQualifier = "Foo::";
   C.Scope = "ns::Foo::";
   C.Documentation = "This is x().";
-  C.Header = "\"foo.h\"";
+  C.Includes.emplace_back();
+  auto &Include = C.Includes.back();
+  Include.Header = "\"foo.h\"";
   C.Kind = CompletionItemKind::Method;
   C.Score.Total = 1.0;
   C.Origin = SymbolOrigin::AST | SymbolOrigin::Static;
 
   CodeCompleteOptions Opts;
   Opts.IncludeIndicator.Insert = "^";
   Opts.IncludeIndicator.NoInsert = "";
   Opts.EnableSnippets = false;
 
   auto R = C.render(Opts);
   EXPECT_EQ(R.label, "Foo::x(bool) const");
   EXPECT_EQ(R.insertText, "Foo::x");
   EXPECT_EQ(R.insertTextFormat, InsertTextFormat::PlainText);
   EXPECT_EQ(R.filterText, "x");
   EXPECT_EQ(R.detail, "int\n\"foo.h\"");
   EXPECT_EQ(R.documentation, "This is x().");
   EXPECT_THAT(R.additionalTextEdits, IsEmpty());
   EXPECT_EQ(R.sortText, sortText(1.0, "x"));
 
   Opts.EnableSnippets = true;
   R = C.render(Opts);
   EXPECT_EQ(R.insertText, "Foo::x(${0:bool})");
   EXPECT_EQ(R.insertTextFormat, InsertTextFormat::Snippet);
 
-  C.HeaderInsertion.emplace();
+  Include.Insertion.emplace();
   R = C.render(Opts);
   EXPECT_EQ(R.label, "^Foo::x(bool) const");
   EXPECT_THAT(R.additionalTextEdits, Not(IsEmpty()));
 
   Opts.ShowOrigins = true;
   R = C.render(Opts);
   EXPECT_EQ(R.label, "^[AS]Foo::x(bool) const");
 
TEST(CompletionTest, EnableSpeculativeIndexRequest) {
 
   CompleteAtPoint("3");
   // Speculation failed. Sent speculative index request and the new index
   // request after sema.
   auto Reqs3 = Requests.consumeRequests();
   ASSERT_EQ(Reqs3.size(), 2u);
 }
 
+TEST(CompletionTest, InsertTheMostPopularHeader) {
+  std::string DeclFile = URI::createFile(testPath("foo")).toString();
+  Symbol sym = func("Func");
+  sym.CanonicalDeclaration.FileURI = DeclFile;
+  sym.IncludeHeaders.emplace_back("\"foo.h\"", 2);
+  sym.IncludeHeaders.emplace_back("\"bar.h\"", 1000);
+
+  auto Results = completions("Fun^", {sym}).Completions;
+  assert(!Results.empty());
+  EXPECT_THAT(Results[0], AllOf(Named("Func"), InsertInclude("\"bar.h\"")));
+  EXPECT_EQ(Results[0].Includes.size(), 2u);
+}
+
+TEST(CompletionTest, NoInsertIncludeIfOnePresent) {
+  MockFSProvider FS;
+  MockCompilationDatabase CDB;
+
+  std::string FooHeader = testPath("foo.h");
+  FS.Files[FooHeader] = "";
+
+  IgnoreDiagnostics DiagConsumer;
+  ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
+
+  std::string DeclFile = URI::createFile(testPath("foo")).toString();
+  Symbol sym = func("Func");
+  sym.CanonicalDeclaration.FileURI = DeclFile;
+  sym.IncludeHeaders.emplace_back("\"foo.h\"", 2);
+  sym.IncludeHeaders.emplace_back("\"bar.h\"", 1000);
+
+  EXPECT_THAT(
+      completions(Server, "#include \"foo.h\"\nFun^", {sym}).Completions,
+      UnorderedElementsAre(
+          AllOf(Named("Func"), HasInclude("\"foo.h\""), Not(InsertInclude()))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 TEST(FileIndexTest, NoIncludeCollected) {
   FileIndex M;
   update(M, "f", "class string {};");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   bool SeenSymbol = false;
   M.fuzzyFind(Req, [&](const Symbol &Sym) {
-    EXPECT_TRUE(Sym.IncludeHeader.empty());
+    EXPECT_TRUE(Sym.IncludeHeaders.empty());
     SeenSymbol = true;
   });
   EXPECT_TRUE(SeenSymbol);
 }
 
 TEST(FileIndexTest, TemplateParamsInLabel) {
   auto Source = R"cpp(
 template <class Ty>

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

TEST(MergeIndexTest, FindOccurrences) {
 
   EXPECT_THAT(Results, UnorderedElementsAre(
                            AllOf(OccurrenceRange(Test1Code.range("Foo")),
                                  FileURI("unittest:///test.cc")),
                            AllOf(OccurrenceRange(Test2Code.range("Foo")),
                                  FileURI("unittest:///test2.cc"))));
 }
 
+MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References,  "") {
+  return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
+}
+
+TEST(MergeTest, MergeIncludesOnDifferentDefinitions) {
+  Symbol L, R;
+  L.Name = "left";
+  R.Name = "right";
+  L.ID = R.ID = SymbolID("hello");
+  L.IncludeHeaders.emplace_back("common", 1);
+  R.IncludeHeaders.emplace_back("common", 1);
+  R.IncludeHeaders.emplace_back("new", 1);
+
+  // Both have no definition.
+  Symbol M = mergeSymbol(L, R);
+  EXPECT_THAT(M.IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
+                                   IncludeHeaderWithRef("new", 1u)));
+
+  // Only merge references of the same includes but do not merge new #includes.
+  L.Definition.FileURI = "file:/left.h";
+  M = mergeSymbol(L, R);
+  EXPECT_THAT(M.IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef("common", 2u)));
+
+  // Definitions are the same.
+  R.Definition.FileURI = "file:/right.h";
+  M = mergeSymbol(L, R);
+  EXPECT_THAT(M.IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
+                                   IncludeHeaderWithRef("new", 1u)));
+
+  // Definitions are different.
+  R.Definition.FileURI = "file:/right.h";
+  M = mergeSymbol(L, R);
+  EXPECT_THAT(M.IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
+                                   IncludeHeaderWithRef("new", 1u)));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 MATCHER_P(ReturnType, D, "") { return arg.ReturnType == D; }
 MATCHER_P(Doc, D, "") { return arg.Documentation == D; }
 MATCHER_P(Snippet, S, "") {
   return (arg.Name + arg.CompletionSnippetSuffix).str() == S;
 }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
 MATCHER_P(DeclURI, P, "") { return arg.CanonicalDeclaration.FileURI == P; }
 MATCHER_P(DefURI, P, "") { return arg.Definition.FileURI == P; }
-MATCHER_P(IncludeHeader, P, "") { return arg.IncludeHeader == P; }
+MATCHER_P(IncludeHeader, P, "") {
+  return (arg.IncludeHeaders.size() == 1) &&
+         (arg.IncludeHeaders.begin()->IncludeHeader == P);
+}
+MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References,  "") {
+  return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
+}
 MATCHER_P(DeclRange, Pos, "") {
   return std::tie(arg.CanonicalDeclaration.Start.Line,
                   arg.CanonicalDeclaration.Start.Column,
                   arg.CanonicalDeclaration.End.Line,
                   arg.CanonicalDeclaration.End.Column) ==
          std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
                   Pos.end.character);
 }
Start:
     Line: 1
     Column: 0
   End:
     Line: 1
     Column: 1
 IsIndexedForCodeCompletion:    true
 Documentation:    'Foo doc'
 ReturnType:    'int'
+IncludeHeaders:
+  - Header:    'include1'
+    References:    7
+  - Header:    'include2'
+    References:    3
 ...
 )";
   const std::string YAML2 = R"(
 ---
 ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858
 Name:   'Foo2'
 Scope:   'clang::'
 SymInfo:
)";
 
   auto Symbols1 = symbolsFromYAML(YAML1);
 
   EXPECT_THAT(Symbols1,
               UnorderedElementsAre(AllOf(QName("clang::Foo1"), Labeled("Foo1"),
                                          Doc("Foo doc"), ReturnType("int"),
                                          DeclURI("file:///path/foo.h"),
                                          ForCodeCompletion(true))));
+  auto &Sym1 = *Symbols1.begin();
+  EXPECT_THAT(Sym1.IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef("include1", 7u),
+                                   IncludeHeaderWithRef("include2", 3u)));
   auto Symbols2 = symbolsFromYAML(YAML2);
   EXPECT_THAT(Symbols2, UnorderedElementsAre(AllOf(
                             QName("clang::Foo2"), Labeled("Foo2-sig"),
                             Not(HasReturnType()), DeclURI("file:///path/bar.h"),
                             ForCodeCompletion(false))));
 
   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")));
 }
 
 TEST_F(SymbolCollectorTest, IncludeHeaderSameAsFileURI) {
   CollectorOpts.CollectIncludePath = true;
   runSymbolCollector("class Foo {};", /*Main=*/"");
-  EXPECT_THAT(Symbols,
-              UnorderedElementsAre(AllOf(QName("Foo"), DeclURI(TestHeaderURI),
-                                         IncludeHeader(TestHeaderURI))));
+  EXPECT_THAT(Symbols, UnorderedElementsAre(
+                           AllOf(QName("Foo"), DeclURI(TestHeaderURI))));
+  EXPECT_THAT(Symbols.begin()->IncludeHeaders,
+              UnorderedElementsAre(IncludeHeaderWithRef(TestHeaderURI, 1u)));
 }
 
 #ifndef _WIN32
 TEST_F(SymbolCollectorTest, CanonicalSTLHeader) {
   CollectorOpts.CollectIncludePath = true;
   CanonicalIncludes Includes;
   addSystemHeadersMapping(&Includes);
   CollectorOpts.Includes = &Includes;