[clangd] Initial implementation of expected types

[ilya-biryukov]

Summary

Provides facilities to model the C++ conversion rules without the AST.
The introduced representation can be stored in the index and used to
implement type-based ranking improvements for index-based completions.

[ilya-biryukov]

The implementation might look a bit scary, please feel free to ask for comments/clarifications!

[ilya-biryukov]

clangd/ExpectedTypes.h

119

I assume this will be controversial. Happy to discuss/change.
We are currently building this representation based on USRs for types, the alternative is to store the USRs directly. Would be a bit more debuggable/explainable in case of failures, but also not particularly readable.

[sammccall]

This seems very clever, but extremely complicated - you've implemented much of C++'s conversion logic, it's not clear to me which parts are actually necessary to completion quality.
(Honestly this applies to expected types overall - it seems intuitively likely that it's a good signal, it seems less obvious that it pulls its weight if it can't be made simple).

From the outside it seems much of it is YAGNI, and if we do then we need to build it up slowly with an eye for maintainability.
Can we start with expected type boosting (no conversions) as previously discussed, and later measure which other parts make a difference? (I think we'll need/want the simple model anyway, for this to work with Dex and other token-based indexes).

clangd/ExpectedTypes.h

66

While a hash of a string might be a reasonable choice in the long term, I worry about debuggability. (With SymbolID we can just look up the symbol).

You could make the hashing an implementation detail of the index, and have the APIs speak in terms of opaque strings. But that forces the index to be able to report the full opaque string of each returned symbol (for scoring), so the index now has to have a lookup table... messy.

Another fun thing about this representation is that you're storing 20 bytes of data (+ overhead) for common types like "void" where we could get away with one.

66

in the *short run* I'd suggest just printing the type name and using that as the representation.
I'm happy to (eventually) learn about the semantics of USRs in types, but not today :-)

68

this represents a type (in the c++ sense), not a conversion, right?

69

"convertible (using equality)" is confusing.

It sounds like "this is actually an equivalence class of types" but I think that's not true, because it's not symmetric.

Isn't the model here just "SType is a serializable token representing a type. They can be compared for equality."

72

Is this a placeholder name? It's not clear what it means.

Suggest OpaqueType or ExpectedType

81

can we separate "get the representative set of types for R" from "encode them as SType"?
Seems like the APIs would be easier to test and understand.

(I think at least the former should be a non-member function BTW, to keep clear that SType itself isn't aware of any clever folding or whatnot)

82

coupling to CompletionResult seems premature here, can we stick to passing getExpectedType() until we know that abstraction needs to be broken?

91

I don't understand the scale here. If better conversions get higher numbers, what number does "no conversion" get?
The code looks like worse conversions get higher numbers.
I'd suggest using an additive penalty to avoid confusion with scores, but really...

this all seems like YAGNI. Will a set do for now?

213

why is implementing one of these directions not enough?

It should probably be:
As far as I can tell, derived-to-base is the tricky one here: it's an important conversion (albeit one we should leave out of the first patch), and you can't ask "what's convertible to base" since the answer is an open set you can't see.

So it seems the minimal set you need for handling pointer to base is Type getRepresentative(Type) and set<Type> getRepresentativesAfterConversion(Type) or so...

213

names are unclear: is collectConvertibleFrom(T) the convertible-from types for T (i.e the types T is convertible from), or the types that are convertible from T?

[ioeric]

In D52273#1241281, @sammccall wrote:

This seems very clever, but extremely complicated - you've implemented much of C++'s conversion logic, it's not clear to me which parts are actually necessary to completion quality.
(Honestly this applies to expected types overall - it seems intuitively likely that it's a good signal, it seems less obvious that it pulls its weight if it can't be made simple).

From the outside it seems much of it is YAGNI, and if we do then we need to build it up slowly with an eye for maintainability.
Can we start with expected type boosting (no conversions) as previously discussed, and later measure which other parts make a difference? (I think we'll need/want the simple model anyway, for this to work with Dex and other token-based indexes).

+1 to a simpler model.

As chatted offline, I think the return type can be split into multiple orthogonal signals. For example, const T & can be split into 3 independent signals {const, type T, reference}. I think this can make the reasoning of boosting/scoring easier for both index and code completion. Agree with Sam that we should start with something simple (e.g. type matching without conversing) and land basic components to make further evaluation possible.

[ilya-biryukov]

This seems very clever, but extremely complicated - you've implemented much of C++'s conversion logic, it's not clear to me which parts are actually necessary to completion quality.

Clearly the model that supports C++ conversions is something that will improve code completion quality.
I do agree it's not trivial, but would argue we at least want:

• qualification conversions (i.e. adding const)
• user-defined conversions (e.g. operator bool is commonly useful think)
• derived-to-base conversions (Derived* should convert to Base*)

Without those, we don't support a bunch of useful cases.

As chatted offline, I think the return type can be split into multiple orthogonal signals. For example, const T & can be split into 3 independent signals {const, type T, reference}. I think this can make the reasoning of boosting/scoring easier for both index and code completion. Agree with Sam that we should start with something simple (e.g. type matching without conversing) and land basic components to make further evaluation possible.

Yeah, I do keep it in mind and I think it's a great idea. E.g., we can put all numeric types into one equivalence class and get rid of all numeric conversions.
That adds some complexity to the interface, though, I wanted to measure how the trivial solution (enumerate all types) works. To make sure we actually can't get away without it.

[ilya-biryukov]

clangd/ExpectedTypes.h

68

It's an "expression" with an extra data with some extra data (whether the user conversion was applied to get this expression)

82

There's some useful logic that is tied to completion results, e.g. to extract function return type CompletionResult.
Happy to accept a decl, but would keep the name fromCompletionResult. Does that LG?

213

Derived-to-base and user conversions.

We can't enumerate all derived classes for some type, so instead need to enumerate all bases when adding a symbol to the index.
We can't enumerate all types that have user-defined conversions to some type T, so we need to enumerate all user-defined conversions when adding a symbol instead.

[sammccall]

Happy to speculate about what might work here, but I strongly believe the path forward here is to build the simplest version of this feature, without conversions, and try to avoid complicated conversion logic if we can get most of the benefit in simpler ways.

In D52273#1243652, @ilya-biryukov wrote:

This seems very clever, but extremely complicated - you've implemented much of C++'s conversion logic, it's not clear to me which parts are actually necessary to completion quality.

Clearly the model that supports C++ conversions is something that will improve code completion quality.

It's not clear that will be significant. This isn't hard to measure, so I'm not sure why we should guess. And I'm not sure why it all has to go in the first patch.

I do agree it's not trivial, but would argue we at least want:

• qualification conversions (i.e. adding const)

Another approach here is just always dropping const. (And refs, and so on). This will create some false positives, but maybe they don't hurt much. This handles some true cases too, like invoking copy constructors.

• user-defined conversions (e.g. operator bool is commonly useful think)

My guess is you're not going to measure a difference here, bool has lots of false positives and others are rare.

• derived-to-base conversions (Derived* should convert to Base*)

Yes, probably. If this ends up being the only "chain" we have to follow, we're probably in good shape complexity-wise.

[ilya-biryukov]

• Simplify the initial implementation
• Rename SType to OpaqueType

[ilya-biryukov]

I've run the measurements on a highly simplified vs the original complicated model and got roughly the same results wrt to ranking improvements, so sending a new version of the patch with highly simplified mode for the type representation.
I believe there are still gains to be had from a more thorough treatment of C++ conversions, but there is definitely much to do in other areas that should provide better ground for seeing the actual improvements with the more complicated model.

In any case, starting with something simple is definitely a better ground. Thanks for initial review and suggestions!
And please take a look at the new version, it is significantly simpler and should be pretty easy to review :-)

[malaperle]

What is the goal for doing this without the AST? Is the goal to not have to keep the AST and save memory?

[ilya-biryukov]

In D52273#1294767, @malaperle wrote:

What is the goal for doing this without the AST? Is the goal to not have to keep the AST and save memory?

We don't have AST for index completions.

[ioeric]

clangd/ExpectedTypes.cpp

28

maybe add a comment what ValueDecl covers roughly? E.g. functions, classes, variables etc.

41

IIUC, we also encode the qualifiers into the final representation? If so, have you considered the underlying type without qualifiers? It seems to me this might be too restrictive for type-based boosting. For code completion ranking, I think type qualifiers (const etc) can be separate signals.

clangd/ExpectedTypes.h

11

We might want to formalize what "convertible" means here. E.g. does it cover conversion between base and derived class? Does it cover double <-> int conversion?

30

The name seems opaque ;) Why is it opaque?

38

why "preferred type"? maybe add a comment?

41

What is the raw representation? A hash or the type name or USR?

[ilya-biryukov]

@ioeric, thanks for the review round!
Answering the most important comments, will shortly send changes to actually address the rest.

clangd/ExpectedTypes.cpp

41

This function's responsibility is to encode the type. There is code to strip the qualifiers from the types in toEquivClass.
The initial patch does not take qualifiers into account as none of the complicated conversion logic (qualifiers were taken into account there) the original patch had made much difference in the ranking measurements I made.
That said, this change does not aim to finalize the type encoding. I'll be looking into improving the type-based ranking after this lands, might re-add qualifiers if they turn out to be an improvement. Want to prove this with measurements, though.

clangd/ExpectedTypes.h

11

I want to leave it vague for now. Convertible means whatever we think is good for code completion ranking.
Formalizing means we'll either dig into the C++ encoding or be imprecise.

Happy to add the docs, but they'll probably get outdated on every change. Reading the code is actually simpler to get what's going on at this point.

38

That's the terminology that clang uses for completion's context type. Will add a comment, thanks!

41

A string representation of the usr, but users shouldn't rely on it.
The contract is: you can use it to compare for equality and nothing else, so the comment is actually accurate :-)

