Immunitable data in C ++

Hi, Habr! Much is said about immotable data, but it is difficult to find something about C ++ implementation. And, therefore, I decided to fill this gap in the debut article. Moreover, the D language is, but not in C ++. There will be a lot of code and a lot of letters.

On style - utility classes and metafunctions use names in the STL and boost style, custom classes in the Qt style, which I mostly work with.

Introduction

What is immutable data? Immunitable data is our old friend const , only more strict. Ideally, immobility means context-independent immutability under no circumstances.

Essentially, immutable data should:

ensure physical and logical constancy;
prohibit the assignment of a new value at the compilation stage;

All operations must be performed on the copy, not on the original.

Immunity data came from functional programming and found a place in parallel programming, because they guarantee the absence of side effects.

How can i implement immutable data in C ++?

In C ++, we have (very simplistic):

values - objects of fundamental types, instances of classes (structures, unions), enumerations;
pointers;

links;

arrays

Functions and void does not make sense to be immutable. We also will not make links immutable, for this there is a const reference_wrapper .

As for the rest of the types listed above, wrappers can be made for them (or rather, a non-standard protective substitute). What will be the result? The goal is to do something like a type modifier, retaining the natural semantics for working with objects of this type.

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]

Interface

The general interface is simple - all work is performed by the base class, which is derived from the characteristics (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; };

Barring the assignment operator, we prohibit the moving assignment operator, but do not prohibit the moving constructor.

immutable_impl is something like a switch, but by type (I didn’t do this - it complicates the code too much, and in the simple case it’s not really needed - IMHO).

 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; }; }

As restrictions, explicitly prohibiting all assignment operations (macros help):

 template <typename Type, typename RhsType> constexpr Immutable<Type>& operator Op=(Immutable<Type> &&, RhsType &&) = delete;

Now let's consider how the individual components are implemented.

Immunity Values

Values (hereinafter referred to as value) are objects of fundamental types, instances of classes (structures, unions), and enumerations. For value, there is no class that determines whether a type is a class, structure, or union:

 template <typename Type, bool = std::is_class<Type>::value || std::is_union<Type>::value> class immutable_value;

If yes, then CRTP is used for implementation:

 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; };

Unfortunately, in C ++ there is no operator overload . . Although it is expected in C ++ 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 ), but the question is still open, because the committee found inconsistencies .

Then you could just write:

  constexpr Base operator.() const { return value(); }

But a decision on this issue is expected in March, so for this purpose we are using the operator ():

  constexpr Base operator()() const { return value(); }

Pay attention to the constructor: ~~

  constexpr explicit immutable_value(const Base &value) : Base(value) , m_value(value) { }

both the immutable_value and the base class are initialized there. This allows you to intelligently manipulate immutable_value through operator (). For example:

 QPoint point(100, 500); Immutable<QPoint> test(point); test().setX(1000); //     qDebug() << test().isNull() << test().x() << test().y();

If the type is built-in, the implementation will be one-to-one, with the exception of the base class ( to return to comply with DRY, but somehow I didn’t want to complicate things, especially since immutable_value was done after the rest ...):

 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; };

Immunable Arrays

So far, it seems to be simple and uninteresting, but now let's take up the arrays. It is necessary to do something like std :: array while retaining the natural semantics of working with an array, including working with STL (which can weaken immunity).

The peculiarity of relization is that when the index is addressed to a multidimensional, an array of a lower dimension is returned, also immutable. The array type is recursively instantiated: see operator [], and specific types for iterators, etc. are inferred using 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; }; }

To determine the type of a smaller dimension, the class of characteristics is used:

 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; }; }

which for multidimensional arrays for indexing returns an immutable array of lower dimension.

Comparison operators are very simple:

Comparison operators

 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); }

Immunate Iterator

To work with an immutable array, an imimiable iterator array_iterator is used:

 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); } }      ,     .  ,  - :

Sample code with an immutable array

 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++;

For multidimensional arrays, all the same:

Example with a multidimensional, immutable array

 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; }

Immunable Pointers

Let's try to slightly protect the pointers. In this section, we will look at regular pointers (raw pointers), and then (much further) we will look at smart pointers. SFINAE will be used for smart pointers.

