[clangd] Initial implementation of expected types

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.

Reviewers: sammccall, ioeric

Reviewed By: sammccall

Subscribers: malaperle, mgorny, MaskRay, jkorous, arphaman, kadircet, cfe-commits

Differential Revision: https://reviews.llvm.org/D52273

5 files changed, 304 insertions, 0 deletions

diff --git a/clang-tools-extra/clangd/CMakeLists.txt b/clang-tools-extra/clangd/CMakeLists.txt
index bf59eb9782e..2aa975a82bc 100644
--- a/clang-tools-extra/clangd/CMakeLists.txt
+++ b/clang-tools-extra/clangd/CMakeLists.txt
@@ -19,6 +19,7 @@ add_clang_library(clangDaemon
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
+  ExpectedTypes.cpp
   FindSymbols.cpp
   FileDistance.cpp
   FS.cpp
diff --git a/clang-tools-extra/clangd/ExpectedTypes.cpp b/clang-tools-extra/clangd/ExpectedTypes.cpp
new file mode 100644
index 00000000000..5c9cec89c26
--- /dev/null
+++ b/clang-tools-extra/clangd/ExpectedTypes.cpp
@@ -0,0 +1,80 @@
+#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
diff --git a/clang-tools-extra/clangd/ExpectedTypes.h b/clang-tools-extra/clangd/ExpectedTypes.h
new file mode 100644
index 00000000000..2f231283d7d
--- /dev/null
+++ b/clang-tools-extra/clangd/ExpectedTypes.h
@@ -0,0 +1,65 @@
+//===--- 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
diff --git a/clang-tools-extra/unittests/clangd/CMakeLists.txt b/clang-tools-extra/unittests/clangd/CMakeLists.txt
index b6233b07f94..8ac440e444e 100644
--- a/clang-tools-extra/unittests/clangd/CMakeLists.txt
+++ b/clang-tools-extra/unittests/clangd/CMakeLists.txt
@@ -19,6 +19,7 @@ add_extra_unittest(ClangdTests
   ContextTests.cpp
   DexTests.cpp
   DraftStoreTests.cpp
+  ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
diff --git a/clang-tools-extra/unittests/clangd/ExpectedTypeTest.cpp b/clang-tools-extra/unittests/clangd/ExpectedTypeTest.cpp
new file mode 100644
index 00000000000..e739869e437
--- /dev/null
+++ b/clang-tools-extra/unittests/clangd/ExpectedTypeTest.cpp
@@ -0,0 +1,157 @@
+//===-- 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