diff --git a/llvm/include/llvm/ADT/IntrusiveVariant.h b/llvm/include/llvm/ADT/IntrusiveVariant.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/IntrusiveVariant.h @@ -0,0 +1,463 @@ +//===- IntrusiveVariant.h - Compact type safe union -------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file provides IntrusiveVariant, a class template modeled in the spirit +// of std::variant, but leveraging the "common initial sequence" rule for union +// members to store the runtime tag at the beginning of the IntrusiveVariant's +// alternative types, allowing for it to be packed more efficiently into bits +// that would otherwise be used for padding. +// +// However, this requires several restrictions be placed on valid alternative +// types. All alternative types of an IntrusiveVariant must: +// +// * Be standard-layout. This implies (among other things): +// * All non-static data members must have the same access control. +// * All non-static data members must be declared in only one class in the +// inheritence hierarchy. +// * No virtual methods. +// * Begin their class definition by invoking the +// DECLARE_INTRUSIVE_ALTERNATIVE macro. This declares a member named +// `IntrusiveVariantTagMember` which must not be referenced outside of the +// implementation of IntrusiveVariant, and declares some `friend` types to +// make the tag accessible to the implementation. +// +// Additionally, some features were omitted that are present in the C++17 +// std::variant to keep the code simpler: +// +// * All alternative types must be trivially-destructible. +// * All copy/move constructors and assignment operators for the variant are +// disabled if any type is not trivially-constructible and/or +// trivially-copyable, respectively. +// * All alternative types must be unique, and cannot be referred to by index. +// * No equivalent to std::monostate. An instantiation must have at least +// IntrusiveVariant::MinNumberOfAlternatives alternatives. +// +// If a use case for the above materializes these can always be added +// retroactively. +// +// Example: +// +// class AltInt { +// DECLARE_INTRUSIVE_ALTERNATIVE +// int Int; +// +// public: +// AltInt() : Int(0) {} +// AltInt(int Int) : Int(Int) {} +// int getInt() const { return Int; } +// void setInt(int Int) { this->Int = Int; } +// }; +// +// class AltDouble { +// DECLARE_INTRUSIVE_ALTERNATIVE +// double Double; +// +// public: +// AltDouble(double Double) : Double(Double) {} +// double getDouble() const { return Double; } +// void setDouble(double Double) { this->Double = Double; } +// }; +// +// class AltComplexInt { +// DECLARE_INTRUSIVE_ALTERNATIVE +// int Real; +// int Imag; +// +// public: +// AltComplexInt(int Real, int Imag) : Real(Real), Imag(Imag) {} +// int getReal() const { return Real; } +// void setReal(int Real) { this->Real = Real; } +// int getImag() const { return Imag; } +// void setImag(int Imag) { this->Imag = Imag; } +// }; +// +// TEST(VariantTest, HeaderExample) { +// using MyVariant = IntrusiveVariant; +// +// MyVariant DefaultConstructedVariant; +// ASSERT_TRUE(DefaultConstructedVariant.holdsAlternative()); +// ASSERT_EQ(DefaultConstructedVariant.get().getInt(), 0); +// MyVariant Variant{in_place_type_t{}, 4, 2}; +// ASSERT_TRUE(Variant.holdsAlternative()); +// int NonSense = visit( +// makeVisitor( +// [](AltInt &AI) { return AI.getInt(); }, +// [](AltDouble &AD) { return static_cast(AD.getDouble()); }, +// [](AltComplexInt &ACI) { return ACI.getReal() + ACI.getImag(); }), +// Variant); +// ASSERT_EQ(NonSense, 6); +// Variant.emplace(2.0); +// ASSERT_TRUE(Variant.holdsAlternative()); +// Variant.get().setDouble(3.0); +// AltDouble AD = Variant.get(); +// double D = AD.getDouble(); +// ASSERT_EQ(D, 3.0); +// Variant.emplace(4, 5); +// ASSERT_EQ(Variant.get().getReal(), 4); +// ASSERT_EQ(Variant.get().getImag(), 5); +// } +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_INTRUSIVEVARIANT_H +#define LLVM_ADT_INTRUSIVEVARIANT_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/VariantTraits.h" +#include "llvm/Support/ErrorHandling.h" +#include +#include +#include + +namespace llvm { + +template class IntrusiveVariant; + +/// Helper to get the number of alternative types of a (possibly cv-qualified) +/// IntrusiveVariant type as a constexpr. See std::variant_size. +template +struct IntrusiveVariantSize : IntrusiveVariantSize> {}; +template +struct IntrusiveVariantSize> + : std::integral_constant {}; + +/// Simple value type which must be the first member of all alternative types +/// of an IntrusiveVariant. See DECLARE_INTRUSIVE_ALTERNATIVE. +/// +/// The internal implementation assumes this is layout-compatible with the +/// "common initial sequence" of all alternative types contained in the private +/// union of the IntrusiveVariant. +struct IntrusiveVariantTag { + uint8_t Index = std::numeric_limits::max(); + IntrusiveVariantTag() {} + IntrusiveVariantTag(uint8_t Index) : Index(Index) {} +}; + +/// A helper macro to add the declarations needed to use a type as an +/// alternative for IntrusiveVariant. Must be the first declaration of the +/// class. +#define DECLARE_INTRUSIVE_ALTERNATIVE \ + ::llvm::IntrusiveVariantTag IntrusiveVariantTagMember; \ + template friend class ::llvm::IntrusiveVariant; \ + template \ + friend union ::llvm::detail::UnionImpl; + +namespace detail { +// This struct is used to access the intrusive tag of the alternative types. +// +// All such types must be have an initial sequence which is layout-compatible +// with this struct or the access causes undefined behavior. +struct CommonInitialSequenceT { + IntrusiveVariantTag Tag; +}; + +// The inner implementation of the "type safe union". Members are only +// accessible directly via an Index, so IntrusiveVariant must use indexOf to +// convert a pair of T and Ts... into an index. +// +// Effectively implemented as a "linked list" of recursively defined union +// templates. This is the recursive portion of the definition. +// +// We use in_place_index_t here both to disambiguate the constructor and to make +// defining the overload set for getMember more natural. +template union UnionImpl { + using TailT = UnionImpl; + HeadT Head; + TailT Tail; + HeadT &getMember(in_place_index_t) { return Head; } + const HeadT &getMember(in_place_index_t) const { return Head; } + template decltype(auto) getMember(in_place_index_t) { + return Tail.getMember(in_place_index); + } + template decltype(auto) getMember(in_place_index_t) const { + return Tail.getMember(in_place_index); + } + template + UnionImpl(in_place_index_t, ArgTs &&...Args) { + new (&Head) HeadT(std::forward(Args)...); + Head.IntrusiveVariantTagMember.Index = Index; + } + template + UnionImpl(in_place_index_t, ArgTs &&...Args) { + new (&Tail) TailT(in_place_index_t{}, std::forward(Args)...); + } + UnionImpl(const UnionImpl &) = default; + UnionImpl(UnionImpl &&) = default; + UnionImpl &operator=(const UnionImpl &) = default; + UnionImpl &operator=(UnionImpl &&) = default; + // This is safe, assuming the member types are all trivially destructible. + ~UnionImpl() = default; +}; +// The base case for the above, i.e. when the tail pack is empty. This is the +// "(cons head nil)" of the linked list. +template union UnionImpl { + HeadT Head; + HeadT &getMember(in_place_index_t) { return Head; } + const HeadT &getMember(in_place_index_t) const { return Head; } + template + UnionImpl(in_place_index_t, ArgTs &&...Args) { + new (&Head) HeadT(std::forward(Args)...); + Head.IntrusiveVariantTagMember.Index = Index; + } + UnionImpl(const UnionImpl &) = default; + UnionImpl(UnionImpl &&) = default; + UnionImpl &operator=(const UnionImpl &) = default; + UnionImpl &operator=(UnionImpl &&) = default; + // This is safe, assuming the member types are all trivially destructible. + ~UnionImpl() = default; +}; +} // end namespace detail + +template +struct variant_traits_detail::VariantTraits> { + static constexpr size_t numAlts() { return sizeof...(Ts); } + static constexpr size_t getIndex(const IntrusiveVariant &Variant) { + return Variant.index(); + } + template + static constexpr decltype(auto) getAlt(VariantT &&Variant) { + return std::forward(Variant).template getAlt(); + } +}; + +/// A class template modeled in the spirit of std::variant, but leveraging the +/// "common initial sequence" rule for union members to store the runtime tag +/// at the beginning of each variant alternative itself, allowing for it to be +/// packed more efficiently into bits that would otherwise be used for padding. +template class IntrusiveVariant { +public: + /// The static minimum number of alternative types supported for an + /// instantiation of IntrusiveVariant. + static constexpr size_t MinNumberOfAlternatives = 1; + +private: + static_assert(llvm::conjunction...>::value, + "IntrusiveVariant alternatives must be standard-layout."); + static_assert( + llvm::conjunction...>::value, + "IntrusiveVariant alternatives must be trivially-destructible."); + template static constexpr bool tagIsFirstMember() { + constexpr bool IsFirstMember[] = { + !offsetof(Us, IntrusiveVariantTagMember)...}; + for (size_t I = 0; I < sizeof...(Us); ++I) + if (!IsFirstMember[I]) + return false; + return true; + } + static_assert( + tagIsFirstMember() && + llvm::conjunction< + std::is_same...>::value, + "IntrusiveVariant alternatives' class definition must begin with " + "DECLARE_INTRUSIVE_ALTERNATIVE"); + static_assert( + TypesAreDistinct{}, + "Repeated alternative types in IntrusiveVariant are not allowed."); + + friend struct variant_traits_detail::VariantTraits; + + // Alias for the UnionImpl of this IntrusiveVariant. + using UnionT = detail::UnionImpl<0, Ts...>; + // Helper to get the in_place_index_t for T in Ts... + template + using InPlaceIndexT = in_place_index_t{}>; + // Helper to check if a type is in the set Ts... + template using IsAlternativeType = llvm::is_one_of; + + // The only data member of IntrusiveVariant, meaning the variant is the same + // size and has the same alignment requirements as the union of all of its + // alternative types. + union { + detail::CommonInitialSequenceT CommonInitialSequence; + UnionT Union; + }; + + // Returns the current dynamic index of this variant. + size_t index() const { return CommonInitialSequence.Tag.Index; } + + // Convenience methods to get the union member for an alternative type T. + template T &getAlt() { + return Union.getMember(InPlaceIndexT{}); + } + template const T &getAlt() const { + return Union.getMember(InPlaceIndexT{}); + } + template auto &getAlt() { + return Union.getMember(in_place_index); + } + template const auto &getAlt() const { + return Union.getMember(in_place_index); + } + +public: + /// A default constructed IntrusiveVariant holds a default constructed value + /// of its first alternative. Only enabled if the first alternative has a + /// default constructor. + template >{}, + typename std::enable_if_t = 0> + constexpr IntrusiveVariant() : Union(in_place_index_t<0>{}) {} + /// The forwarding constructor requires a disambiguation tag + /// in_place_type_t, and creates an IntrusiveVariant holding the + /// alternative T constructed with the constructor arguments Args... + template {}, int> = 0, + typename... ArgTs> + explicit constexpr IntrusiveVariant(in_place_type_t, ArgTs &&...Args) + : Union(InPlaceIndexT{}, std::forward(Args)...) {} + /// Converting constructor from alternative types. + template {}, int> = 0> + constexpr IntrusiveVariant(T &&Alt) + : Union(InPlaceIndexT{}, std::forward(Alt)) {} + IntrusiveVariant(const IntrusiveVariant &) = default; + IntrusiveVariant(IntrusiveVariant &&) = default; + ~IntrusiveVariant() = default; + IntrusiveVariant &operator=(const IntrusiveVariant &) = default; + IntrusiveVariant &operator=(IntrusiveVariant &&) = default; + /// Replaces the held value with a new value of alternative type T in-place, + /// constructing the new value with constructor arguments Args... + /// + /// Returns the newly constructed alternative type value. + template T &emplace(ArgTs &&...Args) { + new (&Union) UnionT(InPlaceIndexT{}, std::forward(Args)...); + return Union.getMember(InPlaceIndexT{}); + } + /// Check if this variant holds a value of the given alternative type T. + template constexpr bool holdsAlternative() const { + return index() == FirstIndexOfType(); + } + /// Reads the value of alternative type T. + /// + /// Behavior undefined if this does not hold a value of alternative type T. + template constexpr T &get() { + assert(holdsAlternative()); + return getAlt(); + } + /// Reads the value of alternative type T. + /// + /// Behavior undefined if this does not hold a value of alternative type T. + template constexpr const T &get() const { + assert(holdsAlternative()); + return getAlt(); + } + /// Obtains a pointer to the value of alternative type T if this holds a + /// value of alternative type T. Otherwise, returns nullptr. + template constexpr T *getIf() { + if (holdsAlternative()) + return &getAlt(); + return nullptr; + } + /// Obtains a pointer to the value of alternative type T if this holds a + /// value of alternative type T. Otherwise, returns nullptr. + template constexpr const T *getIf() const { + if (holdsAlternative()) + return &getAlt(); + return nullptr; + } + + /// Equality operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T != U, returns false. + /// Otherwise, returns LHS.get() == RHS.get(). + friend constexpr bool operator==(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() != RHS.index()) + return false; + return variant_traits_detail::visitSameAlt(std::equal_to<>{}, LHS, RHS); + } + + /// Inequality operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T != U, returns true. + /// Otherwise, returns LHS.get() != RHS.get(). + friend constexpr bool operator!=(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() != RHS.index()) + return true; + return variant_traits_detail::visitSameAlt(std::not_equal_to<>{}, LHS, RHS); + } + + /// Less-than operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T precedes U in Ts..., returns true. + /// If U precedes T in Ts..., returns false. + /// Otherwise, returns LHS.get() < RHS.get(). + friend constexpr bool operator<(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() < RHS.index()) + return true; + if (RHS.index() > LHS.index()) + return false; + return variant_traits_detail::visitSameAlt(std::less<>{}, LHS, RHS); + } + + /// Greater-than operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T precedes U in Ts..., returns false. + /// If U precedes T in Ts..., returns true. + /// Otherwise, returns LHS.get() > RHS.get(). + friend constexpr bool operator>(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() < RHS.index()) + return false; + if (RHS.index() > LHS.index()) + return true; + return variant_traits_detail::visitSameAlt(std::greater<>{}, LHS, RHS); + } + + /// Less-equal operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T precedes U in Ts..., returns true. + /// If U precedes T in Ts..., returns false. + /// Otherwise, returns LHS.get() <= RHS.get(). + friend constexpr bool operator<=(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() < RHS.index()) + return true; + if (RHS.index() > LHS.index()) + return false; + return variant_traits_detail::visitSameAlt(std::less_equal<>{}, LHS, RHS); + } + + /// Greater-equal operator. + /// + /// The alternative types held by LHS and RHS are T and U, respectively; then: + /// + /// If T precedes U in Ts..., returns false. + /// If U precedes T in Ts..., returns true. + /// Otherwise, returns LHS.get() >= RHS.get(). + friend constexpr bool operator>=(const IntrusiveVariant &LHS, + const IntrusiveVariant &RHS) { + if (LHS.index() < RHS.index()) + return false; + if (RHS.index() > LHS.index()) + return true; + return variant_traits_detail::visitSameAlt(std::greater_equal<>{}, LHS, + RHS); + } + + /// Enabled if all alternative types overload hash_value. + friend hash_code hash_value(const IntrusiveVariant &IV) { + return visit( + [&](auto &&Alt) { return hash_combine(IV.index(), hash_value(Alt)); }, + IV); + } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_INTRUSIVEVARIANT_H diff --git a/llvm/include/llvm/ADT/STLForwardCompat.h b/llvm/include/llvm/ADT/STLForwardCompat.h --- a/llvm/include/llvm/ADT/STLForwardCompat.h +++ b/llvm/include/llvm/ADT/STLForwardCompat.h @@ -16,10 +16,31 @@ #ifndef LLVM_ADT_STLFORWARDCOMPAT_H #define LLVM_ADT_STLFORWARDCOMPAT_H +#include #include namespace llvm { +//===----------------------------------------------------------------------===// +// Features from C++20 +//===----------------------------------------------------------------------===// + +template +struct remove_cvref // NOLINT(readability-identifier-naming) +{ + using type = std::remove_cv_t>; +}; + +template +using remove_cvref_t // NOLINT(readability-identifier-naming) + = typename llvm::remove_cvref::type; + +template +struct type_identity // NOLINT(readability-identifier-naming) +{ + using type = T; +}; + //===----------------------------------------------------------------------===// // Features from C++17 //===----------------------------------------------------------------------===// @@ -56,26 +77,32 @@ { explicit in_place_type_t() = default; }; +/// \warning This must not be odr-used, as it cannot be made \c inline in C++14. +template +constexpr in_place_type_t + in_place_type; // NOLINT(readability-identifier-naming) template struct in_place_index_t // NOLINT(readability-identifier-naming) { explicit in_place_index_t() = default; }; +/// \warning This must not be odr-used, as it cannot be made \c inline in C++14. +template +constexpr in_place_index_t + in_place_index; // NOLINT(readability-identifier-naming) -//===----------------------------------------------------------------------===// -// Features from C++20 -//===----------------------------------------------------------------------===// - -template -struct remove_cvref // NOLINT(readability-identifier-naming) -{ - using type = std::remove_cv_t>; -}; - -template -using remove_cvref_t // NOLINT(readability-identifier-naming) - = typename llvm::remove_cvref::type; +/// Implementation of std::experimental::make_array. Should be deleted in favor +/// of the C++17 deduction guide for std::array. +template +static constexpr auto +make_array(ArgTs &&...Args) // NOLINT(readability-identifier-naming) + -> std::array{}, + std::common_type, + type_identity>::type, + sizeof...(ArgTs)> { + return {std::forward(Args)...}; +} } // namespace llvm diff --git a/llvm/include/llvm/ADT/VariantTraits.h b/llvm/include/llvm/ADT/VariantTraits.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/VariantTraits.h @@ -0,0 +1,136 @@ +//===- VariantTraits.h - Common interfaces for variant-like types --C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains common interfaces for variant-like types. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/STLExtras.h" + +#ifndef LLVM_ADT_VARIANTTRAITS_H +#define LLVM_ADT_VARIANTTRAITS_H + +namespace llvm { + +namespace variant_traits_detail { + +template struct VariantTraits { + // static constexpr size_t numAlts(); + // static constexpr size_t getIndex(const VariantT &); + // template + // static constexpr decltype(auto) getAlt(VariantT &&Variant); +}; + +template using Traits = struct VariantTraits>; + +template +static constexpr decltype(auto) thunkSameAlt(VisitorT &&Visitor, + VariantTs &&...Variants) { + return std::forward(Visitor)( + Traits::template getAlt( + std::forward(Variants))...); +} + +template +static constexpr auto +visitSameAltImpl(size_t Index, std::index_sequence, + VisitorT &&Visitor, HeadVariantT &&HeadVariant, + TailVariantTs &&...TailVariants) { + constexpr auto Thunks = make_array( + thunkSameAlt...); + return Thunks[Index](std::forward(Visitor), + std::forward(HeadVariant), + std::forward(TailVariants)...); +} + +template +static constexpr decltype(auto) visitSameAlt(VisitorT &&Visitor, + HeadVariantT &&HeadVariant, + TailVariantTs &&...TailVariants) { + static_assert(conjunction, + remove_cvref_t>...>{}, + "all IntrusiveVariant arguments to visitSameAlt must " + "be of the same type"); + return visitSameAltImpl( + Traits::getIndex(HeadVariant), + std::make_index_sequence::numAlts()>{}, + std::forward(Visitor), std::forward(HeadVariant), + std::forward(TailVariants)...); +} +template struct Thunk { + template + inline static constexpr decltype(auto) thunk(VisitorT &&Visitor, + VariantTs &&...Variants) { + return std::forward(Visitor)( + Traits::template getAlt( + std::forward(Variants))...); + } +}; +template +static constexpr auto makeThunkForSequence(std::index_sequence) { + return Thunk::template thunk; +} + +template +static constexpr auto +accumulateCartesianProductThunks(std::index_sequence) { + return makeThunkForSequence( + std::index_sequence{}); +} +template +static constexpr auto +accumulateCartesianProductThunks(std::index_sequence, + std::index_sequence, + TailSequenceTs... Tail) { + return make_array(accumulateCartesianProductThunks( + std::index_sequence{}, Tail...)...); +} +template +static constexpr auto makeThunkMatrix() { + return accumulateCartesianProductThunks( + std::index_sequence<>{}, + std::make_index_sequence::numAlts()>{}...); +} + +template +static constexpr const ThunkT &indexThunkMatrix(const ThunkT &Thunk) { + return Thunk; +} +template +static constexpr auto &&indexThunkMatrix(const ThunkMatrixT &ThunkMatrix, + size_t HeadIndex, + TailIndexTs... TailIndexes) { + return indexThunkMatrix(ThunkMatrix[HeadIndex], TailIndexes...); +} +} // namespace variant_traits_detail + +/// Invokes the provided Visitor using overload resolution based on the +/// dynamic alternative type held in Variant. See std::variant. +/// +/// The return type is decltype(Visitor(Variant.get())) for all T in the +/// alternative types Ts... of Variant. This must be a valid expression of the +/// same type and value category for all Ts... +template +constexpr decltype(auto) visit(VisitorT &&Visitor, VariantTs &&...Variants) { + constexpr auto ThunkMatrix = + variant_traits_detail::makeThunkMatrix(); + const auto &Thunk = variant_traits_detail::indexThunkMatrix( + ThunkMatrix, + variant_traits_detail::VariantTraits>::getIndex( + std::forward(Variants))...); + return Thunk(std::forward(Visitor), + std::forward(Variants)...); +} + +} // namespace llvm + +#endif // LLVM_ADT_VARIANTTRAITS_H diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -41,6 +41,7 @@ IntEqClassesTest.cpp IntervalMapTest.cpp IntrusiveRefCntPtrTest.cpp + IntrusiveVariantTest.cpp IteratorTest.cpp MappedIteratorTest.cpp MapVectorTest.cpp diff --git a/llvm/unittests/ADT/IntrusiveVariantTest.cpp b/llvm/unittests/ADT/IntrusiveVariantTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/ADT/IntrusiveVariantTest.cpp @@ -0,0 +1,260 @@ +//===- llvm/unittest/Support/AnyTest.cpp - Any tests ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/IntrusiveVariant.h" +#include "gtest/gtest.h" +#include + +using namespace llvm; + +namespace { + +class A { + DECLARE_INTRUSIVE_ALTERNATIVE +}; + +class B { + DECLARE_INTRUSIVE_ALTERNATIVE +}; + +TEST(IntrusiveVariantTest, SingleAlternative) { IntrusiveVariant V; } + +TEST(IntrusiveVariantTest, ZeroArgConstructionAndAssignment) { + IntrusiveVariant V; + ASSERT_TRUE(V.holdsAlternative()); + visit(makeVisitor([](A) {}, [](B) { FAIL(); }), V); + visit(makeVisitor([](B) { FAIL(); }, [](A) {}), V); + visit(makeVisitor([](A &) {}, [](B &) { FAIL(); }), V); + visit(makeVisitor([](A) {}, [](B &) { FAIL(); }), V); + visit(makeVisitor([](A &) {}, [](B) { FAIL(); }), V); + visit(makeVisitor([](auto &&) {}), V); + + V.emplace(); + ASSERT_TRUE(V.holdsAlternative()); + + IntrusiveVariant W{V}; + ASSERT_TRUE(W.holdsAlternative()); + + const IntrusiveVariant X{V}; + ASSERT_TRUE(X.holdsAlternative()); +} + +#define DECLARE_ALT(NAME, TYPE) \ + class NAME { \ + DECLARE_INTRUSIVE_ALTERNATIVE \ + TYPE Val; \ + \ + public: \ + NAME(TYPE Val) : Val(Val) {} \ + TYPE getVal() const { return Val; } \ + friend bool operator==(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() == RHS.getVal(); \ + } \ + friend bool operator!=(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() != RHS.getVal(); \ + } \ + friend bool operator<(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() < RHS.getVal(); \ + } \ + friend bool operator>(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() > RHS.getVal(); \ + } \ + friend bool operator<=(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() <= RHS.getVal(); \ + } \ + friend bool operator>=(const NAME &LHS, const NAME &RHS) { \ + return LHS.getVal() >= RHS.getVal(); \ + } \ + } +DECLARE_ALT(I, int); +DECLARE_ALT(F, float); +DECLARE_ALT(D, double); + +TEST(IntrusiveVariantTest, ConstructionAndAssignment) { + IntrusiveVariant V{in_place_type, 2.0f}; + visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); }, + [](D) { FAIL(); }), + V); + IntrusiveVariant W{V}; + visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); }, + [](D) { FAIL(); }), + W); + W.emplace(42); + visit(makeVisitor([](I X) { EXPECT_EQ(X.getVal(), 42); }, [](F) { FAIL(); }, + [](D) { FAIL(); }), + W); + W = V; + visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); }, + [](D) { FAIL(); }), + W); +} + +TEST(IntrusiveVariantTest, Comparison) { + IntrusiveVariant V{in_place_type_t{}, 1}; + IntrusiveVariant W{in_place_type, 2.0f}; + IntrusiveVariant X{in_place_type, 2.0f}; + IntrusiveVariant Y{in_place_type, 3.0f}; + IntrusiveVariant Z{in_place_type_t{}, 3.0}; + EXPECT_NE(V, W); + EXPECT_LT(V, W); + EXPECT_LE(V, W); + EXPECT_GT(W, V); + EXPECT_GE(W, V); + EXPECT_EQ(W, X); + EXPECT_LE(W, X); + EXPECT_GE(W, X); + EXPECT_NE(W, Y); + EXPECT_NE(X, Y); + EXPECT_LT(X, Y); + EXPECT_LE(X, Y); + EXPECT_GT(Y, X); + EXPECT_GE(Y, X); + EXPECT_NE(Y, Z); + std::swap(X, Y); + EXPECT_EQ(W, Y); + EXPECT_NE(W, X); +} + +TEST(IntrusiveVariantTest, IntrusiveVariantSize) { + constexpr auto One = IntrusiveVariantSize>{}; + EXPECT_EQ(One, 1u); + constexpr auto Two = IntrusiveVariantSize>{}; + EXPECT_EQ(Two, 2u); + constexpr auto Three = IntrusiveVariantSize>{}; + EXPECT_EQ(Three, 3u); +} + +TEST(IntrusiveVariantTest, HoldsAlternative) { + IntrusiveVariant V{in_place_type_t{}, 2.0}; + EXPECT_FALSE(V.holdsAlternative()); + EXPECT_FALSE(V.holdsAlternative()); + EXPECT_TRUE(V.holdsAlternative()); + V.emplace(1); + EXPECT_TRUE(V.holdsAlternative()); + EXPECT_FALSE(V.holdsAlternative()); + EXPECT_FALSE(V.holdsAlternative()); + const IntrusiveVariant C{in_place_type, 2.0f}; + EXPECT_FALSE(C.holdsAlternative()); + EXPECT_TRUE(C.holdsAlternative()); + EXPECT_FALSE(C.holdsAlternative()); +} + +TEST(IntrusiveVariantTest, Get) { + IntrusiveVariant V{in_place_type_t{}, 2.0}; + EXPECT_EQ(V.get(), D{2.0}); + EXPECT_EQ(V.get(), *V.getIf()); + EXPECT_EQ(&V.get(), V.getIf()); + V.emplace(1); + EXPECT_EQ(V.get(), I{1}); + EXPECT_EQ(V.get(), *V.getIf()); + EXPECT_EQ(&V.get(), V.getIf()); + const IntrusiveVariant C{in_place_type_t{}, 2.0}; + EXPECT_EQ(C.get(), D{2.0}); + EXPECT_EQ(C.get(), *C.getIf()); + EXPECT_EQ(&C.get(), C.getIf()); +} + +TEST(IntrusiveVariantTest, GetIf) { + IntrusiveVariant V{in_place_type_t{}, 2.0}; + EXPECT_EQ(V.getIf(), nullptr); + EXPECT_EQ(V.getIf(), nullptr); + EXPECT_NE(V.getIf(), nullptr); + V.emplace(1); + EXPECT_NE(V.getIf(), nullptr); + EXPECT_EQ(V.getIf(), nullptr); + EXPECT_EQ(V.getIf(), nullptr); + const IntrusiveVariant C{in_place_type, 2.0f}; + EXPECT_EQ(C.getIf(), nullptr); + EXPECT_NE(C.getIf(), nullptr); + EXPECT_EQ(C.getIf(), nullptr); +} + +struct IntA { + DECLARE_INTRUSIVE_ALTERNATIVE + int Val; + IntA(int Val) : Val(Val) {} + friend hash_code hash_value(const IntA &IA) { return hash_value(IA.Val); } +}; + +struct IntB { + DECLARE_INTRUSIVE_ALTERNATIVE + int Val; + IntB(int Val) : Val(Val) {} + friend hash_code hash_value(const IntB &IB) { return hash_value(IB.Val); } +}; + +TEST(IntrusiveVariantTest, HashValue) { + IntrusiveVariant ATwo{in_place_type_t{}, 2}; + IntrusiveVariant AThree{in_place_type_t{}, 3}; + IntrusiveVariant BTwo{in_place_type_t{}, 2}; + EXPECT_EQ(hash_value(ATwo), hash_value(ATwo)); + EXPECT_NE(hash_value(ATwo), hash_value(AThree)); + EXPECT_NE(hash_value(ATwo), hash_value(BTwo)); +} + +class AltInt { + DECLARE_INTRUSIVE_ALTERNATIVE + int Int; + +public: + AltInt() : Int(0) {} + AltInt(int Int) : Int(Int) {} + int getInt() const { return Int; } + void setInt(int Int) { this->Int = Int; } +}; + +class AltDouble { + DECLARE_INTRUSIVE_ALTERNATIVE + double Double; + +public: + AltDouble(double Double) : Double(Double) {} + double getDouble() const { return Double; } + void setDouble(double Double) { this->Double = Double; } +}; + +class AltComplexInt { + DECLARE_INTRUSIVE_ALTERNATIVE + int Real; + int Imag; + +public: + AltComplexInt(int Real, int Imag) : Real(Real), Imag(Imag) {} + int getReal() const { return Real; } + void setReal(int Real) { this->Real = Real; } + int getImag() const { return Imag; } + void setImag(int Imag) { this->Imag = Imag; } +}; + +TEST(IntrusiveVariantTest, HeaderExample) { + using MyVariant = IntrusiveVariant; + + MyVariant DefaultConstructedVariant; + ASSERT_TRUE(DefaultConstructedVariant.holdsAlternative()); + ASSERT_EQ(DefaultConstructedVariant.get().getInt(), 0); + MyVariant Variant{in_place_type_t{}, 4, 2}; + ASSERT_TRUE(Variant.holdsAlternative()); + int NonSense = visit( + makeVisitor( + [](AltInt &AI) { return AI.getInt(); }, + [](AltDouble &AD) { return static_cast(AD.getDouble()); }, + [](AltComplexInt &ACI) { return ACI.getReal() + ACI.getImag(); }), + Variant); + ASSERT_EQ(NonSense, 6); + Variant.emplace(2.0); + ASSERT_TRUE(Variant.holdsAlternative()); + Variant.get().setDouble(3.0); + AltDouble AD = Variant.get(); + double D = AD.getDouble(); + ASSERT_EQ(D, 3.0); + Variant.emplace(4, 5); + ASSERT_EQ(Variant.get().getReal(), 4); + ASSERT_EQ(Variant.get().getImag(), 5); +} + +} // anonymous namespace diff --git a/llvm/unittests/ADT/STLForwardCompatTest.cpp b/llvm/unittests/ADT/STLForwardCompatTest.cpp --- a/llvm/unittests/ADT/STLForwardCompatTest.cpp +++ b/llvm/unittests/ADT/STLForwardCompatTest.cpp @@ -42,6 +42,17 @@ std::true_type>::value)); } +TEST(STLForwardCompatTest, MakeArrayTest) { + ASSERT_EQ((llvm::make_array()), (std::array{})); + ASSERT_EQ((llvm::make_array()), (std::array{})); + ASSERT_EQ((llvm::make_array(1u, 2u, 3u)), + (std::array{1, 2, 3})); + ASSERT_EQ((llvm::make_array(1u, 2u, 3u)), + (llvm::make_array(size_t(1), size_t(2u), size_t(3u)))); + ASSERT_EQ((llvm::make_array(true, false, false, true)), + (std::array{true, false, false, true})); +} + template class STLForwardCompatRemoveCVRefTest : public ::testing::Test {};