Привет, Хабр! Об иммутабельных данных немало говориться, но о реализации на С++ найти что-то сложно. И, потому, решил данный восполнить пробел в дебютной статье. Тем более, что в языке D есть, а в С++ – нет. Будет много кода и много букв.
О стиле – служебные классы и метафункции используют имена в стиле STL и boost, пользовательские классы в стиле Qt, с которой я в основном и работаю.
Введение
Что из себя представляют иммутабельные данные? Иммутабельные данные – это наш старый знакомый const, только более строгий. В идеале иммутабельность означает контекстно-независиую неизменяемость ни при каких условиях.
По сути иммутабельные данные должны:
- обеспечивать физическую и логическую константность;
- запрещать присваивание нового значения на этапе компиляции;
все операции должны проводиться над копией, а не над оригиналом.
Иммутабельные данные пришли из функционального программирования и нашли место в параллельном програмировании, т. к. гарантируют отсутсвие побочных эффектов.
Как можно реализовать иммутабельные данные в С++?
В С++ у нас есть (сильно упрощенно):
- значения – объекты фундаментальных типов, экземпляры классов (структур, объединений), перечислений;
- указатели;
ссылки;
массивы.
Функции и void не имеет смысл делать иммутабельными. Ссылки тоже не будем делать иммутабельными, для этого есть const reference_wrapper.
Что касается остальных вышеперечисленных типов, то для них можно сделать обертки (а точнее нестандартный защитный заместитель). Что будет в итоге? Цель сделать как-бы модификатор типа, сохранив естественную семантику для работы с объектами данного типа.
Immutable<int> a(1), b(2); qDebug() << (a + b).value() << (a + 1).value() << (1 + a).value(); int x[] = { 1, 2, 3, 4, 5 }; Immutable<decltype(x)> arr(x); qDebug() << arr[0]
Интерфейс
Общий интерфейс прост – всю работу выполняет базовый класс, который выводится из характеристик (traits):
template <typename Type> class Immutable : public immutable::immutable_impl<Type>::type { public: static_assert(!std::is_same<Type, std::nullptr_t>::value, "nullptr_t cannot used for immutable"); static_assert(!std::is_volatile<Type>::value, "volatile data cannot used for immutable"); using ImplType = typename immutable::immutable_impl<Type>; using BaseClass = typename ImplType::type; using BaseClass::BaseClass; using value_type = typename ImplType::value_type; constexpr Immutable& operator=(const Immutable &) = delete; };
Запрещая оператор присваивания, мы запрещаем перемещающий оператор присваивания, но не запрещаем перемещающий конструктор.
immutable_impl что-то вроде switch, но по типам (не стал делать такой – слишком усложняет код, да и в простом случае он не особо нужен – ИМХО).
namespace immutable { template <typename SrcType> struct immutable_impl { using Type = std::remove_reference_t<SrcType>; using type = std::conditional_t< std::is_array<Type>::value, array<Type>, std::conditional_t < std::is_pointer<Type>::value, pointer<Type>, std::conditional_t < is_smart_pointer<Type>::value, smart_pointer<Type>, immutable_value<Type> > > >; using value_type = typename type::value_type; }; }
В качестве ограничений явно запретив все операции присваивания (макросы помогают):
template <typename Type, typename RhsType> constexpr Immutable<Type>& operator Op=(Immutable<Type> &&, RhsType &&) = delete;
А теперь давайте рассотрим как реализованы отдельные компоненты.
Иммутабельные значения
Под значениями (далее value) понимаются объекты фундаментальных типов, экземпляры классов (структур, объединений), перечислений. Для value у на есть класс, который определяет является ли тип классом, структурой или объединением:
template <typename Type, bool = std::is_class<Type>::value || std::is_union<Type>::value> class immutable_value;
Если да, то для реализации используется используется CRTP:
template <typename Base> class immutable_value<Base, true> : private Base { public: using value_type = Base; constexpr explicit immutable_value(const Base &value) : Base(value) , m_value(value) { } constexpr explicit operator Base() const { return value(); } constexpr Base operator()() const { return value(); } constexpr Base value() const { return m_value; } private: const Base m_value; };
К сожалению, в С++ пока нет перегрузки оператора .. Хотя, это ожидается в С++ 17 (http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0252r0.pdf, http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0252r0.pdf, http://www.open-std.org/JTC1/SC22/wg21/docs/papers/2015/p0060r0.html), но вопрос еще открыт, ибо коммитет нашел нестыковки.
Тогда бы можно было просто написать:
constexpr Base operator.() const { return value(); }
Но решение по этому вопросу ожидается в марте, поэтому для этих целей пока используем оператор ():
constexpr Base operator()() const { return value(); }
Обратите внимание, на конструктор:~~
constexpr explicit immutable_value(const Base &value) : Base(value) , m_value(value) { }
там инициализируется как immutable_value, так и базовый класс. Это позволяет осмысленно манипулировать с immutable_value через operator (). Например:
QPoint point(100, 500); Immutable<QPoint> test(point); test().setX(1000); // не поменяет исходный объект qDebug() << test().isNull() << test().x() << test().y();
Если же тип является встроенным, то реализация будет один-в-один, за исключением базового класса (можно было бы изъвернуться, чтобы соответствовать DRY, но как-то не хотелось усложнять, тем более, что immutable_value делался после остальных...):
template <typename Type> class immutable_value<Type, false> { public: using value_type = Type; constexpr explicit immutable_value(const Type &value) : m_value(value) { } constexpr explicit operator Type() const { return value(); } constexpr Type operator()() const { return value(); } // Base operator . () const // { // return value(); // } constexpr Type value() const { return m_value; } private: const Type m_value; };
Иммутабельные массивы
Пока вроде бы просто и неинтересно, но теперь примемся за массивы. Надо сделать что-то вроде std::array сохранив естест��енную семантику работы с массивом, в том числе для работы с STL (что может ослабить иммутабельность).
Особенность релизации заключается в том, что при обращении по индексу к многомерному возвращается массив меньшей размерности, тоже иммутабельный. Тип массива рекурсивно инстанцируется: см. operator[], а конкретные типы для итераторов и т.д выводятся с помощью array_traits.
namespace immutable { template <typename Tp> class array; template <typename ArrayType> struct array_traits; template <typename Tp, std::size_t Size> class array<Tp[Size]> { typedef Tp* pointer_type; typedef const Tp* const_pointer; public: using array_type = const Tp[Size]; using value_type = typename array_traits<array_type>::value_type; using size_type = typename array_traits<array_type>::size_type; using iterator = array_iterator<array_type>; using const_iterator = array_iterator<array_type>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; constexpr explicit array(array_type &&array) : m_array(std::forward<array_type>(array)) { } constexpr explicit array(array_type &array) : m_array(array) { } ~array() = default; constexpr size_type size() const noexcept { return Size; } constexpr bool empty() const noexcept { return size() == 0; } constexpr const_pointer value() const noexcept { return data(); } constexpr value_type operator[](size_type n) const noexcept { return value_type(m_array[n]); } // рекурсивное инстанцирование для типа меньшей размерности constexpr value_type at(size_type n) const { return n < Size ? operator [](n) : out_of_range(); } const_iterator begin() const noexcept { return const_iterator(m_array.get()); } const_iterator end() const noexcept { return const_iterator(m_array.get() + Size); } const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } const_iterator cbegin() const noexcept { return const_iterator(data()); } const_iterator cend() const noexcept { return const_iterator(data() + Size); } const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } constexpr value_type front() const noexcept { return *begin(); } constexpr value_type back() const noexcept { return *(end() - 1); } private: constexpr pointer_type data() const noexcept { return m_array.get(); } [[noreturn]] constexpr value_type out_of_range() const { throw std::out_of_range("array: out of range");} private: const std::reference_wrapper<array_type> m_array; }; }
Для определения типа меньшей размерности используется класс характеристик:
namespace immutable { template <typename ArrayType, std::size_t Size> struct array_traits<ArrayType[Size]> { using value_type = std::conditional_t<std::rank<ArrayType[Size]>::value == 1, ArrayType, array<ArrayType> // immutable::array >; using size_type = std::size_t; }; }
который для многомерных массивов для при индексировании возвращает иммутабельный массив меньшей размерности.
Операторы сравнения очень просты:
template<typename Tp, std::size_t Size> inline bool operator==(const array<Tp[Size]>& one, const array<Tp[Size]>& two) { return std::equal(one.begin(), one.end(), two.begin()); } template<typename Tp, std::size_t Size> inline bool operator!=(const array<Tp[Size]>& one, const array<Tp[Size]>& two) { return !(one == two); } template<typename Tp, std::size_t Size> inline bool operator<(const array<Tp[Size]>& a, const array<Tp[Size]>& b) { return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); } template<typename Tp, std::size_t Size> inline bool operator>(const array<Tp[Size]>& one, const array<Tp[Size]>& two) { return two < one; } template<typename Tp, std::size_t Size> inline bool operator<=(const array<Tp[Size]>& one, const array<Tp[Size]>& two) { return !(one > two); } template<typename Tp, std::size_t Size> inline bool operator>=(const array<Tp[Size]>& one, const array<Tp[Size]>& two) { return !(one < two); }
Иммутабельный итератор
Для работы с иммутабельным массивом используется иммутабельный итератор array_iterator:
namespace immutable { template <typename Tp> class array; template <typename Array> class array_iterator : public std::iterator<std::bidirectional_iterator_tag, Array> { public: using element_type = std::remove_extent_t<Array>; using value_type = std::conditional_t< std::rank<Array>::value == 1, element_type, array<element_type> >; using ptr_to_array_type = const element_type *; static_assert(std::is_array<Array>::value, "Substitution error: template argument must be array"); constexpr array_iterator(ptr_to_array_type ptr) : m_ptr(ptr) { } constexpr value_type operator *() const { return value_type(*m_ptr);} constexpr array_iterator operator++() { ++m_ptr; return *this; } constexpr array_iterator operator--() { --m_ptr; return *this; } constexpr bool operator == (const array_iterator &other) const { return m_ptr == other.m_ptr; } private: ptr_to_array_type m_ptr; }; template <typename Array> inline constexpr array_iterator<Array> operator++(array_iterator<Array> &it, int) { auto res = it; ++it; return res; } template <typename Array> inline constexpr array_iterator<Array> operator--(array_iterator<Array> &it, int) { auto res = it; --it; return res; } template <typename Array> inline constexpr bool operator != (const array_iterator<Array> &a, const array_iterator<Array> &b) { return !(a == b); } } Отделение массивов от указателей сделано сознательно, несмотря на их близкое родство. В итоге, получим что-то вроде:
int x[5] = { 1, 2, 3, 4, 5 }; int y[5] = { 1, 2, 3, 4, 5 }; immutable::array<decltype(x)> a(x); immutable::array<decltype(y)> b(y); qDebug() << (a == b); const char str[] = "abcdef"; immutable::array<decltype(str)> imstr(str); auto it = imstr.begin(); while(*it) qDebug() << *it++;
Для многомерных массивов все тоже самое:
int y[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } }; int z[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } }; immutable::array<decltype(y)> b(y); immutable::array<decltype(z)> c(z); for(auto row = b.begin(); row != b.end(); ++row) { qDebug() << "(*row)[0]" << (*row)[0]; } for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) qDebug() << b[i][j]; qDebug() << (b == c); for(auto row = b.begin(); row != b.end(); ++row) { for(auto col = (*row).begin(); col != (*row).end(); ++col) qDebug() << *col; }
Иммутабельные указатели
Попробуем слегка обезопасить указатели. В этом разделе рассмотрим обычные указатели (raw pointers), а далее (сильно далее) рассмотрим smart pointers. Для smart pointers будет использоваться SFINAE.
По реализации immutable::pointer скажу сразу, что pointer не удаляет данные, не считает ссылки, а только обеспечивает неизменяемость объекта. (Если переданный указатель изменен или удален из-вне, то это нарушение контракта, которое средствами языка не отследить (стандартными средствами)). В конце-концов, защититься от умышленного вредительства или игры с адресами невозможно. Указатель должен быть корректно инициализирован.
immutable::pointer может работать с указателями на указатели любой степени ссылочности (скажем так).
Например:
immutable::pointer<QApplication*> app(&a); app->quit(); char c = 'A'; char *pc = &c; char **ppc = &pc; char ***pppc = &ppc; immutable::pointer<char***> x(pppc); qDebug() << ***x;
Кроме вышеперечисленного, immutable::pointer не поддерживает работы со строками в стиле С:
const char *cstr = "test"; immutable::pointer<decltype(str)> p(cstr); while(*p++) qDebug() << *p;
Данный код будет работать не так как ожидается, т.к. immutable::pointer при инкременте возвращает новый immutable::pointer с другим адресом, а в условном выражении будет проверяться результат инкремента, т.е. значение второго символа строки.
Вернемся к реализации. Класс pointer предоставляет общий интерфейс и, в зависимости от того что из себя представляет Tp (указатель на указатель или прото указатель) использует конкретную реализации pointer_impl.
template <typename Tp> class pointer { public: static_assert( std::is_pointer<Tp>::value, "Tp must be pointer"); static_assert(!std::is_volatile<Tp>::value, "Tp must be nonvolatile pointer"); static_assert(!std::is_void<std::remove_pointer_t<Tp>>::value, "Tp can't be void pointer"); typedef Tp source_type; typedef pointer_impl<Tp> pointer_type; typedef typename pointer_type::value_type value_type; constexpr explicit pointer(Tp ptr) : m_ptr(ptr) { } constexpr pointer(std::nullptr_t) = delete; // Перегрузка защищает от 0 ~pointer() = default; constexpr const pointer_type value() const { return m_ptr; } /** * @brief operator = необязательное объявление, т.к const *const автоматически * запрещает присваивание. * При попытке присвоить, компиляторы дают несколько избыточных ошибок, * которые могут быть разбросаны по файлам и малоинформативны, * а явное описание " = delete" приводит к тому, что диагностируется * только одна конкретная ошибка */ pointer& operator=(const pointer&) = delete; constexpr /*immutable<value_type>*/ value_type operator*() const { return *value(); } constexpr const pointer_type operator->() const { return value(); } // добавим неоднозначности template <typename T> constexpr operator T() = delete; template <typename T> constexpr operator T() const = delete; /** * @brief operator [] не реализован сознательно, чтобы не смешивать массивы * и указатели. * * Использование типов-аргументов по-умолчанию помогают компилятору * дать более короткое и конкретное сообщение об ошибке * (использовании удаленной функции) * @return */ template <typename Ret = std::remove_pointer_t<Tp>, typename IndexType = ssize_t> constexpr Ret operator[](IndexType) const = delete; constexpr bool operator == (const pointer &other) const { return value() == other.value(); } constexpr bool operator < (const pointer &other) const { return value() < other.value(); } private: const pointer_type m_ptr; };
Суть следующая: был тип T , а для его хранения/представления используется (шаблонно-рекурсивно) реализация pointer_impl<T , true>, что можно изобразить так:
pointer_impl<T***, true>{ pointer_impl<T**, true> { pointer_impl<T*, false> { const T *const } } }
Итого, получается: const T const const *const.
Для простого указателя (который не указывает на другой указатель) реализация следующая:
template <typename Type> class pointer_impl<Type, false> { public: typedef std::remove_pointer_t<Type> source_type; typedef source_type *const pointer_type; typedef source_type value_type; constexpr pointer_impl(Type value) : m_value(value) { } constexpr value_type operator*() const noexcept { return *m_value; // * для обычных указателей } constexpr bool operator == (const pointer_impl &other) const noexcept { return m_value == other; } constexpr bool operator < (const pointer_impl &other) const noexcept { return m_value < other; } constexpr const pointer_type operator->() const noexcept { using class_type = std::remove_pointer_t<pointer_type>; static_assert(std::is_class<class_type>::value || std::is_union<class_type>::value , "-> used only for class, union or struct"); return m_value; } private: const pointer_type m_value; };
Для вложенных указателей (указатели на указатели):
template <typename Type> class pointer_impl<Type, true> { public: typedef std::remove_pointer_t<Type> source_type; typedef pointer_impl<source_type> pointer_type; typedef pointer_impl<source_type> value_type; constexpr /* implicit */ pointer_impl(Type value) : m_value(*value) { // /\ remove pointer } constexpr bool operator == (const pointer_impl &other) const { return m_value == other; // рекурсивное инстанцирование } constexpr bool operator < (const pointer_impl &other) const { return m_value < other; // рекурсивное инстанцирование } constexpr value_type operator*() const { return value_type(m_value); // рекурсивное инстанцирование } constexpr const pointer_type operator->() const { return m_value; } private: const pointer_type m_value; };
Для следующих видов указателей особого смысла не стоит делать специализации:
- указатель на массив (*)[];
- указатель на функцию(*)(Args… [...]);
- указатель на переменную класса, Class:: весьма специфичная вещь, нужна при "колдовстве" с классом, нужно связывать с объектом;
-указатель на метод класса (Class::)(Args… [...]) [const][volatile].
Иммутабельные smart pointers
Как определить что перед нами smart pointer? Smart pointers реализуют операторы * и ->. Чтобы определить их наличие воспользуемся SFINAE (реализацию SFINAE рассмотрим позже):
namespace immutable { // is_base_of<_Class, _Tp> template <typename Tp> class is_smart_pointer { DECLARE_SFINAE_TESTER(unref, T, t, t.operator*()); DECLARE_SFINAE_TESTER(raw, T, t, t.operator->()); public: static const bool value = std::is_class<Tp>::value && GET_SFINAE_RESULT(unref, Tp) && GET_SFINAE_RESULT(raw, Tp); }; }
Скажу сразу, что через operator ->, увы, используя косвенное обращение, можно нарушить иммутабельность, особенно если в классе есть mutable данные. Кроме того константность возвращаемого значения может быть снята, как компилятором (при выводе типа), так и пользователем.
Реализация – здесь все просто:
namespace immutable { template <typename Type> class smart_pointer { public: constexpr explicit smart_pointer(Type &&ptr) noexcept : m_value(std::forward<Type>(ptr)) { } constexpr explicit smart_pointer(const Type &ptr) : m_value(ptr) { } constexpr const auto operator->() const { const auto res = value().operator->(); return immutable::pointer<decltype(res)>(res);// in C++17 immutable::pointer(res); } constexpr const auto operator*() const { return value().operator*(); } constexpr const Type value() const { return m_value; } private: const Type m_value; }; }
SFINAE
Что это такое и с чем его едят лишний раз объяснять не надо. С помощью SFINAE можно определить наличие в классе методов, типов-членов и т.д, даже наличие перегруженных функций (если задать в выражении testexpr вызов нужной функции с необходимыми параметрами). arg может быть пустым и не участвовать в testexpr. Здесь используется SFINAE с типами и SFINAE с выражениями:
#define DECLARE_SFINAE_BASE(Name, ArgType, arg, testexpr) \ typedef char SuccessType; \ typedef struct { SuccessType a[2]; } FailureType; \ template <typename ArgType> \ static decltype(auto) test(ArgType &&arg) \ -> decltype(testexpr, SuccessType()); \ static FailureType test(...); #define DECLARE_SFINAE_TESTER(Name, ArgType, arg, testexpr) \ struct Name { \ DECLARE_SFINAE_BASE(Name, ArgType, arg, testexpr) \ }; #define GET_SFINAE_RESULT(Name, Type) (sizeof(Name::test(std::declval<Type>())) == \ sizeof(typename Name::SuccessType))
И еще: перегрузку можно разрешить (найти нужную перегруженную функцию) если сигнатуры совпадают, но отличаются квалификатором const [ volatile ] или volatile совместно с SFINAE в три фазы:
1) SFINAE — если есть, то ОК
2) SFINAE + QNonConstOverload, если не получилось, то
3) SFINAE + QConstOverload
В исходниках Qt можно найти интересную и полезную вещь:
template <typename... Args> struct QNonConstOverload { template <typename R, typename T> Q_DECL_CONSTEXPR auto operator()(R (T::*ptr)(Args...)) const Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } template <typename R, typename T> static Q_DECL_CONSTEXPR auto of(R (T::*ptr)(Args...)) Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } }; template <typename... Args> struct QConstOverload { template <typename R, typename T> Q_DECL_CONSTEXPR auto operator()(R (T::*ptr)(Args...) const) const Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } template <typename R, typename T> static Q_DECL_CONSTEXPR auto of(R (T::*ptr)(Args...) const) Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } }; template <typename... Args> struct QOverload : QConstOverload<Args...>, QNonConstOverload<Args...> { using QConstOverload<Args...>::of; using QConstOverload<Args...>::operator(); using QNonConstOverload<Args...>::of; using QNonConstOverload<Args...>::operator(); template <typename R> Q_DECL_CONSTEXPR auto operator()(R (*ptr)(Args...)) const Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } template <typename R> static Q_DECL_CONSTEXPR auto of(R (*ptr)(Args...)) Q_DECL_NOTHROW -> decltype(ptr) { return ptr; } };
Итог
Попробуем что получилось:
QPoint point(100, 500); Immutable<QPoint> test(point); test().setX(1000); // не поменяет исходный объект qDebug() << test().isNull() << test().x() << test().y(); int x[] = { 1, 2, 3, 4, 5 }; Immutable<decltype(x)> arr(x); qDebug() << arr[0];
Операторы
Давате вспомним про операторы! Например, добавим поддержку оператора сложения:
Сначала реализуем оператор сложения вида Immutable<Type> + Type:
template <typename Type> inline constexpr Immutable<Type> operator+(const Immutable<Type> &a, Type &&b) { return Immutable<Type>(a.value() + b); }
В С++17 вместо
return Immutable<Type>(a.value() + b);
можно записать
return Immutable(a.value() + b);
Т.к. оператор + коммутативен, то Type + Immutable<Type> можно реализовать в виде:
template <typename Type> inline constexpr Immutable<Type> operator+(Type &&a, const Immutable<Type> &b) { return b + std::forward<Type>(a); }
И снова, через первую форму реализуем Immutable<Type> + Immutable<Type>:
template <typename Type> inline constexpr Immutable<Type> operator+(const Immutable<Type> &a, const Immutable<Type> &b) { return a + b.value(); }
Теперь можем работать:
Immutable<int> a(1), b(2); qDebug() << (a + b).value() << (a + 1).value() << (1 + a).value();
Аналогично можно определить остальные операции. Вот только не надо перегружать операторы получения адреса, &&, ||! Унарные +, -, !, ~ могут пригодиться… Эти операции наследуются: (), [], ->, ->, (унарный).
Операторы сравнения должны возвращать значения булевского типа:
template <typename Type> inline constexpr bool operator==(const Immutable<Type> &a, const Immutable<Type> &b) { return a.value() == b.value(); } template <typename Type> inline constexpr bool operator!=(const Immutable<Type> &a, const Immutable<Type> &b) { return !(a == b); } template <typename Type> inline constexpr bool operator>(const Immutable<Type> &a, const Immutable<Type> &b) { return a.value() > b.value(); } template <typename Type> inline constexpr bool operator<(const Immutable<Type> &a, const Immutable<Type> &b) { return b < a; } template <typename Type> inline constexpr bool operator>=(const Immutable<Type> &a, const Immutable<Type> &b) { return !(a < b); } template <typename Type> inline constexpr bool operator<=(const Immutable<Type> &a, const Immutable<Type> &b) { return !(b < a); }
