[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 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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

69 ↗

(On Diff #166165)

"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 ↗

(On Diff #166165)

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

Suggest OpaqueType or ExpectedType

81 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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

91 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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

82 ↗

(On Diff #166165)

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 ↗

(On Diff #166165)

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

27 ↗

(On Diff #173337)

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

40 ↗

(On Diff #173337)

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

10 ↗

(On Diff #173337)

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?

29 ↗

(On Diff #173337)

The name seems opaque ;) Why is it opaque?

37 ↗

(On Diff #173337)

why "preferred type"? maybe add a comment?

40 ↗

(On Diff #173337)

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

40 ↗

(On Diff #173337)

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

10 ↗

(On Diff #173337)

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.

37 ↗

(On Diff #173337)

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

40 ↗

(On Diff #173337)

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

12 ↗

(On Diff #173337)

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

15 ↗

(On Diff #173337)

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

16 ↗

(On Diff #173337)

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

25 ↗

(On Diff #173337)

nit: dyn_cast_or_null below instead?

30 ↗

(On Diff #173337)

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

33 ↗

(On Diff #173337)

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

37 ↗

(On Diff #173337)

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

46 ↗

(On Diff #173337)

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?

71 ↗

(On Diff #173337)

can you reuse fromPreferredType for the rest?

clangd/ExpectedTypes.h

32 ↗

(On Diff #173337)

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

79 ↗

(On Diff #173337)

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.

92 ↗

(On Diff #173337)

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

12 ↗

(On Diff #173337)

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

15 ↗

(On Diff #173337)

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.

16 ↗

(On Diff #173337)

¯\_(ツ)_/¯

30 ↗

(On Diff #173337)

It was not important, removed it.

46 ↗

(On Diff #173337)

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

10 ↗

(On Diff #173337)

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

29 ↗

(On Diff #173337)

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.

32 ↗

(On Diff #173337)

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.

40 ↗

(On Diff #173337)

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

unittests/clangd/ExpectedTypeTest.cpp

79 ↗

(On Diff #173337)

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.

92 ↗

(On Diff #173337)

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

15 ↗

(On Diff #174217)

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.

18 ↗

(On Diff #174217)

("stable" might suggest across versions)

42 ↗

(On Diff #174217)

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.

49 ↗

(On Diff #174217)

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

59 ↗

(On Diff #174217)

any reason to put this in the header?

32 ↗

(On Diff #173337)

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...)

unittests/clangd/ExpectedTypeTest.cpp

29 ↗

(On Diff #174217)

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

51 ↗

(On Diff #174217)

"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.

107 ↗

(On Diff #174217)

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

110 ↗

(On Diff #174217)

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

142 ↗

(On Diff #174217)

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).

173 ↗

(On Diff #174217)

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

42 ↗

(On Diff #174217)

Done. Using fromType now.

59 ↗

(On Diff #174217)

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

32 ↗

(On Diff #173337)

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.

unittests/clangd/ExpectedTypeTest.cpp

51 ↗

(On Diff #174217)

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

142 ↗

(On Diff #174217)

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

173 ↗

(On Diff #174217)

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

8 ↗

(On Diff #175050)

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

unittests/clangd/ExpectedTypeTest.cpp

33 ↗

(On Diff #175050)

drop llvm:: here and below?

[ilya-biryukov]

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

clang-tools-extra/trunk/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
   FS.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   JSONTransport.cpp
   Logger.cpp

clang-tools-extra/trunk/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++ types that can be used to check whether they are
+// convertible between each other for the purposes of code completion ranking
+// without looking at the ASTs. Note that we don't aim to fully mimic the C++
+// conversion rules, merely try to have a model that gives useful improvements
+// to the code completion ranking.
+//
+// We define an encoding of AST types as opaque strings, which can be stored in
+// the index. Similar types (such as `int` and `long`) are folded together,
+// forming equivalence classes with the same encoding.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_EXPECTED_TYPES_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_EXPECTED_TYPES_H
+
+#include "clang/AST/Type.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+class CodeCompletionResult;
+
+namespace clangd {
+/// A representation of a type that can be computed based on clang AST and
+/// compared for equality. The encoding is stable between different ASTs, this
+/// allows the representation to be stored in the index and compared with types
+/// coming from a different AST later.
+/// OpaqueType is a strongly-typedefed std::string, you can get the underlying
+/// string with raw().
+class OpaqueType {
+public:
+  /// Create a type from a code completion result.
+  static llvm::Optional<OpaqueType>
+  fromCompletionResult(ASTContext &Ctx, const CodeCompletionResult &R);
+  /// Construct an instance from a clang::QualType. This is usually a
+  /// PreferredType from a clang's completion context.
+  static llvm::Optional<OpaqueType> fromType(ASTContext &Ctx, QualType Type);
+
+  /// Get the raw byte representation of the type. You can only rely on the
+  /// types being equal iff their raw representation is the same. The particular
+  /// details of the used encoding might change over time and one should not
+  /// rely on it.
+  llvm::StringRef raw() const { return Data; }
+
+  friend bool operator==(const OpaqueType &L, const OpaqueType &R) {
+    return L.Data == R.Data;
+  }
+  friend bool operator!=(const OpaqueType &L, const OpaqueType &R) {
+    return !(L == R);
+  }
+
+private:
+  static llvm::Optional<OpaqueType> encode(ASTContext &Ctx, QualType Type);
+  explicit OpaqueType(std::string Data);
+
+  std::string Data;
+};
+} // namespace clangd
+} // namespace clang
+#endif

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

+#include "ExpectedTypes.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Type.h"
+#include "clang/Index/USRGeneration.h"
+#include "clang/Sema/CodeCompleteConsumer.h"
+#include "llvm/ADT/STLExtras.h"
+
+using namespace llvm;
+
+namespace clang {
+namespace clangd {
+namespace {
+
+static const Type *toEquivClass(ASTContext &Ctx, QualType T) {
+  if (T.isNull() || T->isDependentType())
+    return nullptr;
+  // Drop references, we do not handle reference inits properly anyway.
+  T = T.getCanonicalType().getNonReferenceType();
+  // Numeric types are the simplest case.
+  if (T->isBooleanType())
+    return Ctx.BoolTy.getTypePtr();
+  if (T->isIntegerType() && !T->isEnumeralType())
+    return Ctx.IntTy.getTypePtr(); // All integers are equivalent.
+  if (T->isFloatingType() && !T->isComplexType())
+    return Ctx.FloatTy.getTypePtr(); // All floats are equivalent.
+
+  // Do some simple transformations.
+  if (T->isArrayType()) // Decay arrays to pointers.
+    return Ctx.getPointerType(QualType(T->getArrayElementTypeNoTypeQual(), 0))
+        .getTypePtr();
+  // Drop the qualifiers and return the resulting type.
+  // FIXME: also drop qualifiers from pointer types, e.g. 'const T* => T*'
+  return T.getTypePtr();
+}
+
+static Optional<QualType> typeOfCompletion(const CodeCompletionResult &R) {
+  auto *VD = dyn_cast_or_null<ValueDecl>(R.Declaration);
+  if (!VD)
+    return None; // We handle only variables and functions below.
+  auto T = VD->getType();
+  if (auto FuncT = T->getAs<FunctionType>()) {
+    // 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 FuncT->getReturnType();
+  }
+  return T;
+}
+} // namespace
+
+Optional<OpaqueType> OpaqueType::encode(ASTContext &Ctx, QualType T) {
+  if (T.isNull())
+    return None;
+  const Type *C = toEquivClass(Ctx, T);
+  if (!C)
+    return None;
+  SmallString<128> Encoded;
+  if (index::generateUSRForType(QualType(C, 0), Ctx, Encoded))
+    return None;
+  return OpaqueType(Encoded.str());
+}
+
+OpaqueType::OpaqueType(std::string Data) : Data(std::move(Data)) {}
+
+Optional<OpaqueType> OpaqueType::fromType(ASTContext &Ctx, QualType Type) {
+  return encode(Ctx, Type);
+}
+
+Optional<OpaqueType>
+OpaqueType::fromCompletionResult(ASTContext &Ctx,
+                                 const CodeCompletionResult &R) {
+  auto T = typeOfCompletion(R);
+  if (!T)
+    return None;
+  return encode(Ctx, *T);
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/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
   FSTests.cpp
   FunctionTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp

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

+//===-- ExpectedTypeTest.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 "llvm/ADT/StringRef.h"
+#include "gmock/gmock-matchers.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using ::testing::Field;
+using ::testing::Matcher;
+using ::testing::SizeIs;
+using ::testing::UnorderedElementsAreArray;
+
+class ExpectedTypeConversionTest : public ::testing::Test {
+protected:
+  void build(StringRef Code) {
+    assert(!AST && "AST built twice");
+    AST = TestTU::withCode(Code).build();
+  }
+
+  const ValueDecl *decl(StringRef Name) {
+    return &cast<ValueDecl>(findDecl(*AST, Name));
+  }
+
+  QualType typeOf(StringRef Name) {
+    return decl(Name)->getType().getCanonicalType();
+  }
+
+  /// An overload for convenience.
+  Optional<OpaqueType> fromCompletionResult(const ValueDecl *D) {
+    return OpaqueType::fromCompletionResult(
+        ASTCtx(), CodeCompletionResult(D, CCP_Declaration));
+  }
+
+  /// A set of DeclNames whose type match each other computed by
+  /// OpaqueType::fromCompletionResult.
+  using EquivClass = std::set<std::string>;
+
+  Matcher<std::map<std::string, EquivClass>>
+  ClassesAre(ArrayRef<EquivClass> Classes) {
+    using MapEntry = std::map<std::string, EquivClass>::value_type;
+
+    std::vector<Matcher<MapEntry>> Elements;
+    Elements.reserve(Classes.size());
+    for (auto &Cls : Classes)
+      Elements.push_back(Field(&MapEntry::second, Cls));
+    return UnorderedElementsAreArray(Elements);
+  }
+
+  // Groups \p Decls into equivalence classes based on the result of
+  // 'OpaqueType::fromCompletionResult'.
+  std::map<std::string, EquivClass>
+  buildEquivClasses(ArrayRef<StringRef> DeclNames) {
+    std::map<std::string, EquivClass> Classes;
+    for (StringRef Name : DeclNames) {
+      auto Type = OpaqueType::fromType(ASTCtx(), typeOf(Name));
+      Classes[Type->raw()].insert(Name);
+    }
+    return Classes;
+  }
+
+  ASTContext &ASTCtx() { return AST->getASTContext(); }
+
+private:
+  // Set after calling build().
+  Optional<ParsedAST> AST;
+};
+
+TEST_F(ExpectedTypeConversionTest, BasicTypes) {
+  build(R"cpp(
+    // ints.
+    bool b;
+    int i;
+    unsigned int ui;
+    long long ll;
+
+    // floats.
+    float f;
+    double d;
+
+    // pointers
+    int* iptr;
+    bool* bptr;
+
+    // user-defined types.
+    struct X {};
+    X user_type;
+  )cpp");
+
+  EXPECT_THAT(buildEquivClasses({"b", "i", "ui", "ll", "f", "d", "iptr", "bptr",
+                                 "user_type"}),
+              ClassesAre({{"b"},
+                          {"i", "ui", "ll"},
+                          {"f", "d"},
+                          {"iptr"},
+                          {"bptr"},
+                          {"user_type"}}));
+}
+
+TEST_F(ExpectedTypeConversionTest, ReferencesDontMatter) {
+  build(R"cpp(
+    int noref;
+    int & ref = noref;
+    const int & const_ref = noref;
+    int && rv_ref = 10;
+  )cpp");
+
+  EXPECT_THAT(buildEquivClasses({"noref", "ref", "const_ref", "rv_ref"}),
+              SizeIs(1));
+}
+
+TEST_F(ExpectedTypeConversionTest, ArraysDecay) {
+  build(R"cpp(
+     int arr[2];
+     int (&arr_ref)[2] = arr;
+     int *ptr;
+  )cpp");
+
+  EXPECT_THAT(buildEquivClasses({"arr", "arr_ref", "ptr"}), SizeIs(1));
+}
+
+TEST_F(ExpectedTypeConversionTest, FunctionReturns) {
+  build(R"cpp(
+     int returns_int();
+     int* returns_ptr();
+
+     int int_;
+     int* int_ptr;
+  )cpp");
+
+  OpaqueType IntTy = *OpaqueType::fromType(ASTCtx(), typeOf("int_"));
+  EXPECT_EQ(fromCompletionResult(decl("returns_int")), IntTy);
+
+  OpaqueType IntPtrTy = *OpaqueType::fromType(ASTCtx(), typeOf("int_ptr"));
+  EXPECT_EQ(fromCompletionResult(decl("returns_ptr")), IntPtrTy);
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang