Index: clangd/CMakeLists.txt
===================================================================
--- clangd/CMakeLists.txt
+++ clangd/CMakeLists.txt
@@ -19,6 +19,7 @@
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
+  ExpectedTypes.cpp
   FindSymbols.cpp
   FileDistance.cpp
   FuzzyMatch.cpp
Index: clangd/ExpectedTypes.h
===================================================================
--- /dev/null
+++ clangd/ExpectedTypes.h
@@ -0,0 +1,221 @@
+//===--- ExpectedTypes.h - Simplified C++ types -----------------*- C++-*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// A simplified model of C++ conversions that can be used to check whether types
+// are converible between each other. Used for code completion ranking.
+//
+// When using clang APIs, we cannot determine if a type coming from an AST is
+// convertible to another type without looking at both types in the same AST.
+// This is exactly what we need for index-based completions. Instead of the
+// AST-based approach, we choose to enumerate all 'unfinished' conversions that
+// the compiler can perform for a particular type. We do this in two directions:
+//   1. When looking at a conversion source (e.g. a completion result), we
+//      determine the set of types that could be results of direct conversions.
+//      E.g. if the completion result is 'foo' from the following code:
+//          struct Cls {
+//            operator int();
+//          };
+//          Cls foo;
+//      then the types for 'foo' are 'Cls' and 'int'.
+//   2. When looking at a target type for conversion (e.g. a preferred type in a
+//      code completion), we determine the set of types that could be converted
+//      to our target type, i.e. we attempt to enumerate conversions in a
+//      reverse direction.
+//      E.g. if we are completing a :
+//          struct Cls {
+//              Cls(int a);
+//          };
+//          Cls bar = ^; // <-- complete at '^'
+//     then the expected types in this context are 'Cls' and 'int'.
+// When the resulting sets from (1) and (2) intersect, the types are considered
+// to be convertible.
+// The actual implementation is a bit more complicated to handle various C++
+// percularities, e.g. reference binding, user-defined conversions, etc.
+// See the interface and documentation of SType for more details.
+// Known limitations:
+//   - no support for dependent types (template, SFINAE tricks, etc.),
+//   - does not attempt to determine ambiguous conversions,
+//   - integral conversion are highly simplified,
+//   - does not have any special handling for common idioms, e.g.
+//     unique_ptr<Derived> -> unique_ptr<Base>
+//   - no special support for C and ObjC, only C++ is considered.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_EXPECTED_TYPES_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_EXPECTED_TYPES_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include <array>
+#include <cstring>
+#include <set>
+
+namespace clang {
+class CodeCompletionResult;
+
+namespace clangd {
+/// FIXME(ibiryukov): this helpers should live somewhere else.
+using SHA1Array = std::array<uint8_t, 20>;
+SHA1Array computeSHA1(llvm::StringRef Input);
+
+/// Represents a type of partially applied conversion. Should be treated as an
+/// opaque value and can only be used to check whether the types are converible
+/// between each other (by using the equality operator).
+/// Representation is fixed-size, small and cheap to copy.
+class SType {
+public:
+  SType() = default;
+
+  /// Compute the types of the completion result. Apart from the completion type
+  /// itself, may also contain some extra types that model user-defined and
+  /// builtin conversions.
+  /// Since this information is supposed to be stored in the index, the
+  /// implementation attempts to store as little types as possible.
+  static llvm::SmallVector<SType, 2>
+  fromCompletionResult(ASTContext &Ctx, const CodeCompletionResult &R);
+
+  /// Compute a set of types that should be matched for copy initialization.
+  /// Examples of copy initialization are:
+  ///   1. Type a = ^ // explicit copy-init syntax.
+  ///   2. foo(^)     // converting to a function parameter type.
+  /// Since this information should only be computed once per code completion,
+  /// the number of types can typically be large (up to dozens).
+  ///
+  /// The result is a map from a type to a multiplier (>= 1) that denotes the
+  /// quality of conversion that had to be applied (better conversion receive
+  /// higher multipliers).
+  static llvm::DenseMap<SType, float> forCopyInitOf(ASTContext &Ctx,
+                                                    QualType Target);
+  // FIXME(ibiryukov): support other cases when completion exposes those, e.g.
+  //                   direct-init, static_cast, etc.
+
+  static SType fromHexStr(llvm::StringRef Str);
+  std::string toHexStr() const;
+
+  friend bool operator==(const SType &L, const SType &R) {
+    return L.Data == R.Data;
+  }
+  friend bool operator!=(const SType &L, const SType &R) { return !(L == R); }
+  friend unsigned hash_value(const SType &T) {
+    // FIXME(ibiryukov): share this code with SymbolID.
+    // We already have a good hash, just return the first bytes.
+    assert(sizeof(size_t) <= 20 && "size_t longer than SHA1!");
+    size_t Result;
+    memcpy(&Result, T.Data.begin(), sizeof(size_t));
+    return llvm::hash_code(Result);
+  }
+
+private:
+  friend llvm::DenseMapInfo<SType>;
+
+  explicit SType(SHA1Array Data);
+  SHA1Array Data;
+};
+
+/// Checks whether expected types match. The interface is not symmetrical on
+/// purpose:
+///    - first parameter should be obtained from the context that knows the
+///      type we want to match, e.g. from preferred type in code completion
+///      using SType::forCopyInitOf.
+///    - second parameter should be obtained from the items we are trying to
+///      match, e.g. from a completion result using SType::fromCompletionResult.
+/// Returns the multiplier to be used for upranking matched results (>= 1).
+llvm::Optional<float> typesMatch(const llvm::DenseMap<SType, float> &Expected,
+                                 llvm::ArrayRef<SType> Actual);
+
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+// Support STypes as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::SType> {
+  static inline clang::clangd::SType getEmptyKey() {
+    static clang::clangd::SType Key =
+        clang::clangd::SType(clang::clangd::computeSHA1("EMPTY_KEY"));
+    return Key;
+  }
+  static inline clang::clangd::SType getTombstoneKey() {
+    static clang::clangd::SType Key =
+        clang::clangd::SType(clang::clangd::computeSHA1("EMPTY_KEY"));
+    return Key;
+  }
+  static unsigned getHashValue(const clang::clangd::SType &Sym) {
+    return hash_value(Sym);
+  }
+  static bool isEqual(const clang::clangd::SType &LHS,
+                      const clang::clangd::SType &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+namespace clang {
+namespace clangd {
+// Private API, please do not use. Exposed only for tests.
+namespace detail {
+/// Indicates if expression is an l-value or an r-value.
+enum class ValueCategory {
+  LVal,
+  RVal,
+};
+/// Models an expression of a particular type and value category.
+class MockExpr {
+public:
+  static llvm::Optional<MockExpr> forCompletion(const CodeCompletionResult &R);
+  static llvm::Optional<MockExpr> forFunctionReturn(QualType Ret);
+
+  QualType getType() const { return Type; }
+  ValueCategory getValueCat() const { return Cat; }
+
+private:
+  MockExpr(ValueCategory Cat, QualType Type)
+      : Cat(Cat), Type(Type.getCanonicalType()) {
+    assert(!Type.isNull());
+    assert(!Type->isReferenceType() &&
+           "expressions do not have reference types");
+  }
+
+  ValueCategory Cat;
+  QualType Type;
+};
+
+/// Contains enough data to build SType.
+struct PartialConv {
+  PartialConv(QualType Type, ValueCategory Cat, bool AfterUserConv = false)
+      : Type(Type.getCanonicalType()), Cat(Cat), AfterUserConv(AfterUserConv) {
+    assert(!Type.isNull());
+    assert(!Type->isReferenceType());
+  }
+  QualType Type;
+  ValueCategory Cat;
+  /// Indicates if the user-defined conversion was applied.
+  bool AfterUserConv;
+};
+inline bool operator==(PartialConv L, PartialConv R) {
+  return std::tie(L.Type, L.Cat, L.AfterUserConv) ==
+         std::tie(R.Type, R.Cat, R.AfterUserConv);
+}
+inline bool operator!=(PartialConv L, PartialConv R) { return !(L == R); }
+inline bool operator<(PartialConv L, PartialConv R) {
+  void *LT = L.Type.getAsOpaquePtr();
+  void *RT = R.Type.getAsOpaquePtr();
+  return std::tie(LT, L.Cat, L.AfterUserConv) <
+         std::tie(RT, R.Cat, R.AfterUserConv);
+}
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const PartialConv &C);
+
+void collectConvertibleFrom(ASTContext &Ctx, MockExpr Source,
+                            llvm::function_ref<void(PartialConv)> OutF);
+void collectConvertibleTo(ASTContext &Ctx, QualType Target,
+                          llvm::function_ref<void(PartialConv)> OutF);
+} // namespace detail
+} // namespace clangd
+} // namespace clang
+
+#endif
\ No newline at end of file
Index: clangd/ExpectedTypes.cpp
===================================================================
--- /dev/null
+++ clangd/ExpectedTypes.cpp
@@ -0,0 +1,502 @@
+#include "ExpectedTypes.h"
+#include "Logger.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Type.h"
+#include "clang/Index/USRGeneration.h"
+#include "clang/Sema/CodeCompleteConsumer.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/SHA1.h"
+#include <algorithm>
+
+namespace clang {
+namespace clangd {
+
+using detail::MockExpr;
+using detail::PartialConv;
+using detail::ValueCategory;
+
+namespace {
+
+template <class Func> void chain(PartialConv Input, Func F) { F(Input); }
+
+template <class Func, class... Rest>
+void chain(PartialConv Input, Func F, Rest... Fs) {
+  F(Input, [Fs...](PartialConv C) { return chain(C, Fs...); });
+}
+
+void forEachBase(CXXRecordDecl *Record,
+                 llvm::function_ref<void(CXXRecordDecl *)> OnBase) {
+  class DFS {
+  public:
+    DFS(CXXRecordDecl *Root, llvm::function_ref<void(CXXRecordDecl *)> OnBase)
+        : OnBase(OnBase) {
+      Seen.insert(Root);
+      visit(Root);
+    }
+
+  private:
+    void visit(CXXRecordDecl *Record) {
+      if (!Record->isCompleteDefinition())
+        return;
+      for (const CXXBaseSpecifier &Base : Record->bases()) {
+        if (Base.getType().isNull() || Base.getAccessSpecifier() != AS_public)
+          continue;
+        auto *BaseRecord = Base.getType()->getAsCXXRecordDecl();
+        if (!BaseRecord || !Seen.insert(BaseRecord).second)
+          continue;
+        OnBase(BaseRecord);
+        visit(BaseRecord);
+      }
+    }
+
+  private:
+    llvm::SmallPtrSet<CXXRecordDecl *, 8> Seen;
+    llvm::function_ref<void(CXXRecordDecl *)> OnBase;
+  };
+
+  DFS(Record, OnBase);
+}
+
+struct Dedup {
+  Dedup(llvm::function_ref<void(PartialConv)> OutF) : OutF(OutF) {}
+
+  void operator()(PartialConv C) {
+    if (!Seen.insert(C).second)
+      return;
+    OutF(C);
+  }
+
+private:
+  llvm::SmallSet<PartialConv, 16> Seen;
+  llvm::function_ref<void(PartialConv)> OutF;
+};
+
+class TypeEnumerator {
+public:
+  TypeEnumerator(ASTContext &Ctx) : Ctx(Ctx) {}
+
+  void inverseCopyInit(QualType Target,
+                       llvm::function_ref<void(PartialConv)> OutF) {
+    if (Target->isDependentType())
+      return;
+    Dedup Collector(OutF);
+    inverseCopyInitNoUserConv(Target, [&Collector](PartialConv C) {
+      if (C.Type->isDependentType())
+        return;
+      assert(!C.AfterUserConv &&
+             "user conversions should be handled separately");
+      Collector(C);
+      // A standard conversion is also allowed after a user conversion.
+      C.AfterUserConv = true;
+      Collector(C);
+    });
+    inverseUserConversion(Target, [&Collector](PartialConv C) {
+      if (C.Type->isDependentType())
+        return;
+      Collector(C);
+    });
+  }
+
+  void directConversions(PartialConv C,
+                         llvm::function_ref<void(PartialConv)> OutF) {
+    if (C.Type->isDependentType())
+      return;
+    Dedup Collector(OutF);
+    directConversionsNoUserConv(C, Collector);
+    doUserConversion(C, Collector);
+  }
+
+private:
+  using ConsumerFunc = llvm::function_ref<void(PartialConv)>;
+
+  void inverseCopyInitNoUserConv(QualType T,
+                                 llvm::function_ref<void(PartialConv)> OutF) {
+    if (T->isReferenceType())
+      return inverseReferenceInit(T, OutF);
+    inverseStandardConversion(PartialConv{T, ValueCategory::LVal}, OutF);
+    inverseStandardConversion(PartialConv{T, ValueCategory::RVal}, OutF);
+  }
+
+  void directConversionsNoUserConv(PartialConv C,
+                                   llvm::function_ref<void(PartialConv)> OutF) {
+    doStandardConversion(C, OutF);
+    doReferenceInit(C, OutF);
+  }
+
+  void doUserConversion(PartialConv C, ConsumerFunc OutF) {
+    CXXRecordDecl *Cls = C.Type->getAsCXXRecordDecl();
+    // FIXME(ibiryukov): what if definition is completed at some point in the
+    //                   future?
+    if (!Cls || !Cls->isCompleteDefinition())
+      return;
+    // We record results of direct conversions.
+    for (auto Conv : Cls->getVisibleConversionFunctions()) {
+      if (Conv->getAccess() != AS_public || !llvm::isa<CXXConversionDecl>(Conv))
+        continue;
+      auto ConvSource = MockExpr::forFunctionReturn(
+          llvm::cast<CXXConversionDecl>(Conv)->getConversionType());
+      if (!ConvSource)
+        continue;
+      directConversionsNoUserConv(
+          PartialConv(ConvSource->getType(), ConvSource->getValueCat()),
+          [&](PartialConv C) {
+            C.AfterUserConv = true;
+            OutF(C);
+          });
+    }
+  }
+
+  void inverseUserConversion(QualType T, ConsumerFunc OutF) {
+    CXXRecordDecl *Cls = T->getAsCXXRecordDecl();
+    if (!Cls || !Cls->isCompleteDefinition())
+      return;
+    for (auto Ctor : Cls->ctors()) {
+      if (Ctor->isDeleted() || Ctor->getAccess() != AS_public)
+        continue;
+      // FIXME(ibiryukov): we want to filter out explicit ctors only for copy
+      //    init. However, sema does not provide enough information in code
+      //    completion to do that at the moment.
+      if (!Ctor->isConvertingConstructor(/*AllowExplicit=*/true))
+        continue;
+      // This can happen for ctors with variadic args.
+      if (Ctor->getNumParams() < 1)
+        continue;
+      auto ParamT = Ctor->getParamDecl(0)->getType();
+      if (!Ctor->isCopyOrMoveConstructor()) {
+        inverseCopyInitNoUserConv(ParamT, OutF);
+        continue;
+      }
+      // "Double conversions" are allowed for copy and move ctors.
+      inverseCopyInitNoUserConv(ParamT, [&](PartialConv C) {
+        OutF(C);
+        assert(!C.AfterUserConv);
+        C.AfterUserConv = true;
+        OutF(C);
+      });
+    }
+  }
+
+  void doReferenceInit(PartialConv C, ConsumerFunc OutF) {
+    OutF(C);
+    forAllBaseTypes(C.Type, [&](QualType T) { OutF(PartialConv{T, C.Cat}); });
+    // FIXME: function-to-reference conversions?
+    // User conversions are handled separately.
+  }
+  void inverseReferenceInit(QualType Ref, ConsumerFunc OutF) {
+    assert(Ref->isReferenceType());
+    QualType RefTarget = Ref->getPointeeType();
+    bool CanBindToLVal = Ref->isLValueReferenceType();
+    bool CanBindToRVal =
+        Ref->isRValueReferenceType() ||
+        (Ref->isLValueReferenceType() && RefTarget.isConstQualified() &&
+         !RefTarget.isVolatileQualified());
+    auto TryBindReference = [&](QualType T) {
+      if (CanBindToLVal) {
+        // Direct binding.
+        OutF(PartialConv{T, ValueCategory::LVal});
+      }
+      if (CanBindToRVal) {
+        // Direct binding.
+        OutF(PartialConv{T, ValueCategory::RVal});
+        // r-values can also be obtained via conversions.
+        inverseStandardConversion(
+            PartialConv{T, ValueCategory::RVal}, OutF,
+            /*AllowLValToRVal=*/!Ref->isRValueReferenceType());
+      }
+    };
+
+    TryBindReference(RefTarget);
+    forLessQualifiedTypes(RefTarget, [&](QualType T) { TryBindReference(T); });
+  }
+
+  // Handle enumerating direct and inverse results of the C++ standard
+  // conversions. The following conversions are handled by this function: (first
+  // standard conversion part)
+  // 1. lvalue-to-rvalue
+  // 2. array-to-pointer
+  // 3. function-to-pointer
+  // (second standard conversion part)
+  // 4. integral and floating promotions and conversions
+  // 5. boolean conversions
+  // 6. pointer conversions
+  // 7. pointer-to-member conversions
+  // (third standard conversion part)
+  // 8. function pointer conversion
+  // 9. qualification conversion
+  void doStandardConversion(PartialConv C, ConsumerFunc OutF) {
+    // Handled by inverse conversions:
+    // 1. lvalue-to-rvalue
+    // 2. array-to-pointer
+    // 3. function-to-pointer
+    // 4. integral and floating promotions and conversions
+    // To avoid enumerating all integral types, we map all possible conversions
+    // to either 'int' or 'float'.
+    if (C.Type->isIntegralOrUnscopedEnumerationType()) {
+      if (C.Type.getUnqualifiedType() != Ctx.IntTy)
+        OutF(PartialConv{Ctx.IntTy, ValueCategory::RVal});
+    }
+    if (C.Type->isFloatingType()) {
+      if (C.Type.getUnqualifiedType() != Ctx.FloatTy)
+        OutF(PartialConv{Ctx.FloatTy, ValueCategory::RVal});
+    }
+    // FIXME: 5. boolean conversions
+    // 6. pointer conversions
+    if (C.Type->isPointerType()) {
+      QualType Pointee = C.Type->getPointeeType();
+      // Derived-to-base pointer conversions.
+      forAllBaseTypes(Pointee, [&](QualType BaseT) {
+        OutF(PartialConv{Ctx.getQualifiedType(Ctx.getPointerType(BaseT),
+                                              C.Type.getQualifiers()),
+                         ValueCategory::RVal});
+      });
+      // void pointer conversions.
+      if (!Pointee->isVoidType())
+        OutF(PartialConv{
+            Ctx.getQualifiedType(Ctx.getPointerType(Ctx.getQualifiedType(
+                                     Ctx.VoidTy, Pointee.getQualifiers())),
+                                 C.Type.getQualifiers()),
+            ValueCategory::RVal});
+    }
+    // FIXME: 7. pointer-to-member conversions
+    // Handled by inverse conversions:
+    // 8. function pointer conversion
+    // 9. qualification conversion
+
+    // No conversions is also an option.
+    OutF(C);
+  }
+
+  void inverseStandardConversion(PartialConv C, ConsumerFunc OutF,
+                                 bool AllowLvalToRval = true) {
+    if (C.Type->getAsCXXRecordDecl())
+      return; // C++ class type conversions are handled by
+              // inverseUserConversion.
+    // First, define all inverse conversions we are going to apply.
+    // 9. qualification conversion
+    auto QualConv = [this](PartialConv C, ConsumerFunc OutF) {
+      OutF(C);
+      if (!C.Type->isPointerType())
+        return;
+      forLessQualifiedTypes(C.Type->getPointeeType(), [&](QualType T) {
+        OutF(PartialConv{
+            Ctx.getQualifiedType(Ctx.getPointerType(T), C.Type.getQualifiers()),
+            ValueCategory::RVal});
+      });
+      OutF(PartialConv{Ctx.NullPtrTy, ValueCategory::RVal});
+    };
+    // FIXME: 8. function pointer conversion
+    // FIXME: 7. pointer-to-member conversions
+    // 6. pointer conversions
+    // FIXME: 5. boolean conversions
+    // 4. integral and floating promotions and conversions
+    auto NumConv = [this](PartialConv C, ConsumerFunc OutF) {
+      OutF(C);
+      // Any integer or floating type could've been obtained by doing integer
+      // conversions. We model those by adding 'float' and 'int' with various
+      // qualifiers as source types.
+      if ((C.Type->isIntegerType() && !C.Type->isEnumeralType()) ||
+          C.Type->isFloatingType()) {
+        OutF(PartialConv{Ctx.IntTy, ValueCategory::RVal});
+        OutF(PartialConv{Ctx.FloatTy, ValueCategory::RVal});
+
+        OutF(PartialConv{Ctx.IntTy.withConst(), ValueCategory::RVal});
+        OutF(PartialConv{Ctx.FloatTy.withConst(), ValueCategory::RVal});
+        // We do not add volatile because it is rare. It means we will not
+        // classify 'volatile int' as convertible to 'int'.
+      }
+      // FIXME: Enum types.
+    };
+    // (second standard conversion part)
+    // FIXME: 3. function-to-pointer
+    // 2. array-to-pointer
+    // 1. lvalue-to-rvalue
+    auto LvalToRvalConv = [](PartialConv C, ConsumerFunc OutF) {
+      OutF(C);
+      if (C.Cat == ValueCategory::RVal)
+        OutF(PartialConv{C.Type, ValueCategory::LVal});
+    };
+    // Run the computations we defined.
+    if (AllowLvalToRval)
+      chain(C, QualConv, NumConv, LvalToRvalConv, OutF);
+    else
+      chain(C, QualConv, NumConv, OutF);
+  }
+
+  void forLessQualifiedTypes(QualType T,
+                             llvm::function_ref<void(QualType T)> Cont) {
+    if (T.isConstQualified()) {
+      QualType NoConst = T;
+      NoConst.removeLocalConst();
+      Cont(NoConst);
+    }
+    if (T.isVolatileQualified()) {
+      QualType NoVolatile = T;
+      NoVolatile.removeLocalVolatile();
+      Cont(NoVolatile);
+    }
+    if (T.isConstQualified() && T.isVolatileQualified()) {
+      QualType NoCV = T;
+      NoCV.removeLocalCVRQualifiers(Qualifiers::Const | Qualifiers::Volatile);
+      Cont(NoCV);
+    }
+  }
+
+  void forAllBaseTypes(QualType T, llvm::function_ref<void(QualType)> OutF) {
+    auto *Cls = T->getAsCXXRecordDecl();
+    if (!Cls)
+      return;
+
+    auto Quals = T.getQualifiers();
+    forEachBase(Cls, [&](CXXRecordDecl *Base) {
+      OutF(Ctx.getQualifiedType(Ctx.getRecordType(Base), Quals));
+    });
+  }
+
+  ASTContext &Ctx;
+};
+
+llvm::Optional<SHA1Array> encodeSType(ASTContext &Ctx, const PartialConv &C) {
+  assert(!C.Type.isNull());
+  assert(C.Type.isCanonical());
+
+  llvm::SHA1 S;
+  S.init();
+  S.update(C.Cat == ValueCategory::LVal ? "{LV}" : "{RV}");
+  S.update(C.AfterUserConv ? "{user-conv}" : "{no-user-conv}");
+  llvm::SmallString<128> Out;
+  if (!index::generateUSRForType(C.Type, Ctx, Out))
+    S.update(Out);
+  else
+    return llvm::None;
+
+  SHA1Array Data;
+  llvm::copy(S.final(), Data.begin());
+  return Data;
+}
+} // namespace
+
+SHA1Array computeSHA1(llvm::StringRef Input) {
+  llvm::SHA1 S;
+  S.update(Input);
+
+  SHA1Array Result;
+  llvm::copy(S.final(), Result.begin());
+  return Result;
+}
+
+SType::SType(SHA1Array Data) : Data(Data) {}
+
+SType SType::fromHexStr(llvm::StringRef Str) {
+  std::string StrData = llvm::fromHex(Str);
+  assert(StrData.size() == 20);
+  SHA1Array Data;
+  llvm::copy(StrData, Data.begin());
+  return SType(Data);
+}
+
+std::string SType::toHexStr() const { return llvm::toHex(Data); }
+
+llvm::Optional<MockExpr>
+MockExpr::forCompletion(const CodeCompletionResult &R) {
+  if (!R.Declaration)
+    return llvm::None;
+  auto *VD = llvm::dyn_cast<ValueDecl>(R.Declaration);
+  if (!VD)
+    return llvm::None;
+
+  QualType T = VD->getType().getCanonicalType();
+  // Just ignore the references, completions that name existing decls are always
+  // l-values.
+  if (T->isReferenceType())
+    T = T->getPointeeType();
+  if (!T->isFunctionType())
+    return MockExpr(ValueCategory::LVal, T);
+  // Functions are a special case. They are completed as 'foo()' and we want to
+  // match their return type, rather than the function type itself.
+  // FIXME(ibiryukov): in some cases, we might want to avoid completing `()`
+  // after the function name, e.g. `std::cout << std::endl`.
+  return MockExpr::forFunctionReturn(T->getAs<FunctionType>()->getReturnType());
+}
+
+llvm::Optional<MockExpr> MockExpr::forFunctionReturn(QualType Ret) {
+  if (Ret->isDependentType())
+    return llvm::None;
+  if (!Ret->isReferenceType())
+    return MockExpr(ValueCategory::RVal, Ret);
+  return MockExpr(Ret->isLValueReferenceType() ? ValueCategory::LVal
+                                               : ValueCategory::RVal,
+                  Ret->getPointeeType());
+}
+
+llvm::DenseMap<SType, float> SType::forCopyInitOf(ASTContext &Ctx,
+                                                  QualType Target) {
+  llvm::DenseMap<SType, float> Result;
+  detail::collectConvertibleTo(Ctx, Target, [&](PartialConv C) {
+    auto Encoded = encodeSType(Ctx, C);
+    if (!Encoded)
+      return;
+
+    // FIXME(ibiryukov): this should live in Quality.h
+    float QualityMult;
+    if (C.AfterUserConv)
+      QualityMult = 1.5; // user conversions are not good.
+    else if (C.Type.getUnqualifiedType() != Target.getUnqualifiedType())
+      QualityMult = 2.0; // standard conversions are a bit worse, but not much.
+    else
+      QualityMult = 3.0; // exact type matches are great.
+
+    float &Score = Result[SType(*Encoded)];
+    Score = std::max(Score, QualityMult);
+  });
+  return Result;
+}
+
+llvm::SmallVector<SType, 2>
+SType::fromCompletionResult(ASTContext &Ctx, const CodeCompletionResult &R) {
+  auto E = MockExpr::forCompletion(R);
+  if (!E)
+    return {};
+  llvm::SmallVector<SType, 2> Result;
+  detail::collectConvertibleFrom(Ctx, *E, [&](PartialConv C) {
+    auto T = encodeSType(Ctx, C);
+    if (!T)
+      return;
+    Result.push_back(SType(*T));
+  });
+  return Result;
+}
+
+llvm::Optional<float> typesMatch(const llvm::DenseMap<SType, float> &Expected,
+                                 llvm::ArrayRef<SType> Actual) {
+  llvm::Optional<float> Mult;
+  for (auto T : Actual) {
+    auto It = Expected.find(T);
+    if (It == Expected.end())
+      continue;
+    Mult = std::max(Mult.getValueOr(1.0f), It->second);
+  }
+  return Mult;
+}
+namespace detail {
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const PartialConv &C) {
+  return OS << (C.Cat == ValueCategory::LVal ? "lval " : "rval ")
+            << C.Type.getAsString() << (C.AfterUserConv ? "[user-conv]" : "");
+}
+
+void collectConvertibleFrom(ASTContext &Ctx, MockExpr Source,
+                            llvm::function_ref<void(PartialConv)> OutF) {
+  QualType T = Source.getType();
+  ValueCategory VC = Source.getValueCat();
+  TypeEnumerator(Ctx).directConversions(PartialConv{T, VC},
+                                        [OutF](PartialConv C) { OutF(C); });
+}
+
+void collectConvertibleTo(ASTContext &Ctx, QualType Target,
+                          llvm::function_ref<void(PartialConv)> OutF) {
+  if (Target.isNull())
+    return;
+  TypeEnumerator(Ctx).inverseCopyInit(Target, OutF);
+}
+} // namespace detail
+} // namespace clangd
+} // namespace clang
Index: unittests/clangd/CMakeLists.txt
===================================================================
--- unittests/clangd/CMakeLists.txt
+++ unittests/clangd/CMakeLists.txt
@@ -18,6 +18,7 @@
   ContextTests.cpp
   DexTests.cpp
   DraftStoreTests.cpp
+  ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
Index: unittests/clangd/ExpectedTypeTest.cpp
===================================================================
--- /dev/null
+++ unittests/clangd/ExpectedTypeTest.cpp
@@ -0,0 +1,475 @@
+//===-- SimpleTypeTests.cpp  ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangdUnit.h"
+#include "ExpectedTypes.h"
+#include "TestTU.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock-matchers.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using detail::MockExpr;
+using detail::PartialConv;
+using detail::ValueCategory;
+
+using ::testing::ElementsAre;
+using ::testing::Field;
+using ::testing::Matcher;
+using ::testing::UnorderedElementsAre;
+using ::testing::UnorderedElementsAreArray;
+
+class ASTTest : public ::testing::Test {
+protected:
+  void build(llvm::StringRef Code) {
+    assert(!AST && "AST built twice");
+    AST = TestTU::withCode(Code).build();
+  }
+
+  const ValueDecl *decl(llvm::StringRef Name) {
+    return &llvm::cast<ValueDecl>(findDecl(*AST, Name));
+  }
+
+  QualType typeOf(llvm::StringRef Name) {
+    return decl(Name)->getType().getCanonicalType();
+  }
+
+  ASTContext &ASTCtx() { return AST->getASTContext(); }
+
+private:
+  // Set after calling build().
+  llvm::Optional<ParsedAST> AST;
+};
+
+class ExpectedTypeCollectorTest : public ASTTest {
+protected:
+  std::vector<PartialConv> convertibleTo(QualType To) {
+    std::vector<PartialConv> Result;
+    detail::collectConvertibleTo(ASTCtx(), To,
+                                 [&](PartialConv C) { Result.push_back(C); });
+    return Result;
+  }
+
+  std::vector<PartialConv> convertibleFrom(const NamedDecl *D) {
+    std::vector<PartialConv> Result;
+    detail::collectConvertibleFrom(
+        ASTCtx(),
+        *MockExpr::forCompletion(CodeCompletionResult(D, CCP_Declaration)),
+        [&](PartialConv C) { Result.push_back(C); });
+    return Result;
+  }
+};
+
+// Matchers for l-values and r-values, which don't come from user-defined
+// conversions.
+MATCHER_P(lv, TypeStr, "") {
+  return arg.Cat == ValueCategory::LVal && arg.Type.getAsString() == TypeStr;
+}
+MATCHER_P(rv, TypeStr, "") {
+  return arg.Cat == ValueCategory::RVal && arg.Type.getAsString() == TypeStr;
+}
+
+Matcher<PartialConv> converted(Matcher<PartialConv> M) {
+  return AllOf(M, Field(&PartialConv::AfterUserConv, true));
+}
+
+std::vector<Matcher<PartialConv>>
+alsoConverted(std::vector<Matcher<PartialConv>> Matchers) {
+  std::vector<Matcher<PartialConv>> Result;
+  Result.reserve(Matchers.size() * 2);
+  for (auto M : Matchers) {
+    Result.push_back(M);
+    Result.push_back(converted(M));
+  }
+  return Result;
+}
+
+template <class... StrT>
+Matcher<std::vector<PartialConv>> stdConversions(StrT... TypeStrs) {
+  return UnorderedElementsAreArray(
+      alsoConverted({lv(TypeStrs)..., rv(TypeStrs)...}));
+}
+
+std::vector<Matcher<PartialConv>> concat(std::vector<Matcher<PartialConv>> L,
+                                         std::vector<Matcher<PartialConv>> R) {
+  L.reserve(L.size() + R.size());
+  L.insert(L.end(), R.begin(), R.end());
+  return L;
+}
+
+TEST_F(ExpectedTypeCollectorTest, NumericTypes) {
+  build(R"cpp(
+    bool b;
+    int i;
+    unsigned int ui;
+    long long ll;
+    float f;
+    double d;
+  )cpp");
+
+  EXPECT_THAT(convertibleTo(decl("i")->getType()),
+              stdConversions("int", "float", "const int", "const float"));
+  EXPECT_THAT(convertibleFrom(decl("i")), UnorderedElementsAre(lv("int")));
+
+  const ValueDecl *Ints[] = {decl("b"), decl("ui"), decl("ll")};
+  for (const auto *D : Ints) {
+    std::string DType = D->getType().getAsString();
+    EXPECT_THAT(
+        convertibleTo(D->getType()),
+        stdConversions(DType, "int", "float", "const int", "const float"));
+    EXPECT_THAT(convertibleFrom(D), UnorderedElementsAre(lv(DType), rv("int")));
+  }
+
+  // Check float.
+  EXPECT_THAT(convertibleTo(decl("f")->getType()),
+              stdConversions("int", "float", "const int", "const float"));
+  EXPECT_THAT(convertibleFrom(decl("f")), UnorderedElementsAre(lv("float")));
+  // Check double.
+  EXPECT_THAT(
+      convertibleTo(decl("d")->getType()),
+      stdConversions("int", "double", "float", "const int", "const float"));
+  EXPECT_THAT(convertibleFrom(decl("d")),
+              UnorderedElementsAre(rv("float"), lv("double")));
+}
+
+TEST_F(ExpectedTypeCollectorTest, EnumTypes) {
+  build(R"cpp(
+    enum UnscopedEnum {};
+    enum class ScopedEnum {};
+
+    UnscopedEnum ue;
+    ScopedEnum se;
+  )cpp");
+
+  // Unscoped enums.
+  EXPECT_THAT(convertibleTo(decl("ue")->getType()),
+              stdConversions("enum UnscopedEnum"));
+  EXPECT_THAT(convertibleFrom(decl("ue")),
+              UnorderedElementsAre(lv("enum UnscopedEnum"), rv("int")));
+
+  // Scoped enums.
+  EXPECT_THAT(convertibleTo(decl("se")->getType()),
+              stdConversions("enum ScopedEnum"));
+  EXPECT_THAT(convertibleFrom(decl("se")),
+              UnorderedElementsAre(lv("enum ScopedEnum")));
+}
+
+TEST_F(ExpectedTypeCollectorTest, ClassTypes) {
+  build(R"cpp(
+    struct IndBase {};
+    struct Base : IndBase {};
+    struct Derived : Base {};
+
+    Derived foo;
+  )cpp");
+
+  EXPECT_THAT(convertibleTo(decl("foo")->getType()),
+              stdConversions("struct Derived", "const struct Derived"));
+  EXPECT_THAT(convertibleFrom(decl("foo")),
+              UnorderedElementsAre(lv("struct Derived"), lv("struct Base"),
+                                   lv("struct IndBase")));
+}
+
+TEST_F(ExpectedTypeCollectorTest, PointerTypes) {
+  build(R"cpp(
+    struct Base {};
+    struct Derived : Base {};
+
+    Derived* p_derived;
+    const Derived* p_const_derived;
+    void* p_void;
+    decltype(nullptr) p_null;
+  )cpp");
+
+  EXPECT_THAT(convertibleTo(decl("p_derived")->getType()),
+              stdConversions("struct Derived *", "nullptr_t"));
+  EXPECT_THAT(convertibleFrom(decl("p_derived")),
+              UnorderedElementsAre(lv("struct Derived *"), rv("struct Base *"),
+                                   rv("void *")));
+
+  EXPECT_THAT(convertibleTo(decl("p_const_derived")->getType()),
+              stdConversions("const struct Derived *", "struct Derived *",
+                             "nullptr_t"));
+  EXPECT_THAT(convertibleFrom(decl("p_const_derived")),
+              UnorderedElementsAre(lv("const struct Derived *"),
+                                   rv("const struct Base *"),
+                                   rv("const void *")));
+  EXPECT_THAT(convertibleTo(decl("p_null")->getType()),
+              stdConversions("nullptr_t"));
+  EXPECT_THAT(convertibleFrom(decl("p_null")),
+              UnorderedElementsAre(lv("nullptr_t")));
+  EXPECT_THAT(convertibleTo(decl("p_void")->getType()),
+              stdConversions("void *", "nullptr_t"));
+  EXPECT_THAT(convertibleFrom(decl("p_void")),
+              UnorderedElementsAre(lv("void *")));
+}
+
+TEST_F(ExpectedTypeCollectorTest, ReferenceBinding) {
+  build(R"cpp(
+    int &lv;
+    int &&rv;
+    const int& clv;
+  )cpp");
+
+  EXPECT_THAT(convertibleTo(decl("lv")->getType()),
+              UnorderedElementsAre(lv("int"), converted(lv("int"))));
+  EXPECT_THAT(convertibleFrom(decl("lv")), UnorderedElementsAre(lv("int")));
+
+  EXPECT_THAT(
+      convertibleTo(decl("rv")->getType()),
+      UnorderedElementsAreArray(alsoConverted(
+          {rv("int"), rv("float"), rv("const int"), rv("const float")})));
+  EXPECT_THAT(convertibleFrom(decl("rv")), UnorderedElementsAre(lv("int")));
+
+  EXPECT_THAT(convertibleTo(decl("clv")->getType()),
+              stdConversions("int", "const int", "float", "const float"));
+  EXPECT_THAT(convertibleFrom(decl("clv")),
+              UnorderedElementsAre(lv("const int")));
+}
+
+TEST_F(ExpectedTypeCollectorTest, UserConversions) {
+  build(R"cpp(
+    struct Foo {
+      Foo(int&);
+      operator int*();
+    };
+
+    Foo foo;
+  )cpp");
+  EXPECT_THAT(
+      convertibleTo(decl("foo")->getType()),
+      UnorderedElementsAreArray(concat(
+          {lv("int")},
+          alsoConverted({lv("struct Foo"), rv("struct Foo"),
+                         lv("const struct Foo"), rv("const struct Foo")}))));
+  EXPECT_THAT(convertibleFrom(decl("foo")),
+              UnorderedElementsAre(lv("struct Foo"), converted(rv("int *")),
+                                   converted(rv("void *"))));
+}
+
+class ConvertibleToMatcher
+    : public ::testing::MatcherInterface<const ValueDecl *> {
+  ASTContext &Ctx;
+  QualType To;
+  llvm::DenseMap<SType, float> ExpectedTypes;
+
+public:
+  ConvertibleToMatcher(ASTContext &Ctx, QualType To)
+      : Ctx(Ctx), To(To.getCanonicalType()) {
+    ExpectedTypes = SType::forCopyInitOf(Ctx, To);
+  }
+
+  void DescribeTo(std::ostream *OS) const override {
+
+    *OS << "Is convertible to type '" << To.getAsString() << "'";
+  }
+
+  bool MatchAndExplain(const ValueDecl *V,
+                       ::testing::MatchResultListener *L) const override {
+    assert(V);
+    assert(&V->getASTContext() == &Ctx && "different ASTs?");
+    auto ConvertibleTo = SType::fromCompletionResult(
+        Ctx, CodeCompletionResult(V, CCP_Declaration));
+
+    bool Matched = typesMatch(ExpectedTypes, ConvertibleTo).hasValue();
+    if (L->IsInterested())
+      *L << "Set of types for source and target "
+         << (Matched ? "matched" : "did not match")
+         << "\n\tTarget type: " << To.getAsString()
+         << "\n\tSource value type: " << V->getType().getAsString();
+    return Matched;
+  }
+};
+
+class ExpectedTypeConversionTest : public ASTTest {
+protected:
+  Matcher<const ValueDecl *> isConvertibleTo(QualType To) {
+    return ::testing::MakeMatcher(new ConvertibleToMatcher(ASTCtx(), To));
+  }
+};
+
+TEST_F(ExpectedTypeConversionTest, BasicTypes) {
+  build(R"cpp(
+    bool b;
+    int i;
+    unsigned int ui;
+    long long ll;
+    float f;
+    double d;
+    int func();
+    int* iptr;
+    bool* bptr;
+  )cpp");
+
+  const ValueDecl *Nums[] = {decl("b"),  decl("i"), decl("ui"),
+                             decl("ll"), decl("f"), decl("d")};
+  const ValueDecl *Func = decl("func");
+  const ValueDecl *IntPtr = decl("iptr");
+  const ValueDecl *BoolPtr = decl("bptr");
+
+  for (const ValueDecl *Num : Nums) {
+    for (const ValueDecl *OtherNum : Nums)
+      EXPECT_THAT(Num, isConvertibleTo(OtherNum->getType()));
+    EXPECT_THAT(Num, Not(isConvertibleTo(Func->getType())));
+    EXPECT_THAT(Num, Not(isConvertibleTo(IntPtr->getType())));
+    EXPECT_THAT(Num, Not(isConvertibleTo(BoolPtr->getType())));
+  }
+
+  EXPECT_THAT(IntPtr, isConvertibleTo(IntPtr->getType()));
+  EXPECT_THAT(IntPtr, Not(isConvertibleTo(BoolPtr->getType())));
+}
+
+TEST_F(ExpectedTypeConversionTest, Enums) {
+  build(R"cpp(
+    enum UnscopedEnum {};
+    enum OtherUnscopedEnum {};
+    enum class ScopedEnum {};
+
+    int i;
+    float f;
+    UnscopedEnum ue;
+    OtherUnscopedEnum oue;
+    ScopedEnum e;
+  )cpp");
+
+  // Unscoped enums are convertible to any other integer type, but not to any
+  // other unscoped enum type.
+  EXPECT_THAT(decl("ue"),
+              AllOf(isConvertibleTo(typeOf("f")), isConvertibleTo(typeOf("i")),
+                    Not(isConvertibleTo(typeOf("oue")))));
+  // Scoped enums are not convertible to any numeric types.
+  EXPECT_THAT(decl("e"), AllOf(Not(isConvertibleTo(typeOf("f"))),
+                               Not(isConvertibleTo(typeOf("i")))));
+
+  /// Numeric types are not convertible to any of the enum types.
+  EXPECT_THAT(decl("i"), AllOf(Not(isConvertibleTo(typeOf("ue"))),
+                               Not(isConvertibleTo(typeOf("e")))));
+  EXPECT_THAT(decl("f"), AllOf(Not(isConvertibleTo(typeOf("ue"))),
+                               Not(isConvertibleTo(typeOf("e")))));
+}
+
+TEST_F(ExpectedTypeConversionTest, ClassBases) {
+  build(R"cpp(
+    struct Base {};
+    struct Derived : Base {};
+    struct Unrelated {};
+
+    Base base;
+    Derived derived;
+    Unrelated unrelated;
+  )cpp");
+
+  EXPECT_THAT(decl("derived"),
+              AllOf(isConvertibleTo(typeOf("base")),
+                    Not(isConvertibleTo(typeOf("unrelated")))));
+  EXPECT_THAT(decl("base"), AllOf(Not(isConvertibleTo(typeOf("derived"))),
+                                  Not(isConvertibleTo(typeOf("unrelated")))));
+}
+
+TEST_F(ExpectedTypeConversionTest, Pointers) {
+  build(R"cpp(
+    struct Base {};
+    struct Derived : Base {};
+    strucr Unrelated {};
+
+    Base* p_base;
+    Derived* p_derived;
+    Unrelated* p_unrelated;
+
+    const Base* p_const_base;
+    const Derived* p_const_derived;
+
+    void* p_void;
+    const void* p_const_void;
+  )cpp");
+
+  EXPECT_THAT(decl("p_derived"),
+              AllOf(isConvertibleTo(typeOf("p_base")),
+                    isConvertibleTo(typeOf("p_const_base")),
+                    isConvertibleTo(typeOf("p_const_derived")),
+                    Not(isConvertibleTo(typeOf("p_unrelated"))),
+                    isConvertibleTo(typeOf("p_void")),
+                    isConvertibleTo(typeOf("p_const_void"))));
+  EXPECT_THAT(decl("p_const_derived"),
+              AllOf(Not(isConvertibleTo(typeOf("p_base"))),
+                    isConvertibleTo(typeOf("p_const_base")),
+                    Not(isConvertibleTo(typeOf("p_derived"))),
+                    Not(isConvertibleTo(typeOf("p_unrelated"))),
+                    Not(isConvertibleTo(typeOf("p_void"))),
+                    isConvertibleTo(typeOf("p_const_void"))));
+  EXPECT_THAT(decl("p_base"),
+              AllOf(isConvertibleTo(typeOf("p_const_base")),
+                    Not(isConvertibleTo(typeOf("p_derived"))),
+                    Not(isConvertibleTo(typeOf("p_const_derived")))));
+}
+
+TEST_F(ExpectedTypeConversionTest, ValueCategories) {
+  build(R"cpp(
+    int x;
+
+    int& lv;
+    const int& const_lv;
+    int&& rv;
+
+    int int_func();
+    int&& rv_func();
+    int& lv_func();
+    const int& const_lv_func();
+  )cpp");
+  EXPECT_THAT(decl("x"), AllOf(isConvertibleTo(typeOf("lv")),
+                               isConvertibleTo(typeOf("const_lv")),
+                               Not(isConvertibleTo(typeOf("rv")))));
+  EXPECT_THAT(decl("const_lv"), isConvertibleTo(typeOf("x")));
+  EXPECT_THAT(decl("rv"), AllOf(isConvertibleTo(typeOf("lv")),
+                                isConvertibleTo(typeOf("const_lv")),
+                                Not(isConvertibleTo(typeOf("rv")))));
+  EXPECT_THAT(decl("lv_func"), AllOf(isConvertibleTo(typeOf("lv")),
+                                     isConvertibleTo(typeOf("const_lv")),
+                                     Not(isConvertibleTo(typeOf("rv")))));
+  EXPECT_THAT(decl("rv_func"), AllOf(Not(isConvertibleTo(typeOf("lv"))),
+                                     isConvertibleTo(typeOf("const_lv")),
+                                     isConvertibleTo(typeOf("rv"))));
+}
+
+TEST_F(ExpectedTypeConversionTest, InaccessibleBases) {
+  build(R"cpp(
+    struct Base {};
+    struct PrivateBase : Base {};
+    struct ProtectedBase {};
+    struct PublicBase {};
+
+    struct X : PublicBase
+              , private PrivateBase
+              , protected ProtectedBase {};
+
+    Base base;
+
+    PrivateBase privBase;
+    ProtectedBase protBase;
+    PublicBase pubBase;
+
+    X x;
+  )cpp");
+
+  EXPECT_THAT(decl("x"), AllOf(isConvertibleTo(typeOf("pubBase")),
+                               Not(isConvertibleTo(typeOf("protBase"))),
+                               Not(isConvertibleTo(typeOf("base"))),
+                               Not(isConvertibleTo(typeOf("privBase")))));
+}
+} // namespace
+} // namespace clangd
+} // namespace clang