[sammccall]

clangd/ExpectedTypes.cpp

13

returning QualType vs Type*? It seems we strip all qualifiers, seems clearest for the return type to reflect that.

16

Maybe we want Ctx.getUnqualifiedArrayType here or (more likely?) do array-to-pointer decay?

17

wow, "enumeral" might be my favorite c++-made-up word, displacing "emplace"...

26

nit: dyn_cast_or_null below instead?

31

nit: is canonicalization necessary here? you do it in toEquivClass
(I guess dropping references is, for the function type check)

34

nit: I'd put the special case in the if() block, but up to you

38

dropping references seems redundant here, as you do it again later

47

I think ultimately we may want to replace this with a custom walker:

• we may want to ignore attributes (e.g. const) or bail out in some cases
• generateUSRForType may not have the exact semantics we want for other random reasons
• we can do tricks with hash_combine to avoid actually building huge strings we don't care about

not something for this patch, but maybe a FIXME?

72

can you reuse fromPreferredType for the rest?

clangd/ExpectedTypes.h

33

Does this need to be a separate class rather than using std::string?
There are echoes of SymbolID here, but there were some factors that don't apply here:

• it was fixed-width
• memory layout was important as we stored lots of these in memory
• we hashed them a lot and wanted a specific hash function

I suspect at least initially producing a somewhat readable std::string a la USRGeneration would be enough.