By implementing immutable :: pointer, I’ll say right away that pointer does not delete data, does not count references, but only ensures the immutability of the object. (If the passed pointer is changed or deleted from outside, then this is a breach of contract that cannot be tracked by means of the language (by standard means)). In the end, it is impossible to defend against deliberate sabotage or playing with addresses. The pointer must be correctly initialized.

The immutable :: pointer can work with pointers to pointers of any degree of reference (let's say).

For example:

An example of working with immutable index

 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;

In addition to the above, immutable :: pointer does not support working with C-style strings:

 const char *cstr = "test"; immutable::pointer<decltype(str)> p(cstr); while(*p++) qDebug() << *p;

This code will not work as expected, because immutable :: pointer with increment returns the new immutable :: pointer with a different address, and in the conditional expression the result of the increment will be checked, i.e. the value of the second character of the string.

Let's return to the implementation. The pointer class provides a generic interface and, depending on what Tp is (pointer to pointer or proto pointer), uses a specific implementation of 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; };

The essence is as follows: there was a type T , and for its storage / presentation, a pointer_impl <T , true> implementation is used (template-recursive) , which can be represented as follows:

 pointer_impl<T***, true>{ pointer_impl<T**, true> { pointer_impl<T*, false> { const T *const } } }

Total, it turns out: const T const const * const.

For a simple pointer (which does not point to another pointer), the implementation is as follows:

  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; };

For nested pointers (pointers to pointers):

  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; };

What not to do!

For the following types of pointers special meaning should not be done specialization:

pointer to array (*) [];
pointer to the function (*) (Args ... [...]);
a pointer to a class variable, Class :: a very specific thing, is needed when "witchcraft" with the class, you need to associate with the object;

pointer to a class method (Class ::) (Args ... [...]) [const] [volatile].

Immunable smart pointers

How to determine what is in front of us smart pointer? Smart pointers are implemented by operators * and ->. To determine their presence, we will use SFINAE (we will consider the implementation of SFINAE later):

 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); }; }

I will say right away that through operator ->, alas, using indirect recourse, it is possible to break the immunity, especially if there is mutable data in the class. In addition, the constancy of the return value can be removed, both by the compiler (at type deduction) and by the user.

Implementation - everything is simple here:

 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

What it is and what it is eaten with is no need to explain. Using SFINAE, you can determine the presence of methods in the class, member types, etc., even the presence of overloaded functions (if you specify a call to the desired function with the necessary parameters in the testexpr expression). arg may be empty and not participate in testexpr. It uses SFINAE with types and SFINAE with expressions:

 #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))

And another thing: overloading can be resolved (find the desired overloaded function) if the signatures match, but differ in the const [volatile] or volatile qualifier together with SFINAE in three phases:

1) SFINAE - if yes, then OK

2) SFINAE + QNonConstOverload, if not, then

3) SFINAE + QConstOverload

In the Qt source you can find an interesting and useful thing:

Overload resolution with const

  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; } };

Total

Let's try what happened:

 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];

Operators

Let's remember about the operators! For example, add support for the addition operator:

First, we implement the addition operator of the form Immutable<Type> + Type:

 template <typename Type> inline constexpr Immutable<Type> operator+(const Immutable<Type> &a, Type &&b) { return Immutable<Type>(a.value() + b); }

In C ++ 17 instead of

  return Immutable<Type>(a.value() + b);

can write

 return Immutable(a.value() + b);

Since operator + is commutative, then Type + Immutable<Type> can be implemented in the form:

 template <typename Type> inline constexpr Immutable<Type> operator+(Type &&a, const Immutable<Type> &b) { return b + std::forward<Type>(a); }

And again, through the first form, we implement Immutable<Type> + Immutable<Type> :

 template <typename Type> inline constexpr Immutable<Type> operator+(const Immutable<Type> &a, const Immutable<Type> &b) { return a + b.value(); }

Now we can work:

 Immutable<int> a(1), b(2); qDebug() << (a + b).value() << (a + 1).value() << (1 + a).value();

Similarly, you can define the remaining operations. That's just not necessary to overload the operators receiving the address, &&, ||! Unary +, -,!, ~ Can be useful ... These operations are inherited: (), [], ->, -> , (unary).

Comparison operators must return values of Boolean type: