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