unittests/clangd/ExpectedTypeTest.cpp

80

note that if you think it's useful you can To.dump(*L->stream())
Maybe this is more interesting if/when we have a custom visitor.

93

I really like the declarative equivalence-class setup of the tests.

A couple of suggestions:

• maybe store the equivalence classes as groups of strings rather than decls, and lazily grab the decls. It's easier to tersely represent them...
• I think the "convertibleTo" DSL obscures/abstracts the actual APIs you're testing - they build opaque types, and you're asserting equality.
• pairwise assertion messages may not give enough context: if you expect a == b == c, and a != b, then whether a == c and b == c are probably relevant

I'd consider actually building up the equivalence classes map<OpaqueType, set</*decl*/string>> and writing a MATCHER_P2(ClassesAre, /*vector<set<string>>*/Classes, /*ParsedAST*/AST, "classes are " + testing::PrintToString(Classes))

That way the actual and expected equivalence classes will be dumped on failure, and you can still grab the decls/types from the AST to dump their details.

[sammccall]

Forgot to say - the scope here looks just right, thanks for slimming this down!

[ilya-biryukov]

• Address comments

[ilya-biryukov]

clangd/ExpectedTypes.cpp

13

Done. That produces a bit more trouble at the callsites, so not sure if it's an improvement overall.

16

Added array-to-pointer decays, they should improve ranking when assigning from an array to a pointer, which is nice.
Also added a FIXME that we should drop qualifiers from inner types of the pointers (since we do this for arrays). I think it's fine to leave it for the later improvements.

17

¯\_(ツ)_/¯

31

It was not important, removed it.

47

USRs actually seems like a pretty good fit here. I'm not sure dropping attributes for internal types would make a big difference in the scoring and not sure how big of a problem the strings are, would be nice to actually learn it's a problem (in memory consumption, memory alloc rates, etc) before changing this.

It's definitely possible to do that, of course, we have a room to change the encoding whenever we want, but would avoid adding a FIXME and committing to this approach in the initial patch.

clangd/ExpectedTypes.h

11

Added a clarification that we want "convertible for the purpose of code completion".

30

Removed the "opaque" from the comment, hopefully this causes less confusion.
The idea is that users shouldn't rely on this representation in any other way than comparing it for equality.

33

