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 FS.cpp Index: clangd/ExpectedTypes.h =================================================================== --- /dev/null +++ clangd/ExpectedTypes.h @@ -0,0 +1,66 @@ +//===--- 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. +// +// 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. +// Unfortunately, we do not have ASTs for index-based completion, so we have use +// a stable encoding for the C++ types and map them into equivalence classes +// based on convertibility. +//===----------------------------------------------------------------------===// +#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. +class OpaqueType { +public: + /// Create a type from a code completion result. + static llvm::Optional + fromCompletionResult(ASTContext &Ctx, const CodeCompletionResult &R); + /// Create a type from a preferred type provided by clang for the code + /// completion context. + static llvm::Optional fromPreferredType(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 rawStr() 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 encode(ASTContext &Ctx, QualType Type); + explicit OpaqueType(std::string Data); + + std::string Data; +}; +} // namespace clangd +} // namespace clang +#endif Index: clangd/ExpectedTypes.cpp =================================================================== --- /dev/null +++ clangd/ExpectedTypes.cpp @@ -0,0 +1,78 @@ +#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" + +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->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 llvm::Optional +typeOfCompletion(const CodeCompletionResult &R) { + auto *VD = llvm::dyn_cast_or_null(R.Declaration); + if (!VD) + return llvm::None; // We handle only variables and functions below. + auto T = VD->getType(); + if (auto FuncT = T->getAs()) { + // 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 + +llvm::Optional OpaqueType::encode(ASTContext &Ctx, QualType T) { + if (T.isNull()) + return llvm::None; + const Type *C = toEquivClass(Ctx, T); + if (!C) + return llvm::None; + llvm::SmallString<128> Encoded; + if (index::generateUSRForType(QualType(C, 0), Ctx, Encoded)) + return llvm::None; + return OpaqueType(Encoded.str()); +} + +OpaqueType::OpaqueType(std::string Data) : Data(std::move(Data)) {} + +llvm::Optional OpaqueType::fromPreferredType(ASTContext &Ctx, + QualType Type) { + return encode(Ctx, Type); +} + +llvm::Optional +OpaqueType::fromCompletionResult(ASTContext &Ctx, + const CodeCompletionResult &R) { + auto T = typeOfCompletion(R); + if (!T) + return llvm::None; + return encode(Ctx, *T); +} + +} // namespace clangd +} // namespace clang Index: unittests/clangd/CMakeLists.txt =================================================================== --- unittests/clangd/CMakeLists.txt +++ unittests/clangd/CMakeLists.txt @@ -19,6 +19,7 @@ ContextTests.cpp DexTests.cpp DraftStoreTests.cpp + ExpectedTypeTest.cpp FileDistanceTests.cpp FileIndexTests.cpp FindSymbolsTests.cpp Index: unittests/clangd/ExpectedTypeTest.cpp =================================================================== --- /dev/null +++ unittests/clangd/ExpectedTypeTest.cpp @@ -0,0 +1,198 @@ +//===-- 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" + +namespace clang { +namespace clangd { +namespace { + +using ::testing::Field; +using ::testing::Matcher; +using ::testing::SizeIs; +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(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 AST; +}; + +class ConvertibleToMatcher + : public ::testing::MatcherInterface { + ASTContext &Ctx; + QualType To; + OpaqueType PreferredType; + +public: + ConvertibleToMatcher(ASTContext &Ctx, QualType To) + : Ctx(Ctx), To(To.getCanonicalType()), + PreferredType(*OpaqueType::fromPreferredType(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 = OpaqueType::fromCompletionResult( + Ctx, CodeCompletionResult(V, CCP_Declaration)); + + bool Matched = PreferredType == ConvertibleTo; + if (L->IsInterested()) + *L << "Types of 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 isConvertibleTo(QualType To) { + return ::testing::MakeMatcher(new ConvertibleToMatcher(ASTCtx(), To)); + } + + // A set of DeclNames whose type match each other computed by + // OpaqueType::fromCompletionResult. + using EquivClass = std::set; + + Matcher> + ClassesAre(llvm::ArrayRef Classes) { + using MapEntry = std::map::value_type; + + std::vector> 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 + buildEquivClasses(llvm::ArrayRef Decls) { + std::map Classes; + for (auto *D : Decls) { + auto Type = OpaqueType::fromCompletionResult( + ASTCtx(), CodeCompletionResult(D, CCP_Declaration)); + Classes[Type->rawStr()].insert(D->getNameAsString()); + } + return Classes; + } +}; + +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"); + + const ValueDecl *Decls[] = {decl("b"), decl("i"), decl("ui"), + decl("ll"), decl("f"), decl("d"), + decl("iptr"), decl("bptr"), decl("user_type")}; + EXPECT_THAT(buildEquivClasses(Decls), 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"); + + const ValueDecl *Decls[] = {decl("noref"), decl("ref"), decl("const_ref"), + decl("rv_ref")}; + EXPECT_THAT(buildEquivClasses(Decls), SizeIs(1)); +} + +TEST_F(ExpectedTypeConversionTest, ArraysDecay) { + build(R"cpp( + int arr[2]; + int (&arr_ref)[2] = arr; + int *ptr; + )cpp"); + + const ValueDecl *Decls[] = {decl("arr"), decl("arr_ref"), decl("ptr")}; + EXPECT_THAT(buildEquivClasses(Decls), SizeIs(1)); +} + +TEST_F(ExpectedTypeConversionTest, FunctionReturns) { + build(R"cpp( + int returns_int(); + int* returns_ptr(); + + int int_; + int* int_ptr; + )cpp"); + + const ValueDecl *RetInt = decl("returns_int"); + const ValueDecl *RetPtr = decl("returns_ptr"); + + QualType IntTy = typeOf("int_"); + QualType IntPtrTy = typeOf("int_ptr"); + + EXPECT_THAT(RetInt, isConvertibleTo(IntTy)); + EXPECT_THAT(RetPtr, isConvertibleTo(IntPtrTy)); + + EXPECT_THAT(RetInt, Not(isConvertibleTo(IntPtrTy))); + EXPECT_THAT(RetPtr, Not(isConvertibleTo(IntTy))); +} + + +} // namespace +} // namespace clangd +} // namespace clang