[clangd] Extract scoring/ranking logic, and shave yaks.

[sammccall]

Summary

Code completion scoring was embedded in CodeComplete.cpp, which is bad:

• awkward to test. The mechanisms (extracting info from index/sema) can be unit-tested well, the policy (scoring) should be quantitatively measured. Neither was easily possible, and debugging was hard. The intermediate signal struct makes this easier.
• hard to reuse. This is a bug in workspaceSymbols: it just presents the results in the index order, which is not sorted in practice, it needs to rank them! Also, index implementations care about scoring (both query-dependent and independent) in order to truncate result lists appropriately.

The main yak shaved here is the build() function that had 3 variants across
unit tests is unified in TestTU.h (rather than adding a 4th variant).

[ilya-biryukov]

The change makes both testing and scoring code better.
Even though those are largely independent changes, perfectly happy to review them together.

I mostly have NITs here, overall the changes LG.

clangd/CodeComplete.cpp

36 ↗

(On Diff #145458)

Is this used by DEBUG() macro?
It would be nice to have a short comment saying why we need this define.

909 ↗

(On Diff #145458)

NIT: Maybe use float here instead of auto? Would remove the need to look at evaluate for anyone reading the code for the first time.

clangd/Quality.cpp

83 ↗

(On Diff #145458)

This function does not seem to be exposed outside this C++ file. Maybe add static?

clangd/Quality.h

45 ↗

(On Diff #145458)

Maybe use doxygen-style comments to be consistent with the rest of LLVM?

66 ↗

(On Diff #145458)

Maybe rename to Inaccessible? It seems to be closer to what this bool means in C++, if I'm reading the code correctly.
Or add a comment explaining what "unavailable" means?

80 ↗

(On Diff #145458)

As you mentioned in the change description, moving TopN and sortText to a separate file might be a good idea since they don't depend on various clangd-specific bits.
But I'm perfectly happy to leave it as is and do this later if needed.

119 ↗

(On Diff #145458)

Maybe mention that it's used for LSP sortText? To give a bit more context on why we need this function.

unittests/clangd/TestTU.cpp

56 ↗

(On Diff #145458)

Maybe add braces for the loop body here? It seems to be long enough that it could actually, arguably, improve readability.
We could some nesting by inverting the condition too:
if (QName != ...) continue;

62 ↗

(On Diff #145458)

Maybe use FAIL() instead of ADD_FAILURE() followed by llvm_unreachable()?
llvm_unreachable may produce surprising behaviors, i.e. miscompiles in opt mode etc, IIUC.
Both failing or returning a first matching symbol while also signalling an error seem like good alternatives here.

unittests/clangd/TestTU.h

28 ↗

(On Diff #145458)

I really like this helper, now that we can reuse the code between different tests!
It took me some time to get the semantics of this constructor, though.
I suggest to have a few constructor functions with more descriptive name (my names are not great, but should give the idea):

static TestTU FromSourceFile(StringRef Code);
static TestTU FromHeaderFile(StringRef Code);
static TestTU WithImplicitInclude(StringRef Source, StringRef IncludedHeader);

[sammccall]

Address comments

[sammccall]

clangd/CodeComplete.cpp

909 ↗

(On Diff #145458)

Done. I was worried we might switch to double one day, seems unlikely.

clangd/Quality.h

66 ↗

(On Diff #145458)

So it's Unavailable || Inaccessible, where neither is all that well-defined :-)
I renamed to Forbidden to avoid conflation with either, and added examples as a comment.

80 ↗

(On Diff #145458)

Yeah, I'd rather punt on this for now to avoid creating too many tiny files and a random standard library supplement. If TopN is pulled out, llvm/Support might be a better place for it.

119 ↗

(On Diff #145458)

Oops, I wrote the comment but put it in the cpp file by mistake...

unittests/clangd/TestTU.cpp

62 ↗

(On Diff #145458)

FAIL() is the same as ADD_FAILURE() but it causes the enclosing function to immediately return - it can only be used from void functions.

llvm_unreachable may produce surprising behaviors, i.e. miscompiles in opt mode etc, IIUC

Right. After offline discussion, we don't care about asserts-disabled test behavior if the asserts-enabled failure is sensible, so just replaced with an assert.

unittests/clangd/TestTU.h

28 ↗

(On Diff #145458)

Done, Just added withCode and withHeaderCode for now, and anyone who wants something more complicated can set the fields directly.
(The names mirror the struct fields)

[ilya-biryukov]

The new uploaded diff has lots of unrelated changes to clang-tidy, clang-move, etc...
Looking at commits, it seems arc diff was called with the wrong base commit...
Could you please reupload the change?

clangd/Quality.h

45 ↗

(On Diff #145458)

Some changes are missing?
File still uses 2-slash instead of 3-slash comments.

66 ↗

(On Diff #145458)

Thanks! Forbidden with a comment LG.

unittests/clangd/TestTU.h

28 ↗

(On Diff #145458)

LG, thanks.

[sammccall]

fix diffbase?

[sammccall]

Doxygen

[ilya-biryukov]

LGTM

clang-tools-extra/trunk/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp
   ProtocolHandlers.cpp
+  Quality.cpp
   SourceCode.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp

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

 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Logger.h"
+#include "Quality.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "URI.h"
 #include "index/Index.h"
 #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/Support/Format.h"
 #include <queue>
 
+// We log detailed candidate here if you run with -debug-only=codecomplete.
+#define DEBUG_TYPE "codecomplete"
+
 namespace clang {
 namespace clangd {
 namespace {
 
 CompletionItemKind toCompletionItemKind(CXCursorKind CursorKind) {
   switch (CursorKind) {
   case CXCursor_MacroInstantiation:
   case CXCursor_MacroDefinition:
for (const auto &Chunk : CCS) {
     default:
       Result += Chunk.Text;
       break;
     }
   }
   return Result;
 }
 
-// Produces an integer that sorts in the same order as F.
-// That is: a < b <==> encodeFloat(a) < encodeFloat(b).
-uint32_t encodeFloat(float F) {
-  static_assert(std::numeric_limits<float>::is_iec559, "");
-  static_assert(sizeof(float) == sizeof(uint32_t), "");
-  constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);
-
-  // Get the bits of the float. Endianness is the same as for integers.
-  uint32_t U;
-  memcpy(&U, &F, sizeof(float));
-  // IEEE 754 floats compare like sign-magnitude integers.
-  if (U & TopBit)    // Negative float.
-    return 0 - U;    // Map onto the low half of integers, order reversed.
-  return U + TopBit; // Positive floats map onto the high half of integers.
-}
-
-// Returns a string that sorts in the same order as (-Score, Name), for LSP.
-std::string sortText(float Score, llvm::StringRef Name) {
-  // We convert -Score to an integer, and hex-encode for readability.
-  // Example: [0.5, "foo"] -> "41000000foo"
-  std::string S;
-  llvm::raw_string_ostream OS(S);
-  write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
-            /*Width=*/2 * sizeof(Score));
-  OS << Name;
-  OS.flush();
-  return S;
-}
-
 /// Creates a `HeaderFile` from \p Header which can be either a URI or a literal
 /// include.
 static llvm::Expected<HeaderFile> toHeaderFile(StringRef Header,
                                                llvm::StringRef HintPath) {
   if (isLiteralInclude(Header))
     return HeaderFile{Header.str(), /*Verbatim=*/true};
   auto U = URI::parse(Header);
   if (!U)

 /// 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;
 
-  // Computes the "symbol quality" score for this completion. Higher is better.
-  float score() const {
-    float Score = 1;
-    if (IndexResult)
-      Score *= quality(*IndexResult);
-    if (SemaResult) {
-      // For now we just use the Sema priority, mapping it onto a 0-2 interval.
-      // That makes 1 neutral-ish, so we don't reward/penalize non-Sema results.
-      // Priority 80 is a really bad score.
-      Score *= 2 - std::min<float>(80, SemaResult->Priority) / 40;
-
-      switch (static_cast<CXAvailabilityKind>(SemaResult->Availability)) {
-      case CXAvailability_Available:
-        // No penalty.
-        break;
-      case CXAvailability_Deprecated:
-        Score *= 0.1f;
-        break;
-      case CXAvailability_NotAccessible:
-      case CXAvailability_NotAvailable:
-        Score = 0;
-        break;
-      }
-    }
-    return Score;
-  }
-
   // Builds an LSP completion item.
   CompletionItem build(StringRef FileName, const CompletionItemScores &Scores,
                        const CodeCompleteOptions &Opts,
                        CodeCompletionString *SemaCCS,
                        const IncludeInserter *Includes) const {
     assert(bool(SemaResult) == bool(SemaCCS));
     CompletionItem I;
     if (SemaResult) {
CompletionItem build(StringRef FileName, const CompletionItemScores &Scores,
     }
     I.scoreInfo = Scores;
     I.sortText = sortText(Scores.finalScore, Name);
     I.insertTextFormat = Opts.EnableSnippets ? InsertTextFormat::Snippet
                                              : InsertTextFormat::PlainText;
     return I;
   }
 };
+using ScoredCandidate = std::pair<CompletionCandidate, CompletionItemScores>;
 
 // Determine the symbol ID for a Sema code completion result, if possible.
 llvm::Optional<SymbolID> getSymbolID(const CodeCompletionResult &R) {
   switch (R.Kind) {
   case CodeCompletionResult::RK_Declaration:
   case CodeCompletionResult::RK_Pattern: {
     llvm::SmallString<128> USR;
     if (/*Ignore=*/clang::index::generateUSRForDecl(R.Declaration, USR))

 
 private:
   CodeCompleteOptions Opts;
   std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
   CodeCompletionTUInfo CCTUInfo;
   UniqueFunction<void()> ResultsCallback;
 };
 
-// Tracks a bounded number of candidates with the best scores.
-class TopN {
-public:
-  using value_type = std::pair<CompletionCandidate, CompletionItemScores>;
-  static constexpr size_t Unbounded = std::numeric_limits<size_t>::max();
-
-  TopN(size_t N) : N(N) {}
-
-  // Adds a candidate to the set.
-  // Returns true if a candidate was dropped to get back under N.
-  bool push(value_type &&V) {
-    bool Dropped = false;
-    if (Heap.size() >= N) {
-      Dropped = true;
-      if (N > 0 && greater(V, Heap.front())) {
-        std::pop_heap(Heap.begin(), Heap.end(), greater);
-        Heap.back() = std::move(V);
-        std::push_heap(Heap.begin(), Heap.end(), greater);
-      }
-    } else {
-      Heap.push_back(std::move(V));
-      std::push_heap(Heap.begin(), Heap.end(), greater);
-    }
-    assert(Heap.size() <= N);
-    assert(std::is_heap(Heap.begin(), Heap.end(), greater));
-    return Dropped;
-  }
-
-  // Returns candidates from best to worst.
-  std::vector<value_type> items() && {
-    std::sort_heap(Heap.begin(), Heap.end(), greater);
-    assert(Heap.size() <= N);
-    return std::move(Heap);
-  }
-
-private:
-  static bool greater(const value_type &L, const value_type &R) {
+struct ScoredCandidateGreater {
+  bool operator()(const ScoredCandidate &L, const ScoredCandidate &R) {
     if (L.second.finalScore != R.second.finalScore)
       return L.second.finalScore > R.second.finalScore;
     return L.first.Name < R.first.Name; // Earlier name is better.
   }
-
-  const size_t N;
-  std::vector<value_type> Heap; // Min-heap, comparator is greater().
 };
 
 class SignatureHelpCollector final : public CodeCompleteConsumer {
 
 public:
   SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
                          SignatureHelp &SigHelp)
       : CodeCompleteConsumer(CodeCompleteOpts, /*OutputIsBinary=*/false),
private:
 
   // Merges the Sema and Index results where possible, scores them, and
   // returns the top results from best to worst.
   std::vector<std::pair<CompletionCandidate, CompletionItemScores>>
   mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
                const SymbolSlab &IndexResults) {
     trace::Span Tracer("Merge and score results");
     // We only keep the best N results at any time, in "native" format.
-    TopN Top(Opts.Limit == 0 ? TopN::Unbounded : Opts.Limit);
+    TopN<ScoredCandidate, ScoredCandidateGreater> Top(
+        Opts.Limit == 0 ? std::numeric_limits<size_t>::max() : Opts.Limit);
     llvm::DenseSet<const Symbol *> UsedIndexResults;
     auto CorrespondingIndexResult =
         [&](const CodeCompletionResult &SemaResult) -> const Symbol * {
       if (auto SymID = getSymbolID(SemaResult)) {
         auto I = IndexResults.find(*SymID);
         if (I != IndexResults.end()) {
           UsedIndexResults.insert(&*I);
           return &*I;
for (const auto &IndexResult : IndexResults) {
       if (UsedIndexResults.count(&IndexResult))
         continue;
       addCandidate(Top, /*SemaResult=*/nullptr, &IndexResult);
     }
     return std::move(Top).items();
   }
 
   // Scores a candidate and adds it to the TopN structure.
-  void addCandidate(TopN &Candidates, const CodeCompletionResult *SemaResult,
+  void addCandidate(TopN<ScoredCandidate, ScoredCandidateGreater> &Candidates,
+                    const CodeCompletionResult *SemaResult,
                     const Symbol *IndexResult) {
     CompletionCandidate C;
     C.SemaResult = SemaResult;
     C.IndexResult = IndexResult;
     C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
 
-    CompletionItemScores Scores;
+    SymbolQualitySignals Quality;
+    SymbolRelevanceSignals Relevance;
     if (auto FuzzyScore = Filter->match(C.Name))
-      Scores.filterScore = *FuzzyScore;
+      Relevance.NameMatch = *FuzzyScore;
     else
       return;
-    Scores.symbolScore = C.score();
-    // We score candidates by multiplying symbolScore ("quality" of the result)
-    // with filterScore (how well it matched the query).
-    // This is sensitive to the distribution of both component scores!
-    Scores.finalScore = Scores.filterScore * Scores.symbolScore;
+    if (IndexResult)
+      Quality.merge(*IndexResult);
+    if (SemaResult) {
+      Quality.merge(*SemaResult);
+      Relevance.merge(*SemaResult);
+    }
+
+    float QualScore = Quality.evaluate(), RelScore = Relevance.evaluate();
+    CompletionItemScores Scores;
+    Scores.finalScore = evaluateSymbolAndRelevance(QualScore, RelScore);
+    // The purpose of exporting component scores is to allow NameMatch to be
+    // replaced on the client-side. So we export (NameMatch, final/NameMatch)
+    // rather than (RelScore, QualScore).
+    Scores.filterScore = Relevance.NameMatch;
+    Scores.symbolScore =
+        Scores.filterScore ? Scores.finalScore / Scores.filterScore : QualScore;
+
+    DEBUG(llvm::dbgs() << "CodeComplete: " << C.Name
+                       << (IndexResult ? " (index)" : "")
+                       << (SemaResult ? " (sema)" : "") << " = "
+                       << Scores.finalScore << "\n"
+                       << Quality << Relevance << "\n");
 
     NSema += bool(SemaResult);
     NIndex += bool(IndexResult);
     NBoth += SemaResult && IndexResult;
     if (Candidates.push({C, Scores}))
       Incomplete = true;
   }
 

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

+//===--- Quality.h - Ranking alternatives for ambiguous queries -*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+///
+/// Some operations such as code completion produce a set of candidates.
+/// Usually the user can choose between them, but we should put the best options
+/// at the top (they're easier to select, and more likely to be seen).
+///
+/// This file defines building blocks for ranking candidates.
+/// It's used by the features directly and also in the implementation of
+/// indexes, as indexes also need to heuristically limit their results.
+///
+/// The facilities here are:
+///   - retrieving scoring signals from e.g. indexes, AST, CodeCompletionString
+///     These are structured in a way that they can be debugged, and are fairly
+///     consistent regardless of the source.
+///   - compute scores from scoring signals. These are suitable for sorting.
+///   - sorting utilities like the TopN container.
+/// These could be split up further to isolate dependencies if we care.
+///
+//===---------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_QUALITY_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_QUALITY_H
+#include "llvm/ADT/StringRef.h"
+#include <algorithm>
+#include <functional>
+#include <vector>
+namespace llvm {
+class raw_ostream;
+}
+namespace clang {
+class CodeCompletionResult;
+namespace clangd {
+struct Symbol;
+
+// Signals structs are designed to be aggregated from 0 or more sources.
+// A default instance has neutral signals, and sources are merged into it.
+// They can be dumped for debugging, and evaluate()d into a score.
+
+/// Attributes of a symbol that affect how much we like it.
+struct SymbolQualitySignals {
+  unsigned SemaCCPriority = 0; // 1-80, 1 is best. 0 means absent.
+                               // FIXME: this is actually a mix of symbol
+                               //        quality and relevance. Untangle this.
+  bool Deprecated = false;
+  unsigned References = 0;
+
+  void merge(const CodeCompletionResult &SemaCCResult);
+  void merge(const Symbol &IndexResult);
+
+  // Condense these signals down to a single number, higher is better.
+  float evaluate() const;
+};
+llvm::raw_ostream &operator<<(llvm::raw_ostream &,
+                              const SymbolQualitySignals &);
+
+/// Attributes of a symbol-query pair that affect how much we like it.
+struct SymbolRelevanceSignals {
+  // 0-1 fuzzy-match score for unqualified name. Must be explicitly assigned.
+  float NameMatch = 1;
+  bool Forbidden = false; // Unavailable (e.g const) or inaccessible (private).
+
+  void merge(const CodeCompletionResult &SemaResult);
+
+  // Condense these signals down to a single number, higher is better.
+  float evaluate() const;
+};
+llvm::raw_ostream &operator<<(llvm::raw_ostream &,
+                              const SymbolRelevanceSignals &);
+
+/// Combine symbol quality and relevance into a single score.
+float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance);
+
+/// TopN<T> is a lossy container that preserves only the "best" N elements.
+template <typename T, typename Compare = std::greater<T>> class TopN {
+public:
+  using value_type = T;
+  TopN(size_t N, Compare Greater = Compare())
+      : N(N), Greater(std::move(Greater)) {}
+
+  // Adds a candidate to the set.
+  // Returns true if a candidate was dropped to get back under N.
+  bool push(value_type &&V) {
+    bool Dropped = false;
+    if (Heap.size() >= N) {
+      Dropped = true;
+      if (N > 0 && Greater(V, Heap.front())) {
+        std::pop_heap(Heap.begin(), Heap.end(), Greater);
+        Heap.back() = std::move(V);
+        std::push_heap(Heap.begin(), Heap.end(), Greater);
+      }
+    } else {
+      Heap.push_back(std::move(V));
+      std::push_heap(Heap.begin(), Heap.end(), Greater);
+    }
+    assert(Heap.size() <= N);
+    assert(std::is_heap(Heap.begin(), Heap.end(), Greater));
+    return Dropped;
+  }
+
+  // Returns candidates from best to worst.
+  std::vector<value_type> items() && {
+    std::sort_heap(Heap.begin(), Heap.end(), Greater);
+    assert(Heap.size() <= N);
+    return std::move(Heap);
+  }
+
+private:
+  const size_t N;
+  std::vector<value_type> Heap; // Min-heap, comparator is Greater.
+  Compare Greater;
+};
+
+/// Returns a string that sorts in the same order as (-Score, Tiebreak), for LSP.
+/// (The highest score compares smallest so it sorts at the top).
+std::string sortText(float Score, llvm::StringRef Tiebreak = "");
+
+} // namespace clangd
+} // namespace clang
+
+#endif

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

+//===--- Quality.cpp --------------------------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+#include "Quality.h"
+#include "index/Index.h"
+#include "clang/Sema/CodeCompleteConsumer.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace clangd {
+using namespace llvm;
+
+void SymbolQualitySignals::merge(const CodeCompletionResult &SemaCCResult) {
+  SemaCCPriority = SemaCCResult.Priority;
+
+  if (SemaCCResult.Availability == CXAvailability_Deprecated)
+    Deprecated = true;
+}
+
+void SymbolQualitySignals::merge(const Symbol &IndexResult) {
+  References = std::max(IndexResult.References, References);
+}
+
+float SymbolQualitySignals::evaluate() const {
+  float Score = 1;
+
+  // This avoids a sharp gradient for tail symbols, and also neatly avoids the
+  // question of whether 0 references means a bad symbol or missing data.
+  if (References >= 3)
+    Score *= std::log(References);
+
+  if (SemaCCPriority)
+    // Map onto a 0-2 interval, so we don't reward/penalize non-Sema results.
+    // Priority 80 is a really bad score.
+    Score *= 2 - std::min<float>(80, SemaCCPriority) / 40;
+
+  if (Deprecated)
+    Score *= 0.1;
+
+  return Score;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const SymbolQualitySignals &S) {
+  OS << formatv("=== Symbol quality: {0}\n", S.evaluate());
+  if (S.SemaCCPriority)
+    OS << formatv("\tSemaCCPriority: {0}\n", S.SemaCCPriority);
+  OS << formatv("\tReferences: {0}\n", S.References);
+  OS << formatv("\tDeprecated: {0}\n", S.Deprecated);
+  return OS;
+}
+
+void SymbolRelevanceSignals::merge(const CodeCompletionResult &SemaCCResult) {
+  if (SemaCCResult.Availability == CXAvailability_NotAvailable ||
+      SemaCCResult.Availability == CXAvailability_NotAccessible)
+    Forbidden = true;
+}
+
+float SymbolRelevanceSignals::evaluate() const {
+  if (Forbidden)
+    return 0;
+  return NameMatch;
+}
+raw_ostream &operator<<(raw_ostream &OS, const SymbolRelevanceSignals &S) {
+  OS << formatv("=== Symbol relevance: {0}\n", S.evaluate());
+  OS << formatv("\tName match: {0}\n", S.NameMatch);
+  OS << formatv("\tForbidden: {0}\n", S.Forbidden);
+  return OS;
+}
+
+float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {
+  return SymbolQuality * SymbolRelevance;
+}
+
+// Produces an integer that sorts in the same order as F.
+// That is: a < b <==> encodeFloat(a) < encodeFloat(b).
+static uint32_t encodeFloat(float F) {
+  static_assert(std::numeric_limits<float>::is_iec559, "");
+  constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);
+
+  // Get the bits of the float. Endianness is the same as for integers.
+  uint32_t U = FloatToBits(F);
+  // IEEE 754 floats compare like sign-magnitude integers.
+  if (U & TopBit)    // Negative float.
+    return 0 - U;    // Map onto the low half of integers, order reversed.
+  return U + TopBit; // Positive floats map onto the high half of integers.
+}
+
+std::string sortText(float Score, llvm::StringRef Name) {
+  // We convert -Score to an integer, and hex-encode for readability.
+  // Example: [0.5, "foo"] -> "41000000foo"
+  std::string S;
+  llvm::raw_string_ostream OS(S);
+  write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
+            /*Width=*/2 * sizeof(Score));
+  OS << Name;
+  OS.flush();
+  return S;
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   DraftStoreTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
+  QualityTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp
   TestFS.cpp
+  TestTU.cpp
   ThreadingTests.cpp
   TraceTests.cpp
   TUSchedulerTests.cpp
   URITests.cpp
   XRefsTests.cpp
   )
 
 target_link_libraries(ClangdTests

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

 //===-- ClangdUnitTests.cpp - ClangdUnit tests ------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Annotations.h"
 #include "ClangdUnit.h"
 #include "SourceCode.h"
-#include "TestFS.h"
-#include "clang/Frontend/CompilerInvocation.h"
-#include "clang/Frontend/PCHContainerOperations.h"
-#include "clang/Frontend/Utils.h"
+#include "TestTU.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 namespace {
 using testing::ElementsAre;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Pair;
 
 testing::Matcher<const Diag &> WithFix(testing::Matcher<Fix> FixMatcher) {
   return Field(&Diag::Fixes, ElementsAre(FixMatcher));
 }
 
 testing::Matcher<const Diag &> WithNote(testing::Matcher<Note> NoteMatcher) {
   return Field(&Diag::Notes, ElementsAre(NoteMatcher));
 }
 
-// FIXME: this is duplicated with FileIndexTests. Share it.
-ParsedAST build(StringRef Code, std::vector<const char *> Flags = {}) {
-  std::vector<const char *> Cmd = {"clang", "main.cpp"};
-  Cmd.insert(Cmd.begin() + 1, Flags.begin(), Flags.end());
-  auto CI = createInvocationFromCommandLine(Cmd);
-  auto Buf = MemoryBuffer::getMemBuffer(Code);
-  auto AST = ParsedAST::Build(std::move(CI), nullptr, std::move(Buf),
-                              std::make_shared<PCHContainerOperations>(),
-                              vfs::getRealFileSystem());
-  assert(AST.hasValue());
-  return std::move(*AST);
-}
-
-std::vector<Diag> buildDiags(llvm::StringRef Code,
-                             std::vector<const char *> Flags = {}) {
-  return build(Code, std::move(Flags)).getDiagnostics();
-}
-
 MATCHER_P2(Diag, Range, Message,
            "Diag at " + llvm::to_string(Range) + " = [" + Message + "]") {
   return arg.Range == Range && arg.Message == Message;
 }
 
 MATCHER_P3(Fix, Range, Replacement, Message,
            "Fix " + llvm::to_string(Range) + " => " +
                testing::PrintToString(Replacement) + " = [" + Message + "]") {
Annotations Test(R"cpp(
     int main() {
       $typo[[go\
 o]]();
       foo()$semicolon[[]]
       $unk[[unknown]]();
     }
   )cpp");
   EXPECT_THAT(
-      buildDiags(Test.code()),
+      TestTU::withCode(Test.code()).build().getDiagnostics(),
       ElementsAre(
           // This range spans lines.
           AllOf(Diag(Test.range("typo"),
                      "use of undeclared identifier 'goo'; did you mean 'foo'?"),
                 WithFix(
                     Fix(Test.range("typo"), "foo", "change 'go\\ o' to 'foo'")),
                 // This is a pretty normal range.
                 WithNote(Diag(Test.range("decl"), "'foo' declared here"))),
           // This range is zero-width, and at the end of a line.
           AllOf(Diag(Test.range("semicolon"), "expected ';' after expression"),
                 WithFix(Fix(Test.range("semicolon"), ";", "insert ';'"))),
           // This range isn't provided by clang, we expand to the token.
           Diag(Test.range("unk"), "use of undeclared identifier 'unknown'")));
 }
 
 TEST(DiagnosticsTest, FlagsMatter) {
   Annotations Test("[[void]] main() {}");
-  EXPECT_THAT(buildDiags(Test.code()),
+  auto TU = TestTU::withCode(Test.code());
+  EXPECT_THAT(TU.build().getDiagnostics(),
               ElementsAre(AllOf(Diag(Test.range(), "'main' must return 'int'"),
                                 WithFix(Fix(Test.range(), "int",
                                             "change 'void' to 'int'")))));
   // Same code built as C gets different diagnostics.
+  TU.Filename = "Plain.c";
   EXPECT_THAT(
-      buildDiags(Test.code(), {"-x", "c"}),
+      TU.build().getDiagnostics(),
       ElementsAre(AllOf(
           Diag(Test.range(), "return type of 'main' is not 'int'"),
           WithFix(Fix(Test.range(), "int", "change return type to 'int'")))));
 }
 
 TEST(DiagnosticsTest, Preprocessor) {
   // This looks like a preamble, but there's an #else in the middle!
   // Check that:
   //  - the #else doesn't generate diagnostics (we had this bug)
   //  - we get diagnostics from the taken branch
   //  - we get no diagnostics from the not taken branch
   Annotations Test(R"cpp(
     #ifndef FOO
     #define FOO
       int a = [[b]];
     #else
       int x = y;
     #endif
     )cpp");
   EXPECT_THAT(
-      buildDiags(Test.code()),
+      TestTU::withCode(Test.code()).build().getDiagnostics(),
       ElementsAre(Diag(Test.range(), "use of undeclared identifier 'b'")));
 }
 
 TEST(DiagnosticsTest, ToLSP) {
   clangd::Diag D;
   D.Message = "something terrible happened";
   D.Range = {pos(1, 2), pos(3, 4)};
   D.InsideMainFile = true;
for (const char *Text : {
            "int ^foo();",  // beginning of identifier
            "int ^foo^();", // end of identifier
            "int foo(^);",  // non-identifier
            "^int foo();",  // beginning of file (can't back up)
            "int ^f0^0();", // after a digit (lexing at N-1 is wrong)
            "int ^λλ^λ();", // UTF-8 handled properly when backing up
        }) {
     Annotations TestCase(Text);
-    auto AST = build(TestCase.code());
+    auto AST = TestTU::withCode(TestCase.code()).build();
     const auto &SourceMgr = AST.getASTContext().getSourceManager();
     SourceLocation Actual = getBeginningOfIdentifier(
         AST, TestCase.points().back(), SourceMgr.getMainFileID());
     Position ActualPos =
         offsetToPosition(TestCase.code(), SourceMgr.getFileOffset(Actual));
     EXPECT_EQ(TestCase.points().front(), ActualPos) << Text;
   }
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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 "TestFS.h"
+#include "TestTU.h"
 #include "index/FileIndex.h"
-#include "clang/Frontend/CompilerInvocation.h"
-#include "clang/Frontend/PCHContainerOperations.h"
-#include "clang/Frontend/Utils.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   I.fuzzyFind(Req, [&](const Symbol &Sym) {
     Matches.push_back((Sym.Scope + Sym.Name).str());
   });
   return Matches;
 }
 
-/// Create an ParsedAST for \p Code. Returns None if \p Code is empty.
-/// \p Code is put into <Path>.h which is included by \p <BasePath>.cpp.
-llvm::Optional<ParsedAST> build(llvm::StringRef BasePath,
-                                llvm::StringRef Code) {
-  if (Code.empty())
-    return llvm::None;
-
-  assert(llvm::sys::path::extension(BasePath).empty() &&
-         "BasePath must be a base file path without extension.");
-  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
-      new vfs::InMemoryFileSystem);
-  std::string Path = testPath((BasePath + ".cpp").str());
-  std::string Header = testPath((BasePath + ".h").str());
-  VFS->addFile(Path, 0, llvm::MemoryBuffer::getMemBuffer(""));
-  VFS->addFile(Header, 0, llvm::MemoryBuffer::getMemBuffer(Code));
-  const char *Args[] = {"clang", "-xc++", "-include", Header.c_str(),
-                        Path.c_str()};
-
-  auto CI = createInvocationFromCommandLine(Args);
-
-  auto Buf = llvm::MemoryBuffer::getMemBuffer(Code);
-  auto AST = ParsedAST::Build(std::move(CI), nullptr, std::move(Buf),
-                              std::make_shared<PCHContainerOperations>(), VFS);
-  assert(AST.hasValue());
-  return std::move(*AST);
+// Adds Basename.cpp, which includes Basename.h, which contains Code.
+void update(FileIndex &M, llvm::StringRef Basename, llvm::StringRef Code) {
+  TestTU File;
+  File.Filename = (Basename + ".cpp").str();
+  File.HeaderFilename = (Basename + ".h").str();
+  File.HeaderCode = Code;
+  auto AST = File.build();
+  M.update(File.Filename, &AST);
 }
 
 TEST(FileIndexTest, IndexAST) {
   FileIndex M;
-  M.update(
-      "f1",
-      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
+  update(M, "f1", "namespace ns { void f() {} class X {}; }");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
 }
 
 TEST(FileIndexTest, NoLocal) {
   FileIndex M;
-  M.update(
-      "f1",
-      build("f1", "namespace ns { void f() { int local = 0; } class X {}; }")
-          .getPointer());
+  update(M, "f1", "namespace ns { void f() { int local = 0; } class X {}; }");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns", "ns::f", "ns::X"));
 }
 
 TEST(FileIndexTest, IndexMultiASTAndDeduplicate) {
   FileIndex M;
-  M.update(
-      "f1",
-      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
-  M.update(
-      "f2",
-      build("f2", "namespace ns { void ff() {} class X {}; }").getPointer());
+  update(M, "f1", "namespace ns { void f() {} class X {}; }");
+  update(M, "f2", "namespace ns { void ff() {} class X {}; }");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X", "ns::ff"));
 }
 
 TEST(FileIndexTest, RemoveAST) {
   FileIndex M;
-  M.update(
-      "f1",
-      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
+  update(M, "f1", "namespace ns { void f() {} class X {}; }");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
 
-  M.update("f1", nullptr);
+  M.update("f1.cpp", nullptr);
   EXPECT_THAT(match(M, Req), UnorderedElementsAre());
 }
 
 TEST(FileIndexTest, RemoveNonExisting) {
   FileIndex M;
-  M.update("no", nullptr);
+  M.update("no.cpp", nullptr);
   EXPECT_THAT(match(M, FuzzyFindRequest()), UnorderedElementsAre());
 }
 
 TEST(FileIndexTest, IgnoreClassMembers) {
   FileIndex M;
-  M.update("f1",
-           build("f1", "class X { static int m1; int m2; static void f(); };")
-               .getPointer());
+  update(M, "f1", "class X { static int m1; int m2; static void f(); };");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("X"));
 }
 
 TEST(FileIndexTest, NoIncludeCollected) {
   FileIndex M;
-  M.update("f", build("f", "class string {};").getPointer());
+  update(M, "f", "class string {};");
 
   FuzzyFindRequest Req;
   Req.Query = "";
   bool SeenSymbol = false;
   M.fuzzyFind(Req, [&](const Symbol &Sym) {
     EXPECT_TRUE(Sym.Detail->IncludeHeader.empty());
     SeenSymbol = true;
   });
   EXPECT_TRUE(SeenSymbol);
 }
 
 TEST(FileIndexTest, TemplateParamsInLabel) {
   auto Source = R"cpp(
 template <class Ty>
 class vector {
 };
 
 template <class Ty, class Arg>
 vector<Ty> make_vector(Arg A) {}
 )cpp";
 
   FileIndex M;
-  M.update("f", build("f", Source).getPointer());
+  update(M, "f", Source);
 
   FuzzyFindRequest Req;
   Req.Query = "";
   bool SeenVector = false;
   bool SeenMakeVector = false;
   M.fuzzyFind(Req, [&](const Symbol &Sym) {
     if (Sym.Name == "vector") {
       EXPECT_EQ(Sym.CompletionLabel, "vector<class Ty>");

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

+//===-- SourceCodeTests.cpp  ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Evaluating scoring functions isn't a great fit for assert-based tests.
+// For interesting cases, both exact scores and "X beats Y" are too brittle to
+// make good hard assertions.
+//
+// Here we test the signal extraction and sanity-check that signals point in
+// the right direction. This should be supplemented by quality metrics which
+// we can compute from a corpus of queries and preferred rankings.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Quality.h"
+#include "TestTU.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+TEST(QualityTests, SymbolQualitySignalExtraction) {
+  auto Header = TestTU::withHeaderCode(R"cpp(
+    int x;
+
+    [[deprecated]]
+    int f() { return x; }
+  )cpp");
+  auto Symbols = Header.headerSymbols();
+  auto AST = Header.build();
+
+  SymbolQualitySignals Quality;
+  Quality.merge(findSymbol(Symbols, "x"));
+  EXPECT_FALSE(Quality.Deprecated);
+  EXPECT_EQ(Quality.SemaCCPriority, SymbolQualitySignals().SemaCCPriority);
+  EXPECT_EQ(Quality.References, SymbolQualitySignals().References);
+
+  Symbol F = findSymbol(Symbols, "f");
+  F.References = 24; // TestTU doesn't count references, so fake it.
+  Quality = {};
+  Quality.merge(F);
+  EXPECT_FALSE(Quality.Deprecated); // FIXME: Include deprecated bit in index.
+  EXPECT_EQ(Quality.SemaCCPriority, SymbolQualitySignals().SemaCCPriority);
+  EXPECT_EQ(Quality.References, 24u);
+
+  Quality = {};
+  Quality.merge(CodeCompletionResult(&findDecl(AST, "f"), /*Priority=*/42));
+  EXPECT_TRUE(Quality.Deprecated);
+  EXPECT_EQ(Quality.SemaCCPriority, 42u);
+  EXPECT_EQ(Quality.References, SymbolQualitySignals().References);
+}
+
+TEST(QualityTests, SymbolRelevanceSignalExtraction) {
+  auto AST = TestTU::withHeaderCode(R"cpp(
+    [[deprecated]]
+    int f() { return 0; }
+  )cpp")
+                 .build();
+
+  SymbolRelevanceSignals Relevance;
+  Relevance.merge(CodeCompletionResult(&findDecl(AST, "f"), /*Priority=*/42,
+                                       nullptr, false, /*Accessible=*/false));
+  EXPECT_EQ(Relevance.NameMatch, SymbolRelevanceSignals().NameMatch);
+  EXPECT_TRUE(Relevance.Forbidden);
+}
+
+// Do the signals move the scores in the direction we expect?
+TEST(QualityTests, SymbolQualitySignalsSanity) {
+  SymbolQualitySignals Default;
+  EXPECT_EQ(Default.evaluate(), 1);
+
+  SymbolQualitySignals Deprecated;
+  Deprecated.Deprecated = true;
+  EXPECT_LT(Deprecated.evaluate(), Default.evaluate());
+
+  SymbolQualitySignals WithReferences, ManyReferences;
+  WithReferences.References = 10;
+  ManyReferences.References = 1000;
+  EXPECT_GT(WithReferences.evaluate(), Default.evaluate());
+  EXPECT_GT(ManyReferences.evaluate(), WithReferences.evaluate());
+
+  SymbolQualitySignals LowPriority, HighPriority;
+  LowPriority.SemaCCPriority = 60;
+  HighPriority.SemaCCPriority = 20;
+  EXPECT_GT(HighPriority.evaluate(), Default.evaluate());
+  EXPECT_LT(LowPriority.evaluate(), Default.evaluate());
+}
+
+TEST(QualityTests, SymbolRelevanceSignalsSanity) {
+  SymbolRelevanceSignals Default;
+  EXPECT_EQ(Default.evaluate(), 1);
+
+  SymbolRelevanceSignals Forbidden;
+  Forbidden.Forbidden = true;
+  EXPECT_LT(Forbidden.evaluate(), Default.evaluate());
+
+  SymbolRelevanceSignals PoorNameMatch;
+  PoorNameMatch.NameMatch = 0.2;
+  EXPECT_LT(PoorNameMatch.evaluate(), Default.evaluate());
+}
+
+TEST(QualityTests, SortText) {
+  EXPECT_LT(sortText(std::numeric_limits<float>::infinity()), sortText(1000.2));
+  EXPECT_LT(sortText(1000.2), sortText(1));
+  EXPECT_LT(sortText(1), sortText(0.3));
+  EXPECT_LT(sortText(0.3), sortText(0));
+  EXPECT_LT(sortText(0), sortText(-10));
+  EXPECT_LT(sortText(-10), sortText(-std::numeric_limits<float>::infinity()));
+
+  EXPECT_LT(sortText(1, "z"), sortText(0, "a"));
+  EXPECT_LT(sortText(0, "a"), sortText(0, "z"));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

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

 using namespace llvm;
 
 IntrusiveRefCntPtr<vfs::FileSystem>
 buildTestFS(StringMap<std::string> const &Files) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> MemFS(
       new vfs::InMemoryFileSystem);
   for (auto &FileAndContents : Files) {
     MemFS->addFile(FileAndContents.first(), time_t(),
-                   MemoryBuffer::getMemBuffer(FileAndContents.second,
+                   MemoryBuffer::getMemBufferCopy(FileAndContents.second,
                                                   FileAndContents.first()));
   }
   return MemFS;
 }
 
 MockCompilationDatabase::MockCompilationDatabase(bool UseRelPaths)
     : ExtraClangFlags({"-ffreestanding"}), UseRelPaths(UseRelPaths) {
   // -ffreestanding avoids implicit stdc-predef.h.
 }

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

+//===--- TestTU.h - Scratch source files for testing ------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+//
+// Many tests for indexing, code completion etc are most naturally expressed
+// using code examples.
+// TestTU lets test define these examples in a common way without dealing with
+// the mechanics of VFS and compiler interactions, and then easily grab the
+// AST, particular symbols, etc.
+//
+//===---------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_TESTTU_H
+#define LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_TESTTU_H
+#include "ClangdUnit.h"
+#include "index/Index.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+
+struct TestTU {
+  static TestTU withCode(llvm::StringRef Code) {
+    TestTU TU;
+    TU.Code = Code;
+    return TU;
+  }
+
+  static TestTU withHeaderCode(llvm::StringRef HeaderCode) {
+    TestTU TU;
+    TU.HeaderCode = HeaderCode;
+    return TU;
+  }
+
+  // The code to be compiled.
+  std::string Code;
+  std::string Filename = "TestTU.cpp";
+
+  // Define contents of a header to be included by TestTU.cpp.
+  std::string HeaderCode;
+  std::string HeaderFilename = "TestTU.h";
+
+  ParsedAST build() const;
+  SymbolSlab headerSymbols() const;
+  std::unique_ptr<SymbolIndex> index() const;
+};
+
+// Look up an index symbol by qualified name, which must be unique.
+const Symbol &findSymbol(const SymbolSlab &, llvm::StringRef QName);
+// Look up an AST symbol by qualified name, which must be unique and top-level.
+const NamedDecl &findDecl(ParsedAST &AST, llvm::StringRef QName);
+
+} // namespace clangd
+} // namespace clang
+#endif

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

+//===--- TestTU.cpp - Scratch source files for testing ------------*-
+//C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+#include "TestTU.h"
+#include "TestFS.h"
+#include "index/FileIndex.h"
+#include "index/MemIndex.h"
+#include "clang/Frontend/CompilerInvocation.h"
+#include "clang/Frontend/PCHContainerOperations.h"
+#include "clang/Frontend/Utils.h"
+
+namespace clang {
+namespace clangd {
+using namespace llvm;
+
+ParsedAST TestTU::build() const {
+  std::string FullFilename = testPath(Filename),
+              FullHeaderName = testPath(HeaderFilename);
+  std::vector<const char *> Cmd = {"clang", FullFilename.c_str()};
+  // FIXME: this shouldn't need to be conditional, but it breaks a
+  // GoToDefinition test for some reason (getMacroArgExpandedLocation fails).
+  if (!HeaderCode.empty()) {
+    Cmd.push_back("-include");
+    Cmd.push_back(FullHeaderName.c_str());
+  }
+  auto AST = ParsedAST::Build(
+      createInvocationFromCommandLine(Cmd), nullptr,
+      MemoryBuffer::getMemBufferCopy(Code),
+      std::make_shared<PCHContainerOperations>(),
+      buildTestFS({{FullFilename, Code}, {FullHeaderName, HeaderCode}}));
+  if (!AST.hasValue()) {
+    ADD_FAILURE() << "Failed to build code:\n" << Code;
+    llvm_unreachable("Failed to build TestTU!");
+  }
+  return std::move(*AST);
+}
+
+SymbolSlab TestTU::headerSymbols() const {
+  auto AST = build();
+  return indexAST(&AST);
+}
+
+std::unique_ptr<SymbolIndex> TestTU::index() const {
+  return MemIndex::build(headerSymbols());
+}
+
+// Look up a symbol by qualified name, which must be unique.
+const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) {
+  const Symbol *Result = nullptr;
+  for (const Symbol &S : Slab) {
+    if (QName != (S.Scope + S.Name).str())
+      continue;
+    if (Result) {
+      ADD_FAILURE() << "Multiple symbols named " << QName << ":\n"
+                    << *Result << "\n---\n"
+                    << S;
+      assert(false && "QName is not unique");
+    }
+    Result = &S;
+  }
+  if (!Result) {
+    ADD_FAILURE() << "No symbol named " << QName << " in "
+                  << ::testing::PrintToString(Slab);
+    assert(false && "No symbol with QName");
+  }
+  return *Result;
+}
+
+const NamedDecl &findDecl(ParsedAST &AST, llvm::StringRef QName) {
+  const NamedDecl *Result = nullptr;
+  for (const Decl *D : AST.getTopLevelDecls()) {
+    auto *ND = dyn_cast<NamedDecl>(D);
+    if (!ND || ND->getNameAsString() != QName)
+      continue;
+    if (Result) {
+      ADD_FAILURE() << "Multiple Decls named " << QName;
+      assert(false && "QName is not unique");
+    }
+    Result = ND;
+  }
+  if (!Result) {
+    ADD_FAILURE() << "No Decl named " << QName << " in AST";
+    assert(false && "No Decl with QName");
+  }
+  return *Result;
+}
+
+} // namespace clangd
+} // namespace clang

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

 //===-- XRefsTests.cpp  ---------------------------*- C++ -*--------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "Annotations.h"
 #include "ClangdUnit.h"
 #include "Compiler.h"
 #include "Matchers.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
+#include "TestTU.h"
 #include "XRefs.h"
-#include "gmock/gmock.h"
 #include "index/FileIndex.h"
 #include "index/SymbolCollector.h"
-#include "clang/Frontend/CompilerInvocation.h"
-#include "clang/Frontend/PCHContainerOperations.h"
-#include "clang/Frontend/Utils.h"
 #include "clang/Index/IndexingAction.h"
 #include "llvm/Support/Path.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 namespace {
 using testing::ElementsAre;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Matcher;
 using testing::UnorderedElementsAreArray;
 
 class IgnoreDiagnostics : public DiagnosticsConsumer {
   void onDiagnosticsReady(PathRef File,
                           std::vector<Diag> Diagnostics) override {}
 };
 
-// FIXME: this is duplicated with FileIndexTests. Share it.
-ParsedAST build(StringRef MainCode, StringRef HeaderCode = "") {
-  auto HeaderPath = testPath("foo.h");
-  auto MainPath = testPath("foo.cpp");
-  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
-      new vfs::InMemoryFileSystem());
-  VFS->addFile(MainPath, 0, llvm::MemoryBuffer::getMemBuffer(MainCode));
-  VFS->addFile(HeaderPath, 0, llvm::MemoryBuffer::getMemBuffer(HeaderCode));
-  std::vector<const char *> Cmd = {"clang", "-xc++", MainPath.c_str()};
-  if (!HeaderCode.empty()) {
-    std::vector<const char *> args = {"-include", HeaderPath.c_str()};
-    Cmd.insert(Cmd.begin() + 1, args.begin(), args.end());
-  }
-  auto CI = createInvocationFromCommandLine(Cmd);
-
-  auto Buf = MemoryBuffer::getMemBuffer(MainCode);
-  auto AST = ParsedAST::Build(std::move(CI), nullptr, std::move(Buf),
-                              std::make_shared<PCHContainerOperations>(), VFS);
-  assert(AST.hasValue());
-  return std::move(*AST);
-}
-
-std::unique_ptr<SymbolIndex> buildIndex(StringRef MainCode,
-                                        StringRef HeaderCode) {
-  auto AST = build(MainCode, HeaderCode);
-  return MemIndex::build(indexAST(&AST));
-}
-
 // Extracts ranges from an annotated example, and constructs a matcher for a
 // highlight set. Ranges should be named $read/$write as appropriate.
 Matcher<const std::vector<DocumentHighlight> &>
 HighlightsFrom(const Annotations &Test) {
   std::vector<DocumentHighlight> Expected;
   auto Add = [&](const Range &R, DocumentHighlightKind K) {
     Expected.emplace_back();
     Expected.back().range = R;
const char *Tests[] = {
         int main() {
           [[foo]]([[foo]](42));
           auto *X = &[[foo]];
         }
       )cpp",
   };
   for (const char *Test : Tests) {
     Annotations T(Test);
-    auto AST = build(T.code());
+    auto AST = TestTU::withCode(T.code()).build();
     EXPECT_THAT(findDocumentHighlights(AST, T.point()), HighlightsFrom(T))
         << Test;
   }
 }
 
 MATCHER_P(RangeIs, R, "") { return arg.range == R; }
 
 TEST(GoToDefinition, WithIndex) {
   Annotations SymbolHeader(R"cpp(
         class $forward[[Forward]];
         class $foo[[Foo]] {};
 
         void $f1[[f1]]();
 
         inline void $f2[[f2]]() {}
       )cpp");
   Annotations SymbolCpp(R"cpp(
       class $forward[[forward]] {};
       void  $f1[[f1]]() {}
     )cpp");
 
-  auto Index = buildIndex(SymbolCpp.code(), SymbolHeader.code());
+  TestTU TU;
+  TU.Code = SymbolCpp.code();
+  TU.HeaderCode = SymbolHeader.code();
+  auto Index = TU.index();
   auto runFindDefinitionsWithIndex = [&Index](const Annotations &Main) {
-    auto AST = build(/*MainCode=*/Main.code(),
-                     /*HeaderCode=*/"");
+    auto AST = TestTU::withCode(Main.code()).build();
     return clangd::findDefinitions(AST, Main.point(), Index.get());
   };
 
   Annotations Test(R"cpp(// only declaration in AST.
         void [[f1]]();
         int main() {
           ^f1();
         }
const char *Tests[] = {
       R"cpp(
          #define FF() class [[Test]] {};
          FF();
          void f() { T^est a; }
       )cpp",
   };
   for (const char *Test : Tests) {
     Annotations T(Test);
-    auto AST = build(T.code());
+    auto AST = TestTU::withCode(T.code()).build();
     std::vector<Matcher<Location>> ExpectedLocations;
     for (const auto &R : T.ranges())
       ExpectedLocations.push_back(RangeIs(R));
     EXPECT_THAT(findDefinitions(AST, T.point()),
                 ElementsAreArray(ExpectedLocations))
         << Test;
   }
 }
OneTest Tests[] = {
             void g() { struct outer o; o.v.d^ef++; }
           )cpp",
           "Declared in union outer::(anonymous)\n\nint def",
       },
   };
 
   for (const OneTest &Test : Tests) {
     Annotations T(Test.Input);
-    auto AST = build(T.code());
+    auto AST = TestTU::withCode(T.code()).build();
     Hover H = getHover(AST, T.point());
 
     EXPECT_EQ(H.contents.value, Test.ExpectedHover) << Test.Input;
   }
 }
 
 TEST(GoToInclude, All) {
   MockFSProvider FS;