diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -76,7 +76,6 @@ }; namespace detail { -template using void_t = void; template class Op, class... Args> struct detector { using value_t = std::false_type; }; 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 @@ -64,6 +64,9 @@ explicit in_place_index_t() = default; }; +template +using void_t = void; // NOLINT(readability-identifier-naming) + //===----------------------------------------------------------------------===// // Features from C++20 //===----------------------------------------------------------------------===// diff --git a/llvm/include/llvm/ADT/SmallSet.h b/llvm/include/llvm/ADT/SmallSet.h --- a/llvm/include/llvm/ADT/SmallSet.h +++ b/llvm/include/llvm/ADT/SmallSet.h @@ -16,7 +16,7 @@ #include "llvm/ADT/None.h" #include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/iterator.h" #include "llvm/Support/Compiler.h" @@ -30,14 +30,14 @@ namespace llvm { /// SmallSetIterator - This class implements a const_iterator for SmallSet by -/// delegating to the underlying SmallVector or Set iterators. +/// delegating to the underlying StaticVector or Set iterators. template class SmallSetIterator : public iterator_facade_base, std::forward_iterator_tag, T> { private: using SetIterTy = typename std::set::const_iterator; - using VecIterTy = typename SmallVector::const_iterator; + using VecIterTy = typename StaticVector::const_iterator; using SelfTy = SmallSetIterator; /// Iterators to the parts of the SmallSet containing the data. They are set @@ -134,14 +134,13 @@ /// std::set to maintain reasonable lookup times. template > class SmallSet { - /// Use a SmallVector to hold the elements here (even though it will never - /// reach its 'large' stage) to avoid calling the default ctors of elements - /// we will never use. - SmallVector Vector; + /// Use a StaticVector to hold the elements here to avoid calling the default + /// ctors of elements we will never use. + StaticVector Vector; std::set Set; - using VIterator = typename SmallVector::const_iterator; - using mutable_iterator = typename SmallVector::iterator; + using VIterator = typename StaticVector::const_iterator; + using mutable_iterator = typename StaticVector::iterator; // In small mode SmallPtrSet uses linear search for the elements, so it is // not a good idea to choose this value too high. You may consider using a diff --git a/llvm/include/llvm/ADT/StaticVector.h b/llvm/include/llvm/ADT/StaticVector.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/StaticVector.h @@ -0,0 +1,2636 @@ +//===- StaticVector.h - Fixed-sized vector implementation ----------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 +// +//===----------------------------------------------------------------------===// +/// +/// \file StaticVector.h +/// `llvm::StaticVector` class definition. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_STATICVECTOR_H +#define LLVM_ADT_STATICVECTOR_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/STLForwardCompat.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MathExtras.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace llvm { + +namespace detail { +template +class is_iterator : public std::false_type {}; + +template +class is_iterator>::iterator_category>> + : public std::true_type {}; +} // namespace detail + +/// Determine whether a type is an iterator (i.e. belongs to any iterator +/// category). +template using is_iterator = detail::is_iterator; + +/// Determine whether a type belongs to the specified iterator category. +/// +/// \tparam T Iterator type to query. +/// \tparam Cat Iterator category `T` must belong to. +template ::value> +class is_iterator_category : public std::false_type {}; + +template +class is_iterator_category + : public // clang-format off + std::is_base_of< + Cat, + typename std::iterator_traits< + std::remove_reference_t + >::iterator_category + > // clang-format on +{}; + +template +using is_input_iterator = is_iterator_category; + +template +using is_output_iterator = is_iterator_category; + +template +using is_forward_iterator = is_iterator_category; + +namespace detail { +template +class has_begin_member : public std::false_type {}; + +template +class has_begin_member().begin())>> + : public std::true_type {}; + +template +class has_begin_adl : public std::false_type {}; + +template +class has_begin_adl()))>> + : public std::true_type {}; + +template +class has_begin_std : public std::false_type {}; + +template +class has_begin_std()))>> + : public std::true_type {}; + +template +class has_end_member : public std::false_type {}; + +template +class has_end_member().end())>> + : public std::true_type {}; + +template +class has_end_adl : public std::false_type {}; + +template +class has_end_adl()))>> + : public std::true_type {}; + +template +class has_end_std : public std::false_type {}; + +template +class has_end_std()))>> + : public std::true_type {}; + +template +class has_size : public std::false_type {}; + +template +class has_size().size())>> + : public std::true_type {}; + +template ::value> +class has_size_returns_integral : public std::false_type {}; + +template +class has_size_returns_integral + : public std::is_integral().size())> {}; + +} // namespace detail + +template +using has_begin = + llvm::disjunction, detail::has_begin_adl, + detail::has_begin_std>; + +template +using has_end = + llvm::disjunction, detail::has_end_adl, + detail::has_end_std>; + +template using has_size = detail::has_size_returns_integral; + +namespace detail { +/// Determine the return type of the `begin` function associated with a +/// container type. +/// +/// The type evaluates to `void` if no `begin` function is available. +template ::value, + bool ADL = has_begin_adl::value, + bool STL = has_begin_std::value> +struct get_begin_type { + using type = void; +}; + +template +struct get_begin_type { + using type = decltype(std::declval().begin()); +}; + +template +struct get_begin_type { + using type = decltype(begin(std::declval())); +}; + +template +struct get_begin_type { + using type = decltype(std::begin(std::declval())); +}; + +/// Determine the return type of the `end` function associated with a +/// container type. +/// +/// The type evaluates to `void` if no `end` function is available. +template ::value, + bool ADL = has_end_adl::value, + bool STL = has_end_std::value> +struct get_end_type { + using type = void; +}; + +template +struct get_end_type { + using type = decltype(std::declval().end()); +}; + +template +struct get_end_type { + using type = decltype(end(std::declval())); +}; + +template +struct get_end_type { + using type = decltype(std::end(std::declval())); +}; +} // namespace detail + +template +using get_begin_type = detail::get_begin_type; + +template +using get_begin_type_t = typename get_begin_type::type; + +template +using get_end_type = detail::get_end_type; + +template +using get_end_type_t = typename get_end_type::type; + +/// Determine whether a presumed container type can be iterated in the forward +/// direction via an input iterator. +/// +/// The container type must have begin + end functions that return the same +/// type, and both those return types must belong to the input iterator +/// category. +template +using is_input_iterable = // clang-format off + llvm::conjunction< + std::is_same, get_end_type_t>, + is_input_iterator< + get_begin_type_t + > + >; // clang-format on + +/// Determine whether a presumed container type can be iterated in the forward +/// direction via an output iterator. +/// +/// The container type must have begin + end functions that return the same +/// type, and both those return types must belong to the input iterator +/// category. +template +using is_output_iterable = // clang-format off + llvm::conjunction< + std::is_same, get_end_type_t>, + is_output_iterator< + get_begin_type_t + > + >; // clang-format on + +/// Determine whether a presumed container type can be iterated in the forward +/// direction via a forward iterator. +/// +/// The container type must have begin + end functions that return the same +/// type, and both those return types must belong to the forward iterator +/// category. +template +using is_forward_iterable = // clang-format off + llvm::conjunction< + std::is_same, get_end_type_t>, + is_forward_iterator< + get_begin_type_t + > + >; // clang-format on + +namespace detail { +template +class is_dereferenceable : public std::false_type {}; + +template +class is_dereferenceable())>> + : public std::true_type {}; +} // namespace detail +template using is_dereferenceable = detail::is_dereferenceable; + +namespace detail { +template +class is_convertible_iterator : public std::false_type {}; + +template +class is_convertible_iterator + : public std::is_convertible()), To> {}; +} // namespace detail + +template +using is_convertible_input_iterator = + detail::is_convertible_iterator::value>; + +template +using is_convertible_output_iterator = + detail::is_convertible_iterator::value>; + +template +using is_convertible_forward_iterator = + detail::is_convertible_iterator::value>; + +template +using is_input_iterable_and_convertible = // clang-format off + llvm::conjunction< + is_input_iterable, + is_convertible_input_iterator,To> + >; // clang-format on + +template +using is_output_iterable_and_convertible = // clang-format off + llvm::conjunction< + is_output_iterable, + is_convertible_output_iterator,To> + >; // clang-format on + +template +using is_forward_iterable_and_convertible = // clang-format off + llvm::conjunction< + is_forward_iterable, + is_convertible_forward_iterator,To> + >; // clang-format on + +template >::value> +struct get_container_size { + size_t operator()(remove_cvref_t const &Container) const { + return std::distance(adl_begin(Container), adl_end(Container)); + } +}; + +template struct get_container_size { + constexpr size_t + operator()(remove_cvref_t const &Container) const { + return Container.size(); + } +}; + +namespace static_vector_detail { + +template class EmplaceImplSelector; + +} // namespace static_vector_detail + +template class StaticVectorStorage { +public: + using value_type = T; + using pointer = T *; + using reference = T &; + using const_pointer = T const *; + using const_reference = T const &; + using size_type = size_t; + + static constexpr size_type Capacity = C; + +private: + // Choose the minmally sized unsigned integer which can represent the capacity + // of the StaticVector. + // clang-format off + using MinSizeStorageT = + std::conditional_t(Capacity), uint8_t, + std::conditional_t(Capacity), uint16_t, + std::conditional_t(Capacity), uint32_t, + size_type + > + > + >; + // clang-format on + + // Determine whether 'l' < 'r' at compile-time. + // + // Only defined because you can't use a '<' in a template argument without + // triggering a parse error. + static constexpr bool lessThan(size_t L, size_t R) { return L < R; } + + // Only use the minimal storage size if it will actually reduce sizeof(*this). + using SizeStorageT = + std::conditional_t; + +private: + SizeStorageT Size; + std::aligned_storage_t Data[Capacity]; + +public: + constexpr StaticVectorStorage(size_t S = 0) : Size(S) {} + + class ZeroInitTag {}; + constexpr StaticVectorStorage(ZeroInitTag, size_t S = 0) : Size(S), Data{0} {} + + pointer data() { return reinterpret_cast(Data); } + + constexpr const_pointer data() const { + return reinterpret_cast(Data); + } + + constexpr size_type size() const { return Size; } + constexpr size_type capacity() const { return Capacity; } + + constexpr SizeStorageT rawSize() const { return Size; } + + void setSize(size_type NewSize) { + assert(NewSize <= capacity()); + Size = static_cast(NewSize); + } +}; + +template class StaticVectorStorage { +public: + using value_type = T; + using pointer = T *; + using reference = T &; + using const_pointer = T const *; + using const_reference = T const &; + using size_type = size_t; + + static constexpr size_type Capacity = 0; + + constexpr StaticVectorStorage(size_type S = 0) {} + + class ZeroInitTag {}; + constexpr StaticVectorStorage(ZeroInitTag) {} + + pointer data() { return nullptr; } + constexpr const_pointer data() const { return nullptr; } + + constexpr size_type size() const { return 0; } + constexpr size_type capacity() const { return 0; } + + constexpr size_type rawSize() const { return 0; } + void setSize(size_type NewSize) { assert(NewSize == 0); } +}; + +/// +/// Implements a version of the `vector` container with capacity fixed at +/// compile-time. +/// +/// Mostly follows the spec at: +/// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0843r2.html +/// +/// \tparam T Type of data to be stored in the `StaticVector`. +/// \tparam C Capacity of the `StaticVector` container in number of elements. +/// +/// \warning A large `C` implies a large `sizeof(StaticVector)`. Be mindful +/// of this relationship when declaring this container on the stack. +/// +/// This container will not heap-allocate any storage. All the storage is +/// determined up-front at compile-time and resides within this container. +/// +/// Essentially this container implements the `vector` API over top of a +/// C-array with some special care taken to ensure that `T` need not be default +/// constructible. +/// +/// You can emplace elements on the back at low cost, and the container will +/// track the number of valid elements for you. +/// +template +class StaticVector : private StaticVectorStorage { + using StorageT = StaticVectorStorage; + +public: + /// \name Basic container types + /// \{ + + /// Type of values stored in `StaticVector`. + using value_type = typename StorageT::value_type; + + /// Pointer type of values stored in `StaticVector`. + using pointer = typename StorageT::pointer; + + /// Reference type of values stored in `StaticVector`. + using reference = typename StorageT::reference; + + /// const-qualified pointer type of values stored in `StaticVector`. + using const_pointer = typename StorageT::const_pointer; + + /// const-qualified reference type of values stored in `StaticVector`. + using const_reference = typename StorageT::const_reference; + + /// Integer type used to represent size. + using size_type = typename StorageT::size_type; + /// \} + + /// \name Iterator types. + /// \{ + + /// Forward iterator for the `StaticVector` class. + using iterator = pointer; + + /// Forward const-iterator for the `StaticVector` class. + using const_iterator = const_pointer; + + /// Reverse iterator for the `StaticVector` class. + using reverse_iterator = std::reverse_iterator; + + /// Reverse const-iterator for the `StaticVector` class. + using const_reverse_iterator = std::reverse_iterator; + + /// \} + + enum : size_type { Capacity = StorageT::Capacity }; + +private: + /// True if it's cheap enough to take parameters by value. Doing so avoids + /// overhead related to mitigations for reference invalidation. + static constexpr bool TakesParamByValue = + std::is_trivially_copyable::value && sizeof(T) <= 2 * sizeof(void *); + + /// Either const T& or T, depending on whether it's cheap enough to take + /// parameters by value. + using ValueParamT = typename std::conditional::type; + +public: + /// \name Constructors + /// \{ + constexpr StaticVector() = default; + + StaticVector(StaticVector const &Other); + + StaticVector(StaticVector &&Other); + + explicit StaticVector(size_type N); + + StaticVector(size_type N, ValueParamT Val); + + template < // clang-format off + typename InputIt, + std::enable_if_t::value + > * = nullptr + > // clang-format on + StaticVector(InputIt First, InputIt Last); + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation>, + is_forward_iterable_and_convertible + >::value + > * = nullptr + > // clang-format on + StaticVector(ContainerT &&Container); + + template < // clang-format off + typename U, + std::enable_if_t< + std::is_constructible::value + > * = nullptr + > // clang-format on + StaticVector(std::initializer_list IL); + /// \} + + /// \name Destructor + /// \{ + ~StaticVector(); + /// \} + + /// \name Assignment operators and methods + /// \{ + auto operator=(StaticVector const &Other) -> StaticVector &; + auto operator=(StaticVector &&Other) -> StaticVector &; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + conjunction< + negation>, + is_forward_iterable_and_convertible + >::value + > * = nullptr + > // clang-format on + auto operator=(ContainerT &&Container) -> StaticVector &; + + // NOLINTBEGIN(readability-identifier-naming) + + template < // clang-format off + typename InputIt, + std::enable_if_t< + is_convertible_input_iterator::value + > * = nullptr + > // clang-format on + auto assign(InputIt First, InputIt Last) -> StaticVector &; + + auto assign(size_type N, ValueParamT Val) -> StaticVector &; + + template < // clang-format off + typename U, + std::enable_if_t< + std::is_convertible::value + > * = nullptr + > // clang-format on + auto assign(std::initializer_list IL) -> StaticVector &; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_input_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto assign(ContainerT &&Container) -> StaticVector &; + + template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * = nullptr + > // clang-format on + auto checked_assign(FwdIt First, FwdIt Last) -> Error; + + auto checked_assign(size_type N, ValueParamT Val) -> Error; + + template < // clang-format off + typename U, + std::enable_if_t< + std::is_convertible::value + > * = nullptr + > // clang-format on + auto checked_assign(std::initializer_list IL) -> Error; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto checked_assign(ContainerT &&Container) -> Error; + + /// \} + + /// \name Begin & End methods + /// \{ + auto begin() -> iterator; + auto end() -> iterator; + constexpr auto begin() const -> const_iterator; + constexpr auto end() const -> const_iterator; + constexpr auto cbegin() const -> const_iterator; + constexpr auto cend() const -> const_iterator; + + auto rbegin() -> reverse_iterator; + auto rend() -> reverse_iterator; + constexpr auto rbegin() const -> const_reverse_iterator; + constexpr auto rend() const -> const_reverse_iterator; + constexpr auto crbegin() const -> const_reverse_iterator; + constexpr auto crend() const -> const_reverse_iterator; + /// \} + + /// \name Element access methods + /// \{ + auto operator[](size_type Offs) -> reference; + auto operator[](size_type Offs) const -> const_reference; + + auto front() -> reference; + auto front() const -> const_reference; + + auto back() -> reference; + auto back() const -> const_reference; + + auto data() -> pointer; + constexpr auto data() const -> const_pointer; + /// \} + + /// \name Container queries + /// \{ + constexpr auto size() const -> size_type; + constexpr auto capacity() const -> size_type; + constexpr bool empty() const; + /// \} + + /// \name Container content manipulation methods + /// \{ + + void resize(size_type NewSize); + void resize_for_overwrite(size_type NewSize); + void resize(size_type, ValueParamT Val); + + template + void resize_emplace(size_type NewSize, ArgsT &&...Args); + + Error checked_resize(size_type NewSize); + Error checked_resize_for_overwrite(size_type NewSize); + Error checked_resize(size_type NewSize, ValueParamT Val); + + template + Error checked_resize_emplace(size_type NewSize, ArgsT &&...Args); + + auto push_back(value_type &&Val) -> reference; + auto push_back(const_reference Val) -> reference; + + template auto emplace_back(ArgsT &&...Args) -> reference; + + auto checked_push_back(value_type &&Val) -> Expected; + auto checked_push_back(const_reference Val) -> Expected; + + template + auto checked_emplace_back(ArgsT &&...Args) -> Expected; + + template + auto emplace(const_iterator Pos, ArgsT &&...Args) -> iterator; + + template + auto checked_emplace(const_iterator Pos, ArgsT &&...Args) + -> Expected; + + auto append(size_type N, ValueParamT Val) -> iterator; + + auto checked_append(size_type N, ValueParamT Val) -> Expected; + + template < // clang-format off + typename InputIt, + std::enable_if_t< + is_convertible_input_iterator::value + > * = nullptr + > // clang-format on + auto append(InputIt First, InputIt Last) -> iterator; + + template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * = nullptr + > // clang-format on + auto checked_append(FwdIt First, FwdIt Last) -> Expected; + + template < // clang-format off + typename U, + std::enable_if< + std::is_convertible::value + > * = nullptr + > // clang-format on + auto append(std::initializer_list IL) -> iterator; + + template < // clang-format off + typename U, + std::enable_if< + std::is_convertible::value + > * = nullptr + > // clang-format on + auto checked_append(std::initializer_list IL) -> Expected; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_input_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto append(ContainerT &&Container) -> iterator; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto checked_append(ContainerT &&Container) -> Expected; + + auto insert(const_iterator Pos, const_reference Val) -> iterator; + auto insert(const_iterator Pos, value_type &&Val) -> iterator; + auto insert(const_iterator Pos, size_type N, ValueParamT Val) -> iterator; + + template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * = nullptr + > // clang-format on + auto insert(const_iterator Pos, FwdIt First, FwdIt Last) -> iterator; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto insert(const_iterator Pos, ContainerT &&Container) -> iterator; + + auto checked_insert(const_iterator Pos, const_reference Val) + -> Expected; + auto checked_insert(const_iterator Pos, value_type &&Val) + -> Expected; + auto checked_insert(const_iterator Pos, size_type N, ValueParamT Val) + -> Expected; + + template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * = nullptr + > // clang-format on + auto checked_insert(const_iterator Pos, FwdIt First, FwdIt Last) + -> Expected; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto checked_insert(const_iterator Pos, ContainerT &&Container) + -> Expected; + + void clear(); + + void pop_back(); + void pop_back_n(size_type N); + auto pop_back_val() -> value_type; + + auto checked_pop_back() -> Error; + auto checked_pop_back_n(size_type N) -> Error; + auto checked_pop_back_val() -> Expected; + + auto erase(const_iterator Pos) -> iterator; + auto erase(const_iterator First, const_iterator Last) -> iterator; + + auto checked_erase(const_iterator Pos) -> Expected; + auto checked_erase(const_iterator First, const_iterator Last) + -> Expected; + /// \} + + // NOLINTEND(readability-identifier-naming) + + /// \name Comparison operators + /// \{ + bool operator==(StaticVector const &RHS) const; + bool operator!=(StaticVector const &RHS) const; + bool operator<(StaticVector const &RHS) const; + bool operator>(StaticVector const &RHS) const; + bool operator<=(StaticVector const &RHS) const; + bool operator>=(StaticVector const &RHS) const; + /// \} + + /* implicit */ operator ArrayRef() const { + return {data(), size()}; + } + + /* implicit */ operator MutableArrayRef() { + return {data(), size()}; + } + +private: + using StorageT::setSize; + + template + auto emplaceSingleArgImpl(const_iterator Pos, ArgT &&Args) -> iterator; + + template + auto emplaceImpl(const_iterator Pos, ArgsT &&...Args) -> iterator; + + template + friend class static_vector_detail::EmplaceImplSelector; + + template + static void construct(U *Ptr, ArgsT &&...Args) { + ::new ((void *)Ptr) U(std::forward(Args)...); + } + + template + static pointer constructRange(pointer B, pointer E, ArgsT const &...Args) { + for (; B < E; ++B) { + construct(B, Args...); + } + return B; + } + + template static void destroy(U *Ptr); + + static void destroyRange(iterator B, iterator E); + + template + static bool aliases(pointer B, pointer E, ArgsT &&...Args); +}; + +namespace static_vector_detail { + +template ::value> +class Destroy { +public: + void operator()(T *P) const { P->~T(); } + + void operator()(T *B, T *E) const { + for (auto *P = E - 1; P >= B; --P) + P->~T(); + } +}; + +// Trivial specialization. +template class Destroy { +public: + void operator()(T *P) const {} + void operator()(T *B, T *E) const {} +}; + +template +constexpr int aliasesSingle(T *B, T *E, bool &Result, ArgT &&Arg) { + return (Result |= std::addressof(Arg) >= B && std::addressof(Arg) <= E, 0); +} + +template constexpr void eval(Tn &&...) {} + +// Emplace implementation selector template. +// +// Special case implementation to deal with aliased copy insertion if the size +// of the parameter pack == 1. +template class EmplaceImplSelector { +public: + template + typename StaticVecT::iterator + operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos, + ArgsT &&...Args) { + return Vec.emplaceImpl(Pos, std::forward(Args)...); + } +}; + +template class EmplaceImplSelector<1, ArgsT...> { +public: + template + typename StaticVecT::iterator + operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos, + ArgsT &&...Args) { + return Vec.emplaceSingleArgImpl(Pos, std::forward(Args)...); + } +}; + +template +using GetEmplaceSelector = EmplaceImplSelector; + +} // namespace static_vector_detail + +/// +/// Destroy the object at the specified location. +/// +/// This function will generate no code if `T` is trivially destructible. +/// +/// \param Ptr Pointer to the object to destroy. +/// +template +template +inline void StaticVector::destroy(U *Ptr) { + static_vector_detail::Destroy()(Ptr); +} + +/// +/// Destroy elements in a specified range. +/// +/// This function will generate no code if `T` is trivially destructible. +/// +/// \param B Beginning of the range of elements to destroy. +/// \param E End of the range of elements to destroy. +/// +template +inline void StaticVector::destroyRange(iterator First, iterator Last) { + static_vector_detail::Destroy()(First, Last); +} + +/// +/// Determine whether any of the references in the parameter pack alias with the +/// specified range. +/// +/// \param B Beginning of the range to check for aliasing +/// \param E End of the range to check for aliasing. +/// \param Args Parameter pack to check for aliasing range `[B,E)`. +/// +/// \return `true` if any reference in the parameter pack aliases `[B,E)`; +/// `false` otherwise. +/// +template +template +inline bool StaticVector::aliases(pointer B, pointer E, ArgsT &&...Args) { + bool Result = false; + // evaluation order does not matter, so use a dummy function. + static_vector_detail::eval(static_vector_detail::aliasesSingle( + B, E, Result, std::forward(Args))...); + return Result; +} + +/// +/// Constructor with initial size specifier. +/// +/// \param N Number of default-constructed elements to add during +/// construction. +/// +/// \note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(size_type N) : StorageT(N) { + constructRange(begin(), end()); +} + +/// +/// Constructor with initial size + value specifiers. +/// +/// \param N Number of elements to add during construction. +/// \param Val Value to copy while adding elements. +/// +/// \note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(size_type N, ValueParamT Val) + : StorageT(N) { + std::uninitialized_fill_n(begin(), N, Val); +} + +/// +/// Copy constructor. +/// +/// Copy contents of another `StaticVector`. +/// +/// \param Other `StaticVector` object to copy. +/// +/// \note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(StaticVector const &Other) + : StorageT(Other.size()) { + std::uninitialized_copy(Other.begin(), Other.end(), begin()); +} + +/// +/// Move constructor. +/// +/// Move all the elements from another `StaticVector` into this one. +/// +/// \param Other `StaticVector` object to copy. +/// +/// Notice that a move construction is not as fast as if the container were +/// heap allocated. We do need to visit all elements in `Other`. +/// +/// \note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(StaticVector &&Other) + : StorageT(Other.size()) { + auto *First = Other.begin(); + auto *Last = Other.end(); + std::uninitialized_copy(std::make_move_iterator(First), + std::make_move_iterator(Last), begin()); +} + +/// +/// Copy range constructor +/// +/// Copy all the elements in the range `[first, Last). +/// +/// \param First First element to copy. +/// \param Last One-past the last element to copy. +/// +/// \note Complexity = O(n) +/// +template +template < + typename InputIt, + std::enable_if_t::value> *> +inline StaticVector::StaticVector(InputIt First, InputIt Last) + : StorageT(static_cast(std::distance(First, Last))) { + std::uninitialized_copy(First, Last, begin()); +} + +/// +/// Copy from an unknown container type which is input iterable. +/// +/// \param Container The container to copy from. +/// +/// \note Complexity = O(n) +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation,ContainerT>>, + is_forward_iterable_and_convertible + >::value + > * +> // clang-format on +inline StaticVector::StaticVector(ContainerT &&Container) + : StaticVector(adl_begin(Container), adl_end(Container)) {} + +/// +/// Initializer list constructor. +/// +/// Initialize the `StaticVector` to contain copies of elements in the +/// specified `initializer_list`. +/// +/// \param IL Initializer list to copy elements from. +/// +/// \note Complexity = O(n) +/// +template +template ::value> *> +inline StaticVector::StaticVector(std::initializer_list IL) + : StaticVector(IL.begin(), IL.end()) {} + +/// +/// Destructor. +/// +/// Destroy all currently valid elements in the container. This code will +/// evaluate to nothing if `ValueType` is trivially destructrible. +/// +/// \note Complexity = O(n) if `T` is non-trivially destructible; O(1) +/// otherwise. +/// +template inline StaticVector::~StaticVector() { + destroyRange(begin(), end()); +} + +/// +/// Copy assignment operator. +/// +/// Clear current contents and then copy elements from another `StaticVector`. +/// +/// \param Other `StaticVector` to copy contents from. +/// +/// \return A reference to this `StaticVector`. +/// +/// \note Complexity = O(n) +/// +template +inline auto StaticVector::operator=(StaticVector const &Other) + -> StaticVector & { + assign(Other.begin(), Other.end()); + return *this; +} + +/// +/// Move assignment operator. +/// +/// Clear current contents and then move elements from another `StaticVector`. +/// +/// \param Other `StaticVector` to move contents from. +/// +/// Notice that a move assignment is not as fast as if the container were heap +/// allocated. We do need to visit all elements in `Other`. +/// +/// \return A reference to this `StaticVector`. +/// +/// \note Complexity = O(n) +/// +template +inline auto StaticVector::operator=(StaticVector &&Other) + -> StaticVector & { + + size_type OtherSize = Other.size(); + size_type ThisSize = size(); + + if (ThisSize >= OtherSize) { + // assign common elements. + iterator NewEnd = begin(); + if (OtherSize) + NewEnd = std::move(Other.begin(), Other.end(), NewEnd); + + // Destroy extra elements. + destroyRange(NewEnd, end()); + } else { + // Move assign over current elements. + if (ThisSize) { + std::move(Other.begin(), Other.begin() + ThisSize, begin()); + } + // Move construct the new elements in place. + std::uninitialized_copy(std::make_move_iterator(Other.begin() + ThisSize), + std::make_move_iterator(Other.end()), + begin() + ThisSize); + } + setSize(OtherSize); + return *this; +} + +/// +/// Container assignment operator. +/// +/// Clear current contents and then copy elements from another container. +/// +/// This operator is only enabled when the `ContainerT` is forward iterable and +/// the type obtained from dereferencing the iterator is convertible to `T`. +/// +/// \return A reference to this `StaticVector`. +/// +/// \note Complexity = O(n) +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation, ContainerT>>, + is_forward_iterable_and_convertible + >::value + > * +> // clang-format on +inline auto StaticVector::operator=(ContainerT &&Container) + -> StaticVector & { + assign(Container); + return *this; +} + +/// +/// Assign contents between specified input iterators. +/// +/// \param First iterator referring to the first element to copy. +/// \param Last iterator referring to one-past the last element to copy. +/// +/// \return A reference to this `StaticVector`. +/// +/// \note Complexity = O(n) +/// +template +template < // clang-format off + typename InputIt, + std::enable_if_t< + is_convertible_input_iterator::value + > * +> // clang-format on +inline auto StaticVector::assign(InputIt First, InputIt Last) + -> StaticVector & { + clear(); + append(First, Last); + return *this; +} + +template +template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * +> // clang-format on +inline auto StaticVector::checked_assign(FwdIt First, FwdIt Last) + -> Error { + if (size_t(std::distance(First, Last)) > capacity()) { + return createStringError(std::errc::invalid_argument, + "assign exceeds capacity"); + } + + assign(First, Last); + return Error::success(); +} + +/// +/// Assign contents to a specified number of values. +/// +/// Clear current contents and then assign `N` elements to `Val` at the front +/// of the container. +/// +/// \param N Number of elements to create during the assignment. +/// \param Val Value to assign to newly created elements. +/// +/// \return A reference to this `StaticVector`. +/// +/// \note Complexity = O(n) +/// +template +inline auto StaticVector::assign(size_type N, ValueParamT Val) + -> StaticVector & { + clear(); + append(N, Val); + return *this; +} + +template +inline auto StaticVector::checked_assign(size_type N, ValueParamT Val) + -> Error { + if (N > capacity()) { + return createStringError(std::errc::invalid_argument, + "assign exceeds capacity"); + } + + assign(N, Val); + return Error::success(); +} + +/// +/// Copy assign from a std::initializer_list which holds elements of a type +/// which is convertible to `T`. +/// +/// \param IL `std::initializer_list` to copy assign from. +/// +/// \return A reference to this `StaticVector`. +/// +template +template < // clang-format off + typename U, + std::enable_if_t< + std::is_convertible::value + > * +> // clang-format on +inline auto StaticVector::assign(std::initializer_list IL) + -> StaticVector & { + return assign(IL.begin(), IL.end()); +} + +template +template < // clang-format off + typename U, + std::enable_if_t< + std::is_convertible::value + > * +> // clang-format on +inline auto StaticVector::checked_assign(std::initializer_list IL) + -> Error { + if (IL.size() > capacity()) { + return createStringError(std::errc::invalid_argument, + "assign exceeds capacity"); + } + + assign(IL.begin(), IL.end()); + return Error::success(); +} + +/// +/// Copy assign from an arbitrary container which holds elements of a type which +/// is convertible to `T`. +/// +/// \param Container Reference to the container to copy assign from. +/// +/// \return A reference to this `StaticVector`. +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_input_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::assign(ContainerT &&Container) + -> StaticVector & { + auto B = adl_begin(Container); + auto E = adl_end(Container); + + using IterT = + std::conditional_t::value, + std::move_iterator, decltype(B)>; + + return assign(IterT(B), IterT(E)); +} + +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::checked_assign(ContainerT &&Container) + -> Error { + if (get_container_size()(Container) > capacity()) { + return createStringError(std::errc::bad_address, + "assign causes buffer overflow."); + } + + assign(std::forward(Container)); + return Error::success(); +} + +/// +/// Access a specified element in the `StaticVector`. +/// +/// An assertion will trigger when specified index is out of bounds. +/// +/// \param Offs Index of the element to access. +/// +/// \return A reference to the element at the specified index. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::operator[](size_type Offs) -> reference { + assert(Offs < size()); + return data()[Offs]; +} + +/// +/// Access a specified element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger when specified index is out of bounds. +/// +/// \param Offs Index of the element to access. +/// +/// \return A const-qualified reference to the element at the specified index. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::operator[](size_type Offs) const + -> const_reference { + assert(Offs < size()); + return data()[Offs]; +} + +/// +/// Access the first element in the `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// \return A reference to the first element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::front() -> reference { + return operator[](0); +} + +/// +/// Access the first element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// \return A const-qualified reference to the first element in the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::front() const -> const_reference { + return operator[](0); +} + +/// +/// Access the last element in the `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// \return A reference to the last element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::back() -> reference { + return operator[](size() - 1); +} + +/// +/// Access the last element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// \return A const-qualified reference to the last element in the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::back() const -> const_reference { + return operator[](size() - 1); +} + +/// +/// Return a pointer to the data buffer. +/// +/// This method is provided to allow interoperation with C-APIs. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::data() -> pointer { + return StorageT::data(); +} + +/// +/// Return a const-qualified pointer to the data buffer. +/// +/// This method is provided to allow interoperation with C-APIs. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::data() const -> const_pointer { + return StorageT::data(); +} + +/// +/// Report the number of elements that can be accommodated by the storage. +/// +/// \return The maximum number of elements the container can store. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::capacity() const -> size_type { + return StorageT::capacity(); +} + +/// +/// Report the current number of valid elements in the `StaticVector`. +/// +/// \return The number of elements currently contained by the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::size() const -> size_type { + return StorageT::size(); +} + +/// +/// Report whether the `StaticVector` contains no elements. +/// +/// \return `true` if no elements are currently inserted into the container; +/// `false` otherwise. +/// +/// \note Complexity = O(1) +/// +template +constexpr bool StaticVector::empty() const { + return StorageT::rawSize() == 0; +} + +/// +/// Return a forward iterator corresponding to the front of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::begin() -> iterator { + return data(); +} + +/// +/// Return a forward iterator corresponding to one-past the last valid +/// element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::end() -> iterator { + return data() + size(); +} + +/// +/// Return a forward const-iterator corresponding to the front of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::begin() const -> const_iterator { + return data(); +} + +/// +/// Return a forward constiterator corresponding to one-past the +/// last valid element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::end() const -> const_iterator { + return data() + size(); +} + +/// +/// Return a forward const-iterator corresponding to the front of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::cbegin() const -> const_iterator { + return begin(); +} + +/// +/// Return a forward constiterator corresponding to one-past the +/// last valid element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::cend() const -> const_iterator { + return end(); +} + +/// +/// Return a reverse iterator corresponding to the back of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::rbegin() -> reverse_iterator { + return reverse_iterator(end()); +} + +/// +/// Return a reverse iterator corresponding to one-before the first +/// valid element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::rend() -> reverse_iterator { + return reverse_iterator(begin()); +} + +/// +/// Return a reverse const-iterator corresponding to the back of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::rbegin() const -> const_reverse_iterator { + return const_reverse_iterator(end()); +} + +/// +/// Return a reverse const-iterator corresponding to one-before the +/// first valid element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::rend() const -> const_reverse_iterator { + return const_reverse_iterator(begin()); +} + +/// +/// Return a reverse const-iterator corresponding to the back of the +/// `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::crbegin() const -> const_reverse_iterator { + return rbegin(); +} + +/// +/// Return a reverse const-iterator corresponding to one-before the +/// first valid element in the `StaticVector`. +/// +/// \note Complexity = O(1) +/// +template +constexpr auto StaticVector::crend() const -> const_reverse_iterator { + return rend(); +} + +/// +/// Resize the conainer to a specified size; emplace newly created +/// elements (if any). +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are constructed via perfect-forwarding +/// specified arguments in the `Args` parameter pack. +/// +/// \param NewSize New size of the `StaticVector`. +/// \param Args Parameter pack of constructor arguments to use while +/// constructing new elements (if any). +/// +/// \note Complexity = O(n) +/// +template +template +inline void StaticVector::resize_emplace(size_type NewSize, + ArgsT &&...Args) { + assert(NewSize <= capacity()); + + if (NewSize > size()) { + auto NewEnd = begin() + NewSize; + pointer P = constructRange(end(), NewEnd - 1, Args...); + // Can forward args to the last element emplaced. + construct(P, std::forward(Args)...); + } else { + destroyRange(begin() + NewSize, end()); + } + + setSize(NewSize); +} + +template +template +inline Error StaticVector::checked_resize_emplace(size_type NewSize, + ArgsT &&...Args) { + if (NewSize > capacity()) { + return createStringError(std::errc::bad_address, + "capacity exceeded by resize."); + } + + resize_emplace(NewSize, std::forward(Args)...); + return Error::success(); +} + +/// +/// Resize the conainer to a specified size; default construct newly +/// created elements (if any). +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are default constructed. +/// +/// \param NewSize New size of the `StaticVector`. +/// +/// \note Complexity = O(m); where 'm' is the number of elements destroyed +/// or constructed. +/// +template +inline void StaticVector::resize(size_type NewSize) { + resize_emplace(NewSize); +} + +template +inline Error StaticVector::checked_resize(size_type NewSize) { + return checked_resize_emplace(NewSize); +} + +/// +/// Resize the conainer to a specified size; copy construct newly +/// created elements from specified value. +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are copy constructed. +/// +/// \param NewSize New size of the `StaticVector`. +/// \param Val Value to copy construct into new elements. +/// +/// \note Complexity = O(m); where 'm' is the number of elements destroyed +/// or constructed. +/// +template +inline void StaticVector::resize(size_type NewSize, ValueParamT Val) { + resize_emplace(NewSize, Val); +} + +template +inline Error StaticVector::checked_resize(size_type NewSize, + ValueParamT Val) { + return checked_resize_emplace(NewSize, Val); +} + +/// +/// Resize the buffer, but POD data types will be left uninitialized. +/// +/// \param NewSize New number of elements to size of the storage buffer. +/// +/// \note Complexity = O(m); where 'm' is the number of elements destroyed or +/// constructed. +template +inline void StaticVector::resize_for_overwrite(size_type NewSize) { + + if (NewSize < size()) { + destroyRange(data() + NewSize, data() + size()); + setSize(NewSize); + } else if (NewSize > size()) { + assert(NewSize <= capacity()); + + for (auto I = end(), E = begin() + NewSize; I != E; ++I) + ::new (I) value_type; + + setSize(NewSize); + } +} + +template +inline Error +StaticVector::checked_resize_for_overwrite(size_type NewSize) { + if (NewSize > capacity()) + return createStringError(std::errc::bad_address, + "resize exceeds capacity."); + + resize_for_overwrite(NewSize); + return Error::success(); +} + +/// +/// Insert a new element at the back, constructed with specified +/// arguments (saves creation of a temporary). +/// +/// \param Args Parameter pack of arguments to pass to the constructor of +/// the new element. +/// +/// \return A `reference` to the newly inserted object. +/// +/// \note Complexity = O(1) +/// +template +template +inline auto StaticVector::emplace_back(ArgsT &&...Args) -> reference { + assert(size() < capacity()); + construct(data() + size(), std::forward(Args)...); + + setSize(size() + 1); + return back(); +} + +template +template +inline auto StaticVector::checked_emplace_back(ArgsT &&...Args) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "emplace_back exceeds capacity"); + + return emplace_back(std::forward(Args)...); +} + +/// +/// Move a new element to the back. +/// +/// \param Val Object to move into the new back element. +/// +/// \return A `reference` to the newly inserted object. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::push_back(value_type &&Val) -> reference { + return emplace_back(std::move(Val)); +} + +template +inline auto StaticVector::checked_push_back(value_type &&Val) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "push_back exceeds capacity"); + + return push_back(std::move(Val)); +} + +/// +/// Copy a new element at the back. +/// +/// \param Val Object to copy to the new back element. +/// +/// \return A `reference` to the newly inserted object. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::push_back(const_reference Val) -> reference { + return emplace_back(Val); +} + +template +inline auto StaticVector::checked_push_back(const_reference Val) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "push_back exceeds capacity"); + + return push_back(Val); +} + +/// +/// Insert an object constructed via specified arguments into this +/// `StaticVector` before a specified position. +/// +/// If `Pos == end()`, then the new members are inserted at the back of +/// the `StaticVector`. +/// +/// \param Pos Position in the current `StaticVector` to insert before. +/// \param Args Parameter pack of constructor args to pass to the newly +/// create element. +/// +/// \return An `iterator` which represents the newly inserted element. +/// +/// \note Complexity = O(m); where `m` is the number of items between +/// `Pos` and end(). +/// +template +template +auto StaticVector::emplace(const_iterator Pos, ArgsT &&...Args) + -> iterator { + using SelectorT = static_vector_detail::GetEmplaceSelector; + return SelectorT()(*this, Pos, std::forward(Args)...); +} + +template +template +auto StaticVector::checked_emplace(const_iterator Pos, ArgsT &&...Args) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "emplace exceeds capacity."); + + if (Pos < cbegin() || Pos > cend()) + return createStringError(std::errc::invalid_argument, + "emplace insertion position."); + + return emplace(Pos, std::forward(Args)...); +} + +/// +/// General implementation of emplace used for most parameter pack sizes. +/// +/// \param Pos Position in `this` to insert before. +/// \param Args Parameter pack used to construct the new element in place. +/// +/// \return An `iterator` which represents the newly inserted element. +/// +template +template +auto StaticVector::emplaceImpl(const_iterator Pos, ArgsT &&...Args) + -> iterator { + assert(size() < capacity()); + + size_type Idx = std::distance(cbegin(), Pos); + pointer PIns = data() + Idx; + std::aligned_storage_t AliasTmp; + + bool Aliases = aliases(PIns, end(), std::forward(Args)...); + + if (Aliases) { + // One of the constructor args aliases the buffer we're about to move. + // Construct a temporary and then move that into the final position after + // moving existing elements up. + construct(reinterpret_cast(std::addressof(AliasTmp)), + std::forward(Args)...); + } + + if (Idx != size()) { + construct(this->end(), std::move(back())); + std::move_backward(PIns, end() - 1, end()); + destroy(PIns); + } + + if (Aliases) { + construct(PIns, std::move(reinterpret_cast(AliasTmp))); + destroy((pointer)std::addressof(AliasTmp)); + } else { + construct(PIns, std::forward(Args)...); + } + + setSize(size() + 1); + + return PIns; +} + +/// +/// Specialized implementation of emplace used for size==1 parameter packs. +/// +/// This specialized implementation allows us to more efficiently handle the +/// case where the parameter aliases with the back range of the `StaticVector` +/// which will be moved upwards during the insertion. +/// +/// \param Pos Position in `this` to insert before. +/// \param Arg Parameter used to construct the new element in place. +/// +/// \return An `iterator` which represents the newly inserted element. +/// +template +template +auto StaticVector::emplaceSingleArgImpl(const_iterator Pos, ArgT &&Arg) + -> iterator { + assert(size() < capacity()); + + size_type Idx = std::distance(cbegin(), Pos); + pointer PIns = data() + Idx; + auto *ConstructPtr = std::addressof(Arg); + + bool Aliases = aliases(PIns, end(), std::forward(Arg)); + + if (Idx != size()) { + construct(this->end(), std::move(back())); + std::move_backward(PIns, end() - 1, end()); + destroy(PIns); + } + + if (Aliases) { + // Adjust the pointer... 'ConstructPtr' might not be a pointer to a + // `value_type`. It could be a member of a `value_type` which is + // convertible to a `value_type`. Therefore, we need to cast to char and + // adjust by sizeof(value_type) to ensure we're pointing at the right thing. + char *AdjustPtr = const_cast((char const *)ConstructPtr); + AdjustPtr += sizeof(value_type); + ConstructPtr = (decltype(ConstructPtr))(AdjustPtr); + } + + construct(PIns, std::forward(*ConstructPtr)); + + setSize(size() + 1); + + return PIns; +} + +/// +/// Insert a new elements by copy before the specified position. +/// +/// If `Pos == end()`, the new member is appended. +/// +/// \param Pos Position in the `StaticVector` to insert before. +/// \param Val Object to copy-construct into new elements inserted. +/// +/// \return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// \note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, const_reference Val) + -> iterator { + return emplace(Pos, Val); +} + +template +auto StaticVector::checked_insert(const_iterator Pos, const_reference Val) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "insert exceeds capacity."); + + if (Pos < cbegin() || Pos > cend()) + return createStringError(std::errc::invalid_argument, + "invalid insertion position."); + + return insert(Pos, Val); +} + +/// +/// Insert a new elements via move construction before the specified position. +/// +/// If `Pos == end()`, the new member is appended. +/// +/// \param Pos Position in the `StaticVector` to insert before. +/// \param Val Object to copy-construct into new elements inserted. +/// +/// \return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// \note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, value_type &&Val) + -> iterator { + return emplace(Pos, std::move(Val)); +} + +template +auto StaticVector::checked_insert(const_iterator Pos, value_type &&Val) + -> Expected { + if (size() >= capacity()) + return createStringError(std::errc::bad_address, + "insert exceeds capacity."); + + if (Pos < cbegin() || Pos > cend()) + return createStringError(std::errc::invalid_argument, + "invalid insertion position."); + + return insert(Pos, std::move(Val)); +} + +/// +/// Insert `N` new elements before the specified position. +/// +/// If `Pos == end()`, then the new members are inserted at the back +/// of the `StaticVector`. +/// +/// \param Pos Position in the `StaticVector` to insert before. +/// \param N Number of elements to insert. +/// \param Val Object to copy-construct into new elements inserted. +/// +/// \return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// \note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, size_type N, + ValueParamT Val) -> iterator { + assert(Pos >= cbegin()); + assert(Pos <= cend()); + assert(size() + N <= capacity()); + + iterator I = begin() + std::distance(cbegin(), Pos); + iterator OldEnd = end(); + + value_type const *CopyPtr = std::addressof(Val); + + if (size_t(OldEnd - I) >= N) { + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + append(std::make_move_iterator(OldEnd - N), + std::make_move_iterator(OldEnd)); + + // Copy the existing elements that get replaced. + std::move_backward(I, OldEnd - N, OldEnd); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= CopyPtr && CopyPtr < OldEnd) + CopyPtr += N; + + std::fill_n(I, N, *CopyPtr); + } else { + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + setSize(size() + N); + size_t NumOverwritten = OldEnd - I; + + std::uninitialized_copy(std::make_move_iterator(I), + std::make_move_iterator(OldEnd), end() - N); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= CopyPtr && CopyPtr < end()) + CopyPtr += N; + + // Replace the overwritten part. + std::fill_n(I, NumOverwritten, *CopyPtr); + + // Insert the non-overwritten middle part. + std::uninitialized_fill_n(OldEnd, N - NumOverwritten, *CopyPtr); + } + + return I; +} + +template +auto StaticVector::checked_insert(const_iterator Pos, size_type N, + ValueParamT Val) -> Expected { + if (Pos < cbegin() || Pos > cend()) { + return createStringError(std::errc::invalid_argument, + "insert position is out of bounds"); + } + + if (size() + N > capacity()) { + return createStringError(std::errc::bad_address, "insert exceeds capacity"); + } + + return insert(Pos, N, Val); +} + +/// +/// Insert new elements from an iterator range. +/// +/// Insert new vector members which are copies of values described by +/// input iterator range `[First, Last)` before the specified position +/// (`Pos`). If `Pos == end()`, then the new members are inserted at +/// the back of the `StaticVector`. +/// +/// \param Pos Position in the `StaticVector` to insert before. +/// \param First Input iterator referencing the first element to insert. +/// \param Last Input iterator referencing one-past the last element to insert. +/// +/// \return `Pos` if `First == Last`; otherwise an `iterator` which +/// represents the first newly inserted item. +/// +/// \note Complexity = O(m + `std::distance(First, Last)`); where `m` is the +/// number of items between `Pos` and `end()`. +/// +template +template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * +> // clang-format on +auto StaticVector::insert(const_iterator Pos, FwdIt First, FwdIt Last) + -> iterator { + iterator I = begin() + std::distance(cbegin(), Pos); + iterator OldEnd = end(); + + if (I == OldEnd) { + append(First, Last); + } else { + + size_t N = std::distance(First, Last); + assert(size() + N <= capacity()); + + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + if (size_t(OldEnd - I) >= N) { + append(std::make_move_iterator(end() - N), + std::make_move_iterator(end())); + + // Copy the existing elements that get replaced. + std::move_backward(I, OldEnd - N, OldEnd); + + std::copy(First, Last, I); + } else { + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + setSize(size() + N); + size_t NumOverwritten = OldEnd - I; + std::uninitialized_copy(std::make_move_iterator(I), + std::make_move_iterator(OldEnd), + end() - NumOverwritten); + + // Replace the overwritten part. + for (T *J = I; NumOverwritten > 0; --NumOverwritten) { + *J = *First; + ++J; + ++First; + } + + // Insert the non-overwritten middle part. + std::uninitialized_copy(First, Last, OldEnd); + } + } + return I; +} + +template +template < // clang-format off + typename FwdIt, + std::enable_if_t< + is_convertible_forward_iterator::value + > * +> // clang-format on +auto StaticVector::checked_insert(const_iterator Pos, FwdIt First, + FwdIt Last) -> Expected { + if (Pos < cbegin() || Pos > cend()) + return createStringError(std::errc::invalid_argument, + "insert position is out of bounds"); + + if (size() + std::distance(First, Last) > capacity()) + return createStringError(std::errc::bad_address, "insert exceeds capacity"); + + return insert(Pos, First, Last); +} + +/// +/// Insert a copy of values in the specified container before the +/// specified position. +/// +/// \note Shortcut method for common call: +/// `insert(Pos, container.begin(), container.end());` +/// +/// \param Pos Position in the `StaticVector` to insert before. +/// \param Container Container whose contents to insert before `Pos`. +/// +/// \return `Pos` if `Container` is empty; otherwise an `iterator` which +/// represents the first newly inserted item. +/// +/// \note Complexity = O(m + n); +/// where `m` is the number of items between `Pos` and `end()`. +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::insert(const_iterator Pos, + ContainerT &&Container) -> iterator { + return insert(Pos, adl_begin(Container), adl_end(Container)); +} + +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::checked_insert(const_iterator Pos, + ContainerT &&Container) + -> Expected { + return checked_insert(Pos, adl_begin(Container), adl_end(Container)); +} + +/// +/// Append `N` new elements before the specified position. +/// +/// \param N Number of elements to append. +/// \param Val Object to copy-construct into new elements inserted. +/// +/// \return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// \note Complexity = O(N) +/// +template +inline auto StaticVector::append(size_type N, ValueParamT Val) + -> iterator { + auto I = end(); + resize_emplace(size() + N, Val); + return I; +} + +template +inline auto StaticVector::checked_append(size_type N, ValueParamT Val) + -> Expected { + auto I = end(); + if (auto E = checked_resize_emplace(size() + N, Val)) + return E; + return I; +} + +/// +/// Append copies of values in a range. +/// +/// \param First First position in the range to copy +/// \param Last One-past the last position to copy. +/// +/// \note Complexity = O(std::distance(First, Last)) +/// +template +template < // clang-format off + typename InputIt, + std::enable_if_t< + is_convertible_input_iterator::value + > * +> // clang-format on +auto StaticVector::append(InputIt First, InputIt Last) -> iterator { + auto *NewElemPos = end(); + auto *NewEnd = std::uninitialized_copy(First, Last, NewElemPos); + setSize(std::distance(begin(), NewEnd)); + + return NewElemPos; +} + +template +template < + typename InputIt, + std::enable_if_t::value> *> +auto StaticVector::checked_append(InputIt First, InputIt Last) + -> Expected { + if (std::distance(First, Last) + size() > capacity()) + return createStringError(std::errc::invalid_argument, + "append exceeds capacity"); + + return append(First, Last); +} + +/// +/// Append copies of elements in a `std::initializer_list` holding a type which +/// is convertible to `T`. +/// +/// \param IL initializer_list to append copies from. +/// +/// \note Complexity = O(n) +/// +template +template ::value> *> +inline auto StaticVector::append(std::initializer_list IL) + -> iterator { + return append(IL.begin(), IL.end()); +} + +template +template ::value> *> +inline auto StaticVector::checked_append(std::initializer_list IL) + -> Expected { + if (IL.size() + size() > capacity()) { + return createStringError(std::errc::bad_address, + "append exceeds capacity."); + } + + return append(IL); +} + +/// +/// Append copies of elements in an arbitrary container holding a type which is +/// convertible to `T`. +/// +/// \param Container The container to append copies from. +/// +/// \note Complexity = O(n) +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_input_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::append(ContainerT &&Container) -> iterator { + auto B = adl_begin(Container); + auto E = adl_end(Container); + + using IterT = + std::conditional_t::value, + std::move_iterator, decltype(B)>; + + return append(IterT(B), IterT(E)); +} + +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::checked_append(ContainerT &&Container) + -> Expected { + auto B = adl_begin(Container); + auto E = adl_end(Container); + + if (get_container_size()(Container) + size() > capacity()) { + return createStringError(std::errc::invalid_argument, + "append exceeds capacity"); + } + + using IterT = + std::conditional_t::value, + std::move_iterator, decltype(B)>; + + return append(IterT(B), IterT(E)); +} + +/// +/// Mark the current `StaticVector` as empty and destroy all elememts. +/// +/// \note Complexity = O(1) if `T` is trivially destructible; +/// O(n) otherwise. +/// +template inline void StaticVector::clear() { + destroyRange(begin(), end()); + setSize(0); +} + +/// +/// Decrease the size of the container by `1`, removing the last element. +/// +/// Asserts if the container is `Empty()`. +/// +/// \note Complexity = O(1) +/// +template inline void StaticVector::pop_back() { + assert(size() >= 1); + setSize(size() - 1); + destroy(end()); +} + +template +inline auto StaticVector::checked_pop_back() -> Error { + if (size() < 1) { + return createStringError(std::errc::bad_address, "popped empty"); + } + + pop_back(); + return Error::success(); +} + +/// +/// Decrease the size of the container by `N`, removing the last elements. +/// +/// Asserts if the container does not have `N` elements to remove. +/// +/// \note Complexity = O(1) +/// +template +inline void StaticVector::pop_back_n(size_type N) { + assert(size() >= N); + destroyRange(end() - N, end()); + setSize(size() - N); +} + +template +inline auto StaticVector::checked_pop_back_n(size_type N) -> Error { + if (size() < N) { + return createStringError(std::errc::invalid_argument, + "popped too many elements"); + } + + pop_back_n(N); + return Error::success(); +} + +/// +/// Decrease the size of the container by `1`, removing the last element. +/// +/// Asserts if the container is `empty()`. +/// +/// \note Complexity = O(1) +/// +template +inline auto StaticVector::pop_back_val() -> value_type { + auto OldBack = back(); + pop_back(); + return OldBack; +} + +template +inline auto StaticVector::checked_pop_back_val() -> Expected { + if (empty()) { + return createStringError(std::errc::bad_address, "popped empty"); + } + + return pop_back_val(); +} + +/// +/// Erase a single element at a specified position from the +/// `StaticVector`. +/// +/// If `Pos == end()`, then no member is removed. +/// +/// \param Pos Position of the element to erase from the `StaticVector`. +/// +/// \return An `iterator` referring to the new location of the element that +/// followed the erased element. This is `end()` if the operation erased +/// the last element. +/// +/// \note Complexity = O(m); where `m` is the number of items between `Pos` +/// and `end()`. +/// +template +auto StaticVector::erase(const_iterator Pos) -> iterator { + assert(Pos >= cbegin()); + assert(Pos <= cend()); + + auto I = const_cast(Pos); + if (I != cend()) { + std::move(I + 1, end(), I); + pop_back(); + } + return I; +} + +template +auto StaticVector::checked_erase(const_iterator First, + const_iterator Last) + -> Expected { + if (First > Last) { + return createStringError(std::errc::invalid_argument, + "malformed erase range"); + } + if (First < cbegin() || Last > cend()) { + return createStringError(std::errc::bad_address, + "erase range beyond container bounds"); + } + + return erase(First, Last); +} + +/// +/// Erase a sequence of elements in the range `[First, Last)` from the +/// `StaticVector`. +/// +/// If `First == Last`, then no member is erased. +/// +/// \param First The first element in the `StaticVector` to erase. +/// \param Last One-past the last element in the `StaticVector` to erase. +/// +/// \return An `iterator` referring to the new location of the element that +/// followed the erased element(s). This is `end()` if the operation +/// erased the last element. +/// +/// \note Complexity = O(m); where `m` is the number of items between `First` +/// and `end()`. +/// +template +auto StaticVector::erase(const_iterator First, const_iterator Last) + -> iterator { + assert(First <= Last); + assert(First >= cbegin() && Last >= cbegin()); + + auto F = const_cast(First); + auto L = const_cast(Last); + + iterator I = std::move(L, end(), F); + destroyRange(I, end()); + setSize(std::distance(begin(), I)); + return F; +} + +template +auto StaticVector::checked_erase(const_iterator Pos) + -> Expected { + if (Pos < cbegin() || Pos > cend()) { + return createStringError(std::errc::bad_address, + "erased element out of range"); + } + + return erase(Pos); +} + +/// +/// Compare two `StaticVector`s for equality. +/// +/// \return `true` if the containers are equal in size and value; `false` +/// otherwise. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator==(StaticVector const &RHS) const { + return size() == RHS.size() && + std::equal(begin(), end(), RHS.begin(), RHS.end()); +} + +/// +/// Compare two `StaticVector`s for inequality. +/// +/// \return `false` if the containers are equal in size and value; `true` +/// otherwise. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator!=(StaticVector const &RHS) const { + return !operator==(RHS); +} + +/// +/// Compare to another `StaticVector` for less-than relation using +/// lexicographical comparison. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator<(StaticVector const &RHS) const { + return std::lexicographical_compare(begin(), end(), RHS.begin(), RHS.end()); +} + +/// +/// Compare to another `StaticVector` for greater-than relation using +/// lexicographical comparison. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator>(StaticVector const &RHS) const { + return RHS.operator<(*this); +} + +/// +/// Compare to another `StaticVector` for less-than or equal relation using +/// lexicographical comparison. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator<=(StaticVector const &RHS) const { + return !RHS.operator<(*this); +} + +/// +/// Compare to another `StaticVector` for greater-than or equal +/// relation using lexicographical comparison. +/// +/// \note Complexity = O(n) +/// +template +inline bool StaticVector::operator>=(StaticVector const &RHS) const { + return !operator<(RHS); +} + +} // namespace llvm + +#endif // LLVM_ADT_STATICVECTOR_H diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h b/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h --- a/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h +++ b/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h @@ -12,7 +12,7 @@ #include "llvm/ADT/APSInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/Optional.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/DebugInfo/CodeView/CVRecord.h" #include "llvm/DebugInfo/CodeView/CodeView.h" @@ -684,7 +684,7 @@ MaxArgs }; - SmallVector ArgIndices; + StaticVector ArgIndices; }; // LF_VFTABLE diff --git a/llvm/include/llvm/Support/YAMLTraits.h b/llvm/include/llvm/Support/YAMLTraits.h --- a/llvm/include/llvm/Support/YAMLTraits.h +++ b/llvm/include/llvm/Support/YAMLTraits.h @@ -12,6 +12,7 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" @@ -1980,6 +1981,11 @@ SmallVectorImpl, std::enable_if_t::flow>::value>> : SequenceTraitsImpl, SequenceElementTraits::flow> {}; +template +struct SequenceTraits< + StaticVector, + std::enable_if_t::flow>::value>> + : SequenceTraitsImpl, SequenceElementTraits::flow> {}; // Sequences of fundamental types use flow formatting. template diff --git a/llvm/lib/Target/X86/X86ISelLowering.cpp b/llvm/lib/Target/X86/X86ISelLowering.cpp --- a/llvm/lib/Target/X86/X86ISelLowering.cpp +++ b/llvm/lib/Target/X86/X86ISelLowering.cpp @@ -23,6 +23,7 @@ #include "X86TargetObjectFile.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringSwitch.h" @@ -28299,7 +28300,7 @@ /* 8 */ 0, /* 9 */ 0, /* a */ 0, /* b */ 0, /* c */ 0, /* d */ 0, /* e */ 0, /* f */ 0}; - SmallVector LUTVec; + StaticVector LUTVec; for (int i = 0; i < NumBytes; ++i) LUTVec.push_back(DAG.getConstant(LUT[i % 16], DL, MVT::i8)); SDValue InRegLUT = DAG.getBuildVector(CurrVT, DL, LUTVec); 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 @@ -68,6 +68,7 @@ SparseBitVectorTest.cpp SparseMultiSetTest.cpp SparseSetTest.cpp + StaticVectorTest.cpp StatisticTest.cpp StringExtrasTest.cpp StringMapTest.cpp diff --git a/llvm/unittests/ADT/StaticVectorTest.cpp b/llvm/unittests/ADT/StaticVectorTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/ADT/StaticVectorTest.cpp @@ -0,0 +1,2340 @@ +//===- llvm/unittest/ADT/StaticVectorTest.cpp -------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/StaticVector.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Support/Compiler.h" +#include "gtest/gtest.h" +#include +#include + +using namespace llvm; + +namespace { + +/// An llvm::ArrayRef derived class which is only forward iterable via adl begin +/// and end functions. +template class ForceADL : private ArrayRef { + using BaseT = ArrayRef; + +public: + using BaseT::BaseT; + using iterator = typename BaseT::iterator; + + friend iterator begin(ForceADL const &AR) { + return reinterpret_cast(AR).begin(); + } + + friend iterator end(ForceADL const &AR) { + return reinterpret_cast(AR).end(); + } +}; + +/// A helper class that counts the total number of constructor and +/// destructor calls. +class Constructable { +private: + static int numConstructorCalls; + static int numMoveConstructorCalls; + static int numCopyConstructorCalls; + static int numDestructorCalls; + static int numAssignmentCalls; + static int numMoveAssignmentCalls; + static int numCopyAssignmentCalls; + + bool constructed; + int value; + +public: + Constructable() : constructed(true), value(0) { ++numConstructorCalls; } + + Constructable(int val) : constructed(true), value(val) { + ++numConstructorCalls; + } + + Constructable(const Constructable &src) : constructed(true) { + value = src.value; + ++numConstructorCalls; + ++numCopyConstructorCalls; + } + + Constructable(Constructable &&src) : constructed(true) { + value = src.value; + src.value = 0; + ++numConstructorCalls; + ++numMoveConstructorCalls; + } + + ~Constructable() { + EXPECT_TRUE(constructed); + ++numDestructorCalls; + constructed = false; + } + + Constructable &operator=(const Constructable &src) { + EXPECT_TRUE(constructed); + value = src.value; + ++numAssignmentCalls; + ++numCopyAssignmentCalls; + return *this; + } + + Constructable &operator=(Constructable &&src) { + EXPECT_TRUE(constructed); + value = src.value; + src.value = 0; + ++numAssignmentCalls; + ++numMoveAssignmentCalls; + return *this; + } + + int getValue() const { return abs(value); } + + static void reset() { + numConstructorCalls = 0; + numMoveConstructorCalls = 0; + numCopyConstructorCalls = 0; + numDestructorCalls = 0; + numAssignmentCalls = 0; + numMoveAssignmentCalls = 0; + numCopyAssignmentCalls = 0; + } + + static int getNumConstructorCalls() { return numConstructorCalls; } + + static int getNumMoveConstructorCalls() { return numMoveConstructorCalls; } + + static int getNumCopyConstructorCalls() { return numCopyConstructorCalls; } + + static int getNumDestructorCalls() { return numDestructorCalls; } + + static int getNumAssignmentCalls() { return numAssignmentCalls; } + + static int getNumMoveAssignmentCalls() { return numMoveAssignmentCalls; } + + static int getNumCopyAssignmentCalls() { return numCopyAssignmentCalls; } + + friend bool operator==(const Constructable &c0, const Constructable &c1) { + return c0.getValue() == c1.getValue(); + } + + friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable &c0, + const Constructable &c1) { + return c0.getValue() != c1.getValue(); + } +}; + +int Constructable::numConstructorCalls; +int Constructable::numCopyConstructorCalls; +int Constructable::numMoveConstructorCalls; +int Constructable::numDestructorCalls; +int Constructable::numAssignmentCalls; +int Constructable::numCopyAssignmentCalls; +int Constructable::numMoveAssignmentCalls; + +struct NonCopyable { + NonCopyable() {} + NonCopyable(NonCopyable &&) {} + NonCopyable &operator=(NonCopyable &&) { return *this; } + +private: + NonCopyable(const NonCopyable &) = delete; + NonCopyable &operator=(const NonCopyable &) = delete; +}; + +LLVM_ATTRIBUTE_USED void CompileTest() { + StaticVector V; + V.resize(42); +} + +class StaticVectorTestBase : public testing::Test { +protected: + void SetUp() override { Constructable::reset(); } + + template void assertEmpty(VectorT &v) { + // Size tests + EXPECT_EQ(0u, v.size()); + EXPECT_TRUE(v.empty()); + + // Iterator tests + EXPECT_TRUE(v.begin() == v.end()); + } + + // Assert that v contains the specified values, in order. + template + void assertValuesInOrder(VectorT &v, llvm::ArrayRef AR) { + EXPECT_EQ(AR.size(), v.size()); + + auto I1 = AR.begin(); + auto E1 = AR.end(); + + auto I2 = v.begin(); + auto E2 = v.end(); + + for (; I1 != E1 && I2 != E2; ++I1, ++I2) { + auto Expected = *I1; + auto Value = I2->getValue(); + EXPECT_EQ(Value, Expected); + } + } + + // Generate a sequence of values to initialize the vector. + template + void makeSequence(VectorT &v, int start, int end) { + for (int i = start; i <= end; ++i) { + v.push_back(Constructable(i)); + } + } +}; + +// Test fixture class +template +class StaticVectorTest : public StaticVectorTestBase { +protected: + VectorT theVector; + VectorT otherVector; +}; + +typedef ::testing::Types, + StaticVector, + StaticVector> + StaticVectorTestTypes; +TYPED_TEST_SUITE(StaticVectorTest, StaticVectorTestTypes, ); + +// Constructor test. +TYPED_TEST(StaticVectorTest, ConstructorNonIterTest) { + SCOPED_TRACE("ConstructorTest"); + this->theVector = StaticVector(2, 2); + this->assertValuesInOrder(this->theVector, {2, 2}); +} + +// Constructor test. +TYPED_TEST(StaticVectorTest, ConstructorIterTest) { + SCOPED_TRACE("ConstructorTest"); + int arr[] = {1, 2, 3}; + this->theVector = + StaticVector(std::begin(arr), std::end(arr)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +// New vector test. +TYPED_TEST(StaticVectorTest, EmptyVectorTest) { + SCOPED_TRACE("EmptyVectorTest"); + this->assertEmpty(this->theVector); + EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend()); + EXPECT_EQ(0, Constructable::getNumConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumDestructorCalls()); +} + +// Simple insertions and deletions. +TYPED_TEST(StaticVectorTest, PushPopTest) { + SCOPED_TRACE("PushPopTest"); + + // Track whether the vector will potentially have to grow. + bool const RequiresGrowth = this->theVector.capacity() < 3; + if (RequiresGrowth) + return; + + // Push an element + this->theVector.emplace_back(1); + + EXPECT_EQ(1, Constructable::getNumConstructorCalls()); + + // Size tests + this->assertValuesInOrder(this->theVector, {1}); + EXPECT_FALSE(this->theVector.begin() == this->theVector.end()); + EXPECT_FALSE(this->theVector.empty()); + + // Push another element + this->theVector.push_back(Constructable(2)); + this->assertValuesInOrder(this->theVector, {1, 2}); + + // Insert at beginning. Reserve space to avoid reference invalidation from + // this->theVector[1]. + this->theVector.insert(this->theVector.begin(), this->theVector[1]); + this->assertValuesInOrder(this->theVector, {2, 1, 2}); + + // Pop one element + this->theVector.pop_back(); + this->assertValuesInOrder(this->theVector, {2, 1}); + + // Pop remaining elements + this->theVector.pop_back_n(2); + this->assertEmpty(this->theVector); + + // Check number of constructor calls. Should be 2 for each list element, + // one for the argument to push_back, one for the argument to insert, + // and one for the list element itself. + EXPECT_EQ(5, Constructable::getNumConstructorCalls()); + EXPECT_EQ(5, Constructable::getNumDestructorCalls()); +} + +// Simple insertions and deletions with error checks. +TYPED_TEST(StaticVectorTest, CheckedPushPopTest) { + SCOPED_TRACE("CheckedPushPopTest"); + auto IL = {0, 0, 0}; + this->theVector.assign(IL); + + // Push an element + { + auto Exp = this->theVector.checked_emplace_back(1); + if (!Exp) { + EXPECT_GT(4u, this->theVector.capacity()); + consumeError(Exp.takeError()); + this->assertValuesInOrder(this->theVector, {0, 0, 0}); + return; + } + + EXPECT_EQ(4, Constructable::getNumConstructorCalls()); + + // Size tests + this->assertValuesInOrder(this->theVector, {0, 0, 0, 1}); + EXPECT_FALSE(this->theVector.begin() == this->theVector.end()); + EXPECT_FALSE(this->theVector.empty()); + } + + // Push another element + { + auto Exp = this->theVector.checked_push_back(Constructable(2)); + + if (!Exp) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(Exp.takeError()); + this->assertValuesInOrder(this->theVector, {0, 0, 0, 1}); + return; + } + this->assertValuesInOrder(this->theVector, {0, 0, 0, 1, 2}); + } + + // Insert at beginning. Reserve space to avoid reference invalidation from + // this->theVector[1]. + { + auto Exp = this->theVector.checked_insert(this->theVector.begin() + 3, + this->theVector[4]); + if (!Exp) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(Exp.takeError()); + this->assertValuesInOrder(this->theVector, {0, 0, 0, 1, 2}); + return; + } + this->assertValuesInOrder(this->theVector, {0, 0, 0, 2, 1, 2}); + } + + // Pop one element + { + auto E = this->theVector.checked_pop_back(); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + return; + } + this->assertValuesInOrder(this->theVector, {0, 0, 0, 2, 1}); + } + + // Try popping too many elements. + { + auto E = this->theVector.checked_pop_back_n(6); + EXPECT_TRUE(bool(E)); + if (E) + return; + + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {0, 0, 0, 2, 1}); + } + + // Pop remaining elements + { + auto E = this->theVector.checked_pop_back_n(5); + EXPECT_FALSE(bool(E)); + if (E) + return; + + consumeError(std::move(E)); + this->assertEmpty(this->theVector); + } + + // Check number of constructor calls. Should be 2 for each list element, + // one for the argument to push_back, one for the argument to insert, + // and one for the list element itself. + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); + EXPECT_EQ(8, Constructable::getNumConstructorCalls()); +} + +// Clear test. +TYPED_TEST(StaticVectorTest, ClearTest) { + SCOPED_TRACE("ClearTest"); + + this->makeSequence(this->theVector, 1, 2); + this->theVector.clear(); + + this->assertEmpty(this->theVector); + EXPECT_EQ(4, Constructable::getNumConstructorCalls()); + EXPECT_EQ(4, Constructable::getNumDestructorCalls()); +} + +// Resize smaller test. +TYPED_TEST(StaticVectorTest, ResizeShrinkTest) { + SCOPED_TRACE("ResizeShrinkTest"); + + this->makeSequence(this->theVector, 1, 3); + this->theVector.resize(1); + + this->assertValuesInOrder(this->theVector, {1}); + EXPECT_EQ(6, Constructable::getNumConstructorCalls()); + EXPECT_EQ(5, Constructable::getNumDestructorCalls()); +} + +// Checked resize smaller test. +TYPED_TEST(StaticVectorTest, CheckedResizeShrinkTest) { + SCOPED_TRACE("CheckedResizeShrinkTest"); + + this->makeSequence(this->theVector, 1, 3); + auto E = this->theVector.checked_resize(1); + EXPECT_FALSE(E); + if (E) { + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } else { + this->assertValuesInOrder(this->theVector, {1}); + EXPECT_EQ(6, Constructable::getNumConstructorCalls()); + EXPECT_EQ(5, Constructable::getNumDestructorCalls()); + } +} + +// Resize bigger test. +TYPED_TEST(StaticVectorTest, ResizeGrowTest) { + SCOPED_TRACE("ResizeGrowTest"); + + this->theVector.resize(2); + + EXPECT_EQ(2, Constructable::getNumConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumDestructorCalls()); + EXPECT_EQ(2u, this->theVector.size()); +} + +// Checked resize bigger test. +TYPED_TEST(StaticVectorTest, CheckedResizeGrowTest) { + SCOPED_TRACE("CheckedResizeGrowTest"); + + if (auto E = this->theVector.checked_resize(6)) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(std::move(E)); + } else { + EXPECT_EQ(6, Constructable::getNumConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumDestructorCalls()); + EXPECT_EQ(6u, this->theVector.size()); + } +} + +// Resize with elements test. +TYPED_TEST(StaticVectorTest, ResizeWithElementsTest) { + this->theVector.resize(2); + + Constructable::reset(); + + this->theVector.resize(4); + + size_t Ctors = Constructable::getNumConstructorCalls(); + EXPECT_TRUE(Ctors == 2); + size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); + EXPECT_TRUE(MoveCtors == 0); + size_t Dtors = Constructable::getNumDestructorCalls(); + EXPECT_TRUE(Dtors == 0); +} + +// Checked resize with elements test. +TYPED_TEST(StaticVectorTest, CheckedResizeWithElementsTest) { + this->theVector.resize(2); + + Constructable::reset(); + + if (auto E = this->theVector.checked_resize(6)) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(std::move(E)); + } else { + size_t Ctors = Constructable::getNumConstructorCalls(); + EXPECT_TRUE(Ctors == 4); + size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); + EXPECT_TRUE(MoveCtors == 0); + size_t Dtors = Constructable::getNumDestructorCalls(); + EXPECT_TRUE(Dtors == 0); + } +} + +// Resize with fill value. +TYPED_TEST(StaticVectorTest, ResizeFillTest) { + SCOPED_TRACE("ResizeFillTest"); + + this->theVector.resize(3, Constructable(77)); + this->assertValuesInOrder(this->theVector, {77, 77, 77}); +} + +// Checked resize with fill value. +TYPED_TEST(StaticVectorTest, CheckedResizeFillTest) { + SCOPED_TRACE("CheckedResizeFillTest"); + + if (auto E = this->theVector.checked_resize(6, Constructable(77))) { + EXPECT_GT(6u, this->theVector.capacity()); + EXPECT_TRUE(this->theVector.empty()); + consumeError(std::move(E)); + } else { + this->assertValuesInOrder(this->theVector, {77, 77, 77, 77, 77, 77}); + } +} + +// Emplace resize with fill value. +TYPED_TEST(StaticVectorTest, EmplaceResizeFillTest) { + SCOPED_TRACE("EmplaceResizeFillTest"); + + this->theVector.resize_emplace(3u, 77); + this->assertValuesInOrder(this->theVector, {77, 77, 77}); +} + +// Checked resize with fill value. +TYPED_TEST(StaticVectorTest, CheckedEmplaceResizeFillTest) { + SCOPED_TRACE("CheckedEmplaceResizeFillTest"); + + if (auto E = this->theVector.checked_resize_emplace(6, 77)) { + EXPECT_GT(6u, this->theVector.capacity()); + EXPECT_TRUE(this->theVector.empty()); + consumeError(std::move(E)); + } else { + this->assertValuesInOrder(this->theVector, {77, 77, 77, 77, 77, 77}); + } +} + +TEST(StaticVectorTest, ResizeForOverwrite) { + // Inline storage. + StaticVector V; + V.push_back(5U); + V.pop_back(); + V.resize_for_overwrite(V.size() + 1U); + EXPECT_EQ(5U, V.back()); + V.pop_back(); + V.resize(V.size() + 1); + EXPECT_EQ(0U, V.back()); +} + +TEST(StaticVectorTest, CheckedResizeForOverwrite) { + // Inline storage. + StaticVector V; + V.push_back(5U); + V.pop_back(); + + { + auto E = V.checked_resize_for_overwrite(V.size() + 1U); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + return; + } + EXPECT_EQ(5u, V.back()); + V.pop_back(); + } + + { + auto E = V.checked_resize(V.size() + 1); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + return; + } + EXPECT_EQ(0u, V.back()); + } + + { + auto E = V.checked_resize_for_overwrite(V.size() + 4); + EXPECT_TRUE(bool(E)); + if (E) { + consumeError(std::move(E)); + } else { + return; + } + } +} + +// Iteration tests. +TYPED_TEST(StaticVectorTest, IterationTest) { + this->makeSequence(this->theVector, 1, 2); + + // Forward Iteration + typename TypeParam::iterator it = this->theVector.begin(); + EXPECT_TRUE(*it == this->theVector.front()); + EXPECT_TRUE(*it == this->theVector[0]); + EXPECT_EQ(1, it->getValue()); + ++it; + EXPECT_TRUE(*it == this->theVector[1]); + EXPECT_TRUE(*it == this->theVector.back()); + EXPECT_EQ(2, it->getValue()); + ++it; + EXPECT_TRUE(it == this->theVector.end()); + --it; + EXPECT_TRUE(*it == this->theVector[1]); + EXPECT_EQ(2, it->getValue()); + --it; + EXPECT_TRUE(*it == this->theVector[0]); + EXPECT_EQ(1, it->getValue()); + + // Reverse Iteration + typename TypeParam::reverse_iterator rit = this->theVector.rbegin(); + EXPECT_TRUE(*rit == this->theVector[1]); + EXPECT_EQ(2, rit->getValue()); + ++rit; + EXPECT_TRUE(*rit == this->theVector[0]); + EXPECT_EQ(1, rit->getValue()); + ++rit; + EXPECT_TRUE(rit == this->theVector.rend()); + --rit; + EXPECT_TRUE(*rit == this->theVector[0]); + EXPECT_EQ(1, rit->getValue()); + --rit; + EXPECT_TRUE(*rit == this->theVector[1]); + EXPECT_EQ(2, rit->getValue()); +} + +// Swap test. +TYPED_TEST(StaticVectorTest, SwapTest) { + SCOPED_TRACE("SwapTest"); + + this->makeSequence(this->theVector, 1, 2); + std::swap(this->theVector, this->otherVector); + + this->assertEmpty(this->theVector); + this->assertValuesInOrder(this->otherVector, {1, 2}); +} + +// Append test +TYPED_TEST(StaticVectorTest, AppendTest) { + SCOPED_TRACE("AppendTest"); + + this->makeSequence(this->otherVector, 2, 3); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(this->otherVector.begin(), this->otherVector.end()); + + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +// Checked append test +TYPED_TEST(StaticVectorTest, CheckedAppendTest) { + SCOPED_TRACE("CheckedAppendTest"); + + this->makeSequence(this->otherVector, 2, 5); + + this->theVector.push_back(Constructable(1)); + auto Exp = this->theVector.checked_append(this->otherVector.begin(), + this->otherVector.end()); + + if (!Exp) { + EXPECT_GT(5, this->theVector.capacity()); + consumeError(Exp.takeError()); + return; + } + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 5}); +} + +// Append repeated test +TYPED_TEST(StaticVectorTest, AppendRepeatedTest) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(2, Constructable(77)); + this->assertValuesInOrder(this->theVector, {1, 77, 77}); +} + +// Checked append repeated test +TYPED_TEST(StaticVectorTest, CheckedAppendRepeatedTest) { + SCOPED_TRACE("CheckedAppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + + { + auto Exp0 = this->theVector.checked_append(2, Constructable(77)); + EXPECT_TRUE(bool(Exp0)); + if (!Exp0) { + EXPECT_GT(3u, this->theVector.capacity()); + consumeError(Exp0.takeError()); + } else { + this->assertValuesInOrder(this->theVector, {1, 77, 77}); + } + } + + { + auto Exp1 = this->theVector.checked_append(2, Constructable(88)); + if (!Exp1) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(Exp1.takeError()); + } else { + this->assertValuesInOrder(this->theVector, {1, 77, 77, 88, 88}); + } + } +} + +// Append test +TYPED_TEST(StaticVectorTest, AppendNonIterTest) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(2, 7); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); +} + +struct output_iterator { + typedef std::output_iterator_tag iterator_category; + typedef int value_type; + typedef int difference_type; + typedef value_type *pointer; + typedef value_type &reference; + operator int() { return 2; } + operator Constructable() { return 7; } +}; + +TYPED_TEST(StaticVectorTest, AppendRepeatedNonForwardIterator) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(output_iterator(), output_iterator()); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendRepeatedNonForwardIterator) { + SCOPED_TRACE("CheckedAppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + auto Exp = + this->theVector.checked_append(output_iterator(), output_iterator()); + EXPECT_TRUE(bool(Exp)); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); +} + +TYPED_TEST(StaticVectorTest, AppendStaticVector) { + SCOPED_TRACE("AppendStaticVector"); + + StaticVector otherVector = {7, 7}; + this->theVector.push_back(Constructable(1)); + auto I = this->theVector.append(otherVector); + EXPECT_EQ(I, this->theVector.begin() + 1); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendStaticVector) { + SCOPED_TRACE("CheckedAppendStaticVector"); + + StaticVector otherVector = {7, 7}; + this->theVector.push_back(Constructable(1)); + auto Exp0 = this->theVector.checked_append(otherVector); + EXPECT_TRUE(bool(Exp0)); + if (!Exp0) { + consumeError(Exp0.takeError()); + this->assertValuesInOrder(this->theVector, {1}); + return; + } else { + EXPECT_EQ(*Exp0, this->theVector.begin() + 1); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); + } + + auto Exp1 = this->theVector.checked_append(otherVector); + if (!Exp1) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(Exp1.takeError()); + this->assertValuesInOrder(this->theVector, {1, 7, 7}); + return; + } else { + EXPECT_EQ(*Exp1, this->theVector.begin() + 3); + this->assertValuesInOrder(this->theVector, {1, 7, 7, 7, 7}); + } +} + +TYPED_TEST(StaticVectorTest, AppendArrayRefTest) { + SCOPED_TRACE("AppendArrayRefTest"); + auto IL = {1, 2, 3}; + ArrayRef AR(IL); + this->theVector.append(AR); + this->assertValuesInOrder(this->theVector, IL); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendArrayRefTest) { + SCOPED_TRACE("CheckedAppendArrayRefTest"); + auto IL = {1, 2, 3}; + ArrayRef AR(IL); + + { + auto Exp = this->theVector.checked_append(AR); + EXPECT_TRUE(bool(Exp)); + if (!Exp) { + EXPECT_TRUE(this->theVector.empty()); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + } + + { + auto Exp = this->theVector.checked_append(AR); + if (!Exp) { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3, 1, 2, 3}); + } + } +} + +TYPED_TEST(StaticVectorTest, AppendInitializerListTest) { + SCOPED_TRACE("AppendInitializerListTest"); + auto IL = {1, 2, 3}; + this->theVector.append(IL); + this->assertValuesInOrder(this->theVector, IL); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendInitializerListTest) { + SCOPED_TRACE("CheckedAppendInitializerListTest"); + auto IL = {1, 2, 3}; + + { + auto Exp = this->theVector.checked_append(IL); + EXPECT_TRUE(bool(Exp)); + if (!Exp) { + EXPECT_TRUE(this->theVector.empty()); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + } + + { + auto Exp = this->theVector.checked_append(IL); + if (!Exp) { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3, 1, 2, 3}); + } + } +} + +TYPED_TEST(StaticVectorTest, AppendContainerADL) { + SCOPED_TRACE("AppendContainerADL"); + int IArr[]{1, 2, 3}; + this->theVector.append(ForceADL(IArr)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendContainerADL) { + SCOPED_TRACE("CheckedAppendContainerADL"); + int IArr[]{1, 2, 3}; + + { + auto Exp = this->theVector.checked_append(ForceADL(IArr)); + EXPECT_TRUE(bool(Exp)); + if (!Exp) { + EXPECT_TRUE(this->theVector.empty()); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + } + + { + auto Exp = this->theVector.checked_append(ForceADL(IArr)); + if (!Exp) { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3, 1, 2, 3}); + } + } +} + +TYPED_TEST(StaticVectorTest, AppendRangeTest) { + SCOPED_TRACE("AppendRangeTest"); + int IArr[]{1, 2, 3}; + this->theVector.append(make_range(std::begin(IArr), std::end(IArr))); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendRangeTest) { + SCOPED_TRACE("CheckedAppendRangeTest"); + int IArr[]{1, 2, 3}; + auto Range = make_range(std::begin(IArr), std::end(IArr)); + + { + auto Exp = this->theVector.checked_append(Range); + EXPECT_TRUE(bool(Exp)); + if (!Exp) { + EXPECT_TRUE(this->theVector.empty()); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + } + + { + auto Exp = this->theVector.checked_append(Range); + if (!Exp) { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3, 1, 2, 3}); + } + } +} + +TYPED_TEST(StaticVectorTest, AppendCArrayTest) { + SCOPED_TRACE("AppendCArrayTest"); + const int IArr[]{1, 2, 3}; + this->theVector.append(IArr); + this->assertValuesInOrder(this->theVector, IArr); +} + +TYPED_TEST(StaticVectorTest, CheckedAppendCArrayTest) { + SCOPED_TRACE("CheckedAppendCArrayTest"); + const int IArr[]{1, 2, 3}; + + { + auto Exp = this->theVector.checked_append(IArr); + EXPECT_TRUE(bool(Exp)); + if (!Exp) { + EXPECT_TRUE(this->theVector.empty()); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + } + + { + auto Exp = this->theVector.checked_append(IArr); + if (!Exp) { + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + consumeError(Exp.takeError()); + return; + } else { + this->assertValuesInOrder(this->theVector, {1, 2, 3, 1, 2, 3}); + } + } +} + +// Assign test +TYPED_TEST(StaticVectorTest, AssignTest) { + SCOPED_TRACE("AssignTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.assign(2, Constructable(77)); + this->assertValuesInOrder(this->theVector, {77, 77}); +} + +// Checked assign test +TYPED_TEST(StaticVectorTest, CheckedAssignTest) { + SCOPED_TRACE("CheckedAssignTest"); + + this->theVector.push_back(Constructable(1)); + + { + auto E = this->theVector.checked_assign(2u, Constructable(77)); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + return; + } else { + this->assertValuesInOrder(this->theVector, {77, 77}); + } + } + + { + auto E = this->theVector.checked_assign(5u, Constructable(99)); + if (E) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {77, 77}); + return; + } + + this->assertValuesInOrder(this->theVector, {99, 99, 99, 99, 99}); + } +} + +// Assign range test +TYPED_TEST(StaticVectorTest, AssignRangeTest) { + SCOPED_TRACE("AssignRangeTest"); + + this->theVector.push_back(Constructable(1)); + int arr[] = {1, 2, 3}; + this->theVector.assign(std::begin(arr), std::end(arr)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +// Checked assign range test +TYPED_TEST(StaticVectorTest, CheckedAssignRangeTest) { + SCOPED_TRACE("CheckedAssignRangeTest"); + + this->theVector.push_back(Constructable(1)); + + { + int Arr[] = {1, 2, 3}; + + auto E = this->theVector.checked_assign(std::begin(Arr), std::end(Arr)); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {1}); + return; + } + + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + + { + int Arr[] = {1, 2, 3, 4, 5}; + + auto E = this->theVector.checked_assign(std::begin(Arr), std::end(Arr)); + if (E) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + return; + } + + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 5}); + } +} + +// Assign test +TYPED_TEST(StaticVectorTest, AssignNonIterTest) { + SCOPED_TRACE("AssignNonIterTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.assign(2, 7); + this->assertValuesInOrder(this->theVector, {7, 7}); +} + +// Checked assign test +TYPED_TEST(StaticVectorTest, CheckedAssignNonIterTest) { + SCOPED_TRACE("CheckedAssignNonIterTest"); + + this->theVector.push_back(Constructable(1)); + + { + auto E = this->theVector.checked_assign(2, 7); + EXPECT_FALSE(bool(E)); + if (E) { + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, {7, 7}); + } + + { + auto E = this->theVector.checked_assign(5, 9); + if (E) { + EXPECT_GT(5u, this->theVector.capacity()); + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {7, 7}); + return; + } + + this->assertValuesInOrder(this->theVector, {9, 9, 9, 9, 9}); + } +} + +TYPED_TEST(StaticVectorTest, AssignStaticVector) { + SCOPED_TRACE("AssignStaticVector"); + + StaticVector otherVector = {7, 7}; + this->theVector.push_back(Constructable(1)); + this->theVector.assign(otherVector); + this->assertValuesInOrder(this->theVector, {7, 7}); +} + +TYPED_TEST(StaticVectorTest, CheckedAssignStaticVector) { + SCOPED_TRACE("CheckedAssignStaticVector"); + StaticVector otherVector; + this->theVector.push_back(Constructable(1)); + + { + otherVector = {7, 7}; + + auto E = this->theVector.checked_assign(otherVector); + EXPECT_FALSE(E); + if (E) { + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, {7, 7}); + } + + { + otherVector = {1, 2, 3, 4, 5, 6}; + + auto E = this->theVector.checked_assign(otherVector); + if (E) { + EXPECT_GT(otherVector.size(), this->theVector.capacity()); + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 5, 6}); + } +} + +TYPED_TEST(StaticVectorTest, AssignCArrayVector) { + SCOPED_TRACE("AssignCArrayVector"); + + int Arr[]{1, 3, 5}; + + this->theVector.emplace_back(1); + + // Use the assign() member function to assign. + this->theVector.assign(Arr); + this->assertValuesInOrder(this->theVector, Arr); + + this->theVector.clear(); + this->theVector.emplace_back(1); + + // Use operator=() to assign. + this->theVector = Arr; + this->assertValuesInOrder(this->theVector, Arr); +} + +TYPED_TEST(StaticVectorTest, CheckedAssignCArrayVector) { + SCOPED_TRACE("CheckedAssignCArrayVector"); + + this->theVector.emplace_back(1); + + // Use the assign() member function to assign. + { + int Arr[]{1, 3, 5}; + + auto E = this->theVector.checked_assign(Arr); + EXPECT_FALSE(E); + if (E) { + consumeError(std::move(E)); + return; + } + this->assertValuesInOrder(this->theVector, Arr); + } + + { + int Arr[]{1, 3, 5, 7, 9}; + + auto E = this->theVector.checked_assign(Arr); + if (E) { + EXPECT_GT(std::extent::value, this->theVector.capacity()); + consumeError(std::move(E)); + this->assertValuesInOrder(this->theVector, {1, 3, 5}); + return; + } + this->assertValuesInOrder(this->theVector, Arr); + } +} + +TYPED_TEST(StaticVectorTest, AssignInitializerList) { + SCOPED_TRACE("AssignInitializerList"); + + this->theVector.emplace_back(1); + this->theVector.assign({2, 4, 6, 8}); + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); + + this->theVector.clear(); + this->theVector.emplace_back(1); + this->theVector = {2, 4, 6, 8}; + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); +} + +TYPED_TEST(StaticVectorTest, CheckedAssignInitializerList) { + SCOPED_TRACE("CheckedAssignInitializerList"); + + { + auto IL = {2, 4, 6, 8}; + this->theVector.emplace_back(1); + auto E = this->theVector.checked_assign(IL); + EXPECT_FALSE(E); + + if (E) { + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, IL); + } + + { + auto IL = {3, 6, 5, 7, 9, 11}; + auto E = this->theVector.checked_assign(IL); + + if (E) { + EXPECT_GT(IL.size(), this->theVector.capacity()); + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, IL); + } +} + +TYPED_TEST(StaticVectorTest, AssignArrayRef) { + SCOPED_TRACE("AssignArrayRef"); + + auto IL = {2, 4, 6, 8}; + ArrayRef AR(IL); + + this->theVector.emplace_back(1); + this->theVector.assign(AR); + this->assertValuesInOrder(this->theVector, AR); + + this->theVector.clear(); + + this->theVector.emplace_back(1); + this->theVector = AR; + this->assertValuesInOrder(this->theVector, AR); +} + +TYPED_TEST(StaticVectorTest, CheckedAssignArrayRef) { + SCOPED_TRACE("CheckedAssignArrayRef"); + + { + auto IL = {2, 4, 6, 8}; + ArrayRef AR(IL); + + this->theVector.emplace_back(1); + auto E = this->theVector.checked_assign(AR); + EXPECT_FALSE(E); + + if (E) { + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, AR); + } + + { + auto IL = {3, 6, 5, 7, 9, 11}; + ArrayRef AR(IL); + + auto E = this->theVector.checked_assign(AR); + + if (E) { + EXPECT_GT(IL.size(), this->theVector.capacity()); + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); + consumeError(std::move(E)); + return; + } + + this->assertValuesInOrder(this->theVector, AR); + } +} + +// Move-assign test +TYPED_TEST(StaticVectorTest, MoveAssignTest) { + SCOPED_TRACE("MoveAssignTest"); + + // Set up our vector with a single element, but enough capacity for 4. + this->theVector.emplace_back(1); + + // Set up the other vector with 2 elements. + this->otherVector.push_back(Constructable(2)); + this->otherVector.push_back(Constructable(3)); + + // Move-assign from the other vector. + this->theVector = std::move(this->otherVector); + + // Make sure we have the right result. + this->assertValuesInOrder(this->theVector, {2, 3}); + + // Make sure the # of constructor/destructor calls line up. There + // are two live objects after clearing the other vector. + this->otherVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls() - 2, + Constructable::getNumDestructorCalls()); + + // There shouldn't be any live objects any more. + this->theVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); +} + +// Checked move-assign test +TYPED_TEST(StaticVectorTest, CheckedMoveAssignTest) { + SCOPED_TRACE("CheckedMoveAssignTest"); + + // Set up our vector with a single element, but enough capacity for 4. + this->theVector.emplace_back(1); + + // Set up the other vector with 2 elements. + this->otherVector.emplace_back(2); + this->otherVector.emplace_back(3); + + // Move-assign from the other vector. + auto E = this->theVector.checked_assign(std::move(this->otherVector)); + EXPECT_FALSE(bool(E)); + + if (E) { + consumeError(std::move(E)); + return; + } + + // Make sure we have the right result. + this->assertValuesInOrder(this->theVector, {2, 3}); + + // Make sure the # of constructor/destructor calls line up. There + // are two live objects after clearing the other vector. + this->otherVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls() - 2, + Constructable::getNumDestructorCalls()); + + // There shouldn't be any live objects any more. + this->theVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); +} + +// Erase a single element +TYPED_TEST(StaticVectorTest, EraseTest) { + SCOPED_TRACE("EraseTest"); + + this->makeSequence(this->theVector, 1, 3); + const auto &theConstVector = this->theVector; + auto I = this->theVector.erase(theConstVector.begin()); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {2, 3}); +} + +// Erase a single element +TYPED_TEST(StaticVectorTest, CheckedEraseTest) { + SCOPED_TRACE("CheckedEraseTest"); + + this->makeSequence(this->theVector, 1, 3); + const auto &theConstVector = this->theVector; + + { + auto Exp = this->theVector.checked_erase(theConstVector.begin()); + EXPECT_TRUE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + return; + } else { + EXPECT_EQ(*Exp, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {2, 3}); + } + } + + // Erase end() (do nothing). + { + auto Exp = this->theVector.checked_erase(theConstVector.end()); + EXPECT_TRUE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + return; + } else { + EXPECT_EQ(*Exp, this->theVector.end()); + this->assertValuesInOrder(this->theVector, {2, 3}); + } + } + + // Erase out of bounds (after buffer). + { + auto Exp = this->theVector.checked_erase(theConstVector.end() + 1); + EXPECT_FALSE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + this->assertValuesInOrder(this->theVector, {2, 3}); + } else { + return; + } + } + + // Erase out of bounds (before buffer). + { + auto Exp = this->theVector.checked_erase(theConstVector.begin() - 1); + EXPECT_FALSE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + this->assertValuesInOrder(this->theVector, {2, 3}); + } else { + return; + } + } +} + +// Erase a range of elements +TYPED_TEST(StaticVectorTest, EraseRangeTest) { + SCOPED_TRACE("EraseRangeTest"); + + this->makeSequence(this->theVector, 1, 3); + const auto &theConstVector = this->theVector; + this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2); + this->assertValuesInOrder(this->theVector, {3}); +} + +// Erase a range of elements +TYPED_TEST(StaticVectorTest, CheckedEraseRangeTest) { + SCOPED_TRACE("CheckedEraseRangeTest"); + + { + this->theVector.clear(); + this->makeSequence(this->theVector, 1, 3); + + auto Exp = this->theVector.checked_erase(this->theVector.cbegin(), + this->theVector.cbegin() + 2); + EXPECT_TRUE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + return; + } + + this->assertValuesInOrder(this->theVector, {3}); + } + + // Erase empty range at end() (do nothing). + { + this->theVector.clear(); + this->makeSequence(this->theVector, 1, 3); + + auto Exp = this->theVector.checked_erase(this->theVector.cend(), + this->theVector.cend()); + EXPECT_TRUE(bool(Exp)); + + if (!Exp) { + consumeError(Exp.takeError()); + return; + } + + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + + // Erase invalid range past end(). + { + auto Exp = this->theVector.checked_erase(this->theVector.cbegin() + 1, + this->theVector.cend() + 1); + EXPECT_FALSE(bool(Exp)); + + if (Exp) { + return; + } + + consumeError(Exp.takeError()); + + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } + + // Erase invalid range before begin(). + { + auto Exp = this->theVector.checked_erase(this->theVector.cbegin() - 1, + this->theVector.cbegin() + 1); + EXPECT_FALSE(bool(Exp)); + + if (Exp) { + return; + } + + consumeError(Exp.takeError()); + + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + } +} + +// Insert a single element. +TYPED_TEST(StaticVectorTest, InsertTest) { + SCOPED_TRACE("InsertTest"); + + this->makeSequence(this->theVector, 1, 3); + typename TypeParam::iterator I = + this->theVector.insert(this->theVector.begin() + 1, Constructable(77)); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); +} + +// Checked insert a single element. +TYPED_TEST(StaticVectorTest, CheckedInsertTest) { + SCOPED_TRACE("CheckedInsertTest"); + + this->makeSequence(this->theVector, 1, 3); + + { + Expected I = this->theVector.checked_insert( + this->theVector.cbegin() + 1, Constructable(77)); + EXPECT_TRUE(bool(I)); + + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 1, *I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); + } + + // Potentially exceed capacity. + { + Expected I = this->theVector.checked_insert( + this->theVector.cbegin() + 3, Constructable(99)); + + if (!I) { + EXPECT_GT(5u, this->theVector.capacity()); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 3, *I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 99, 3}); + } + + // Insert out of bounds. + { + Expected I = this->theVector.checked_insert( + this->theVector.cbegin() + 6, Constructable(1010)); + + EXPECT_FALSE(bool(I)); + if (I) { + return; + } + + consumeError(I.takeError()); + + this->assertValuesInOrder(this->theVector, {1, 77, 2, 99, 3}); + } +} + +// Insert a copy of a single element. +TYPED_TEST(StaticVectorTest, InsertCopy) { + SCOPED_TRACE("InsertTest"); + + this->makeSequence(this->theVector, 1, 3); + Constructable C(77); + typename TypeParam::iterator I = + this->theVector.insert(this->theVector.begin() + 1, C); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); +} + +// Checked insert a copy of a single element. +TYPED_TEST(StaticVectorTest, CheckedInsertCopy) { + SCOPED_TRACE("CheckedInsertTest"); + + this->makeSequence(this->theVector, 1, 3); + + { + Constructable Ins(77); + Expected I = + this->theVector.checked_insert(this->theVector.cbegin() + 1, Ins); + EXPECT_TRUE(bool(I)); + + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 1, *I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); + } + + // Potentially exceed capacity. + { + Constructable Ins(99); + Expected I = + this->theVector.checked_insert(this->theVector.cbegin() + 3, Ins); + + if (!I) { + EXPECT_GT(5u, this->theVector.capacity()); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 3, *I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 99, 3}); + } + + // Insert out of bounds. + { + Constructable Ins(1010); + Expected I = + this->theVector.checked_insert(this->theVector.cbegin() + 6, Ins); + + EXPECT_FALSE(bool(I)); + if (I) { + return; + } + + consumeError(I.takeError()); + + this->assertValuesInOrder(this->theVector, {1, 77, 2, 99, 3}); + } +} + +// Insert repeated elements. +TYPED_TEST(StaticVectorTest, InsertRepeatedTest) { + SCOPED_TRACE("InsertRepeatedTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.begin() + 1, 2u, + Constructable(16)); + // Move construct the top element into newly allocated space, and optionally + // reallocate the whole buffer, move constructing into it. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 4 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 6); + // Move assign the next two to shift them up and make a gap. + EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); + // Copy construct the two new elements from the parameter. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // All without any copy construction. + EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 16, 16, 2, 3, 4}); +} + +// Checked insert repeated elements. +TYPED_TEST(StaticVectorTest, CheckedInsertRepeatedTest) { + SCOPED_TRACE("CheckedInsertRepeatedTest"); + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + + auto I = this->theVector.checked_insert(this->theVector.begin() + 1, 2u, + Constructable(16)); + + if (!I) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(I.takeError()); + return; + } + + // Move construct the top element into newly allocated space, and optionally + // reallocate the whole buffer, move constructing into it. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 4 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 6); + // Move assign the next two to shift them up and make a gap. + EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); + // Copy construct the two new elements from the parameter. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // All without any copy construction. + EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, *I); + this->assertValuesInOrder(this->theVector, {1, 16, 16, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedNonIterTest) { + SCOPED_TRACE("InsertRepeatedNonIterTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 7, 7, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, CheckedInsertRepeatedNonIterTest) { + SCOPED_TRACE("CheckedInsertRepeatedNonIterTest"); + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + + auto I = this->theVector.checked_insert(this->theVector.begin() + 1, 2u, 7); + if (!I) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 1, *I); + this->assertValuesInOrder(this->theVector, {1, 7, 7, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedAtEndTest) { + SCOPED_TRACE("InsertRepeatedAtEndTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16)); + // Just copy construct them into newly allocated space + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + // Move everything across if reallocation is needed. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || + Constructable::getNumMoveConstructorCalls() == 4); + // Without ever moving or copying anything else. + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + + EXPECT_EQ(this->theVector.begin() + 4, I); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 16, 16}); +} + +TYPED_TEST(StaticVectorTest, CheckedInsertRepeatedAtEndTest) { + SCOPED_TRACE("CheckedInsertRepeatedAtEndTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + + auto I = this->theVector.checked_insert(this->theVector.end(), 2u, + Constructable(16)); + + if (!I) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(I.takeError()); + return; + } + + // Just copy construct them into newly allocated space + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + // Move everything across if reallocation is needed. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || + Constructable::getNumMoveConstructorCalls() == 4); + // Without ever moving or copying anything else. + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + + EXPECT_EQ(this->theVector.begin() + 4, *I); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 16, 16}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedEmptyTest) { + SCOPED_TRACE("InsertRepeatedEmptyTest"); + + if (this->theVector.capacity() < 4) + return; + + auto I = this->theVector.insert(this->theVector.end(), 2, 10); + EXPECT_EQ(I, this->theVector.begin()); + EXPECT_EQ(0, Constructable::getNumMoveConstructorCalls()); + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + this->assertValuesInOrder(this->theVector, {10, 10}); + + this->makeSequence(this->theVector, 12, 13); + + // Empty insert. + EXPECT_EQ( + this->theVector.end(), + this->theVector.insert(this->theVector.end(), 0, Constructable(42))); + EXPECT_EQ(this->theVector.begin() + 1, + this->theVector.insert(this->theVector.begin() + 1, 0, + Constructable(42))); +} + +TYPED_TEST(StaticVectorTest, CheckedInsertRepeatedEmptyTest) { + SCOPED_TRACE("CheckedInsertRepeatedEmptyTest"); + + { + auto I = this->theVector.checked_insert(this->theVector.end(), 2, 10); + + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(*I, this->theVector.begin()); + EXPECT_EQ(0, Constructable::getNumMoveConstructorCalls()); + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + this->assertValuesInOrder(this->theVector, {10, 10}); + } + + this->makeSequence(this->theVector, 12, 13); + + // Empty insert. + { + auto I = this->theVector.checked_insert(this->theVector.cend(), 0, + Constructable(42)); + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.end(), *I); + } + + // Empty insert. + { + auto I = this->theVector.checked_insert(this->theVector.cbegin() + 1, 0, + Constructable(42)); + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 1, *I); + } +} + +// Insert range. +TYPED_TEST(StaticVectorTest, InsertRangeTest) { + SCOPED_TRACE("InsertRangeTest"); + + if (this->theVector.capacity() < 6) + return; + + Constructable Arr[3] = {Constructable(77), Constructable(77), + Constructable(77)}; + + this->makeSequence(this->theVector, 1, 3); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); + // Move construct the top 3 elements into newly allocated space. + // Possibly move the whole sequence into new space first. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 3 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 5); + // Copy assign the lower 2 new elements into existing space. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // Copy construct the third element into newly allocated space. + EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 77, 77, 77, 2, 3}); +} + +// Insert range. +TYPED_TEST(StaticVectorTest, CheckedInsertRangeTest) { + SCOPED_TRACE("CheckedInsertRangeTest"); + + Constructable Arr[3] = {Constructable(77), Constructable(77), + Constructable(77)}; + + this->makeSequence(this->theVector, 1, 3); + Constructable::reset(); + + auto I = + this->theVector.checked_insert(this->theVector.begin() + 1, Arr, Arr + 3); + + if (!I) { + EXPECT_GT(6u, this->theVector.capacity()); + consumeError(I.takeError()); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); + return; + } + + // Move construct the top 3 elements into newly allocated space. + // Possibly move the whole sequence into new space first. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 3 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 5); + // Copy assign the lower 2 new elements into existing space. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // Copy construct the third element into newly allocated space. + EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, *I); + + this->assertValuesInOrder(this->theVector, {1, 77, 77, 77, 2, 3}); +} + +TYPED_TEST(StaticVectorTest, InsertRangeAtEndTest) { + SCOPED_TRACE("InsertRangeAtEndTest"); + + if (this->theVector.capacity() < 6) + return; + + Constructable Arr[3] = {Constructable(77), Constructable(77), + Constructable(77)}; + + this->makeSequence(this->theVector, 1, 3); + + // Insert at end. + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.end(), Arr, Arr + 3); + // Copy construct the 3 elements into new space at the top. + EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); + // Don't copy/move anything else. + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + // Reallocation might occur, causing all elements to be moved into the new + // buffer. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || + Constructable::getNumMoveConstructorCalls() == 3); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(this->theVector.begin() + 3, I); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 77, 77, 77}); +} + +TYPED_TEST(StaticVectorTest, InsertEmptyRangeTest) { + SCOPED_TRACE("InsertRangeTest"); + auto IL = {1, 2, 3}; + auto I = + this->theVector.insert(this->theVector.begin(), IL.begin(), IL.end()); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, IL); + + // Empty insert. + EXPECT_EQ(this->theVector.end(), + this->theVector.insert(this->theVector.end(), + this->theVector.begin(), + this->theVector.begin())); + EXPECT_EQ(this->theVector.begin() + 1, + this->theVector.insert(this->theVector.begin() + 1, + this->theVector.begin(), + this->theVector.begin())); +} + +TYPED_TEST(StaticVectorTest, CheckedInsertEmptyRangeTest) { + SCOPED_TRACE("CheckedInsertRangeTest"); + auto IL = {1, 2, 3}; + + { + auto I = this->theVector.checked_insert(this->theVector.cbegin(), + IL.begin(), IL.end()); + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(*I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, IL); + } + + // Empty insert. + { + auto I = this->theVector.checked_insert(this->theVector.cend(), + this->theVector.cbegin(), + this->theVector.cbegin()); + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.end(), *I); + } + + // Empty insert. + { + auto I = this->theVector.checked_insert(this->theVector.cbegin() + 1, + this->theVector.begin(), + this->theVector.begin()); + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(this->theVector.begin() + 1, *I); + } +} + +TYPED_TEST(StaticVectorTest, InsertCArrayTest) { + SCOPED_TRACE("InsertCArrayTest"); + const int Arr[]{1, 2, 3}; + + this->theVector.emplace_back(4); + + auto I = this->theVector.insert(this->theVector.begin(), Arr); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertInializerListTest) { + SCOPED_TRACE("InsertInializerListTest"); + auto IL = {1, 2, 3}; + + this->theVector.emplace_back(4); + + auto I = this->theVector.insert(this->theVector.begin(), IL); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertArrayRefTest) { + SCOPED_TRACE("InsertArrayRefTest"); + auto IL = {2, 3, 4}; + + this->theVector.emplace_back(1); + + auto I = this->theVector.insert(this->theVector.end(), IL); + EXPECT_EQ(I, this->theVector.begin() + 1); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +// Comparison tests. +TYPED_TEST(StaticVectorTest, ComparisonTest) { + SCOPED_TRACE("ComparisonTest"); + + this->makeSequence(this->theVector, 1, 3); + this->makeSequence(this->otherVector, 1, 3); + + EXPECT_TRUE(this->theVector == this->otherVector); + EXPECT_FALSE(this->theVector != this->otherVector); + + this->otherVector.clear(); + this->makeSequence(this->otherVector, 2, 4); + + EXPECT_FALSE(this->theVector == this->otherVector); + EXPECT_TRUE(this->theVector != this->otherVector); +} + +// Constant vector tests. +TYPED_TEST(StaticVectorTest, ConstVectorTest) { + const TypeParam constVector; + + EXPECT_EQ(0u, constVector.size()); + EXPECT_TRUE(constVector.empty()); + EXPECT_TRUE(constVector.begin() == constVector.end()); +} + +// Direct array access. +TYPED_TEST(StaticVectorTest, DirectVectorTest) { + EXPECT_EQ(0u, this->theVector.size()); + // this->theVector.reserve(4); + // if (this->theVector.capacity() < 4U) + // return; + EXPECT_LE(4u, this->theVector.capacity()); + EXPECT_EQ(0, Constructable::getNumConstructorCalls()); + this->theVector.push_back(1); + this->theVector.push_back(2); + this->theVector.push_back(3); + this->theVector.push_back(4); + EXPECT_EQ(4u, this->theVector.size()); + EXPECT_EQ(8, Constructable::getNumConstructorCalls()); + EXPECT_EQ(1, this->theVector[0].getValue()); + EXPECT_EQ(2, this->theVector[1].getValue()); + EXPECT_EQ(3, this->theVector[2].getValue()); + EXPECT_EQ(4, this->theVector[3].getValue()); +} + +TYPED_TEST(StaticVectorTest, IteratorTest) { + std::list L; + this->theVector.insert(this->theVector.end(), L.begin(), L.end()); +} + +TYPED_TEST(StaticVectorTest, CheckedIteratorTest) { + std::list L; + auto I = + this->theVector.checked_insert(this->theVector.end(), L.begin(), L.end()); + EXPECT_TRUE(bool(I)); + if (!I) + consumeError(I.takeError()); +} + +template class DualStaticVectorsTest; + +template +class DualStaticVectorsTest> + : public StaticVectorTestBase { +protected: + VectorT1 theVector; + VectorT2 otherVector; + + template + static unsigned NumBuiltinElts(const StaticVector &) { + return N; + } +}; + +typedef ::testing::Types< + // Small mode -> Small mode. + std::pair, StaticVector>, + std::pair, StaticVector>> + DualStaticVectorTestTypes; + +TYPED_TEST_SUITE(DualStaticVectorsTest, DualStaticVectorTestTypes, ); + +TYPED_TEST(DualStaticVectorsTest, MoveAssignment) { + SCOPED_TRACE("MoveAssignTest-DualVectorTypes"); + + // Set up our vector with four elements. + for (unsigned I = 0; I < 4; ++I) + this->otherVector.push_back(Constructable(I)); + + const Constructable *OrigDataPtr = this->otherVector.data(); + + // Move-assign from the other vector. + this->theVector = std::move(this->otherVector); + + // Make sure we have the right result. + this->assertValuesInOrder(this->theVector, {0, 1, 2, 3}); + + // Make sure the # of constructor/destructor calls line up. There + // are two live objects after clearing the other vector. + this->otherVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls() - 4, + Constructable::getNumDestructorCalls()); + + // If the source vector (otherVector) was in small-mode, assert that we just + // moved the data pointer over. + EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 || + this->theVector.data() == OrigDataPtr); + + // There shouldn't be any live objects any more. + this->theVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); + + // We shouldn't have copied anything in this whole process. + EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0); +} + +struct notassignable { + int &X; + notassignable(int &XRef) : X(XRef) {} +}; + +TEST(StaticVectorCustomTest, NoAssignTest) { + int X = 0; + StaticVector vec; + vec.push_back(notassignable(X)); + X = 42; + EXPECT_EQ(42, vec.pop_back_val().X); +} + +TEST(StaticVectorCustomTest, CheckedNoAssignTest) { + int X = 0; + StaticVector vec; + auto Ref = vec.checked_push_back(notassignable(X)); + + EXPECT_TRUE(bool(Ref)); + if (!Ref) { + consumeError(Ref.takeError()); + return; + } + + X = 42; + + auto Copy = vec.checked_pop_back_val(); + + EXPECT_TRUE(bool(Copy)); + if (!Copy) { + consumeError(Copy.takeError()); + return; + } + + EXPECT_EQ(42, Copy->X); +} + +struct MovedFrom { + bool HasValue; + MovedFrom() : HasValue(true) {} + MovedFrom(MovedFrom &&M) : HasValue(M.HasValue) { M.HasValue = false; } + MovedFrom &operator=(MovedFrom &&M) { + HasValue = M.HasValue; + M.HasValue = false; + return *this; + } +}; + +TEST(StaticVectorTest, MidInsert) { + StaticVector V; + V.push_back(MovedFrom()); + V.insert(V.begin(), MovedFrom()); + for (MovedFrom &M : V) + EXPECT_TRUE(M.HasValue); +} + +TEST(StaticVectorTest, CheckedMidInsert) { + StaticVector V; + auto Ref = V.checked_push_back(MovedFrom()); + + EXPECT_TRUE(bool(Ref)); + if (!Ref) { + consumeError(Ref.takeError()); + return; + } + + auto I = V.checked_insert(V.begin(), MovedFrom()); + + EXPECT_TRUE(bool(I)); + if (!I) { + consumeError(I.takeError()); + return; + } + + EXPECT_EQ(V.begin(), *I); + + for (MovedFrom &M : V) + EXPECT_TRUE(M.HasValue); +} + +enum EmplaceableArgState { + EAS_Defaulted, + EAS_Arg, + EAS_LValue, + EAS_RValue, + EAS_Failure +}; + +template struct EmplaceableArg { + EmplaceableArgState State; + EmplaceableArg() : State(EAS_Defaulted) {} + EmplaceableArg(EmplaceableArg &&X) + : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {} + EmplaceableArg(EmplaceableArg &X) + : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {} + + explicit EmplaceableArg(bool) : State(EAS_Arg) {} + +private: + EmplaceableArg &operator=(EmplaceableArg &&) = delete; + EmplaceableArg &operator=(const EmplaceableArg &) = delete; +}; + +enum EmplaceableState { ES_Emplaced, ES_Moved }; +struct Emplaceable { + EmplaceableArg<0> A0; + EmplaceableArg<1> A1; + EmplaceableArg<2> A2; + EmplaceableArg<3> A3; + EmplaceableState State; + + Emplaceable() : State(ES_Emplaced) {} + + template + explicit Emplaceable(A0Ty &&A0) + : A0(std::forward(A0)), State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1) + : A0(std::forward(A0)), A1(std::forward(A1)), + State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2) + : A0(std::forward(A0)), A1(std::forward(A1)), + A2(std::forward(A2)), State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3) + : A0(std::forward(A0)), A1(std::forward(A1)), + A2(std::forward(A2)), A3(std::forward(A3)), + State(ES_Emplaced) {} + + Emplaceable(Emplaceable &&) : State(ES_Moved) {} + Emplaceable &operator=(Emplaceable &&) { + State = ES_Moved; + return *this; + } + +private: + Emplaceable(const Emplaceable &) = delete; + Emplaceable &operator=(const Emplaceable &) = delete; +}; + +TEST(StaticVectorTest, EmplaceBack) { + EmplaceableArg<0> A0(true); + EmplaceableArg<1> A1(true); + EmplaceableArg<2> A2(true); + EmplaceableArg<3> A3(true); + { + StaticVector V; + Emplaceable &back = V.emplace_back(); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_Defaulted); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0)); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(A0); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_LValue); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(A0, A1); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_LValue); + EXPECT_TRUE(back.A1.State == EAS_LValue); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1)); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_RValue); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_LValue); + EXPECT_TRUE(back.A2.State == EAS_RValue); + EXPECT_TRUE(back.A3.State == EAS_LValue); + } + { + StaticVector V; + V.emplace_back(); + V.emplace_back(42); + EXPECT_EQ(2U, V.size()); + EXPECT_EQ(0, V[0]); + EXPECT_EQ(42, V[1]); + } +} + +} // namespace diff --git a/llvm/utils/LLVMVisualizers/llvm.natvis b/llvm/utils/LLVMVisualizers/llvm.natvis --- a/llvm/utils/LLVMVisualizers/llvm.natvis +++ b/llvm/utils/LLVMVisualizers/llvm.natvis @@ -31,6 +31,29 @@ + + + {((pointer)Data)[0]}{*this,view(elt1)} + + , {((pointer)Data)[1]}{*this,view(elt2)} + + , {((pointer)Data)[2]}{*this,view(elt3)} + + , {((pointer)Data)[3]}{*this,view(elt4)} + + , /* {Size - 4} more*/ + empty + {{{*this,view(elt0)}}} + Uninitialized + + Size,d + Capacity,d + + Size + (pointer)Data + + + {U.VAL}