Would still want to keep it as a marker type just for the sake of indicating what we return and documentation purposes.
It also adds some type safety (granted, not much) for some use-cases.

There's still an option to go strings with rawStr() if needed.

41

Clarified that we leave a room for ourselves to change the encoding we use.

unittests/clangd/ExpectedTypeTest.cpp

80

From the personal experience, looking at the string representation is usually to figure out what's wrong and dumping wouldn't actually help.
Will probably punt on this for now, happy to reconsider when we'll have a use-case for this.

93

Thanks, this approach works most of the time.
The 'FunctionReturns' test actually relies on the asymmetrical nature of the API, so I had to leave the old API too, but it actually looks much nicer there.

[sammccall]

clangd/ExpectedTypes.h

16

I think this largely rehashes the second sentence of the above para. I'd suggest this one focus more closely on what our model *is*:

We define an encoding of AST types as opaque strings, which can be stored in the index.
Similar types (such as `string` and `const string&`) are folded together, forming equivalence classes with the same encoding.

19

("stable" might suggest across versions)

33

For documentation purposes, using OpaqueType = std::string or so seems like a reasonable compromise?

This is very heavyweight for the amount of typesafety we get.
(Apart from the class itself, you've got == and !=, we should definitely have << as well, DenseMapInfo<> and < may get added down the line...)

43

I'd suggest just fromType, exposing this as the primary method, and then on fromCompletionResult document why it's different.

Having the names suggest the underlying structure (that fromType is "more fundamental") aids understanding, and doesn't really feel like we're painting ourselves into a corner.

Alternately, fromCompletionContext and fromCompletionResult would be more clearly symmetrical.

50

nit: if you keep this class, call this raw() for consistency with symbolid?(

60

any reason to put this in the header?

unittests/clangd/ExpectedTypeTest.cpp

30

This seems fine as a fixture, but I'd merge with the subclass - tests should be easy to read!

52

"convertible to" is a problematic description for a couple of reasons:

• it's a relationship between types, but encapsulates unrelated semantics to do with completions
• it's a higher level of abstraction than the code under test

As discussed offline/below, I think the best remedy here is just to drop this matcher - it's only used in one test that can now live with something much simpler.

108

nit: any reason this takes Decl*s instead of strings? would be a bit terser not to wrap the args in decl()

111

I think we could simplify by only testing the type encodings/equiv classes here, and relying on the function -> return type conversion happening elsewhere.

143

Ooh, we should avoid folding bool with other integer types I think!

You hardly ever want to pass a bool where an int is expected. (The reverse int -> bool is somewhat common, but no more than pointer -> bool... type equivalence isn't the right hammer to solve that case).

174

I think this test is a bit too high-level - there are big abstractions between the test code and the code under test (which is pretty simple).

I'd suggest just
`EXPECT_EQ(

OpaqueType::fromCompletionResult(ASTCtx(), decl("returns_int")),
OpaqueType::fromExpectedType(ASTCtx(), decl("int_"));`

(If you think there's something worth testing for the pointer case, I'd do that instead rather than as well)

[ilya-biryukov]

• Address comments

[ilya-biryukov]

clangd/ExpectedTypes.h

33

As discussed offline, kept the class with an expectation that we'll use the fixed-size representation at some point. Added a comment that it can be viewed as a strong typedef to string for now.

43

Done. Using fromType now.

60

It uses a private constructor of the class, so it seems natural for it to be a private static function.

unittests/clangd/ExpectedTypeTest.cpp

52

Done. It was needed only for one test, testing it diretly now.

143

Fair point, changed this. Bool requires a whole different handling anyway, e.g. I definitely want my pointers to be boosted in if conditions.

174

Done. There is still a helper variable per case (I think it improves the readability a little), but otherwise the test is more straightforward now.

[sammccall]

clangd/ExpectedTypes.cpp

9

nit: using namespace llvm (until/unless we switch other files)

unittests/clangd/ExpectedTypeTest.cpp

34

drop llvm:: here and below?

[ilya-biryukov]

• Add using namespace llvm, get rid of llvm::

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ClangdServer.cpp
   ClangdUnit.cpp
   CodeComplete.cpp
   CodeCompletionStrings.cpp
   Compiler.cpp
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
+  ExpectedTypes.cpp
   FindSymbols.cpp
   FileDistance.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp

clangd/ExpectedTypes.h

+//===--- 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

clangd/ExpectedTypes.cpp

+#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

unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   CancellationTests.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   DexTests.cpp
   DraftStoreTests.cpp
+  ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   QualityTests.cpp

unittests/clangd/ExpectedTypeTest.cpp

+//===-- 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